Faith and Fate: Limits of Transformers on Compositionality
By Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jian, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang and 6 more. Neural Information Processing Systems, 2023
650 citations recorded by the source corpus.
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.
Subfields: Astronomy and Astrophysics, Sociology and Political Science
View Paper: https://www.semanticscholar.org/paper/7d97c17a75beb89f938eaac1d3ca60ac2245fb2e
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Astronomy and Astrophysics
In Sociology and Political Science
Citations in the corpus
- Many-shot Jailbreaking (2024, background): “Similarly, the diversity and amount of distribution shifts that might be induced under large context windows make it difficult to both train and evaluate models to act safely on out-of-distribution data (Anil et al., 2022; Dziri et al., 2023).”
- Dream 7B: Diffusion Large Language Models (2025, neutral): “This question becomes increasingly important as AR models exhibit inherent limitations in complex reasoning, long-term planning, and maintaining coherence across extended contexts (Bubeck et al., 2023; Dziri et al., 2023; Bachmann and Nagarajan, 2024; Ye et al., 2025a).”
- Large Language Models as Commonsense Knowledge for Large-Scale Task Planning (2023, background): “Even though LLMs are trained on internet-scale data, this strategy shows limits in generalization [10, 4], especially when encountering uncommon, complex tasks.”
- The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity (2025, neutral): “Earlier iterations of LLMs [9, 10, 11] exhibited poor performance on reasoning benchmarks [12, 13, 14, 6].”
- To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoning (2024, background): “…can provide human-readable explanations of how problems are solved (Joshi et al., 2023; Lanham et al., 2023), but most frequently it is invoked to improve an LLM’s ability to answer complex questions via intermediate computation (Madaan & Yazdanbakhsh, 2022; Wang et al., 2023a; Dziri et al., 2023).”
- Evaluation and mitigation of the limitations of large language models in clinical decision-making (2024, neutral): “The subset was evenly split between the four target pathologies with 20 patients randomly selected from each pathology and matching the makeup of the full dataset (Supplementary Section H).”