A Fano-Style Accuracy Upper Bound for LLM Single-Pass Reasoning in Multi-Hop QA
Authors: Kaiyang Wan
Lang Gao
Honglin Mu
Preslav Nakov
Yuxia Wang
Xiuying Chen
Venue: ICLR 2026 Poster (2026)
Keywords: large language models
multi-hop question answering
information-theoretic analysis
multi-call reasoning framework
Primary area: foundation or frontier models, including LLMs
TL;DR: We derive a Fano-style accuracy bound for single-pass LLM in multi-hop QA, revealing an Accuracy Cliff, analyze MHQA’s vulnerability, and validate the theory with a controlled benchmark and the InfoQA framework.

Abstract: 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  \href{https://anonymous.4open.science/r/InfoQA-55D1}{InfoQA}.

Published as a conference paper at ICLR 2026
A FANO-STYLE ACCURACY UPPER BOUND FOR LLM SINGLE- PASS REASONING IN MULTI-HOP QA
Kaiyang Wan Lang Gao', Honglin Mu', Preslav Nakov!, Yuxia Wang"1, Xiuying Chen Ix
'MBZAA, PINSAIT, Sofia University "St. Kliment Ohridski"
Xiuying. Suying.Chen&e
Chen @ mbzuai.ac.ae
ABSTRACT
Multi-Hop Question Answering (MHQA) requires integrating dispersed, interde- pendent evidence through sequential reasoning under noise. This task is challeng- ing for LLMs as they have a finite per-pass output capacity, beyond which the inte- gration of task-relevane evidence proves unreliable. Consequently, the single-pass reasoning paradigm is inherently vulnerable to this capacity overflow. To formal- ize this bottleneck, our analysis establishes a Fano-style accuracy upper bound, defining theoretical performance ceiling for single-pass LLMs. This bound re- veals that accuracy inevitably collapses once task complexity exceeds model ca- pacity, providing general principles for capacity-aware representation and struc- turing 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 accu- racy by combining sapacity-aware task decomposition with active pruning of prior reasoning traces, keeping the information load within the single-pass limit. It fur- ther achieves robustness by a dependdenc--xxplici workflow that enables precise control over the reasoning path. We construct stringent and noise-rich bench- mark to validate our theory and framework. Experimental results show that model behavior aligns with our predicted capacity curves while InfoQA achieves consis- tent performance improvements. We hope our work inspires more LLM multi-step reasoning methods: InfoQA
INTRODUCTION
Multi-Hop Question Answering (MHQA) (Yang et al. 2018 Trivedi et al. 2022; Mavi et al. 2024) is an important NLP task with critical applications in real-world domains such as scientific liter- ature analysis and complex fact verification (Yin et al. 2023] Yu et al., 2021). The task requires integrating multiple, interdependent pieces of evidence that appear in different segments of a long provided context. As a result, solving MHQA demands compositional reasoning: the model must carry forward intermediate findings from one evidence source and use them to locate or interpret information in subsequent sources. This stepwise dependency structure forms a reasoning chain, where the accuracy of each intermediate inference directly determines the correctness of the final answer. Accordingly, task success hinges on accurately resolving each reasoning hop while main- taining a coherent chain that faithfully composes intermediate findings into the final conclusion.
MHQA remains challenging for Large Language Models (LLMs) (Achiam et al. 2023 Bai
al. 2023 Liu et al. 2024) despite recent advances in prompting strategies and reasoning tech- niques (Havrilla et al. 2024). As shown in Figure [a). intuitively, because an LLM generates only a finite number tokens in single pass and each token has limited representational capacity, the model is constrained by an upper bound on the total information it can carry forward. This output capacity bound limits the amount of dispersed evidence that the model can reliably integrate at once. When the reasoning chain spans multiple evidence sources or when the context contains substan- tial irrelevant content, the total information load often exceeds this bound. As a result, the model becomes prone to capacity overflow, where relevant signals are diluted or overshadowed by noise, leading to inaccurate intermediate inferences and, consequently, incorrect final answers.
"Corresooniing author.

---

