# A Fano-Style Accuracy Upper Bound for LLM Single-Pass Reasoning in Multi-Hop QA

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 21 of its 32 references that are in the map.
- First posted on arXiv 25 Sep 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 21 of 21)

- [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)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [ChatDev: Communicative Agents for Software Development](https://mlsanity.com/paper/2307.07924/) (2023)
- [MuSiQue: Multihop Questions via Single-hop Question Composition](https://mlsanity.com/paper/2108.00573/) (2021)
- [Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models](https://mlsanity.com/paper/2305.04091/) (2023)
- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [An LLM Compiler for Parallel Function Calling](https://mlsanity.com/paper/2312.04511/) (2023)
- [Assisting in Writing Wikipedia-like Articles From Scratch with Large Language Models](https://mlsanity.com/paper/2402.14207/) (2024)
- [GLoRe: When, Where, and How to Improve LLM Reasoning via Global and Local Refinements](https://mlsanity.com/paper/2402.10963/) (2024)
- [Multi-hop Question Answering](https://mlsanity.com/paper/2204.09140/) (2022)
- [Did You Read the Instructions? Rethinking the Effectiveness of Task Definitions in Instruction Learning](https://mlsanity.com/paper/2306.01150/) (2023)
- [FIRE: Fact-checking with Iterative Retrieval and Verification](https://mlsanity.com/paper/2411.00784/) (2024)
- [A Cognitive Writing Perspective for Constrained Long-Form Text Generation](https://mlsanity.com/paper/2502.12568/) (2025)

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

- [Logical Phase Transitions: Understanding Collapse in LLM Logical Reasoning](https://mlsanity.com/paper/2601.02902/) (2026)
- [Symphony: A Cognitively-Inspired Multi-Agent System for Long-Video Understanding](https://mlsanity.com/paper/2603.17307/) (2026)
- [MARTI-MARS2: Scaling Multi-Agent Self-Search via Reinforcement Learning for Code Generation](https://mlsanity.com/paper/2602.07848/) (2026)
- [Inside the Unfair Judge: A Mechanistic Interpretability Account of LLM-as-Judge Bias](https://mlsanity.com/paper/2607.11871/) (2026)
- [A Quantitative Study of Sustained Focus in Large Language Models via Repetitive Deterministic Prediction Tasks](https://mlsanity.com/paper/2511.00763/) (2025)
- [The Architecture of Errors: From Universal Impossibility to Patch-Local LLM Reliability](https://mlsanity.com/paper/2605.30628/) (2026)
- [Presentation, Not Mechanism: A Render Confound in Deprecation-Aware Memory Evaluation](https://mlsanity.com/paper/2607.16019/) (2026)
- [First Things First: Teaching LLM-Based Agents to Prioritize Must-Haves before Nice-to-Haves](https://mlsanity.com/paper/2609.05224/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)

## Abstract (arXiv)

Multi-Hop Question Answering (MHQA) requires integrating dispersed, interdependent evidence through sequential reasoning under noise. This task is challenging for LLMs as they have a finite per-pass output capacity, beyond which the integration of task-relevant evidence proves unreliable. Consequently, the single-pass reasoning paradigm is inherently vulnerable to this capacity overflow. To formalize this bottleneck, our analysis establishes a Fano-style accuracy upper bound, defining a theoretical performance ceiling for single-pass LLMs. This bound reveals that accuracy inevitably collapses once task complexity exceeds model capacity, providing general principles for capacity-aware representation and structuring of MHQA in LLMs. Building on these principles, we introduce a proof-of-concept multi-call framework for MHQA, InfoQA. It ensures high per-step accuracy by combining capacity-aware task decomposition with active pruning of prior reasoning traces, keeping the information load within the single-pass limit. It further achieves robustness by a dependency-explicit workflow that enables precise control over the reasoning path. We construct a stringent and noise-rich benchmark to validate our theory and framework. Experimental results show that model behavior aligns with our predicted capacity curves while InfoQA achieves consistent performance improvements. We hope our work inspires more LLM multi-step reasoning methods: faGithub hrefhttps://github.com/KaiyangWan/InfoQAInfoQA.