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

This paper establishes a Fano-style theoretical upper bound demonstrating that single-pass LLM reasoning fails when task complexity exceeds model capacity, and proposes InfoQA, a multi-call framework that overcomes this bottleneck through capacity-aware decomposition and active trace pruning to achieve robust multi-hop QA performance.

The Gist

The Big Idea: The "Brain Overload" Problem

Imagine you are trying to solve a complex mystery, like finding out who wrote a book that inspired a movie, which was then adapted into a play. To solve this, you have to read a massive library of books (the "context"), find the right page in one book, read a sentence, then find a different book based on that sentence, and so on.

The paper argues that Large Language Models (LLMs)—the AI brains behind tools like chatbots—have a serious problem when doing this kind of "multi-hop" reasoning.

The Problem:
Think of an LLM's single pass of reasoning like a single, short-term memory buffer. It can only hold a certain amount of information at once.

• If the mystery is simple, the AI can hold all the clues in its head and solve it.
• But if the mystery requires jumping through many clues (hops) or reading a very long library (long context), the AI's "mental bucket" overflows.

When this bucket overflows, the AI doesn't just get a little bit confused; it hits a "Cliff." Its performance doesn't slowly get worse; it suddenly crashes. It starts mixing up clues, ignoring important facts, and giving wrong answers because the noise (irrelevant text) drowns out the signal (the real clues).

The Theory: The "Accuracy Cliff"

The authors used math (specifically information theory) to prove this limit exists. They call it the Accuracy Cliff.

• The Analogy: Imagine you are trying to carry water from a river to a garden using a cup.
  • If the garden is close (simple task), you can carry enough water in one trip.
  • If the garden is far and you have to carry a huge amount of water (complex task), your cup has a limit.
  • The paper proves that once the amount of water you need to carry exceeds the size of your cup, you cannot succeed, no matter how smart you are. You simply cannot fit the answer in the output.

They found that for these AI models, once the task gets too complex (too many "hops" or too much text), the accuracy drops off a cliff, not a gentle slope.

The Solution: InfoQA (The "Team of Investigators" Approach)

Since the AI's "single cup" is too small for big tasks, the authors built a new framework called InfoQA. Instead of asking the AI to solve the whole mystery in one giant gulp, they break it down.

How InfoQA works (The Metaphor):
Imagine you are a detective chief. Instead of asking one tired detective to read the whole library and solve the case in one hour, you organize a relay race.

1. Capacity-Aware Decomposition (Breaking the Task):
   You don't ask, "Who wrote the book for the movie?" immediately. Instead, you ask a series of small, easy questions:

   • Step 1: "Who wrote 'Dune'?" (The AI answers: "Frank Herbert.")
   • Step 2: "What movie was 'Dune' adapted into?" (The AI uses the answer from Step 1 to find the movie.)
   • Step 3: "Who directed that movie?"
     By breaking the big problem into tiny steps, the AI never has to hold too much information at once. It stays within its "cup size."

2. Pruning the Traces (Cleaning the Desk):
   After the AI answers Step 1, it writes down the answer. In a normal setup, the AI would keep the entire history of its thoughts, the whole library text, and the previous questions in its memory for Step 2. This makes the "desk" messy and crowded.
   InfoQA is like a strict office manager. After Step 1 is done, it throws away the old notes and the irrelevant library pages. It only keeps the current answer ("Frank Herbert") and rewrites the next question to be super short: "Who directed the movie based on Frank Herbert's book?"
   This keeps the information load low and prevents the AI from getting confused by old noise.

3. Dependency Workflow (The Chain of Command):
   The system explicitly links the steps. It ensures that the answer to Step 1 is the only thing used to start Step 2. This prevents the AI from getting lost or "drifting" off track.

The Results: Does it Work?

The authors built a special test (a "noise-rich" benchmark) where they could control exactly how hard the questions were. They tested this against standard AI methods (like Chain-of-Thought).

• The Cliff Confirmed: The standard methods hit the "Accuracy Cliff." As the questions got longer and more complex, their scores plummeted to near zero.
• InfoQA Wins: The new method stayed steady. Even when the questions were very long and had many steps, InfoQA kept getting the right answers because it never let the AI's "mental bucket" overflow.

Summary

The paper says: "Don't ask an AI to do too much in one breath."
If you force an AI to solve a complex, multi-step puzzle in a single pass, it will fail because its memory capacity is limited. Instead, break the puzzle into small, manageable pieces, solve them one by one, and throw away the old trash after every step. This keeps the AI sharp and accurate, even for the hardest problems.

Technical Summary

1. Problem Statement

The paper addresses the fundamental limitations of Large Language Models (LLMs) in Multi-Hop Question Answering (MHQA). MHQA requires integrating dispersed, interdependent evidence from a long context through sequential reasoning.

• The Core Bottleneck: LLMs operating in a single-pass paradigm (generating a full reasoning chain in one forward pass) are constrained by a finite output capacity. As the reasoning chain lengthens (more hops) or the context grows (more noise), the total information load exceeds the model's per-pass capacity.
• The Consequence: This leads to Capacity Overflow, where relevant signals are diluted by noise, causing intermediate inferences to fail. The paper argues that this results in an "Accuracy Cliff"—a sharp, non-linear collapse in performance once task complexity surpasses a specific theoretical threshold, rather than a gradual degradation.

