Cited by 335Syntax, Semantics, Linguistic VariationPhilosophy and Theoretical ScienceCybernetics and Technology in Society

The DOI matches its Crossref record; 82 of the 82 references it cites were found in a registry or an index; none of the 41 sources its claims cite is checked for support yet.

Faith and Fate: Limits of Transformers on Compositionality

Open access

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.

Overview

AI snapshot

Written from the paper’s full text.

TL;DR

Transformer LLMs can achieve near-perfect in-domain accuracy on compositional tasks but fail sharply out-of-domain, often relying on linearized subgraph matching rather than systematic multi-step reasoning. The paper argues empirically and theoretically that error propagation makes autoregressive transformers increasingly unlikely to solve compositionally complex tasks as problem size grows.

Key findings

  • Off-the-shelf ChatGPT and GPT4 achieve only 55% and 59% accuracy on 3-digit by 3-digit multiplication, and zero-/few-shot performance declines to near zero as problem size or graph parallelism increases.
  • Fine-tuning GPT3 on task-specific question-answer or question-scratchpad data gives near-perfect in-domain performance but fails to generalize to out-of-domain deeper or wider computation graphs; grokking was not observed for multiplication after 420K question-answer steps or 30K scratchpad steps.
  • Models appear to reduce multi-step reasoning to linearized subgraph matching: full computation subgraphs appear more frequently in training for correctly predicted test examples, and 82.3% of final correct answers for 4-digit by 2-digit multiplications had at least one error in the computation graph.
  • Error analysis shows fully correct nodes decrease sharply with graph layer, propagation errors usually exceed local errors, and DP/puzzle tasks show high restoration errors; theoretical propositions show incorrect-prediction probability can converge exponentially to ≈1 as problem size increases under stated assumptions.

Methods

  • The paper formulates compositional tasks as computation graphs and measures complexity via reasoning depth, reasoning width, average parallelism, and relative information gain.
  • It studies three tasks—long-form multi-digit multiplication up to 5×5 digits, Einstein logic grid puzzles, and a dynamic-programming relaxation of maximum weighted independent set—evaluating GPT3, ChatGPT, GPT4, FlanT5, and LLaMA with zero-shot, few-shot, question-answer fine-tuning, and question-scratchpad fine-tuning; each task uses 500 test examples.
  • It complements experiments with theoretical analysis of error accumulation for independent and iterated applications of estimated functions.

Limitations

  • The paper states that scratchpad analysis can only establish correlation between model generation and preceding context because the authors lack access to model activations, and that alternative linearizations of reasoning may yield different performance.
  • The paper also states that compute budget constraints and limited access to the largest language models prevented pushing empirical limits further.
  • Evident from the text: fine-tuning is mainly on GPT3, grokking is tested only on multiplication, puzzle training uses a subset due to combinatorial explosion, and the theoretical results rely on assumptions such as independent errors, low collision, and c ≪ ϵ that may not hold generally.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.52202/075280-3081

Cites

82 of 82 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

65 Own interpretation · 45 Own result · 17 Sources not found · 8 No basis given · 4 Own method

Show all 90 claims

  • It may state two separate claims as one. 29
  • The quote only partly states this claim. 4
  • Probably not a substantial claim. 25
