Research map / Large language models / Reasoning and chain of thought
Lost in Transmission: When and Why LLMs Fail to Reason Globally
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the bounded attention prefix oracle (BAPO) model of LLM communication bandwidth, proves which global reasoning problems are BAPO-hard or BAPO-easy, shows CoT makes constant-bandwidth BAPOs Turing-complete, and validates predictions with failures of GPT-4o, Claude, and Gemini.
Problem
LLMs fail on global reasoning tasks requiring integration of information across large parts of the input; the paper seeks a principled explanation based on limited information flow between residual streams via attention.
Approach
Model the transformer's cross-token communication as a bounded attention prefix oracle with two bandwidths (prefix bits and attended tokens), classify problems as BAPO-easy (constant bandwidth) or BAPO-hard, and show chain-of-thought reduces any decidable problem to constant-bandwidth steps.
Key results
- GPT-4o, Claude, and Gemini perform well on BAPO-easy problems but fail on BAPO-hard problems at length 200, with accuracy not above random guessing for large models.
- CoT modestly improves non-reasoning models on BAPO-hard problems at small n, but substantial drops remain under a 250-word limit.
- o3 and Gemini 2.5 Flash succeed on BAPO-hard problems when unconstrained, using often over 10k reasoning tokens.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BAPO-hard rather than BAPO-easy tasks | GPT-4o, Claude, and Gemini · BAPO reasoning tasks | accuracy | Hurt |
| Add chain-of-thought prompting with a soft limit of 250 words | Non-reasoning LLMs · BAPO-hard problems | accuracy | Helped |
| Use reasoning without imposing a limit on internal reasoning tokens | o3 and Gemini 2.5 Flash · BAPO-hard problems | accuracy | Helped |
| Increase model scale | LLMs across model scales · BAPO tasks | accuracy | Helped |
| Increase model scale | LLMs across model scales · BAPO-hard problems | accuracy | No clear effect |
| Ask whether the majority of hotel reviews are positive instead of finding a negative review | LLMs on hotel reviews from the Space dataset · Hotel review aggregation | accuracy | Hurt |
| Use variable tracking that requires reasoning about assignment chains | LLMs · Code variable tracking | accuracy | Hurt |
Surprising findings
- Even large frontier LLMs fail on Majority, a problem a single majority gate in TC0 would solve.
- Adding CoT makes constant-bandwidth BAPOs Turing-complete, so bandwidth can be reduced by reasoning steps, though with impractically many steps.
Limitations
- BAPO ignores tokenization and other LLM failure modes, so BAPO-easiness does not guarantee success.
- Many lower bounds are loose and the root cause of the effective bandwidth limit is unknown.
- Experiments use only single-token-output, non-reasoning prompts for most models and a 250-word CoT soft limit.
Experimental setup
Datasets: SPACE hotel reviews RULER variable tracking
Benchmarks: BAPO-easy and BAPO-hard synthetic problems (Index, Equality, Disjointness, Match2, Match3, Reachability, Majority, Uniqu real-world review aggregation variable tracking in code
Metrics: accuracy 95% t-test confidence interval
Baselines: o3 Gemini 2.5 Flash
Builds on: chain-of-thought prompting one-way communication complexity Turing-completeness of CoT transformers
Closest papers by meaning
- Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs (ICML 2026 · similarity 0.92)
- Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought (NeurIPS 2025 · similarity 0.89)
- A Implies B: Circuit Analysis in LLMs for Propositional Logical Reasoning (NeurIPS 2025 · similarity 0.89)
- GSM-$\infty$: How Do your LLMs Behave over Infinitely Increasing Reasoning Complexity and Context Length? (ICML 2025 · similarity 0.88)
- Let Me Think! A Long Chain of Thought Can Be Worth Exponentially Many Short Ones (NeurIPS 2025 · similarity 0.88)
- Finding the Minimal Parameter Budget for Implicit Reasoning: A Data Complexity Driven Scaling Law for Language Models (ICML 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.