mlsanityData to 7 Oct 2026

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

arXiv 2606.00376 ↗First posted 29 May 2026cs.AI cs.CL cs.LGcited by 1

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

Abstract (arXiv)

Extended chain-of-thought reasoning can degrade performance on deterministic state-tracking tasks, not solely because of preference biases but, on the evidence we present, because of information-theoretic limits in the capacity of decoder-only attention. We present: (1) an Attention Bottleneck analysis providing evidence that total state-tracking capacity in bits is bounded in terms of head count, head dimension, and context length under stated modeling assumptions, and that total capacity is not the binding constraint; (2) a context-dependent error model with a depth-dependent quadratic term in the error exponent; (3) the State-Space Jaccard metric measuring state drift; and (4) a Deterministic Horizon d^* ∈ [19, 31] (at α = 0.5) marking the depth at which unaided accuracy crosses 50%. Across twelve models and eight task domains (including SWE-Bench, WebArena, and SQL-Multi), tool-integrated reasoning reaches 76-94% accuracy versus 17-42% for neural chain-of-thought on PermutationProbe. Fine-tuning on optimal-length traces yields <3 percentage-point improvement, supporting an architectural ceiling.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 59 of its 77 references that are in the map. First posted on arXiv 29 May 2026.

Builds on

59 of 77 references.

Closest ancestors · 9

Same direction, newest first

  1. 2025When More is Less: Understanding Chain-of-Thought Length in LLMs11 Feb
  2. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers4 Feb
  3. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems20 Feb
  4. 2023Graph of Thoughts: Solving Elaborate Problems with Large Language Models18 Aug
  5. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective24 May
  6. 2022Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks22 Nov
  7. 2022Large Language Models are Zero-Shot Reasoners24 May
  8. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Models21 Mar
  9. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 50

  1. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,355
  2. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,146
  3. 2023Toolformer: Language Models Can Teach Themselves to Use Toolscited by 4,072
  4. 2023Lost in the Middle: How Language Models Use Long Contextscited by 3,383
  5. 2023SWE-bench: Can Language Models Resolve Real-World GitHub Issues?cited by 3,193
  6. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
  7. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,115
  8. 2023WebArena: A Realistic Web Environment for Building Autonomous Agentscited by 1,908
  9. 2023Gorilla: Large Language Model Connected with Massive APIscited by 1,302
  10. 2018Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Taskcited by 1,120
  11. 2022Measuring and Narrowing the Compositionality Gap in Language Modelscited by 1,054
  12. 2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 946
38 more
  1. 2022In-context Learning and Induction Headscited by 930
  2. 2022STaR: Bootstrapping Reasoning With Reasoningcited by 895
  3. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  4. 2015Deep Learning and the Information Bottleneck Principlecited by 793
  5. 2017Opening the Black Box of Deep Neural Networks via Informationcited by 494
  6. 2025Stop Overthinking: A Survey on Efficient Reasoning for Large Language Modelscited by 456
  7. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  8. 2023Augmented Language Models: a Surveycited by 398
  9. 2023Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoningcited by 379
  10. 2023On the Planning Abilities of Large Language Models : A Critical Investigationcited by 308
  11. 2023Tool Learning with Foundation Modelscited by 302
  12. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  13. 2024Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Modelscited by 282
  14. 2019Measuring Compositional Generalization: A Comprehensive Method on Realistic Datacited by 280
  15. 2023ToRA: A Tool-Integrated Reasoning Agent for Mathematical Problem Solvingcited by 276
  16. 2020COGS: A Compositional Generalization Challenge Based on Semantic Interpretationcited by 260
  17. 2022Neural Networks and the Chomsky Hierarchycited by 214
  18. 2025Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusionscited by 208
  19. 2022TALM: Tool Augmented Language Modelscited by 197
  20. 2024The Illusion of State in State-Space Modelscited by 181
  21. 2023Birth of a Transformer: A Memory Viewpointcited by 154
  22. 2024Same Task, More Tokens: the Impact of Input Length on the Reasoning Performance of Large Language Modelscited by 150
  23. 2023Representational Strengths and Limitations of Transformerscited by 132
  24. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  25. 2023Chain of Code: Reasoning with a Language Model-Augmented Code Emulatorcited by 120
  26. 2025Between Underthinking and Overthinking: An Empirical Study of Reasoning Length and correctness in LLMscited by 115
  27. 2025DeepSeek-R1 Thoughtology: Let's think about LLM Reasoningcited by 91
  28. 2024Transformers need glasses! Information over-squashing in language taskscited by 87
  29. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  30. 2021Making Transformers Solve Compositional Taskscited by 72
  31. 2020The Information Bottleneck Problem and Its Applications in Machine Learningcited by 66
  32. 2024On Limitations of the Transformer Architecturecited by 63
  33. 2025Inference-Time Scaling for Complex Tasks: Where We Stand and What Lies Aheadcited by 43
  34. 2023The Impact of Depth on Compositional Generalization in Transformer Language Modelscited by 37
  35. 2024Attention Entropy is a Key Factor: An Analysis of Parallel Context Encoding with Full-attention-based Pre-trained Language Modelscited by 26
  36. 2025AgentMath: Empowering Mathematical Reasoning for Large Language Models via Tool-Augmented Agentcited by 17
  37. 2024Self-Attention Limits Working Memory Capacity of Transformer-Based Modelscited by 5
  38. 2025You Do Not Fully Utilize Transformer's Representation Capacitycited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026The Bitter Lesson of Tool Callingcited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2025Bounds of Chain-of-Thought Robustness: Reasoning Steps, Embed Norms, and Beyond
  2. 2026Thinking Traps in Long Chain-of-Thought: A Measurable Study and Trap-Aware Adaptive Restart
  3. 2026The Complexity Ceiling Benchmark: A Multi-Domain Evaluation of Sequential Reasoning Under Depth Scaling
  4. 2026When Chain-of-Thought Helps and When It Hurts: An Empirical Investigation of the Serial-Depth Bottleneck in LLM Reasoning
  5. 2026CRISP: Compressing Redundancy in Chain-of-Thought via Intrinsic Saliency Pruning
  6. 2026Stateful Reasoning via Insight Replay
  7. 2026When does Chain-of-Thought Help: A Markovian Perspective
  8. 2026An Asymptotic Theory of Chain-of-Thought in In-Context Learning