SpecHop: Continuous Speculation for Accelerating Multi-Hop Retrieval Agents

# SpecHop: Continuous Speculation for Accelerating Multi-Hop Retrieval Agents
Source: [https://arxiv.org/html/2605.21965](https://arxiv.org/html/2605.21965)
Mehrdad Saberi Keivan Rezaei11footnotemark:1Soheil Feizi University of Maryland, College Park \{msaberi, krezaei, sfeizi\}@umd\.eduProject:[https://github\.com/mehrdadsaberi/spechop](https://github.com/mehrdadsaberi/spechop)

###### 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 proposeSpecHop, 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 thatSpecHopcan approach oracle latency gains with enough active threads\. Empirically, on retrieval\-augmented multi\-hop tasks,SpecHopclosely matches theoretical predictions and reduces latency by up to 40% in some settings\.

## 1Introduction

Large language models \(LLMs\) are increasingly equipped with external tools, including web search, document retrieval, code execution environments, and APIs\[[15](https://arxiv.org/html/2605.21965#bib.bib26),[34](https://arxiv.org/html/2605.21965#bib.bib19),[12](https://arxiv.org/html/2605.21965#bib.bib31),[3](https://arxiv.org/html/2605.21965#bib.bib30),[1](https://arxiv.org/html/2605.21965#bib.bib29)\]\. 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](https://arxiv.org/html/2605.21965#bib.bib21),[24](https://arxiv.org/html/2605.21965#bib.bib20),[11](https://arxiv.org/html/2605.21965#bib.bib33),[4](https://arxiv.org/html/2605.21965#bib.bib34),[29](https://arxiv.org/html/2605.21965#bib.bib2)\]\. In these settings, the model’s trajectory is no longer a single forward generation, but amulti\-stepprocess 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](https://arxiv.org/html/2605.21965#bib.bib4),[6](https://arxiv.org/html/2605.21965#bib.bib36),[23](https://arxiv.org/html/2605.21965#bib.bib5),[26](https://arxiv.org/html/2605.21965#bib.bib37)\]\.

Enabling language models to call external tools improves performance, but also introduces substantial execution latency\[[35](https://arxiv.org/html/2605.21965#bib.bib1),[20](https://arxiv.org/html/2605.21965#bib.bib22)\]\. 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](https://arxiv.org/html/2605.21965#bib.bib35)\]\. In this work, we accelerate suchmulti\-hoptool\-use trajectories without changing the trajectory the model would have taken without acceleration\.

Yeet al\.\[[35](https://arxiv.org/html/2605.21965#bib.bib1)\]propose*Speculative Actions*, which assume access to a speculator that predicts a tool call return with non\-zero success probabilitypp\. 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 inmulti\-hoptool\-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 proposeSpecHop, a continuous speculation framework that pushes toward the oracle latency gain\. Rather than waiting idly for each target tool call to return,SpecHopkeepsa speculative pipeline active throughout the trajectory\. It maintainsmultiple parallel threads, each corresponding to a different speculative stage of the same underlying trajectory, andcontinues speculating future hopswhile 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,SpecHopcommits 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](https://arxiv.org/html/2605.21965#S1.F1)\)\. Thus,SpecHoppreserves the original trajectory under verification while reducing wall\-clock latency\.

We theoretically studySpecHopand 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 evaluateSpecHopon retrieval\-augmented multi\-hop QA tasks \(2WikiMultihopQA\[[6](https://arxiv.org/html/2605.21965#bib.bib36)\], MuSiQue\[[23](https://arxiv.org/html/2605.21965#bib.bib5)\], and DeepResearch\-9K\[[29](https://arxiv.org/html/2605.21965#bib.bib2)\]\) 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, withSpecHoppreserving task accuracy while achieving up to40%40\\%latency gain over standard multi\-hop execution\.

![Refer to caption](https://arxiv.org/html/2605.21965v1/x1.png)Figure 1:Overview ofSpecHopwithcontinuous speculative execution, maintainingk=3k=3active threads on a query requiring44external calls\. Initially,T1\\textsc\{T\}\_\{1\}calls the target tool for\(𝐚1,𝐨1\)\(\\mathbf\{a\}\_\{1\},\\mathbf\{o\}\_\{1\}\)\. In parallel,T2\\textsc\{T\}\_\{2\}speculates the first observation as𝐨^1\\hat\{\\mathbf\{o\}\}\_\{1\}and continues to the next hop, where it calls the target tool for\(𝐚2,𝐨2\)\(\\mathbf\{a\}\_\{2\},\\mathbf\{o\}\_\{2\}\);T3\\textsc\{T\}\_\{3\}is created similarly\. When𝐨1\\mathbf\{o\}\_\{1\}returns, the verifier𝒱\\mathcal\{V\}compares it with𝐨^1\\hat\{\\mathbf\{o\}\}\_\{1\}\. Since verification fails,T2\\textsc\{T\}\_\{2\}and its downstream speculative threadT3\\textsc\{T\}\_\{3\}are discarded, and the method resumes from the last verified thread\. The system then creates new speculative threadsT4\\textsc\{T\}\_\{4\}andT5\\textsc\{T\}\_\{5\}whileT1\\textsc\{T\}\_\{1\}waits for the target output of\(𝐚2,𝐨2\)\(\\mathbf\{a\}\_\{2\},\\mathbf\{o\}\_\{2\}\)\. When𝐨2\\mathbf\{o\}\_\{2\}returns, verification against𝐨^2\\hat\{\\mathbf\{o\}\}\_\{2\}fromT4\\textsc\{T\}\_\{4\}succeeds, so the system commits toT4\\textsc\{T\}\_\{4\}and continues speculation withT6\\textsc\{T\}\_\{6\}\. Subsequent verifications also succeed: the system commits toT5\\textsc\{T\}\_\{5\}after𝐨3\\mathbf\{o\}\_\{3\}returns, and once𝐨4\\mathbf\{o\}\_\{4\}returns,T5\\textsc\{T\}\_\{5\}produces the final answerff\. By keeping the pipeline active instead of waiting sequentially at each hop,SpecHopreduces wall\-clock latency while preserving the original verified trajectory\.
## 2Related Work

##### Speculative decoding\.

Autoregressive token generation in large language models can create memory\-bandwidth bottlenecks during inference\[[8](https://arxiv.org/html/2605.21965#bib.bib11),[30](https://arxiv.org/html/2605.21965#bib.bib13)\]\. 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](https://arxiv.org/html/2605.21965#bib.bib12),[8](https://arxiv.org/html/2605.21965#bib.bib11)\]\. Recent work extends this idea with multiple drafters\[[10](https://arxiv.org/html/2605.21965#bib.bib15)\], parallel speculative pipelines\[[37](https://arxiv.org/html/2605.21965#bib.bib14)\], and draft/target models with different vocabulary spaces\[[21](https://arxiv.org/html/2605.21965#bib.bib16)\]\. 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](https://arxiv.org/html/2605.21965#bib.bib6)\]\. Branch\-prediction methods estimate future control flow using history registers and execution patterns\[[36](https://arxiv.org/html/2605.21965#bib.bib8)\], 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](https://arxiv.org/html/2605.21965#bib.bib7),[22](https://arxiv.org/html/2605.21965#bib.bib9)\]\.SpecHopadapts 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](https://arxiv.org/html/2605.21965#bib.bib18)\]and search, has become central to retrieval\-augmented generation and agentic frameworks\[[14](https://arxiv.org/html/2605.21965#bib.bib24),[27](https://arxiv.org/html/2605.21965#bib.bib27),[17](https://arxiv.org/html/2605.21965#bib.bib25),[32](https://arxiv.org/html/2605.21965#bib.bib23)\]\. Accelerating retrieval\-augmented agents has recently been studied from several complementary angles\.Wanget al\.\[[28](https://arxiv.org/html/2605.21965#bib.bib17)\]focus on static retrieval at the beginning of the pipeline, using multiple speculative RAG models with different retrieved documents and later verifying with a larger generalist LLM to reduce latency without sacrificing accuracy\.Suiet al\.\[[20](https://arxiv.org/html/2605.21965#bib.bib22)\]propose anticipating tool\-call needs earlier by identifying patterns in the model’s generation, allowing the system to launch tools before the model explicitly reaches the tool\-call point\. Closest to our work,Yeet al\.\[[35](https://arxiv.org/html/2605.21965#bib.bib1)\]show that some external calls can be replaced by faster speculative models, providing empirical evidence that individual tool\-use hops can sometimes be accelerated through speculation\.

## 3Accelerating Multihop Tool\-Use Trajectories

Language models capable of tool use answer queries by invoking external tools when additional information or computation is needed\. They often decompose a query into intermediate steps, each resolved either from parametric knowledge or through tools such as web search, document retrieval, or databases of documents such as Wikipedia articles\. This behavior is common in settings studied by DeepResearch\[[29](https://arxiv.org/html/2605.21965#bib.bib2)\]and multihop question\-answering datasets\[[6](https://arxiv.org/html/2605.21965#bib.bib36),[23](https://arxiv.org/html/2605.21965#bib.bib5),[33](https://arxiv.org/html/2605.21965#bib.bib4)\]\. Given a queryqq, the modelℳ\\mathcal\{M\}follows an iterative tool\-augmented trajectory: it generates intermediate reasoning, calls tools, receives observations, updates its state, and repeats this process until producing the final answer\.

Formally, for a queryqq, the modelℳ\\mathcal\{M\}follows an inference trajectory over states𝐬0,𝐬1,…,𝐬N\\mathbf\{s\}\_\{0\},\\mathbf\{s\}\_\{1\},\\dots,\\mathbf\{s\}\_\{N\}, where𝐬0\\mathbf\{s\}\_\{0\}is induced by the query and𝐬N\\mathbf\{s\}\_\{N\}is terminal\. At each state𝐬i\\mathbf\{s\}\_\{i\}for0≤i<N0\\leq i<N, the model conditions on the prior context, generates an intermediate segment𝝉i\\boldsymbol\{\\tau\}\_\{i\}, and selects a tool action𝐚i\\mathbf\{a\}\_\{i\}\. The tool returns an observation𝐨i\\mathbf\{o\}\_\{i\}, which is added to the context to form the next state𝐬i\+1\\mathbf\{s\}\_\{i\+1\}\. From𝐬N\\mathbf\{s\}\_\{N\}, the model generates the final answerff\.

qq𝐬0\\mathbf\{s\}\_\{0\}⋯\\cdots𝐬i\\mathbf\{s\}\_\{i\}𝐬i\+1\\mathbf\{s\}\_\{i\+1\}⋯\\cdots𝐬N\\mathbf\{s\}\_\{N\}ff\(𝝉i,\(𝐚i,𝐨i\)\)\\left\(\\boldsymbol\{\\tau\}\_\{i\},\\left\(\\mathbf\{a\}\_\{i\},\\mathbf\{o\}\_\{i\}\\right\)\\right\)hop

Thus, the trajectory consists ofNNhops\. Because the model typically waits for each tool response before proceeding, inference latency includes both language\-model decoding time and external\-tool latency from web search, retrieval, code execution, or database queries\.

##### System latency\.

Processing a queryqqrequires the model to complete allNNhops: generating intermediate segments𝝉i\\boldsymbol\{\\tau\}\_\{i\}, selecting tool actions𝐚i\\mathbf\{a\}\_\{i\}, receiving observations𝐨i\\mathbf\{o\}\_\{i\}, and transitioning to the next state\. We model the wall\-clock time of each component as a random variable\. LetTsegT\_\{\\mathrm\{seg\}\}be the time to generate an intermediate segment, and letTtargetT\_\{\\mathrm\{target\}\}be the time for the target tool to return its result and for the model to consume the observation before continuing\. Thus, the latency of one sequential hop is

Thop=Tseg\+Ttarget\.T\_\{\\mathrm\{hop\}\}=T\_\{\\mathrm\{seg\}\}\+T\_\{\\mathrm\{target\}\}\.For a query requiringNNhops, the expected total time to reach the final state isN​𝔼​\[Thop\]N\\mathbb\{E\}\\left\[T\_\{\\mathrm\{hop\}\}\\right\]\.

### 3\.1Access to a Speculator Tool

Following\[[35](https://arxiv.org/html/2605.21965#bib.bib1)\], we assume access to a speculator tool that can replace the original target tool\. The speculator has two key properties\. First, unlike the target tool, the speculator is approximate: there is uncertainty about whether its returned observation is true\. Second, the speculator is faster than the target tool, and therefore can potentially reduce wall\-clock latency when its output is correct\.

##### Speculator accuracy\.

The speculator’s accuracy depends on the target tool and task\. FollowingYeet al\.\[[35](https://arxiv.org/html/2605.21965#bib.bib1)\], we model the speculator as succeeding at each hop with probabilityp\>0p\>0, where success means that the speculative observation leads the model to the same next state as the target\-tool observation\. This can occur when the needed factual information is already captured by an off\-the\-shelf model’s parametric knowledge, or is available in a smaller database or cache\. Prior work suggests such speculators can be useful in practice, achieving nontrivial success probabilities\.

##### Speculator latency\.

LetTspecT\_\{\\mathrm\{spec\}\}be the random variable denoting the latency of the speculator, including the time required to produce the speculative observation and enable the model to transition to the next state\. We assume that the speculator is more efficient than the target tool, i\.e\.,Tspec<TtargetT\_\{\\mathrm\{spec\}\}<T\_\{\\mathrm\{target\}\}\.

We make the following assumptions to leverage speculators while preserving the target\-tool trajectory\.

###### Assumption 1\(Fast approximate speculator\)

There exists a speculator𝒮\\mathcal\{S\}that can be used in place of the target tool𝒯\\mathcal\{T\}\. Given the same action𝐚i\\mathbf\{a\}\_\{i\}, the speculator produces a speculative observation𝐨^i=𝒮​\(𝐚i\)\\hat\{\\mathbf\{o\}\}\_\{i\}=\\mathcal\{S\}\(\\mathbf\{a\}\_\{i\}\)in timeTspec<TtargetT\_\{\\mathrm\{spec\}\}<T\_\{\\mathrm\{target\}\}\. With probabilityp\>0p\>0, this speculative observation induces the same next state as the target\-tool observation𝐨i=𝒯​\(𝐚i\)\.\\mathbf\{o\}\_\{i\}=\\mathcal\{T\}\(\\mathbf\{a\}\_\{i\}\)\.That is, with probabilitypp, we have

Update​\(𝐬i,𝝉i,𝐚i,𝐨^i\)=Update​\(𝐬i,𝝉i,𝐚i,𝐨i\)\.\\mathrm\{Update\}\(\\mathbf\{s\}\_\{i\},\\boldsymbol\{\\tau\}\_\{i\},\\mathbf\{a\}\_\{i\},\\hat\{\\mathbf\{o\}\}\_\{i\}\)=\\mathrm\{Update\}\(\\mathbf\{s\}\_\{i\},\\boldsymbol\{\\tau\}\_\{i\},\\mathbf\{a\}\_\{i\},\\mathbf\{o\}\_\{i\}\)\.

###### Assumption 2\(Verifiable equivalence\)

There exists a verifier𝒱\\mathcal\{V\}that can determine whether the speculative observation is equivalent to the target\-tool observation for the purpose of the model’s next state\. Formally, the verifier takes the current state, generated segment, action, speculative observation, and target observation, and returns

𝒱​\(𝐬i,𝝉i,𝐚i,𝐨^i,𝐨i\)∈\{0,1\}\.\\mathcal\{V\}\(\\mathbf\{s\}\_\{i\},\\boldsymbol\{\\tau\}\_\{i\},\\mathbf\{a\}\_\{i\},\\hat\{\\mathbf\{o\}\}\_\{i\},\\mathbf\{o\}\_\{i\}\)\\in\\\{0,1\\\}\.When𝒱​\(𝐬i,𝛕i,𝐚i,𝐨^i,𝐨i\)=1\\mathcal\{V\}\(\\mathbf\{s\}\_\{i\},\\boldsymbol\{\\tau\}\_\{i\},\\mathbf\{a\}\_\{i\},\\hat\{\\mathbf\{o\}\}\_\{i\},\\mathbf\{o\}\_\{i\}\)=1, the system is allowed to commit the speculative transition\. When the verifier returns0, the system has to discard the speculative branch\.

##### Verification in information retrieval\.

In information\-retrieval setups, verification can check whether the target tool and speculator provide the required information, e\.g\., the same factual knowledge or semantically equivalent evidence for the model’s inquiry\. A restrictive verifier lowers the success ratepp, while a looser verifier that ensures the speculative observation is sufficiently informative can preserve the trajectory to some extent and maintain task accuracy with higherpp\.

### 3\.2Leveraging Speculation for Fast and Accurate Trajectories

We parameterize the latency profile of the system using two dimensionless quantities\. First, we define the*relative speculator latency*α≜𝔼​\[Tspec\]/𝔼​\[Ttarget\]\\alpha\\triangleq\{\\mathbb\{E\}\\left\[T\_\{\\mathrm\{spec\}\}\\right\]\}/\\mathbb\{E\}\\left\[T\_\{\\mathrm\{target\}\}\\right\]\. Since the speculator is assumed to be faster than the target tool, we haveα<1\\alpha<1\. Second, we define the*decoding\-to\-tool latency ratio*β≜𝔼​\[Tseg\]/𝔼​\[Ttarget\]\\beta\\triangleq\\mathbb\{E\}\\left\[T\_\{\\mathrm\{seg\}\}\\right\]/\\mathbb\{E\}\\left\[T\_\{\\mathrm\{target\}\}\\right\]\. This quantity measures how much time is spent on model\-side segment generation relative to target\-tool execution\.

We first characterize the best theoretical latency gain achievable with the speculator𝒮\\mathcal\{S\}\. To do so, we analyze an idealized oracle\-verification setting that upper bounds the possible gain from speculation\.

###### Observation 1\(Oracle speculative hop latency\)

Assume an idealized oracle\-verification setting in which, at each hop, the system runs the speculator𝒮\\mathcal\{S\}and the target tool𝒯\\mathcal\{T\}in parallel\. As soon as the speculative observation is produced, an oracle verifier determines whether it would match the target\-tool result, without waiting for the target tool to finish\. If speculation succeeds, which happens with probabilitypp, the system proceeds using the speculative result; otherwise, it waits for and falls back to the target\-tool result\. Then the expected latency of a single hop is

𝔼​\[Thopspec\]=𝔼​\[Tseg\]\+p​𝔼​\[Tspec\]\+\(1−p\)​𝔼​\[Ttarget\]\.\\mathbb\{E\}\\left\[T\_\{\\mathrm\{hop\}\}^\{\\mathrm\{spec\}\}\\right\]=\\mathbb\{E\}\\left\[T\_\{\\mathrm\{seg\}\}\\right\]\+p\\ \\mathbb\{E\}\\left\[T\_\{\\mathrm\{spec\}\}\\right\]\+\(1\-p\)\\ \\mathbb\{E\}\\left\[T\_\{\\mathrm\{target\}\}\\right\]\.

###### Corollary 1\(Oracle relative latency\)

Under the setting of Observation[1](https://arxiv.org/html/2605.21965#Thmobservationth1), the relative latency of oracle speculation compared to sequential execution is

RelLat∗≜𝔼​\[Thopspec\]𝔼​\[Thop\]=𝔼​\[Tseg\]\+p​𝔼​\[Tspec\]\+\(1−p\)​𝔼​\[Ttarget\]𝔼​\[Tseg\]\+𝔼​\[Ttarget\]=1−p​\(1−α\)1\+β\.\\mathrm\{RelLat\}^\{\*\}\\triangleq\\frac\{\\mathbb\{E\}\\left\[T\_\{\\mathrm\{hop\}\}^\{\\mathrm\{spec\}\}\\right\]\}\{\\mathbb\{E\}\\left\[T\_\{\\mathrm\{hop\}\}\\right\]\}=\\frac\{\\mathbb\{E\}\\left\[T\_\{\\mathrm\{seg\}\}\\right\]\+p\\mathbb\{E\}\\left\[T\_\{\\mathrm\{spec\}\}\\right\]\+\(1\-p\)\\mathbb\{E\}\\left\[T\_\{\\mathrm\{target\}\}\\right\]\}\{\\mathbb\{E\}\\left\[T\_\{\\mathrm\{seg\}\}\\right\]\+\\mathbb\{E\}\\left\[T\_\{\\mathrm\{target\}\}\\right\]\}=1\-\\frac\{p\(1\-\\alpha\)\}\{1\+\\beta\}\.

Corollary[1](https://arxiv.org/html/2605.21965#Thmtheorem1)shows that latency gain depends on three quantities: the speculation success probabilitypp, relative speculator latencyα\\alpha, and decoding\-to\-tool latency ratioβ\\beta\. Gains increase with more accurate or cheaper speculation, and decrease when model decoding dominates tool execution\.

So far, we assumed an oracle verifier that immediately determines whether the target\-tool output induces the same next state as the speculator\. In practice, verification requires observing the target\-tool output and checking the speculative result\.SpecHopaddresses this issue through asynchronous verification while pushing speculation forward\.

### 3\.3SpecHopwith a Bounded Speculative Window

We describe an algorithm that maintains up tokkparallel threads, enabling speculation while verifying each speculative transition against the target tool\. Suppose the model is at state𝐬i\\mathbf\{s\}\_\{i\}\. It generates the segment𝝉i\\boldsymbol\{\\tau\}\_\{i\}and action𝐚i\\mathbf\{a\}\_\{i\}\. We create an original verifier threadT1\\textsc\{T\}\_\{1\}that calls the target tool on𝐚i\\mathbf\{a\}\_\{i\}\. In parallel, we invoke the speculator on the same action; using the speculative observation, the model transitions to a speculative next state and continues execution, creating a speculative continuationT2\\textsc\{T\}\_\{2\}\. Then,T2\\textsc\{T\}\_\{2\}generates the next segment and action, launches the target tool, and in parallel invokes the speculator again to createT3\\textsc\{T\}\_\{3\}\. This process repeats: each thread calls the target tool for its current action, while the next thread is created by speculating that action’s observation and continuing from the speculative state\. The system continues until it maintainskkactive threads, denoted byT1:k\\textsc\{T\}\_\{1\{:\}k\}\.

When the target tool result fromT1\\textsc\{T\}\_\{1\}returns, the verifier𝒱\\mathcal\{V\}compares it with the speculative observation used to createT2\\textsc\{T\}\_\{2\}\. If verification fails, then allT\(2:k\)\\textsc\{T\}\_\{\(2\{:\}k\)\}are discarded, and the system resumes the threadT1\\textsc\{T\}\_\{1\}for next hop at state𝐬i\+1\\mathbf\{s\}\_\{i\+1\}\. If verification succeeds, thenT1\\textsc\{T\}\_\{1\}is discarded andT\(2:k\)\\textsc\{T\}\_\{\(2\{:\}k\)\}remain valid continuations from the verified state\. The same procedure is then applied recursively: when the target\-tool result fromT2\\textsc\{T\}\_\{2\}returns, it is compared against the speculative observation used to createT3\\textsc\{T\}\_\{3\}\. If verified,T2\\textsc\{T\}\_\{2\}is discarded andT\(3:k\)\\textsc\{T\}\_\{\(3\{:\}k\)\}remain valid; otherwise, all threads are discarded and the system resumesT2\\textsc\{T\}\_\{2\}from the verified state𝐬i\+2\\mathbf\{s\}\_\{i\+2\}\. In general, the algorithm either verifies all speculative transitions and advances to𝐬i\+k\\mathbf\{s\}\_\{i\+k\}, or encounters the first failed verification at someTj\\textsc\{T\}\_\{j\}, discards all downstream threadsT\(j\+1:k\)\\textsc\{T\}\_\{\(j\+1\{:\}k\)\}, and resumes from the corresponding verified state𝐬i\+j\\mathbf\{s\}\_\{i\+j\}\.

Letℒk​\(N\)\\mathcal\{L\}\_\{k\}\(N\)denote the expected latency ofSpecHopwith window sizekkon a trajectory withNNremaining hops\. We characterize this latency in the following theorem\.

###### Theorem 2\(Expected runtime with a bounded speculative window\)

For a trajectory withNNremaining hops, supposeSpecHopuses a speculative window of sizekk, and each speculative hop succeeds independently with probabilitypp\. Then the expected wall\-clock latency satisfies

ℒk​\(N\)=N​\(𝔼​\[Tseg\]\+μk−1μk​𝔼​\[Tspec\]\+1μk​𝔼​\[Ttarget\]\)\+O​\(1\),\\displaystyle\\mathcal\{L\}\_\{k\}\(N\)=N\\left\(\\mathbb\{E\}\\left\[T\_\{\\mathrm\{seg\}\}\\right\]\+\\frac\{\\mu\_\{k\}\-1\}\{\\mu\_\{k\}\}\\mathbb\{E\}\\left\[T\_\{\\mathrm\{spec\}\}\\right\]\+\\frac\{1\}\{\\mu\_\{k\}\}\\mathbb\{E\}\\left\[T\_\{\\mathrm\{target\}\}\\right\]\\right\)\+O\(1\),whereμk=1−pk1−p\\mu\_\{k\}=\\frac\{1\-p^\{k\}\}\{1\-p\}is the expected number of hops advanced in one speculative round\.

###### Corollary 3\(Relative latency of bounded\-window speculation\)

Under the setting of Theorem[2](https://arxiv.org/html/2605.21965#Thmtheorem2), the relative latency ofSpecHopwith window sizekkis

RelLatk≜ℒk​\(N\)N​𝔼​\[Thop\]=β\+α\+\(1−α\)​\(1−p\)1−pk1\+β=1−\(1−α\)​\(1−1−p1−pk\)1\+β\+O​\(1N\)\.\\mathrm\{RelLat\}\_\{k\}\\triangleq\\frac\{\\mathcal\{L\}\_\{k\}\(N\)\}\{N\\ \\mathbb\{E\}\\left\[T\_\{\\mathrm\{hop\}\}\\right\]\}=\\frac\{\\beta\+\\alpha\+\\frac\{\(1\-\\alpha\)\(1\-p\)\}\{1\-p^\{k\}\}\}\{1\+\\beta\}=1\-\\frac\{\(1\-\\alpha\)\\left\(1\-\\frac\{1\-p\}\{1\-p^\{k\}\}\\right\)\}\{1\+\\beta\}\+O\\left\(\\frac\{1\}\{N\}\\right\)\.

As shown in Corollary[3](https://arxiv.org/html/2605.21965#Thmtheorem3),SpecHopapproaches the ideal oracle performance ask→∞k\\to\\inftywhenNNis sufficiently large\. In particular,limk→∞RelLatk=RelLat∗\.\\lim\_\{k\\to\\infty\}\\mathrm\{RelLat\}\_\{k\}=\\mathrm\{RelLat\}^\{\*\}\.See Appendix[B\.1](https://arxiv.org/html/2605.21965#A2.SS1)for the proof\.

Algorithm 1SpecHop: Continuous Speculative Execution withkkActive Threads1:query

qq, model

ℳ\\mathcal\{M\}, target tool

𝒯\\mathcal\{T\}, speculator

𝒮\\mathcal\{S\}, verifier

𝒱\\mathcal\{V\}, window size

kk
2:Final answer

ff
3:

T1←Init​\(M,q\)\\textsc\{T\}\_\{1\}\\leftarrow\\mathrm\{Init\}\(M,q\)
4:

𝒲←\{T1\}\\mathcal\{W\}\\leftarrow\\\{\\textsc\{T\}\_\{1\}\\\}⊳\\trianglerightInitialize with the first thread

5:whiletruedo

6:if

\|𝒲\|<k\|\\mathcal\{W\}\|<kthen⊳\\trianglerightExtend the speculative window

7:Extend the last thread in

𝒲\\mathcal\{W\}by one hop using model

ℳ\\mathcal\{M\}and the speculator

𝒮\\mathcal\{S\}
8:Launch the corresponding target\-tool call

𝒯\\mathcal\{T\}asynchronously

9:endif

10:⊳\\trianglerightVerify speculation with target\-tool observations

11:ifthe earliest target\-tool call in

𝒲\\mathcal\{W\}has returnedthen

12:Verify its result against the corresponding speculative observation using

𝒱\\mathcal\{V\}
13:ifverification succeedsthen

14:Commit the earliest speculative hop and shift

𝒲\\mathcal\{W\}forward

15:else

16:Roll back to the verified thread with target\-tool called

17:

𝒲←\{Tverified\}\\mathcal\{W\}\\leftarrow\\\{\\textsc\{T\}\_\{\\mathrm\{verified\}\}\\\}⊳\\trianglerightKeep the verified thread

18:endif

19:endif

20:ifthe verified trajectory reaches a final answerthen

21:return

ff
22:endif

23:endwhile

### 3\.4SpecHopwith Continuous Speculation but Bounded Active Threads

Motivated by Corollary[3](https://arxiv.org/html/2605.21965#Thmtheorem3), we introduce a continuous version ofSpecHopthat avoids the stop\-and\-wait bottleneck of a fixed speculative window\. We first describe a variant that maintainskkactive threads throughout execution, and then discuss how to choosekkto approximate thek→∞k\\to\\inftybehavior\. In the bounded\-window version, the system creates up tokkthreads and then waits for verification before deciding which speculative trajectory to retain\. When speculation is consistently successful, this can still create a bottleneck: once the window is exhausted, the system may wait for the target\-tool output of the last thread before creating further speculative continuations\.

The continuous version avoids this by keepingkkactive threads at all times\. Whenever the earliest unresolved speculation is verified, the corresponding verifier thread is discarded, the window shifts forward, and the system immediately extends the frontier by speculating from the last active thread\. If verification fails, all downstream speculative threads are discarded and execution resumes from the verified target\-tool state\. Thus, as long as speculation remains valid, the system keeps speculating ahead rather than stopping at the end of a finite window\. Algorithm[1](https://arxiv.org/html/2605.21965#alg1)gives an abstract implementation, with full implementation\-level pseudocode in Appendix[2](https://arxiv.org/html/2605.21965#alg2)\.

##### SelectingkkforSpecHopwith continuous speculation\.

The continuous version ofSpecHopdoes not need an unbounded number of active threads to emulate thek→∞k\\to\\inftybehavior\. The key observation is that a new speculative thread is only useful if it can be created before the earliest unresolved target\-tool call returns\. Otherwise, the system would already have verified the earliest speculation and shifted the window forward\. To provide theoretical insight into how many active threads are required, we letν\\nudenote the maximum coefficient of variation of the system, defined such that for any latency variableX∈\{Tseg,Tspec,Ttarget\}X\\in\\\{T\_\{\\mathrm\{seg\}\},T\_\{\\mathrm\{spec\}\},T\_\{\\mathrm\{target\}\}\\\}, its standard deviation is bounded by its expectation:std​\(X\)≤ν​𝔼​\[X\]\.\\mathrm\{std\}\(X\)\\leq\\nu\\mathbb\{E\}\\left\[X\\right\]\.

###### Theorem 4\(Probability ofSpecHopwithkkactive threads starves\)

Under a CLT approximation, forSpecHopwithkkactive speculative threads, the probability that the pipeline starves before the target tool resolves is bounded using the standard normal CDFΦ\\Phi:

Pstarve​\(k\)≤Φ​\(\(1\+β\)−k​\(α\+β\)ν​k​α2\+\(k−1\)​β2\+1\)P\_\{\\text\{starve\}\}\(k\)\\leq\\Phi\\left\(\\frac\{\(1\+\\beta\)\-k\(\\alpha\+\\beta\)\}\{\\nu\\sqrt\{k\\alpha^\{2\}\+\(k\-1\)\\beta^\{2\}\+1\}\}\\right\)

According to Theorem[4](https://arxiv.org/html/2605.21965#Thmtheorem4)\(see Appendix[B\.2](https://arxiv.org/html/2605.21965#A2.SS2)for proof and details\), choosingk⋆=⌈\(1\+β\)/\(α\+β\)⌉k^\{\\star\}=\\left\\lceil\{\(1\+\\beta\)\}/\{\(\\alpha\+\\beta\)\}\\right\\rceilensuresPstarve≤0\.5P\_\{\\text\{starve\}\}\\leq 0\.5\. To illustrate what a reliable choice ofkklooks like in practice, we consider two representative settings motivated by our empirical measurements, aiming for a starvation probability below5%5\\%under the volatility boundν≤0\.4\\nu\\leq 0\.4\. Using Theorem[4](https://arxiv.org/html/2605.21965#Thmtheorem4), when\(α,β\)=\(0\.2,0\.15\)\(\\alpha,\\beta\)=\(0\.2,0\.15\), choosingk0\.05⋆=6k^\{\\star\}\_\{0\.05\}=6satisfies this goal; when\(α,β\)=\(0\.3,0\.75\)\(\\alpha,\\beta\)=\(0\.3,0\.75\), choosingk0\.05⋆=3k^\{\\star\}\_\{0\.05\}=3suffices\. Thus, near\-optimal latency can be achieved with a small number of threads in realistic stochastic settings\.

## 4Experiments

In this section, we empirically evaluateSpecHop\. We first describe the experimental setup in Section[4\.1](https://arxiv.org/html/2605.21965#S4.SS1)\. We then present our main results in Section[4\.2](https://arxiv.org/html/2605.21965#S4.SS2), showing thatSpecHopsubstantially reduces wall\-clock latency\. Additional analyses and ablations can be found in Appendix[C](https://arxiv.org/html/2605.21965#A3)\)\.

Table 1:Latency reduction achieved bySpecHop\. We report the empirical speculation success probability \(p^\\hat\{p\}\), relative speculator latency \(α^\\hat\{\\alpha\}\), and the decoding\-to\-tool latency ratio \(β^\\hat\{\\beta\}\)\.SpecHopconsistently achieves empirical relative latencies \(RelLat\\mathrm\{RelLat\}\) that closely approach the theoretical optimal \(RelLat^∗\\hat\{\\mathrm\{RelLat\}\}^\{\*\}\) across three datasets, two target tools \(𝒯\\mathcal\{T\}\), and various speculative models \(𝒮\\mathcal\{S\}\)\.### 4\.1Experimental Setup

##### Datasets\.

We evaluateSpecHopon three multi\-hop question\-answering datasets: 2WikiMultihopQA\[[6](https://arxiv.org/html/2605.21965#bib.bib36)\], MuSiQue\[[23](https://arxiv.org/html/2605.21965#bib.bib5)\], and DeepResearch\-9K\[[29](https://arxiv.org/html/2605.21965#bib.bib2)\]\. For 2WikiMultihopQA and MuSiQue, the per\-example hop budget is derived from their dataset attributes \(i\.e\., number of distinct Wikipedia titles appearing insupporting\_factsfor 2WikiMultihopQA, and length ofquestion\_decompositionfor MuSiQue\), ranging from 2 to 4 hops\. We allow our model the budget of 2 extra hops for each sample\. For DeepResearch\-9K we evaluate samples with difficulty 2 \(difficulty ranges from 1 to 3\), as they provide challenging tasks that need multiple hops of retrieval for answering, and are not too complex for models in our parameter range, and we allow fix budget of 10 hops for samples\.

##### Generator Model \(ℳ\\mathcal\{M\}\)\.

Our primary generator is CoRAG\-Llama3\.1\-8B\-MultihopQA\[[26](https://arxiv.org/html/2605.21965#bib.bib37)\], which is trained to generate intermediate sub\-questions hop\-by\-hop, making it a natural fit for continuous speculative execution\. Appendix[C\.1](https://arxiv.org/html/2605.21965#A3.SS1)also reports additional experiments with GPT\-5\[[16](https://arxiv.org/html/2605.21965#bib.bib41)\]asℳ\\mathcal\{M\}\.

##### Target Tool \(𝒯\\mathcal\{T\}\)\.

We evaluate two distinct retrieval backends as our target tools\. \(1\) E5 Retrieval: A local HTTP service querying a KILT/Wikipedia passage corpus, returning the top 5 nearest\-neighbor passages for each sub\-question \(2\) Web Search: A DuckDuckGo\-based web retrieval tool returning 5 search results per query, with a 3\-second page\-fetch timeout\.

##### Speculator \(𝒮\\mathcal\{S\}\) and verifer \(𝒱\\mathcal\{V\}\)

We mainly use LLMs as speculator, including Llama 3\.1 8B\[[5](https://arxiv.org/html/2605.21965#bib.bib39)\], Qwen 3 8B\[[31](https://arxiv.org/html/2605.21965#bib.bib38)\], GPT\-4o mini, and GPT\-4o\[[7](https://arxiv.org/html/2605.21965#bib.bib40)\]\. These models span different speed–accuracy trade\-offs, inducing distinct\(p,α\)\(p,\\alpha\)values\. SinceSpecHoponly requires a fast substitute for the target tool𝒯\\mathcal\{T\}, we also evaluate a cached retrieval backend as the speculator in Section[4\.2](https://arxiv.org/html/2605.21965#S4.SS2)\. We use a deterministic rule\-based verifier that compares the target\-tool sub\-answer with the speculative sub\-answer for each hop and decides whether to accept the speculation\. The verifier relies on normalization, exact match, and token\-set Jaccard similarity\. Appendix[D\.1](https://arxiv.org/html/2605.21965#A4.SS1)provides implementation details, and Appendix[C\.3](https://arxiv.org/html/2605.21965#A3.SS3)reports a human evaluation of its reliability\.

Table 2:End\-to\-end task performance \(EM/F1\) and absolute wall\-clock latency \(seconds\)\.SpecHoppreserves the accuracy of the standard trajectory \(which usesℳ\\mathcal\{M\}and𝒯\\mathcal\{T\}without𝒮\\mathcal\{S\}\), while substantially reducing execution time\. Here,𝒮\\mathcal\{S\}is Llama 3\.1 8B\. Full Speculation uses only the speculator for all hops without target\-tool verification, leading to severe accuracy degradation\.
##### Standard multi\-hop execution\.

Given an input question,ℳ\\mathcal\{M\}generates a sub\-question at each hop\. The target tool𝒯\\mathcal\{T\}retrieves top documents containing the answer to the sub\-question, andℳ\\mathcal\{M\}uses them to produce a sub\-answer\. The resulting \(sub\-question, sub\-answer\) pair is added to the context for generating the next sub\-question\. After the hop budget is reached,ℳ\\mathcal\{M\}uses the original question and allNN\(sub\-question, sub\-answer\) pairs to generate the final answer\.

Appendix[D\.1](https://arxiv.org/html/2605.21965#A4.SS1)contains more details on the experimental setup, including generation hyperparameters, specific target tool configurations, early stopping criteria, andSpecHopsimulation methodology\.

### 4\.2Results

![Refer to caption](https://arxiv.org/html/2605.21965v1/x2.png)Figure 2:The effect of active thread limit \(kk\) on relative latency \(RelLat\\mathrm\{RelLat\}\) and computational cost \(average number of calls to the target tool𝒯\\mathcal\{T\}, speculator𝒮\\mathcal\{S\}, and generator modelℳ\\mathcal\{M\}\)\. The evaluation setting uses GPT\-4o as the speculator \(𝒮\\mathcal\{S\}\) and Web Search as the target tool \(𝒯\\mathcal\{T\}\)\. The dashed line is the theoretical optimal relative latency \(RelLat∗\\mathrm\{RelLat\}^\{\*\}\)\. The “Standard” setting refers to not usingSpecHop\. Additional trade\-off results for other configurations are provided in Appendix \(Figure[4](https://arxiv.org/html/2605.21965#A3.F4)\)\.We run continuousSpecHopwithk→∞k\\rightarrow\\inftysetting, meaning that we do not impose a limit on the number of active threads\. The algorithm dynamically creates new threads until the first unresolved thread is verified, allowing speculative continuations to yield additional latency reduction\.

##### SpecHopachieves significant latency reduction across settings\.

We use hat notation \(e\.g\.,p^\\hat\{p\},α^\\hat\{\\alpha\},β^\\hat\{\\beta\}\) to denote empirical values measured in our experiments, distinguishing them from their theoretical counterparts\. As shown in Table[1](https://arxiv.org/html/2605.21965#S4.T1),SpecHopachieves latency gains that closely match the optimal theoretical limits \(RelLat∗\\mathrm\{RelLat\}^\{\*\}\) across three datasets, two target tools𝒯\\mathcal\{T\}, and diverse speculators𝒮\\mathcal\{S\}\. In the Web search setting, network\-bound fetching creates a large bottleneck, making local speculative generation much faster and yielding low relative speculator latency \(α^\\hat\{\\alpha\}\)\. GPT\-based speculators incur API overhead and thus have higherα^\\hat\{\\alpha\}than local Llama and Qwen models, but they achieve higher speculation success ratesp^\\hat\{p\}\. We omit GPT speculators for the E5 target tool as their API latency is not consistently lower than local E5 retrieval latency \(α^\>1\\hat\{\\alpha\}\>1\), violating faster speculator assumption\.

Overall,SpecHop’s empirical relative latency \(RelLat\\mathrm\{RelLat\}\) tightly approaches the optimal bounds\. For example, using GPT\-4o as the Web\-search speculator on 2WikiMultihopQA achievesRelLat=0\.60\\mathrm\{RelLat\}=0\.60, corresponding to a40%40\\%reduction in total execution time, close to its optimal limit of0\.500\.50\.

##### SpecHopfully preserves trajectory and answer quality\.

As detailed in Tables[2](https://arxiv.org/html/2605.21965#S4.T2),SpecHoptightly preserves the task accuracy and final answer quality of the standard sequential execution\. Across all datasets and speculator configurations, deviations in EM and F1 scores \(Exact Match and token F1 on SQuAD\-normalized answers\) are marginal\. By employing a strictly defined verifier \(𝒱\\mathcal\{V\}\),SpecHopensures that no unauthorized deviations occur in the multi\-hop trajectory\. This verification step keeps the system consistent\. Conversely, the “Full Speculation” approach, i\.e\., for all hops only the speculator is called, demonstrates the danger of unverified generation\. While this method is significantly faster \(particularly when bypassing an expensive𝒯\\mathcal\{T\}like Web Search\) it heavily degrades answer quality\. As shown in Table[2](https://arxiv.org/html/2605.21965#S4.T2), Full Speculation causes EM to plummet from 68\.7 to 38\.7 on 2WikiMultihopQA and nearly halves it from 10\.0 to 5\.7 on MuSiQue\.SpecHopeffectively eliminates this accuracy trade\-off, securing substantial speedups while maintaining reliability\.

##### SpecHopoffers a latency\-compute cost trade\-off viakk\.

Theorem[4](https://arxiv.org/html/2605.21965#Thmtheorem4)provides insights on how increasingkkresults in smaller chance of starvation\. However, maintaining a large number of active threads inherently increases the total number of parallel executions\. By restrictingSpecHopto smaller active threads, it provides a flexible trade\-off between maximizing latency reduction and controlling computational overhead\. Figure[2](https://arxiv.org/html/2605.21965#S4.F2)illustrates this dynamic for the continuousSpecHopframework, utilizing GPT\-4o as the speculator \(𝒮\\mathcal\{S\}\) and Web Search as the target tool \(𝒯\\mathcal\{T\}\)\. The plots track both the relative latency and the total number of model/tool calls across different values ofkk\.

For instance, on DeepResearch\-9K, restricting the window tok=3k=3achieves a highly competitiveRelLat\\mathrm\{RelLat\}of0\.750\.75, close to thek→∞k\\rightarrow\\inftylimit of0\.710\.71\. At this reduced capacity, the system incurs a moderate compute overhead: the average number of𝒯\\mathcal\{T\}calls increases from5\.485\.48in standard sequential execution to10\.6910\.69, whileℳ\\mathcal\{M\}calls increase from5\.485\.48to17\.8317\.83\. Finally, we note that while our theoretical analysis focuses on avoiding starvation and derives bounds based on\(α^,β^\)\(\\hat\{\\alpha\},\\hat\{\\beta\}\), the shape of this trade\-off curve is also strongly influenced by the speculator’s empirical success probabilityp^\\hat\{p\}and behavior; when the speculator is weak, larger values ofkkare less useful\. Evaluation of this trade\-off across additional configurations, including GPT\-5 asℳ\\mathcal\{M\}, is provided in Figure[4](https://arxiv.org/html/2605.21965#A3.F4)\.

![Refer to caption](https://arxiv.org/html/2605.21965v1/x3.png)Figure 3:Performance ofSpecHopusing a fast E5\-cache as the speculator \(𝒮\\mathcal\{S\}\) on the 2WikiMultihopQA dataset\. The cache size varies from 5% to 25% of the full index\. The plots show the empirical success probability \(p^\\hat\{p\}\), relative speculator latency \(α^\\hat\{\\alpha\}\), and resulting relative latency \(RelLat\\mathrm\{RelLat\}\) when accelerating both the full E5 retriever and Web Search target tools \(𝒯\\mathcal\{T\}\)\.
##### SpecHopis not limited to LLM speculators\.

In retrieval\-augmented systems, a small optimized cache can answer queries much faster than full retrieval or web search, but a naive cache\-first strategy is unreliable because incomplete or misleading cache results can compound errors\.SpecHopinstead uses the cache as a speculator, using its low latency while verifying outputs against the target tool𝒯\\mathcal\{T\}\.

We implement a fast E5\-cache backend containing only 5%, 10%, or 25% of the Wikipedia index, selecting “heavy\-hitter” passages by Wikipedia in\-degree as a proxy for centrality\. As shown in Figure[3](https://arxiv.org/html/2605.21965#S4.F3), increasing the cache fraction from 0\.05 to 0\.25 steadily improvesp^\\hat\{p\}, exceeding 60% for E5 retrieval and 50% for Web Search\. Since the local cache is much faster than web search \(α^≈0\.05\\hat\{\\alpha\}\\approx 0\.05\), this yields substantial speedups; at 0\.25 cache fraction,SpecHopreduces Web Search relative latency toRelLat=0\.64\\mathrm\{RelLat\}=0\.64, demonstrating that simple, high\-speed data subsystems can seamlessly accelerate complex reasoning agents when paired with continuous verification\.

## 5Conclusion

We accelerate multi\-hop information\-intensive trajectories by proposingSpecHop, which leverages a speculator to continuously advance speculative execution\. We provide a theoretical framework to study the latency of our algorithm and compare it with the optimal achievable gain\. Empirically, we show thatSpecHopclosely follows the theory and reduces latency while preserving task accuracy\.

## Acknowledgement

This project was supported in part by a grant from an NSF CAREER AWARD 1942230, the ONR PECASE grant N00014\-25\-1\-2378, ARO’s Early Career Program Award 310902\-00001, Army Grant No\. W911NF2120076, the NSF award CCF2212458, NSF Award No\. 2229885 \(NSF Institute for Trustworthy AI in Law and Society, TRAILS\), a MURI grant 14262683, DARPA AIQ grant HR00112590066 and an award from meta 314593\-00001\.

## References

- \[1\]Anthropic\(2026\)Computer use tool\.Note:[https://docs\.anthropic\.com/en/docs/agents\-and\-tools/tool\-use/computer\-use\-tool](https://docs.anthropic.com/en/docs/agents-and-tools/tool-use/computer-use-tool)Accessed: 2026\-05\-01Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1)\.
- \[2\]C\. Chen, S\. Borgeaud, G\. Irving, J\. Lespiau, L\. Sifre, and J\. Jumper\(2023\)Accelerating large language model decoding with speculative sampling\.arXiv preprint arXiv:2302\.01318\.Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px1.p1.1)\.
- \[3\]Google AI for Developers\(2026\)Function calling with the gemini api\.Note:[https://ai\.google\.dev/gemini\-api/docs/function\-calling](https://ai.google.dev/gemini-api/docs/function-calling)Accessed: 2026\-05\-01Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1)\.
- \[4\]Google AI for Developers\(2026\)Gemini deep research agent\.Note:[https://ai\.google\.dev/gemini\-api/docs/deep\-research](https://ai.google.dev/gemini-api/docs/deep-research)Accessed May 1, 2026Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1)\.
- \[5\]A\. Grattafiori, A\. Dubey, A\. Jauhri, A\. Pandey, A\. Kadian, A\. Al\-Dahle, A\. Letman, A\. Mathur, A\. Schelten, A\. Vaughan,et al\.\(2024\)The llama 3 herd of models\.arXiv preprint arXiv:2407\.21783\.Cited by:[§4\.1](https://arxiv.org/html/2605.21965#S4.SS1.SSS0.Px4.p1.2)\.
- \[6\]X\. Ho, A\. D\. Nguyen, S\. Sugawara, and A\. Aizawa\(2020\)Constructing a multi\-hop qa dataset for comprehensive evaluation of reasoning steps\.InProceedings of the 28th International Conference on Computational Linguistics,pp\. 6609–6625\.Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1),[§1](https://arxiv.org/html/2605.21965#S1.p5.1),[§3](https://arxiv.org/html/2605.21965#S3.p1.2),[§4\.1](https://arxiv.org/html/2605.21965#S4.SS1.SSS0.Px1.p1.1),[Table 1](https://arxiv.org/html/2605.21965#S4.T1.37.23.24.1.3),[Table 2](https://arxiv.org/html/2605.21965#S4.T2.9.2.1.3)\.
- \[7\]A\. Hurst, A\. Lerer, A\. P\. Goucher, A\. Perelman, A\. Ramesh, A\. Clark, A\. Ostrow, A\. Welihinda, A\. Hayes, A\. Radford,et al\.\(2024\)Gpt\-4o system card\.arXiv preprint arXiv:2410\.21276\.Cited by:[§4\.1](https://arxiv.org/html/2605.21965#S4.SS1.SSS0.Px4.p1.2)\.
- \[8\]Y\. Leviathan, M\. Kalman, and Y\. Matias\(2023\)Fast inference from transformers via speculative decoding\.InInternational Conference on Machine Learning,pp\. 19274–19286\.Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px1.p1.1)\.
- \[9\]P\. Lewis, E\. Perez, A\. Piktus, F\. Petroni, V\. Karpukhin, N\. Goyal, H\. Küttler, M\. Lewis, W\. Yih, T\. Rocktäschel,et al\.\(2020\)Retrieval\-augmented generation for knowledge\-intensive nlp tasks\.Advances in neural information processing systems33,pp\. 9459–9474\.Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px3.p1.1)\.
- \[10\]B\. McDanel, S\. Q\. Zhang, Y\. Hu, and Z\. Liu\(2025\)Pipespec: breaking stage dependencies in hierarchical llm decoding\.InFindings of the Association for Computational Linguistics: ACL 2025,pp\. 12909–12920\.Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px1.p1.1)\.
- \[11\]OpenAI\(2025\)Introducing deep research\.Note:[https://openai\.com/index/introducing\-deep\-research/](https://openai.com/index/introducing-deep-research/)Accessed May 1, 2026Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1)\.
- \[12\]OpenAI\(2026\)Using tools\.Note:[https://developers\.openai\.com/api/docs/guides/tools](https://developers.openai.com/api/docs/guides/tools)Accessed May 1, 2026Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1)\.
- \[13\]Q\. Qi, R\. Abhyankar, and Y\. Zhang\(2025\-12\)Demystifying delays in reasoning: a pilot temporal and token analysis of reasoning systems\.InNeurIPS 2025 Workshop on Efficient Reasoning,Vancouver, Canada\.Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p2.1)\.
- \[14\]P\. Radhakrishnan, J\. Chen, B\. Xu, P\. Ramaswami, H\. Pho, A\. Olmos, J\. Manyika, and R\. V\. Guha\(2024\)Knowing when to ask–bridging large language models and data\.arXiv preprint arXiv:2409\.13741\.Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px3.p1.1)\.
- \[15\]T\. Schick, J\. Dwivedi\-Yu, R\. Dessì, R\. Raileanu, M\. Lomeli, E\. Hambro, L\. Zettlemoyer, N\. Cancedda, and T\. Scialom\(2023\)Toolformer: language models can teach themselves to use tools\.Advances in neural information processing systems36,pp\. 68539–68551\.Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1)\.
- \[16\]A\. Singh, A\. Fry, A\. Perelman, A\. Tart, A\. Ganesh, A\. El\-Kishky, A\. McLaughlin, A\. Low, A\. Ostrow, A\. Ananthram,et al\.\(2025\)Openai gpt\-5 system card\.arXiv preprint arXiv:2601\.03267\.Cited by:[§4\.1](https://arxiv.org/html/2605.21965#S4.SS1.SSS0.Px2.p1.1)\.
- \[17\]A\. Singh, A\. Ehtesham, S\. Kumar, and T\. T\. Khoei\(2025\)Agentic retrieval\-augmented generation: a survey on agentic rag\.arXiv preprint arXiv:2501\.09136\.Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px3.p1.1)\.
- \[18\]J\. E\. Smith and A\. R\. Pleszkun\(1995\)Implementing precise interrupts in pipelined processors\.pp\. 372–383\.External Links:ISBN 0818665270Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px2.p1.1)\.
- \[19\]J\. E\. Smith\(1981\)A study of branch prediction strategies\.InProceedings of the 8th Annual Symposium on Computer Architecture,ISCA ’81,Washington, DC, USA,pp\. 135–148\.Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px2.p1.1)\.
- \[20\]Y\. Sui, H\. Zhao, R\. Ma, Z\. He, H\. Wang, J\. Li, and Y\. Yang\(2026\)Act while thinking: accelerating llm agents via pattern\-aware speculative tool execution\.arXiv preprint arXiv:2603\.18897\.Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p2.1),[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px3.p1.1)\.
- \[21\]N\. Timor, J\. Mamou, D\. Korat, M\. Berchansky, G\. Jain, O\. Pereg, M\. Wasserblat, and D\. Harel\(2025\)Accelerating llm inference with lossless speculative decoding algorithms for heterogeneous vocabularies\.arXiv preprint arXiv:2502\.05202\.Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px1.p1.1)\.
- \[22\]R\. M\. Tomasulo\(1967\)An efficient algorithm for exploiting multiple arithmetic units\.IBM Journal of Research and Development11\(1\),pp\. 25–33\.External Links:[Document](https://dx.doi.org/10.1147/rd.111.0025)Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px2.p1.1)\.
- \[23\]H\. Trivedi, N\. Balasubramanian, T\. Khot, and A\. Sabharwal\(2022\)MuSiQue: multihop questions via single\-hop question composition\.Transactions of the Association for Computational Linguistics10,pp\. 539–554\.Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1),[§1](https://arxiv.org/html/2605.21965#S1.p5.1),[§3](https://arxiv.org/html/2605.21965#S3.p1.2),[§4\.1](https://arxiv.org/html/2605.21965#S4.SS1.SSS0.Px1.p1.1),[Table 1](https://arxiv.org/html/2605.21965#S4.T1.37.23.24.1.4),[Table 2](https://arxiv.org/html/2605.21965#S4.T2.9.2.1.4)\.
- \[24\]G\. Wang, Y\. Xie, Y\. Jiang, A\. Mandlekar, C\. Xiao, Y\. Zhu, L\. Fan, and A\. Anandkumar\(2023\)Voyager: an open\-ended embodied agent with large language models\.arXiv preprint arXiv:2305\.16291\.Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1)\.
- \[25\]L\. Wang, C\. Ma, X\. Feng, Z\. Zhang, H\. Yang, J\. Zhang, Z\. Chen, J\. Tang, X\. Chen, Y\. Lin,et al\.\(2024\)A survey on large language model based autonomous agents\.Frontiers of Computer Science18\(6\),pp\. 186345\.Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1)\.
- \[26\]L\. Wang, H\. Chen, N\. Yang, X\. Huang, Z\. Dou, and F\. Wei\(2025\)Chain\-of\-retrieval augmented generation\.arXiv preprint arXiv:2501\.14342\.Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1),[§4\.1](https://arxiv.org/html/2605.21965#S4.SS1.SSS0.Px2.p1.1)\.
- \[27\]R\. Wang, Q\. Zhao, Y\. Yan, D\. Zha, Y\. Chen, S\. Yu, Z\. Liu, Y\. Wang, S\. Wang, X\. Han,et al\.\(2025\)Deepnote: note\-centric deep retrievalaugmented generation\.Preprint\.Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px3.p1.1)\.
- \[28\]Z\. Wang, Z\. Wang, L\. Le, H\. S\. Zheng, S\. Mishra, V\. Perot, Y\. Zhang, A\. Mattapalli, A\. Taly, J\. Shang,et al\.\(2024\)Speculative rag: enhancing retrieval augmented generation through drafting\.arXiv preprint arXiv:2407\.08223\.Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px3.p1.1)\.
- \[29\]T\. Wu, Y\. Wang, X\. Ma, X\. He, S\. Wang, D\. Yin, and X\. Zhao\(2026\)Deepresearch\-9k: a challenging benchmark dataset of deep\-research agent\.arXiv preprint arXiv:2603\.01152\.Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1),[§1](https://arxiv.org/html/2605.21965#S1.p5.1),[§3](https://arxiv.org/html/2605.21965#S3.p1.2),[§4\.1](https://arxiv.org/html/2605.21965#S4.SS1.SSS0.Px1.p1.1),[Table 1](https://arxiv.org/html/2605.21965#S4.T1.37.23.24.1.5),[Table 2](https://arxiv.org/html/2605.21965#S4.T2.9.2.1.5)\.
- \[30\]M\. Yan, S\. Agarwal, and S\. Venkataraman\(2025\)Decoding speculative decoding\.InProceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies \(Volume 1: Long Papers\),pp\. 6460–6473\.Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px1.p1.1)\.
- \[31\]A\. Yang, A\. Li, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Gao, C\. Huang, C\. Lv, C\. Zheng, D\. Liu, F\. Zhou, F\. Huang, F\. Hu, H\. Ge, H\. Wei, H\. Lin, J\. Tang, J\. Yang, J\. Tu, J\. Zhang, J\. Yang, J\. Yang, and J\. Zhou\(2025\)Qwen3 technical report\.arXiv\.External Links:[Document](https://dx.doi.org/10.48550/arxiv.2505.09388)Cited by:[§4\.1](https://arxiv.org/html/2605.21965#S4.SS1.SSS0.Px4.p1.2)\.
- \[32\]Y\. Yang, G\. Deng, Ö\. F\. Akgül, N\. Chitsazan, Y\. Govilkar, A\. Tigalappanavara, S\. Zhang, S\. Sahu, and V\. Prasanna\(2026\)SPARC\-rag: adaptive sequential\-parallel scaling with context management for retrieval\-augmented generation\.arXiv preprint arXiv:2602\.00083\.Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px3.p1.1)\.
- \[33\]Z\. Yang, P\. Qi, S\. Zhang, Y\. Bengio, W\. Cohen, R\. Salakhutdinov, and C\. D\. Manning\(2018\)HotpotQA: a dataset for diverse, explainable multi\-hop question answering\.InProceedings of the 2018 conference on empirical methods in natural language processing,pp\. 2369–2380\.Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1),[§3](https://arxiv.org/html/2605.21965#S3.p1.2)\.
- \[34\]S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. Narasimhan, and Y\. Cao\(2022\)React: synergizing reasoning and acting in language models\.arXiv preprint arXiv:2210\.03629\.Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p1.1)\.
- \[35\]N\. Ye, A\. Ahuja, G\. Liargkovas, Y\. Lu, K\. Kaffes, and T\. Peng\(2025\)Speculative actions: a lossless framework for faster agentic systems\.arXiv preprint arXiv:2510\.04371\.Cited by:[§1](https://arxiv.org/html/2605.21965#S1.p2.1),[§1](https://arxiv.org/html/2605.21965#S1.p3.1),[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px3.p1.1),[§3\.1](https://arxiv.org/html/2605.21965#S3.SS1.SSS0.Px1.p1.1),[§3\.1](https://arxiv.org/html/2605.21965#S3.SS1.p1.1)\.
- \[36\]T\. Yeh and Y\. N\. Patt\(1991\)Two\-level adaptive training branch prediction\.InProceedings of the 24th Annual International Symposium on Microarchitecture,MICRO 24,New York, NY, USA,pp\. 51–61\.External Links:ISBN 0897914600,[Link](https://doi.org/10.1145/123465.123475),[Document](https://dx.doi.org/10.1145/123465.123475)Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px2.p1.1)\.
- \[37\]H\. Yin, M\. Xiao, T\. Li, X\. Zhang, D\. Yu, and G\. Zhang\(2025\)SpecPipe: accelerating pipeline parallelism\-based llm inference with speculative decoding\.arXiv preprint arXiv:2504\.04104\.Cited by:[§2](https://arxiv.org/html/2605.21965#S2.SS0.SSS0.Px1.p1.1)\.

## Appendix AFull Implementation of the Algorithm

Algorithm 2SpecHop: Continuous Speculative Execution withkkActive Threads1:Query

qq, model

MM, target tool

TT, speculator

SS, verifier

VV, window size

kk
2:Final answer

ff
3:

𝐬←Init​\(M,q\)\\mathbf\{s\}\\leftarrow\\mathrm\{Init\}\(M,q\)
4:whiletruedo

5:

\(𝝉,𝐚\)←M​\(𝐬\)\(\\boldsymbol\{\\tau\},\\mathbf\{a\}\)\\leftarrow M\(\\mathbf\{s\}\)
6:if

𝝉\\boldsymbol\{\\tau\}contains a final answerthen

7:return

ExtractAnswer​\(𝝉\)\\mathrm\{ExtractAnswer\}\(\\boldsymbol\{\\tau\}\)
8:endif

9:Launch

T​\(𝐚\)T\(\\mathbf\{a\}\)asynchronously

10:

verifier​\_​thread←\(𝐬,𝝉,\(𝐚,T​\(𝐚\)\)\)\\mathrm\{verifier\\\_thread\}\\leftarrow\(\\mathbf\{s\},\\boldsymbol\{\\tau\},\(\\mathbf\{a\},T\(\\mathbf\{a\}\)\)\)
11:

𝒲←\[verifier​\_​thread\]\\mathcal\{W\}\\leftarrow\[\\mathrm\{verifier\\\_thread\}\]
12:whiletruedo

13:if

\|𝒲\|<k\|\\mathcal\{W\}\|<kthen

14:

\(𝐬′,𝝉′,\(𝐚′,⋅\)\)←Back​\(𝒲\)\(\\mathbf\{s\}^\{\\prime\},\\boldsymbol\{\\tau\}^\{\\prime\},\(\\mathbf\{a\}^\{\\prime\},\\cdot\)\)\\leftarrow\\mathrm\{Back\}\(\\mathcal\{W\}\)
15:if

𝝉′\\boldsymbol\{\\tau\}^\{\\prime\}does contain a final answerthen

16:

𝐨^′←S​\(𝐚′\)\\hat\{\\mathbf\{o\}\}^\{\\prime\}\\leftarrow S\(\\mathbf\{a\}^\{\\prime\}\)
17:

𝐬^′←Update​\(𝐬′,𝝉′,𝐚′,𝐨^′\)\\hat\{\\mathbf\{s\}\}^\{\\prime\}\\leftarrow\\mathrm\{Update\}\(\\mathbf\{s\}^\{\\prime\},\\boldsymbol\{\\tau\}^\{\\prime\},\\mathbf\{a\}^\{\\prime\},\\hat\{\\mathbf\{o\}\}^\{\\prime\}\)
18:

\(𝝉spec,𝐚spec\)←M​\(𝐬^′\)\(\\boldsymbol\{\\tau\}\_\{\\mathrm\{spec\}\},\\mathbf\{a\}\_\{\\mathrm\{spec\}\}\)\\leftarrow M\(\\hat\{\\mathbf\{s\}\}^\{\\prime\}\)
19:Launch

T​\(𝐚spec\)T\(\\mathbf\{a\}\_\{\\mathrm\{spec\}\}\)asynchronously

20:

spec​\_​thread←\(𝐬^′,𝝉spec,\(𝐚spec,T​\(𝐚spec\)\)\)\\mathrm\{spec\\\_thread\}\\leftarrow\(\\hat\{\\mathbf\{s\}\}^\{\\prime\},\\boldsymbol\{\\tau\}\_\{\\mathrm\{spec\}\},\(\\mathbf\{a\}\_\{\\mathrm\{spec\}\},T\(\\mathbf\{a\}\_\{\\mathrm\{spec\}\}\)\)\)
21:

𝒲\.push​\_​back​\(spec​\_​thread\)\\mathcal\{W\}\.\\mathrm\{push\\\_back\}\(\\mathrm\{spec\\\_thread\}\)
22:endif

23:endif

24:if

verifier​\_​thread\\mathrm\{verifier\\\_thread\}is donethen

25:

\(𝐬0,𝝉0,\(𝐚0,𝐨0\)\)←verifier​\_​thread\(\\mathbf\{s\}\_\{0\},\\boldsymbol\{\\tau\}\_\{0\},\(\\mathbf\{a\}\_\{0\},\\mathbf\{o\}\_\{0\}\)\)\\leftarrow\\mathrm\{verifier\\\_thread\}
26:

𝒲\.pop​\_​front​\(\)\\mathcal\{W\}\.\\mathrm\{pop\\\_front\}\(\)
27:

spec​\_​thread←Front​\(𝒲\)\\mathrm\{spec\\\_thread\}\\leftarrow\\mathrm\{Front\}\(\\mathcal\{W\}\)
28:

\(\(𝐬0,𝝉0,\(𝐚0,𝐨^0\)\),𝝉spec,\(𝐚spec,⋅\)\)←spec​\_​thread\\left\(\\left\(\\mathbf\{s\}\_\{0\},\\boldsymbol\{\\tau\}\_\{0\},\(\\mathbf\{a\}\_\{0\},\\hat\{\\mathbf\{o\}\}\_\{0\}\)\\right\),\\boldsymbol\{\\tau\}\_\{\\mathrm\{spec\}\},\(\\mathbf\{a\}\_\{\\mathrm\{spec\}\},\\cdot\)\\right\)\\leftarrow\\mathrm\{spec\\\_thread\}
29:if

V​\(𝐨0,𝐨^0\)=trueV\(\\mathbf\{o\}\_\{0\},\\hat\{\\mathbf\{o\}\}\_\{0\}\)=\\mathrm\{true\}then

30:

verifier​\_​thread←spec​\_​thread\\mathrm\{verifier\\\_thread\}\\leftarrow\\mathrm\{spec\\\_thread\}
31:else

32:

𝐬←Update​\(𝐬0,𝝉0,𝐚0,𝐨0\)\\mathbf\{s\}\\leftarrow\\mathrm\{Update\}\(\\mathbf\{s\}\_\{0\},\\boldsymbol\{\\tau\}\_\{0\},\\mathbf\{a\}\_\{0\},\\mathbf\{o\}\_\{0\}\)
33:

𝒲←∅\\mathcal\{W\}\\leftarrow\\emptyset
34:break

35:endif

36:endif

37:endwhile

38:endwhile

## Appendix BProofs

### B\.1Proof of Theorem[2](https://arxiv.org/html/2605.21965#Thmtheorem2)

Letℒk​\(N\)\\mathcal\{L\}\_\{k\}\(N\)denote the expected wall\-clock latency ofSpecHopwith a bounded speculative window of sizekkon a trajectory withNNremaining hops\. We assume the latencies of individual segment generations, speculative tool calls, and target tool calls are independent observations of the random variablesTsegT\_\{\\mathrm\{seg\}\},TspecT\_\{\\mathrm\{spec\}\}, andTtargetT\_\{\\mathrm\{target\}\}, respectively\.

For1≤j<k1\\leq j<k, the system advances byjjhops when the firstj−1j\-1speculative hops are verified and thejj\-th speculative hop fails\. This event has probabilitypj−1​\(1−p\)p^\{j\-1\}\(1\-p\)\. Forj=kj=k, the system advances bykkhops when the firstk−1k\-1speculative hops are all verified, which has probabilitypk−1p^\{k\-1\}\. We can compact these probabilities by defining the weight sequence:

wj=\{pj−1​\(1−p\),1≤j<k,pk−1,j=k\.w\_\{j\}=\\begin\{cases\}p^\{j\-1\}\(1\-p\),&1\\leq j<k,\\\\ p^\{k\-1\},&j=k\.\\end\{cases\}These weights form a valid probability distribution for the number of hops advanced in a single round, summing to one:

∑j=1kwj=∑j=1k−1pj−1​\(1−p\)\+pk−1=1\.\\sum\_\{j=1\}^\{k\}w\_\{j\}=\\sum\_\{j=1\}^\{k\-1\}p^\{j\-1\}\(1\-p\)\+p^\{k\-1\}=1\.
If the system advances byjjhops, it must sequentially wait for the generation ofjjsegments,j−1j\-1speculative tool calls, and exactly one target\-tool call to resolve the final state\. Because expectation is a linear operator, the expected wall\-clock cost of this round is:

𝔼​\[Cj\]=j​𝔼​\[Tseg\]\+\(j−1\)​𝔼​\[Tspec\]\+𝔼​\[Ttarget\]\.\\mathbb\{E\}\\left\[C\_\{j\}\\right\]=j\\mathbb\{E\}\\left\[T\_\{\\mathrm\{seg\}\}\\right\]\+\(j\-1\)\\mathbb\{E\}\\left\[T\_\{\\mathrm\{spec\}\}\\right\]\+\\mathbb\{E\}\\left\[T\_\{\\mathrm\{target\}\}\\right\]\.
By the Law of Total Expectation, we can formulate the recurrence relation for the remaining trajectory as:

ℒk​\(N\)=∑j=1kwj​\(𝔼​\[Cj\]\+ℒk​\(n−j\)\)\.\\mathcal\{L\}\_\{k\}\(N\)=\\sum\_\{j=1\}^\{k\}w\_\{j\}\\big\(\\mathbb\{E\}\\left\[C\_\{j\}\\right\]\+\\mathcal\{L\}\_\{k\}\(n\-j\)\\big\)\.
We now solve this recurrence asymptotically\. Assume

ℒk​\(N\)=λk​N\+O​\(1\),\\mathcal\{L\}\_\{k\}\(N\)=\\lambda\_\{k\}\\ N\+O\(1\),whereλk\\lambda\_\{k\}is the expected latency per completed hop\. Substituting into the recurrence gives:

λk​N\+O​\(1\)\\displaystyle\\lambda\_\{k\}\\ N\+O\(1\)=∑j=1kwj​\(𝔼​\[Cj\]\+λk​\(N−j\)\+O​\(1\)\)\\displaystyle=\\sum\_\{j=1\}^\{k\}w\_\{j\}\\left\(\\mathbb\{E\}\\left\[C\_\{j\}\\right\]\+\\lambda\_\{k\}\(N\-j\)\+O\(1\)\\right\)=∑j=1kwj​𝔼​\[Cj\]\+λk​N​∑j=1kwj−λk​∑j=1kj​wj\+O​\(1\)\.\\displaystyle=\\sum\_\{j=1\}^\{k\}w\_\{j\}\\mathbb\{E\}\\left\[C\_\{j\}\\right\]\+\\lambda\_\{k\}N\\sum\_\{j=1\}^\{k\}w\_\{j\}\-\\lambda\_\{k\}\\sum\_\{j=1\}^\{k\}jw\_\{j\}\+O\(1\)\.Since∑j=1kwj=1\\sum\_\{j=1\}^\{k\}w\_\{j\}=1, canceling theλk​N\\lambda\_\{k\}\\ Nterms from both sides yields:

λk=∑j=1kwj​𝔼​\[Cj\]∑j=1kj​wj\.\\lambda\_\{k\}=\\frac\{\\sum\_\{j=1\}^\{k\}w\_\{j\}\\mathbb\{E\}\\left\[C\_\{j\}\\right\]\}\{\\sum\_\{j=1\}^\{k\}jw\_\{j\}\}\.
Letμk≜∑j=1kj​wj\\mu\_\{k\}\\triangleq\\sum\_\{j=1\}^\{k\}jw\_\{j\}denote the expected number of hops advanced in one speculative round\. Using the definition ofwjw\_\{j\}, we obtain:

μk=∑j=1k−1j​pj−1​\(1−p\)\+k​pk−1=1−pk1−p\.\\mu\_\{k\}=\\sum\_\{j=1\}^\{k\-1\}jp^\{j\-1\}\(1\-p\)\+kp^\{k\-1\}=\\frac\{1\-p^\{k\}\}\{1\-p\}\.Moreover, the expected number of speculative tool calls in a round is:

∑j=1k\(j−1\)​wj=∑j=1kj​wj−∑j=1kwj=μk−1\.\\sum\_\{j=1\}^\{k\}\(j\-1\)w\_\{j\}=\\sum\_\{j=1\}^\{k\}jw\_\{j\}\-\\sum\_\{j=1\}^\{k\}w\_\{j\}=\\mu\_\{k\}\-1\.
We now evaluate the numerator ofλk\\lambda\_\{k\}by substituting𝔼​\[Cj\]\\mathbb\{E\}\\left\[C\_\{j\}\\right\]and pulling the expectations out of the summations:

∑j=1kwj​𝔼​\[Cj\]\\displaystyle\\sum\_\{j=1\}^\{k\}w\_\{j\}\\mathbb\{E\}\\left\[C\_\{j\}\\right\]=∑j=1kwj​\(j​𝔼​\[Tseg\]\+\(j−1\)​𝔼​\[Tspec\]\+𝔼​\[Ttarget\]\)\\displaystyle=\\sum\_\{j=1\}^\{k\}w\_\{j\}\\left\(j\\mathbb\{E\}\\left\[T\_\{\\mathrm\{seg\}\}\\right\]\+\(j\-1\)\\mathbb\{E\}\\left\[T\_\{\\mathrm\{spec\}\}\\right\]\+\\mathbb\{E\}\\left\[T\_\{\\mathrm\{target\}\}\\right\]\\right\)=𝔼​\[Tseg\]​∑j=1kj​wj\+𝔼​\[Tspec\]​∑j=1k\(j−1\)​wj\+𝔼​\[Ttarget\]​∑j=1kwj\\displaystyle=\\mathbb\{E\}\\left\[T\_\{\\mathrm\{seg\}\}\\right\]\\sum\_\{j=1\}^\{k\}jw\_\{j\}\+\\mathbb\{E\}\\left\[T\_\{\\mathrm\{spec\}\}\\right\]\\sum\_\{j=1\}^\{k\}\(j\-1\)w\_\{j\}\+\\mathbb\{E\}\\left\[T\_\{\\mathrm\{target\}\}\\right\]\\sum\_\{j=1\}^\{k\}w\_\{j\}=𝔼​\[Tseg\]​μk\+𝔼​\[Tspec\]​\(μk−1\)\+𝔼​\[Ttarget\]\.\\displaystyle=\\mathbb\{E\}\\left\[T\_\{\\mathrm\{seg\}\}\\right\]\\mu\_\{k\}\+\\mathbb\{E\}\\left\[T\_\{\\mathrm\{spec\}\}\\right\]\(\\mu\_\{k\}\-1\)\+\\mathbb\{E\}\\left\[T\_\{\\mathrm\{target\}\}\\right\]\.
Dividing byμk\\mu\_\{k\}yields the expected latency per hop:

λk=𝔼​\[Tseg\]​μk\+𝔼​\[Tspec\]​\(μk−1\)\+𝔼​\[Ttarget\]μk=𝔼​\[Tseg\]\+μk−1μk​𝔼​\[Tspec\]\+1μk​𝔼​\[Ttarget\]\.\\lambda\_\{k\}=\\frac\{\\mathbb\{E\}\\left\[T\_\{\\mathrm\{seg\}\}\\right\]\\mu\_\{k\}\+\\mathbb\{E\}\\left\[T\_\{\\mathrm\{spec\}\}\\right\]\(\\mu\_\{k\}\-1\)\+\\mathbb\{E\}\\left\[T\_\{\\mathrm\{target\}\}\\right\]\}\{\\mu\_\{k\}\}=\\mathbb\{E\}\\left\[T\_\{\\mathrm\{seg\}\}\\right\]\+\\frac\{\\mu\_\{k\}\-1\}\{\\mu\_\{k\}\}\\mathbb\{E\}\\left\[T\_\{\\mathrm\{spec\}\}\\right\]\+\\frac\{1\}\{\\mu\_\{k\}\}\\mathbb\{E\}\\left\[T\_\{\\mathrm\{target\}\}\\right\]\.
Substituting this exact rate back into our asymptotic assumptionℒk​\(N\)=λk​N\+O​\(1\)\\mathcal\{L\}\_\{k\}\(N\)=\\lambda\_\{k\}N\+O\(1\)gives the final expected runtime:

ℒk​\(N\)=N​\(𝔼​\[Tseg\]\+μk−1μk​𝔼​\[Tspec\]\+1μk​𝔼​\[Ttarget\]\)\+O​\(1\),\\mathcal\{L\}\_\{k\}\(N\)=N\\left\(\\mathbb\{E\}\\left\[T\_\{\\mathrm\{seg\}\}\\right\]\+\\frac\{\\mu\_\{k\}\-1\}\{\\mu\_\{k\}\}\\mathbb\{E\}\\left\[T\_\{\\mathrm\{spec\}\}\\right\]\+\\frac\{1\}\{\\mu\_\{k\}\}\\mathbb\{E\}\\left\[T\_\{\\mathrm\{target\}\}\\right\]\\right\)\+O\(1\),whereμk=1−pk1−p\\mu\_\{k\}=\\frac\{1\-p^\{k\}\}\{1\-p\}\. This proves Theorem[2](https://arxiv.org/html/2605.21965#Thmtheorem2)\.

### B\.2More details on Pipeline Starvation

##### Proof of Theorem[4](https://arxiv.org/html/2605.21965#Thmtheorem4)

Let the latenciesTsegT\_\{\\text\{seg\}\},TspecT\_\{\\text\{spec\}\}, andTtargetT\_\{\\text\{target\}\}be independent random variables with meansμseg,μspec,μtarget\\mu\_\{\\text\{seg\}\},\\mu\_\{\\text\{spec\}\},\\mu\_\{\\text\{target\}\}and variancesσseg2,σspec2,σtarget2\\sigma\_\{\\text\{seg\}\}^\{2\},\\sigma\_\{\\text\{spec\}\}^\{2\},\\sigma\_\{\\text\{target\}\}^\{2\}\.

Pipeline starvation occurs when the target tool outlasts the cumulative execution ofkkactive speculative threads\. More specifically, starvation occurs if:

Ttarget\>∑i=1kTspec,i\+∑i=2kTseg,iT\_\{\\text\{target\}\}\>\\sum\_\{i=1\}^\{k\}T\_\{\\text\{spec\},i\}\+\\sum\_\{i=2\}^\{k\}T\_\{\\text\{seg\},i\}
We define the time difference variableDkD\_\{k\}, representing the latency buffer generated by the speculative pipeline:

Dk=∑i=1kTspec,i\+∑i=2kTseg,i−TtargetD\_\{k\}=\\sum\_\{i=1\}^\{k\}T\_\{\\text\{spec\},i\}\+\\sum\_\{i=2\}^\{k\}T\_\{\\text\{seg\},i\}\-T\_\{\\text\{target\}\}Starvation occurs whenDk<0D\_\{k\}<0\. Assuming independence among the discrete execution steps, the expectation \(μD\\mu\_\{D\}\) and variance \(σD2\\sigma\_\{D\}^\{2\}\) ofDkD\_\{k\}are:

μD=k​μspec\+\(k−1\)​μseg−μtarget\\mu\_\{D\}=k\\mu\_\{\\text\{spec\}\}\+\(k\-1\)\\mu\_\{\\text\{seg\}\}\-\\mu\_\{\\text\{target\}\}σD2=k​σspec2\+\(k−1\)​σseg2\+σtarget2\\sigma\_\{D\}^\{2\}=k\\sigma\_\{\\text\{spec\}\}^\{2\}\+\(k\-1\)\\sigma\_\{\\text\{seg\}\}^\{2\}\+\\sigma\_\{\\text\{target\}\}^\{2\}
By the Central Limit Theorem \(CLT\), for a sufficient sequence of steps,DkD\_\{k\}approximates a normal distribution𝒩​\(μD,σD2\)\\mathcal\{N\}\(\\mu\_\{D\},\\sigma\_\{D\}^\{2\}\)\. The probability of starvation is therefore evaluated using the standard normal cumulative distribution functionΦ\\Phi:

P​\(Dk<0\)=Φ​\(0−μDσD\)=Φ​\(μtarget\+\(k−1\)​μseg\+μseg−k​μspec−k​μsegσD\)P\(D\_\{k\}<0\)=\\Phi\\left\(\\frac\{0\-\\mu\_\{D\}\}\{\\sigma\_\{D\}\}\\right\)=\\Phi\\left\(\\frac\{\\mu\_\{\\text\{target\}\}\+\(k\-1\)\\mu\_\{\\text\{seg\}\}\+\\mu\_\{\\text\{seg\}\}\-k\\mu\_\{\\text\{spec\}\}\-k\\mu\_\{\\text\{seg\}\}\}\{\\sigma\_\{D\}\}\\right\)Simplifying the numerator yields the generalized stochastic probability:

Pstarve​\(k\)≈Φ​\(\(μtarget\+μseg\)−k​\(μspec\+μseg\)k​σspec2\+\(k−1\)​σseg2\+σtarget2\)P\_\{\\text\{starve\}\}\(k\)\\approx\\Phi\\left\(\\frac\{\(\\mu\_\{\\text\{target\}\}\+\\mu\_\{\\text\{seg\}\}\)\-k\(\\mu\_\{\\text\{spec\}\}\+\\mu\_\{\\text\{seg\}\}\)\}\{\\sqrt\{k\\sigma\_\{\\text\{spec\}\}^\{2\}\+\(k\-1\)\\sigma\_\{\\text\{seg\}\}^\{2\}\+\\sigma\_\{\\text\{target\}\}^\{2\}\}\}\\right\)
To generalize this bound without relying on absolute wall\-clock metrics, we leverageν\\nu, such thatσX≤ν​μX\\sigma\_\{X\}\\leq\\nu\\mu\_\{X\}for all system latencies\. We substitute this bound into the denominator:

σD≤ν​k​μspec2\+\(k−1\)​μseg2\+μtarget2\\sigma\_\{D\}\\leq\\nu\\sqrt\{k\\mu\_\{\\text\{spec\}\}^\{2\}\+\(k\-1\)\\mu\_\{\\text\{seg\}\}^\{2\}\+\\mu\_\{\\text\{target\}\}^\{2\}\}
Next, we divide both the numerator and the variance components inside the square root by the target meanμtarget\\mu\_\{\\text\{target\}\}, allowing us to substitute the dimensionless relative cost ratiosα=μspec/μtarget\\alpha=\\mu\_\{\\text\{spec\}\}/\\mu\_\{\\text\{target\}\}andβ=μseg/μtarget\\beta=\\mu\_\{\\text\{seg\}\}/\\mu\_\{\\text\{target\}\}:

Pstarve​\(k\)≤Φ​\(\(1\+β\)−k​\(α\+β\)r​k​α2\+\(k−1\)​β2\+1\)P\_\{\\text\{starve\}\}\(k\)\\leq\\Phi\\left\(\\frac\{\(1\+\\beta\)\-k\(\\alpha\+\\beta\)\}\{r\\sqrt\{k\\alpha^\{2\}\+\(k\-1\)\\beta^\{2\}\+1\}\}\\right\)This completes the proof, establishing a strict upper bound on starvation probability parameterized entirely by relative system costs and network volatility\.

###### Corollary 5\(Risk\-Adjusted Capacity\)

To bound the starvation probability below an error rateϵ\\epsilon, the required active windowkϵ⋆k^\{\\star\}\_\{\\epsilon\}forSpecHopis:

kϵ⋆≈⌈kdet\+z1−ϵ⋅ν⋅kdet​α2\+\(kdet−1\)​β2\+1α\+β⌉k^\{\\star\}\_\{\\epsilon\}\\approx\\left\\lceil k\_\{\\text\{det\}\}\+z\_\{1\-\\epsilon\}\\cdot\\nu\\cdot\\frac\{\\sqrt\{k\_\{\\text\{det\}\}\\alpha^\{2\}\+\(k\_\{\\text\{det\}\}\-1\)\\beta^\{2\}\+1\}\}\{\\alpha\+\\beta\}\\right\\rceilwherez1−ϵz\_\{1\-\\epsilon\}is the\(1−ϵ\)\(1\-\\epsilon\)\-quantile of the standard normal distribution, andkdet=1\+βα\+βk\_\{\\text\{det\}\}=\\frac\{1\+\\beta\}\{\\alpha\+\\beta\}\.

Theorem[4](https://arxiv.org/html/2605.21965#Thmtheorem4)shows that the required number of active threads depends on the relative latency profile of the system, captured byα\\alphaandβ\\beta\. Intuitively, when the speculator is much faster than the target tool,α\\alphais small, so the system can sustain a larger speculative window before verification returns\. In contrast, when model decoding dominates the hop latency,β\\betais larger, and fewer active threads are sufficient because the model cannot speculate far ahead before the target\-tool result becomes available\.

Practical Examples \(ϵ=0\.05\\epsilon=0\.05for95%95\\%reliability\)\.Based on our empirical results, system latencies exhibit a maximum volatility bound ofν≤0\.4\\nu\\leq 0\.4\. We consider two representative settings\. First, in a fast\-speculator and tool\-intensive setting \(α=0\.2,β=0\.15\\alpha=0\.2,\\beta=0\.15\), the deterministic baseline iskdet≈3\.28k\_\{\\mathrm\{det\}\}\\approx 3\.28, and the stochastic bound requiresk0\.05⋆=6k^\{\\star\}\_\{0\.05\}=6active threads\. Second, in a setting with a slower speculator and a less tool\-intensive task \(α=0\.3,β=0\.75\\alpha=0\.3,\\beta=0\.75\), the deterministic baseline iskdet≈1\.67k\_\{\\mathrm\{det\}\}\\approx 1\.67, and onlyk0\.05⋆=3k^\{\\star\}\_\{0\.05\}=3active threads are required\. This suggests that, with high probability, near\-optimal latency reduction can be achieved with a strictly limited amount of parallelism in realistic stochastic settings\.

## Appendix CAdditional Results

2WikiMultihopQAMuSiQueDeepResearch\-9KSpeculator \(𝒮\\mathcal\{S\}\)ppα\\alphaβ\\beta\\columncolormetricbgRelLat∗\\mathrm\{RelLat\}^\{\*\}↓\\downarrow\\columncolormetricbgRelLat\\mathrm\{RelLat\}↓\\ \\downarrowppα\\alphaβ\\beta\\columncolormetricbgRelLat∗\\mathrm\{RelLat\}^\{\*\}↓\\downarrow\\columncolormetricbgRelLat\\mathrm\{RelLat\}↓\\ \\downarrowppα\\alphaβ\\beta\\columncolormetricbgRelLat∗\\mathrm\{RelLat\}^\{\*\}↓\\downarrow\\columncolormetricbgRelLat\\mathrm\{RelLat\}↓\\ \\downarrowWebGPT\-4o mini0\.440\.150\.34\\columncolormetricbg0\.72\\columncolormetricbg0\.780\.560\.140\.23\\columncolormetricbg0\.61\\columncolormetricbg0\.700\.670\.150\.26\\columncolormetricbg0\.55\\columncolormetricbg0\.60

Table 3:Latency reduction achieved bySpecHopusing an off\-the\-shelfGPT\-5as the generator model \(ℳ\\mathcal\{M\}\)\. The target tool is Web Search, and the speculator is GPT\-4o mini\. The results demonstrate that even when wrapping a highly capable, generalized reasoning model, continuous speculation yields significant wall\-clock speedups across all multi\-hop datasets\.### C\.1Generalization to State\-of\-the\-Art Off\-the\-Shelfℳ\\mathcal\{M\}\(GPT\-5\)

While our primary experiments utilize CoRAG, we demonstrate the generalizability ofSpecHopby applying it to an off\-the\-shelf GPT\-5 model\. Rather than fine\-tuning, we provide GPT\-5 with a single\-shot prompt \(refer to Appendix[D\.2](https://arxiv.org/html/2605.21965#A4.SS2)for more details\) demonstrating the desired multi\-hop sub\-query and answer format\. We wrap this standard GPT\-5 agent in our continuous speculation and verification framework, replacing its native sequential tool calls with our speculative threads\.

Table[3](https://arxiv.org/html/2605.21965#A3.T3)shows the relative latency achieved by our method, using GPT\-4o mini as𝒮\\mathcal\{S\}and Web Search as𝒯\\mathcal\{T\}\. We can see that our method consistently achieves high relative latency in all settings, while preserving EM and F1 \(Table[4](https://arxiv.org/html/2605.21965#A3.T4)\)\. One notable point about using GPT\-5 asℳ\\mathcal\{M\}is the higher generator latency, which can be observed directly in Figure[5](https://arxiv.org/html/2605.21965#A3.F5)\(top right plot\), and higherβ\\betafor results in Table[3](https://arxiv.org/html/2605.21965#A3.T3)compared to Table[1](https://arxiv.org/html/2605.21965#S4.T1)\.

Table 4:Comprehensive breakdown of Exact Match \(EM\) and F1 scores across all evaluated configurations\.SpecHoptightly preserves the task accuracy of the standard sequential execution\. Unless otherwise noted, the generator model \(ℳ\\mathcal\{M\}\) is CoRAG\. The final row reflects experiments where the standard trajectory was produced using GPT\-5 as the generator model \(ℳ\\mathcal\{M\}\), maintaining accuracy even with a highly capable off\-the\-shelf model\.
### C\.2Effect ofSpecHopon EM/F1

While the primary advantage ofSpecHopis substantial wall\-clock latency reduction, it is critical that these speedups do not compromise the task performance of the underlying retrieval\-augmented trajectory\. BecauseSpecHopemploys a strict verification step using the verifier𝒱\\mathcal\{V\}before committing to any prediction from the speculator model𝒮\\mathcal\{S\}, the final trajectory effectively mirrors the one that would have been produced by the generator modelℳ\\mathcal\{M\}operating sequentially with the target tool𝒯\\mathcal\{T\}\.

Table[4](https://arxiv.org/html/2605.21965#A3.T4)details the Exact Match \(EM\) and F1 scores for both the standard sequential baseline andSpecHopacross all available experimental configurations, spanning three datasets, two target tools \(𝒯\\mathcal\{T\}\), and multiple speculator models \(𝒮\\mathcal\{S\}\)\. As shown, the task metrics remain nearly identical across all settings\. Minor deviations \(typically<1%<1\\%\) arise strictly from benign variations accepted by the verifier𝒱\\mathcal\{V\}\(e\.g\., functionally equivalent string variations or negligible API noise\)\. This comprehensive breakdown confirms thatSpecHopsuccessfully accelerates inference without degrading the reasoning or retrieval accuracy of either local generator models \(CoRAG\) or highly capable off\-the\-shelf generator models \(GPT\-5\)\.

ℳ\\mathcal\{M\}: CoRAG,𝒮\\mathcal\{S\}: Llama 3\.1 8B,𝒯\\mathcal\{T\}: E5 Retrieval ![Refer to caption](https://arxiv.org/html/2605.21965v1/x4.png)

ℳ\\mathcal\{M\}: CoRAG,𝒮\\mathcal\{S\}: Llama 3\.1 8B,𝒯\\mathcal\{T\}: Web Search ![Refer to caption](https://arxiv.org/html/2605.21965v1/x5.png)

ℳ\\mathcal\{M\}: GPT\-5,𝒮\\mathcal\{S\}: GPT\-4o mini,𝒯\\mathcal\{T\}: Web Search ![Refer to caption](https://arxiv.org/html/2605.21965v1/x6.png)

Figure 4:The effect of the active thread limit \(kk\) on relative latency \(RelLat\\mathrm\{RelLat\}\) and computational cost across various extended configurations\. The plots track the average number of calls to the target tool \(𝒯\\mathcal\{T\}\), speculator \(𝒮\\mathcal\{S\}\), and generator model \(ℳ\\mathcal\{M\}\)\. The first two rows utilize CoRAG as the standard generator model, exploring different combinations of speculators and target tools\. The final row demonstrates thekk\-capacity trade\-off when wrapping a highly capable off\-the\-shelf GPT\-5 model \(refer to Appendix[C\.1](https://arxiv.org/html/2605.21965#A3.SS1)for more details\)\.
### C\.3Human Evaluation of Verifier Performance

BecauseSpecHop’s mathematical losslessness relies entirely on the correctness of the verifier \(𝒱\\mathcal\{V\}\), we conducted a human evaluation of our deterministic rule\-based verifier to ensure it does not falsely accept divergent speculative trajectories\. We randomly sampled 100 verification decisions \(50 accepted and 50 rejected by the verifier\) from the 2WikiMultihopQA evaluation, utilizing Llama 3\.1 8B as the speculator \(𝒮\\mathcal\{S\}\) and E5 as the target tool \(𝒯\\mathcal\{T\}\)\.

Treating human judgment as the ground truth, the verifier achieved a perfect precision of 100\.0% and a high recall of 96\.2%\. The 100% precision confirms that there were zero false positives, meaning the verifier never incorrectly passed a flawed speculation that could compound errors or hurt the multi\-hop trajectory\. The slightly lower recall indicates that the verifier’s heuristics are appropriately conservative, occasionally rejecting functionally correct speculations to strictly guarantee trajectory integrity\. These results empirically validate that our verification mechanism safely accelerates inference without compromising the accuracy of the baseline reasoning path\.

2WikiMultihopQAMuSiQueDeepResearch\-9KSpeculator Model \(𝒮\\mathcal\{S\}\)RelLat\\mathrm\{RelLat\}\\columncolormetricbgRelLatE​M=t​r​u​e\\mathrm\{RelLat\}\_\{EM=true\}RelLat\\mathrm\{RelLat\}\\columncolormetricbgRelLatE​M=t​r​u​e\\mathrm\{RelLat\}\_\{EM=true\}RelLat\\mathrm\{RelLat\}\\columncolormetricbgRelLatE​M=t​r​u​e\\mathrm\{RelLat\}\_\{EM=true\}E5Llama 3\.1 8B0\.91\\columncolormetricbg0\.910\.87\\columncolormetricbg0\.860\.88\\columncolormetricbg0\.84Qwen 3 8B0\.95\\columncolormetricbg0\.960\.89\\columncolormetricbg0\.910\.92\\columncolormetricbg0\.87WebLlama 3\.1 8B0\.78\\columncolormetricbg0\.770\.72\\columncolormetricbg0\.710\.76\\columncolormetricbg0\.65Qwen 3 8B0\.88\\columncolormetricbg0\.870\.78\\columncolormetricbg0\.750\.78\\columncolormetricbg0\.65GPT\-4o mini0\.76\\columncolormetricbg0\.760\.72\\columncolormetricbg0\.760\.75\\columncolormetricbg0\.63GPT\-4o0\.60\\columncolormetricbg0\.590\.69\\columncolormetricbg0\.640\.72\\columncolormetricbg0\.60GPT\-4o mini \(ℳ\\mathcal\{M\}: GPT\-5\)0\.78\\columncolormetricbg0\.760\.70\\columncolormetricbg0\.660\.60\\columncolormetricbg0\.56

Table 5:Comparison of overall empirical relative latency \(RelLat\\mathrm\{RelLat\}\) against the relative latency isolated to the subset of queries answered correctly by the base model \(RelLatE​M=t​r​u​e\\mathrm\{RelLat\}\_\{EM=true\}\)\.SpecHopconsistently delivers robust speedups on successful multi\-hop trajectories, confirming that latency reductions hold steady regardless of the underlying sample difficulty \(e\.g\., the challenging MuSiQue versus the easier 2WikiMultihopQA\)\.
### C\.4Latency Gain on Correct Predictions \(EM=True\)

The global latency gains reported in our main experiments encompass all evaluated samples, regardless of whether the generator model \(ℳ\\mathcal\{M\}\) ultimately produced the correct final answer\. As detailed in Table[4](https://arxiv.org/html/2605.21965#A3.T4), the intrinsic difficulty of the tasks varies significantly; for instance, MuSiQue is highly challenging for the baseline models \(resulting in low Exact Match and F1 scores\), whereas 2WikiMultihopQA is relatively easier \(yielding high EM and F1 scores\)\.

In datasets with lower base performance, it is critical to ensure that the reported latency reductions are not simply an artifact of failing trajectories \(e\.g\., the model getting confused or failing to retrieve useful context\)\. To validate this, we filter the evaluation pipeline to isolate the subset of samples where the model successfully reasons through the problem and outputs the correct final answer \(EM=True\)\.

Table[5](https://arxiv.org/html/2605.21965#A3.T5)compares the overall relative latency \(RelLat\\mathrm\{RelLat\}\) with the relative latency on this successful subset \(RelLatE​M=t​r​u​e\\mathrm\{RelLat\}\_\{EM=true\}\)\. The results demonstrate that the lower overall accuracy on challenging datasets like MuSiQue does not invalidateSpecHop’s efficiency gains\. Across all datasets and speculator configurations,SpecHopconsistently achieves similar—and frequently even greater—latency reductions on the accurately predicted samples\. This confirms that continuous speculation reliably accelerates successful, complex reasoning paths across all sample difficulties without bias toward failing trajectories\.

![Refer to caption](https://arxiv.org/html/2605.21965v1/x7.png)Figure 5:Empirical distributions of hop\-level latency components and resulting relative latency metrics\. Mean \(μ\\mu\) and standard deviation \(σ\\sigma\) are annotated for temporal components\. Unless otherwise specified on the axes, the default configuration uses CoRAG as the generator model \(ℳ\\mathcal\{M\}\), Llama 3\.1 8B as the speculator \(𝒮\\mathcal\{S\}\), 2WikiMultihopQA as the dataset, and Web Search as target tool \(𝒯\\mathcal\{T\}\)\. The top row isolates the variance inherent to the target tool \(ttoolt\_\{\\mathrm\{tool\}\}\), the speculator \(tspect\_\{\\mathrm\{spec\}\}\), and the generator model \(tsegt\_\{\\mathrm\{seg\}\}\), including a direct comparison between local CoRAG and API\-based GPT\-5 generation speeds\. The bottom row highlights the practical speedups \(RelLat\\mathrm\{RelLat\}\) achieved across different datasets and target tools compared to their theoretical limits \(RelLat∗\\mathrm\{RelLat\}^\{\*\}\)\.
### C\.5Distribution of Latency Components

To better understand where time is spent during speculative execution, we plot the empirical distribution of stage runtimes, specifically the time spent on model generation \(tsegt\_\{\\mathrm\{seg\}\}\), target tool execution \(ttargett\_\{\\mathrm\{target\}\}\), and speculative execution \(tspect\_\{\\mathrm\{spec\}\}\)\. Figure[5](https://arxiv.org/html/2605.21965#A3.F5)visualizes these distributions, providing critical insight into the system’s temporal bottlenecks and the resulting efficiency gains\.

Looking at the individual stage latencies \(top row\), we observe a stark contrast between the target tools\. The local E5 retriever is highly deterministic and fast \(μ=0\.44\\mu=0\.44s\), whereas Web Search introduces a massive temporal bottleneck with a heavy right tail \(μ=4\.15\\mu=4\.15s,σ=1\.68\\sigma=1\.68s\) due to network\-bound page fetching\. The speculator latency \(tspect\_\{\\mathrm\{spec\}\}\) highlights the architectural divide between local and API\-based models: local speculators like Llama 3\.1 8B and Qwen 3 8B resolve in under 0\.2 seconds, while API\-dependent models like the GPT\-4o series suffer from network overhead, pushing their mean execution times to roughly 0\.6 seconds\. Similarly, the generator latency \(tsegt\_\{\\mathrm\{seg\}\}\) shows that while the local CoRAG model is tightly optimized \(μ=0\.33\\mu=0\.33s\), querying the off\-the\-shelf GPT\-5 model introduces significantly higher base latency \(μ=1\.48\\mu=1\.48s\)\.

The bottom row translates these component latencies into system\-wide speedups\. Because Web Search dominates the sequential trajectory time, it offers the greatest opportunity for optimization\. Consequently, the empirical relative latency \(RelLat\\mathrm\{RelLat\}\) for Web Search tasks exhibits much lower medians and wider variance compared to E5 tasks, which naturally cluster closer to 1\.0 due to their already low base latency\. Finally, the scatter plot comparing Oracle to Empirical Relative Latency demonstrates thatSpecHopis highly efficient in practice; across all dataset and tool combinations, the empirical speedups closely hug the idealy=xy=xline, proving that our continuous speculation framework successfully captures the vast majority of the theoretical maximum latency gain\.

## Appendix DImplementation Details

### D\.1Additional Implementation and Setup Details

This section details the system configurations and execution rules omitted from the main text for brevity\. All of our experiments are done with two NVIDIA L40 48GB GPUs, to load and use the generator model \(ℳ\\mathcal\{M\}\), speculator \(𝒮\\mathcal\{S\}\), and target tool \(𝒯\\mathcal\{T\}\)\.

##### Generation Hyperparameters\.

To ensure deterministic evaluation and minimize generation variance, all local generator models \(ℳ\\mathcal\{M\}\) are served using vLLM with greedy decoding \(temperature = 0\.0\)\. During standard multi\-hop execution, the generator produces sub\-queries with a 64\-token cap, and intermediate/final answers with a 128\-token cap\. When utilizing LLMs as speculators \(𝒮\\mathcal\{S\}\), we enforce a strict 16\-token generation cap to minimize the speculative latency \(tspect\_\{\\mathrm\{spec\}\}\)\.

##### Dataset Splits and Early Stopping\.

We evaluate on thevalidationsplits for 2WikiMultihopQA and MuSiQue, and thetrainsplit for DeepResearch\-9K \(as it is the standard release split for the benchmark\)\. During inference, to prevent infinite loops or degenerate trajectories, the pipeline halts ifℳ\\mathcal\{M\}generates the exact same sub\-query twice \(determined via normalized string matching\)\. Furthermore, if the target tool \(𝒯\\mathcal\{T\}\) repeatedly fails to find relevant context—returning the literal string “No relevant information found”—we terminate the trajectory early\. We allow one such failure for 2WikiMultihopQA and MuSiQue, and two failures for DeepResearch\-9K before aborting\.

##### Target Tool \(𝒯\\mathcal\{T\}\) Backends\.

For theE5 Retrievaltarget tool, queries are encoded with a maximum length of 64 tokens using theintfloat/e5\-large\-v2model\. For memory efficiency during parallel retrieval, the passage index is loaded via shards and queried usingint8row\-wise quantization\. For theWeb Searchtarget tool, the system fetches the HTML of the returned DuckDuckGo URLs in parallel\. Each page’s visible text is extracted and truncated to 10,000 characters\. The total target tool latency \(ttargett\_\{\\mathrm\{target\}\}\) incorporates both the search API response time and the maximum page\-fetch time across the parallel requests \(capped strictly by the 3\-second timeout\)\.

##### Cached\-Retrieval Speculator \(𝒮\\mathcal\{S\}\)\.

For the experiments evaluating a fast cache retriever as the speculator, the speculative backend is implemented as a smaller E5 index built from a heavily sharded subset of Wikipedia passages\. The generator \(ℳ\\mathcal\{M\}\) then produces the speculative observation \(𝐨^i\\hat\{\\mathbf\{o\}\}\_\{i\}\) using this truncated, rapidly retrieved context, following the same intermediate\-answer prompt template as the target\-tool path but strictly bounded by the shorter speculative token cap\.

##### Latency Measurement and Simulation\.

To ensure strict comparability and isolate the temporal gains ofSpecHop, we execute the full set of required trajectory calls sequentially, recording the exact wall\-clock times for every atomic stage: sub\-query generation \(tsegt\_\{\\mathrm\{seg\}\}\), target tool execution \(ttargett\_\{\\mathrm\{target\}\}\), and speculative execution \(tspect\_\{\\mathrm\{spec\}\}\)\. The end\-to\-end relative latency \(RelLat\\mathrm\{RelLat\}\) forSpecHopis then calculated using a deterministic discrete\-event simulator that applies the continuous speculation schedule \(Algorithm[1](https://arxiv.org/html/2605.21965#alg1)\) over the empirically recorded stage times\. This ensures that the reported speedups are unaffected by transient hardware loads or background system noise\.

##### Metrics\.

Answer quality \(Exact Match and F1\) is computed using standard SQuAD\-style text normalization\. In addition to measuring accuracy against the dataset’s gold answers, we report the agreement between the speculative trajectory and the baseline trajectory to verify our theoretical losslessness\.

### D\.2System Prompts forℳ\\mathcal\{M\}

For our off\-the\-shelf evaluation using GPT\-5 as the generator model \(ℳ\\mathcal\{M\}\), we design a structured, one\-shot prompting pipeline to enforce the required multi\-hop reasoning and tool\-use trajectory\. The pipeline consists of a universal system instruction and step\-specific user prompts for each stage of the generation process\. To ensure strict structural compliance and easy parsing by the verifier \(𝒱\\mathcal\{V\}\), we utilize XML\-style tags\.

#### Universal System Instruction

This system prompt establishes the strict behavioral constraints and provides a single\-shot example to align the off\-the\-shelf model with our trajectory format\.

You are a strict multi\-hop QA agent\. Follow the required XML\-like tags exactly\.Rules: 1\) Only output one of the allowed tags at a time based on the current instruction\. 2\) Allowed tags: <subquestion\>\.\.\.</subquestion\>, <subanswer\>\.\.\.</subanswer\>, <final\_answer\>\.\.\.</final\_answer\>\. 3\) Never output explanations, markdown, JSON, or any text outside the required tag\. 4\) Keep subquestions simple and answerable via web search snippets\. 5\) Subquestions should target a single short factual answer \(name, year, place, yes/no\)\. 6\) Subanswers should be a single short factual answer \(name, year, place, yes/no\)\. 7\) Use at most \{max\_hops\} subquestions, but stop as soon as the final answer can be derived from the subanswers with certainty\.Format example to imitate: question: "Which film has the director who was born earlier, Face Of A Fugitive or Cage Of Gold?" output: <subquestion\> Who directed Face Of A Fugitive? </subquestion\><subanswer\> Paul Wendkos </subanswer\><subquestion\> What is the birth year of Paul Wendkos? </subquestion\><subanswer\> 1925 </subanswer\><subquestion\> Who directed Cage Of Gold </subquestion\><subanswer\> Basil Dearden </subanswer\><subquestion\> What is the birth year of Basil Dearden? </subquestion\><subanswer\> 1911 </subanswer\><final\_answer\> Cage Of Gold </final\_answer\>

#### Step\-Specific User Prompts

At each step of the trajectory, the generator model \(ℳ\\mathcal\{M\}\) receives the universal system prompt along with one of the following specific instructions, depending on the current state of the inference loop\.

##### 1\. Next Sub\-question Generation\.

Invoked when the model needs to query the target tool \(𝒯\\mathcal\{T\}\) or speculator \(𝒮\\mathcal\{S\}\)\.Main question: \{question\}Current hop index: \{hops\_done \+ 1\} / \{max\_hops\} Existing reasoning trace: \{trace\_blob\}Output exactly one next subquestion in this format: <subquestion\> \.\.\. </subquestion\>

##### 2\. Sub\-answer Generation\.

Invoked to process the retrieved documents from the tool\.Main question: \{question\}Current subquestion: \{subquestion\}Search results: \{search\_snippets\}Answer the current subquestion only using the search results\. If uncertain, return a short best\-effort answer\. Output exactly: <subanswer\> \.\.\. </subanswer\>

##### 3\. Final Answer Generation\.

Invoked when the hop budget is exhausted or sufficient information is gathered\.Main question: \{question\}Reasoning trace: \{trace\_blob\}Output exactly one final answer tag: <final\_answer\> \.\.\. </final\_answer\>

##### Formatting Fallback Mechanism\.

In the rare event that the off\-the\-shelf model outputs reasoning tokens outside the designated XML tags or deviates from the schema, we use a lightweight fallback prompt to force structural compliance before advancing the trajectory:Your previous output violated the required format\. Previous output: \{bad\_output\}Return ONLY one valid \{required\_tag\} tag and nothing else\.

### D\.3System Prompts for𝒮\\mathcal\{S\}

For all LLM\-based speculator models \(𝒮\\mathcal\{S\}\), we employ a highly concise, few\-shot prompting strategy designed to minimize generation latency and enforce strictly formatted, direct answers\. The speculator is explicitly instructed to act as a “fast assistant” and bypass any conversational filler or step\-by\-step reasoning\.

#### Universal System Instruction

This system prompt establishes the rapid\-response persona and provides four diverse few\-shot examples to demonstrate the expected question\-answer mapping using XML\-style tags\.

You are a fast assistant\. Return only the direct answer, with no explanation\.<question\>What is the name of the performer of the song Velvet Goldmine?</question\> <answer\>T\. Rex</answer\><question\>Where is Babu Nanthankode from?</question\> <answer\>Thiruvananthapuram, India\.</answer\><question\>What is the birthdate of Hans Olsen \(Cyclist\)?</question\> <answer\>1 January 1885</answer\><question\>Is Reservoir High School located in Victoria?</question\> <answer\>Yes\.</answer\>

#### Sub\-query Speculation Prompt

At inference time, the specific sub\-query generated byℳ\\mathcal\{M\}is injected into the user prompt\. We append the opening<answer\>tag to force the speculator model to immediately begin generating the factual response without preamble\.

<question\>\{subquery\}</question\> <answer\>

##### Generation Parameters and Post\-Processing\.

To further ensure optimal latency and deterministic behavior, all speculator calls are executed using greedy decoding \(temperature = 0\.0\) and a strict length limit \(max\_new\_tokens = 16\)\. After generation, a lightweight post\-processing step automatically strips any residual<answer\>or</answer\>tags before passing the predicted observation to the verifier \(𝒱\\mathcal\{V\}\)\.

### D\.4Deterministic Rule\-Based Verifier \(𝒱\\mathcal\{V\}\) Implementation

To ensure trajectory losslessness without the latency overhead of an LLM\-based evaluator, we utilize a lightweight, deterministic rule\-based verifier \(𝒱\\mathcal\{V\}\)\. Because the integrity of the speculative framework relies entirely on preventing false positives, our implementation employs a set of conservative heuristics to guarantee that only factually equivalent observations are accepted\.

The verifier compares the speculative observation \(𝐨^i\\hat\{\\mathbf\{o\}\}\_\{i\}\) with the target tool’s observation \(𝐨i\\mathbf\{o\}\_\{i\}\) through a strict evaluation pipeline\. First, both texts undergo standard normalization \(lowercasing, diacritic and punctuation removal\)\. The verifier then immediately rejects any speculative outputs that match common refusal or uncertainty patterns \(e\.g\., “I don’t know,” “information unavailable”\) to prevent the trajectory from absorbing uninformative responses\.

For factual verification, the system enforces a strict numeric consistency check: if the target observation contains multi\-digit numbers \(such as years or quantities\), the speculative observation must contain matching numeric values, otherwise it is automatically rejected\. Final acceptance requires either a direct substring match or a high degree of lexical overlap\. Specifically, after filtering out standard English stopwords, the speculation must achieve either≥72%\\geq 72\\%token coverage or a Jaccard similarity of≥0\.55\\geq 0\.55\. For exceptionally short answers \(under 5 characters\), the verifier defaults to requiring a perfect token match\. This robust, cautious design ensures that speculative threads only commit when they deliver the precise factual payload required by the generator model \(ℳ\\mathcal\{M\}\)\.

## Appendix ELimitation

SpecHoprequires a fast, approximate speculator \(𝒮\\mathcal\{S\}\) and a reliable verifier \(𝒱\\mathcal\{V\}\), as formalized in Assumptions[1](https://arxiv.org/html/2605.21965#Thmassumption1)and[2](https://arxiv.org/html/2605.21965#Thmassumption2)\. In domains where these tools are unavailable, or where verifying an answer is as expensive as executing the full target tool \(𝒯\\mathcal\{T\}\), the latency reduction from continuous speculation cannot be achieved\. Furthermore, whileSpecHopachieves significant latency reduction in many settings, it generally introduces a noticeable increase in overall computation cost\. Because the framework maintains a continuous window of active threads, it requires running multiple parallel instances of models and tools simultaneously\. Nevertheless,SpecHopremains a highly practical solution in scenarios where minimizing wall\-clock latency is critical and a higher computational overhead is a tolerable trade\-off\.