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

arXiv: https://arxiv.org/abs/2505.08140 · HTML: https://mlsanity.com/paper/2505.08140/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 37 of its 50 references that are in the map.
- First posted on arXiv 13 May 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 37)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Locating and Editing Factual Associations in GPT](https://mlsanity.com/paper/2202.05262/) (2022)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Let's Think Dot by Dot: Hidden Computation in Transformer Language Models](https://mlsanity.com/paper/2404.15758/) (2024)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [ZeroSCROLLS: A Zero-Shot Benchmark for Long Text Understanding](https://mlsanity.com/paper/2305.14196/) (2023)
- [Birth of a Transformer: A Memory Viewpoint](https://mlsanity.com/paper/2306.00802/) (2023)
- [Adaptive Attention Span in Transformers](https://mlsanity.com/paper/1905.07799/) (2019)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [AgentOccam: A Simple Yet Strong Baseline for LLM-Based Web Agents](https://mlsanity.com/paper/2410.13825/) (2024)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [Extractive Opinion Summarization in Quantized Transformer Spaces](https://mlsanity.com/paper/2012.04443/) (2020)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)
- [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024)
- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)

## Built on by (most cited first, 9 of 9)

- [The Price of a Second Thought: On the Evaluation of Reasoning Efficiency in Large Language Models](https://mlsanity.com/paper/2505.22017/) (2025)
- [Understanding the Challenges in Iterative Generative Optimization with LLMs](https://mlsanity.com/paper/2603.23994/) (2026)
- [The Context Gathering Decision Process: A POMDP Framework for Agentic Search](https://mlsanity.com/paper/2605.07042/) (2026)
- [Curriculum-Guided Layer Scaling for Language Model Pretraining](https://mlsanity.com/paper/2506.11389/) (2025)
- [Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs](https://mlsanity.com/paper/2602.02909/) (2026)
- [AI-rithmetic](https://mlsanity.com/paper/2602.10416/) (2026)
- [How Task Structure Limits Multi-Agent Success: An Information-Theoretic Analysis](https://mlsanity.com/paper/2606.13733/) (2026)
- [Subagents vs Agent Skills: Executing Reusable Knowledge for Long-Horizon Agentic Tasks](https://mlsanity.com/paper/2609.09233/) (2026)
- [Scaling of Capability and Efficiency at Inference Time in Large Reasoning Models](https://mlsanity.com/paper/2609.27166/) (2026)

## Abstract (arXiv)

Despite their many successes, transformer-based large language models (LLMs) continue to struggle with tasks that require complex reasoning over large parts of their input. We argue that these failures arise due to capacity limits on the accurate flow of information within LLMs. To formalize this issue, we introduce the bounded attention prefix oracle (BAPO) model, a new computational framework that models bandwidth constraints on attention heads, the mechanism for internal communication in LLMs. We show that several important reasoning problems like graph reachability require high communication bandwidth for BAPOs to solve; we call these problems BAPO-hard. Our experiments corroborate our theoretical predictions: GPT-4o, Claude, and Gemini succeed on BAPO-easy tasks and fail even on relatively small BAPO-hard tasks. BAPOs also reveal another benefit of chain of thought (CoT): we prove that breaking down a task using CoT can turn any BAPO-hard problem into a BAPO-easy one. Our results offer principled explanations for key LLM failures and suggest directions for architectures and inference methods that mitigate bandwidth limits.