49 of 49
  • The paper relies on this without support.

    The three compositional tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer.

    “These tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer.”
  • The paper relies on this without support.

    Human problem-solving skills can be represented as a graph structure where vertices are partial solutions and edges are operators that modify those solutions.

    “Human problem-solving skills can be conceptualized as a graph structure, where each vertex represents a partial solution and the edges represent operators that can be applied to modify these solutions.”
  • The paper relies on this without support.

    Reasoning depth in a computation graph is a proxy for the maximum level of multi-hop reasoning required to solve the task.

    “In computation graphs, reasoning depth is a proxy for the maximum level of multi-hop reasoning required to solve the task.”
  • The paper relies on this without support.

    The three studied tasks are representative compositional tasks.

    “we study three straightforward and flexible representative compositional tasks: long-form multiplication, logic grid puzzles (i.e., Einstein's puzzle [61]), and a classic dynamic programming problem.”
  • The paper relies on this without support.

    As K and M increase, synthesizing different partial solutions that satisfy individual constraints becomes highly compositionally complex.

    “As K and M increase, synthesizing different partial solutions that satisfy individual constraints becomes highly compositionally complex.”
  • The paper relies on this without support.

    Algorithms designed to solve compositional tasks typically involve multiple independent applications of a function and/or iterated applications of the same function.

    “Algorithms designed to solve compositional tasks typically involve multiple independent applications of a function and/or iterated applications of the same function.”
  • The paper relies on this without support.

    A transformer executing such an algorithm acts as an estimator of these functions.

    “A transformer executing such an algorithm acts as an estimator of these functions.”
  • The authors state this as an assumption.

    In Proposition 4.1, h_n is a perfect estimator of h_n.

    “Assume that h n is a perfect estimator of h n and that h n has low collision, with c n being an upper bound of h n 's collision rate (c n < c ∀n, with c ≪ 1).”
  • The authors state this as an assumption.

    In Proposition 4.1, h_n has low collision, with c_n being an upper bound of h_n's collision rate (c_n < c for all n, with c << 1).

    “Assume that h n is a perfect estimator of h n and that h n has low collision, with c n being an upper bound of h n 's collision rate (c n < c ∀n, with c ≪ 1).”
  • The authors state this as an assumption.

    In Proposition 4.1, g's errors are independent.

    “If P(g ̸ = g) = ϵ > 0 where g's errors are independent”
  • The authors state this as an assumption.

    In Proposition 4.2, the probability of recovering from a mistake due to the randomness of applying the estimator on an incorrect input is at most c.

    “Assume that the probability of recovering from a mistake due to the randomness of applying the estimator on an incorrect input has probability at most c.”
  • The authors state this as an assumption.

    In Proposition 4.2's current form, there is a single valid reasoning for each input since g is a function.

    “In Prop.4.2's current form, we implicitly assume that there is a single valid reasoning for each input since g is a function.”
  • The authors state this as an assumption.

    When g has low collision, c << epsilon.

    “It is reasonable to assume c ≪ ϵ when g has low collision, since c represents the probability of the estimator g(y) arriving at the correct output g(x) by chance when given the wrong input y ̸ = x.”
  • The paper relies on this without support.

    The tasks evaluated are low collision settings.

    “They are also all low collision settings.”
  • The authors state this as an assumption.

    The theoretical proofs' assumptions hold for the abstract compositional tasks and autoregressive language models considered.

    “The proofs presented in §4 show that, under reasonable assumptions, the probability of incorrect predictions converges exponentially to ≈ 1 for abstract compositional tasks.”
  • The authors state this as an assumption.

    In Proposition D.1, P(h_n = h_n)=1.

    “Assume P(h n = h n ) = 1”
  • The authors state this as an assumption.

    In Proposition D.1, P(h_n(X)=h_n(Y) | X≠Y) < c_n.

    “P(h n (X) = h n (Y ) | X ̸ = Y ) < c n”
  • The authors state this as an assumption.

    In Proposition D.1, c_n ≤ β α^n for some α∈(0,1) and β>0.

    “if c n ≤ βα n for some some α ∈ (0, 1) and β > 0”
  • The authors state this as an assumption.

    In Lemma D.2, P(z(g(X))=1 | z(X)=0) ≤ c.

    “Assume P(z( g(X)) = 1 | z(X) = 0) ≤ c”
  • The authors state this as an assumption.

    In Lemma D.2, P(z(g(X))=0 | z(X)=1) = ε > 0 with c+ε<1.

    “P(z( g(X)) = 0 | z(X) = 1) = ϵ > 0 with c + ϵ < 1”
  • The authors state this as an assumption.

    In Proposition D.2, P(g(X)=g(Y) | X≠Y) ≤ c.

    “Assume P(g(X) = g(Y ) | X ̸ = Y ) ≤ c”
  • The authors state this as an assumption.

    In Proposition D.2, P(g≠g)=ε>0 with c+ε<1.

    “If P(g ̸ = g) = ϵ > 0 with c + ϵ < 1”
  • The authors state this as an assumption.

    The mathematical framework used is a simplified representation of how multi-step reasoning works.

    “The mathematical framework used is a simplified representation of how multi-step reasoning works”
  • The authors state this as an assumption.

    c ≪ ϵ when g has low collision.

    “It is reasonable to assume c ≪ ϵ when g has low collision, since c represents the probability of the estimator g(y) arriving at the correct output g(x) by chance when given the wrong input y ̸ = x.”
  • The authors state this as an assumption.

    Assuming approximately uniform errors, c ≈ ϵ/|Im(g)|, which implies c ≪ ϵ when g has low collision.

    “Assuming approximately uniform errors, c ≈ ϵ/|Im(g)|, which in turn implies c ≪ ϵ since g being low collision implies |Im(g)| is large.”
25 of 25

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?

Self-check

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

Each contradiction between two passages listed here was confirmed by an independent check.

4 of 4

Citations

Cites

  • Language Models are Few-Shot Learners

    Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020) · arXiv · doi:10.48550/arxiv.2005.14165 · Cited by 23,372 · cited 5×

    “5-turbo) [40], GPT3 (text-davinci-003) [8], FlanT5 [? ] and LLaMa [57].”
    BackgroundMethodInfluential
  • Scaling Laws for Neural Language Models

    Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., & Amodei, D. (2020) · arXiv · doi:10.48550/arxiv.2001.08361 · Cited by 9,550

  • Z3: An Efficient SMT Solver

    de Moura, L., & Bjørner, N. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78800-3_24 · Cited by 6,595 · cited 1×

    “Graph Construction Algorithm To solve the complex compositional reasoning process for a logical grid puzzle, we use existing puzzle solvers [21] to generate the computation graph.”
    Method
  • Time Series Analysis

    Feigelson, E. (2003) · Statistics for Environmental Science and Management · doi:10.1007/978-3-319-03762-2_13 · Cited by 6,344 · cited 2×

    “When f is an affine transformation, the process falls simultaneously between two perspectives: time series [26] and dynamic programming and control [5].”
    Background
  • LLaMA: Open and Efficient Foundation Language Models

    Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al. (2023) · arXiv · doi:10.48550/arxiv.2302.13971 · Cited by 4,602 · cited 3×

    “[57] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample.”
    Background
  • Chain-Of-Thought Prompting Elicits Reasoning in Large Language Models

    Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E., Le, Q. V., & Zhou, D. (2022) · Advances in Neural Information Processing Systems 35 · doi:10.52202/068431-1800 · Cited by 4,505 · cited 3×

    “[61] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou.”
    BackgroundMethod
  • The Architecture of Complexity

    Simon, H. A. (1991) · Springer eBooks · doi:10.1007/978-1-4899-0718-9_31 · Cited by 4,479 · cited 1×

    “Applying step-by-step reasoning is fundamental to human intelligence [51, 50].”
    Background
  • PaLM: Scaling Language Modeling with Pathways

    Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al. (2022) · arXiv · doi:10.48550/arxiv.2204.02311 · Cited by 2,590 · cited 1×

    “Reasoning abilities in transformer LLMs Recently, transformers [11, 58, 57, 17, 16, 63, 73, 74] have demonstrated impressive reasoning abilities across a wide range of tasks, even outperforming humans in certain cases [79, 28, 15, 85].”
    Background
  • Self-Refine: Iterative Refinement with Self-Feedback

    Madaan, A., Tandon, N., Gupta, P., Hallinan, S., Gao, L., Wiegreffe, S., Alon, U., Dziri, N., Prabhumoye, S., Yang, Y., et al. (2023) · arXiv · doi:10.48550/arxiv.2303.17651 · Cited by 2,314 · cited 2×

    “[36] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Sean Welleck, Bodhisattwa Prasad Majumder, Shashank Gupta, Amir Yazdanbakhsh, and Peter Clark.”
    BackgroundMethodSelf-citation
  • Shortcut learning in deep neural networks

    Geirhos, R., Jacobsen, J.-H., Michaelis, C., Zemel, R., Brendel, W., Bethge, M., & Wichmann, F. A. (2020) · Nature Machine Intelligence · doi:10.1038/s42256-020-00257-z · Cited by 2,224 · cited 2×

    “[25] Robert Geirhos, Jörn-Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann.”
    Background

