ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning

On September 7, 2026, the arXiv cs.LG preprint arXiv:2608.18242v2 officially released ClosureBench, a constructive benchmark for graph reasoning. This benchmark avoids overfitting of models to a fixed test set by generating instances as needed. Tasks are constructed using clear logical primitives, and answers are verified by executing code to ensure accurate truth values with unlimited instance supply. ClosureBench covers 26 task categories, including three levels of complexity and three independent difficulty dimensions (graph size, edge density, and query depth). Evaluation shows that accuracy decreases with increasing graph size and query depth, from open-source models with 1.5B parameters to advanced systems such as o3, GPT-4.1, Gemini 2.5, and Claude Sonnet 4. The difficulty mainly stems from the propagation of rules on the graph during multi-step reasoning, rather than from the surface form or reasoning rules themselves; a finely tuned 4B model maintains an accuracy of approximately 93% through output verification programs...