CoChat
Sign Up
PreprintCited by 124Syntax, Semantics, Linguistic VariationPhilosophy and Theoretical ScienceCybernetics and Technology in Society

Faith and Fate: Limits of Transformers on Compositionality

Open access
Dziri, Nouha, Lu, Ximing, Sclar, Melanie, Li, Xiang Lorraine, Jiang, Liwei, Lin, Bill Yuchen, West, Peter, Bhagavatula, Chandra +8 more·2023·arXiv
DOI 10.48550/arxiv.2305.18654arXiv 2305.18654
Open this paper in CoChat — free accountOpen PDF

Abstract

Transformer large language models (LLMs) have sparked admiration for their exceptional performance on tasks that demand intricate multi-step reasoning. Yet, these models simultaneously show failures on surprisingly trivial problems. This begs the question: Are these errors incidental, or do they signal more substantial limitations? In an attempt to demystify transformer LLMs, we investigate the limits of these models across three representative compositional tasks -- multi-digit multiplication, logic grid puzzles, and a classic dynamic programming problem. These tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer. We formulate compositional tasks as computation graphs to systematically quantify the level of complexity, and break down reasoning steps into intermediate sub-procedures. Our empirical findings suggest that transformer LLMs solve compositional tasks by reducing multi-step compositional reasoning into linearized subgraph matching, without necessarily developing systematic problem-solving skills. To round off our empirical study, we provide theoretical arguments on abstract multi-step reasoning problems that highlight how autoregressive generations' performance can rapidly decay with\,increased\,task\,complexity.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2305.18654

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • AutoMix employs a non-LLM setup for routing and avoids escalating issues such as hallucination and reasoning errors.

    “Addressing the notable challenges of self-correction in large language models [Madaan et al., 2023, Huang et al., 2023b], AutoMix employs a non-LLM setup for routing and avoids escalating issues such as hallucination and reasoning errors [Dziri et al., 2023].”

    From AutoMix: Automatically Mixing Language Models (2023) · cites this paper as Dziri et al., 2023

    Section 4 (p. 8) says reasoning errors in autoregressive transformer LLMs rapidly escalate as compositional problems grow. The paper does not establish that AutoMix’s non-LLM routing prevents those errors, nor does the cited passage address hallucination. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

No citation lists for this paper

No DOI on record — the citation lists can’t be looked up.

Cited by 124

