PaperlayerView exact revision on arXiv

Source-linked AI summary

Trace as State: Reasoning Traces as Conditional States for Long-Context Transformers

Xu Zou, Jie Tang

arXiv:2609.02702v1cs.CL

TL;DR

Long-context reasoning can depend on task state discovered only after earlier context has been processed, creating a mismatch with causal Transformers. The paper formalizes this through conditional state updates and introduces TRACE AS STATE, which places reasoning traces before context rereading; it outperforms TRACE APPEND in 26 of 27 reported combinations. Its evaluated realization requires access to raw reasoning traces or another exposed state interface.

  • Problem

    Causal Transformers cannot use later-discovered task state to alter representations already formed for preceding context tokens.

  • Method

    TRACE AS STATE serializes collected reasoning traces as textual task-state proxies and places them before the long-context block in a fresh causal pass.

  • Results

    26 of 27 reported combinations favor TRACE AS STATE over TRACE APPEND across three models, three tasks, and three metrics.

  • Takeaways & Limitations

    The results support placing useful task-state information before context rereading while retaining causal processing within each pass.

  • Takeaways & Limitations

    The evaluated method requires access to raw reasoning traces or another exposed state interface, so final-answer-only APIs may require a different interface.

Abstract

from arXiv · show

Transformers process information causally, but long-context reasoning may depend on task state discovered only later. We formalize this mismatch through conditional state update tasks. For causal state update processors, providing the condition first can require exponentially less memory in the worst case than providing it last. Motivated by this principle, we introduce Trace as State. We use collected reasoning traces as a textual proxy for task state and place it before the long-context block on a fresh pass, allowing information derived previously to guide rereading. We conduct extensive experiments on Trace as State and Trace Append, a matched control that uses the same task state proxy but put it after the context. Across three models and three long-context datasets, Trace as State outperforms Trace Append in 26 of 27 reported combinations of model, task, and metric. On GraphWalks Parents, exact match lifts DeepSeek V4 Pro Preview from 29.2% on the initial pass and 43.0% with Trace Appendto 81.8% with Trace as State, and from 66.4% and 83.2% to 100.0% for GLM-5.2. These results show that placing traces before the context can improve long-context reasoning while retaining the causal transformer structure.

1 Introduction

Long-context reasoning faces a mismatch between causal input order and when task-relevant state becomes available. TRACE AS STATE addresses this by feeding serialized reasoning traces before rereading the context, outperforming TRACE APPEND in nearly all reported combinations.

  • Long-context tasks may require state such as an active target, search frontier, or rejected hypotheses that becomes available only after earlier context processing.
  • Condition-first processing can require exponentially less worst-case memory than condition-last processing for causal state updates.
  • TRACE AS STATE feeds collected reasoning traces back as textual state proxies before the long-context block in a fresh causal pass.
  • TRACE APPEND uses the same trace proxy after the context, allowing it to guide later reasoning but not earlier context representations.
  • 26 of 27 reported combinations favor TRACE AS STATE over TRACE APPEND across three models and three long-context benchmarks.

2 Related Work

Related work studies long-context sensitivity, causal-order effects, architectural recurrence, rereading, textual feedback, and reasoning traces as externalized computational state.

  • Long-context evaluations remain sensitive to evidence position, distractors, and the operations needed to combine information across an input.
  • Prior approaches address causal-order limitations through repeated options, repeated context, recurrent computation, or iterative text processing.
  • Rereading and textual-feedback methods carry task-relevant text forward, including repeated questions, bounded histories, and recursively replayed evidence pools.
  • TRACE AS STATE is illustrated as placing a textual task-state proxy before the context during a fresh causal pass.
  • Recent work treats reasoning traces as records of evolving computational state, while also finding that models may not reliably acknowledge their influence.

3 Methodology

The methodology formalizes order-dependent memory in causal state updates and tests whether reasoning traces are more useful before, rather than after, context rereading.

  • Causal State Updates: A causal state update processor reads each input unit once and updates persistent memory using its current memory and the newly received unit.
  • Conditional State Updates: A conditional state update task sets the initial state to condition z, applies the update rule across C, and returns the final state.
  • Order-Dependent Memory: Condition-first order [z, C] lets the processor update the realized state path, whereas condition-last order [C, z] delays selection of the path until after C.
  • Order-Dependent Memory: Condition-last processing may require exponentially more memory in the worst case because it must preserve response profiles for every possible initial condition.
  • Trace as State: Reasoning traces are treated as incomplete, lossy, or incorrect textual proxies for task state rather than privileged internal states.
  • Trace Placement: TRACE AS STATE runs the model on x, serializes collected traces as T, and supplies [T, x] on a fresh pass; TRACE APPEND supplies [x, T].

4 Experiments

