Length Penalties Cannot Reach Every Reasoning Budget: Ensemble Inequivalence in Reasoning Graphs

There are two common ways to make a reasoning model think less. One imposes a hard budget: a cap on the steps or tokens it may spend. The other adds a soft penalty, a cost per token, inside reranking or reinforcement learning. Practitioners treat these as interchangeable, on the assumption that some penalty strength reproduces any budget you want. Statistical physics has a precise account of when that assumption fails. Fixing a system's energy exactly (the "microcanonical" description) and fixing only a price on energy (the "canonical," temperature-controlled description) give different states whenever the log-count of states at a given energy is not a concave function of that energy. This happens in systems where parts interact over long range, so the whole is not the sum of its parts.

We propose that reasoning traces are such a system. Logical dependency mapping turns a chain of thought into a directed acyclic graph (DAG), where each node is a claim and each edge points to the claims it relies on. Under that mapping, a trace's validity is non-additive: one broken parent invalidates every descendant. Our hypothesis is that this non-additivity makes the count of fully valid traces, viewed as a function of length, non-concave. There would be a short "deductive" mode and a long "speculative branching" mode, with a depleted middle. If so, no length penalty can ever produce traces in that middle range, sweeping the penalty makes average length jump discontinuously, and only budget-conditioned methods can reach those lengths. The project measures this curve directly on graph-annotated math benchmarks and tests whether the unreachable middle is where the best accuracy per token lives.

Core Claim

Let $\tau$ be a complete reasoning trace sampled from a reference model $\pi_{\text{ref}}$. Let $E(\tau)$ be its structural cost, measured as the number of nodes in its extracted dependency DAG, with token count as a secondary measure. Let $V(\tau)\in\{0,1\}$ indicate that the trace is perfect: it reaches the correct answer and is logically closed, meaning every step has valid parents and contributes to the answer. This is the Perfect Reasoning Rate criterion of DAG-Math. Define the structural entropy

$$s(E) = \log \Pr_{\tau\sim\pi_{\text{ref}}}\big[V(\tau)=1,\ E(\tau)=E\big],$$

which is the log-mass of perfect traces at cost $E$. A per-token penalty of strength $\lambda$ yields the tilted ("canonical") distribution $\pi_\lambda(\tau)\propto \pi_{\text{ref}}(\tau)V(\tau)e^{-\lambda E(\tau)}$. This is also the known optimum of KL-regularized RL with a length-penalized reward, so the setting covers training as well as reranking. Its mean cost satisfies

$$\frac{d\langle E\rangle_\lambda}{d\lambda} = -\mathrm{Var}_\lambda(E).$$

The canonical family therefore only reaches costs on the concave hull of $s$. Wherever $s$ dips below its hull, $\langle E\rangle_\lambda$ jumps across the dip at a critical $\lambda^*$, and the length distribution turns bimodal there. The size of this length-variance spike is the analogue of a specific-heat peak at a first-order phase transition.

Inside the dip, $ds/dE$ increases with $E$. In plain terms, each extra unit of budget buys more perfect traces than the last. This is the reasoning analogue of negative specific heat, which is stable only under a fixed budget.

The new, falsifiable claim has two parts. First, $s(E)$ is measurably non-concave on hard problems. Second, the non-concavity comes from the DAG's non-additive validity, not from length alone. Replacing DAG closure with an additive per-step score should restore concavity.

Grounding in Prior Work

The physics supplies the method. Venaille and Bouchet compare fixed-energy entropy maximization with its Lagrange-multiplier relaxation for 2D and geophysical flows. They show that states with negative specific heat exist only in the fixed-energy description and that phase transitions differ between the two. Equilibrium and out of equilibrium phase transitions in systems with long range interactions and in 2D flows and Statistical mechanics of two-dimensional and geophysical flows trace this breakdown to non-additivity. We reuse exactly one piece of this machinery: the diagnostic that inequivalence is detected by non-concavity of entropy in the constrained quantity. We do not claim fluids and proofs share dynamics.

The work on positive and negative temperatures in multimode fibers, Bridging Rayleigh-Jeans and Bose-Einstein condensation, concerns bounded spectra. We set it aside, because "negative temperature reasoning" lacks an operational test we find convincing.

The reasoning literature motivates the hypothesis. DAG-Math finds that failing models show "speculative branching," an explosion in the number of branches leaving a step, rather than deductive aggregation. It reports Gemini-2.5-Flash at 52.4% accuracy but only 17.0% PRR on AIME 2025. That points to two qualitatively different trace populations, which is what a bimodal $s(E)$ would produce. CoTJudger extracts the shortest effective path through a reasoning graph and finds redundancy of up to 86.5% (Qwen3-Max), with a U-shaped dependence on difficulty. Both papers describe these structures but offer no account of why budget controls behave as they do; that account is what we add.

CGRiC makes the non-additivity concrete. It propagates risk through claim DAGs because a flawed parent poisons its descendants.

The strongest selection method we compete against is the Thinking Reward Model of Characterizing, Evaluating, and Optimizing Complex Reasoning. It scores traces by structural quality and treats length as one preference signal among several; it never asks which budgets a penalty can reach.

Research Program

The first stage measures $s(E)$. For each problem, we sample several hundred complete traces from Qwen3-8B, plus one larger open model, using the DAG-MATH schema (step identifier, inference rule, parent steps, conclusion) from the DAG-MATH codebase. We then score closure and correctness.

