ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning

Stefano Goria

cs.LGAug 18, 2026

ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning

Authors: Stefano Goria

Organizations: AIM Research Lab

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: The ClosureBench pipeline. Generation (top): graphs are sampled and a program over the task’s primitives computes verified ground truth (we use Ein, § 2.5 ). Evaluation (bottom): models receive only natural-language questions and produce JSON answers scored against precomputed ground truth. Models never see the programs.

Primitive	Definition	Example question	Categories
Degree	$\sum_{j}A[i,j]$	how many does $X$ point to?	degree_count, degree_max
Reachability	$\mathrm{TC}[X,Y]$	can $X$ reach $Y$ ?	reachability, has_path
Reachable-set size	$\|R(X)\|$	how many can $X$ reach?	reach_then_count, reach_then_filter
Set operations	$R(X)\cap R(Y)$ , $R(X)\setminus R(Y)$	reachable from $X$ but not $Y$ ?	set_intersect, set_difference, negative_reach
Triangles	$\mathrm{trace}(A^{3})/6$	how many triangles?	triangle_count, triangle_in_subgraph
Connectivity (SCC)	$\mathrm{TC}[i,j]\wedge\mathrm{TC}[j,i]$	are $X,Y$ mutually reachable?	scc_same, scc_then_count

Table 1: Reasoning primitives, the questions they answer, and the categories that use them.

A

is the adjacency matrix;

R(X)

is the set of nodes reachable from

X

Level	Name	Steps	Test	Representative Categories
L1	Atomic	1	550	triangle count, reachability, degree, ancestor, set ops
L2	Chain	2–3	400	reach-then-count, SCC-then-count, kinship chain
L3	Composition	3–5	350	conditional, multi-query, aggregate-over-set

Table 2: Task taxonomy. Each level increases the number of chained reasoning operations. L1–L3 are included in the current release (1,300 instances total). SCC: strongly connected component.

Figure 2: Measuring memorisation (Qwen3-4B fine-tuned on 1,300 answer pairs). The gap between seen (78.5%) and held-out (59.2%) accuracy (19.3pp by epoch 5) is a memorisation signal that a fixed benchmark cannot measure.

Figure 3: Accuracy by compositional level across all evaluated models. Every model degrades from L1 to L3 except Ein SFT (94%

\to

93%). Dotted lines separate open models, frontier API, and program synthesis.

Open models (direct mode)
Model	L1	L2	L3	Overall
Qwen2.5-1.5B	35.1	22.2	15.4	25.8
Qwen3.5-2B	40.2	31.8	23.1	33.0
Qwen3-4B	47.8	43.0	22.3	39.5
Qwen3.5-9B	52.0	46.2	26.3	43.3
Frontier API (direct mode)

Table 3: Main results on ClosureBench (lenient scoring). All models are evaluated on the same 1,300-instance held-out split, spanning graph sizes

n{=}4

–

10

; accuracy is averaged over that range ( Table 4 breaks it out by

n

). All methods degrade from L1 to L3 except Ein SFT, which stays nearly flat.

Figure 4: Accuracy vs. graph size (

n

) at each compositional level, for the open models on a dedicated size sweep (

n

up to 20). L1 degrades gently; L3 steeply. Size and depth compound rather than add.

Model	$n{=}4$	$n{=}6$	$n{=}8$	$n{=}10$
o3	95	90	94	94
Gemini 2.5 Flash	92	89	85	79
GPT-4.1 (CoT)	92	88	85	75
Claude Sonnet 4 (CoT)	92	81	78	78

Table 4: Held-out overall accuracy (%) by graph size

n

(lenient). Every frontier model degrades with

n

except o3, whose L1/L2 stay near-perfect. The decline is driven by the compositional (L3) tasks, which drop sharply once

n

exceeds

{\sim}5

and then plateau rather than declining smoothly; per-

n

L3 estimates (

{\sim}

50 instances each) are too noisy to tabulate. Modes: o3 and Gemini direct, GPT-4.1 and Claude CoT.

Model	Mode	Tok/ans	Acc. (%)	Tok/correct
Qwen3-4B	Direct	38	39.5	96
Qwen3.5-9B	Direct	52	43.3	120
GPT-4.1	Direct	7	52.4	13
Gemini Flash	Direct	1,261	87.4	1,443
GPT-4.1	CoT	431	86.2	500
o3	Direct	844	92.8	910

Table 5: Token cost per answer and cost-efficiency (tokens per correct answer). CoT reasoning consumes 10–50

\times

more tokens than direct mode, with superlinear scaling at higher compositional levels.

\star

Figure 5: Token efficiency: accuracy vs. mean tokens per answer (log scale). Ein SFT (star) achieves the highest accuracy at moderate token cost.