Research works printed but not linked: 26

  1. [3][3] Cem Anil, Yuhuai Wu, Anders Johan Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Venkatesh Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. In Advances in Neural Information Processing Systems , volume 35, pages 38546-38556. Curran Associates, Inc., 2022. -
  2. [5][5] Yoshua Bengio, Réjean Ducharme, and Pascal Vincent. A neural probabilistic language model. In Advances in Neural Information Processing Systems , volume 13. MIT Press, 2000. -
  3. [6][6] D. Bertsekas. Abstract Dynamic Programming: 3rd Edition . Athena scientific optimization and computation series. Athena Scientific., 2022. -
  4. [7][7] Gregor Betz, Christian Voigt, and Kyle Richardson. Critical thinking for language models. In Proceedings of the 14th International Conference on Computational Semantics (IWCS) , pages 63-75, 2021. -
  5. [11][11] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D. Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems , volume 33, pages 1877-1901, 2020. -
  6. [14][14] David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. Proceedings of the 40th International Conference on Machine Learning , 202:55445562, 2023. -
  7. [20][20] Antonia Creswell, Murray Shanahan, and Irina Higgins. Selection-inference: Exploiting large language models for interpretable logical reasoning. In International Conference on Learning Representations , 2023. -
  8. [30][30] Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics , 8:156-171, 2020. -
  9. [31][31] James Douglas Hamilton. Time series analysis . Princeton university press, 1994. -
  10. [32][32] Chadi Helwe, Chloé Clavel, and Fabian M. Suchanek. Reasoning with transformer-based models: Deep learning, but shallow reasoning. In Danqi Chen, Jonathan Berant, Andrew McCallum, and Sameer Singh, editors, 3rd Conference on Automated Knowledge Base Construction, AKBC 2021, Virtual, October 4-8, 2021 , 2021. -
  11. [34][34] James Hiebert. Conceptual and procedural knowledge: The case of mathematics . Routledge, 2013. -
  12. [35][35] Albert Qiaochu Jiang, Sean Welleck, Jin Peng Zhou, Timothee Lacroix, Jiacheng Liu, Wenda Li, Mateja Jamnik, Guillaume Lample, and Yuhuai Wu. Draft, sketch, and prove: Guiding formal theorem provers with informal proofs. In The Eleventh International Conference on Learning Representations , 2023. -
  13. [39][39] Jon Kleinberg and Eva Tardos. Algorithm Design . Addison-Wesley Longman Publishing Co., Inc., USA, 2005. -
  14. [45][45] Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Representations , 2022. -
  15. [46][46] Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In International Conference on Learning Representations , 2023. -
  16. [52][52] William Merrill, Nikolaos Tsilivis, and Aman Shukla. A tale of two circuits: Grokking as competition of sparse and dense subnetworks. In ICLR 2023 Workshop on Mathematical and Empirical Understanding of Foundation Models , 2023. -
  17. [60][60] Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations , 2022. -
  18. [61][61] Patrick Prosser. Hybrid algorithms for the constraint satisfaction problem. Computational intelligence , 9(3):268-299, 1993. -
  19. [66][66] Abulhair Saparov and He He. Language models are greedy reasoners: A systematic formal analysis of chain-of-thought. In International Conference on Learning Representations , 2023. -
  20. [67][67] Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang, Uzi Vishkin, Micah Goldblum, and Tom Goldstein. Can you learn an algorithm? generalizing from easy to hard problems with recurrent networks. In Advances in Neural Information Processing Systems , volume 34, pages 6695-6706. Curran Associates, Inc., 2021. -
  21. [68][68] Herbert A. Simon. The architecture of complexity. Proceedings of the American Philosophical Society , 106(6):467-482, 1962. -
  22. [71][71] Keith Stenning and Michiel Van Lambalgen. Human reasoning and cognitive science . MIT Press, 2012. -
  23. [76][76] Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Large language models still can't plan (a benchmark for LLMs on planning and reasoning about change). In NeurIPS 2022 Foundation Models for Decision Making Workshop , 2022. -
  24. [78][78] Petar Veliˇ ckovi´ c and Charles Blundell. Neural algorithmic reasoning. Patterns , 2(7):100273, 2021. -
  25. [79][79] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. Emergent abilities of large language models. Transactions on Machine Learning Research , 2022. Survey Certification. -
  26. [82][82] Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning to self-correct. In International Conference on Learning Representations , 2023. -

Authors
Dziri, N., Lu, X., Sclar, M., Li, X. L., Jiang, L., Lin, B. Y., West, P., Bhagavatula, C., Bras, R. L., Hwang, J. D., Sanyal, S., Welleck, S., Ren, X., Ettinger, A., Harchaoui, Z., & Choi, Y.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2023
Pages
70293-70332
ISSN
1049-5258 (ISSN-L)
DOI
10.48550/arxiv.2305.18654
arXiv
2305.18654
OpenAlex
W7133191918
Semantic Scholar
7d97c17a75beb89f938eaac1d3ca60ac2245fb2e
Cited by
124
References
0
Citations by year
2026: 39 · 2025: 28 · 2024: 35 · 2023: 22
FWCI
370.60
Type
conference paper
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • neural information processing systems (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (2134012)
  • Allen Institute for Artificial Intelligence
  • Defense Advanced Research Projects Agency (N66001-19-2-4031, N66001-19)
  • Naval Information Warfare Center Pacific
Topics
  • Social Sciences › Arts and Humanities › Language and Linguistics › Syntax, Semantics, Linguistic Variation
  • Social Sciences › Psychology › Experimental and Cognitive Psychology › Philosophy and Theoretical Science
  • Social Sciences › Arts and Humanities › History and Philosophy of Science › Cybernetics and Technology in Society
Keywords
transformer models, compositional generalization, compositional reasoning, large language models

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review