Published as a conference paper at ICLR 2026
Instruction Token
Noise Token
Evidence Token
Reasoning Token
Answer Token
Integration Step
Complesat
Pizmpl BrowornnSSp--
Capacity Overflow
(8) LLM Single-pass Reasoning Paradigm
3-hop QA Example
LLM
Complesity
Soquential Dependenee
(b) LLM Multi-call Reasoning Paradigm
Complesity&Capsity Management
Figure 1: Comparison of single-pase pass and multi-call reasoning paradigms. Single-pass reasoning is constrained by the limited output capacity of LLMs, making it difficult solve long-context and multi-hop problems. Multi-call reasoning mitigates this by decomposing tasks into sequentially dependent sub-steps, ensuring high per-step accuracy and a reliable reasoning chain.
To formalize this intuition, we first present an irfommation-theorete analysis that derives a Fano- style accuracy upper bound for LLM dingle-pass reasoning. This analysis reveals the Accuracy Cliff:: when the task's information demand surpasses the model's output capacity, performance does degrade gracefully but instead collapses sharply. We then examine why MHQA tasks partic- ularly prone to exceeding this cliff. By formalizing and dissecting the task structure, we identify two compounding challenges: Stepwise Capacity Overflow, driven by the super-linear growth of infor- mation demand with hop count and context length, and Cross-Step Error Accumulation, stemming from the amplification of even small per-step errors along the reasoning chain. Together, these anal- yses demonstrate that the single-pass paradigm is fundamentally inadequate for MHQA, motivating design of capacity- aware, multi-call paradigm as shown in Figure (b).
Building on the identified single-pass limitations and the structural demands of MHQA, we intro- duce InfoQA, proof-of-coneept multi-call framework for MHQA. InfoQA serves concretely demonstrate how multi-call reasoning alleviates the dual crises of Stepwise Capacity Overflow and Cross-Step Error Accumulation. It does so by (i) capacity-aware task decomposition, which lowers the information demand and secures per-step accuracy, (ii) dependency-explice workflow, which enforces alignment across reasoning steps and prevents the chain from drifting off course, and (iii) iterative query contraction, which condenses the problem state and filters noise keep information load manageable.
To precisely control hop count and context length, and thereby modulate the task-side informa- tion demand, we construct dedicated dataset to test our theory. Experiments confirm that single- pass methods indeed exhibit an Accuracy Cliff. with results closely matching our theoretical curves. Moreover, as prooffof-concepl, InfoQA consistently outperforms single-pass baselines, further demonstrating the practical advantage multi-call reasoning.
Our contributions can be summarized as follows:
1. We provide rigorous information- -hotmattion-hhoretiic analysis of LLM single-pass reasoning, de- riving Fano-style accuracy upper bound and revealing the Accuracy Cliff' phenomenon (Section
2. We dissect the structure of MHQA to explain why it is particularly prone to exceeding this limit, identifying two compounding challenges: Stepwise Capacity Overflow and Cross- Step Error Accumulation (Section
3. We introduce InfoQA proof-of-concept in Section 4 and. in Section 5 construct a controlled benchmark to validate our theory while demonstrating the practical advantage of multi-call reasoning paradigm.
2

---

Published as a conference paper at ICLR 2026
2 THE INFORMATION BOTTLENECK IN LLM SINGLE-PASS REASONING
To analyze the inherent limits of single-pass LLM in complex reasoning, this section establishes a theoretical framework. We begin by formalizing the task and our analytical tools, then derive universal accuracy upper bound that reveals fundamental relationship between task complexity and model capacity.
2.1 FORMALIZING MHQA AND ANALYTICAL BASIS
Problem Formulation. We study MHQA a closed-buok setting, where the model must answer solely from the provided context. Formally, the input consists of User Query and Context N), where E = {EI..... e are the necessary evidence snippets and N is irrelevant noise. The model generates output Y, which includes its intermediate reasoning trace R and the final answer tokens. An extractor g then maps this output to the predicted answer À gY).
Analytical Basis. Our analysis rests upon two foundational principles from information theory. We H+) to denote Shannon entropy (Shannon 1948 and ((:-)) for mutual information.
Conditional Fano Inequality (Fano & Hawkins 1961.. This principle establishes that to achieve a low error rate, the model's s output must suffciintly resolve the initial uncertainty about the answer. It connects the error probability, P.
Pr(Å + A C), to the residual uncertainty ( Q, J,C, Y):
HAA YY < h(P.) + Pe log([A) 1).
(1)
Output Entropy Bound (Cover) 1999). This principle states that the amount of information an output Y can provide about the answer A is fundamentally capped by its own entropy. Formally, the mutual information is bounded as:
I(A Q,C) S H(Y).
We provide a more detailed discussion in Appendix A.2
2.2 FANO-STYLE ACCURACY UPPER BOUND
The performance of LLMs in single-pass reasoning is governed by a fundamental principle: the information bottleneck. Any single-pass output has a finite information-carryinn capacity. When a task's complexity exceeds this capacity, a theoretical performance ceiling emerges, making ideal accuracy unattainable. By combining the Fano inequality with the output entropy bound from Sec- tion 2.1 we derive our central theorem, which forms the cornerstone of our framework.
Theorem (A Fano-Style Accuracy Upper Bound for Single-Pase Reasoning). For any single-pur pasle-pass, closed-book policy, let A E A be the ground-truth answer. Define the task information demand as B 2 (A Q, C) and the model's output capacity C' & HY)). The maximum achievable accuracy, Acc 1 Pe, is implicitly bounded by the following relationship:
h(Acc) + (1 Acc) log(1 - 1) 2 B C,
(3)
where i(.) denotes the binary entropy function and h(Acc) = h(1 Pc).
This theorem dictates that whenever the information demand 33 of a task exceeds the output capacity C' of a model, achieving perfect accuracy (Acc = 1) becomes mathematically impossible.
2.3 FROM THEORY INTUITION: COROLLARIES AND THE ACCURACY CLIFF
While the exact bound in Theorem is precise, its implications are more transparent through sim- plified corollaries. Together, they reveal a phenomenon we term the Accuracy Cliff.
Linear Accuracy Bound. By applying simple relaxations the main theorem, we obtain practical linear upper bound on accuracy:
Acc S min ( 1, B-
(4)
log [A]
3

---

Published as a conference paper at ICLR 2026
Uniform-Distributinn Case. In the common scenario where the context makes all potential answers nearly equiprobable, the information demand simplifies to 3 zs log |A], and the general bound from Theorem I yields more elegant and insightful upper bound accuracy (proof in Appendix A..
min C+11
Acc S
(5)
Phase Transition and the Cliff Edge. As shown in Figure 2 (taking C' = 200 as an example), equation S
1.5
describes the Accuracy Cliff curve reveals a sharp, saass-transition-like behavior: (a) Capacity-Sufficien
Model Capacity
Regime (3 v C + 1): Before the critical threshold, the accuracy is capped at 1, where performance is perfect and stable. (b) Capacity-Overflow Regime (3 > C+ 1);
0.5
P=C+1=00
Accuracy
Immediately after this point, the performance ceiling collapses. The maximum achievable accuracy is no longer 1, but begins decay hyperbolically according to the ratio (C + 1). This transition from perfect ac- curacy to a rapid decay is the essence of the "Accuracy Cliff," illustrating how performance does not degrade gracefully but instead falls off sharply when the task complexity overwhelms the model's Iss capacity.
0.2
Effective Information Demand ß The Accuracy Cliff. The the- oretical upper bound on accuracy is plot- ted against information demand 3, using C = 200 an illustrative example. Once B > C + 1, the accuracy declines sharply.
Figure 2:
This section establishes universal performance bound that formalizes the fundamental limits of the single- pass reasoning paradigm. proves that dingl-passs ac- curacy is ultimately constrained by an insurmountable barrier: the ratio of the task's information demand 3 to the model's output capacity C. This insight does more than just explain existing fail- ures; it shows the path forward. If single-pass reasoning is inherently bounded, the only viable solution is to transcend it. This thcoretical bottleneck leads to the next critical questions: In a real- world MHQA setting, what factors cause the information demand 3 to grow explosively? And how can we represent and structure the task to circumvent this single-pass limit?
ANATOMY OF THE MULTI-HOP CHALLENGE
In this section, we provide detailed dissection of the MHQA task, building on the Accuracy Cliff phenomenon from Section to uncover the root causes of capacity overflow. The essence of MHQA the navigation of a latent reasoning chain, represented as:
Zu
01
Z1
22
OK ZK 0x11, A.
In this chain, Zo is the initial entity from the query. A is the final answer, and each intermediate Z a crucial "bridge" entity. The transformation de represents the reasoning process itself that uses the context C' to advance from one entity to the next. This inherent chain structure is the source of a dual challenge: the risk of Stepwise Capacity Overflow within each individual step, and the systemic threat of Cross-Step Error Accumulation along the entire chain.
3.1 CHALLENGE 1: STEPWISE CAPACITY OVERFLOW
To predict when a model will be pushed off the Accuracy Cliff (3 > C) established in Section we now model the information demand 3 function of task properties in MHQA.
Modeling Tisk Demand. To connect our theoretical bound with observable task propertics, model B as function of hop count (h) and effective context length (L). Our model is based on three assumptions: (i) a baseline complexity fg representing the irreducible overhead of parsing query and locating evidence in any single step: (ii) a context burden that scales linearly with context length (L) to reflect the worsening signal-to-noise ratio; and (iii) a hop amplification factor 1h11 (7 2 1) that captures the super-linear growth in complexity uncertainty from prior steps propagates to subsequent ones. Combining these gives us the parametric form:
3(h, L.) Bo h-1
4

---

Published as a conference paper at ICLR 2026
This model shows that for y 1, 3 grows super-linearly with the number of reasoning hops. This exponential growth is the primary driver that pushes a model toward the "Accuracy Cliff."
Plug-in Accuracy Bound. By substituting this demand model into equation 5 get concrete, testable prediction for how accuracy is limited by task characteristics:
Acc(h, L)
mink 1,
C+1
Bo + aa
This equation formalizes a Capacity Crisis: as the number of hops h or context length L increases, the information demand 3 escalates rapidly, heightening the likelihood of a capacity overflow C and a consequent collapse in accuracy.
3.2 CHALLENGE 2: CROSS-STEE ERROR ACCUMULATION
The second challenge, Cross-Step Error Accumulation, arises not from the informational depth of any single step, but from the sequential nature of the reasoning chain itself. Even if the per-step accuracy is high, the overall probability of success can still collapse due to the amplification of small, individual enrors they propagate through the chain. To formalize this phenomenon, first define stepwise success event, Sk, where the model's prediction 2ạ. must be both correct and consistent with the prior state:
S
{ 2 = Z A 2 = 2x 02 (h- = 11:....... lo.=)...,KK)
Sk+1
(A
Ả Φ 1 Q1)
Overall success, Succ n Sk. therefore requires every step in the chain to succeed.
By the chain rule, Pr(Succ) is the product the condi- tional success probabilities at each step:
13-
K+1
K+1
Pr(Succ)
II 1=1
Pr (S Sen) = II
(
0.8
Pr(Succ)
k=1
0.5-
Pr 2x = Zz A 2x = 0b
(2x (2x- 1,.1,
Sek
0.4
G-
(9)
0.2
If we assume a uniform per-step success rate of at least 1 - E, the overall success probability is bounded by:
0.0
Pr(Succ) 2 (1+
(K(+1)) (10)
Figure 3: Error Accumulation. Even small per-step error rate (s) causes rapid decay in overall success probability as the number of hops (K) increases.
This linear decay, visualized in Figure formalizes the Compounding Crisis. shows how the chain structure acts as еттоr amplifier. While the Capacity Crisis is the "spark" that generates individual errors, Cross-Step Error Accumulation is the "powder keg" that makes even small sparks catastrophic, causing the entire reasoning process to fail.
An Inescapable Dilemma. Built upon the above two challenges, our deconstruction of the multi- hop challenge reveals a dual, interlocking crisis rooted in its latent chain structure. The single-pass reasoning paradigm is thus caught in vise grip: is simultaneously vulnerable to Stepwise Capacity Overflow, which generates inevitable per-step errors, and to Cross-Step Error Accumulation, which guarantees that these errors will be catastrophically amplified. This dual-front assault renders the conventional single-pass paradigm fundamentally untenable for complex reasoning. Therefore, the issue is the very single-pass paradigm force into.
INFOQA: A MULTI-CALL REASONING PARADIGM FOR MHQA
Our theoretical analysis in Section established universal performance limit for single-past rea- soning: the Accuracy Cliff. which dictates that accuracy inevitably collapses when information de- mand (3) exceeds model capacity (C).
5

---

Published as a conference paper at ICLR 2026
-apacity-Ararn Desmpouiin
Hopp ]-]
Hops
Hop
Quiry
Hopx
Hop:
Query
Hopx
Instraction Context
LLM
Pruned Context
L.M
Pruned Context
LLM
Dependency- Workflow
Figure 4: The InfoQA framework integrates three key components: (1) Capacity-Aware Task De- composition, which reduces the information demand by generating single-hop sub-questions; (2) Dependency-Explicci Workflow, where the evolving contracted query carries the reasoning state across steps; and (3) Iterative Query Contraction, which prunes reasoning traces and rewrites the query with 2x. Each LLM call approximates Φ and produces 2z.
Subsequently, our deconstruction of the MHQA task in JectionBrreveaee exactly why this limit is so perilous in practice. We found that MHQA's structure not only causes 3 to escalate exponentially, making capacity overflow almost certain, but also catastrophically amplifies the resulting errors along its reasoning chain. This dual diagnosis dictates the principles for an effective solution: successful methodology must be both capacity-aware to manage per-step information load, and robust to maintain the integrity of the chain.
4.1 THE INFOQA FRAMEWORK
InfoQA is multi-call reasoning framework designed from the ground up navigate the dual crises of multi-hop reasoning. operationalizes the principle decomposition by breaking down single, high-demand query into sequence of capacity-alignes sub-tasks, each with manageable informa- tion load. This is achieved through three synergistic components, as depicted Figure
Capacity-Aware Task Decomposition. The first step in InfoQA is to transform high-level multi- hop question into a simpler, single-hop sub-question. This decomposition is critical for reducing the initial information demand Q) For a question such as: "What is the birth date of the lead actor in the movie directed by the person who wrote 'Dune" "?", the initial sub-question
[A Q, C)) to more manageable per-step demand, B1 H (Z,
generated as: "Based on the provided context, who wrote "Dune"?" ?" By focusing the LLM on this narrow task, we ensure the reasoning step remains well within its single-pass capacity C, thereby directly counteracting the Capacity Crisis
Dependency-Explite Workflow. Once the problem is decomposed, a critical challenge to reli- ably link sequential steps, countering the Compounding Crisis described in equation 10 InfoQA achieves this with a Dependency-Expp ory, the workflow's 's state is explicitly maintained and passed the current, contracted query itself. After finding Žg. the query Q& is updated to Qk+1 by embedding this finding. For example: Qs: "..., directed by the person who wrote 'Dune"? > Finding: "Frank Herbert" -> Qx+1: "..., directed by Frank Herbert?". This makes the reasoning chain transparent, controllable, and robust against error propagation.
Workflow. Instead relying on model's internal mem-
Iterative Query Contraction. This mechanism is the engine that ensures the information load remains low throughout the entire reasoning process. After each step, InfoQA contracts the problem state two actions: Pruning, where the extensive reasoning trace is discarded prevent noise accumulation, and Contraction, where the query rewritten with the latest finding 2g. By iteratively pruning thoughts and contracting the query. we ensure the prompt for every step represents the most concise form the remaining problem. This prevents prompt length from growing with reasoning depth, acting as the crucial enabler that protects the entire chain from Stepwise Capacity Overflow.
EXPERIMENTS
We conducted experiments to validate the two central claims this work. Our evaluation is twofold: 1. Theory Validation: We first tested whether the empirical performance of LLMs aligns with our theoretical Fano-style accuracy upper bound, confirming that the Accuracy Cliff is a real and pre- dictable phenomenon. 2. Framework Validation: We then evaluated whether InfoQA framework can effectively transcend this theoretical limit, alleviating the capacity bottleneck to yield substantial performance gains.

---

Published as a conference paper at ICLR 2026
5.1 EXPERIMENTAL SETUP
Existing MHQA benchmarks are unsuitable for our study as they lack fine-grained control over task difficulty and often compromised by data artifacts, preventing a rigorous test of our theory. We therefore constructed a new, stringent, and noise-rich synthetic benchmark guided by three core principles: (i) systematic control over information demand (8) by varying hop count and distractor scale: (ii) high semantic similarity between evidence and distractors to prevent shorteut learning; and (ii)) a path maximization strategy for evidence placement to enforce genuine, non-trivial reasoning chains. This process yielded suite of datasets with systematically varied hop counts and context lengths, allowing for a precise evaluation of model performance against our theoretical bounds. We provide the key statistics of our benchmark in Table I detailed construction consideration and algorithm in Appendix A.44
Benchmark Construction.
and
Models and Baselines. We conducted our experiments on the Qwen3-8B and -14B (Yang eet al. 2025). We chose this publicly available model fam- ily to minimize architectural and training biases, allowing for fair evaluation of the reasoning paradigms themselves. All re- sults were obtained via official API calls. For all methods, we set temperature to 0.2 and a max-
Table 1: Statistics of our synthetic multi-hop QA benchmark.
1-hop
2-hop
3-hop
4-hop
Context Length
[0.5k, 1k, 2k, Sk, 10K]
Samples per
300
300
300
300
Total Samples
1,800
1,800
1,800
1,800
Evidence Order
[e:]
[ea,e:]
[e2.es.er]
lea, 6a, ei)
Evidence Position
[1/2]
[1/3,
(1/4,2/4,3/4)
11/5,2/5,3/5, 4/5]
Grand Total
7,200
imum generation length of 4096 tokens. Other parameters were default. We compared InfoQA
against a comprehensive suite of strong single-pass baselines, including: (i) Direct Prompting, (ii)
Chain-of-Thought (CoT) (Wei et al. 2022), (iii) Self-Consistency ( (Wang et al. 2023b). (iv)
Relf- (Madaan et al. 2023), (v) ReAct Yao et al. 2023). (vi) Plan-and-Solve (Wang et al.
2023a), and (vii) Self-Ask (Press et al. 2023). All baseline prompts were implemented as zero-shot, single-pass methods, carefully designed to follow the principles laid out in their respective original papers. All LLM calls within the InfoQA framework used the same backbone model and inference settings the baselines. We used F1 as the evaluation metric.
5.2 EMPIRICAL VALIDATION OF THE ACCURACY CLIFF
The results of Qwen3-14p 14B and Qwen3-8B 3BB showed the same phenomenon; we analyze Qwen3- 14BB and present Qwen3-8B in Appendix A.7 Table 2 Summarizes the average F1 scores across different context lengths and hop counts of Qwen3-14HB Our first experimental goal is to validate our core theoretical claim: the performance of single-pass models in MHQA is governed by an accuracy cliff- Concretely, we tested whether the empirical performance of strong prompting baselines conforms to the Fano-style accuracy upper bound derived Section
To connect theory with data, fit the parameters O (Bo, a,7, C) of our plug-in accuracy bound (Eq. 7 to empirical Fl scores, using Fl as a proxy for accuracy, Ace(h, L) = Fi(h, L). We minimized the mean absolute deviation between the ob- servations and the bound:
Parameter Estimation Protocol.
C+1 Aco(h, L) min{1, Bo Baaa (L.L)
min
(11)
For each baseline conducted fine-grained grid search over (a, Bu, C) and select the mini- mizer with respect to MAE. The fitted curves were then overlaid with empirical points (F1) as a function of the fitted effective demand (h,, L). We present the fitted plots in Figure 5 with detailed fitting statistics in Appendix and fitting algorithm in Appendix A.5
Alignment with Predicted Curves. Three consistent patterns emerged. (i) Accuracy cliff: as the effective demand 3 grows with hop count and context length, empirical points adhere closely to the theoretical bound and then collapse once 3 2 C'+1, 1, consistent with the predicted cliff.
OOu implementation Self-Consistency involves generating five reasoning paths by querying the model with varying temperatures: {0.1, 0.3, 0.5, 0.7, 0.9). The final answer is determined by a majority vote. For Refi-Refine, we report the final answer after one iteration of feedhack and refinement.
7

---

Published as a conference paper at ICLR 2026
Table 2: Average Fl scores of Qwen3-14B across different reasoning depths and context lengths. We compare InfoQA with single-past baselines: Chain-of- of-Thhught (CoT), Self-Refine (S-R), Self- Consistency (S-C), ReAct, Plan-and-Solve (P&S), Self-Ask (S-A), and InfoQA with ablation: w/o Capacity-Awas Aware Task Decomposition (D.) and w/o Pruning Past Reasoning Trace (P.).
Average Fl Score
Hops
Context Length
Direct
CoT
S-R
S-C
ReAct
P&S
S-A
InfoQA
w/o D.
w/o P.
0.5k
1,00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.87
1,00
1.00
2k
0.99
1.00
0.99
1.00
0.99
1.00
0.99
1.00
0.79
1.00
1
0.97
0.98
1.00
0.97
0.98
0.97
0.99
0.63
1,00
0.93
0.98
0.82
1.00
0.72
0.89
0.93
0.98
0.31
0.96
10k
0.91
0.96
0.79
0.98
0.59
0.84
0.85
0.95
0.28
0.90
0.5k
0.78
1.00
1.00
1.00
1.00
1.00
0.84
1,00
0.85
1,00
0.74
1.00
0.98
1.00
1,00
1.00
0.75
1.00
0.84
1.00
0.66
1.00
0.94
1,00
0.91
0,988
0.69
1,00
0.83
1,00
0.54
0.99
0.77
0.99
0.96
0.85
0.68
1,00
0.84
0.98
8k
0.23
0.79
0.39
0.83
0.53
0,54
0.63
0.96
0.52
0.88
1k
0.55
0.97
0.83
0.98
0.916
0.92
0.75
0.98
0.80
0.96
3
0.41
0.84
0.83
0.74
0.96
0.94
4k
0.31
0.72
0.30
0.77
0.59
0.61
0.64
0.84
0.60
0.79
0.06
0.32
0.12
0.35
0.24
0.19
0.52
0.64
0.43
0.44
10k
0.04
0.27
0.10
0.26
0.20
0.15
0.39
0.42
0.29
0.39
0.5k
0.26
0.98
0.90
0,99
0.96
0.96
0.94
0.96
0.92
0.95
0.13
0.95
0.79
0.98
0.87
0,93
0.84
0.96
0.84
0.92
0.09
0,77
0.46
0.80
0.64
0.66
0.76
0.95
0.75
0.83
4
4k
0.02
0.49
0.34
0,54
0.41
0.38
0.55
0.93
0.56
0.69
0.36
10k
0.00
0.09
0.09
0,12
0.06
0.06
0.21
0.30
0.23
0.18
Overall Average (2-4 hop)
0.32
0.73
0.57
0.75
0.66
0.66
0.65
0.86
0.65
0.78
1 hop Average
0.97
0.98
0.93
0.99
0.88
0.95
0.96
0.99
0.61
0.98
hop Average
hop Average
0.34
0.70
0.49
0.72
0.63
0.61
0.65
0.80
0.62
0.75
hop Average
0.09
0.57
0.45
0.61
0.51
0.53
0.61
0.80
0.60
0.65
Context Average (2-4 hop)
0.5k
0.58
0.99
0.98
0.98
0.88
0.98
0.98
0.48
0.97
0.87
0.99
0.94
0.95
0.78
0.98
0.83
0.96
0.38
0.69
0.92
0.83
0.83
0.73
0.96
0.75
0.92
0.29
0,73
0.47
0.77
0.65
0.61
0.62
0.92
0.67
0.82
8k
0.10
0.43
0.21
0.46
0.30
0,30
0.50
0.76
0.42
0.56
(ii) Capacity and hop inflation: CoT substantially increases the effective single-pass capacity C and reduces hop inflation relative to Direct, thereby delaying the onset of the cliff; S-C exhibits similar trend. (ii) Method-specific overheads: certain methods introduce additional demand. For example, S-A shows large 30 (higher base demand), which offsets the benefit of a larger C. Overall, the fitted overlays corroborate these findings: empirical markers align tightly with the theoretical envelope at low 3 and diverge only when the bound becomes active.
5.3 PERFORMANCE OF INFOQA
Overall performance. As shown in Table 2 InfoQA achieves the best results across most settings, with an overall average of 0.86 on 2-4 hop tasks, substantially outperforming strong singleppass baselines such as S-C (0.75) and CoT (0.73). The key strength of InfoQA lies in its robustness along two axes. First, in terms of depth robustness, InfoQA sustains high accuracy even the hop count increases, whereas single-pass baselines suffer sharp degradation beyond 2 hops due to compounded informational demand and eтror accumulation. Second, in terms of length robustness. InfoQA mains reliable under long contexts 18k-10k tokens), while methods like Direct and ReAct collapse to near-zero. This stability comes from explicitly pruning past traces and contracting queries, which prevents context inflation and keeps the effective demand B within the model's per-pass capacity C.
Ablation study. We further examined the contribution of InfoQA's key design choices: (i) w/o Decomposition (w/o D.), which executed the full reasoning chain in a single-pass without capacity control, and (ii) w/o Pruning (w/o P.). which preserved all past reasoning traces without contraction.
8

---

Published as a conference paper at ICLR 2026
Fano-Style (Fl)
Empirioa (I+1)
Empirical
Empiriall (l-3)
Empiriall (h=4)
Direct
CoT
S-R
S-C
3.4
3.0
338
1300
1330
260
2346
3900
230
400
$00
300
230
560
750
1000
1230
290
420
ReAct
S-A
wil
3.8
3.4
200
600
100
125
170
x-axis: Efflctive Information Demand (fited)
Figure 5: Qwenn- 14B F1 vs. theoretical curves across single-pas pangle-pas methods. The x-axis shows the estimated effective information demand (3), fitted per method, and the y-axis shows the F1 score.
As shown in Table 2 w/o D. quickly saturated at longer contexts and higher hops (overall average 0.65), confirming the single-pase bottleneck predicted by the Accuracy Cliff. Meanwhile, w/o P. performed better but still trailed InfoQA (0.78 vs. 0.86), as unpruned traces inflated context length and exacerbated cross-step errors. These results highlighted that both capacity-aware decomposition and iterative pruming were indispensable: decomposition ensured per-step demand remained within capacity, while pruning prevented error amplification across the reasoning chain.
Error Analysis of InfoQA. Compared with single-pass baselines, InfoQA exhibits a distinct er- profile. Since its multi-call design try prevent capacity overflow, most residual failures not caused by information bottlenecks but by semantic drift during iterative query contraction. In particular, the contracted query may sometimes omit subtle constraints (e.g., temporal qualifiers or entity disambiguation), causing the reasoning chain to pursue a plausible but incorrect path. An- other source of failure lies in the intrinsic model capacity: even when the task is decomposed into single-hop sub-questions, extremely long contexts can exceed the model's base comprehension abil- ity. Combined with multi-hop error accumulation, this results in degraded performance for InfoQA on long-con cong-context, high-hop scenarios. These errors suggest that future work should focus bet- ter decomposition to minimize the sub-task demand, improving contraction fidelity, and improving model's base capacity.
6 RELATED WORK
LLM Single-pass Prompting Methods. Single-pass prompting methods ask the model complete the entire reasoning process in one forward generation, without external decomposition or iterative calls. Classic examples (Kojima et al. 2022; Chen al. 2025 Cuntirescu-Pereins
al.) 2023)
include Direct prompting, Chain-of-Ti Thouuhh (CoT) (Wei et al. (022). More structured variants such as ReAct (Yao al.) 2023). Plan-and-See -nd-Svee (Wang et al.J (023a), and Self-Ask (Press al., 2023) guide the model with explicit prompting templates to elicit stepwise reasoning. Despite these design differences, all of them operate within a single forward pass, meaning that the reasoning chain must fit entirely within the model's per-pass information capacity. As result, their performance inevitably degrades when task complexity exceeds this capacity. Our work formalizes and quantifies this single-pass capacity limit, showing that it gives rise the "accuracy cliff" observed in MHQA task.
Multi-call Methods. In contrast to single-past prompting, multi-call methods decompose reasoning into multiple model invocations, with each call addressing a sub-task. A representative line of work is Self-Refin (Madaan et al. 2023), which iteratively generates feedback and refines the answer.

---

Published as a conference paper at ICLR 2026
Other approaches adopt recursive or pipeline-style reasoning, such sueti-step decomposition for Kim et al. 2024), fact check-
question answering (Li et al.) 2024), programming (Qian et al. 2024;
ing (Xie et al. 2025) and writing (Shao et al. 2024 Wan et al.] 2025). The success of these methods has empirically ly validated the effectiveness of distributing the reasoning load across multiple calls.
work provides theoretical foundation from information capac- ity perspective to explain why such an approach is beneficial. We show that single-pass methods face an inherent capacity bottleneck and that multi-call reasoning can provably keep the per-step information demand below the model's 's capacity.
Building on this paradigm,
Thoormation-Theorrtee Perspectives on MHQA. Information theory useful analyze the chal- lenges and bottlenecks of MHQA tasks. Xu et al. (2025) focused on retrieval-based systems, using pointwise conditional V-information to quantify the contribution of documents and optimize the retriever's selection process. Chen (2025) addressed the parameter storage capacity, establishing theoretical lower bound on the number of parameters necessary to reliably store multi-hop reason- ing chains within the model weights. Complementary to these retrieval and storage perspectives, our work targets the closed-book setting to formalize the single-pass output channel capacity bottleneck, identifying the Accuracy Cliff where performance collapses due to limited generation bandwidth rather than insufficient knowledge storage.
7 CONCLUSION AND FUTURE WORK
In this work, we began by providing an information- analysis of MHQA with LLMs. By deriving Fano-style accuracy upper bound, we formalized the fundamental capacity bottleneck of single-pass reasoning and revealed the Accuracy Cliff, where accuracy collapses once information demand exceeds model capacity. Building on this insight, we dissected MHQA to identify the dual challenges of stepwise capacity overflow and cross-step error accumulation, showing why single- pass reasoning inherently fragile. To validate our theoretical analysis, we introduced InfoQA, capacity-aware multi-call proof-of-concept that decomposes complex queries into manageable steps, prunes noisy traces, and explicitly controls dependency flow. Our experiments results align with the predicted capacity curves and InfoQA achieves consistent gains.
Looking ahead, we believe this work opens several promising directions: First, extending our analy- sis to multi-call settings could clarify how information accumulates across calls and what new limits emerge. Second, adaptive decomposition strategies would let systems dynamically decide how to split queries based on complexity and improving model's base information capacity. Third, applying the capacity- -ouud perspective to domains such as science or law would test its robustness under real-world noise and reasoning demands.
ETHICS STATEMENT
As part of our experimental design, we generated synthetic dataset in which all personal names and company names are entirely fictitious. These synthetic entities do not correspond to real individuals or organizations. The use of fabricated identifiers was intentional, in order to avoid potential privacy, legal, or ethical concerns that could arise from using real-world data. No personally identifiable information (PII) or sensitive data were collected or used in this work. Therefore, we believe that our research does not pose risks to individuals, groups, or organizations.
REPRODUCIBILITY STATEMENT
To ensure the reproducibility of our work, we provide an anonymous GitHub repository containing: (I) the synthetic dataset used in our experiments, (2) the code for constructing the dataset, (3) the implementation of all baselines as well as our proposed model, (4) the code used to fit empirical results to our theoretical curves, and (5) detailed README guidelines to facilitate reproduction of results. All experiments can be reproduced directly using the provided resources. In addition, we have uploaded a compressed archive containing all these files as part of our paper submission, so that reviewers access and reproduce our results even without relying on the external repository.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, lige Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. GPT-4 technical report. ArXiv preprint, abs/2303.08774 2023.
Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, et al. Qwen technical report. ArXiv preprint, abs/2309. 16609, 2023.
Qiguang Chen, Libo Qin, Jinhao Liu, Dengyun Peng, Jiannan Guan, Peng Wang, Mengkang Hu, Yuhang Zhou, Te Gao, and Wanxiang Che. Towards reasoning era: A survey of long chain-of- thought for reasoning large language models. ArXiv preprint, ftss/2503.0967,, 2025.
Thomas Y Chen. How many parameters for multi-hop? An iifommation-thhoree capacity law for knowledge retrieval in large language models. Proceedings of the Workshop on Knowledgeable Foundation Models at ACL, Vienna, Austria, 2025.
Thomas M Cover. Elements of information theory. John Wiley Sons, 1999.
Robert M Fano and David Hawkins. Transmission of information: A statistical theory of communi- cations. American Journal of Physics, 29(11):793-794, 1961.
Alexander Havrilla, Sharath Chandra Raparthy, Christoforos Nalmpantis, Jane Dwivedi- Yu, Maksym Zhuravinskyi, Eric Hambro, and Roberta Raileanu. Glore: When, where, and how to improve LLM reasoning via global and local refinements. In Proceedings of the Forty-first International Conference on Machine Learning. ICML '2024, Vienna, Austria, 2024. OpenRe- view.net.
Schoon Kim, Suhong Moon, Ryan Tabrizi, Nicholas Lee, Michael W. Mahoney, Kurt Keutzer, and Amir Gholami. An LLM compiler for parallel function calling. In Proceedings of the Forty-first International Conference on Machine Learning, ICML '2024, Vienna, Austria, 2024. OpenRe- view.net.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems, NeurlPS '2022, New Orleans, LA, USA, 2022.
Xinyi Li, Sai Wang, Siqi Zeng, Yu Wu, and Yi Yang. A survey on LLM--assed multi-agent systems: Workflow, infrastructure, and challenges. Vicinagearth, 1(1):9, 2024.
Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. DeepSeek- V3 technical report. ArXiv preprint, 199424 2024.
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang. Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurIPS '2023, New Orleans, LA, USA, 2023.
Vaibhav Mavi, Anubhav Jangra, Adam Jatowt, et al. Multi-hop question answering, Foundations and Trends Information Retrieval, 17(5):457-586 2024.
Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah Smith, and Mike Lewis. Measuring and narrowing the compositionality gap in language models. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 5687-5711, Singapore, 2023. Association for Computational Linguistics. doi: 10.18863//11/02.. findings-emmlp.77..
11

---

Published as a conference paper at ICLR 2026
Chen Qian, Wei Liu, Hongzhang Liu, Nuo Chen, Yufan Dang, Jiahao Li, Cheng Yang, Weize Chen. Yusheng Su, Xin Cong, et al. ChatDev: Communicative agents for software development. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguisties, ACI. '2024, pp. 15174-15186, Bangkok, Thailand, 2024.
Claude E Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379 423, 1948.
Yijia Shao, Yucheng Jiang, Theodore Kanell, Peter Xu, Omar Khattab, and Monica Lam. Assisting in writing Wikipedia- articles from scratch with large language models. In Kevin Duh, Helena Gomez, and Steven Bethard (eds.). Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Vol- ume I: Long Papers). pp. 6252-6626622 0252-6278, 6278, Mexico City, Mexico, 2024. Association for Computational Linguistics.
Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. MuSiQue: Multi- hop questions via single-hop question composition. Transactions of the Association for Compu- tutional Linguistics, 10:539-554, 2022. doi: 10. 1a21166/aaaaa0004777
Kaiyang Wan, Honglin Mu, Rui Hao, Haoran Luo, Tianle Gu, and Xiuying Chen. A cognitive writing perspective for constrained long-form text generation. ArXiv preprint, 0os/2502.125666 2025.
Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka-Wer Lee, and Ee-Peng Lim. Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.). Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 2609-2634, Toronto, Canada, 2023a. Association for Computational Linguistics. doi: 10. 1/t33//111202.aclllooo 147.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In Proceedings of the Eleventh International Conference on Learning Representations, ICLR '2023, Kigali, Rwanda, 2023b. OpenReview.net.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoe V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho. and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Anmual Conference on Neural Information Processing Systems, NeurIPS '002,, New Orleans, LA, USA, 2022.
Zhuohan Xie, Rui Xing, Yuxia Wang, Jiahui Geng, Hasan Iqbal, Dhruy Sahnan, Iryna Gurevych, and Preslav Nakov. FIRE: Fact-checking with iterative retrieval and verification. In Findings of the Association for Computational Linguistics: NAACI. 2025, NAACL '25, pp. 2901-2914, Albuquerque, NM, USA, 2025.
Hao Xu, Yunxiao Zhao, Jiayang Zhang, Zhiqiang Wang, and Ru Li. LOG: A local-to-global opti- mization approach for retrieval-based explainable multi-hop question answering. In Proceedings of the 31st International Conference on Computational Linguistics, ICLR '2025, pp. 9085-9095, Singapore, 2025.
An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, al. Qwen3 technical report. ArXiv preprint, abs/2505.095 09938, 2025.
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpoiQA: A dataset for diverse, explainable multi-hop ques- Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun't ichi Tsujii (eds.), Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2369-22 2380. Brussels, Belgium, 2018. Association for Computational Linguistics. doi: 10.18853/v1/D18...
tion answering.
12

