💻 computer science

Beyond the Largest Gap: Multi-Boundary Ranked-List Truncation for Multi-Hop Retrieval

The paper proposes GapR, a fast and effective multi-boundary ranked-list truncation method that improves multi-hop retrieval performance and downstream answer quality by identifying multiple informative score boundaries rather than relying on a single largest gap, thereby balancing evidence coverage with computational efficiency.

Original authors: Yanbo Liu

Published 2026-09-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yanbo Liu

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the modern digital age, artificial intelligence systems often act as powerful engines for answering complex questions, but they are not omniscient. To function accurately, these systems frequently rely on a process called retrieval-augmented generation. Imagine a student taking an open-book exam: the student (the AI) has access to a vast library of documents (the internet or a database) and must find the specific pages needed to construct a correct answer. The system first searches for relevant documents, ranks them by how well they seem to match the question, and then feeds the top results into a language model to generate a response. The critical challenge lies in deciding how many of those search results to actually read. If the system reads too few, it might miss a crucial fact needed to solve a puzzle. If it reads too many, it wastes time and energy processing irrelevant information, which can sometimes confuse the final answer. This balancing act becomes particularly difficult when a question requires "multi-hop" reasoning, where the answer is not found in a single document but is hidden across several different pieces of text that must be connected like links in a chain.

For years, researchers have tried to solve this by creating smart rules that automatically decide where to stop reading the list of search results. The most common approach has been to look for the biggest drop in confidence scores between one document and the next. The logic was simple: if the score for a document is high and the next one is suddenly much lower, that big gap likely marks the end of the useful information. However, a new study by Yanbo Liu at Hubei University suggests this traditional method is fundamentally flawed for complex questions. The research demonstrates that in multi-hop scenarios, the largest drop in confidence often occurs in the middle of the necessary evidence, not at the end. Consequently, systems relying on this single gap frequently stop reading too early, cutting off vital information that appears later in the list with lower scores but is essential for the final answer.

To address this systematic failure, the author developed a new method called GapR. Instead of looking for just one dramatic drop in scores, GapR scans the entire list of search results to identify multiple significant changes in confidence. It acts like a careful editor who knows that a story might have several important turning points. The method filters out tiny, insignificant fluctuations in the scores that might just be noise, but it keeps track of several distinct boundaries where the relevance of the documents changes. Crucially, it does not stop at the first or largest gap it finds. Instead, it looks at all the significant gaps it has identified and chooses the one that appears furthest down the list. This strategy ensures that the system retains later documents that might contain "bridge" facts—pieces of information that connect earlier findings to the final answer—even if those documents have lower initial scores. By preserving these later pieces of evidence, the method aims to provide the AI with a more complete picture without blindly including every single document in the database.

The researchers tested this approach on three major datasets designed for complex, multi-step questions: HotpotQA, 2WikiMultiHopQA, and MuSiQue. They compared GapR against standard fixed-length methods, which always read the same number of documents, and against other adaptive methods that try to guess the stopping point. The results showed that GapR consistently outperformed these alternatives. Under similar conditions where the amount of information read was roughly the same, GapR achieved significantly better results in finding the correct evidence. It successfully located more of the necessary facts required to answer the questions, particularly in cases where the evidence was scattered across different documents. The study found that in many instances, the traditional method of stopping at the largest gap would have missed the final piece of the puzzle, whereas GapR's multi-boundary approach captured it.

Beyond simply finding more correct answers, the new method proved to be remarkably efficient. While other advanced techniques that try to adapt to each question often require heavy computational power and take milliseconds to make a decision, GapR operates with incredible speed. The study measured the time it takes to decide where to stop reading and found that GapR requires only 15 to 24 microseconds per question. This is more than a thousand times faster than some of the more complex adaptive methods currently in use. This speed is vital for real-world applications where systems must handle thousands of questions per second without slowing down. The research confirms that by changing how the system interprets the list of search results—looking for multiple boundaries rather than just one—the quality of the information retrieved can be improved without sacrificing the speed needed for practical use.

The implications of these findings extend to the reliability of AI systems in high-stakes environments. When an AI is asked to solve a problem that requires connecting multiple facts, the difference between a correct answer and a hallucinated one often depends on whether it has seen the final, crucial document. The study shows that the old assumption—that the biggest drop in confidence signals the end of the story—is often wrong. By adopting a more nuanced view that acknowledges multiple potential stopping points, systems can avoid the trap of premature truncation. The experiments further confirmed that this improved retrieval of evidence translates into better final answers when fed into large language models, although the exact improvement depends on the specific model used. Ultimately, the work provides a practical, lightweight solution that allows AI systems to be both smarter and faster, ensuring they read just enough to get the job done right.

Technical Summary: Beyond the Largest Gap: Multi-Boundary Ranked-List Truncation for Multi-Hop Retrieval

1. Problem Statement

In Retrieval-Augmented Generation (RAG), particularly for multi-hop question answering (QA), determining the optimal length of the retrieved context is a critical challenge. The standard Fixed Top-K strategy is inflexible: a small $K$ risks truncating necessary evidence, while a large $K$ introduces computational costs and distracting noise.

Existing adaptive truncation methods typically rely on a single-boundary assumption, identifying the end of useful evidence by locating the largest drop (gap) in the ranked retrieval scores. The paper argues this assumption is fundamentally flawed for multi-hop retrieval because:

