How Many Things Must a Model Hold at Once? Elimination Width as the Difficulty Axis for Contamination-Free Reasoning Tests

When a language model solves a puzzle, a system of equations, or a logic problem, some of the work is bookkeeping. At every point it must keep track of the quantities it has introduced but not yet resolved. Classical graph algorithms have an exact name for this burden. If the variables of a problem are "eliminated" one at a time, solved and substituted away as in Gaussian elimination, then the largest set of variables that are simultaneously entangled during the process is the width of that elimination order. The smallest width over all orders is the problem's treewidth. Exact solvers pay a cost exponential in this width, and not in the number of variables or the length of the problem text. We propose to test whether language models pay a similar price. Concretely, we will generate fresh reasoning problems in which width is varied while node count, edge count, depth, and prompt length are held fixed. We will also build an evaluator that reads a model's free-form reasoning and recovers which elimination order the model actually followed.

This matters because contamination-free "dynamic" benchmarks currently set difficulty with crude knobs. DyVal generates reasoning problems from random directed acyclic graphs (DAGs) and varies their depth, width, and node count. The 3-SAT characterization varies the clause-to-variable ratio and shows that models exploit shortcuts such as prompt length correlating with unsatisfiability. If width is the quantity that actually governs failure, then procedural benchmarks are measuring a proxy, and apparent reasoning gains can come from shortcuts that the proxy leaves open. A width-controlled generator gives a difficulty axis that has no cheap proxy in surface statistics. Because every instance is freshly sampled, a model cannot have memorized it.

Core Claim

We make two linked claims, and both can be falsified. The first concerns problems. At fixed variable count, edge count, depth, and token length, a model's accuracy falls with the treewidth of the problem's constraint graph (the graph linking variables that appear in a common constraint), and width explains variance that the DyVal knobs do not. The second concerns presentation. The order in which constraints are written out has a width of its own: the maximum number of variables that have been mentioned but still have unmentioned constraints, which graph theorists call the vertex separation number of the order, equal to pathwidth when minimized. We predict that this presentation width, not "forward versus reversed" as such, explains the order sensitivity DyVal found (GPT-4 lost 13.6% accuracy on reachability when descriptions were given in reversed topological order). The cleanest test of the second claim uses non-topological orders with low separation and topological orders with high separation. If accuracy tracks separation rather than topological-ness, then DyVal's "reversal curse" is a width effect.

The evaluation component serves the measurement. It is not a new kind of judge. An LLM reads the candidate's reasoning and extracts its intermediate claims ("x3 = 2·x5 − 1", "so x5 must be 2"). A symbolic checker then verifies each claim exactly against the known solution space. The order in which variables are first resolved defines the model's implicit elimination order, and we compute its width. This lets us ask a question no prior work has asked: when models fail, is it because they chose a needlessly wide order, or because even the optimal order exceeds some capacity?

Research Program

The first artifact is a generator. We sample constraint graphs as partial k-trees, a standard family whose treewidth is at most k by construction. We verify the exact treewidth with an exact solver at these small sizes (8 to 30 variables). Edges are added or pruned so that graphs of different width have identical variable and edge counts. On each graph we instantiate three problem types where variable elimination is the natural algorithm. The first is sparse integer or modular linear systems, where elimination fill-in is the classical notion. The second is small-domain constraint puzzles verbalized in natural language, in the style of the 3-SAT paper's "SAT-Menu" format. The third is 3-SAT formulas whose primal graph has controlled treewidth at fixed clause ratio. A template engine pads or trims the verbalization to equalize token length across width levels. This removes the length shortcut the 3-SAT study identified.

The second artifact is the trace reader. It follows the "LLM as translator, solver as checker" design that the 3-SAT paper found near-perfect in its SAT-Translate setting. The LLM never decides whether the reasoning is correct. It only maps prose to typed claims about named variables, and the checker decides truth. We borrow from VALOR-EVAL the idea of extracting discrete units before matching. VALOR-EVAL extracts objects and relations from captions. We extract derivation steps and their order, which is a different target. Restricting the judge to extraction is also a partial defense against the family bias documented in Preference Leakage, which reports win-rate inflation up to 37.1% on Arena-Hard when judge and candidate are related. We will check this defense directly by running extractors from two model families.

The ordering ideas come from direction-one work that shows order, not content, decides whether a sequential procedure succeeds. Minimum Violation Permutations counts backward edges in a vertex order to predict extra Bellman-Ford passes, and PAFT reorders tabular columns topologically so that dependency violations fall from 22% to 3%. Both treat order as something to optimize for an algorithm or a generator. We instead treat order width as a measurement axis for a model's reasoning, and we measure the order the model itself chooses.

