Faith and Fate: Limits of Transformers on Compositionality

2023/05/29 by Nouha Dziri, Ximing Lu, Dziri, Nouha +29 · 13 voices · 72 citations
Computer Science · Materials Science · #Artificial Intelligence (cs.AI) #Computation and Language (cs.CL) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning in Materials Science #Natural Language Processing Techniques #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2305.18654

openalex publication_date 2023/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Wrong and More Confident: A Field Experiment on Large Language Models Taking a Graduate Economics Exam
• Confidently Wrong: Exception Chain Collapse in Frontier LLM Rule Evaluation
• Cognitive Dark Matter: Measuring What AI Misses
• Causal Reasoning Favors Encoders: On The Limits of Decoder-Only Models
• Curriculum Guided Massive Multi Agent System Solving For Robust Long Horizon Tasks
• The Missing Layer of AGI: From Pattern Alchemy to Coordination Physics
• AsymPuzl: An Asymmetric Puzzle for multi-agent cooperation
• Nexus: Higher-Order Attention Mechanisms in Transformers
• When Do Symbolic Solvers Enhance Reasoning in Large Language Models?
• Closed-Loop Transformers: Autoregressive Modeling as Iterative Latent Equilibrium
• Orthographic Constraint Satisfaction and Human Difficulty Alignment in Large Language Models
• In-Context Compositional Learning via Sparse Coding Transformer
• Understanding the Staged Dynamics of Transformers in Learning Latent Structure
• Cognitive Foundations for Reasoning and Their Manifestation in LLMs
• Cognitive Maps in Language Models: A Mechanistic Analysis of Spatial Planning
• The 2025 Planning Performance of Frontier Large Language Models
• The Ouroboros of Benchmarking: Reasoning Evaluation in an Era of Saturation
• Next-Latent Prediction Transformers Learn Compact World Models
• DecompSR: A dataset for decomposed analyses of compositional multihop spatial reasoning
• Training LLMs Beyond Next Token Prediction -- Filling the Mutual Information Gap
• EsoLang-Bench: Evaluating Genuine Reasoning in Large Language Models via Esoteric Programming Languages
• The Architecture of Errors: From Universal Impossibility to Patch-Local LLM Reliability
• Transformers Can Learn Rules They've Never Seen: Proof of Computation Beyond Interpolation
• The Kinetics of Reasoning: How Chain-of-Thought Shapes Learning in Transformers?
• Out-of-distribution generalization via composition: A lens through induction heads in Transformers
• When No Paths Lead to Rome: Benchmarking Systematic Neural Relational Reasoning
• Can Language Models Compose Skills In-Context?
• Once Upon an Input: Reasoning via Per-Instance Program Synthesis
• Evaluating LLM Reasoning Beyond Correctness and CoT
• DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMs
• Orchestrating Human-AI Teams: The Manager Agent as a Unifying Research Challenge
• UniCode: A Framework for Generating High Quality Competitive Coding Problems
• Which Word Orders Facilitate Length Generalization in LMs? An Investigation with GCG-Based Artificial Languages
• Self-Verifying Reflection Helps Transformers with CoT Reasoning
• An Alternative Trajectory for Generative AI
• How Do Language Models Compose Functions?
• RegexPSPACE: A Benchmark for Evaluating LLM Reasoning on PSPACE-complete Regex Problems
• Composition-RL: Compose Your Verifiable Prompts for Reinforcement Learning of Large Language Models
• Generating Meaning: Active Inference and the Scope and Limits of Passive AI
• LexiCon: a Benchmark for Planning under Temporal Constraints in Natural Language
• Bridging Reasoning to Learning: Unmasking Illusions using Complexity Out of Distribution Generalization
• Boosting Process-Correct CoT Reasoning by Modeling Solvability of Multiple-Choice QA
• Bridging the Knowledge-Prediction Gap in LLMs on Multiple-Choice Questions
• Local Success Does Not Compose: Benchmarking Large Language Models for Compositional Formal Verification
• When Can AI Models Explain Learning? Validity Criteria for AI as Cognitive Models in Education
• A model of errors in transformers
• Review of Hallucination Understanding in Large Language and Vision Models
• Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error
• From Found to Designed: Concepts as a Design Axis for Large Language Models
• SkillSmith: Learning to Compose Parametric Skills and Textual Knowledge
• Generating meaning: active inference and the scope and limits of passive AI
• Generative AI for Economic Research: Use Cases and Implications for Economists
• Non-Parametric Structural Priors for Geometry Theorem Prediction
• Understanding Subword Compositionality of Large Language Models
• Variation in Verification: Understanding Verification Dynamics in Large Language Models
• PiERN: Token-Level Routing for Integrating High-Precision Computation and Reasoning
• Large Language Models Imitate Logical Reasoning, but at what Cost?
• Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling
• COGITAO: A Visual Reasoning Framework To Study Compositionality & Generalization
• When LLM Meets Time Series: Can LLMs Perform Multi-Step Time Series Reasoning and Inference
• Transforming Agency. On the mode of existence of Large Language Models
• Provable Benefits of In-Tool Learning for Large Language Models
• Dream 7B: Diffusion Large Language Models
• TransLLM: A Unified Multi-Task Foundation Framework for Urban Transportation via Learnable Prompting
• Reinforced Context Order Recovery for Adaptive Reasoning and Planning
• Beyond Ethical Alignment: Evaluating LLMs as Artificial Moral Assistants
• Is GPT-OSS Good? A Comprehensive Evaluation of OpenAI's Latest Open Source Models
• The Missing Reward: Active Inference in the Era of Experience
• Topos Theory for Generative AI and LLMs
• Diagnosing Memorization in Chain-of-Thought Reasoning, One Token at a Time
• CompoST: A Benchmark for Analyzing the Ability of LLMs To Compositionally Interpret Questions in a QALD Setting
• Towards Consistent Long-Term Pose Generation

