PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jueun Kim, Sungho Park, Wook-Shin Han

arXiv:2608.30468v1cs.CLcs.IR

TL;DR

Multi-hop QA often expresses dependent information needs more coarsely than corpus evidence can be retrieved, leaving unclear when a query should be refined. Hi-Q uses evidence-conditioned resolution and dependency-preserving hierarchical refinement, achieving improved accuracy across full-corpus and restricted settings while avoiding corpus-wide graph construction.

  • Problem

    Multi-hop QA has a query–evidence granularity mismatch, and existing strategies do not explicitly decide when a query unit is already evidence-supported versus needing refinement.

  • Method

    Hi-Q tests each query node against retrieved evidence, stops resolved nodes, and expands unresolved nodes through dependency-preserving binary decomposition with semantic coverage verification.

  • Results

    Hi-Q improves answer accuracy over graph-based, iterative, and code-executing baselines across three benchmarks, including full-corpus and restricted retrieval settings.

  • Takeaways & Limitations

    Query granularity can be treated as an evidence-conditioned control variable rather than a fixed design choice, without corpus-wide knowledge graph construction.

  • Takeaways & Limitations

    Evaluation covers English, Wikipedia-derived, passage-based short-answer QA with acyclic dependencies; mutually dependent or jointly optimized branches are outside the modeled setting.

Abstract

from arXiv · show

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/.

1 Introduction

Multi-hop QA compresses dependent information needs into coarse queries, while corpus evidence is often available only at finer granularity. Hi-Q makes refinement conditional on evidence support and preserves dependencies when expanding unresolved queries.

  • Multi-hop queries combine multiple interdependent reasoning steps whose supporting facts are often distributed across fine-grained corpus evidence.
  • Coarse queries can cause retrieval interference, while overly fine queries may lose contextual constraints and over-decompose the reasoning chain.
  • Single retrieval, fixed Graph RAG, and unchecked iterative retrieval fail respectively through entangled constraints, query-agnostic granularity, and propagating unsupported intermediate queries.
  • Hi-Q tests whether retrieved evidence supports each query unit, expanding only unresolved nodes and resolving prerequisite sub-queries before dependent ones.
  • Hi-Q formulates multi-hop RAG as discovering the query unit at which each reasoning step becomes retrievable and answerable under the corpus.
  • Across three benchmarks, Hi-Q outperforms graph-based, iterative, and code-executing baselines under full-corpus retrieval, including a cheaper and more accurate cost-matched configuration.

2 Related Work

Prior approaches address query–evidence mismatch through flat retrieval, corpus-side structures, iterative reformulation, decomposition, or executable strategies. Hi-Q instead decides when refinement is needed against retrieved evidence and the current corpus.

  • Retrieval-Augmented Generation: Standard RAG issues the query as written against flat passages, working best when query and evidence share a granularity.
  • Graph RAG: Graph RAG pre-computes corpus-side structures before queries arrive, making granularity query-agnostic and incurring corpus-wide pre-computation cost.
  • Iterative Retrieval: Iterative retrieval adapts queries from intermediate findings but does not test whether each reformulation is retrievable, allowing early errors to propagate.
  • Query Decomposition: Decomposition methods generate sub-queries before observing evidence, whereas Hi-Q treats decomposition as a node-wise decision against retrieval feedback.
  • Agentic Execution and Learned Strategy Selection: Agentic execution changes retrieval orchestration by treating the corpus as a programmatically accessible environment or by learning a retrieval strategy.

3 Method

Hi-Q performs evidence-conditioned search over query granularity: it stops when a query unit is supported and recursively expands unresolved units through dependency-aware binary decomposition. Coverage checks, bounded recursion, and downstream costs constrain the resulting search.

  • Problem Formulation: Hi-Q first tests whether the current query unit is supported by retrieved evidence, expanding it into smaller dependency-aware sub-queries only when unresolved.
  • Problem Formulation: The resolution operator returns a resolution status, an answer when resolved, and retrieved evidence that becomes part of the node state.
  • Dependency-aware hierarchical query decomposition: Binary expansion resolves the prerequisite branch before the dependent branch, while retaining retrieved evidence and partial context even if the prerequisite remains unresolved.
  • Failure-aware, Evidence-guided Granularity Control: The STOP/EXPAND choice is a threshold on unresolved support that accounts for downstream retrieval, LLM calls, drift risk, synthesis, and answer loss.
  • Failure-aware, Evidence-guided Granularity Control: The method does not claim global optimality for the resulting query tree, and FAIL is handled separately as a budget or feasibility action.
  • Failure-aware, Evidence-guided Granularity Control: A training-free classifier uses the reader’s output to identify evidence-aligned nodes, while calibrated or trained controllers can replace it without changing control semantics.
  • Dependency-aware hierarchical query decomposition: The semantic coverage verifier checks that the split preserves the parent query’s intent without omission, drift, or reordered essential constraints, repairing inconsistent splits once.
  • Dependency-aware hierarchical query decomposition: Recursion stops at resolved nodes and is bounded for non-decomposable queries or maximum depth, after which available evidence supports final synthesis.