Baselines

The naive reference point is DyVal-style final-answer accuracy, with difficulty indexed by node count, depth, and prompt length. We run it on exactly our instances, so the only question is which predictors explain success. Beating it means that adding width to a logistic regression of per-item correctness improves held-out log-likelihood significantly, with confidence intervals from bootstrap over graphs, for each of at least three models. It also means width's coefficient stays significant when length and depth are included.

The strongest existing difficulty knob is the clause-to-variable ratio from the 3-SAT study, which reports GPT-4 SAT-Search accuracy of roughly 10% at the phase transition (α ≈ 4.267). We reproduce α sweeps on our 3-SAT generator with the same models and decoding budget. We then show that at fixed α and fixed length, varying treewidth still moves accuracy. If width at fixed α produces no spread, width adds nothing over α for SAT.

For trace grading, the strongest competitor is a monolithic LLM judge that is shown the problem, the reference solution, and the trace, and asked with chain-of-thought whether every step is valid. Evaluating Open-QA Evaluation reports GPT-4 at 96–98% agreement with human consensus on EVOUNA-TriviaQA. That result concerns final-answer correctness, and we found no reported result on Lacuna for monolithic LLM judges grading step validity of multi-step reasoning traces. Both judges get the same judge model, the same prompt-tuning budget on a disjoint development set, and the same 600 human-labeled traces for testing. Beating it means higher step-level agreement (Cohen's kappa) with humans. It also means the implicit elimination order is recovered more accurately, measured against orders annotated by hand.

The key ablation isolates presentation order. The constraint set, verbalization, and length are held fixed, and only the order of sentences changes. We compare four conditions: topological with low separation, topological with high separation, non-topological with low separation, and non-topological with high separation.

Why not just…?

Why not just keep DyVal's depth and node-count knobs? They may already capture everything. In the partial k-trees we sample, width and depth are correlated, so the regression must include both. If width's coefficient vanishes once depth is included, we will report that depth suffices and drop the first claim. The equal-edge, equal-length construction exists precisely so this outcome can happen.

Why not just use a chain-of-thought LLM judge to grade traces? Graded validity is not enough. We also need the order of resolution, which is a structured object that free-form verdicts do not expose. There is also evidence that chain-of-thought helps on linear text but not graph structure. In DyVal, 33.8% of GPT-4 failures were answers given without substantiating steps, and the NLGIFT study found chain-of-thought ineffective for out-of-distribution graph reasoning. Still, this alternative is a real threat on grading accuracy alone. If the monolithic judge matches our pipeline in step-level kappa, we will say the extraction pipeline is justified only by order recovery.

Why not just refresh or paraphrase static benchmarks, as EvoEval does? Refactoring exposed large memorization effects: the contamination survey reports an average 39.4% drop across 51 models. But refactored sets freeze once published, and paraphrase gives no control over structural difficulty. Our generator is procedural, so staleness is not an issue. We still test for residual template memorization, as described below.

Why not just hand models a solver? The 3-SAT results show translation to a solver works. That settles what tools can do, but it says nothing about what the model does unaided, which is what benchmarks claim to measure.

Proposed Experiments

We evaluate at least two open-weight model families at two sizes plus one API model on 500 instances per cell, matching DyVal's per-dataset sample size. The grid covers three problem types, treewidth 1 through 6, and three variable counts. The first decisive check is the width regression described under Baselines. The second is the four-condition presentation ablation. The prediction is a main effect of separation and no effect of topological-ness once separation is controlled. The opposite result would mean the reversal effect is about causal direction, not bookkeeping load.

The third check uses the implicit orders from correct and failed traces. We test whether failures concentrate where the model's chosen width exceeds the instance's treewidth, which would mean the model picked a bad order. The alternative is that failures begin at a model-specific width threshold regardless of choice, which would mean a capacity limit. We will then prompt models with an optimal elimination order to see whether the first kind of failure is recoverable.

The fourth check probes contamination. We build instances whose constraint graphs are isomorphic to famous puzzles, such as the zebra puzzle structure, under fresh variable names and cover stories. We compare them with random graphs matched on width, size, and length. An accuracy advantage on the famous structures would indicate memorized solution templates surviving surface relabeling, a structural form of the "semantic-level" contamination in the survey's taxonomy. Finally, we validate the trace reader on the 600 human-labeled traces and run it with extractors from two families, so that any family-dependent disagreement in recovered orders is measured rather than assumed away.