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

Dongxin Guo, Jikun Wu, Sm Yiu
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:38496-38533, 2026.

Abstract

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^* \in [19, 31]$ (at $\alpha = 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-guo26ab, title = {The Deterministic Horizon: When Extended Reasoning Fails and Tool Delegation Becomes Necessary}, author = {Guo, Dongxin and Wu, Jikun and Yiu, Sm}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {38496--38533}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/guo26ab/guo26ab.pdf}, url = {https://proceedings.mlr.press/v306/guo26ab.html}, abstract = {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^* \in [19, 31]$ (at $\alpha = 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.} }
Endnote
%0 Conference Paper %T The Deterministic Horizon: When Extended Reasoning Fails and Tool Delegation Becomes Necessary %A Dongxin Guo %A Jikun Wu %A Sm Yiu %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-guo26ab %I PMLR %P 38496--38533 %U https://proceedings.mlr.press/v306/guo26ab.html %V 306 %X 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^* \in [19, 31]$ (at $\alpha = 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.
APA
Guo, D., Wu, J. & Yiu, S.. (2026). The Deterministic Horizon: When Extended Reasoning Fails and Tool Delegation Becomes Necessary. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:38496-38533 Available from https://proceedings.mlr.press/v306/guo26ab.html.

Related Material