4 Experiments

Hi-Q is evaluated across three multi-hop QA benchmarks under full-corpus and controlled supporting/distractor retrieval, measuring both answer accuracy and evidence acquisition. It consistently outperforms iterative, graph-based, and agentic baselines, while targeted analyses examine retrieval recovery, signal robustness, component contributions, reasoning depth, and efficiency.

  • Main results: Hi-Q reaches 52.3 EM and 64.0 F1 averaged across full-corpus benchmarks, exceeding IRCoT by 15.1 EM / 18.2 F1.It also surpasses PropRAG by 11.5 EM / 12.0 F1 on MuSiQue-full and 9.9 EM / 12.1 F1 on 2Wiki-full.
  • Main results: Hi-Q achieves 57.9 EM and 69.3 F1 on average in the controlled supporting/distractor setting, ahead of PropRAG by 5.6 EM / 3.9 F1 and IRCoT by 13.7 EM / 15.8 F1.All reported improvements over IRCoT and PropRAG are significant across the controlled and full-corpus comparisons.
  • Main results: Hi-Q improves over coding-agent and Recursive Language Model baselines by 30.8 EM / 26.8 F1 and 24.4 EM / 26.7 F1, respectively.These comparisons use controlled adaptations standardized with the other baselines rather than reproductions of the original configurations.
  • Main results: Higher pooled retrieval recall does not ensure better answers: Self-Ask reaches 35.7 EM despite retrieving roughly 33% more documents per question than Hi-Q.Hi-Q targets query units whose retrieved evidence is also resolvable by the reader, rather than maximizing retrieval volume.
  • Retrieval analysis: On Clean triggered MuSiQue cases, Leaf@5 raises all-gold cover from 7.9% to 42.7%, while Leaf@all reaches 57.7% with 38.7% answer recovery.Most of the Leaf@all gain is achieved at the budget-matched Leaf@5 setting, indicating that decomposition surfaces passages root retrieval ranks poorly.
  • Ablations: Removing hierarchical refinement lowers performance from 57.9 EM / 69.3 F1 to 51.5 EM / 63.7 F1, while removing dependency awareness lowers it to 47.1 EM / 56.0 F1.Always-decompose also reduces performance from 60.7 EM / 70.8 F1 to 57.3 EM / 68.5 F1, and the verifier repairs 14.8–18.8% of triggered decompositions.
  • Reasoning depth: At three and four hops, Hi-Q reaches 55.2 and 39.2 F1, exceeding IRCoT’s 43.4 and 35.4 and PropRAG’s 43.1 and 26.9.All methods lose performance with increasing hop count, but Hi-Q retains higher F1 at each analyzed depth.
  • Efficiency: Hi-Q uses 70.5% fewer tokens than IRCoT but has 2.11× mean latency, 1.95× the LLM calls, and 7.54× the output tokens.Its recursive overhead is conditional because decomposition, verification, and descendant resolution run only for unresolved nodes.

5 Conclusion

Hi-Q treats query granularity as an evidence-conditioned control variable, expanding only unresolved nodes while preserving prerequisite-to-dependent ordering. This produces finite, depth-bounded hierarchical search without corpus-wide graph construction.

  • 5 Conclusion: Hi-Q improves multi-hop RAG by testing each query node against retrieved evidence and expanding only when support is insufficient.The framework grows a query tree online rather than applying a fixed decomposition template.
  • 5 Conclusion: Dependency-preserving refinement resolves prerequisite sub-queries before dependent ones, preventing unchecked intermediate queries from propagating.The procedure records each node’s evidence and answer status before branching, then invokes the right child after the left call returns.
  • 5 Conclusion: Across full-corpus and controlled settings, evidence-conditioned control improves answer accuracy over graph-based, iterative, and code-executing baselines.The method avoids corpus-wide knowledge graph construction while discovering the granularity at which reasoning steps become retrievable and answerable.
  • 5 Conclusion: Hi-Q’s recursive execution is finite and depth-bounded, with at most 2^dmax+1 − 1 visited nodes and dmax + 1 stack frames.At dmax = 4, the worst case permits 31 visited nodes, whereas the measured mean is 5.7 calls per question because most nodes resolve without expanding.

B Derivation of the STOP/EXPAND Threshold Rule

