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

Computer Science > Artificial Intelligence [Submitted on 29 May 2026] The Deterministic Horizon: When Extended Reasoning Fails and Tool Delegation Becomes Necessary Dongxin Guo, Jikun Wu, Siu Ming Yiu Extended chain-of-thought reasoning can degrade performance on deterministic state-tracking tasks, not due to preference biases, but limits rooted in the information-theoretic capacity of decoder-only attention. We establish: (1) an Attention Bottleneck Theorem with a complementary achievability construction, bounding state-tracking capacity as O(H \cdot \log(L/H) \cdot \sqrt{d_h}); (2) a context-dependent error model yielding super-exponential accuracy decay; (3) the State-Space Jaccard metric distinguishing capability from preference failures; (4) a Deterministic Horizon d^* \in [19, 31] beyond which tool delegation becomes necessary. Across 12 models and 8 task domains (including SWE-Bench, WebArena, and SQL-Multi), tool-integrated reasoning consistently outperforms neural chain-of-thought; on the primary model suite it reaches 86-94% accuracy versus 24-42% for neural chain-of-thought. Fine-tuning on optimal-length traces yields <5% improvement, confirming an architectural ceiling, and high cross-model correlation (r = 0.81-0.91) indicates these failures are architectural rather than training-specific. Our results provide principled guidance for when pure neural reasoning should yield to hybrid approaches in agentic systems. Comments: Accepted at ICML 2026. 4 figures. 51 pages including appendices Subjects: Artificial Intelligence (cs.AI); Computation and Language (cs.CL); Machine Learning (cs.LG) ACM classes: I.2.7; I.2.6 Cite as: arXiv:2606.00376 [cs.AI]   (or arXiv:2606.00376v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2606.00376 Focus to learn more Submission history From: Dongxin Guo [view email] [v1] Fri, 29 May 2026 21:35:23 UTC (90 KB) Access Paper: HTML (experimental) view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-06 Change to browse by: cs cs.CL cs.LG References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)