Method	Exec. rate	Seen	Held-out	Gap
Qwen3-4B (base, direct NL)	100%	34.5%	34.2%	—
Qwen3-4B (answer SFT, direct)	100%	78.5%	59.2%	19.3pp
Qwen3-4B (Python+NetworkX SFT)	97.8%	96.1%	92.6%	3.5pp
Qwen3-4B (Ein SFT)	99.6%	98.0%	94.3%	3.7pp

Table 6: Direct answering vs. program synthesis on the same model (Qwen3-4B, matched LoRA configuration). Trained on the same data, fine-tuning to emit answers memorises (19.3pp seen/held-out gap), while fine-tuning to emit programs generalises (3.5–3.7pp gap). The fair within-model comparison is the fine-tuned-direct row against the program-synthesis rows.

Model	NL	JSON edges	Adj. matrix
Qwen2.5-1.5B	26.5	26.5	24.5
Qwen3.5-2B	28.5	29.5	19.5
Qwen3-4B	40.0	38.0	24.5
Qwen3.5-9B	47.5	51.0	30.0
GPT-4.1	53.0	59.5	44.0
Gemini 2.5 Flash	84.5	88.5	91.0

Table 7: Accuracy (%) across three graph encodings on the same 200-instance subset (direct mode, lenient scoring). The compositional penalty survives every encoding; encoding preference is capacity-dependent (note the adjacency-matrix column reverses sign between small and frontier models).

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Level	Category	Held-out (%)
L1	triangle_count	82
L1	reachability	98
L1	negative_reach	96
L1	degree_count	84
L1	degree_max	94
L1	scc_same	96

Appendix

Table 8: Ein SFT (Qwen3-4B + LoRA) held-out accuracy by category (50 instances per category). Categories below 90% are shown in red .

result_type	JSON value	Example	Categories
boolean	true / false	{"answer": true}	reachability, scc_same, conditional
integer	non-negative integer	{"answer": 3}	triangle_count, degree_count, *_then_count
float	finite real	{"answer": 2.43}	aggregate_over_set, mixed_domain
set	JSON array of strings	{"answer": ["a","c"]}	set_intersect, set_difference, ancestor, sibling, cousin
string	one node label	{"answer": "kiwi"}	degree_max, degree_then_reach
compound	JSON object	{"answer": {"reach": true, "deg": 1}}	multi_query

Appendix

Table 9: JSON output schema. Each instance carries a single result_type ; the model’s "answer" field must conform to the corresponding JSON value. Empty sets and zero counts are valid answers.

Method	Strict	Lenient	Gap
Open models (direct)
Qwen2.5-1.5B	21.3	25.8	$+4.5$
Qwen3.5-2B	27.8	33.0	$+5.2$
Qwen3-4B	33.2	39.5	$+6.3$
Qwen3.5-9B	37.8	43.3	$+5.5$
Frontier API

Appendix

Table 10: Strict vs. lenient accuracy (%) for every evaluated configuration on the same 1,300 held-out instances (seen split for the two SFT rows so marked). Strict counts source-inclusion ambiguities as wrong; lenient accepts the documented

\pm 1

\pm

source corner cases. The method ordering is preserved under both scorings.

Method	Strict	Lenient-only	Wrong	Format err.	No ans.
GPT-4.1 (direct)	46.1	6.3	43.1	4.5	0.0
GPT-4.1 (CoT)	84.6	1.6	10.7	2.5	0.6
GPT-4.1-mini (direct)	43.9	5.3	44.6	6.2	0.0
GPT-4.1-mini (CoT)	84.5	1.3	10.5	3.3	0.4
Claude Sonnet 4 (direct)	79.1	2.6	14.6	3.7	0.0
Claude Sonnet 4 (CoT)	82.0	1.6	12.2	4.2	0.0

Appendix

Table 11: Per-method decomposition of held-out responses (1,300 instances). Columns are mutually exclusive and sum to 100% up to rounding. “Lenient-only” counts responses correct under lenient but not strict scoring.

LLM Reasoning with Graphs

Large language model reasoning with graphs uses structured relationships to support multi-step inference, evidence retrieval, and planning.

See all 198 papers

Aug 2, 2026

Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models

Graph reasoning provides a promising testbed for evaluating the reasoning ability of large language models (LLMs), as graph instances can be programmatically generated, structurally controlled, and naturally scaled to long-input settings. However, existing graph reasoning benchmarks have limited coverage of data complexity, rely heavily on manual construction, and lack unified evaluation across text-based and code-based reasoning modes. To address these limitations, we propose {\dataset}, a five-stage semi-automatic framework for constructing complex graph reasoning benchmarks. It expands benchmark coverage along five dimensions: Graph Size, Task Complexity, Task Description, Graph Loading, and Task Source. The framework uses an LLM-based data generator to automatically produce task descriptions, graph data, reference solutions, graph-loading scripts, question forms, and evaluation scripts, while retaining human validation at key quality-control stages. Based on it, we construct a benchmark with