The STOP/EXPAND rule is derived as a state-dependent cost comparison conditioned on retrieved evidence. Its threshold reflects the relative cost-to-go of premature stopping and unnecessary expansion, while evidence-free routing is strictly disadvantaged when both states occur.

  • B Derivation of the STOP/EXPAND Threshold Rule: The decision state includes the query, history, depth, and retrieved evidence, with Z indicating whether the query is resolvable from that evidence.The posterior p(˜x) is the probability that the query is unresolved given the post-resolution state.
  • B Derivation of the STOP/EXPAND Threshold Rule: EXPAND incurs ΔR when the node is resolvable, whereas STOP incurs ΔU when it is unresolved; both are subtree cost-to-go penalties.These penalties include descendant retrieval and LLM calls, drift risk, synthesis, and terminal answer loss.
  • B Derivation of the STOP/EXPAND Threshold Rule: The expected cost of STOP is p(˜x)ΔU(˜x), and EXPAND is optimal when its conditional expected cost is no larger.The resulting threshold is state-dependent because both penalties vary with the node.
  • B Derivation of the STOP/EXPAND Threshold Rule: Evidence-conditioned routing strictly outperforms always-stop or always-expand whenever unresolved and resolvable states each occur with positive probability.A query-only policy cannot distinguish identical query states paired with different retrieved evidence, so it must disagree with the optimal evidence-conditioned action in at least one case.
  • B Derivation of the STOP/EXPAND Threshold Rule: Estimator disagreement with the optimal rule costs (ΔR + ΔU)|p − θ|, so errors near the threshold are cheaper than errors on clear-cut states.The a = ⊥ test is therefore interpreted as an estimator of a defined decision rather than a heuristic.

C A Learned and Calibrated STOP/EXPAND Policy

Hi-Q’s STOP/EXPAND interface can be implemented with a calibrated learned estimator, but replacing the training-free root policy adds cost without improving accuracy. The evidence-conditioned training-free policy is therefore retained.

  • Learned policy training: 3,060 labelled decision states from 817 training questions support training a logistic action head while freezing the LLM, retriever, and encoder.Model selection, calibration, and testing use disjoint sets of 200, 400, and 1,000 questions.
  • Calibration: 0.111 to 0.082 expected calibration error after Platt calibration shows that the action head’s probabilities are usable for threshold routing.Decision regret also decreases by 0.024, with 95% CI [0.005, 0.047].
  • Policy comparison: 0.30 EM and 1.40 EM losses from learned root policies are not statistically significant, while LLM calls rise from 7.63 to 10.41 or 8.64 per question.The comparison replaces only the root STOP/EXPAND rule and reruns all 1,000 test questions.
  • Policy comparison: The learned estimator neither improves accuracy nor lowers cost, so Hi-Q retains the training-free configuration as a root-level instantiation rather than a recursive learned replacement.The paper does not claim that the trained head computes the posterior of the underlying decision.
  • Related routing baseline: 959 of 1,000 questions are routed to multi-step retrieval by Adaptive-RAG, while an always-multi-step control scores higher, leaving learned routing no advantage over a constant policy.This comparison uses MuSiQue-full with a shared Qwen3.6-27B reader and retrieval stack and is not comparable with Tables 1 and 2.

F Robustness across Reader Backbones

Hi-Q’s QA gains persist across reader architectures rather than depending on one reader backbone. It remains the best average performer with both an independent dense reader and a mixture-of-experts reader.

  • Reader robustness: 60.2 EM / 71.2 F1 with Llama-3.3-70B and 58.3 EM / 68.9 F1 with Qwen3-30B-A3B are Hi-Q’s average QA results across two additional readers.The evaluation spans readers with different architectures.
  • Reader robustness: +3.6 EM with Llama-3.3-70B and +11.0 EM with Qwen3-30B-A3B accompany Hi-Q’s superiority over iterative/decomposition baselines.These are reported gains under the additional-reader evaluations.
  • Table conventions: Tables 11 and 12 report the best value in each column in bold and identify reproduced results with an asterisk.Table 11 uses Llama-3.3-70B; Table 12 uses Qwen3-30B-A3B.

G Robustness to Embedding Models

Hi-Q’s retrieval improvements persist across three embedding backbones, indicating that its gains are not tied to a single encoder. NV-Embed-v2 provides the strongest overall recall and is used as the default encoder.

  • Embedding robustness: 11.8, 14.3, and 8.2 Recall@5-point improvements over dense retrieval alone occur with text-embedding-3-large, Qwen3-Embedding-8B, and NV-Embed-v2, respectively.The comparison averages Recall@5 across the three retrievers.
  • Embedding robustness: NV-Embed-v2 gives the strongest overall recall, motivating its use as Hi-Q’s default encoder.Table 13 reports average Recall@5 across embedding models.

H Trigger Rate and Round-trip Repair Statistics