To keep generation from being forced short, sampling uses a generous cap well above the 4,096-token limit noted in Omni-MATH. We pool problems within each Omni-MATH difficulty tier. To get statistics in the thin middle region, we estimate $s(E)$ by reweighting samples drawn under length-steering prompts back to the reference distribution. Concavity is tested with a bootstrap: we measure the area between $s$ and its concave hull and form a confidence interval.

Extraction noise is a known weakness. Stepwise Confidence Attribution reports 93–99% formatting success, and DAG-MATH reports 98% human-validated dependency accuracy. We therefore repeat the measurement with two independent extraction judges and on the 2,894 gold DAGs.

The second stage isolates the mechanism. We recompute $s(E)$ with the validity indicator replaced by an additive surrogate: a thresholded sum of per-step scores in which each step is judged ignoring its ancestors. The hypothesis predicts that the DAG-closure curve is non-concave and the additive curve is concave on the same traces.

The third stage tests consequences. We sweep $\lambda$ in penalized Best-of-N and look for jumps in mean $E$, bimodality, and a variance spike at $\lambda^*$. We then compare this against fixed-budget selection, which picks the best-scored trace whose $E$ lies in a narrow window. The key quantity is PRR per unit cost in the window the canonical family skips. As a smaller-scale follow-up, we compare length-penalized and budget-window RL fine-tuning on Qwen3-8B. The prediction is that only the second can be trained to land in the dip.

Baselines

The naive reference is single-sample decoding at the model's default temperature, plus hard truncation at a fixed token cap of the kind used in Omni-MATH. Truncation is the usual way a "budget" is imposed today. It is not conditioning on complete traces of a given cost, and we expect it to lose PRR by cutting traces before closure.

The strongest existing selection method is TRM-guided Best-of-N from Characterizing, Evaluating, and Optimizing Complex Reasoning. It reports Qwen3-8B on AIME24 rising from 44.7% at N=1 to 64.0% at N=16. We run it on the same sampled pools and the same N, using the released reward model if available. Otherwise we use an equal-budget retrained version, flagged as a replication.

The direct canonical competitor is that same TRM score minus $\lambda E$, with $\lambda$ tuned on a held-out split using the same search budget given to the window width of our method. The comparison is fair because both methods choose from identical sample pools at identical generation cost, so the only difference is penalty versus constraint.

Self-consistency majority voting is a further reference. CGRiC reports about 400% overhead for it. For it and for penalized selection on PRR-per-node, we found no reported result on Lacuna.

The key-ingredient ablation is the additive-surrogate validity described above. Beating the canonical baseline means one of two outcomes. Either budget-window selection attains PRR at matched mean cost that no $\lambda$ achieves, with a bootstrap interval excluding zero, or it reaches a cost range the $\lambda$ sweep provably skips with at least equal PRR. Matching TRM Best-of-N accuracy at lower mean cost would count as a practical win, not a theoretical one.

Why not just…?

Why not just sweep the length penalty or the sampling temperature finely? This is precisely what the theory says cannot work in the dip. A finer sweep only sharpens the jump at $\lambda^*$; it never lands inside it, because the tilted mean moves only along the concave hull. The $\lambda$-sweep experiment settles this directly. If mean cost varies smoothly and $s(E)$ is concave, the simpler method suffices, and we will report that as the outcome.

Isn't this just the Lagrangian duality gap? For selection from a fixed pool, yes. The hull result is standard convex duality, and we do not claim it as new. What is new is the empirical claim that dependency-graph validity produces the non-concavity, together with its distribution-level consequences for KL-regularized training: bimodality, the variance spike, and the reachability of budgets by penalized RL. Duality alone predicts none of these for any particular task.

Why not just use TRM Best-of-N and ignore budgets? It is the strongest accuracy method and may remain so at large N. But it gives no control over cost, and it is orthogonal to the question here. We combine it with both penalty and window selection, so any gain we report is the effect of constraint versus penalty holding the scorer fixed.

Why not just truncate at a hard token cap? Truncation yields cut-off traces rather than complete traces of a given cost, so it is not the fixed-budget ensemble. CoTJudger's redundancy findings suggest truncation removes the end of the trace, where closure happens, rather than the redundant middle. Our truncation baseline measures this cost directly.

Proposed Experiments and Decisive Checks

The benchmarks are the DAG-MATH gold set (2,894 graph-annotated traces from Omni-MATH, levels 1–6), Omni-MATH tiers for difficulty dependence, and AIME 2024/2025 for comparison with TRM and DAG-Math figures.

The project stands or falls on four checks. First, the concave-hull gap of DAG-closure $s(E)$ must be significantly positive on at least the harder tiers, under both extraction judges. Second, the additive-surrogate curve must be concave on the same traces; if both curves are non-concave, the dependency-structure explanation fails even if the phenomenon is real. Third, the penalized-selection sweep must show a discontinuity in mean cost, with a length-variance peak at the $\lambda$ predicted from the measured $s(E)$. Fourth, budget-window selection must beat tuned penalized selection on PRR at costs inside the predicted gap.

If the first check fails, we will have shown that length penalties and budgets are interchangeable for current reasoning models. That is a useful negative result, and it licenses the simpler practice.