ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning

Researchers introduced ClosureBench, a constructive benchmark for compositional graph-relational reasoning that generates instances on demand with programmatically verified ground truth, avoiding data contamination. Evaluating models from 1.5B to frontier systems (o3, GPT-4.1, Gemini 2.5, Claude Sonnet 4), they found a 19.3 percentage-point accuracy gap between seen and fresh instances for a fine-tuned model, and that a 4B model fine-tuned to emit executable programs achieved 94.3% accuracy on held-out instances, nearly matching frontier models at lower token cost.

arXiv:2608.18242v1 Announce Type: new Abstract: We introduce ClosureBench, a constructive benchmark for compositional graph-relational reasoning with programmatically verified ground truth. Unlike fixed-test-set benchmarks vulnerable to data contamination, ClosureBench generates instances on demand: each task's reference answer is computed by executing a program in the Ein tensor-logic language, ensuring machine-verified correctness. The benchmark spans 26 task categories at three compositional levels L1-L3 , with difficulty controlled along three independent 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 and report three findings. First, because the benchmark can always supply fresh instances, it measures memorisation directly: a model fine-tuned on a fixed test set shows a 19.3 percentage-point gap between its accuracy on seen and on fresh instances, which a static test set cannot reveal. We scope this to supervised fine-tuning on answer pairs, not pretraining contamination. Second, accuracy falls as graph size and query depth increase, and the two interact: models misread the graph from its natural-language description and then reason correctly over the wrong graph, so even the strongest frontier model degrades from atomic to compositional queries. This bottleneck is a property of the reasoning rather than the input format: it persists when the graph is given as a JSON edge list or an adjacency matrix instead of prose. Third, a 4B model fine-tuned to emit executable programs rather than answers stays nearly flat across compositional levels and approaches frontier accuracy 94.3% on held-out instances at a fraction of the token cost. This holds for two program targets, Ein and Python+NetworkX, so it is a property of verified program synthesis rather than of one language.