SpecHop : Continuous Speculation for Accelerating Multi-Hop Retrieval Agents

Mehrdad Saberi, Keivan Rezaei, Soheil Feizi · 2026

Read SpecHop : Continuous Speculation for Accelerating Multi-Hop Retrieval Agents by Mehrdad Saberi, Keivan Rezaei, Soheil Feizi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21965.txt.

Introduction

Mehrdad Saberi, Keivan Rezaei, and Soheil Feizi present SpecHop, a method that speeds up multi-hop retrieval agents by speculating continuously. Such agents wait for tool outputs at each hop, so latency piles up, even though a faster model could guess the next steps. SpecHop runs speculative branches in parallel, committing correct ones as target tool outputs arrive and rolling back wrong ones, preserving accuracy. On retrieval-augmented multi-hop tasks it nears oracle latency gains and cuts latency by up to 40 percent in some settings.

Catalog record

CREATORMehrdad Saberi, Keivan Rezaei, Soheil Feizi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74467
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.21965

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

SpecHop : Continuous Speculation for Accelerating Multi-Hop Retrieval Agents Mehrdad Saberi, Keivan Rezaei, Soheil Feizi Abstract Large language models increasingly use external tools such as web search and document retrieval to solve information-intensive tasks. However, multi-hop tool use in complex tasks introduces substantial latency, since the model must repeatedly wait for tool observations before continuing. We study how to accelerate such trajectories without changing the final trajectory the model would have taken without acceleration, assuming access to faster but less reliable speculator tools. We develop a theoretical framework for lossless speculation in multi-hop tool-use settings, characterizing the optimal achievable latency gain. We propose SpecHop , a continuous speculation framework that maintains multiple speculative threads, verifies predicted observations asynchronously as target tool outputs arrive, commits correct branches, and rolls back incorrect ones. This preserves accuracy while reducing wall-clock latency. We show that SpecHop can approach oracle latency gains with enough active threads. Empirically, on retrieval-augmented multi-hop tasks, SpecHop closely matches theoretical predictions and reduces latency by up to 40% in some settings. 1 Introduction Large language models (LLMs) are increasingly equipped with external tools, including web search, document retrieval, code execution environments, and APIs [ 15 , 34 , 12 , 3 , 1 ] . This enables more complex tasks, such as deep research, agentic workflows, interactive decision making, and information-intensive reasoning that requires interaction with external environments [ 25 , 24 , 11 , 4 , 29 ] . In these settings, the model’s trajectory is no longer a single forward generation, but a multi-step process of reasoning, tool calls, observations, and further reasoning. In this work, we focus on information-gathering tools, such as web search and database retrieval [ 33 , 6 , 23 , 26 ] . Enabling language models to call external tools improves performance, but also introduces substantial execution latency [ 35 , 20 ] . Because inference trajectories are sequential, the model may reason, wait for a web search result, reason again, retrieve documents from a database, and continue this process over multiple hops. Thus, total latency depends not only on model decoding, but also on external tool calls. Recent profiling studies show that this bottleneck is significant in practice: in deep-research agents, web search can account for 73% of end-to-end latency on average for GPT-5, and up to 91% in more complex cases [ 13 ] . In this work, we accelerate such multi-hop tool-use trajectories without changing the trajectory the model would have taken without acceleration. 35 propose Speculative Actions , which assume access to a speculator that predicts a tool call return with non-zero success probability p . They show that such speculators can predict target tool outcomes with lower latency in practice. Their method speculates one hop while the original tool call runs in parallel, then verifies the result to preserve accuracy and reduce latency when speculation succeeds. Building on this setup, we develop a theoretical framework for lossless speculation in multi-hop tool-use trajectories. We first study an oracle-verification setting, where speculative correctness is known immediately, yielding an upper bound on the latency improvement achievable by any lossless speculative method. Motivated by our theoretical analysis of such setup, we propose SpecHop , a continuous speculation framework that pushes toward the oracle latency gain. Rather than waiting idly for each target tool call to return, SpecHop keeps a speculative pipeline active throughout the trajectory. It maintains multiple parallel threads , each corresponding to a different speculative stage of the same underlying trajectory, and continues speculating future hops while previous target calls are still running. When a target output becomes available, a verifier checks whether the corresponding speculative observation is equivalent to the target observation. If verification succeeds, SpecHop commits the speculative branch and extends it with new speculative threads; if verification fails, it discards downstream speculative work and resumes from the last verified state (See Figure 1 ). Thus, SpecHop preserves the original trajectory under verification while reducing wall-clock latency. We theoretically study SpecHop and show that it can close the gap to the oracle latency gain while remaining lossless. We characterize the required number of active threads in terms of the speculator’s relative latency and the fraction of time spent on external tool calls. Empirically, we evaluate SpecHop on retrieval-augmented multi-hop QA tasks (2WikiMultihopQA [ 6 ] , MuSiQue [ 23 ] , and DeepResearch-9K [ 29 ] ) with web search or Wikipedia retrieval as the external tool, and either an LM-based speculator or a fast cache-based speculator. Across these settings, latency matches our theoretical predictions, with SpecHop preserving task accuracy while achieving up to 40\% latency gain over standard multi-hop execution. Figure 1: Overview of SpecHop with continuous speculative execution , maintaining k=3 active threads on a query requiring 4 external calls. Initially, \textsc{T}_{1} calls the target tool for (\mathbf{a}_{1},\mathbf{o}_{1}) . In parallel, \textsc{T}_{2} speculates the first observation as \hat{\mathbf{o}}_{1} and continues to the next hop, where it calls the target tool for (\mathbf{a}_{2},\mathbf{o}_{2}) ; \textsc{T}_{3} is created similarly. When \mathbf{o}_{1} returns, the verifier \mathcal{V} compares it with \hat{\mathbf{o}}_{1} . Since verification fails, \textsc{T}_{2} and its downstream speculative thread \textsc{T}_{3} are discarded, and the method resumes from the last verified thread. The system then creates new speculative threads \textsc{T}_{4} and \textsc{T}_{5} while \textsc{T}_{1} waits for the target output of (\mathbf{a}_{2},\mathbf{o}_{2}) . When \mathbf{o}_{2} returns, verification against \hat{\mathbf{o}}_{2} from \textsc{T}_{4} succeeds, so the system commits to \textsc{T}_{4} and continues speculation with \textsc{T}_{6} . Subsequent verifications also succeed: the system commits to \textsc{T}_{5} after \mathbf{o}_{3} returns, and once \mathbf{o}_{4} returns, \textsc{T}_{5} produces the final answer f . By keeping the pipeline active instead of waiting sequentially at each hop, SpecHop reduces wall-clock latency while preserving the original verified trajectory. 2 Related Work Speculative decoding. Autoregressive token generation in large language models can create memory-bandwidth bottlenecks during inference [ 8 , 30 ] . Speculative decoding mitigates this through a “draft-then-verify” paradigm, where a smaller draft model proposes tokens that are verified by a larger target model, yielding mathematically lossless outputs that match the target model distribution [ 2 , 8 ] . Recent work extends this idea with multiple drafters [ 10 ] , parallel speculative pipelines [ 37 ] , and draft/target models with different vocabulary spaces [ 21 ] . Our work shares the draft-then-verify philosophy, but speculates over tool observations rather than tokens. Foundations of speculative execution. Speculative execution originates in computer architecture, where it is used to overcome instruction-level bottlenecks and avoid stalls from conditional branches [ 19 ] . Branch-prediction methods estimate future control flow using history registers and execution patterns [ 36 ] , while speculative mechanisms execute predicted instructions before they are guaranteed to be needed, verify them once the true control flow is known, and roll back upon misprediction [ 18 , 22 ] . SpecHop adapts this classical systems principle from instruction-level execution to trajectory-level tool use in language model agents. Agentic tool use and retrieval-augmented generation. Equipping language models with external tools, especially retrieval [ 9 ] and search, has become central to retrieval-augmented generation and agentic frameworks [ 14 , 27 , 17 , 32 ] . Accelerating retrieval-augmented agents has recently been studied from several complementary angles. 28

Read the complete text