Show all 82 references

Research works printed but not linked: 6

  1. Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length general- ization in large language models. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 38546-38556.
  2. Arpit Bansal, Avi Schwarzschild, Eitan Borgnia, Zeyad Emam, Furong Huang, Micah Goldblum, and Tom Goldstein. End-to-end algorithm synthesis with recurrent networks: Extrapolation without overthinking. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 20232-20242.
  3. 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.
  4. D. Bertsekas. Abstract Dynamic Programming: 3rd Edition. Athena scientific optimization and computation series. Athena Scientific., 2022.
  5. Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Trans- formers learn shortcuts to automata. In International Conference on Learning Representations, 2023.
  6. 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.

Cited by

Sorted by citations

Items 101–141 of 141

Metadata

Authors
Dziri, N., Lu, X., Sclar, M., Li, X. (., Jiang, L., Lin, B. Y., Welleck, S., West, P., Bhagavatula, C., Bras, R. L., Hwang, J., Sanyal, S., Ren, X., Ettinger, A., Harchaoui, Z., & Choi, Y.
Venue
Advances in Neural Information Processing Systems 36
Published
2023
Pages
70293-70332
ISSN
1049-5258 (ISSN-L)
OpenAlex
W7133191918
Cited by
335
References
82
Citations by year
2026: 106 · 2025: 77 · 2024: 92 · 2023: 60
FWCI
610.22
Type
conference paper
Language
en
Open access
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 › Arts and Humanities › Philosophy › 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.

A language model drew the claims from the paper on 2026-10-23, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-10-23 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

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