2. Theoretical Framework & Methodology

The authors formalize the problem using Information Theory to derive a performance ceiling for single-pass reasoning.

A. Fano-Style Accuracy Upper Bound

The paper derives a theoretical bound based on two principles:

1. Conditional Fano Inequality: Relates error probability ($P_e$) to the residual uncertainty of the answer given the model's output.
2. Output Entropy Bound: States that the mutual information an output can provide is capped by its own entropy (the model's output capacity, $C$).

Theorem 1 (Accuracy Upper Bound):
For a single-pass policy, the maximum achievable accuracy ($Acc$) is bounded by the relationship between the task's Information Demand ($\beta = H(A|Q,C)$) and the model's Output Capacity ($C = H(Y)$):
$$h(Acc) + (1-Acc)\log(|A|-1) \geq \beta - C$$
Where $h(\cdot)$ is the binary entropy function.

Key Insight (The Accuracy Cliff):
When $\beta > C + 1$, perfect accuracy becomes mathematically impossible. The accuracy does not degrade linearly but collapses hyperbolically.

B. Anatomy of the MHQA Challenge

The paper identifies two compounding factors that drive $\beta$ (information demand) to exceed $C$:

1. Stepwise Capacity Overflow: Information demand grows super-linearly with the number of hops ($h$) and context length ($L$). The model is modeled as $\beta(h, L) = \beta_0 + \alpha L \gamma^{h-1}$.
2. Cross-Step Error Accumulation: Even small per-step errors are amplified exponentially as they propagate through the reasoning chain, causing the overall success probability to decay rapidly ($Pr(Succ) \approx (1-\epsilon)^{K+1}$).

3. Proposed Solution: InfoQA

To overcome the single-pass bottleneck, the authors introduce InfoQA, a multi-call reasoning framework designed to keep information demand within the model's capacity at every step.

Three Core Components:

1. Capacity-Aware Task Decomposition:
   • Breaks a complex multi-hop query into a sequence of single-hop sub-questions.
   • This reduces the information demand per step ($\beta_1$) to be well within the model's capacity ($C$), preventing the initial "Accuracy Cliff."
2. Dependency-Explicit Workflow:
   • Instead of relying on implicit memory, the workflow explicitly passes the state.
   • After solving a sub-question, the finding ($\hat{Z}_k$) is embedded into the next query ($Q_{k+1}$), ensuring the reasoning chain remains transparent and aligned.
3. Iterative Query Contraction:
   • Pruning: Discards the full reasoning trace of previous steps to prevent noise accumulation.
   • Contraction: Rewrites the query using the latest finding, keeping the prompt length constant and manageable regardless of the total reasoning depth.

4. Experimental Setup & Results

Benchmark Construction

The authors created a synthetic, noise-rich benchmark to rigorously test their theory.

• Controlled Variables: Systematically varied hop counts (1–4) and context lengths (0.5k–10k tokens).
• Noise: Included semantically similar distractors and irrelevant padding to prevent shortcut learning.
• Models: Evaluated on Qwen3-8B and Qwen3-14B.

Key Findings

1. Validation of the Accuracy Cliff:

   • Empirical results for single-pass baselines (Direct, CoT, ReAct, etc.) closely matched the theoretical Fano-style curves.
   • As effective information demand ($\beta$) increased, performance remained high until a critical threshold, after which it collapsed sharply, confirming the "Accuracy Cliff" phenomenon.
   • Methods like Chain-of-Thought (CoT) showed higher effective capacity ($C$) but still succumbed to the cliff at high complexity.

2. InfoQA Performance:

   • Superiority: InfoQA significantly outperformed all single-pass baselines, achieving an average F1 of 0.86 on 2–4 hop tasks (vs. 0.75 for Self-Consistency and 0.73 for CoT).
   • Robustness:
     • Depth: Maintained high accuracy even at 4 hops, whereas single-pass methods dropped to near-zero.
     • Length: Remained reliable in 8k–10k token contexts, while others collapsed.
   • Ablation: Removing decomposition or pruning caused performance to drop significantly, proving both components are essential for managing capacity and error accumulation.

5. Key Contributions

1. Theoretical Formalization: Provided a rigorous information-theoretic proof (Fano-style bound) establishing that single-pass reasoning has a hard performance ceiling defined by the ratio of information demand to output capacity.
2. Phenomenon Identification: Defined and characterized the "Accuracy Cliff" and the dual crises of Stepwise Capacity Overflow and Cross-Step Error Accumulation.
3. Framework Innovation: Introduced InfoQA, a practical multi-call framework that operationalizes capacity-aware decomposition and iterative pruning to bypass the single-pass limit.
4. Empirical Validation: Constructed a controlled benchmark that validated the theoretical curves and demonstrated the practical necessity of multi-call reasoning for complex MHQA.

6. Significance

This work shifts the paradigm for LLM reasoning from "how to prompt better in one pass" to "how to structure reasoning across multiple calls." It provides a theoretical justification for why multi-step, iterative approaches are necessary for complex tasks, moving beyond empirical observation to a capacity-based explanation. The findings suggest that for high-complexity reasoning, decomposition and state management are more critical than simply increasing model size or context window.