Lost in Transmission: When and Why LLMs Fail to Reason Globally

Tobias Schnabel, Kiran Tomlinson, Adith Swaminathan, Jennifer Neville

Abstract

While Large Language Models (LLMs) demonstrate remarkable capabilities in local pattern matching and short-context reasoning, they frequently stumble on "global" tasks—problems requiring the integration of information across an entire input. This paper investigates this phenomenon through the Bounded Attention Prefix Oracle (BAPO) framework. We demonstrate that these failures are not necessarily due to a lack of parameters or general intelligence, but rather a fundamental communication bottleneck within the Transformer architecture. By formalizing the "effective bandwidth" of internal attention mechanisms, we show why certain tasks like graph reachability are inherently difficult for standard LLMs and how Chain-of-Thought (CoT) serves as a critical architectural workaround to bypass these limits.

Introduction

State-of-the-art LLMs often exhibit puzzling failures on seemingly simple tasks, such as tracking a variable through a long code block or determining if two nodes in a large graph are connected. Traditional analysis focuses on the model's expressivity—what a Transformer can compute in theory. However, this often fails to explain why models with billions of parameters fail in practice as context length grows.

We propose the Effective Bandwidth Hypothesis: the primary constraint on global reasoning is the limited capacity for information to be transmitted from early tokens (the prefix) to the final output token (the suffix). In a standard Transformer, information must pass through a narrow "pipe" of attention heads and residual streams. When the information required to solve a problem exceeds this bandwidth, the model's performance collapses.

The BAPO Framework

To formalize this bottleneck, we introduce the Bounded Attention Prefix Oracle (BAPO). This model splits an input into a prefix and a suffix, simulating the sequential processing of a Transformer:

  1. Prefix Oracle: Represents the pre-processing in early layers, limited by $a$ bits of internal state.
  2. Attention Function: Represents the attention mechanism, restricted to retrieving $b$ tokens from the prefix.
  3. Suffix Oracle: The final computation stage that produces the output.

Under this framework, we categorize tasks into two types:

  • BAPO-Easy: Tasks that can be solved with constant bandwidth as the input length $n$ grows. An example is the INDEX task (finding a specific "needle" in a haystack).
  • BAPO-Hard: Tasks where the required bandwidth must scale with the input size $n$. Examples include REACHABILITY (pathfinding in a graph) and MAJORITY (determining if most bits in a sequence are 1s).

Theoretical and Empirical Results

Our theoretical proofs demonstrate that while INDEX is BAPO-easy, REACHABILITY and MAJORITY are fundamentally BAPO-hard. This suggests that as the input size increases, a fixed-size Transformer will eventually run out of the bandwidth necessary to transmit the required global state to the final layer.

Empirical Confirmation

We evaluated leading models, including GPT-4o, Claude 3.5 Sonnet, and Gemini 1.5 Pro, across synthetic and real-world proxy datasets. The results strongly support the BAPO framework:

  • Consistency on Easy Tasks: Models maintained near-perfect accuracy on BAPO-easy tasks regardless of input length.
  • Collapse on Hard Tasks: Accuracy on BAPO-hard tasks, such as REACHABILITY, plummeted toward random chance as the input length $n$ approached 200 tokens.
  • Real-World Impact: This degradation was mirrored in practical scenarios like Variable Tracking (a programming task from the RULER benchmark), confirming that BAPO-hardness is a reliable predictor of failure in coding and data aggregation.

The Role of Chain-of-Thought (CoT)

One of the most significant insights of this research is the theoretical explanation for the success of Chain-of-Thought (CoT). We prove that adding CoT makes BAPO models Turing-complete, even with constant bandwidth.

CoT acts as a serializer. Instead of attempting to transmit a massive amount of information across a single prefix-suffix split, CoT allows the model to "unroll" a high-bandwidth problem into a sequence of low-bandwidth steps. By writing intermediate results back into the context, the model effectively bypasses its own internal communication limits. This explains why "reasoning" models like OpenAI’s o3 or Gemini 2.5, which utilize thousands of internal CoT tokens, maintain near 100% accuracy on BAPO-hard tasks where standard LLMs fail.

Discussion and Limitations

While the BAPO framework provides a powerful lens for understanding LLM failures, it is a theoretical abstraction. It does not currently account for the nuances of multi-layer interactions, tokenization errors, or "noisy" communication within the residual stream. Furthermore, while we have established lower bounds for bandwidth, the exact "tight" bounds for many reasoning tasks remain an area for future study.

Conclusion

The bottleneck in LLM reasoning is often a matter of communication, not just computation. As we move toward longer context windows and more complex reasoning tasks, simply increasing parameter counts may not be enough. Future architectural improvements should focus on increasing "effective bandwidth" or developing training methods that encourage more bandwidth-efficient reasoning chains. Alternatively, offloading high-bandwidth requirements to external tools remains a viable path for scaling global reasoning capabilities.

Summary updated

BibTeX
@inproceedings{schnabel2025lost,
  author = {Tobias Schnabel and Kiran Tomlinson and Adith Swaminathan and Jennifer Neville},
  title = {{Lost in Transmission: When and Why LLMs Fail to Reason Globally}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=MaJ3ASZ0NI},
}
Figure