202

tasks and evaluate LLMs under text-based, code-based, and augmented reasoning settings. Experiments show that the complexity dimensions reveal model limitations that are less visible in existing benchmarks; existing fine-tuned models struggle to generalize to GraphGym, whereas retrieval-augmented methods show scenario-dependent adaptability, improving textual reasoning but not consistently improving coding reasoning. These findings suggest that ours serves as a challenging and diagnostic benchmark for graph reasoning and provides empirical guidance for future enhancement methods. Code and dataset will be published soon.

Fali Wang, Ali Al-Lawati, Iliyas Bektas +5

The Pennsylvania State University, University Park, PA, USA · Rensselaer Polytechnic Institute, Troy, NY, US

LLM Evaluation LLM Reasoning with Graphs Synthetic Benchmark Generation Implicit Reasoning in Language Models LLMs for Graph Learning

Ask PDF

Sep 10, 2026

GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs

Large Language Models (LLMs) are increasingly asked to reason over structured data such as graphs, yet how reliably they can carry out multi-step graph algorithms in language remains unclear. Existing evaluations tend to use simple tasks on small graphs, to score code generation rather than reasoning over the graph itself, or to fix a single input format. We introduce Graph Theory Bench (GT Bench), a benchmark covering 24 classical graph problems in 44 task-structure settings, with over 100,000 examples across four representations: natural language, structured language, adjacency list, and adjacency matrix. Evaluating eight LLMs on GT Bench shows that accuracy is strongly tied to the input representation, that the best representation shifts with graph density, size, and topology as well as with the model, and that this sensitivity persists, attenuated, in the strongest reasoning models. Building on these observations, we propose the Graph Theory Agent (GTA), which pairs a preference-trained representation selector with plan-and-decompose scaffolding around a frozen executor LLM. GTA lifts Phi-4 from 53.5% to 69.1% on the benchmark's easy split and from 33.0% to 41.5% on its hard split, outperforming eight prompting and agent baselines, and transfers without retraining to GraCoRe and NLGraph. Code for benchmark generation and evaluation: https://github.com/xzx34/GTA. The project homepage is available at https://xzx34.github.io/gta/.

Zixiang Xu, Yanbo Wang, Chenxi Wang +6

University of Southern California · University of California, Los Angeles · Mohamed bin Zayed University of Artificial Intelligence +2

LLM Reasoning with Graphs LLM Agents Graph Reasoning Algorithmic Reasoning

Ask PDF

May 8, 2026

MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMs

We introduce MathConstraint, a hard, adaptive benchmark for evaluating the combinatorial reasoning capabilities of LLMs. We combine constraint satisfaction problems with rigorous solver-based verification and design an adaptive generator to create instances that remain challenging as the LLMs improve in their reasoning capabilities. Unlike existing benchmarks that quickly saturate on fixed datasets or use LLM-as-a-judge for checking solutions,MathConstraint uses parameterized problem types that enable scalable generation of arbitrarily difficult and automatically verifiable instances. We release MathConstraint-Easy (

266

instances), on which frontier models achieve between

72.6\%

(gemini-3.1-flash-lite) and

87.6\%

(gpt-5.5) accuracy, and MathConstraint (

329

instances) on which the same models drop to between

18.5\%

(claude-4.6-sonnet) and

66.9\%

(gpt-5.5) accuracy, demonstrating the resilience of our benchmark generator against rapid progress in LLM reasoning capabilities. We evaluate 12 frontier and open-weight models with and without access to a sandboxed Python environment that includes generic SAT/SMT solvers. Tool access roughly doubles frontier accuracy on MathConstraint (mean

+28

pp; up to

+52

pp for claude-4.6-sonnet). Further, halving the tool-call budget from

8

4

rounds erases up to

37

points -- a sensitivity that most single-budget benchmarks miss. We release the generator, dataset, and evaluation harness as a robust environment for studying combinatorial reasoning and tool-use behavior under adversarially-tunable difficulty.

Viresh Pati, Zhengyu Li, Piyush Jha +3

Georgia Institute of Technology, USA · KNOWIDEA Technologies

Mathematical Reasoning Benchmarks Synthetic Benchmark Generation Mathematical Reasoning LLM Tool Use Constraint Programming Mathematical Problem Generation

Ask PDF

Abstract

LLM Reasoning with Graphs

Explore similar work

Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models

GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs

MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMs