Hi-Q: Hierarchical Evidence-guided Query Refinement for Multi-Hop Question Answering

AI summary

Overview

Research area: Natural Language Processing, specifically multi-hop question answering (QA) and retrieval-augmented generation (RAG).

Technical level: Advanced. The paper formalizes a search problem over query granularity, derives a cost-sensitive threshold rule, and evaluates against graph-based, iterative, and agentic baselines.

Scope: Hi-Q is an evidence-conditioned framework that builds a dependency-ordered query tree online, expanding a query node only when retrieved evidence fails to support it, evaluated on three multi-hop QA benchmarks under full-corpus and controlled retrieval.

What This Paper Is About

Multi-hop QA questions compress a chain of dependent information needs into one sentence, but the corpus exposes facts at a much finer granularity, so even a logically valid decomposition may not match what the retriever can actually find. Hi-Q reframes this as retrievable granularity discovery and asks not how to decompose a question but when a query unit is already supported by evidence and therefore should not be split. The goal is to grow a query tree whose shape is dictated by corpus support signals rather than by a fixed decomposition template or a pre-built knowledge graph.

Key Contributions

1. Retrievable granularity discovery as a problem formulation. The authors frame multi-hop RAG as identifying the query unit at which a reasoning step becomes both retrievable and answerable under a given corpus.

2. Failure-aware granularity control. An evidence-conditioned policy expands a query node only when a resolution operator detects insufficient evidence support. The paper shows this choice corresponds to a cost-sensitive threshold on unresolved support, with the threshold formula derived in Appendix B.

3. Dependency-preserving hierarchical refinement. A binary expansion operator resolves prerequisite sub-queries first and writes their answers and evidence into the interaction history before the dependent branch is resolved, with a semantic coverage verifier that repairs invalid splits.

4. Evaluation under full-corpus retrieval. Across MuSiQue, HotpotQA, and 2WikiMultiHopQA, Hi-Q outperforms graph-based, iterative, and code-executing agent baselines without pre-built knowledge graphs or task-specific fine-tuning, and a cost-matched configuration is cheaper and more accurate than iterative retrieval at a similar number of LLM calls.

Main Findings

• Large gains under full-corpus retrieval. On 1,000-question subsets drawn from corpora of 139,416 passages (MuSiQue), 430,225 (2WikiMultiHopQA), and 5,233,235 (HotpotQA), Hi-Q reaches 52.3 EM and 64.0 F1 averaged over the three benchmarks, ahead of IRCoT by 15.1 EM / 18.2 F1 on that same average. Per-benchmark margins over IRCoT are 13.0 EM / 15.8 F1 on MuSiQue-full, 27.0 EM / 32.5 F1 on 2Wiki-full, and 5.4 EM / 6.3 F1 on HotpotQA-full.

• Gains over graph-based RAG without corpus-wide graph construction. Hi-Q surpasses PropRAG by 11.5 EM / 12.0 F1 on MuSiQue-full and by 9.9 EM / 12.1 F1 on 2Wiki-full, the two full-corpus settings where PropRAG's graph could be built within the compute budget. PropRAG is omitted for HotpotQA-full because LLM-based graph construction over 5.2M passages would cost more than $2,500 in API calls alone.

• Best accuracy in the controlled setting as well. In the sampled supporting/distractor pool used by prior work, Hi-Q achieves 57.9 EM and 69.3 F1 on average, ahead of PropRAG by 5.6 EM / 3.9 F1 and IRCoT by 13.7 EM / 15.8 F1. The largest controlled gains are on MuSiQue: 7.3 EM / 5.0 F1 over PropRAG and 13.1 EM / 14.8 F1 over IRCoT.

• Statistically significant improvements. Every improvement over IRCoT and PropRAG is significant across all six controlled comparisons and all five full-corpus comparisons, with 19 of the 22 EM and F1 tests at p < 10⁻⁴. The smallest margin, 3.2 F1 over PropRAG on 2Wiki in the controlled setting, reaches p = 0.0033, and the F1 gain over PropRAG on MuSiQue-full has a 95% confidence interval of [+9.44, +14.57]. Tests use a paired question-level bootstrap with 10,000 resamples and 95% percentile intervals under temperature-zero decoding.

• Agentic execution relocates rather than removes the problem. Against a coding agent and a Recursive Language Model, Hi-Q improves by 30.8 EM / 26.8 F1 and by 24.4 EM / 26.7 F1 on average. These are controlled adaptations under the standardization applied to all baselines, not reproductions of published configurations.

• Higher retrieval recall does not imply better answers. Self-Ask attains the highest average Recall@5 but issues more sub-queries and retrieves roughly 33% more documents per question than Hi-Q; it reaches 35.7 EM against Hi-Q's 57.9 EM.

• The unresolved-support trigger is precise and conservative. On triggered MuSiQue cases, decomposition on the Clean subset (excluding 366 annotation-error questions) raises all-gold cover from 7.9% at root@5 to 42.7% at budget-matched Leaf@5 and 57.7% at Leaf@all, with 38.7% answer recovery. Manual analysis of 100 sampled unresolved triggers gives an unambiguous false-trigger rate of 10%, meaning the trigger fires on a genuinely unresolved query–evidence state in approximately 90% of cases. Trigger causes are granularity mismatch (66%), annotation error (14%), malformed subquery (10%), false abstention (7%), and reader failure (3%). On 100 normal queries the False Rejection Rate is 11%, and on 50 adversarially unanswerable queries Hi-Q identifies 49 of 50 as unanswerable, a False Acceptance Rate of 2%.

• Each component of the control loop contributes. Removing hierarchical decomposition and using a static one-shot decomposition drops average performance from 57.9 EM / 69.3 F1 to 51.5 EM / 63.7 F1. Removing dependency awareness drops it further to 47.1 EM / 56.0 F1. On a sampled 100-query setting, replacing the failure-aware trigger with always-decompose reduces 60.7 EM / 70.8 F1 to 57.3 EM / 68.5 F1, a 3.4-point drop that bounds the cost of any trigger error. The semantic coverage verifier repairs 14.8–18.8% of triggered decompositions, and its removal costs 1.0 F1 at 4-hop depth on MuSiQue.

• Graceful degradation with reasoning depth. On MuSiQue, Hi-Q reaches 55.2 and 39.2 F1 at 3 and 4 hops, compared with 43.4 and 35.4 for IRCoT and 43.1 and 26.9 for PropRAG.

• Cost profile. Hi-Q uses 70.5% fewer tokens in total than IRCoT but takes 2.11 times the mean latency, 1.95 times the LLM calls, and 7.54 times the output tokens, because the resolution step is paid at every node while decomposition and verification are invoked only for unresolved nodes. The cost-matched variant caps recursion depth at 1, using 2.93 versus IRCoT's 2.92 LLM calls, 9.4 times fewer input tokens, running 25% faster, and costing 8.6 times less per question in API tokens at GPT-4o-mini list prices ($0.15 and $0.60 per 1M input and output tokens as of August 2026), while improving accuracy by 10.4 EM / 11.6 F1 macro-averaged over the three benchmarks, with EM gains from +3.5 to +18.1 (all p ≤ 0.0036). Its output generation remains 77% higher than IRCoT's, 131 versus 74 tokens. Hi-Q is also faster than PropRAG's 23.1 seconds, a figure that excludes corpus-wide graph construction.

Methodology in Plain English

The system treats answering a multi-hop question as a search over how finely to phrase a query. Each query node carries a state consisting of the query itself, an accumulated interaction history, and a recursion depth. Three prompted-LLM modules do the work:

1. A resolution operator rewrites the current query using what has been learned so far while staying anchored to the original question, retrieves the top-k passages (k = 5, using NV-Embed-v2 with L2-normalized dot-product retrieval), and has a reader answer from them. If the reader returns an answer, the node is treated as resolved and stops expanding. If the reader returns nothing, the node is considered unresolved and becomes eligible for refinement. Refinement must precede retrieval because dependent sub-queries often contain references whose meaning is only fixed by earlier steps — for example, once the performer of "III" is identified as Stanton Moore, a downstream query about "the birthplace of the performer of III" can be rewritten around Stanton Moore directly.

2. A binary expansion operator proposes exactly two sub-queries: a prerequisite that resolves a bridge fact and a dependent query that uses that bridge. The order follows entity references and relational dependencies (compositional, temporal, or causal) rather than surface syntax. The prerequisite is resolved first, and its answer, retrieved evidence, and intermediate context are written into the history before the dependent branch runs, so retrieval for the dependent branch is grounded even if the prerequisite itself stays unresolved.

3. A semantic coverage verifier checks whether resolving the left then the right sub-query recovers the intent of the parent without adding, omitting, or reordering constraints. It gets at most one repair attempt; if the revised split is still inconsistent, the node is marked non-decomposable and decomposition stops for that branch.

Binary splitting is chosen over multi-way splitting to avoid over-fragmenting the question or skipping bridge facts. Recursion stops when a sub-query is resolved, or when a sub-query is non-decomposable or maximum depth d_max = 4 is reached, in which case the branch returns a null result and the solver proceeds with available evidence. A synthesis step then aggregates intermediate answers, retrieved evidence, unresolved sub-goals, and history into a final response, disambiguating multiple candidates by consistency with other sub-query results rather than by passage rank alone. Evaluation covers MuSiQue, HotpotQA, and 2WikiMultiHopQA with 1,000 sampled validation questions each, under both the complete corpus and a pooled supporting/distractor corpus, reporting EM, token-level F1, and Recall@2 and Recall@5. GPT-4o-mini is the reader unless otherwise stated; Llama-3.3-70B and Qwen3-30B-A3B are evaluated in Appendix F.

Why This Matters

Impact on research. The paper reframes multi-hop RAG from a question of retrieving more passages to a question of discovering the granularity at which each reasoning step becomes retrievable and answerable. It shows that a resolution test against retrieved evidence can serve as an operational signal for when to decompose, and that such a signal is precise enough to route decomposition without a learned classifier. It also provides a controlled comparison against agentic execution and corpus-side graph construction, arguing that externalizing computation does not settle at what granularity each retrieval call is expressed.

Real-world applications:

• Enterprise and legal search over large document collections, where a question may require chaining facts across filings, contracts, or case documents held in corpora far larger than annotated QA pools.
• Scientific literature assistants, where answering a query requires linking a method to a dataset to a reported result across separate papers.
• Customer-support and IT troubleshooting systems, where a diagnosis depends on resolving a device or configuration fact before a downstream question can be asked.
• Biomedical and clinical knowledge lookup, where a chain such as gene to pathway to drug to trial must be followed through sources that expose information at different levels of detail.

Industry relevance. The cost analysis is directly relevant to deployment. Hi-Q avoids corpus-wide graph construction, which the paper notes would exceed $2,500 in API calls for PropRAG over 5.2M passages, and its cost-matched configuration is reported as 8.6 times cheaper per question than IRCoT at essentially the same number of LLM calls. The overhead is conditional rather than fixed: every node pays for the resolution step, but decomposition, verification, and descendant resolution only run when a node is unresolved.

Future Directions

• Learned control policies. The paper states that a supervised or reinforcement-learned controller observing the same evidence state remains compatible with Hi-Q's interface, distinguishing the method from Adaptive-RAG-style routing that commits before any evidence is seen (compared in Appendix D, where routing reportedly collapses to a near-constant policy).

• Replacing the hard trigger. The training-free test that treats a null reader answer as the unresolved signal is described as a hard classifier that is not claimed to compute the posterior; a calibrated classifier, an entailment model, or a trained cost-sensitive router could substitute without changing the control semantics (Appendix C).

• Scaling to longer dependency chains and broader corpora. The recursion depth is capped at d_max = 4, which the authors say matches the maximum reasoning depth analyzed in MuSiQue; the F1 at 4 hops (39.2 on MuSiQue) is the weakest point reported, and the paper does not claim global optimality of the resulting query tree.

• Strengthening the verifier and reader substitutions. The verifier is limited to one repair attempt and acts mainly as a depth guardrail, and the paper does not report how a different reader module interacts with the trigger beyond the Llama-3.3-70B and Qwen3-30B-A3B evaluations in Appendix F.

Target Audience

Researchers and practitioners working on retrieval-augmented generation, multi-hop question answering, and agentic retrieval systems. The paper is most useful to readers already comfortable with retrieval pipelines and LLM prompting who want to understand when decomposition helps and when it hurts, and

Authors’ abstract

A central bottleneck in multi-hop Question Answering (QA) is that the granularity at which a question is expressed often differs from the granularity at which corpus evidence is retrievable. Existing methods address this mismatch by imposing fixed graph structures over the corpus, by iteratively reformulating the query, or by executing a generated program over it, but these strategies do not explicitly decide when a query unit is already supported by evidence and when it should be refined. We formulate this bottleneck as retrievable granularity discovery and introduce Hi-Q, an evidence-conditioned framework for hierarchical query refinement. At each query node, a resolution operator tests whether retrieved evidence supports the current query unit; resolved nodes terminate, while unresolved nodes are expanded by a dependency-preserving binary operator and checked by a semantic coverage verifier. Hi-Q therefore grows a query tree whose topology is determined by corpus support signals rather than by a fixed decomposition template or a pre-built graph. We evaluate Hi-Q on three multi-hop QA benchmarks, primarily under full-corpus retrieval, where dependent evidence must be located among open-domain distractors rather than within a small annotated pool. In this setting Hi-Q reaches 52.3 EM and 64.0 F1 averaged over the three benchmarks, ahead of the iterative retrieval baseline IRCoT by 15.1 EM / 18.2 F1 on that same average, and ahead of the graph-based RAG baseline PropRAG by 11.5 EM / 12.0 F1 on MuSiQue-full, without corpus-wide graph construction. In the restricted supporting/distractor setting used by prior work, Hi-Q likewise attains the best accuracy, with 57.9 EM and 69.3 F1 on average, ahead of PropRAG by 5.6 EM / 3.9 F1 and IRCoT by 13.7 EM / 15.8 F1. The project page is available at https://hi-q-project.github.io/.