The experiments test Trace as State against Trace Append across three models and long-context datasets, finding a broad advantage for placing reused reasoning traces before the context.

  • Main results: Across 27 model-task-metric combinations, Trace as State scores higher than Trace Append in 26.DeepSeek V4 Pro and Qwen 3.7 Max favor Trace as State throughout; GLM-5.2 differs only on GraphWalks BFS F1, where Trace Append is 0.8 points higher.
  • Main results: Trace as State also scores above the first pass in all reported evaluations.Trace Append improves over the first pass in many settings, indicating that reused trace text can carry useful information.
  • Context-order ablations: Question First substantially improves Parents performance but remains similar to the first-pass baseline on BFS.This suggests that the question itself may provide vital task state for some tasks.
  • Context-order ablations: Re2 improves substantially over the first pass but remains below Trace as State, especially on Parents.The comparison is consistent with serialized reasoning text carrying task-relevant information beyond prompt repetition alone.
  • Control ablations: Trace Only performs similarly to Trace Append but remains well below Trace as State, while Trace as State also outperforms Oracle@5.These controls weaken explanations based solely on generic scaffolding, first-pass answers, or retrospective selection of the best output.
  • Trace-count ablation: Trace as State remains above Trace Append for every trace count from ntr = 1 through ntr = 5.Both conditions receive the same realized traces, and each averages five fresh second-pass repeats per problem.

5 Conclusion

The paper introduces TRACE AS STATE, reusing reasoning traces as textual task-state proxies before rereading long contexts. Its theory and experiments support the view that both carrying state forward and its placement affect long-context reasoning.

  • TRACE AS STATE reuses reasoning traces as textual task-state proxies on a fresh pass over long-context tasks.The method adds cross-pass feedback while retaining causal processing within each pass.
  • The method applies an ordering principle motivated by conditional state-update tasks, where early conditions can guide evolving state more efficiently than late conditions.
  • TRACE AS STATE places prior reasoning before the long-context block so the model can use it while rereading the context.
  • The paper identifies trace selection, compression, improved textual state interfaces, and feedback placement as direct extensions.A broader training framework could jointly learn the model and feedback interface while retaining causal processing within each pass.

Limitations

The evaluated realization depends on accessible reasoning traces or another exposed state interface, adds inference cost, and has limited tested scope. Models exposing only final answers may require a different interface, while broader generalization remains unestablished.

  • The experiments require raw reasoning traces or another accessible state interface; final-answer-only APIs may require a different interface.
  • TRACE AS STATE adds one or more source runs and a fresh pass, increasing inference latency and token cost.Putting state before the original context can also reduce key–value cache reuse in multi-round settings.
  • The evaluation covers three causal transformer models and three long-context task families, without testing multi-round agent tasks.Additional models, domains, context lengths, and interactive settings are needed to establish broader generalization.
  • Because the method reuses only model-generated traces, it introduces no additional ethical concerns or misuse risks beyond those of the underlying models and tasks.

A Attaining the Worst-Case Residual-Map Count

The appendix constructs a finite-state conditional-update task whose residual maps attain the maximum count, establishing a worst-case late-order memory requirement. It also specifies the causal working-state model, scope conditions, and evaluation-scoring details.

  • A Attaining the Worst-Case Residual-Map Count: For an information sequence C, the residual map sends each initial state to its updated state, and K counts distinct residual maps.
  • A Attaining the Worst-Case Residual-Map Count: The corresponding late-order exact working-memory requirement is ⌈|S| log2 |S|⌉ bits.
  • A Attaining the Worst-Case Residual-Map Count: For every finite nonempty state set S, the construction achieves K = |S|^|S|, the maximum possible residual-map count.
  • A Attaining the Worst-Case Residual-Map Count: A condition-first processor needs only a single S-valued register, while the late-order cut must distinguish all residual maps.The condition-first cut has m possible configurations, whereas the late-order construction requires |S|^|S| configurations.
  • A Attaining the Worst-Case Residual-Map Count: The lower bound is an adversarial worst-case result for deterministic, exact, one-pass processors with all persistent writable storage counted.Restricted update families may yield fewer residual maps and a smaller lower bound.
  • A Attaining the Worst-Case Residual-Map Count: Causal transformers fit the state-update abstraction when finite context length and finite precision make their working configuration space finite.The working state includes position, layerwise key–value entries, and other persistent input-dependent inference buffers.
  • A Attaining the Worst-Case Residual-Map Count: The appendix documents scorer edge cases, run qualifications, and record-selection rules for the reported evaluation cells.GraphWalks, MRCRv2, and NUB-1M use task-specific answer extraction and scoring procedures.

C Prompt and State Templates