Hi-Q decomposes more often on benchmarks with greater query–evidence granularity mismatch, and its verifier repairs a substantial fraction of triggered decompositions.

  • Trigger rates: 10.7% of HotpotQA questions trigger decomposition, compared with 45.2% for MuSiQue and 48.6% for 2WikiMHQA.The lower HotpotQA rate is consistent with greater shortcut availability and a relatively simpler reasoning structure.
  • Round-trip repair: 14.8–18.8% of triggered cases receive round-trip repair, showing that verification actively corrects imperfect decompositions.Repair occurs across the recursive calls reported in the statistics.
  • Table overview: Table 14 reports decomposition trigger rate and round-trip repair frequency across datasets.The table organizes both statistics by benchmark.

I Strict Evidence-grounded Evaluation

The evaluation tests whether Hi-Q’s gains persist under stricter grounding, against dedicated decomposition baselines, and across multiple root decompositions. Results support robustness against parametric memorization, while showing that additional decomposition candidates provide only modest gains at rising cost.

  • Strict Evidence-grounded Evaluation: 13.1 EM / 21.7 F1 on MuSiQue, 23.1 EM / 28.8 F1 on 2Wiki, and 29.4 EM / 39.7 F1 on HotpotQA are the closed-book GPT-4o-mini scores, substantially below Hi-Q.This control tests whether Hi-Q’s performance can be explained by parametric knowledge without retrieval.
  • Strict Evidence-grounded Evaluation: GPT-5 reaches 25.0 EM / 37.6 F1 on MuSiQue versus GPT-4o-mini’s 13.1 EM / 21.7 F1, motivating a fixed reader for retrieval-alignment comparisons.The stronger backbone may supply bridge entities that were never retrieved.
  • Strict Evidence-grounded Evaluation: 29.3 Answer Recall exceeds TRQA’s 26.8 and the prompt-based baselines Least-to-Most’s 13.4 and Self-Ask’s 15.6 under TRQA’s reported setting.The comparison uses GPT-3.5-Turbo, ColBERTv2, MuSiQue-full, and Answer Recall for standardization.
  • Strict Evidence-grounded Evaluation: Accuracy increases monotonically but modestly as root-decomposition candidates increase, while token cost grows close to linearly in k.Independent candidates can run in parallel, so wall-clock latency need not increase proportionally.

L Binary Decomposition under High Arity

Hi-Q’s binary expansion is an execution primitive whose controller determines when nodes terminate or expand, rather than an assumption that every question has a linear chain. Controlled evaluations show strong performance as arity rises, while flat aggregation is substantially worse.

  • Binary Decomposition under High Arity: Binary expansion organizes m leaf information needs as at most m −1 binary reductions, while the controller terminates nodes already resolvable from retrieved passages.The experiment constructs controlled questions with m = 2, 3, 4, 5 and holds gold passage density at 25%.
  • Binary Decomposition under High Arity: 95.0 to 99.0 EM is maintained as arity rises from 2 to 5, with a loss of 0.80 EM per additional branch.Generated decompositions are statistically indistinguishable from the binary oracle-plan control, with −1.50 EM and 95% CI [−3.50, +0.50].
  • Binary Decomposition under High Arity: 27.50 EM is lost by flat N-ary aggregation compared with sequential binary reduction, scoring 71.0 versus 98.5 overall.Both variants receive the gold plan and identical retrieval and per-branch reading; the difference is the final combination step.
  • Binary Decomposition under High Arity: Binary Hi-Q’s measured trade-off is additional sequential cost rather than an observed high-arity accuracy failure.Variable-arity branching provides no significant mean-EM improvement over binary decomposition, although it reduces latency.
  • Binary Decomposition under High Arity: 85.5 EM is achieved on 235 comparison questions in 2Wiki using two branches followed by synthesis.Each resolved value is written to H before the dependent branch runs.

N Limitations

Hi-Q is evaluated within a specific QA regime and depends on reliable language-model components and sequentially resolvable dependencies. Its appendix operationalizes refinement through resolution, binary expansion, verification, and synthesis prompts.

  • N Limitations: The evaluation covers English, Wikipedia-derived, passage-based short-answer multi-hop QA and does not establish transfer beyond that setting.Mutually dependent prerequisites and branches requiring joint optimization are outside the modeled state representation.
  • N Limitations: Structured and multimodal QA require heterogeneous evidence representations and retrieval operators, while multilingual and domain-specific settings change language-access assumptions or corpus domain.These settings are not drop-in extensions of the evaluated passage-dependency setup.
  • N Limitations: Hi-Q depends on LLM reliability for resolution, decomposition, verification, and synthesis; false abstention can over-refine, while unsupported answers can stop refinement too early.The binary resolved/unresolved signal does not capture partial or conflicting evidence.
  • Operational Components: The resolution prompts decide whether the original or recursive query is answerable from retrieved evidence, while binary expansion proposes dependency-ordered sub-queries and verification checks intent preservation.Subquery refinement grounds implicit references in accumulated interaction history before retrieval.
Loading 2608.30468v1…