Relevance $\neq$ Utility: Retrieval scores reflect query-document matching, but "bridge" or "later-hop" evidence (essential for reasoning but not directly mentioned in the query) often receives lower scores.
Premature Truncation: The largest score gap frequently occurs within a complete evidence chain rather than after it. Consequently, single-gap methods often truncate critical bridge evidence that appears later in the ranked list with lower scores.
Insufficiency of Scores: The author formally proves (Proposition 1) that without additional assumptions, the ranked score sequence alone is not a sufficient statistic to identify the position of the final necessary evidence, as different evidence distributions can produce identical score sequences.

Empirical analysis across HotpotQA, 2WikiMultiHopQA, and MuSiQue confirms that even when all gold evidence is within the Top-30, 31%–55% of queries still contain gold evidence after the largest score gap.

2. Methodology: GapR

To address the limitations of single-boundary truncation, the author proposes GapR, a training-free, score-only method for query-adaptive ranked-list truncation. GapR replaces the single stopping signal with a multi-boundary aggregation strategy.

Core Components

Query-Relative Gap Filtering:
- Instead of using a global absolute threshold (which fails due to score scale variations across queries), GapR uses the largest gap in the current query ( $g_{max}$ ) as an internal reference.
- It filters candidate boundaries $V_q$ by retaining only those gaps $g_i$ that satisfy $g_i \ge \eta \cdot g_{max}$ , where $\eta$ is a relative filtering ratio (e.g., 0.05). This suppresses weak noise in the tail while preserving significant structural drops.
Multi-Boundary Aggregation:
- GapR selects the top- $r$ strongest candidate boundaries from the filtered set $V_q$ .
- The final truncation point $K_q$ is set to the latest (farthest) boundary among these selected candidates, subject to global bounds $[K_{min}, K_{max}]$ .
- Logic: If an early strong gap exists but a subsequent strong gap also exists, the method extends the context to the later gap, thereby preserving dispersed multi-hop evidence that a single-gap method would miss.

Algorithmic Complexity

GapR operates directly on the existing ranked score structure. It requires no training data, gold labels, generator feedback, or additional model calls.

Time Complexity: $O(L \log r)$ or effectively linear $O(L)$ for constant $r$ , where $L$ is the search prefix length.
Latency: The decision process takes only 15–24 microseconds per query.

3. Key Contributions

Structural Diagnosis: The paper identifies and formalizes the failure mode of largest-gap-based truncation in multi-hop retrieval, demonstrating that the strongest score discontinuity frequently precedes the final necessary evidence.
Multi-Boundary Formulation: GapR introduces a structured view of ranked-list score transitions, using query-relative filtering and multi-boundary aggregation to balance evidence coverage with context expansion.
Simultaneous Efficiency and Effectiveness: The method achieves significant retrieval performance gains over cost-matched baselines while maintaining microsecond-level decision latency, making it suitable for high-throughput, low-latency RAG systems.

4. Experimental Results

Experiments were conducted on HotpotQA, 2WikiMultiHopQA, and MuSiQue using Dense, Hybrid, and Sparse rankers.

Retrieval Effectiveness (RQ1)

Performance: Under comparable context budgets, GapR significantly outperforms Fixed Top-K and AdaptiveK+5 (which adds a fixed buffer to the largest gap) across all datasets and rankers.
Metrics: GapR improves Macro-F1 by 3.29, 3.14, and 2.53 percentage points over Fixed Top-K on the three datasets, respectively. It also consistently outperforms AdaptiveK+5.
Mechanism: The gains are attributed to better query-level budget allocation (reducing premature truncation) rather than simply increasing context size. GapR reduces "under-truncation" (missing evidence) more effectively than baselines without significantly increasing "over-truncation" (redundant content).

Efficiency (RQ3)

Latency: GapR requires 15–24 µs per query for the cutoff decision.
Comparison: This is three orders of magnitude faster than computationally heavier adaptive methods like Surprise (~~47 ms) and TAA-k (~~166 ms).

Downstream Generation (RQ4)

Using Qwen3-8B and DeepSeek-V3.2, improved context allocation led to an overall positive trend in answer quality (Answer F1).
On MuSiQue, GapR exceeded AdaptiveK with both generators. The average gain over cost-matched Fixed Top-K was modest but positive (0.44 points), though results varied by generator: Qwen improved by 1.39 points while DeepSeek improved by 1.64 points on HotpotQA. On MuSiQue, DeepSeek showed a gain of +0.38 points relative to AdaptiveK.

Robustness

GapR's advantages persist across Dense, Hybrid, and Sparse rankers. The method is robust to the choice of ranker, though its ceiling is constrained by the upstream retriever's ability to recall gold evidence (reachability).

5. Significance and Claims

The paper claims that GapR provides a practical, adaptive context truncation solution that resolves the tension between evidence coverage and computational efficiency in multi-hop RAG.

Practical Deployment: By operating in microseconds and requiring no additional models or training, GapR is positioned as a drop-in replacement for existing RAG pipelines, particularly for high-throughput systems where latency is critical.
Theoretical Insight: The work challenges the prevailing assumption that a single score gap defines the end of evidence, proposing instead that multi-hop evidence is often distributed across multiple salient boundaries in the ranked list.
Modest Scope: The author acknowledges that GapR is a prefix truncator and cannot recover evidence missed by the upstream retriever or rerank results. The evaluation is limited to multi-hop QA, and the generation benefits are described as "overall positive" rather than a universal guarantee, as downstream performance depends on the generator's ability to integrate the retrieved facts.

In summary, GapR demonstrates that multi-boundary truncation is a superior strategy for multi-hop retrieval, offering a favorable balance of retrieval quality and runtime efficiency without the overhead of complex adaptive mechanisms.