The appendix fixes how first-pass reasoning traces are serialized into T and how T is placed relative to each dataset’s long-context prompt. It also records model-specific instructions, dataset prompts, and answer-format controls.

  • C.1 Reusable Trace Block: T contains selected first-pass reasoning traces in source order plus a dataset-specific preamble PD.PD is part of T, while visible answers remain outside it.
  • C.1 Reusable Trace Block: Reasoning fields longer than 50,000 characters are truncated to their first 50,000 characters before block formatting removes surrounding whitespace.
  • C.2 Model-Specific Details: Qwen 3.7 Max uses a fixed xhigh reasoning instruction asking the model to validate assumptions, consider alternatives, and prioritize correctness, consistency, and clarity.The instruction is prompt text rather than a provider-side reasoning_effort value.
  • C.2 Model-Specific Details: The fixed serializer adds delimiters and introductory text while preserving reasoning traces, with truncation used to keep second-pass prompts within context capacity.
  • C.2 Model-Specific Details: The experiments use the 2026-4-24 version of Deepseek V4 Pro.
  • C.3 Dataset-Specific Details: For GraphWalks, the trace preamble warns that traces may contain mistakes and instructs verification against the graph.
  • C.3 Dataset-Specific Details: GraphWalks uses a directed-graph system prompt requiring exactly one visible Final Answer line and an identical answer-format instruction appended to the user message.
  • C.3 Dataset-Specific Details: TRACE AS STATE places the complete trace block before the released GraphWalks prompt, whereas TRACE APPEND inserts the identical block before the final Operation and answer-format instruction.MRCRv2 traces are presented as scratchpad hints and must be checked against the conversation and final request.

D GraphWalks Difficulty Profiles

The GraphWalks difficulty analysis examines whether TRACE AS STATE’s timing advantage varies across BFS depth and gold parent-set size. The resulting profiles are descriptive and outcome-informed, not confirmatory evidence about mechanisms.

  • Difficulty variables: The diagnostic stratifies GraphWalks by BFS depth d and Parents gold parent-set size k, while noting that frontier size, early termination, and graph structure also affect difficulty.
  • Binning: BFS bins are 1–2, 3–4, 5–6, 7–8, and 9–10, with problem counts 17, 25, 21, 15, and 22.
  • Estimation: Each plotted point averages five stored repeats within each problem and then averages the problems in its bin.
  • Exact-match profiles: DeepSeek V4 Pro’s largest BFS timing gaps occur at d = 3–6, while Qwen 3.7 Max shows a smaller concentration in the same range.
  • Exact-match profiles: GLM-5.2 has positive exact-match gaps through d = 8 and reverses in the final pooled bin; Parents profiles differ across models.
  • Exact-match profiles: TRACE AS STATE is never below TRACE APPEND in plotted exact-match Parents bins, tying Qwen 3.7 Max at k = 0; Qwen’s separation grows with k.
  • Set F1 profiles: Set F1 preserves the strong DeepSeek V4 Pro BFS pattern, while Parents generally favors TRACE AS STATE with substantial variation in gap size.Set F1 measures partial overlap between predicted and gold node sets.

E Confidence Intervals

The confidence analysis reports paired uncertainty for the main same-T timing contrast and bootstrap uncertainty for broader results and ablations. Most paired intervals favor TRACE AS STATE, but several cross zero.

  • Paired timing contrast: 20 of 24 paired TRACE AS STATE-minus-TRACE APPEND intervals lie fully above zero.Intervals are unadjusted 95% percentile intervals after averaging five repeats within each problem.
  • Paired timing contrast: The four intervals crossing zero are DeepSeek V4 Pro MRCRv2 512K EM, Qwen 3.7 Max GraphWalks BFS F1, and two GLM-5.2 GraphWalks cells.
  • Bootstrap uncertainty: Figures 5 and 6 show cell means with 95% percentile intervals from problem-cluster bootstrap resampling, averaging repeats within each problem.
  • Figure coverage: Figure 5 covers strict same-T GraphWalks and MRCRv2 comparisons plus NUB-1M, while Figure 6 covers the GraphWalks control ablation.
  • Figure coverage: NUB-1M intervals are wider, consistent with its 20 evaluated questions.
  • Paired timing contrast: Table 5 uses n = 100 per cell, 20,000 resamples, and seed 0 for its problem-cluster uncertainty intervals.

GraphWalks 256K control ablations - Exact Match

The GraphWalks control-ablation uncertainty figure summarizes exact-match and set-F1 comparisons for DeepSeek V4 Pro. It reports means with bootstrap intervals and includes majority and oracle controls.

  • Control comparisons: Figure 6 reports DeepSeek V4 Pro GraphWalks 256K control comparisons for exact match and set F1.
  • Uncertainty: Points are means with 95% percentile intervals from 20,000 problem-cluster bootstrap resamples using seed 0.
  • Control metrics: Majority@5 retains answer elements appearing in at least three repeat-level prediction sets, while Oracle@5 reports the retrospective maximum evaluator score among five outputs.

F Token Usage

Table 6 reports provider-reported token usage for solver calls underlying the main results, including pass-specific and combined totals for the trace methods.

  • Table 6 reports token counts returned by provider APIs for solver calls underlying the main results.
  • For retained responses, usage is divided into cached input, missed input, and output tokens.Missed input equals total input minus cached input, and reasoning tokens are included in output.
  • First Pass is the shared source pass used to construct T for Trace as State and Trace Append.
  • The Total tokens columns for Trace as State and Trace Append add their corresponding First Pass counts component-wise.
  • Tokens are reported in millions for the pass named in each row, while Total tokens columns are blank for First Pass.
Loading 2609.02702v1…