Research map / Large language models / Reasoning and chain of thought

The Deterministic Horizon: When Extended Reasoning Fails and Tool Delegation Becomes Necessary

ICML 2026 · Large language models › Reasoning and chain of thought · approach: Long CoT dynamics and efficiency · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Argues that extended chain-of-thought degrades deterministic state tracking due to attention capacity limits, proposes a context-dependent error model and a Deterministic Horizon d*, and shows tool delegation (BFS solver) far outperforms neural CoT on PermutationProbe and real-world task families.

Problem

Extended chain-of-thought reasoning degrades accuracy on deterministic state-space tracking tasks; the paper asks whether this is due to decoder-only attention capacity limits rather than preference biases, and when tool delegation becomes necessary.

Approach

Proposes a context-dependent per-step error model epsilon(d)=eps0+gamma*d/Leff motivated by attention entropy, derives a Deterministic Horizon d* as the depth where success probability crosses alpha, and contrasts neural CoT with tool delegation via an exact BFS solver.

Key results

• Tool delegation (C3, BFS solver) reaches 76-94% accuracy vs 17-42% for neural CoT (C1) on PermutationProbe depth>20 across twelve models.
• Fine-tuning Llama-3.1-8B on 5,000 optimal-length traces improves only +0.9 pp over C1; length prompting (C4) gains +0.6-1.2 pp.
• Deterministic Horizon d* in [19,31] at alpha=0.5; GPT-4o d*≈22.3 from fitted parameters eps0=0.02, gamma=0.15, Leff=150.

Surprising findings

• Fine-tuning on optimal-length traces yields under 3 pp improvement, interpreted as an architectural ceiling.
• Attention entropy explains only a minority of the fitted per-step error growth by the authors' own calculation (~11% of the required budget).

Limitations

• Closed-model architectures (H, d_h) are undisclosed, so d* scaling is validated only on four open-weight models sharing d_h=128.
• Tool condition uses an exact BFS solver, so the C1-C3 gap upper-bounds delegation benefit; imperfect tools not evaluated.
• Theoretical bounds rely on assumed attention concentration and decorrelation; parameters gamma and Leff are fixed by assumption rather than identified.

Experimental setup

Datasets: PermutationProbe FSA-Sim ArithChain CircuitTrace CodeProbe SWE-Bench WebArena Spider

Benchmarks: PermutationProbe SWE-Bench-State WebArena-Nav SQL-Multi

Metrics: accuracy state-space jaccard (SSJ) precision recall Deterministic Horizon d*

Baselines: C2 oracle depth C3 BFS solver tool access C4 length encouragement C5 fine-tuning on optimal traces Sub-task difficulty account (Wu et al.)

Builds on: chain-of-thought prompting LLM-Modulo

Closest papers by meaning

• State of Thought Enables Endogenous Reasoning (NeurIPS 2026 · similarity 0.88)
• Bounds of Chain-of-Thought Robustness: Reasoning Steps, Embed Norms, and Beyond (ICLR 2026 · similarity 0.88)
• Modeling Hierarchical Thinking in Large Reasoning Models (ICML 2026 · similarity 0.87)
• Eliciting Reasoning in Language Models with Cognitive Tools (NeurIPS 2025 · similarity 0.87)
• RAGEN-2: Reasoning Collapse in Agentic RL (ICML 2026 · similarity 0.87)
• Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation (ICML 2025 · similarity 0.87)