---

Published as a conference paper at ICLR 2026
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R. Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In Proceedings of the Eleventh In- ternational Conference on Learning Representations, ICLR '2023, Kigali, Rwanda, 2023, Open- Review.net.
Fan Yin, Jesse Vig, Philippe Laban, Shafiq Joty, Caiming Xiong, and Chien-Sheng Wu. Did you read the instructions? Rethinking the effectiveness of task definitions in instruction learning. In Anna Rogers, Jordan Boyd-Graber and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 3063- 3079, Toronto, Canada, 2023, Association for Computational Linguistics. doi: 10.186533/ acl-long. 172.
Jianxing Yu, Qinliang Su, Xiaojun Quan, and Jian Yin. Multi-hop reasoning question generation and its application. IEEE Transactions on Knowledge and Data Engineering. 35(1):725-744 2021.
D. Zamfirescu- Pereira,, Richmond Y. Wong. Bjoern Hartmann, and Qian Yang. Why johnny can't prompt: How non-Al experts try (and fail) to design LLM prompts. In Albrecht Schmidt, Kaisa Väänänen, Tesh Goyal, Per Ola Kristensson, Anicia Peters, Stefanie Mueller, Julie R. Williamson, and Max L. Wilson (eds.). Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems, CHI '2023, pp. 137:1-437:22 Hamburg, Germany, 2023. ACM. doi: 10.11457554448835888388
A APPENDIX
A.1 LLM USAGE
We used LLMs auxiliary tools during the preparation of this work. Specifically, LLMs were employed three ways: (1) for proofreading and identifying minor typographical errors in the manuscript, (2) for generating a synthetic dataset that was used as part of our experiments, and (3) for automatic code completion during the development of our implementation. All research ideas, experimental design, and final manuscript writing remain the responsibility of the authors.
A.2 INFORMATION THEORETIC PRELIMINARIES: FULL PROOFS AND DISCUSSION
This appendix expands upon the information -heooretii preliminaries introduced in Section We provide complete proofs of the conditional Fano inequality and the output entropy bound, together with intuitive interpretations and implications for multi-hop reasoning.
A.2.1 PROOF OF THE CONDITIONAL FANO INEQUALITY
Setup. Let A be the ground-truth answer, À gY, Q, C.) the prediction derived from the model output Y (allowing the estimator to depend on (Q) and (Q,C) denote the query and context. Define the enror event E' = (Á + A} with probability P. & Pr(E = Q,C).
Step 1: Decomposition of conditional entropy. We begin from the chain rule of entropy:
H(A Q, H(A, F Q,C,Y) H{F A,Q,C,Y). Since E is deterministic function of (A, Y, Q, C), the last term vanishes, yielding
(12)
H(A Q,C,Y)= H(E Q. H(A E,Q,C,Y). Step Bounding each term. By the fact that conditioning reduces entropy.
(13)
H(E C.Y. < H(E Q) h((P.).
where h(-) is the binary entropy function. For the second term, conditioned on E = (error), the uncertainty about A is at most log( |A| 1), since all but the predicted answer remain possible. Thus
((A) F, C,Y) < P. log((AA 1)-
13

---

Published as a conference paper at ICLR 2026
Step 3: Combine. Together, obtain the bound:
H(A C,C.Y) S h(P.) + P. log(1A) -).
(14)
Step 4: Mutual information form. Rearranging yields the equivalent lower bound on mutual
information:
T(A:Y 1 Q,C) 2 - - [b(.) - |o 1)]-
(15)
L
This bound states that unless the predictor extracts at least B H(A Q,C) bits of information about A, nontrivial error is unavoidable. In other words, information demand implies error floor.
A.2.2 PROOF THE OUTPUT ENTROPY BOUND
Setup. The output is a sequence of tokens from vocabulary V. We distinguish two modeling choices for the length constraint.
Step I:
Mutual information bounded by entropy. By definition and because conditioning reduces entropy,
I(AYY Q, < H(Y
Step 2:
Upper bounds output entropy (two cases).
Fixed length m (or padded-to-m with a special token). Then Y E Vm and
H(Y) S log [V m log [V]
(16)
Variable length, at most m tokens (no padding). Then Y UK=D V with cardinality 1-
Ekzo k=
|v|==
hence
VI-1
[|m+t
HYY) log
(17)
V
Either equation or equation choice.
17 provides a valid capacity upper bound, depending on the modeling
A.2.3 IMPLICATIONS FOR MULTI-HOP REASONING
The two inequalities together establish information bottleneck for single-pass reasoning:
Demand side (3 H(A Q, Multi-hop QA inherently requires integrating dispersed
and noisy evidence, which inflates the conditional entropy of the answer.
Supply side (C (Y)). The single-pass output has finite entropy budget, given by
equation 16 or equation 17 scaling with output length and vocabulary.
Error floor (P.). Whenever > C, Fano's 's inequality dictates that the error probability cannot vanish, regardless of model size training.
This formalizes the intuitive statement: "No malter how smart the model is, if the task demands more information than the output can encode, an error plateau is inevitable." "
A.3 PROOF OF THE FANO-STYLE ACCURACY UPPER BOUND AND ITS COROLLARIES
Notation and setup. Throughout, all logarithms base 2, entropies and mutual information are measured in bits. We consider a closed-book, single-pass setting with discrete answer space given (conditioning variables). Let A A be the gold answer, Y be the model's single-pass output (a random variable taking values in a finite or countable set of token sequences), and A = g(Y) ) be the predicted answer obtained by a deterministic extractor g. Define the error probability
A, |A| > 2. The query Q and context
P.
and Acc Pa.
14

---

Published as a conference paper at ICLR 2026
We also define the task information demand 3 - ((A Q, C) and the model's outpur capacity
C a H(Y C). When needed, one may upper-bound C by modeling constraints on Y: if Y has fixed length m (or is padded to m with a special token) then
H(Y Q, & m |og
if Y has variable length at most without padding, then
H(Y Q) s log (
Two ingredients. We rely on two standard facts (made conditional on (Q. ())
Conditional Fano inequality (e.g. Fano & Hawkins 1961 any estimator of A, HA Q, A, h(P.) P. log (IA) - 1),
conditionalized on (Q, C)). For
(18)
where h(-) is the binary entropy function. 2. Output-entropy (capacity) bound (e.g. Cover 1999): for any (A,Y),
I(A;Y Q, & H(Y Q,C) = C.
(19)
A useful comparison between Y and = g(Y). Because Å is a deterministic function of Y, conditioning on the richer variable Y cannot increase uncertainty relative to conditioning on A:
H(A Q, & H(A (AIQ,,,A)
(20)
Combining equation 20 with equation 18 yields
H(A ((AIQ,C,Y) & A(P.) P. log (IA) - 1).
(21)
Proof of Theorem
Start from the chain rule for conditional mutual information:
I(A:Y Q = ((A Q,C) - (AA Q,C,Y) = 3 - (AA Q,C.Y).
Apply equation 21 to upper-bound the second term:
T(A:Y Q,C) 2 B [M(P)) + Pa log( - 1))]
Together with the capacity bound equation 19 obtain
B - ((P.) P. log( Al 1)] $ I(A:Y (Q,)) S C.
Rearranging gives
h(P.) P. log [A| 1) 2 B C.
Finally, substitute Pe = Ace and note that (PP)) = h(1 Ace) = h(Ace) to obtain
h(Acc) + (1 - Acc) log( |A| - 1) 2 B 3-C,
(22)
which is Theorem
Derivation of the Linear Accuracy Bound (Eq.
Starting from Theorem
h(Acc) + (1 - Acc) log(IA) - 1) 2 B C.
Use the elementary relaxations ((Acc) < (binary entropy is at most 1) and log(IA) - 1) s log (Al
(for |A| 2) obtain
1+ (1 Acc) log IA| 2 3 C.
Rearrange:
B - C-1
B C -
1-Ace 2
Acc <
log |A]
log |A
Because accuracy is trivially at most we write the bound with a cap:
Acc < min (1, 1, 3- C
log [A]
which is Eq. 4 (When the right-hand side exceeds 1, the min 1) keeps the bound meaningful.)
15

---

Published as a conference paper at ICLR 2026
Derivation for the Uniform-Distributin Case (Eq. 5). In the common where the context does not provide strong cues to distinguish among candidates, the posterior distribution p(a Q,C) answers E AA is close to uniform. Intuitively, this corresponds to situations where many distractor entities of the correct type (e.g., names, dates, or organizations) appear in the context, so that each candidate remains nearly equally plausible given (Q,C). Formally, this means that the entropy of the answer distribution approaches its maximum, i.e.,
B (AA Q.C) log IA);
since log |A|] is the entropy of a uniform distribution over A. Equivalently, the KL divergence between p(a C) and the uniform distribution ((a is small, i.e.,
(kL (Q,0) (I 0
so that the uncertainty is essentially governed by the candidate set size |A] itself. Since in this regime 3 log |A] 2 log(IA] - 1), replacing log([-A) - 1) by 3 enlarges the left-hand side of the inequality, hence yields weaker but still valid bound.
Plugging this approximation into Theorem ! and again relaxing h(Acc) & 1 gives
+ (1 Acc)
C.
Rearranging isolate Ace:
C+1
C+1 Ace <
- Al-) 3 2 C-C-1
1 1 Ace 2 1
B
Capping at 1 yields
C C+1) B
Ace
1 min
which is Eq. This form emphasizes the capacity-demand ratio (C+1)/B and makes the "accuracy cliff" explicit: the bound equals 1 whenever C'++I. 1,+,,,0 and decays hyperbolically once 3 > C C+1
Remarks.
The proof only uses that À is a (deterministic) function of Y: if Å were randomized given Y, equation 20 would still hold by the data-processing inequality (conditioning on (Q, C, C) is at least as informative as conditioning on (Q, C, A)).
The capacity constant C' is taken as the effective single-pase pasle capacity H(Y | C.) realized by the decoding policy, but it can be boundeb by modeling constraints on Y (e.g., maximum length and vocabulary size).
Equality conditions in the Fano-style bound are generally not attained in practical settings; the utility of the bound is in predicting the regime change at B se C + and explaining aggregate trends (the "accuracy cliff").
A.4 DETAILED BENCHMARK CONSTRUCTION
This appendix provides detailed account of the design principles and generation pipeline for our synthetic, noise-rich Multi-Hop Question Answering (MHQA) benchmark.
A.4.1 MOTIVATION AND DESIGN PRINCIPLES
As stated in the main text, our primary motivation was overcome the limitations of existing MHQA datasets, which often lack the fine-grained control over difficulty and the data hygiene nec- essary for a rigorous evaluation of coormationntheorede limits. To this end, our benchmark was designed around three principles:
1. Systematic Control over Information Demand (3): The benchmark must allow for the precise and independent control of factors known to influence 3, primarily the reasoning hop count (h) and the context length (L). This enables systematic study of how perfor- mance degrades as information demand scales, allowing for direct comparison with our theoretical Accuracy Cliff curves.
16

---

Published as a conference paper at ICLR 2026
2. Resistance to Heuristics and Shortcuts: The benchmark must be designed to test gen- uine reasoning rather than retrieval or pattern matching. This is achieved by ensuring all evidence is previously unseen by the model and is embedded within large number of semantically similar distractors. The high similarity forces the model to perform careful entity disambiguation and information extraction, rather than relying on shallow heuristics.
3. Maximization of Reasoning Path: The placement of evidence within the context must enforce a non-trivial reasoning path. A model should not be able to answer a multi-hop question by simply reading the context linearly. Our design forces the model to traverse back and forth across large sections of distractor text, maximizing the cognitive load and testing the model's ability maintain coherent reasoning state.
A.4.2 DATA GENERATION PIPELINE
Our generation pipeline is a programmatic. four-step process designed instantiate challenging MHQA problems that adhere to the principles above.
Step 1: Reasoning Chain Instantiation. We begin by defining of abstract semantic tem- plates (e.g., '(Person A, wrote, Book B)', '(Book B, was adapted into, Movie C)²). For a k-hop question, we sample i such templates and populate them with distinct entities drawn from curated knowledge base. This forms the gold evidence chain, (2,,e2..... ex A question is then program- matically generated to connect the initial entity e1 to the final entity eg. with the final entity serving as the ground-truth answer. For example, a 2-hop chain might be *(Frank Herbert, wrote, Dune)' and "(Dune, was adapted into, Dune (2021 film))', leading to the question "What film was adapted from the book written by Frank Herbert?".
Step 2: Semantically Rich Distractor Generation. For each piece of gold evidence e;, we gen- erate of Na distractor statements. This is done by taking the semantic template of e, and substituting its entities with other entities the same type (e.g.. other authors, other books). For in- stance, for "Frank Herbert, wrote, Dune)', distractors could be '(Isaac Asimov, wrote, Foundation)' or "(Frank Herbert, wrote, Dune Messiah) This process creates a large pool of plausible but factu- ally incorrect statements that are highly similar to the gold evidence, making the task stringent test of precision.
Step 3: Context Assembly and Path Maximization. This step realizes our third design principle. The gold evidence snippets are deliberately placed out of their logical reasoning order within the context. For instance, for a 3-hop task with logical order ej - 62 > cg, we might place them in the document in the physical order 62 Cg - c1. The snippets the document (e.g., at 1/4, 2/4, and 3/4 of the context length). The generated distractor statements then randomly shuffled and used to fill the space between the evidence snippets. This strategy forces the model to first find in the middle, use its information to find e3 further down, and then use that result to jump back to near the beginning to find e1-
inserted regular intervals within
Step 4: Noise Padding and Finalization. Finally, to control the overall context length (L), we pad the assembled context with generic, irrelevant noise text (e.g., paragraphs generated by LLMs). This padding is added to the beginning, end, and between existing statements until the target token count (from 500 to 10,000) is reached. This ensures the model must not only handle targeted, similar distractors but also vast amounts of truly irrelevant information, faithfully simulating real-world, noisy long-context scenarios.
This pipeline produces suite of challenging and controllable datasets, whose key statistics summarized in Table in the main text. By systematically varying h and L, we can precisely map the performance landscape and validate our theoretical predictions.
17

---

Published as a conference paper at ICLR 2026
Algorithm Multi-hop Reasoning Dataset Construction
1: Input: N 300, {500, 1000, 10000}
2: Output: Multi-hop datasets for each target length L
3: Phase 1: Initialize
4: Define entity dictionary & with categorics (personnel, organizations, etc.)
5: Define templates T; each t includes entity sequence Ex,, chain templates Ct questions Q
6: Phase 2: Generate Base Chains
7: for = 1 to N do
8:
Tii mod IT]
9: chain; + GENERATECHAIINC)
end for
11: function GENERATECHAIN()
Sample entities for E, from &
13: Format C2 with entities to get chain_tents
14:
return (t, shaii_feat entity_yaal values) end function
15:
Phase 3: Generate Distractors
17: function DISTR ACTORS(chain, Pdiist Rearr Tnniss)) Apply distractor templates to create similar and noisy sentences 19: return (similar, noise)
end function
Phase 4: Build Multi-length Dataset
22:
for L; E L do
23:
Compute Tldist; Thooise from Li for each chain, do
24:
25:
for to 4 do Scale distractors: distt |naistt (1 (1+0,6(h-1) 1))
(h)
26:
27:
distractors &- CENTERAT diist 5, Anoise)
sample + BUILDSAMPLE(h, chain, distractors)
29: end for
end for
31: end for
32: function AUILDS chain,
33:
<- Qchain semplate hh--: + chainnennitiee..
34: S + first sentences from balain.chhin_te.ae
35:
ctz CREATECONTEXT(S, D)
36: return (q. a, D, ctx)
37:
end function
38: Phase 5: Assemble Context
39: function CREATECONTEXT(S. D)
Interleave D D.similar and D.noise
41:
Insert S at fixed positions based on h (e.g. for h = 3: positions (1/4,2/4.344) 42: Pad needed to target token length
43: return context
end function
45: Phase 6: Save Output
46: for h 2,, 4}, L; do
47: Write all (g. a, ctx) triples to $h
$1k.. json
48: end for
49: Save dataset statistics
18

---

Published as a conference paper at ICLR 2026
A.5 FITTING ALGORITHM
This section details the procedure used to fit the relationship between effective information demand and task performance (FI). We formalize the parametric model, the loss function, the search strat- egy, numerical safeguards, and the computational complexity, and we provide pseudocode for re- producibility.
Model Assumption (Beta-Bound Structure) For given reasoning depth h 31, and context length (in tokens), we posit that the effective information demand
8(h, L) = a 1 L h-1 + So.
with parameters > 0, > 1. and 30 2 0. The attainable F1 is upper-bounded by an inverse dependence on 3::
Fi L) = min(1, )
where C 2 0 captures constant-information offset and induces a kink at F1 = 1.
Objective Given empirical observations F1 Flemp(( (h, L.), we estimate (a, (a,7, O) by minimizing the mean absolute error (MAE):
7, 7, C)
Σ
Fi(h, L) Flemp (h, L)
N
(b.
where N is the number of (h, L) pairs (here N = 4 x 6 24).
Search Strategy: Fine-Grained Grid Search To avoid local minima introduced by the non- smooth kink at Fl = 1, we employ fine-grained grid search over
a a A, 7EG,
E, CEC.
Unless otherwise stated, we use
A logspace 10 1000- 15), g linspaco (100, 3.00, 20). B = linspacd 200, 21), linspacd 20, 440,2022.
Each method (Direct, CoT, S-R, S-C, ReAct, P&S, S-A) is fitted independently, yielding its (a, 7,,0, C).
Implementation Details and Numerical Stability
Vectorization. For each (a, pair, we first compute the base term aTT^~1 for all (h, T.), and then sweep over So and C. This reduces redundant computation and improves through- put.
Stability at small 3. We enforce ((h, max{B(h, L), 10 10-99-000- avoid division by zero.
Upper-bound consistency. The cap min(l,-) ensures fidelity in the high-resource regime where Fl + 1.
Optional weighting, If desired, weight w(h, I.) can be introduced in L to emphasize specific depths or lengths (default: uniform).
Computational Complexity Let [A], [9), [B], and [C] denote the grid sizes and N the number of samples. The complexity per method is
(IA | [c)
Since N 24 small, the overall runtime remains practical under vectorized implementations. Faster variants can be obtained via coarse-to-fine (multistage) search or by shrinking grid ranges.
19

---

Published as a conference paper at ICLR 2026
Algorithm 2 Fine-Grained Grid Fitting for One Method
Require: Data {(ht, Li, F1,))=1 grids A, 9, B,C best_loss <- +0c, best t- Ø
2: for E A do
3: for
do
4: base; f- Tug h:-1 Vi
5: for 8g B do
6:
3 max(base; + Bo, 10 10-9)
7:
for C E do
8:
F1, min (1, (C 1)/3.) loss f N Ei F1, F F1,]
9:
if loss- < best_loss then
11:
best_loss f- loss; best +- (a, So: C)
end if 13: end for
end for
15: end for
16: end for
17: return best, best loss
Reproducibility All methods share the same (h, grid with h E (1,2,3,4) and L e {0.5k, 1k, 2k, 4k, 8k, 10k). We expand this grid with meshgrid -indexing="iij
and flat- ten to length N = 24 vectors for fitting. The default metric is MAE; alternative choices (e.g.. MAPE or weighted MAE) produce qualitatively similar trends. Parameter uncertainty can be assessed via bootstrap resampling over (h, L) pairs.
A.6 OWEN3-14B FITTING PARAMETERS
As shown in F the plug-in bound provides an excellent global fit, as reflected in the low MAE across all methods, and it captures method-level differences through the parameters (7, C, Bo). CoT and S-C expand the usable regime by increasing C' and reducing 7, thereby mitigating the cliff. S-A incurs a large base-demand penalty (8o), which counteracts the benefit of a higher C. Removing distractors nearly eliminates hop inflation (y z 1), indicating that compounding arises primarily from noise rather than depth. Taken together, these results empirically substantiate the accuracy cliff' predicted by our theory.
Table 3: Fitted parameters of the plug-in accuracy bound (MAE minimization) of Qwen3-14B.
Larger C' indicates higher effective single-pass capacity; smaller y indicates weaker hop inflation.
Method
7
Sn
C
MAE
Direct
0.0100
3.000
40
67.5
0.0963
CoT
0.0100
2.076
0
131
0.0320
S-C
0.00720
2.076
99.2
0.0273
S-R
0.0100
2.282
147
0.0531
ReAct
0.0100
1,768
80
115
0.0429
P&S
0.00268
1,974
20
35.8
0.0444
S-A
0.00518
1.974
160
162
0.0747
w/o D.
0.0100
1.050
70
67.5
0.0589
20

---

Published as a conference paper at ICLR 2026
Table 4: Fitted parameters of the plug-in accuracy bound (MAF minimization) of Qwen3-8B. Larger
C' indicates higher effective single-pass capacity; smaller indicates weaker hop inflation.
Method
a
7
8u
C
MAE
Direct
0.00720
3,000
10
20
0.1061
CoT
0.0100
2.076
60
131
0.0426
S-C
0.0100
2.076
60
131
0.0343
S-R
0.00518
2.076
50
51.7
0.0747
ReAct
0.00518
2.076
70
83.3
0,0465
P&S
0.0100
2.487
160
178
0.0480
S-A
0.00373
2.795
131
0.0475
A.7 EXPERIMENTAL RESULTS OF QWEN3-8B
Theory for single-pass methods. The plug-in accuracy bound in Eq. fits Qwen3-883 single- pass baselines well (Table 3 Figure (6) Direct exhibits small effective per-pass capacity (C x 20) and strong hop inflation ( = 3.0), hence an early accuracy cliff. CoT and S-C attain a much larger capacity (C' x 131) with moderate hop inflation (7 R 2.08) and the lowest MAE 2.0426/0.0343))
so their empirical points hug the theoretical envelope longer. P&S shows the largest C (= 178) but also large base demand (Bg 160) and higher (=z 2.49), which offsets its capacity at greater depth/length. ReAct and S-R have mid-range capacities (C RJ 83.3 and 51.7) and degrade earlier. S-A has sizable 3o (130) and high 7 (=s 2.80), reflecting method-specific overheads that accelerate the cliff despite a decent C. Overall, the fitted overlays confirm the accuracy-cliff picture: empirical Fl follows the bound and collapses once the fitted demand 3 crosses C+1.
Performance of InfoQA. 1. Depth robustness. On 2-4 hops, InfoQA overall average is 0.74 vs. 0.66 for S-C and 0.65 COT. By hop: at 2-hop, 0.89 (InfoQA) vs. 0.82 (S-C); at 3-hop, 0.64 vs. 0.63 ReAt;; at 4-hop, 0.68 vs. 0.52 (S-C) Gains grow with depth: at 4-hop and long contexts (c.g., 8k), InfoQA reaches 0.67, while the best single-pass baseline tops out around 0.16. This matches the theory: capacity-aware decomposition keeps each step's demand Bg < C. 2. Length robustness. InfoQA maintains strong performance as context length increases. For 2-hop at 8k tokens, it achieves 0.74 (vs. 0.67 for S-A and 0.57 for S-C); for 3-hop 10k tokens, it reaches 0.28, exceeding the best single-pass alternative (0.21 for S-C). Even at I-hop, where all methods strong, InfoQA remains competitive (average 0.93) without relying single long reasoning trace.
21

---

Published as a conference paper at ICLR 2026
Table 5: Qwen3-8B's Average FI scores across different reasoning depths and context lengths. We compare InfoQA with single-pass baselines: Chain-of-Thought (CoT), Self-Refine (S-R), Self- Consistency (S-C), ReAct, Plan-and-Solvv (P&S), Self-Ask (S-A).
Average Score
Hops
Context Length
Direct
Col
S-R
S-C
ReAct
P&S
S-A
InfoQA
1,00
0.96
1,00
1.00
0.98
1.00
Ik
0.98
1.00
0.94
1,00
0.98
1.00
0.98
1.00
0.99
4%
0.91
0.97
0.81
0.97
0.93
0,90
0.91
0.97
10k
0.76
0.87
0.49
0.89
0.74
0.68
0.71
0.78
0.5k
0.57
1.00
0.96
1.00
0.98
0.99
0.89
1.00
0.44
0.99
0.88
0,97
0.96
0.28
0.95
0.71
0.94
0.93
0.87
0.89
0.98
2
0.23
0.93
0.43
0.95
0.49
0.78
0.78
0.96
0.10
0.54
0.15
0.49
0.51
0.67
0.74
10K
0.10
0.47
0,56
0.48
0.44
0.42
0.66
0.72
0.5k
0.50
0.96
0.86
0.97
0.96
0.83
0.94
0.92
0.69
2k
0.13
0.79
0,51
0.81
0.82
0.62
0.67
0.83
3
8k
0.04
0.32
0.17
0.31
0.27
0.20
0.25
0.28
0.02
0.20
0.10
0.21
0.15
0.12
0.10
0.28
0.84
0.89
1.00
0.09
0.84
0.72
0.88
0.77
0.72
0.63
0.96
0.03
0.66
0.49
0.64
0.56
0.45
0.47
0.70
0.01
0.44
0.29
0.32
0.28
0.32
0.63
0.00
0.15
0,12
0.16
0.09
0,08
0.16
0.67
0.09
0.03
0.04
Average (2-4 (2-4hop) hop)
hop Average
0.96
0.79
0.90
0.89
0.93
2 hop Average
0.29
0.81
0.62
0.82
0.72
0.76
0.78
0.89
hop Average
4 hop Average
0.04
0.52
0.42
0.52
0.45
0.41
0.40
0.68
Context Average (2-4 hop)
0.5k
0.40
0.97
0.89
0.98
0.95
0.90
0.84
0.97
0.95
0.15
0.80
0.57
0.80
0.77
0.65
0.68
0.84
0.11
0.66
0.33
0.64
0.48
0.49
0.54
0.73
0.05
0.34
0.15
0.35
0.28
0.26
0.36
0.56
0.04
0.25
0,24
0.26
0.21
0.19
0.29
0.37
Fano-Style Bound (F1)
Empiriall (b-1)
Empirical (b-2)
Empitical (b-3)
Empirical (b-4)
Direct
CaT
S-R
1.0
0.5
1.4
0.0
902
1000
1900
3030
300
420
600
100
1000
100
710
100
400
100
S-C
ReAct
PAS
8-A
Information Demand f (fitee)
Figure 6: Qwen3-8B's Empirical F1 vs. theoretical curves across single-pas methods. The x-axis shows the estimated effective information demand (3), fitted per method, and the y-axis shows the F1 score.
22


Reviews:
[{"review_id": "SesG01r2B1", "reviewer": "Reviewer_uBRA", "summary": "This paper conducts an information-theoretic analysis of multi-hop question answering (MHQA) based on large language models (LLMs). Through a fano-style accuracy upper bound, it reveals a phenomenon of an “accuracy cliff” in single-step reasoning. While recent studies have emphasized the existence of reasoning errors and cascading error propagation and have attempted to address these issues from multiple perspectives, the theoretical insights provided in this paper are novel. Furthermore, the authors develop a capacity-aware multi-call proof-of-concept system called InfoQA. In the experiments, they provide both theoretical validation and framework validation.The experimental results show that the empirical findings are consistent with the predicted capacity curves, and that InfoQA also achieves performance improvements.", "questions": "(1) Why is $H(Y)$ used to represent model capacity? How is $H(Y)=200$ determined in the experiments?\n\n(2) How does Figure 1(a) demonstrate that the limited number of LLM tokens constrains the capacity of models to transmit information, and why is $step = 8$ chosen? How does the setup of Figure 2 illustrate the limitations inherent in the single-pass reasoning paradigm, and could similar issues also arise in the multi-call reasoning paradigm?\n\n(3) In the pruned context, how does the pruned ratio affect the model performance?\n\n(4) In capacity-aware task decomposition (Page 6), how to ensure that each single-step reasoning process remains within the processing capacity $C$ of model? Is it possible that, even after decomposition, some subtasks still exceed the effective model capacity $C$?\n\n(5) What are the differences between capacity-aware task decomposition and question-decomposition-based MHQA? To maintain rigor, the authors should avoid using absolute statements such as “the first information-theoretic analysis of MHQA”, as prior research has already demonstrated clear motivations, which may have been overlooked in the this work. It would be helpful for the authors to include a discussion, that situates their approach in relation to recent studies [1,2].\n\n[1] LOG: A Local-to-Global Optimization Approach for Retrieval-based Explainable Multi-Hop Question Answering. COLING2025\n\n[2] How Many Parameters for Multi-Hop? An Information-Theoretic Capacity Law for Knowledge Retrieval in Large Language Models. In Knowledgeable Foundation Models at ACL 2025.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(1) Focusing on information theory, this paper offers a novel perspective by analyzing MHQA from the standpoint of reasoning errors and cascading error propagation in the reasoning process. The rigorous theoretical analysis and findings contribute to readers’ better understanding for MHQA.\n\n(2) Motivated by the theoretical findings, the authors propose a capacity-aware multi-call proof-of-concept famework, which mitigates the issues of the accuracy cliff and cascading errors by reducing information requirements and employing pruning strategies. \n\n(3) The experimental design consists of theory validation and famework validation, which verify the effectiveness of the proposed ideas and methods.", "weaknesses": "(1) The presentation of the paper could be improved, although this can be addressed in a short time. For example, Figures 1 and 2 should include clearer explanations of how they illustrate that the limited token capacity of LLMs constrains information transmission, as well as what the “step = 8” in the figures specifically represents.\n\n(2) The authors claim that this work is the first information-theoretic analysis of MHQA. However, some related studies may have been overlooked. Adding discussions that connect this work with recent research would strengthen the contribution and help readers better position it within the broader literature.\n\n(3) Hyperparameter analysis: including additional experimental studies on parameters such as the pruned ratio and the model capacity $C$ after question decomposition would further enhance the empirical section and provide insights.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zzRR7FLA66", "reviewer": "Reviewer_DhBc", "summary": "This paper utilizes Information Theory to analyze the capability limitations of the single-pass solution to multi-hop question answering (MHQA), reveals the \"Accuracy Cliff\" phenomenon, identifies two challenges (\"Stepwise Capacity Overflow\" and \"Cross-Step Error Accumulation\"), and then proposes a multi-call framework (InfoQA) for MHQA.", "questions": "- Note: I would rate this paper as 7 initially, although this option is not available.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The analysis, grounded in Information Theory, is insightful, and it reveals the limitations of single-pass MHQA solutions.\n2. The experimental results (Table 2) demonstrate the effectiveness of the proposed InfoQA method.", "weaknesses": "1. I appreciate the theoretical analysis and experimental findings in this work, but I have some concerns regarding the analysis based on Information Theory:\n    - I do not think information theory is suitable to assess the capability of natural language. Even if we consider all the possible values of a token (i.e., the size of the vocabulary) and compute the entropy or self-information of this token $H(X) = - \\sum_{x \\in X} p(x) log p(x)$, this still ignores the variability, richness, and ambiguity of the meaning conveyed by natural language. A single word can mean a lot.\n    - With a finite number of tokens in a single pass, inefficient reasoners may suffer from the limited output budget, but efficient ones can use fewer tokens to achieve desirable results.\n    - In addition, inefficient reasoners can utilize inference-time scaling strategies to extend their single-pass reasoning trace, making the limited budget not much of a fundamental issue.\n2. The experiments are conducted on the synthesized dataset proposed by this paper, without empirical results on existing widely used MHQA benchmarks.\n3. Section 5.2 and Figure 5: The empirical results do not align well with the theoretical curves (Accuracy Cliff) to me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bugTSNtQt2", "reviewer": "Reviewer_KUVW", "summary": "The paper addresses the challenge of Multi-Hop Question Answering (MHQA), where multiple, dispersed, and interdependent pieces of evidence need to be integrated through sequential reasoning. This task is particularly difficult for large language models (LLMs) due to their finite output capacity per pass, which makes the integration of relevant evidence unreliable once the task complexity exceeds model capacity. The paper formalizes this bottleneck by introducing a Fano-style accuracy upper bound, which defines a theoretical performance ceiling for single-pass LLMs. This bound shows that as task complexity increases beyond model capacity, accuracy inevitably collapses.\n\nBuilding upon this theoretical foundation, the authors propose a new multi-call framework for MHQA, called InfoQA. InfoQA addresses the capacity overflow by ensuring high per-step accuracy through capacity-aware task decomposition and active pruning of prior reasoning traces. This helps keep the information load within the model’s single-pass limit. Furthermore, InfoQA enhances robustness through a dependency-explicit workflow, which allows for precise control over the reasoning path. To validate their approach, the authors construct a stringent, noise-rich benchmark and show that the model's performance aligns with the theoretical capacity curves. Experimental results demonstrate that InfoQA consistently improves performance in MHQA tasks.", "questions": "Authors may consider revising the presentation and add a main figure to help readers intuitively understand the paper and more baselines are expected to validate the effectiveness of this framework.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The introduction of the Fano-style accuracy upper bound provides a unique theoretical foundation for understanding the limitations of single-pass LLMs in handling complex MHQA tasks. This may provide some insights for future research in capacity-aware representation for LLMs.\n\n2. The work provides a comprehensive experimental result which involves various settings.", "weaknesses": "1. While the InfoQA framework offers clear benefits, the multi-call nature of the approach could introduce overhead, especially for tasks requiring many iterations. This might limit its scalability for more real-time applications or systems with stricter performance requirements.\n\n2. Overemphasis on Theoretical Bound: The theoretical Fano-style upper bound offers valuable insights into the performance limits of single-pass LLMs. However, the heavy focus on this theoretical bound may overshadow more practical solutions for real-world MHQA scenarios. The boundary established may not always align with the practical constraints of large-scale systems, where the focus should be on scalable, efficient reasoning. Moreover, while the paper introduces many complex formulas, they are not always effectively integrated with the core problem of MHQA. The formulas provide theoretical rigor but may not offer direct, actionable solutions for improving the model’s real-world performance.\n\n3. It could benefit from a more direct comparison with other multi-hop question answering systems or frameworks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)