Elamur Research⌕
☰
home / papers / 2026 / Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth

Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth

Paper · 2026 · Michelle Yuan, Weiyi Sun, Amir H. Rezaeian et al.

Summary

The survey asks why transformer models, despite strong results in language and vision, remain unreliable at exact symbolic work such as arithmetic, Boolean logic, parsing, and multi-step algorithmic composition. Instead of running new experiments, Yuan et al. (Oracle AI) gather theoretical results from three areas. Circuit complexity treats model capacity in terms of depth and parallelism. Approximation theory explains why smooth learned mappings struggle with discontinuous, rule-like targets. Communication complexity describes how self-attention limits information flow between tokens. The authors organize these results into a taxonomy of barriers and show how the three views support each other. One example is that fixed depth both limits sequential computation and makes it hard to approximate functions with many discontinuities. They argue that the weaknesses come from the architecture itself, not only from training data. Remedies such as chain-of-thought prompting or scratchpads help only partly. The work gives researchers a single, accessible account of these limits and points toward hybrid and more structurally expressive designs.

Key points

  • The taxonomy has three branches. Circuit complexity covers finite numerical precision, constant depth, and constant output length. Approximation theory covers piecewise-constant functions, multi-step problems, and unbounded worst-case errors. Communication complexity covers sequential relay, long-range comparison, and sequential augmentation.
  • The circuit-complexity background places transformers against the classes AC⁰ ⊂ TC⁰ ⊆ NC¹. Efficiency techniques such as Mixture-of-Experts, Sparse Attention, Flash Attention, and RoPE do not increase fixed computational depth.
  • The paper cites current benchmark results to show how far frontier models still fall short:
    • On the MathArena Apex leaderboard, the best model is Gemini 3 Pro at 23.44%.
    • On FrontierMath Tier-4, the best model is GPT 5.2 Pro at 29.2%.
  • Recommended research directions are:
    • neuro-symbolic models;
    • state-aware and memory-augmented architectures, including state space models;
    • boundary-aware learning, which the authors link to manifold learning.
  • Published at EACL 2026 (Volume 1: Long Papers, pp. 1966–1978). The authors note that the survey's scope is limited to these three frameworks and to discrete reasoning tasks.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,426 works

Cite

Cite as Michelle Yuan, Weiyi Sun, Amir H. Rezaeian, Jyotika Singh, Sandip Ghoshal, Yao-Ting Wang, Miguel Ballesteros and Yassine Benajiba. 2026. Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth. Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.eacl-long.87

