Trace as State: Simple Inference-Time Scaling Lifts DeepSeek V4 Pro 29%→82%

Input Order vs. Reasoning Order Mismatch

Context windows have scaled to millions of tokens, yet causal attention remains unchanged: later information cannot influence earlier representations formed in the same forward pass. Long-context reasoning often requires maintaining task state (search targets, excluded hypotheses) that are only discovered after reading the context and beginning reasoning. An intuitive example: reading a 500,000-word novel only to be told in the last chapter "find the villain" — all preceding details were processed without that goal.

Google DeepMind notes that reasoning performance depends not only on where supporting information appears but also on their relative presentation order.

Method: Trace as State

The reasoning trace is an observable textual proxy for task state (possibly incomplete or erroneous but containing useful state information). The process follows a "read→compute→feedback→reread" loop:

First pass: run normally n_tr times to collect traces.

Serialize traces into text T (adding only delimiters and a prompt that traces may contain errors and must be verified against the original text).

Second pass: strictly compare two placements — [T, x, q] (prepended, Trace as State) vs [x, T, q] (appended, Trace Append). Same x, same T, same model; only order differs.

Theory: Conditional State Update and Exponential Memory Separation

Model the transformer as a causal state updater: reading sequence C = (c₁,…,cₙ), updating state via sᵢ = U(sᵢ₋₁, cᵢ); a "condition" z determines the initial state. Compare two orders (Figure 1B):

Condition first [z, C] : only need to store current state, ⌈b⌉ bits (where b = log₂|S|).

Condition last [C, z] : after reading the sequence, the model must know which initial state to propagate, requiring a full response archive for every possible z. There are |S|^|S| functions from S to itself, worst-case needing ⌈b·2ᵇ⌉ bits — an exponential gap.

This yields an ordering principle : a task condition available before the information it guides is far more useful.

Experimental Setup

Three models (all at max reasoning strength, input budget ~1M tokens):

DeepSeek V4 Pro Preview (CSA+HCA+mHC)

Qwen 3.7 Max (GDN+GA, xhigh prompt)

GLM-5.2 (1M MoE, DSA+IndexCache)

Three benchmarks:

GraphWalks 256K (graph state maintenance, EM+F1)

MRCRv2 8-needle (request binding, EM+Seq. ratio)

NUB-1M (long novel understanding, model-judged accuracy)

Each question repeated 5 times, averaged; second pass includes all 5 traces (truncated to 50k characters).

Main Results: 27 Wins out of 27 Comparisons

GraphWalks Parents shows largest gains (directly targets "state-first"): DeepSeek V4 Pro F1 46.5→91.3; Qwen 3.7 Max EM 60.8→96.4; GLM-5.2 EM/F1 both perfect 100%.

DeepSeek V4 Pro and Qwen 3.7 Max favor prepended traces on every dataset×metric; sole exception is GLM-5.2 BFS F1 (append leads by 0.8 points, but EM still favors prepend).

Trace Append often beats the first-pass baseline (traces do contain information), but prepended traces add further value — "prepend" captures value that "append" cannot.

Ablations: Ruling Out Alternative Explanations

A suite of controls eliminates other explanations:

Question First helps only on some tasks.

Re2 (reread) helps but far less than prepended traces.

Answer Feedback (only answer) shows traces are more useful than answers.

Random Trace (another question's trace) performs worse than no trace — gains must come from same-question traces, ruling out format scaffolding.

Trace Only (no original text) far below prepend — original text remains essential; prepend even exceeds Oracle@5 (picking best answer post-hoc).

Varying trace count n_tr from 1 to 5 shows monotonic performance increase with ordering advantage maintained throughout — trace count itself is an inference-time scaling knob .

Difficulty Analysis and Statistical Significance

Binning by BFS depth d and parent count k: DeepSeek V4 Pro gains concentrate at d=3–6 (max +48.8 points); Qwen's gap widens with k ( k≥6 yields +71.7 points). Authors honestly note these bins are post-hoc annotations, only for hypothesis generation.

Paired bootstrap shows 20 of 24 cells have confidence intervals entirely above zero ; largest difference on DeepSeek V4 Pro Parents EM: +38.80 [+31.60, +46.20].

Cost Analysis

Two-pass inference ≈ doubles input tokens; however, rereading with state reduces output (including reasoning tokens) substantially (DeepSeek V4 Pro on GraphWalks drops from 62.5M to 28.0M). Trade-off: state prepend reduces KV-cache reuse in multi-turn scenarios.

Conclusion

The bottleneck of long-context reasoning is not just window length but information order — placing first-pass insights at the beginning for a second read is a simple method backed by the hard principle of exponential memory separation.

https://arxiv.org/pdf/2609.02702
Trace as State: Reasoning Traces as Conditional States for Long-Context Transformers