ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning

# A Constructive Benchmark for Compositional Graph Reasoning
Source: [https://arxiv.org/html/2608.18242](https://arxiv.org/html/2608.18242)
\\nameStefano Goria\\emailstefano@aimresearchlab\.com

###### Abstract

Large language models are widely reported to fail on multi\-step compositional and logical reasoning, and a growing body of work has measured parts of this gap\. Tracking it is itself hard: new models are trained on the benchmarks used to evaluate them, so a fixed test set decays into a memorisation check soon after release, which has motivated*constructive*benchmarks that generate fresh instances on demand\. We introduceClosureBench, a constructive benchmark for probing, in depth and along controllable axes, where language models fail on graph\-relational logical reasoning\. Each task is built from explicit logic primitives—reachability, degree, set operations, connectivity, and aggregation—and its reference answer is computed by executing code that implements that logic exactly, giving programmatically verified ground truth and an unlimited supply of fresh instances\. The benchmark spans 26 task categories at three compositional levels, with three independent difficulty knobs: graph size, edge density, and query depth\.

Evaluating models from 1\.5B open weights to frontier systems \(o3, GPT\-4\.1, Gemini 2\.5, Claude Sonnet 4\), we find that accuracy falls as graph size and query depth increase, and that the two interact: even the strongest frontier model degrades sharply from atomic to compositional queries\. The difficulty is neither the surface form—it persists when the graph is given as a JSON edge list or an adjacency matrix rather than prose—nor the reasoning rule, which models state correctly, but 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, where every frontier model degrades sharply: o3, the strongest, falls from 96% on atomic queries to 82% on the most compositional, while the 4B model holds at 93%—matching or exceeding the frontier on the hardest tasks at a fraction of the token cost\. The program offloads the multi\-step execution to a runtime, and the model’s residual errors are almost entirely misread edges—the one step it still performs itself\. Constructive generation also supports a direct memorisation check, comparing accuracy on seen versus freshly generated instances\.

Keywords:graph reasoning, compositional generalisation, benchmarks, data contamination, program synthesis

## 1Introduction

Consider a compliance analyst at a bank who must answer a routine but consequential question: can money move from a given customer to a sanctioned entity through any chain of intermediaries? The transactions form a graph—accounts are nodes and a transfer is a directed edge—and the question asks whether a directed path connects the customer to the sanctioned account\. Answering it means chaining several steps: following transfers, tracking which accounts have been reached, and combining the partial results\. A missed path is an undetected sanctions exposure; a spurious one freezes a legitimate account\. This is the kind of multi\-step, relational question that organisations increasingly pose to language models in natural language—and the kind on which language models are reported to be unreliable\.

That report is consistent across settings: models handle single\-step inference well but degrade as a task composes more steps\. A formal analysis of chain\-of\-thought finds accuracy falling as deductions chain\([Saparov and He 2023](https://arxiv.org/html/2608.18242#bib.bib16)\); multi\-hop question answering stays hard when questions genuinely require composing sub\-questions rather than exploiting shortcuts\([Trivedi et al\. 2022](https://arxiv.org/html/2608.18242#bib.bib20);[Ho et al\. 2020](https://arxiv.org/html/2608.18242#bib.bib10)\); dedicated logical\-reasoning suites expose systematic errors on nested and first\-order structure\([Hu et al\. 2022b](https://arxiv.org/html/2608.18242#bib.bib12);[Liu et al\. 2020](https://arxiv.org/html/2608.18242#bib.bib13);[Yu et al\. 2020](https://arxiv.org/html/2608.18242#bib.bib24)\); and grade\-school arithmetic loses accuracy under superficial edits, a sign of pattern\-matching rather than a robust procedure\([Mirzadeh et al\. 2024](https://arxiv.org/html/2608.18242#bib.bib15)\)\. The newest reasoning\-tuned models narrow but do not close the gap: OpenAI’s o1 improves sharply on planning benchmarks yet stays far from solving them\([Valmeekam et al\. 2024](https://arxiv.org/html/2608.18242#bib.bib21)\), and on controlled puzzles the strongest reasoning models collapse once compositional complexity crosses a threshold, curtailing their own reasoning effort as problems grow harder\([Shojaee et al\. 2025](https://arxiv.org/html/2608.18242#bib.bib17)\)\. Whether such failures reflect a genuine limit or the way we test for it is itself debated\([Cheng et al\. 2024](https://arxiv.org/html/2608.18242#bib.bib3)\)—a reason to measure them more precisely\.

Precise measurement runs into two obstacles\. First, benchmarks decay: once a test set is public it is absorbed into the next round of training, so a fixed set of questions soon measures recall rather than reasoning—GSM8K\([Cobbe et al\. 2021](https://arxiv.org/html/2608.18242#bib.bib4)\)and MMLU\([Hendrycks et al\. 2021](https://arxiv.org/html/2608.18242#bib.bib9)\)have saturated, their scores can be inflated by training on leaked data\([Zeng et al\. 2024](https://arxiv.org/html/2608.18242#bib.bib26)\), and small surface edits already move them\([Mirzadeh et al\. 2024](https://arxiv.org/html/2608.18242#bib.bib15)\)\. Procedurally generated benchmarks address this by instantiating fresh instances on demand, as in the DyVal family\([Zhu et al\. 2024a](https://arxiv.org/html/2608.18242#bib.bib27);[Zhu et al\. 2024b](https://arxiv.org/html/2608.18242#bib.bib28)\)and monthly\-refreshed suites such as LiveBench\([White et al\. 2024](https://arxiv.org/html/2608.18242#bib.bib23)\)\. Second, the benchmarks that do target graph reasoning—GraphQA\([Fatemi et al\. 2023](https://arxiv.org/html/2608.18242#bib.bib6)\), NLGraph\([Wang et al\. 2023](https://arxiv.org/html/2608.18242#bib.bib22)\), GraphWiz\([Chen et al\. 2024a](https://arxiv.org/html/2608.18242#bib.bib1)\), GraphArena\([Tang et al\. 2024](https://arxiv.org/html/2608.18242#bib.bib19)\), GraCoRe\([Yuan et al\. 2024](https://arxiv.org/html/2608.18242#bib.bib25)\), GraphInstruct\([Luo et al\. 2024](https://arxiv.org/html/2608.18242#bib.bib14)\), and the kinship\-focused CLUTRR\([Sinha et al\. 2019](https://arxiv.org/html/2608.18242#bib.bib18)\)—score answers by string matching\([Chen et al\. 2024b](https://arxiv.org/html/2608.18242#bib.bib2)\)and vary difficulty along a single coarse axis, so they cannot isolate*which*operation a model fails on or*how much*composition breaks it; the choice of graph encoding alone can move accuracy by tens of points\([Fatemi et al\. 2023](https://arxiv.org/html/2608.18242#bib.bib6)\), confounding reasoning with input format\.

The sanctions query is one instance of a general operation: the*transitive closure*of a relation, the set of all pairs joined by a directed path\. Closure recurs far beyond finance—it decides whether a fault propagates through a dependency graph, whether a change reaches a downstream service, or who descends from whom in a lineage\. Related operations recur just as widely: counting a node’s connections \(degree\), intersecting the sets two sources reach, finding mutually reachable groups \(strongly connected components\), or aggregating a quantity over a reachable set\. We call these graph\-relational*logic primitives*; each is a precise, checkable operation on a graph, and realistic questions compose a handful of them\. Measuring reasoning this precisely means controlling*which*primitives a question uses and*how many*it composes, with a reference answer one can trust\.

ClosureBench—named for that closure operation—provides both\. Each task is a query over one or more logic primitives, and its reference answer is*computed*, not curated: the primitive is executed as a short program—a few lines of tensor logic\([Domingos 2025](https://arxiv.org/html/2608.18242#bib.bib5)\), which expresses graph operations as contractions over the adjacency matrix, run in the Ein language111Ein is an open\-source standalone language, implemented in Rust:[https://github\.com/egolabs\-ai/ein\-lang](https://github.com/egolabs-ai/ein-lang)\.or, equivalently, in Python with NetworkX\.222NetworkX, a Python library for graph algorithms:[https://networkx\.org](https://networkx.org/)\.Because the answer is computed it is exact, and the generator can produce unlimited fresh, contamination\-free instances from independent structural and surface seeds\. The benchmark spans 26 task categories at three compositional levels and exposes three independent difficulty knobs—graph size, edge density, and query depth—so an evaluator can fix two and vary the third to localise where a model breaks\. Models see only a natural\-language question and return a JSON answer; they never see the program behind it\.

We make three contributions:

1. 1\.ClosureBenchitself: a constructive benchmark of 26 graph\-relational categories built from explicit logic primitives, with programmatically computed ground truth, three independent difficulty axes, and surface control \(§[2](https://arxiv.org/html/2608.18242#S2)\)\. Because it supplies unlimited fresh instances, it also gives a direct check for memorisation—the gap between accuracy on seen and on freshly generated instances—which we use to separate recall from reasoning under fine\-tuning \(§[4\.1](https://arxiv.org/html/2608.18242#S4.SS1)\)\.
2. 2\.A diagnostic of where language models fail on these tasks: accuracy falls as graph size and query depth grow and the two interact, and the failure is in executing the computation over the graph—it survives JSON and adjacency\-matrix encodings and is not recovered by extra reasoning tokens—rather than in reading the graph or stating the rule \(§[4\.2](https://arxiv.org/html/2608.18242#S4.SS2)–[4\.6](https://arxiv.org/html/2608.18242#S4.SS6)\)\.
3. 3\.Program synthesis as a level\-invariant, low\-cost alternative—emitting a program instead of an answer, an approach that has driven recent gains in graph reasoning\([Zhu et al\. 2025](https://arxiv.org/html/2608.18242#bib.bib29);[Guo et al\. 2025](https://arxiv.org/html/2608.18242#bib.bib8)\): a 4B model fine\-tuned to emit verified programs stays nearly flat across compositional levels, where every frontier model degrades sharply, at a fraction of the token cost, with Ein and Python targets giving the same result \(§[4\.5](https://arxiv.org/html/2608.18242#S4.SS5)\)\.

## 2ClosureBench Design

ClosureBenchis built around four design principles, each addressing a specific failure mode of existing benchmarks:\(1\) Programmatic ground truth—every reference answer is computed by executing the task’s logic primitives as a program, eliminating human labelling errors;\(2\) Constructive generation—new instances are generated on demand, so the benchmark never runs out of fresh evaluation data;\(3\) Independent complexity axes—three orthogonal parameters let evaluators isolate specific failure modes;\(4\) Domain grounding—tasks are framed in real\-world verticals to test whether models handle contextualised graph descriptions\.

GenerationGraphSamplingProgram\(primitives\)GroundTruthNLQuestionEvaluationModelJSONAnswerScoreFigure 1:TheClosureBenchpipeline\.*Generation*\(top\): graphs are sampled and a program over the task’s primitives computes verified ground truth \(we use Ein, §[2\.5](https://arxiv.org/html/2608.18242#S2.SS5)\)\.*Evaluation*\(bottom\): models receive only natural\-language questions and produce JSON answers scored against precomputed ground truth\. Models never see the programs\.### 2\.1Reasoning Primitives and Query Types

EveryClosureBenchtask is built from a small set of graph\-relational primitives over a graph’s adjacency matrix\. We define the primitives and the query types they induce below, and defer their computation to §[2\.5](https://arxiv.org/html/2608.18242#S2.SS5)\.

Represent a directed graph onnnnodes by its adjacency matrixA∈\{0,1\}n×nA\\in\\\{0,1\\\}^\{n\\times n\}, withA⁡\[i,j\]=1A\[i,j\]\{=\}1iff there is an edgei→ji\{\\to\}j\. Every reference answer is a function ofAAand a few designated query nodes\. The primitives are:

- •Degree\.The out\-degree of nodeiiis the row sumdout​\(i\)=∑jA⁡\[i,j\]d\_\{\\mathrm\{out\}\}\(i\)=\\sum\_\{j\}A\[i,j\]; the in\-degree is the column sum\.*Query:*“Alice pays Bob, Carol, and Dave\. How many accounts does Alice pay?” \(dout​\(Alice\)=3d\_\{\\mathrm\{out\}\}\(\\text\{Alice\}\)\{=\}3\)\.
- •Reachability \(transitive closure\)\.Nodeiireachesjjif a directed path connects them\. The closure matrixTC⁡\(A\)\\mathrm\{TC\}\(A\)hasTC⁡\[i,j\]=1\\mathrm\{TC\}\[i,j\]\{=\}1iffiireachesjj; equivalentlyTC=⋁k=1n−1Ak\\mathrm\{TC\}=\\bigvee\_\{k=1\}^\{n\-1\}A^\{k\}under Boolean arithmetic\.*Query:*“XXsuppliesYY, andYYsuppliesZZ; is there a supply path fromXXtoZZ?”
- •Reachable set\.R⁡\(X\)=\{j:TC⁡\[X,j\]=1\}R\(X\)=\\\{j:\\mathrm\{TC\}\[X,j\]\{=\}1\\\}is the set of nodes reachable fromXX\.*Query:*“How many nodes are reachable fromXX?” \(\|R⁡\(X\)\|\|R\(X\)\|\)\.
- •Set operations\.Queries combine reachable sets with intersectionR⁡\(X\)∩R⁡\(Y\)R\(X\)\\cap R\(Y\), differenceR⁡\(X\)∖R⁡\(Y\)R\(X\)\\setminus R\(Y\), or complement\.*Query:*“Which nodes canXXreach thatYYcannot?” \(R⁡\(X\)∖R⁡\(Y\)R\(X\)\\setminus R\(Y\)\)\.
- •Triangles\.For an undirected graph the triangle count istrace⁡\(A3\)/6\\mathrm\{trace\}\(A^\{3\}\)/6\(each triangle closes six length\-3 walks\)\.*Query:*“How many groups of three nodes that all connect to one another are there?”
- •Strongly connected components \(SCC\)\.Nodesi,ji,jshare an SCC iff each reaches the other,TC⁡\[i,j\]∧TC⁡\[j,i\]\\mathrm\{TC\}\[i,j\]\\wedge\\mathrm\{TC\}\[j,i\]\.*Query:*“CanXXandYYeach reach the other?”
- •Ancestry and kinship\.On a directed acyclic parent→\\tochild graph, ancestry is reachability, and kinship terms follow from it: an ancestor ofXXreachesXX; siblings share a parent; cousins share a grandparent\.*Query:*“Eve is a parent of Carol and Tina; who is the oldest ancestor of Tina?”, or “Are Carol and Dave cousins?”
- •Aggregation\.A scalar summary \(sum, mean, or maximum\) over a set, such as the mean out\-degree overR⁡\(X\)R\(X\),1\|R⁡\(X\)\|​∑i∈R⁡\(X\)dout​\(i\)\\tfrac\{1\}\{\|R\(X\)\|\}\\sum\_\{i\\in R\(X\)\}d\_\{\\mathrm\{out\}\}\(i\)\.*Query:*“Among the nodes reachable fromXX, what is their average number of outgoing links?”

A*query type*is defined by which primitives it invokes and how they compose \([Table1](https://arxiv.org/html/2608.18242#S2.T1)\)\. An*atomic*query invokes one primitive: “canXXreachYY?” is a single closure lookup\. A*chain*feeds one primitive’s output into the next: “how many nodes canXXreach?” is reachability followed by a count overR⁡\(X\)R\(X\)\. A*composition*adds control flow: “ifXXcan reachYY, report\|R⁡\(X\)\|\|R\(X\)\|, otherwise−1\-1” runs a reachability test, branches on the result, then counts\. The taxonomy \(§[2\.2](https://arxiv.org/html/2608.18242#S2.SS2)\) groups tasks by this structure, and the complexity axes \(§[2\.3](https://arxiv.org/html/2608.18242#S2.SS3)\) vary it independently\.

Table 1:Reasoning primitives, the questions they answer, and the categories that use them\.AAis the adjacency matrix;R⁡\(X\)R\(X\)is the set of nodes reachable fromXX\.
### 2\.2Task Taxonomy

ClosureBenchorganises 26 categories into three levels of compositional difficulty \([Table2](https://arxiv.org/html/2608.18242#S2.T2)\); Appendix[A](https://arxiv.org/html/2608.18242#A1)lists all of them with each category’s defining operation\.

L1 \(Atomic, 11 categories\):a single primitive—triangle count, reachability, negative reachability, degree count, maximum degree, same\-SCC membership, set intersection, set difference, and the kinship relations ancestor, sibling, and cousin\. Each isolates one graph\-relational operation\.

L2 \(Chain, 8 categories\):two or three primitives where one feeds the next—reach\-then\-count, reach\-then\-filter, kinship chain, triangles in a reachable subgraph, path\-and\-compare, SCC\-then\-count, degree\-then\-reach, and intersect\-then\-size\. “How many nodes canXXreach?” is reachability followed by a count\.

L3 \(Composition, 7 categories\):three to five primitives with branching or multiple queries—multi\-query, conditional, aggregate\-over\-set, complex kinship, graph comparison, chain\-of\-filters, and mixed\-domain\. “IfXXcan reachYY, return the size of its reachable set, otherwise−1\-1” combines a reachability test, a branch, and a count\.

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\.
### 2\.3Three Independent Complexity Axes

EachClosureBenchinstance is parameterised by three orthogonal complexity dimensions:

Graph size \(nn\):the number of entities \(nodes\)\. Increasingnnmakes the adjacency description longer and enlarges the space the model must track, without changing the computational structure\. The held\-out split usesn∈\{4,…,10\}n\\in\\\{4,\\dots,10\\\}; the size\-scaling study \(§[4\.2](https://arxiv.org/html/2608.18242#S4.SS2)\) pushesnnto 20 on a dedicated sweep\.

Edge density \(ρ\\rho\):the fraction of possible edges present \(ρ∈\[0\.1,0\.5\]\\rho\\in\[0\.1,0\.5\]\)\. Sparse graphs \(ρ=0\.1\\rho=0\.1\) have few connections and simple reachability; dense graphs \(ρ=0\.5\\rho=0\.5\) produce more triangles, larger reachable sets, and more complex SCC structures\.

Query depth \(dd\):the number of chained reasoning operations, corresponding to levels L1–L3\. Increasingddadds compositional steps without changing the underlying graph\.

These axes are orthogonal by construction: increasingnndoes not changedd; increasingρ\\rhodoes not changenn\. This enables controlled ablation studies that isolate specific failure modes—for instance, testing whether a model that succeeds on 4\-node graphs fails on 12\-node graphs with the same query type, or whether density affects triangle counting but not reachability\.

### 2\.4Surface Variation

A key design decision, motivated by GSM\-Symbolic’s finding that surface perturbations degrade memorisation\-dependent performance\([Mirzadeh et al\. 2024](https://arxiv.org/html/2608.18242#bib.bib15)\), is the separation of instance generation into*structural*and*surface*components controlled by independent seeds\.

Structural seed:controls graph topology—which nodes connect to which—and therefore the reference answer\. Two instances with the same structural seed but different surface seeds have identical answers but different natural\-language realisations\.

Surface seed:controls presentation features that do not affect the answer:

- •*Node labels*from disjoint pools: letters \(A–Z\), personal names \(Alice–Vic\), server identifiers \(srv\-00–srv\-29\), or animal names \(ant–zebu\)\.
- •*Domain frames*\(16 total\): fraud detection, supply chain, cybersecurity, compliance, kinship, healthcare, logistics, social media, academia, banking, real estate, telecommunications, energy, government, transport, and abstract—each with domain\-specific vocabulary \(“transferred funds to” vs\. “routes to” vs\. “cites”\)\.
- •*Presentation style*\(5 variants\): flat, grouped by source, grouped by target with reversed verbs, randomly mixed, or varied per\-source phrasing\.
- •*Edge ordering*: the order in which edges appear in the question text\.

The combinatorial space is large: for a 10\-node graph, each label pool provides101010^\{10\}\+ permutations; combined with 16 domains, 5 styles, andm\!m\!edge orderings, a surface seed indexes into a space exceeding101510^\{15\}distinct realisations of the same graph structure\. An evaluator can always generate a fresh surface configuration that shares no tokens with any training data, providing a structural defence against data contamination\.

### 2\.5Generating and Verifying Instances

Generation runs offline \(top of[Figure1](https://arxiv.org/html/2608.18242#S2.F1)\)\. For each instance the generator samples a category and a structural triple\(n,ρ,d\)\(n,\\rho,d\), draws a graph with those parameters, and computes the reference answer by executing the category’s program over the graph; an independent surface seed \(§[2\.4](https://arxiv.org/html/2608.18242#S2.SS4)\) then verbalises the graph and question as natural\-language text\. At evaluation time \(bottom of[Figure1](https://arxiv.org/html/2608.18242#S2.F1)\) a model receives only that text and returns a JSON answer, scored against the precomputed reference\. The five\-step procedure is detailed in Appendix[K](https://arxiv.org/html/2608.18242#A11)\.

The answer is*computed*, not labelled, so it is correct by construction; we additionally cross\-check every released instance against a second, independently written Python\+NetworkX implementation of each category\. Our primary engine is*Ein*, a tensor\-logic language\.[Domingos 2025](https://arxiv.org/html/2608.18242#bib.bib5)argues that logical rules and Einstein summation are the same operation; the primitives of §[2\.1](https://arxiv.org/html/2608.18242#S2.SS1)are naturally tensor contractions over the adjacency matrix, so they express directly and compactly in Ein\. We use it for three properties: \(1\) a parser and type\-checker make execution deterministic and verifiable; \(2\) programs are compact, typically 4–8 lines \(∼\{\\sim\}200 tokens\), which later makes Ein an efficient program\-synthesis target \(§[4\.5](https://arxiv.org/html/2608.18242#S4.SS5)\); and \(3\) it provides the graph primitives \(transitive closure, reachability, degree, selection\) as builtins\. Triangle counting is four lines:

A=edges\(\[\[0,1,1\],\[1,0,1\],\[1,1,0\]\],3\)

A2\[i,k\]=A\[i,j\]A\[j,k\]

A3\[i,j\]=A2\[i,k\]A\[k,j\]

Result=trace\(A3\)/6\.0

*Models never interact with Ein*: the program runs only during generation, so any model can attemptClosureBenchwithout programming knowledge\.

Data splits\.We draw two disjoint splits from the generator, each stratified at 50 instances per category: a*training*split and a*held\-out*split of 1,300 instances each\. All models are evaluated on the held\-out split; the fine\-tuning experiments—the memorisation probe \(§[4\.1](https://arxiv.org/html/2608.18242#S4.SS1)\) and the program\-synthesis models \(§[4\.5](https://arxiv.org/html/2608.18242#S4.SS5)\)—train on the training split and report on the held\-out split\. Because the held\-out split is verbalised from fresh surface seeds, it shares no surface tokens with the training split, so a model’s seen\-vs\-held\-out accuracy gap reflects memorisation rather than transfer \(§[4\.1](https://arxiv.org/html/2608.18242#S4.SS1)\)\.

## 3Experimental Setup

Our experiments useClosureBenchas a lens on how different classes of language model fail on graph\-relational reasoning\. We run three kinds of experiment: we evaluate open\-weight and frontier models off the shelf, to map where accuracy breaks down \(§[4\.2](https://arxiv.org/html/2608.18242#S4.SS2)–[4\.4](https://arxiv.org/html/2608.18242#S4.SS4)\); a*memorisation probe*fine\-tunes a model on the benchmark’s own instances, to test whether the constructive design can detect contamination \(§[4\.1](https://arxiv.org/html/2608.18242#S4.SS1)\); and a*program\-synthesis*experiment fine\-tunes a model to emit an executable program instead of an answer, to test whether the failure can be removed \(§[4\.5](https://arxiv.org/html/2608.18242#S4.SS5)\)\. This section gives the setup common to all three; Appendix[G](https://arxiv.org/html/2608.18242#A7)and the released code reproduce every number\.

In every experiment a model is shown a natural\-language graph question and must return a single JSON object with an"answer"field—for example, “*srv\-0 routes to srv\-2; srv\-2 routes to srv\-4; is there a route from srv\-0 to srv\-4?*” expects`\{"answer": true\}`\. The schema is described generically, with no per\-category examples, so a model must infer the expected type from the wording, as a human evaluator would \(verbatim prompts in Appendix[F](https://arxiv.org/html/2608.18242#A6), the per\-category schema in Appendix[I](https://arxiv.org/html/2608.18242#A9)\)\. Where the provider supports it we evaluate in two modes—*direct*\(answer immediately\) and*chain\-of\-thought*\(CoT: reason step by step, then answer\)—and decode at temperature 0 throughout, so runs are deterministic and reproducible\.

### 3\.1Models

We span three groups\.*Open\-weight models*of increasing size run locally on a single low\-cost device \(one NVIDIA GB10, DGX Spark\): Qwen2\.5\-1\.5B, Qwen3\.5\-2B, Qwen3\-4B, and Qwen3\.5\-9B\.333HuggingFace repositories \(pinned commits\):Qwen/Qwen2\.5\-1\.5B\-Instruct\(989aa79\),Qwen/Qwen3\-4B\(1cfa9a7\),Qwen/Qwen3\.5\-2B\(15852e8\), andQwen/Qwen3\.5\-9B\(c202236\)\. The Qwen3\.5 models use theQwen3\_5ForConditionalGenerationarchitecture \(multimodal\-capable\); we run text\-only inference\.*Frontier models*are queried through their providers’ APIs \(March 2026, default settings\): GPT\-4\.1, GPT\-4\.1\-mini, o3, Claude Sonnet 4, and Gemini 2\.5 Flash; o3 is available in direct mode only\.*Fine\-tuned models*are Qwen3\-4B adapted with LoRA\([Hu et al\. 2022a](https://arxiv.org/html/2608.18242#bib.bib11)\)for the memorisation and program\-synthesis experiments; the configuration is in §[3\.4](https://arxiv.org/html/2608.18242#S3.SS4)\.

### 3\.2Evaluation Set and Difficulty

Unless stated otherwise, all models are evaluated on the same held\-out split \(§[2\.5](https://arxiv.org/html/2608.18242#S2.SS5)\): 1,300 instances, 50 per category, drawn across the full difficulty range—graph sizen∈\{4,…,10\}n\\in\\\{4,\\dots,10\\\}and edge densityρ\\rhodrawn continuously from\[0\.1,0\.5\]\[0\.1,0\.5\], with query depthddset by each category’s level\. The per\-level accuracies we report therefore average overnnandρ\\rho; §[4\.2](https://arxiv.org/html/2608.18242#S4.SS2)breaks accuracy out along each axis\. All models are evaluated on the full 1,300\-instance split\.

### 3\.3Scoring

We report*lenient*accuracy throughout: an answer is correct if it matches the reference, with two documented tolerances for the source\-inclusion ambiguity present in some question phrasings \(±1\\pm 1for the affected count categories,±\\pmone element for the affected set categories\)\.*Strict*scoring removes both tolerances\. The two track each other closely—the gap is0\.00\.0–0\.30\.3pp for program\-synthesis models,0\.90\.9–1\.61\.6pp for frontier CoT, and4\.54\.5–6\.36\.3pp for direct prompting and small open models—and preserve the ordering of methods; the scoring algorithm and every configuration under both conventions are in Appendix[I](https://arxiv.org/html/2608.18242#A9)\([Table10](https://arxiv.org/html/2608.18242#A9.T10)\)\.

### 3\.4Fine\-tuning Experiments

Two experiments fine\-tune a model\. The*memorisation probe*\(§[4\.1](https://arxiv.org/html/2608.18242#S4.SS1)\) fine\-tunes the base model on the training instances with the reference*answers*as targets: if this lifts accuracy on seen instances far above accuracy on fresh held\-out instances, the gap measures how much the model has memorised rather than learned\. The*program\-synthesis*experiment \(§[4\.5](https://arxiv.org/html/2608.18242#S4.SS5)\) fine\-tunes the model to emit an executable*program*\(in Ein or Python\+NetworkX\) whose execution yields the answer, testing whether offloading the computation removes the compositional failure of §[4\.2](https://arxiv.org/html/2608.18242#S4.SS2)\.

Both use the same configuration: Qwen3\-4B with LoRA \(r=16r\{=\}16,α=32\\alpha\{=\}32, dropout 0\.05\), learning rate2×10−42\\times 10^\{\-4\}, batch size 4, 3 epochs, trained on the 1,300\-instance training split and evaluated on the disjoint held\-out split, on the same GB10 device\. The memorisation probe is repeated over 3 seeds \(\{42,137,256\}\\\{42,137,256\\\}\) and averaged\. For program synthesis the model has no prior exposure to Ein; it learns the syntax from a 600\-token specification appended to the system prompt\. Ground truth is computed with the Ein runtime v0\.3\.0\.

## 4Results

We report results in three parts, one per contribution: the memorisation measurement \(§[4\.1](https://arxiv.org/html/2608.18242#S4.SS1)\), the diagnostic of where models fail \(§[4\.2](https://arxiv.org/html/2608.18242#S4.SS2)–[4\.4](https://arxiv.org/html/2608.18242#S4.SS4)\), and program synthesis as an alternative \(§[4\.5](https://arxiv.org/html/2608.18242#S4.SS5)\)\.

### 4\.1Measuring Memorisation

A fixed benchmark cannot separate a model that solved its questions from one that memorised them, since those questions may already be in the model’s training data; a constructive benchmark can, because it supplies fresh instances\. We fine\-tune the base model on the 1,300 training instances with answer supervision \(§[3\.4](https://arxiv.org/html/2608.18242#S3.SS4)\) and track accuracy, over training epochs, on both the seen training instances and a disjoint held\-out set\.[Figure2](https://arxiv.org/html/2608.18242#S4.F2)plots the two curves: seen accuracy climbs to 78\.5% while held\-out plateaus at∼\{\\sim\}59% after epoch 5, a 19\.3pp gap\. Held\-out accuracy does rise from the base model’s∼\{\\sim\}34% to 59\.2%, so fine\-tuning yields some transferable gain; the 19\.3pp gap is the part that does not transfer, and it widens with more training\. The gap is for one model and configuration and its size will vary, so we treat the magnitude as illustrative, not a benchmark constant\.

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\.BecauseClosureBenchcan generate unlimited fresh instances, evaluators can always produce a held\-out set that the model has never seen\. The seen\-vs\-held\-out gap then serves as a*memorisation signal*: a large gap \(here 19\.3pp\) shows that part of the seen\-set accuracy is memorisation that does not carry over to fresh instances\. A fixed benchmark, where all instances are potentially in the training data, cannot make this measurement\. Two caveats: this experiment tests supervised fine\-tuning on aligned pairs and does not address subtler pretraining contamination, and the signal depends on the structural novelty of held\-out instances\.

### 4\.2Where Do Models Fail?

[Table3](https://arxiv.org/html/2608.18242#S4.T3)presents accuracy across all models and levels\. Every model degrades from L1 to L3, which establishes compositional depth as a difficulty axis\. The L1–L3 drop \(the “compositional slope”\) is 20–26pp for open models and 17–23pp for frontier models including o3; for Ein SFT it is1\.3pp\. Program synthesis removes the compositional penalty that the natural\-language \(NL\) reasoning approaches all carry\.[Figure3](https://arxiv.org/html/2608.18242#S4.F3)plots the contrast\.

Figure 3:Accuracy by compositional level across all evaluated models\. Every model degrades from L1 to L3 except Ein SFT \(94%→\\to93%\)\. Dotted lines separate open models, frontier API, and program synthesis\.Table 3:Main results onClosureBench\(lenient scoring\)\. All models are evaluated on the same 1,300\-instance held\-out split, spanning graph sizesn=4n\{=\}4–1010; accuracy is averaged over that range \([Table4](https://arxiv.org/html/2608.18242#S4.T4)breaks it out bynn\)\. All methods degrade from L1 to L3 except Ein SFT, which stays nearly flat\.Beyond the level averages, accuracy depends on graph size, and the two interact\.[Figure4](https://arxiv.org/html/2608.18242#S4.F4)plots this for the open models on a dedicated size sweep \(nnup to 20\): L1 tasks degrade gently, while L3 tasks degrade steeply, so graph size and compositional depth compound rather than add\. A sharp drop appears betweenn=4n\{=\}4andn=8n\{=\}8—about 20pp for both Qwen3\-4B and Qwen3\.5\-9B—after which accuracy declines gradually\. The drop sits at nearly the same place for both model sizes, consistent with a limit in processing graph descriptions rather than a capacity limit, though we test only two small open models here; the L1–L3 gap widens from∼\{\\sim\}26pp atn=4n\{=\}4to∼\{\\sim\}30pp atn=16n\{=\}16, where L3 falls to single digits\.

Figure 4:Accuracy vs\. graph size \(nn\) at each compositional level, for the open models on a dedicated size sweep \(nnup to 20\)\. L1 degrades gently; L3 steeply\. Size and depth compound rather than add\.The frontier models show the same size dependence on the held\-out split, which spansn∈\{4,…,10\}n\\in\\\{4,\\dots,10\\\}\([Table4](https://arxiv.org/html/2608.18242#S4.T4)\)\. Overall accuracy falls withnnfor every frontier model except o3, whose L1 and L2 stay near\-perfect\. The decline is driven by L3, and it takes the form of a threshold rather than a gradient: on small graphs \(n≤5n\\leq 5\) frontier models answer L3 at 85–95%, but pastn≈5n\\approx 5their L3 accuracy drops into a 55–70% band \(o3 higher,∼\{\\sim\}82%\) and then plateaus rather than falling further\. Edge density has a much weaker, non\-monotonic effect \(a few points from sparse to dense\), so no single geometric axis orders the difficulty cleanly\. Size\-dependent degradation on compositional queries is thus a property of every NL\-reasoning model we evaluate, open and frontier\.

Table 4:Held\-out*overall*accuracy \(%\) by graph sizenn\(lenient\)\. Every frontier model degrades withnnexcept o3, whose L1/L2 stay near\-perfect\. The decline is driven by the compositional \(L3\) tasks, which drop sharply oncennexceeds∼5\{\\sim\}5and then plateau rather than declining smoothly; per\-nnL3 estimates \(∼\{\\sim\}50 instances each\) are too noisy to tabulate\. Modes: o3 and Gemini direct, GPT\-4\.1 and Claude CoT\.
### 4\.3Cost of Chain\-of\-Thought

The frontier models reach their best accuracy only with chain\-of\-thought: it recovers much of the compositional loss above \(GPT\-4\.1 rises from 52\.4% to 86\.2% overall\)\. The reasoning tokens are not free, and whether that accuracy is affordable depends on how many are spent per answer, which[Table5](https://arxiv.org/html/2608.18242#S4.T5)quantifies\.

Table 5:Token cost per answer and cost\-efficiency \(tokens per correct answer\)\. CoT reasoning consumes 10–50×\\timesmore tokens than direct mode, with superlinear scaling at higher compositional levels\.⋆\\starAll accuracies are overall \(1,300 instances, lenient scoring\)\.

[Figure5](https://arxiv.org/html/2608.18242#S4.F5)visualises this trade\-off: Ein SFT achieves the best accuracy–cost Pareto point, while CoT models cluster in the high\-token, moderate\-accuracy region\.

Figure 5:Token efficiency: accuracy vs\. mean tokens per answer \(log scale\)\. Ein SFT \(star\) achieves the highest accuracy at moderate token cost\.Costs scale superlinearly with compositional depth: models generate more tokens per reasoning step at higher levels, compounded by error\-recovery overhead \(“Wait, let me reconsider…” segments that appear in 30–40% of L3 CoT traces\)\. The result is a doubly unfavourable scaling regime: more tokens*and*lower accuracy per token as complexity grows\. GPT\-4\.1 CoT uses∼\{\\sim\}431 tokens per answer—a 60×\\timesincrease over direct mode—while only doubling accuracy\. The Ein program\-synthesis approach \(§[4\.5](https://arxiv.org/html/2608.18242#S4.SS5)\) breaks this trade\-off:∼\{\\sim\}200 tokens per answer at 94\.3% accuracy gives the best cost\-efficiency of any method evaluated\.

CoT is not uniformly beneficial\. For GPT\-4\.1, it adds \+70pp onaggregate\_over\_setbut costs−\-2pp onkinship\_complex, the category with the deepest traversal\. For Gemini 2\.5 Flash, CoT*decreases*accuracy on 15 of 26 categories \(up to−\-30pp onreach\_then\_count\) and lowers overall accuracy from 87\.4% to 81\.3%\. Two effects contribute: the model already reasons internally in direct mode \(∼\{\\sim\}1,000 thinking tokens\), so added thinking sometimes revises a correct answer, and under CoT it returns no parseable answer on 9\.5% of instances \([Table11](https://arxiv.org/html/2608.18242#A10.T11)\), its reasoning trace exhausting the output budget before it emits JSON\.

A rough compute comparison points the same way: Ein SFT generates∼\{\\sim\}200 tokens from a 4B model, while frontier CoT generates 400–1,200 tokens from much larger models\. We do not have parameter counts for the closed frontier models, so we do not quantify a combined tokens\-times\-parameters ratio; the token counts alone already favour the small program\-synthesis model\.

### 4\.4Error Analysis

The results so far show*where*models fail; to see*how*, we read the failing responses\. Among the 89 L3 errors of GPT\-4\.1 CoT \(our best frontier CoT model\), three families account for 69%; concrete examples are in Appendix[L](https://arxiv.org/html/2608.18242#A12)\.

Direction confusion \(24%, multi\_query\):The model inconsistently parses directed edges\. “X reports to Y” should encode asX→YX\{\\to\}Y\(out\-degree ofXX\), but the model sometimes counts edges pointing*into*XX, confusing out\-degree with in\-degree or total degree\. For example, a node with out\-degree 1 and in\-degree 2 is reported as having degree 3\. The reachability component is often correct; only the degree is wrong\. The error is systematic across instances\.

Depth truncation \(26%, kinship\_complex\):The model finds the correct root ancestor but counts only 2–3 levels of descendants, systematically undercounting by 2–4\. The distribution of errors is\{−3:10,−4:6,−2:5\}\\\{\-3\{:\}10,\-4\{:\}6,\-2\{:\}5\\\}, consistent with a fixed depth limit\. The model can trace a breadth\-first traversal for a few steps but loses track of deeper branches\.

Accumulation drift \(19%, mixed\_domain\):Multi\-step arithmetic \(find SCC, collect degrees, compute average\) accumulates small errors\. Answers are off by 0\.1–0\.5 on floats—each step is nearly correct but errors compound across 4–5 operations\.

The remaining 31% are format mismatches \(lists instead of dicts\) and semantic ambiguities \(source inclusion\)\. Across all L3 failures, graph size strongly predicts difficulty: 2% failure rate atn=4n\{=\}4vs\. 36% atn=10n\{=\}10\.

The model usually states the reasoning rule correctly; the failures are in carrying it out over the graph\. Depth truncation and accumulation drift are execution errors—the model tracks a traversal or a running total for a few steps, then loses it—and they grow with the number of operations it must hold in working memory\. Direction confusion is a separate, perceptual error: misreading the direction of an edge\. Program synthesis \(§[4\.5](https://arxiv.org/html/2608.18242#S4.SS5)\) offloads the execution to a runtime, which removes the first kind and leaves only the second\.

### 4\.5Program Synthesis as an Alternative

The execution bottleneck \(§[4\.4](https://arxiv.org/html/2608.18242#S4.SS4)\) motivates a different approach: train models to emit*verified programs*whose execution produces the answer, instead of carrying out the computation in context\. When the program is syntactically correct and type\-checks, the Ein runtime returns a deterministic result, which moves the multi\-step execution from the model to the runtime\.

We fine\-tune Qwen3\-4B with LoRA \(r=16r\{=\}16,α=32\\alpha\{=\}32\) on 1,300 \(question, Ein program\) pairs for 3 epochs\. The model has*zero prior exposure*to Ein—it learns the complete syntax from a 600\-token prompt specification appended to the system message\. Training data and evaluation data are fully disjoint \(1,300 / 1,300 instances\), with no shared instances between splits\.

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\.Results \([Table6](https://arxiv.org/html/2608.18242#S4.T6)\): the Ein model executes on 99\.6% of instances \(1,295/1,300\) and reaches 94\.3% held\-out \(1,226/1,300\), with a 3\.7pp seen/held\-out gap\. The controlled comparison is within the same model: the fine\-tuned\-direct model from §[4\.1](https://arxiv.org/html/2608.18242#S4.SS1), trained on the same data with the same LoRA configuration but supervised on answers, reaches 59\.2% held\-out with a 19\.3pp gap\. Supervising on programs rather than answers adds 35pp of held\-out accuracy and shrinks the generalisation gap by 5×\\times, which indicates the model learns to write programs rather than to store input–output pairs\. Held\-out accuracy also exceeds zero\-shot o3 \(92\.8%\), but that sets a task\-specialised fine\-tune against a general model prompted zero\-shot, so we do not read it as evidence of a stronger model\. The results we rely on are the near level\-invariance \([Table3](https://arxiv.org/html/2608.18242#S4.T3)\) and the low token cost \(§[4\.3](https://arxiv.org/html/2608.18242#S4.SS3)\)\.

All 26 categories exceed 82% on held\-out; 21 exceed 90%\. The five below\-90% categories \(triangle\_count,degree\_count,triangle\_in\_subgraph,aggregate\_over\_set,mixed\_domain\) involve either counting operations sensitive to single\-edge errors or compound operations whose multi\-step descriptions make edge extraction harder—the graph\-reading error that remains once execution is offloaded \(§[4\.4](https://arxiv.org/html/2608.18242#S4.SS4)\)\.

Among the 74 held\-out errors, 61 \(82%\) are graph\-parsing mistakes: the model writes syntactically valid Ein programs with correct logic but misreads one or more edges from the natural\-language description\. Only 8 errors \(11%\) involve incorrect program logic, and 5 \(7%\) are execution failures\. The remaining bottleneck is therefore NL comprehension, not program synthesis\.

The approach works with other target languages\. We fine\-tune the same Qwen3\-4B under identical hyperparameters \(r=16r\{=\}16,α=32\\alpha\{=\}32, 3 epochs, temperature 0\) to emit Python\+NetworkX programs\. The Python baseline reaches 92\.6% held\-out accuracy at a 97\.8% execution rate, with a 3\.5pp seen/held\-out gap, close to Ein’s 3\.7pp\. The two targets are within 1\.7pp overall: Python wins or ties on 17 of 26 categories and leads on L3 by\+2\.6\+2\.6pp, while Ein leads on atomic L1 queries and is more compact \(∼\{\\sim\}128 vs\.∼\{\\sim\}156 generated tokens per answer\)\. A zero\-shot Python probe \(GPT\-4\.1, 52 instances\) reaches 78\.8% at∼\{\\sim\}219 tokens, which locates the gain in the fine\-tuning\. We use Ein for its tensor\-logic verification guarantees and its compactness as an SFT target; the effect holds for any verified program\-synthesis target that offloads the multi\-step execution\.

Ein programs average∼\{\\sim\}200 tokens per answer compared to∼\{\\sim\}844 for o3 and∼\{\\sim\}431 for GPT\-4\.1 CoT \([Table5](https://arxiv.org/html/2608.18242#S4.T5)\)\. Combined with higher accuracy, the Ein approach uses∼\{\\sim\}212 tokens per*correct*answer, 6×\\timesfewer than o3 and 6–10×\\timesfewer than frontier CoT models\.

### 4\.6Robustness to Graph Encoding

The compositional penalty \(§[4\.4](https://arxiv.org/html/2608.18242#S4.SS4)\) could be an artefact of the*natural\-language*presentation: a cleaner, structured encoding might remove it\. We test this directly\. On a 200\-instance L1/L2/L3\-uniform subset \(whose NL accuracy matches the full set within 0\.5pp\), we re\-render each graph under three encodings while holding the query sentence fixed: \(i\) the natural\-language enumeration used throughout the paper, \(ii\) a JSON object with explicitnodesandedgeslists, and \(iii\) a labelledN×NN\{\\times\}Nadjacency matrix\. We evaluate four open models and two frontier models in direct mode\.

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\)\.[Table7](https://arxiv.org/html/2608.18242#S4.T7)yields three findings\.\(1\) The bottleneck is not NL phrasing\.A clean JSON edge list is statistically tied with NL for weaker models \(Qwen2\.5\-1\.5B: 26\.5 vs\. 26\.5; Qwen3\-4B: 38\.0 vs\. 40\.0\) and gives capable ones a moderate gain \(\+3\.5\+3\.5to\+6\.5\+6\.5pp, e\.g\. GPT\-4\.1 53\.0→\\to59\.5\)\. Handing the model a perfectly structured edge list does not rescue it; the difficulty is in carrying out the computation over the graph, not the surface form\.\(2\) Encoding preference is capacity\-dependent\.The adjacency matrix is the*worst*encoding for every open model \(−2\-2to−17\.5\-17\.5pp, worst for the mid\-size models that cannot track anN×NN\{\\times\}Ngrid positionally on graphs up ton=20n\{=\}20\), yet the*best*encoding for the strongest model \(Gemini 2\.5 Flash,\+6\.5\+6\.5pp over NL\)\. An unambiguous, position\-addressable matrix is too dense for weak models to parse but the cleanest input for a model with enough capacity to index it, which explains why prior work disagrees on the “best” graph encoding\([Fatemi et al\. 2023](https://arxiv.org/html/2608.18242#bib.bib6)\)\.\(3\) The compositional cliff persists across encodings\.The L1→\\rightarrowL3 drop survives all three representations for every model except Gemini under the adjacency matrix, where it flattens to L2=97\.0=97\.0, L3=84\.8=84\.8\. Encoding choice reshuffles*where*errors land without removing the compositional penalty, which keeps compositional depth as the main difficulty axis\. One caveat on the matrix column: Gemini 2\.5 Flash is a thinking model whose default mode spends internal reasoning tokens, so its strong adjacency\-matrix result reflects that additional compute as well as the encoding itself; we read the column as capacity\-dependent rather than as evidence that matrices are intrinsically easier\. The three findings are unchanged under strict scoring\.

## 5Discussion

ClosureBenchwas built to test whether large language models actually execute compositional graph logic or only appear to, and the results give a consistent answer\. Even the strongest models still fail: accuracy is high on atomic queries and falls sharply as operations compose, and every model we tested—open and frontier—shows the same decline from L1 to L3 \(o3 from 96% to 82%, the others further\)\.

The failure is not a lack of task understanding but of*executing*the computation over the graph\. Three results place it there\. It survives clean structured encodings—a JSON edge list or an adjacency matrix does not rescue it—so it is not an artefact of natural\-language phrasing\. It grows with graph size and depth together, as a working\-memory limit would, for frontier models as well as open ones—o3’s overall accuracy is least affected \(its atomic and chained sub\-tasks stay near\-perfect\), but even its hardest queries degrade with size\. And the individual errors are traversal and accumulation mistakes over a graph the model has otherwise read correctly\.

Fine\-tuning does not fix this by teaching the logic\. Supervising the model on the benchmark’s answers raises seen\-set accuracy steeply while held\-out accuracy plateaus—a 19\.3pp gap—so the model memorises graph–answer pairs rather than learning to compute\. The constructive design is what exposes this: with fresh instances always available, the gap is measurable, which a fixed benchmark cannot do\.

The clearest evidence is that the same 4B model succeeds once it no longer has to hold the computation in its head\. Fine\-tuned to emit a short program—in Ein or Python\+NetworkX—and let a runtime execute it, it stays nearly flat across compositional levels \(1\.3pp from L1 to L3\), matches or exceeds the frontier models on the hardest queries, and uses a fraction of the tokens\. Its remaining errors are almost all misread edges, not wrong logic: once execution is offloaded, only reading the graph is left\. Understanding the task was never the bottleneck; carrying out the computation was\.

Limitations\.\(1\)ClosureBenchcovers only graph\-theoretic tasks with algorithmically computable ground truth\. \(2\) The memorisation probe fine\-tunes on answers for a single model and configuration; it is a diagnostic, not immunity, and does not address subtler pretraining contamination\. \(3\) We lack 30B\+ open models to bridge small open and frontier API\. \(4\) The program\-synthesis result uses one 4B base model and two program targets; whether the near level\-invariance holds for other models and larger scales is untested\. \(5\) Some question templates leave the source\-inclusion convention implicit; we report strict and lenient scores side by side \([Table10](https://arxiv.org/html/2608.18242#A9.T10)\) rather than resolving every template\.

ClosureBench—generator, evaluation harness, and all model responses—is released at[https://github\.com/egolabs\-ai/closurebench](https://github.com/egolabs-ai/closurebench); because instances are generated on demand, an evaluator is never limited to the splits we ship\.

Broader Impact Statement

ClosureBenchis an evaluation artifact; its intended effect is more reliable measurement of compositional reasoning and of memorisation\. The benchmark is fully synthetic and contains no personal or sensitive data, so it carries no direct privacy or fairness risk\. The main foreseeable misuse is training on the released instances to inflate reported scores; the memorisation measurement in §[4\.1](https://arxiv.org/html/2608.18242#S4.SS1)is designed to detect exactly this\. The program\-synthesis results point toward cheaper verified reasoning, which we read as a positive efficiency outcome rather than a capability risk\.

Acknowledgments and Disclosure of Funding

The author declares no competing interests, and this work received no specific external funding\.

## References

- Chen et al\. \(2024a\)Nuo Chen, Yuhan Li, et al\.GraphWiz: An instruction\-following language model for graph problems\.In*Proceedings of KDD*, 2024a\.
- Chen et al\. \(2024b\)Zhi Rui Tam Chen, Zhi Hao Lin, et al\.BEYONDBENCH: Benchmark\-free evaluation of reasoning in language models\.*arXiv preprint arXiv:2509\.24210*, 2024b\.
- Cheng et al\. \(2024\)Kewei Cheng, Jingfeng Yang, Haoming Jiang, et al\.Inductive or deductive? rethinking the fundamental reasoning abilities of LLMs\.*arXiv preprint arXiv:2408\.00114*, 2024\.
- Cobbe et al\. \(2021\)Karl Cobbe, Vineet Kosaraju, et al\.Training verifiers to solve math word problems\.*arXiv preprint arXiv:2110\.14168*, 2021\.
- Domingos \(2025\)Pedro Domingos\.Tensor logic: The language of AI\.*arXiv preprint arXiv:2510\.12269*, 2025\.Proposes tensor logic as a unifying language for AI, showing that logical rules and Einstein summation are fundamentally the same operation\.
- Fatemi et al\. \(2023\)Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi\.Talk like a graph: Encoding graphs for large language models\.*arXiv preprint arXiv:2310\.04560*, 2023\.
- Gebru et al\. \(2021\)Timnit Gebru, Jamie Morgenstern, Briana Vecchione, Jennifer Wortman Vaughan, Hanna Wallach, Hal Daumé III, and Kate Crawford\.Datasheets for datasets\.*Communications of the ACM*, 64\(12\):86–92, 2021\.
- Guo et al\. \(2025\)Xiaojun Guo et al\.G1: Teaching LLMs to reason on graphs with reinforcement learning\.*arXiv preprint arXiv:2505\.18499*, 2025\.
- Hendrycks et al\. \(2021\)Dan Hendrycks, Collin Burns, et al\.Measuring massive multitask language understanding\.In*Proceedings of ICLR*, 2021\.
- Ho et al\. \(2020\)Xanh Ho, Anh\-Khoa Duong Nguyen, et al\.Constructing a multi\-hop QA dataset for comprehensive evaluation of reasoning steps\.*Proceedings of COLING*, 2020\.
- Hu et al\. \(2022a\)Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen\-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen\.LoRA: Low\-rank adaptation of large language models\.*Proceedings of ICLR*, 2022a\.
- Hu et al\. \(2022b\)Simeng Hu, Tianle Ma, et al\.FOLIO: Natural language reasoning with first\-order logic\.*arXiv preprint arXiv:2209\.00840*, 2022b\.
- Liu et al\. \(2020\)Jian Liu, Leyang Cui, et al\.LogiQA: A challenge dataset for machine reading comprehension with logical reasoning\.In*Proceedings of IJCAI*, 2020\.
- Luo et al\. \(2024\)Zihan Luo, Xiran Song, Hong Huang, Jianxun Lian, et al\.GraphInstruct: Empowering large language models with graph understanding and reasoning capability\.*arXiv preprint arXiv:2403\.04483*, 2024\.
- Mirzadeh et al\. \(2024\)Iman Mirzadeh, Keivan Alizadeh, et al\.GSM\-Symbolic: Understanding the limitations of mathematical reasoning in large language models\.*arXiv preprint arXiv:2410\.05229*, 2024\.
- Saparov and He \(2023\)Abulhair Saparov and He He\.Language models are greedy reasoners: A systematic formal analysis of chain\-of\-thought\.*arXiv preprint arXiv:2210\.01240*, 2023\.
- Shojaee et al\. \(2025\)Parshin Shojaee, Iman Mirzadeh, Keivan Alizadeh, Maxwell Horton, Samy Bengio, and Mehrdad Farajtabar\.The illusion of thinking: Understanding the strengths and limitations of reasoning models via the lens of problem complexity\.*arXiv preprint arXiv:2506\.06941*, 2025\.
- Sinha et al\. \(2019\)Koustuv Sinha, Shagun Sodhani, et al\.CLUTRR: A diagnostic benchmark for inductive reasoning from text\.In*Proceedings of EMNLP*, 2019\.
- Tang et al\. \(2024\)Jianheng Tang, Prashant Chandrasekar, and Jia Li\.GraphArena: Evaluating and exploring large language models on graph computation\.*arXiv preprint arXiv:2407\.00379*, 2024\.
- Trivedi et al\. \(2022\)Harsh Trivedi, Niranjan Balasubramanian, et al\.MuSiQue: Multihop questions via single hop question composition\.In*Transactions of ACL*, 2022\.
- Valmeekam et al\. \(2024\)Karthik Valmeekam, Kaya Stechly, and Subbarao Kambhampati\.LLMs still can’t plan; can LRMs? a preliminary evaluation of OpenAI’s o1 on PlanBench\.*arXiv preprint arXiv:2409\.13373*, 2024\.
- Wang et al\. \(2023\)Hao Wang, Haotian Feng, et al\.NLGraph: Can large language models solve graph problems in natural language?*arXiv preprint arXiv:2305\.10037*, 2023\.
- White et al\. \(2024\)Colin White, Samuel Dooley, et al\.LiveBench: A challenging, contamination\-free LLM benchmark\.*arXiv preprint arXiv:2406\.19314*, 2024\.
- Yu et al\. \(2020\)Weihao Yu, Zihan Jiang, et al\.ReClor: A reading comprehension dataset requiring logical reasoning\.In*Proceedings of ICLR*, 2020\.
- Yuan et al\. \(2024\)Zike Yuan et al\.GraCoRe: Benchmarking graph comprehension and complex reasoning in large language models\.*arXiv preprint arXiv:2407\.02936*, 2024\.
- Zeng et al\. \(2024\)Qin Zeng et al\.Inference\-time decontamination: Reusing leaked benchmarks for large language model evaluation\.*Findings of ACL*, 2024\.
- Zhu et al\. \(2024a\)Kaijie Zhu, Jiaao Chen, Jindong Wang, et al\.DyVal: Dynamic evaluation of large language models for reasoning tasks\.*Proceedings of ICLR*, 2024a\.
- Zhu et al\. \(2024b\)Kaijie Zhu, Jindong Wang, Qinlin Yao, Jiaao Chen, Sinno Jialin Pan, and Eric P\. Xing\.DyVal 2: Dynamic evaluation of large language models by meta probing agents\.*Proceedings of NeurIPS*, 2024b\.
- Zhu et al\. \(2025\)Zehua Zhu et al\.Rethinking and benchmarking large language models for graph reasoning\.*arXiv preprint arXiv:2509\.24260*, 2025\.

## Appendix AFull Category Descriptions

L1 \(11 categories\):triangle\_count \(trace⁡\(A3\)/6\\mathrm\{trace\}\(A^\{3\}\)/6\), reachability \(transitive closure,TC​\(A\)​\[s,t\]\\mathrm\{TC\}\(A\)\[s,t\]\), negative\_reach \(set complement\), degree\_count/max, scc\_same, set\_intersect, set\_difference, ancestor, sibling, cousin\.

L2 \(8 categories\):reach\_then\_count, reach\_then\_filter, kinship\_chain, triangle\_in\_subgraph, path\_and\_compare, scc\_then\_count, degree\_then\_reach, intersect\_then\_size\.

L3 \(7 categories\):multi\_query, conditional, aggregate\_over\_set, kinship\_complex, graph\_comparison, chain\_of\_filters, mixed\_domain\.

## Appendix BSample Questions

Below we show one example question from each compositional level\. Models receive only the natural\-language text and must produce a JSON answer\. The generator enforces that every entity named in a question is declared in the node list, and the examples below are reproduced directly from generator output\.

L1 \(reachability\):

> There are 6 stations: deer, cat, wren, puma, quail, lynx\. lynx supplies power to deer\. puma and quail draw power from deer\. cat draws power from wren\. wren supplies power to puma\. Is there a path from lynx to quail?

L2 \(reach\_then\_count\):

> There are 7 suppliers: newt, eagle, kiwi, ibis, zebu, owl, viper\. eagle receives components from ibis\. owl receives components from newt and zebu\. newt ships to eagle and kiwi\. kiwi ships to ibis\. viper ships to eagle, kiwi, and zebu\. How many suppliers can viper reach?

L3 \(conditional\):

> There are 5 departments: kiwi, robin, bear, zebu, newt\. bear reports to robin\. zebu oversees bear\. kiwi reports to bear and newt\. If there is a reporting path from kiwi to robin, how many departments can kiwi reach? Otherwise return−1\-1\.

## Appendix CPer\-Category Results

[Table8](https://arxiv.org/html/2608.18242#A3.T8)reports Ein SFT held\-out accuracy for all 26 categories\.

Table 8:Ein SFT \(Qwen3\-4B \+ LoRA\) held\-out accuracy by category \(50 instances per category\)\. Categories below 90% are shown inred\.
## Appendix DExample Ein Program

The following annotated example shows how Ein computes the reference answer for a “reach\_then\_count” task \(L2\): given a directed graph, count the number of nodes reachable from a source node\.

A=edges\(\[\[0,1,0,0,0\],

\[0,0,1,0,0\],

\[0,0,0,1,1\],

\[0,0,0,0,0\],

\[0,0,0,0,0\]\],5\)

TC=tc\(A\)

Row\[j\]=select\(TC,2,j\)

Result=sum\(Row\)

Walkthrough\.Line 1 declares a5×55\{\\times\}5adjacency matrix\. The edges2→32\{\\to\}3,2→42\{\\to\}4,0→10\{\\to\}1,1→21\{\\to\}2, and2→32\{\\to\}3are encoded as 1s\. Thetcbuiltin computes the transitive closure via repeated Boolean matrix multiplication\.selectextracts row 2 \(source node\), andsumcounts the non\-zero entries\. The result \(here,3\) becomes the ground\-truth answer\.

Key properties: \(1\) the program is compact \(6 lines,∼\{\\sim\}80 tokens\); \(2\) every operation is deterministic; \(3\) the type system ensures dimensional consistency \(matrix×\\timesmatrix→\\tomatrix\); \(4\) the runtime guarantees termination\. The model being evaluated never sees this program—it receives only the natural\-language question “How many nodes can node 2 reach in the following graph?” and must produce\{"answer": 3\}\.

## Appendix EEin Syntax Specification

Ein is a minimal tensor\-logic language with the following core constructs:

Declarations\.Tensors are declared with explicit dimensions:

A=edges\(\[\[0,1\],\[1,0\]\],2\)

v=vec\(\[1,0,1\],3\)

s=42\.0

Einstein summation\.Named indices express contractions:

C\[i,k\]=A\[i,j\]B\[j,k\]

v\[i\]=A\[i,j\]ones\(3\)\[j\]

s=A\[i,j\]B\[i,j\]

Repeated indices on the right\-hand side are summed over \(Einstein convention\)\. Free indices on the left determine the output shape\.

Builtins\.Ein provides domain\-specific operations:

- •tc\(A\)— transitive closure \(Boolean matrix power\)
- •reach\(A, i\)— nodes reachable fromii
- •desc\(A, i\)— descendants ofii\(alias for reach\)
- •has\_path\(A, i, j\)— Boolean reachability test
- •trace\(A\)— matrix trace \(∑iAi​i\\sum\_\{i\}A\_\{ii\}\)
- •sum\(v\),max\(v\),min\(v\)— vector reductions
- •select\(A, i, j\)— index a matrix element
- •ge\(a,b\),gt\(a,b\),eq\(a,b\)— comparison predicates
- •diag\(A\),transpose\(A\)— structural operations
- •ones\(n\),zeros\(n\),eye\(n\)— constructors

Semantics\.Every program is a sequence of assignments evaluated top\-to\-bottom\. The final assignment’s value is the program output\. All operations are over non\-negative reals; Boolean values are represented as\{0,1\}\\\{0,1\\\}\. Programs are guaranteed to terminate \(no loops, no recursion\) and produce exactly one scalar, vector, or matrix value\.

## Appendix FBaseline Prompts

System prompt \(direct mode\):

> You are a reasoning assistant\. Read the graph description carefully, reason about the structure, and provide your answer as a JSON object with an "answer" field\. Do not include any explanation outside the JSON\.

System prompt \(CoT mode\):

> You are a reasoning assistant\. Read the graph description carefully\. Before providing your answer, think step by step about the graph structure and the computation needed\. Then provide your final answer as a JSON object with an "answer" field\.

System prompt \(Ein code\-gen mode\):

The complete Ein syntax reference is appended to the system message\. The model receives this specification at every inference call—it is the*only*source of Ein knowledge beyond the supervised training examples\.

Einisaminimaltensor\-logiclanguageforgraphcomputation\.

Programsoperateonadjacencymatricesandproducescalarorvectorresults\.

SYNTAX:

\-A=edges\(\[\[0,1\],\[1,2\]\],N\)\-\-adjacencymatrixfromedgelist,Nnodes

\-B\[i,k\]=A\[i,j\]A\[j,k\]\-\-Einsteinsummation\(repeatedindicessummed\)

\-Result=trace\(A\)\-\-trace\(sumofdiagonal\)

\-Result=sum\(A\)/sum\(A,1\)\-\-sumall/alongaxis

\-Result=tc\(A\)\-\-transitiveclosure\(reachabilitymatrix\)

\-Result=reach\(A,i\)\-\-nodesreachablefromi,INCLUDINGi

\-Result=desc\(A,i\)\-\-descendantsofi,EXCLUDINGi

\-Result=has\_path\(A,i,j\)\-\-1\.0ifpathexists,else0\.0

\-Result=select\(V,i,d\)\-\-selectelementialongdimd

\-Result=ge/gt/eq\(A,x\)\-\-comparisonpredicates\(return0/1\)

\-U=ones\(N\)/zeros\(N\)\-\-constructors

\-X=A\*B/A\+B/A\-B\-\-elementwiseops

\-:printResult\-\-output\(MUSTbelastline\)

RULES:

\-Startwithcomment://category\_name

\-DefineA=edges\(\.\.\.\)fortheadjacencymatrix

\-Computeanswerusingtensoroperations

\-Endwith:printResult

## Appendix GReproducibility

The experimental setup—models, decoding, prompting, scoring, and the fine\-tuning configuration—is given in §[3](https://arxiv.org/html/2608.18242#S3); all API models were evaluated in March 2026 with provider\-default settings\.

Repository\.The release at[https://github\.com/egolabs\-ai/closurebench](https://github.com/egolabs-ai/closurebench)includes:

- •The 1,300\-instance evaluation set and all model responses \(raw JSONL with reasoning traces\)
- •Instance generator:python \-m closurebench\.generator \-\-seed <N\>produces unlimited fresh instances with verified Ein ground truth
- •Evaluation harness with lenient scoring:python scripts/run\_full\_benchmark\.py
- •Ein and Python SFT training scripts \(fine\-tuned adapter weights will be released on the Hugging Face Hub\)
- •All figures and tables are reproducible from the included data and scripts

The constructive nature of the benchmark means evaluators are not limited to our 1,300 instances: generating a fresh set with a new seed takes under one minute and produces instances with machine\-verified ground truth\.

## Appendix HDatasheet, Licensing, and Maintenance

We summarise the release documentation forClosureBench, following the datasheets\-for\-datasets framework of[Gebru et al\. 2021](https://arxiv.org/html/2608.18242#bib.bib7)\.

Motivation and intended use\.ClosureBenchis intended for evaluating compositional graph\-relational reasoning in language models and for measuring memorisation through the seen\-vs\-held\-out gap\. It is a diagnostic benchmark, not a training corpus: using the released instances as training data defeats the memorisation measurement, so we discourage it\.

Composition\.Each instance is a self\-contained \(question, reference answer\) pair with metadata \(category, level, result type, structural and surface seeds, and the Ein and Python programs that compute the answer\)\. The release contains the training and held\-out splits \(1,300 instances each\) and a further 2,500 instances provided for downstream fine\-tuning\. All instances are synthetic and contain no personal, sensitive, or human\-subject data\.

Collection and generation\.Instances are generated programmatically \(Appendix[K](https://arxiv.org/html/2608.18242#A11)\); there is no human annotation, so there is no annotator bias or labelling error\. Ground truth is computed by program execution and cross\-checked between two independent implementations\.

Licensing\.The dataset and generator are released under CC BY 4\.0; the evaluation and training code under the MIT license\.

Author statement\.The authors bear all responsibility in case of any violation of rights for the released artifacts and confirm the licenses stated above\. All released instances are synthetic and machine\-generated; the release contains no third\-party, personal, or human\-subject data\.

Hosting and maintenance\.The data, generator, and evaluation harness are hosted in a public repository under a versioned release, with an archived snapshot \(assigned a DOI\) accompanying the camera\-ready; the fine\-tuned adapter weights will be released on the Hugging Face Hub\. Because every instance is regenerable from the released code and seeds, the artifact does not depend on continued hosting of any single file\. Corrections and issues are tracked in the repository\.

Reproducibility\.We follow the ML reproducibility checklist; code, data, hyperparameters, compute environment, and random seeds are documented in Appendix[G](https://arxiv.org/html/2608.18242#A7)\.

Ethics and broader impact\.The benchmark is synthetic and contains no personal data\. Its intended effect is more reliable evaluation of reasoning\. The main foreseeable misuse is training on the released instances to inflate scores, which the memorisation measurement \(§[4\.1](https://arxiv.org/html/2608.18242#S4.SS1)\) is designed to expose\.

## Appendix IOutput Schema and Scoring

JSON output schema\.Every model is asked to emit a single JSON object whose only required field isanswer\. The value type depends on the task’sresult\_type, declared at generation time and fixed across all instances of a category\. The full mapping is in[Table9](https://arxiv.org/html/2608.18242#A9.T9)\. The schema is described generically in the system prompt—no per\-category type hints or worked examples are given—so the model must infer the expected type from the question wording, exactly as a human evaluator would\. The parser accepts standard JSON and additionally tolerates one common CoT artefact: a single\{"answer": \.\.\.\}object embedded in a longer string; anything else is recorded as a format error\.

Table 9:JSON output schema\. Each instance carries a singleresult\_type; the model’s"answer"field must conform to the corresponding JSON value\. Empty sets and zero counts are valid answers\.Scoring algorithm\.Predicted answers are matched against the reference value with a single, deterministic procedure\. The strict variant is the default; the lenient variant accepts the documented source\-inclusion ambiguity for descendants/ancestors and the off\-by\-one corner of certain count categories \(concretely:±1\\pm 1for the six count categories where the natural\-language question is silent about whether the source node itself is counted, and±\\pmsource for the six set categories with the same ambiguity\)\. The lenient relaxation never accepts a value that is more than one element away from the strict reference\.

Algorithm 1MatchAnswer\(predictedpp, referencerr, typeτ\\tau, categorycc, modem∈\{strict,lenient\}m\\in\\\{\\text\{strict\},\\text\{lenient\}\\\}\)1:if

ppisNoneor

ppviolates the JSON value type for

τ\\tauthenreturnFormatError

2:endif

3:if

τ=\\tau=booleanthenreturn

Bool​\(p\)=Bool​\(r\)\\textsc\{Bool\}\(p\)=\\textsc\{Bool\}\(r\)
4:endif

5:if

τ=\\tau=integerthen

6:

δ←\|p−r\|\\delta\\leftarrow\|p\-r\|
7:if

δ=0\\delta=0thenreturnCorrect

8:endif

9:if

m=m=lenientand

c∈Ccount\_ambigc\\in C\_\{\\text\{count\\\_ambig\}\}and

δ=1\\delta=1thenreturnCorrect

10:endif

11:returnWrongAnswer

12:endif

13:if

τ=\\tau=floatthenreturn

\|p−r\|≤ϵ\|p\-r\|\\leq\\epsilon?Correct:WrongAnswer⊳\\trianglerightϵ=10−2\\epsilon\{=\}10^\{\-2\}

14:endif

15:if

τ=\\tau=setthen

16:

Sp←Set​\(p\)S\_\{p\}\\leftarrow\\textsc\{Set\}\(p\);

Sr←Set​\(r\)S\_\{r\}\\leftarrow\\textsc\{Set\}\(r\)
17:if

Sp=SrS\_\{p\}=S\_\{r\}thenreturnCorrect

18:endif

19:if

m=m=lenientand

c∈Cset\_ambigc\\in C\_\{\\text\{set\\\_ambig\}\}and

Sp​△Sr=\{source\}S\_\{p\}\\mathop\{\\triangle\}S\_\{r\}=\\\{\\text\{source\}\\\}thenreturnCorrect

20:endif

21:returnWrongAnswer

22:endif

23:if

τ=\\tau=stringthenreturn

Trim​\(p\)=Trim​\(r\)\\textsc\{Trim\}\(p\)=\\textsc\{Trim\}\(r\)?Correct:WrongAnswer

24:endif

25:if

τ=\\tau=compoundthen

26:for all

k∈keys​\(r\)k\\in\\text\{keys\}\(r\)do

27:recurse with

\(pk,rk,τk,c,m\)\(p\_\{k\},r\_\{k\},\\tau\_\{k\},c,m\); any failure

⇒\\RightarrowWrongAnswer

28:endfor

29:returnCorrect

30:endif

Ccount\_ambigC\_\{\\text\{count\\\_ambig\}\}is the set of integer\-valued categories whose natural\-language phrasing leaves source\-inclusion ambiguous:reach\_then\_count,intersect\_then\_size,aggregate\_over\_setand three others\.Cset\_ambigC\_\{\\text\{set\\\_ambig\}\}is the corresponding set\-valued list \(set\_intersect,set\_difference,ancestor,sibling,cousin,negative\_reach\)\. The complete list is in the supplementary code \(closurebench/answer\_matching\.py\)\. The strict variant of the algorithm sets both ambiguity sets to∅\\emptysetand is what we report under “strict scores” in §[3](https://arxiv.org/html/2608.18242#S3)and[Table10](https://arxiv.org/html/2608.18242#A9.T10)\.

Strict vs\. lenient scores side\-by\-side\.For transparency,[Table10](https://arxiv.org/html/2608.18242#A9.T10)reports*every*evaluated configuration under both scoring variants on the same 1,300 held\-out instances\. The strict/lenient gap is largest for direct prompting and small open models \(4\.54\.5–6\.36\.3pp, where the model hedges on the unstated source\-inclusion convention\),0\.90\.9–1\.61\.6pp for frontier CoT, and*essentially zero*\(0\.00\.0–0\.30\.3pp\) for the program\-synthesis models\. The reason is structural: Ein and Python answers are emitted by a runtime that decides source inclusion deterministically, so the model is never asked to guess the convention\.The relative ordering of methods is identical under both scorings: the program\-synthesis models lead under strict scoring \(Ein 94\.0, Python 92\.6\) by the same margin as under lenient\. Lenient scoring does not inflate the reported result\.

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±1\\pm 1/±\\pmsource corner cases\. The method ordering is preserved under both scorings\.MethodStrictLenientGap*Open models \(direct\)*Qwen2\.5\-1\.5B21\.325\.8\+4\.5\+4\.5Qwen3\.5\-2B27\.833\.0\+5\.2\+5\.2Qwen3\-4B33\.239\.5\+6\.3\+6\.3Qwen3\.5\-9B37\.843\.3\+5\.5\+5\.5*Frontier API*GPT\-4\.1 \(direct\)46\.152\.4\+6\.3\+6\.3GPT\-4\.1\-mini \(direct\)43\.949\.2\+5\.3\+5\.3Claude Sonnet 4 \(direct\)79\.181\.7\+2\.6\+2\.6Gemini 2\.5 Flash \(direct\)85\.987\.4\+1\.5\+1\.5GPT\-4\.1 \(CoT\)84\.686\.2\+1\.5\+1\.5GPT\-4\.1\-mini \(CoT\)84\.585\.8\+1\.2\+1\.2Claude Sonnet 4 \(CoT\)82\.083\.6\+1\.6\+1\.6Gemini 2\.5 Flash \(CoT\)80\.481\.3\+0\.9\+0\.9o3 \(direct\)91\.592\.8\+1\.3\+1\.3*Program synthesis \(Qwen3\-4B \+ LoRA\)*Python\+NetworkX SFT \(held\-out\)92\.692\.6\+0\.0\+0\.0Ein SFT \(held\-out\)94\.094\.3\+0\.3\+0\.3Python\+NetworkX SFT \(seen\)96\.096\.1\+0\.1\+0\.1Ein SFT \(seen\)97\.998\.0\+0\.1\+0\.1
## Appendix JFormat\-Error Decomposition

To separate reasoning errors from output\-formatting slips,[Table11](https://arxiv.org/html/2608.18242#A10.T11)decomposes every held\-out response into five mutually exclusive outcomes: strict\-correct, correct only under lenient scoring, wrong answer, format error \(malformed JSON, missing"answer"field, or wrong value type\), and no answer emitted\. The schema is stated in every system prompt \(Appendix[F](https://arxiv.org/html/2608.18242#A6)\), yet frontier CoT methods still forfeit 2–5pp to format/schema slips, and Gemini 2\.5 Flash CoT additionally returns no parseable answer on 9\.5% of instances \(its reasoning trace exhausts the output budget before emitting JSON\)\. Program\-synthesis models have effectively zero format errors because the runtime emits typed output rather than free\-form JSON\.

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\.MethodStrictLenient\-onlyWrongFormat err\.No ans\.GPT\-4\.1 \(direct\)46\.16\.343\.14\.50\.0GPT\-4\.1 \(CoT\)84\.61\.610\.72\.50\.6GPT\-4\.1\-mini \(direct\)43\.95\.344\.66\.20\.0GPT\-4\.1\-mini \(CoT\)84\.51\.310\.53\.30\.4Claude Sonnet 4 \(direct\)79\.12\.614\.63\.70\.0Claude Sonnet 4 \(CoT\)82\.01\.612\.24\.20\.0Gemini 2\.5 Flash \(direct\)85\.91\.57\.23\.51\.9Gemini 2\.5 Flash \(CoT\)80\.40\.76\.62\.89\.5o3 \(direct\)91\.51\.35\.31\.90\.0Python\+NetworkX SFT \(held\-out\)92\.60\.04\.90\.22\.3Ein SFT \(held\-out\)94\.00\.34\.90\.40\.4
## Appendix KGenerative Procedure

ClosureBenchdraws an instance in five steps, controlled by a structural seedsstrs\_\{\\text\{str\}\}and a surface seedssurfs\_\{\\text\{surf\}\}\.

Step 1: Sample the structural triple\(n,ρ,d\)\(n,\\rho,d\)\. We drawnnuniformly from\{4,…,10\}\\\{4,\\dots,10\\\},ρ\\rhouniformly from\[0\.1,0\.5\]\[0\.1,0\.5\], andd∈\{1,2,3\}d\\in\\\{1,2,3\\\}\(the size\-scaling study of §[4\.2](https://arxiv.org/html/2608.18242#S4.SS2)extendsnnto 20 on a dedicated sweep\)\. Category sampling is stratified so each of the 26 categories is represented an equal number of times in the released 1,300\-instance set\.

Step 2: Generate the graph topology\.Conditioned on\(n,ρ\)\(n,\\rho\), edges are drawn fromBernoulli⁡\(ρ\)\\mathrm\{Bernoulli\}\(\\rho\)over alln⁡\(n−1\)n\(n\-1\)ordered pairs \(directed\) or all\(n2\)\\binom\{n\}\{2\}unordered pairs \(undirected\)\. For kinship categories, the topology is constrained to a DAG with a fixed maximum out\-degree; for triangle categories, a small number of triangles is planted to make the answer non\-trivial\.

Step 3: Compute the reference answer\.The Ein program associated with the category is generated by a deterministic template that consumes the topology and any category\-specific metadata \(e\.g\., the source node, the minimum\-degree threshold\)\. The program is then executed by the Ein runtime, and its output is captured as the reference answer\. As an independent cross\-check, the same topology is also passed through a separately written Python\+NetworkX implementation of each category; the two implementations agree on every released instance \(the 1,300 evaluation split and the 1,300 held\-out split\), which guards against template errors in either one\.

Step 4: Apply surface variation\.Conditioned onssurfs\_\{\\text\{surf\}\}, the generator picks \(a\) a node\-label pool \(letters, names, server ids, animals\), \(b\) a domain frame from 16 verticals, \(c\) one of five presentation styles, and \(d\) an edge\-listing order\. The combined surface space exceeds101510^\{15\}realisations of a single underlying topology\.

Step 5: Verbalise the question\.The question template for the category is filled with surface tokens, the edges are spelled out according to the chosen presentation style, and any metadata anchors \(source nodes, threshold values\) are substituted\. The result is the natural\-language string shown to the model; the model never sees the topology, the Ein program, or the reference answer\.

Identicalsstrs\_\{\\text\{str\}\}but differentssurfs\_\{\\text\{surf\}\}yields instances with the same reference answer but no shared surface tokens\. Identicalssurfs\_\{\\text\{surf\}\}but differentsstrs\_\{\\text\{str\}\}yields surface\-identical instances with different answers\. This decomposition is what makes the seen\-vs\-held\-out gap a meaningful memorisation signal: an evaluator can always generate a held\-out batch that shares zero surface tokens with the model’s training data\.

## Appendix LQualitative Examples

We present examples illustrating the three structured failure families \(§[4\.4](https://arxiv.org/html/2608.18242#S4.SS4)\) and the Ein program\-synthesis alternative\.

### L\.1Direction confusion \(multi\_query\)

GPT\-4\.1 CoT on a 6\-node graph\. The question asks for the out\-degree and reachability of node “bear”\. The model correctly identifies the edges but confuses in\-degree with out\-degree:

> Edges: bear→\\torobin, seal→\\tobear, kiwi→\\tobear, kiwi→\\tonewt, seal→\\tokiwi, zebu→\\tokiwi \[\.\.\.\] Out\-degree of bear: bear has edges to robin\. But also seal→\\tobear, kiwi→\\tobear\. So degree = 2\. \{"answer": \[true, 2\]\}

Expected:\{reachable: true, degree: 1\}\. The out\-degree of “bear” is 1 \(→\\torobin\), not 2\. The model counted one incoming edge \(←\\leftarrowseal\) as outgoing\.

### L\.2Depth truncation \(kinship\_complex\)

GPT\-4\.1 CoT, 7\-person family\. The question asks how many people are in Uma’s lineage\. The model finds the correct root but stops too early:

> Bob is a parent of Eve\. Sam is a child of Eve\. Eve is a parent of Tina\. Bob is a child of Nina\. Frank is a child of Nina\. Root ancestor of Uma: tracing up\.\.\. Nina→\\toBob→\\toEve\. Nina is the root\. Lineage: Nina, Bob, Eve, Frank =4 \{"answer": 4\}

Expected: 7 \(Nina, Bob, Frank, Eve, Sam, Tina, Uma\)\. The model found the root \(Nina\) and her direct children \(Bob, Frank\) and grandchild \(Eve\), but missed Eve’s children \(Sam, Tina\) and Uma herself\.

### L\.3Accumulation drift \(mixed\_domain\)

GPT\-4\.1 CoT on an 8\-node graph\. The task requires computing the average out\-degree of an SCC\. The model identifies the SCC correctly but miscounts one member’s edges:

> SCC containing srv\-21: \{srv\-03, srv\-17, srv\-19, srv\-20, srv\-21, srv\-23, srv\-27\} Out\-degrees: srv\-03=1, srv\-17=2, srv\-19=2, srv\-20=5, srv\-21=3, srv\-23=1, srv\-27=3 Wait, let me recount srv\-20\.\.\. srv\-20 routes to srv\-03, srv\-17, srv\-19, srv\-21, srv\-23\. That’s 5\. Average = \(1\+2\+2\+5\+3\+1\+3\)/7 = 17/7 =2\.43 \{"answer": 2\.43\}

Expected: 2\.62 \(≈\\approx18\.33/7\)\. The model miscounted one edge for srv\-27 \(actual out\-degree 4, not 3\), shifting the average\.

### L\.4Ein program success:multi\_query\(L3\)

The same multi\_query task that frontier CoT gets wrong\. Ein SFT emits a 6\-line program:

//multi\_query

A=edges\(\[\[0,1\],\[1,2\],\[3,2\],\[3,8\],\[4,0\],\[4,7\],\[5,1\],\[5,4\],\[6,0\],\[6,5\],\[8,4\],\[8,6\]\]\)

TC=tc\(A\)

Reachable=select\(TC,0,2\)

Degree=select\(sum\(A,1\),0,0\)

:printReachable

:printDegree

Output:\{reachable: 1\.0, degree: 1\.0\}\. Correct\.The program encodes edges as an explicit matrix once, thentccomputes reachability andsum\(A,1\)computes out\-degrees—both deterministically\. No direction confusion is possible because the matrix representation is unambiguous\.

### L\.5Ein failure: correct formula, wrong edges

triangle\_count\(L1, 9\-node graph\)\. The formula is correct but the model misreads edges from the NL description:

A=edges\(\[\[0,1\],\[0,3\],\[0,5\],\[0,6\],\[1,0\],\[1,2\],\[1,3\],\[1,8\],

\[2,1\],\[2,5\],\[2,6\],\[2,7\],\[3,0\],\[3,1\],\[3,4\],\.\.\.\]\)

A2\[i,k\]=A\[i,j\]A\[j,k\]

A3\[i,j\]=A2\[i,k\]A\[k,j\]

Result=trace\(A3\)/6\.0

Output: 2\. Expected: 3\.Thetrace\(A3A^\{3\}\)/6formula is correct\. Two edges were dropped and one added—the same graph\-parsing bottleneck, but isolated to the encoding step rather than pervading the entire reasoning chain\.