@inproceedings{yuan2026barriers,
  title = {{Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth}},
  author = {Michelle Yuan, Weiyi Sun, Amir H. Rezaeian, Jyotika Singh, Sandip Ghoshal, Yao-Ting Wang, Miguel Ballesteros and Yassine Benajiba},
  booktitle = {Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.eacl-long.87},
  url = {https://doi.org/10.18653/v1/2026.eacl-long.87}
}

References

83 references, 16 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, and 1 others. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774.
  2. Miltiadis Allamanis and Pengcheng Yin. 2025. Disproving program equivalence with llms. Preprint, arXiv:2502.18473. — [arXiv:2502.18473](https://arxiv.org/abs/2502.18473) find
  3. Alireza Amiri, Xinting Huang, Mark Rofin, and Michael Hahn. 2025. Lower bounds for chain-of-thought reasoning in hard-attention transformers. arXiv preprint arXiv:2502.02393. — [arXiv:2502.02393](https://arxiv.org/abs/2502.02393) find
  4. Sanjeev Arora, Zhiyuan Li, and Abhishek Panigrahi. 2022. Understanding gradient descent on the edge of stability in deep learning. In International Conference on Machine Learning, pages 948–1024. PMLR. find
  5. Ali Baheri and Cecilia O Alm. 2025. Hierarchical neuro-symbolic decision transformer. arXiv preprint arXiv:2503.07148. — [arXiv:2503.07148](https://arxiv.org/abs/2503.07148) find
  6. Mislav Balunović, Jasper Dekoninck, Ivo Petrov, Nikola Jovanović, and Martin Vechev. 2025. Matharena: Evaluating llms on uncontaminated math competitions. Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmark. find
  7. Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. On the ability and limitations of transformers to recognize formal languages. arXiv preprint arXiv:2009.11264.
  8. Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. 2024. Separations in the representational capabilities of transformers and recurrent architectures. In The Thirty-eighth Annual Conference on Neural Information Processing Systems. find
  9. Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri Chatterji, Annie Chen, Kathleen Creel, Jared Quincy Davis, Dora De… — On the Opportunities and Risks of Foundation Models
  10. Sébastien Bubeck and Mark Sellke. 2021. A universal law of robustness via isoperimetry. Advances in Neural Information Processing Systems, 34:28811– 28822. find
  11. Ziyang Cai, Nayoung Lee, Avi Schwarzschild, Samet Oymak, and Dimitris Papailiopoulos. 2025. Extrapolation by association: Length generalization transfer in transformers. arXiv preprint arXiv:2506.09251. — [arXiv:2506.09251](https://arxiv.org/abs/2506.09251) find
  12. Diego Calanzone, Stefano Teso, and Antonio Vergari. 2025. Logically consistent language models via neuro-symbolic integration. In The Thirteenth International Conference on Learning Representations. find
  13. Bo Chen, Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, and Jiahao Zhang. 2025. find
  14. Circuit complexity bounds for rope-based transformer architecture. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 11091–11108. find
  15. Lijie Chen, Binghui Peng, and Hongxun Wu. 2024. Theoretical limitations of multi-layer transformer. arXiv preprint arXiv:2412.02975. — [arXiv:2412.02975](https://arxiv.org/abs/2412.02975) find
  16. Wenlong Chen and Yingzhen Li. 2023. Calibrating transformers via sparse gaussian processes. In The Eleventh International Conference on Learning Representations. find
  17. Zixiang Chen, Junkai Zhang, Yiwen Kou, Xiangning Chen, Cho-Jui Hsieh, and Quanquan Gu. 2023. Why does sharpness-aware minimization generalize better than sgd? Advances in neural information processing systems, 36:72325–72376. find
  18. David Chiang and Peter Cholak. 2022. Overcoming a theoretical limitation of self-attention. arXiv preprint arXiv:2202.12172. find
  19. Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. 2022. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances in neural information processing systems, 35:16344–16359. find
  20. Shrey Desai and Greg Durrett. 2020. Calibration of pre-trained transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 295–302. find
  21. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies,…
  22. Ronald A DeVore. 1998. Nonlinear approximation. Acta numerica, 7:51–150. find
  23. Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, G Heigold, S Gelly, and 1 others. 2020. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning…
  24. Feyza Duman, Pruthuvi Wijewardena, and Chinmay Hegde. 2023. On the computational complexity of self-attention. Proceedings of Machine Learning Research. find
  25. Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, and 1 others. 2023. Faith and Fate: Limits of Transformers on Compositionality. Advances in Neural Information Processing Systems, 36:70293–70332.
  26. Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. 2023. Towards revealing the mystery behind chain of thought: a theoretical perspective. Advances in Neural Information Processing Systems, 36:70757–70798. find
  27. Yu Feng, Ben Zhou, Weidong Lin, and Dan Roth. 2025. Bird: A trustworthy bayesian inference framework for large language models. In The Thirteenth International Conference on Learning Representations. find
  28. Chenxing Gao, Hang Zhou, Junqing Yu, YuTeng Ye, Jiale Cai, Junle Wang, and Wei Yang. 2024a. Attacking transformers with feature diversity adversarial perturbation. In Proceedings of the AAAI Conference on Artificial Intelligence. find
  29. Muhan Gao, TaiMing Lu, Kuai Yu, Adam Byerly, and Daniel Khashabi. 2024b. Insights into llm long-context failures: when transformers know but don’t tell. In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 7611–7625. find
  30. Elliot Glazer, Ege Erdil, Tamay Besiroglu, Diego Chicharro, Evan Chen, Alex Gunning, Caroline Falkman Olsson, Jean-Stanislas Denain, Anson Ho, Emily de Oliveira Santos, and 1 others. 2024. FrontierMath: A benchmark for evaluating advanced mathematical reasoning in AI. arXiv preprint arXiv:2411.04872… find
  31. Albert Gu and Tri Dao. 2024. Mamba: Linear-time sequence modeling with selective state spaces. In First conference on language modeling. find
  32. Chuan Guo, Alexandre Sablayrolles, Hervé Jégou, and Douwe Kiela. 2021. Gradient-based adversarial attacks against text transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 5747–5757.
  33. Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, and 1 others. 2025. Deepseekr1 incentivizes reasoning in llms through reinforcement learning. Nature, 645(8081):633–638. find
  34. Michael Hahn and Mark Rofin. 2024. Why are sensitive functions hard for transformers? In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 14973–15008. find
  35. Yiding Hao, Dana Angluin, and Robert Frank. 2022. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10:800–810.
  36. Kostas Hatalis, Despina Christou, Joshua Myers, Steven Jones, Keith Lambert, Adam Amos-Binks, Zohreh Dannenhauer, and Dustin Dannenhauer. 2023. Memory matters: The need to improve long-term memory in llm-agents. In Proceedings of the AAAI Symposium Series. find
  37. Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, and 1 others. 2022. Training compute-optimal large language models. arXiv preprint arXiv:2203.15556.
  38. Kijae Hong and Yeonsu Park. 2025. Large language models for semantic join: A comprehensive survey. IEEE Access, 13:184478–184493. find
  39. Kurt Hornik, Maxwell Stinchcombe, and Halbert White. 1989. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359–366. find
  40. Yi Hu, Xiaojuan Tang, Haotong Yang, and Muhan Zhang. 2024. Case-based or rule-based: How do transformers do the math? In International Conference on Machine Learning, pages 19438–19474. PMLR. find
  41. Yuyang Hu, Shichun Liu, Yanwei Yue, Guibin Zhang, Boyang Liu, Fangyi Zhu, Jiahang Lin, Honglin Guo, Shihan Dou, Zhiheng Xi, and 1 others. 2025. Memory in the age of ai agents. arXiv preprint arXiv:2512.13564. — [arXiv:2512.13564](https://arxiv.org/abs/2512.13564) find
  42. Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, and Chinmay Hegde. 2023. On the computational complexity of self-attention. In International conference on algorithmic learning theory, pages 597–619. PMLR. find
  43. Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, and 1 others. 2023. Segment anything. In Proceedings of the IEEE/CVF international conference on computer vision, pages 4015–4026.
  44. Eyal Kushilevitz. 1997. Communication complexity. In Advances in Computers, volume 44, pages 331–360. Elsevier. find
  45. Nayoung Lee, Ziyang Cai, Avi Schwarzschild, Kangwook Lee, and Dimitris Papailiopoulos. 2025. Self-improving transformers overcome easy-to-hard and length generalization challenges. In Forty-second International Conference on Machine Learning. find
  46. Nayoung Lee, Kartik Sreenivasan, Jason D Lee, Kangwook Lee, and Dimitris Papailiopoulos. 2023. Teaching arithmetic to small transformers. arXiv preprint arXiv:2307.03381. find
  47. Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. 2024. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint arXiv:2402.12875, 1. find
  48. Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriano, Puneet K Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. 2023. Graph inductive biases in transformers without message passing. In International Conference on Machine Learning, pages 23321–23337. PMLR. find
  49. Xueqi Ma, Xingjun Ma, Chuang Liu, Sarah Monazam Erfani, and James Bailey. 2024. Exploring high-order message-passing in graph transformers. find
  50. William Merrill and Ashish Sabharwal. 2023a. The expressive power of transformers with chain of thought. arXiv preprint arXiv:2310.07923. find
  51. William Merrill and Ashish Sabharwal. 2023b. A logic for expressing log-precision transformers. Advances in neural information processing systems, 36:52453– 52463. find
  52. William Merrill and Ashish Sabharwal. 2023c. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531–545. find
  53. William Merrill, Ashish Sabharwal, and Noah A Smith. 2022. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843–856. find
  54. Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. 2024. GSM-symbolic: Understanding the limitations of mathematical reasoning in large language models. arXiv preprint arXiv:2410.05229.
  55. Rafael Müller, Simon Kornblith, and Geoffrey E Hinton. 2019. When does label smoothing help? Advances in neural information processing systems, 32. find
  56. Binghui Peng, Srini Narayanan, and Christos Papadimitriou. 2024. On limitations of the transformer architecture. In First Conference on Language Modeling. find
  57. Jorge Pérez, Pablo Barceló, and Javier Marinkovic. 2021. Attention is turing complete. Journal of Machine Learning Research, 22:1–35. find
  58. Stephen J. Ponzio, Jaikumar Radhakrishnan, and S. Venkatesh. 1999. The communication complexity of pointer chasing: applications of entropy and sampling. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC ’99, page 602–611, New York, NY, USA. Association for Computi… find
  59. Ruizhong Qiu, Zhe Xu, Wenxuan Bao, and Hanghang Tong. 2025. Ask, and it shall be given: On the turing completeness of prompting. In The Thirteenth International Conference on Learning Representations. find
  60. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21(140):1–67.
  61. Clayton Sanford, Daniel Hsu, and Matus Telgarsky. 2023. Representational strengths and limitations of transformers. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA. Curran Associates Inc. find
  62. Clayton Sanford, Daniel Hsu, and Matus Telgarsky. 2024. Transformers, parallel computation, and logarithmic depth. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org. find
  63. Erfan Shayegani, Md Abdullah Al Mamun, Yu Fu, Pedram Zaree, Yue Dong, and Nael Abu-Ghazaleh. 2023. Survey of vulnerabilities in large language models revealed by adversarial attacks. arXiv preprint arXiv:2310.10844.
  64. Jyotika Singh. 2023. Natural Language Processing in the Real World: Text Processing, Analytics, and Classification. Chapman and Hall/CRC. find
  65. Jyotika Singh, Weiyi Sun, Amit Agarwal, Viji Krishnamurthy, Yassine Benajiba, Sujith Ravi, and Dan Roth. 2025. Can LLMs narrate tabular data? an evaluation framework for natural language representations of text-to-SQL system outputs. In Proceedings of the 2025 Conference on Empirical Methods in Natu… find
  66. Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. 2024. What formal languages can transformers express? a survey. Transactions of the Association for Computational Linguistics, 12:543– 561. find
  67. Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. 2024. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 568:127063.
  68. Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan. 2020. Sparse sinkhorn attention. In International conference on machine learning, pages 9438–9447. PMLR. find
  69. Lewis Tunstall, Leandro von Werra, and Thomas Wolf. 2022. Natural Language Processing with Transformers: Building Language Applications with Hugging Face. O’Reilly Media, Incorporated. find
  70. Leslie G Valiant. 1984. A theory of the learnable. Communications of the ACM, 27(11):1134–1142. find
  71. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in neural information processing systems, 30.
  72. Heribert Vollmer. 1999. Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag, Berlin, Heidelberg. find
  73. Xilong Wang, Hao Fu, Jindong Wang, and Neil Zhenqiang Gong. 2025. StringLLM: Understanding the string processing capability of large language models. In The Thirteenth International Conference on Learning Representations. find
  74. Yiran Wu, Tianwei Yue, Shaokun Zhang, Chi Wang, and Qingyun Wu. 2023. Stateflow: Enhancing llm task-solving through state-driven workflows. In First Conference on Language Modeling.
  75. Zhaofeng Wu, Linlu Qiu, Alexis Ross, Ekin Akyürek, Boyuan Chen, Bailin Wang, Najoung Kim, Jacob Andreas, and Yoon Kim. 2024. Reasoning or reciting? exploring the capabilities and limitations of language models through counterfactual tasks. In Proceedings of the 2024 Conference of the North American… find
  76. Zhenda Xie, Yixuan Wei, Huanqi Cao, Chenggang Zhao, Chengqi Deng, Jiashi Li, Damai Dai, Huazuo Gao, Jiang Chang, Liang Zhao, and 1 others. 2025. mhc: Manifold-constrained hyper-connections. arXiv preprint arXiv:2512.24880. — [arXiv:2512.24880](https://arxiv.org/abs/2512.24880) find
  77. Kai Yang, Jan Ackermann, Zhenyu He, Guhao Feng, Bohang Zhang, Yunzhen Feng, Qiwei Ye, Di He, and Liwei Wang. 2024. Do efficient transformers really save computation? In International Conference on Machine Learning, pages 55928–55947. PMLR. find
  78. Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. 2021. Self-attention networks can process bounded hierarchical languages. arXiv preprint arXiv:2105.11115. find
  79. Fuheng Zhao, Jiayue Chen, Lawrence Lim, Ishtiyaque Ahmad, Divyakant Agrawal, and Amr El Abbadi. 2025. Llm-sql-solver: Can llms determine sql equivalence? Preprint, arXiv:2312.10321. — [arXiv:2312.10321](https://arxiv.org/abs/2312.10321) find
  80. Jun Zhao, Jingqi Tong, Yurong Mou, Ming Zhang, Qi Zhang, and Xuan-Jing Huang. 2024. Exploring the compositional deficiency of large language models in mathematical reasoning through trap problems. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 16361–… find
  81. Honglu Zhou, Asim Kadav, Farley Lai, Alexandru Niculescu-Mizil, Martin Renqiang Min, Mubbasir Kapadia, and Hans Peter Graf. 2021. Hopper: Multi-hop transformer for spatiotemporal reasoning. In International Conference on Learning Representations. find
  82. Yanqi Zhou, Tao Lei, Hanxiao Liu, Nan Du, Yanping Huang, Vincent Zhao, Andrew M Dai, Quoc V Le, James Laudon, and 1 others. 2022. Mixture-of-experts with expert choice routing. Advances in Neural Information Processing Systems, 35:7103–7114. find
  83. Nikola Zubic, Federico Soldà, Aurelio Sulser, and Davide Scaramuzza. 2025. Limits of deep learning: Sequence modeling through the lens of complexity theory. In The Thirteenth International Conference on Learning Representations. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/yuan-2026-barriers-discrete-reasoning-transformers-survey/