# ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning

arXiv: https://arxiv.org/abs/2608.18242 · HTML: https://mlsanity.com/paper/2608.18242/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 17 of its 29 references that are in the map.
- First posted on arXiv 18 Aug 2026.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 17 of 17)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought](https://mlsanity.com/paper/2210.01240/) (2022)
- [The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity](https://mlsanity.com/paper/2506.06941/) (2025)
- [LiveBench: A Challenging, Contamination-Limited LLM Benchmark](https://mlsanity.com/paper/2406.19314/) (2024)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [FOLIO: Natural Language Reasoning with First-Order Logic](https://mlsanity.com/paper/2209.00840/) (2022)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBench](https://mlsanity.com/paper/2409.13373/) (2024)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [Inductive or Deductive? Rethinking the Fundamental Reasoning Abilities of LLMs](https://mlsanity.com/paper/2408.00114/) (2024)
- [G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning](https://mlsanity.com/paper/2505.18499/) (2025)
- [GraCoRe: Benchmarking Graph Comprehension and Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2407.02936/) (2024)
- [BeyondBench: Contamination-Resistant Evaluation of Reasoning in Language Models](https://mlsanity.com/paper/2509.24210/) (2025)
- [Tensor Logic: The Language of AI](https://mlsanity.com/paper/2510.12269/) (2025)
- [Rethinking and Benchmarking Large Language Models for Graph Reasoning](https://mlsanity.com/paper/2509.24260/) (2025)

## Abstract (arXiv)

Large language models fail on multi-step compositional reasoning, but measuring that failure is hard, because new models are trained on the benchmarks used to evaluate them. A fixed test set becomes a memorisation check soon after release. Constructive benchmarks avoid this by generating instances on demand. We introduce ClosureBench, a constructive benchmark for graph-relational logical reasoning. Each task is built from explicit primitives (reachability, degree, set operations, connectivity, aggregation), and its reference answer is computed by executing code that implements that logic exactly. Ground truth is therefore verified, and the supply of fresh instances is unlimited. The benchmark spans 26 task categories at three compositional levels, with three independent difficulty axes: graph size, edge density, and query depth. We evaluate models from 1.5B open weights to frontier systems (o3, GPT-4.1, Gemini 2.5, Claude Sonnet 4). Accuracy falls as graph size and query depth increase, and the two axes interact. The difficulty does not lie in the surface form, since it persists when the graph is given as a JSON edge list or an adjacency matrix rather than prose, nor in the reasoning rule, which models state correctly. It lies in carrying that rule out over the graph across many steps. A 4B model fine-tuned to emit verified programs instead of answers stays nearly flat across compositional levels, while every frontier model degrades. o3 falls from 96% on atomic queries to 82% on the most compositional; the 4B model holds at 93% at a fraction of the token cost. The program offloads multi-step execution to a runtime, and the model's remaining errors are almost entirely misread edges. Constructive generation also supports a direct memorisation check, comparing accuracy on seen and fresh instances.