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

Michelle Yuan, Weiyi Sun, Amir H. Rezaeian, Jyotika Singh, Sandip Ghoshal, Yao-Ting Wang, Miguel Ballesteros, Yassine Benajiba

TL;DR

While Transformers excel at pattern matching and continuous interpolation, they face hard theoretical limits when it comes to exact discrete reasoning tasks like arithmetic and logic. This survey unifies three distinct theoretical frameworks—circuit complexity, approximation theory, and communication complexity—to explain how fixed depth, smoothness biases, and information bandwidth bottlenecks fundamentally constrain Transformer architectures.

What Problem Does This Paper Address?

Large Language Models (LLMs) powered by Transformer architectures have achieved state-of-the-art performance across language, vision, and perception tasks. However, they consistently hit a wall when faced with reliable discrete reasoning, such as solving multi-digit arithmetic, evaluating boolean logic, or generalizing systematic rules to longer, unfamiliar examples.

Rather than focusing on incremental empirical fixes, this paper addresses the foundational why behind these failures. The authors synthesize recent theoretical literature to clarify the structural and computational barriers that prevent Transformers from executing exact, rule-based symbolic algorithms.

Methods

As a comprehensive survey, the paper does not introduce a new empirical method or algorithm. Instead, it provides a systematic synthesis of recent theoretical computer science literature, organizing the barriers to discrete reasoning into a cohesive taxonomy based on three established theoretical lenses:

  1. Circuit Complexity: Analyzes model capacity by mapping finite-precision, fixed-depth Transformers to Boolean circuit classes (such as $AC^0$ and $TC^0$), framing limitations around sequential depth and parallelism.
  2. Approximation Theory: Examines the inherent difficulty of using smooth, continuous neural networks to represent the sharp, discontinuous, piecewise-constant functions that characterize symbolic logic.
  3. Communication Complexity: Evaluates self-attention layers as synchronous rounds of parallel message-passing, exposing bottlenecks in information bandwidth (hidden dimensions) and multi-hop token coordination.
Figure 1: Taxonomy of barriers to discrete reasoning in transformers, organized by theoretical lens: circuit complexity, approximation theory, and communication complexity.

Datasets

Because this is a theoretical survey, the authors do not train models or introduce new datasets. However, they ground their analysis by referencing the performance of frontier models on challenging, uncontaminated discrete reasoning benchmarks, including:

  • MathArena Apex: A leaderboard featuring complex combinatorics problems (e.g., "The Zigzagging Chessboard").
  • FrontierMath Tier-4: A benchmark designed to test advanced mathematical reasoning.

Key Insights and Ideas

  • The Depth-Communication Link: A Transformer's physical depth (number of layers) directly dictates both its computational circuit depth and its communication rounds. A fixed-depth model can only perform a fixed number of sequential reasoning steps or "hops" of message passing in a single forward pass.
  • The Smoothness Bias Trap: Transformers are fundamentally smooth interpolators. However, discrete tasks are often piecewise-constant (e.g., the carry-over operation in addition, which jumps sharply at a threshold of 10). Forcing a smooth network to fit these sharp boundaries creates "traps" or "holes," leading to catastrophic failures on decision boundaries.
  • Exponential Error Compounding: In multi-step problems, errors compound exponentially ($L^k\epsilon$) with the number of sequential steps ($k$). To maintain precision, a fixed-depth network would require its parameter norms to grow unrealistically large.
  • Information Dilution over Long Ranges: Checking for relations or equality between distant substrings requires information to travel through intervening "filler" tokens. Because of fixed token bandwidth (hidden dimension), the signal becomes diluted or corrupted over long contexts, forcing the model to rely on lossy, hash-like approximations.
  • Chain-of-Thought (CoT) as a Depth Extender: Allowing a model to generate intermediate tokens (CoT or scratchpads) dynamically extends its computational depth. This shifts the architecture from a shallow circuit to one capable of achieving Turing-complete expressive capacity, though it remains bounded by the length of the scratchpad.

Key Results

The paper highlights landmark theoretical results from the literature that define the boundaries of Transformer expressivity:

  • Hard Bounds on Expressivity: Encoder-only transformers with hard attention correspond to $AC^0$ circuits, meaning they are mathematically incapable of recognizing basic properties like parity, majority, or nested formal languages ($DYCK-k$). Even with soft attention or advanced positional encodings like RoPE, they generally do not surpass uniform $TC^0$ bounds in a single forward pass.
  • Empirical Reflection of Theoretical Limits: The authors point to the low success rates of frontier models on advanced benchmarks as empirical proof of these boundaries. For instance, Gemini 3 Pro achieves only 23.44% accuracy on MathArena Apex, and GPT 5.2 Pro maxes out at 29.2% on FrontierMath Tier-4, underscoring that scaling size alone has not solved combinatorial reasoning.

Limitations and Future Work

The authors acknowledge that their survey is strictly bounded by the three chosen theoretical frameworks and focuses exclusively on discrete reasoning tasks, leaving out alternative perspectives or broader task domains.

To bypass these intrinsic architectural boundaries, they recommend that future research pivot away from raw scaling and toward:

  • Neuro-symbolic hybrids: Combining the pattern-recognition strengths of Transformers with explicit, programmable symbolic components (like logic circuits or formal parsers).
  • State-aware and memory-augmented architectures: Integrating external memory or state-space models (e.g., Mamba) to support unbounded sequential computation.
  • Boundary-aware learning: Developing training objectives and inductive biases that explicitly encourage models to represent sharp decision boundaries rather than smoothing over them.

Summary updated

Abstract

Transformers have become the foundational architecture for a broad spectrum of sequence modeling applications, underpinning state-of-the-art systems in natural language processing, vision, and beyond. However, their theoretical limitations in discrete reasoning tasks, such as arithmetic, logical inference, and algorithmic composition, remain a critical open problem. In this survey, we synthesize recent studies from three theoretical perspectives: circuit complexity, approximation theory, and communication complexity, to clarify the structural and computational barriers that transformers face when performing symbolic computations. By connecting these established theoretical frameworks, we provide an accessible and unified account of why current transformer architectures struggle to implement exact discrete algorithms, even as they excel at pattern matching and interpolation. We review key definitions, seminal results, and illustrative examples, highlighting challenges such as depth constraints, difficulty approximating discontinuities, and bottlenecks in inter-token communication. Finally, we discuss implications for model design and suggest promising directions for overcoming these foundational limitations.
BibTeX
@inproceedings{yuan2026barriers,
  author = {Michelle Yuan and Weiyi Sun and Amir H. Rezaeian and Jyotika Singh and Sandip Ghoshal and Yao-Ting Wang and Miguel Ballesteros and Yassine Benajiba},
  title = {{Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth}},
  booktitle = {EACL (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.eacl-long.87},
}
Figure