Discussions

• I'd distinguish "spurious correlation" shortcuts from "next-token shortcuts" . The former is independent of next-token training: in an "x+y=z" task depending on how you distribute your x and y, some [bsky, 4 points, 1 comments]
• Faith and Fate: Limits of Transformers on Compositionality [hn, 3 points, 1 comments]
• Here's my quick review and thoughts of Dziri et al.'s recent paper on the limits of auto-regressive language model capabilities. arxiv.org/abs/2305.18654 [bsky, 2 points, 8 comments]
• Faith and Fate - Limits of Transformers on Compositionality [lemmy, 2 points, 0 comments]
• Faith and Fate: Limits of Transformers on Compositionality [hn, 1 points, 0 comments]
• Faith and Fate: Limits of Transformers on Compositionality [hn, 1 points, 0 comments]
• Faith and Fate arxiv.org/pdf/2305.18654 @nouhadziri.bsky.social presents experiments suggesting that LLMs do not learn the basic (generalizable) capability to compose partial solutions of composition [bsky, 1 points, 1 comments]
• AIs will inevitably fail and depart from the real plane as they are used for more and more complex tasks. arxiv.org/abs/2305.18654 [bsky, 1 points, 0 comments]
• Faith and Fate: Limits of Transformers on Compositionality [hn, 1 points, 0 comments]
• Perhaps they would consider having a look at this paper? arxiv.org/abs/2305.18654 [bsky, 0 points, 0 comments]
• That paper he cites in that slide is great arxiv.org/abs/2305.18654 [bsky, 0 points, 0 comments]
• Faith and Fate: Limits of Transformers on Compositionality [bsky, 0 points, 1 comments]
• どうもTransformerなどの自己回帰型のLLMでは多段階の抽象的な推論は難しい感じがする。前の算数計算の組み合わせ推論の研究 arxiv.org/abs/2305.18654 を見てもそういう気しかしない… [bsky, 0 points, 0 comments]

Related

• Limits of Transformer Language Models on Learning to Compose Algorithms
• Exploring the Compositional Deficiency of Large Language Models in Mathematical Reasoning
• Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalability
• Complexity Control Facilitates Reasoning-Based Compositional Generalization in Transformers
• Compositional Hardness of Code in Large Language Models -- A Probabilistic Perspective