SpecHop: Continuous Speculation for Accelerating Multi-Hop Retrieval Agents

Source: arXiv:2605.21965 · Published 2026-05-21 · By Mehrdad Saberi, Keivan Rezaei, Soheil Feizi

TL;DR

This paper addresses the significant latency in multi-hop retrieval-augmented language model workflows, where models sequentially call external tools like web search or document retrieval multiple times, waiting for each result before continuing. The key novelty is the introduction of SpecHop (SPECHOP), a continuous speculation framework that maintains multiple parallel speculative threads predicting future tool outputs faster but less reliably than the true target tools. By verifying these speculative observations asynchronously and discarding incorrect speculative branches while committing correct ones, SpecHop preserves the exact same final trajectory as the original sequential method but greatly reduces wall-clock latency.

The authors develop a rigorous theoretical latency model for lossless speculation, deriving optimal latency gains and bounds on how many speculative threads are required to approach this optimum given the speculator speed, accuracy, and model decoding overhead. Empirically, they evaluate SpecHop on three multi-hop QA datasets (2WikiMultihopQA, MuSiQue, DeepResearch-9K) and two retrieval backends (E5 retrieval, Web search), using various language models as speculators (e.g., Llama 3.1 8B, GPT-4o). Results show latency reductions up to 40% compared to standard sequential multi-hop execution with essentially no loss in end-task accuracy. SpecHop matches the theoretical latency limits closely and provides a flexible tradeoff between speed and computational cost via the number of speculative threads maintained.

Key findings

• SpecHop achieves up to 40% wall-clock latency reduction on multi-hop retrieval QA tasks compared to sequential tool use, e.g., relative latency (RelLat) of 0.60 versus standard 1.0 using GPT-4o speculator over Web Search on 2WikiMultihopQA.
• Empirical latency reductions closely match theoretically optimal bounds (RelLat*), e.g., 0.50 theoretical limit, 0.60 measured actual.
• Speculative success probabilities (p) vary by speculator: GPT-4o reaches up to 68% success; smaller models like Llama 3.1 8B achieve ~27%–41%.
• Relative speculator latency (α) ranges: local retrieval caches achieve ~0.03–0.05 vs slow web search.
• Number of active speculative threads (k) controls tradeoff: k=3 achieves close to optimal latency with moderate overhead; higher k yields diminishing returns (Fig 2).
• Task accuracy (Exact Match, F1) is preserved within noise under SpecHop versus standard sequential execution, while naively using only speculative tools causes large accuracy drops (e.g., EM falls from 68.7 to 38.7 on 2WikiMultihopQA).
• Verification is reliable using token-based heuristic similarity; false commits are prevented by discarding wrong speculative branches.
• Using a small fast E5-cache as speculator with 25% index coverage yields ~60% success probability and reduces relative latency to 0.64 on Web Search target.

Threat model

The adversary is not attacker in traditional sense; the threat model relates to correctness preservation in speculation: the system assumes that the speculator may produce incorrect observations but that a verifier can perfectly and deterministically detect whether speculative observations match the true tool outputs, preventing incorrect trajectory divergence. The adversary cannot compromise the verifier or force incorrect commits; the model preserves fidelity by rolling back on failed speculation. No adversarial or malicious actor scenario is considered.

Methodology — deep read

The work focuses on accelerating inference trajectories of large language models that rely on sequential multi-hop external tool calls for retrieval or web search. The setting assumes a model M answering a query q via N intermediate hops, each generating an intermediate query and calling an external tool T for an observation oi. The total latency is the sum of decoding time (Tseg) and external tool latency (Ttarget) per hop.

They assume the availability of a faster but approximate speculator tool S that for the same action ai produces a speculative observation ôi in time Tspec < Ttarget, correct with probability p (the observation induces the same next state as the target). They also assume a deterministic verifier V can determine if the speculative observation is equivalent to the true target observation to allow committing or rollback.

Building on this, SpecHop maintains a continuous speculation pipeline with up to k parallel speculative threads T1, T2, ..., Tk. Each thread corresponds to a hypothesized next state obtained by speculating a tool response and continuing the trajectory speculatively. The earliest unresolved speculative thread is verified as the true target observation returns. On verification success, the pipeline advances, discarding the verified thread and moving all speculative threads forward. On failure, speculative threads downstream of the failure are discarded and the process resumes from the last verified state.

They mathematically model expected latency under these assumptions, deriving closed-form expressions for latency gain relative to standard sequential execution, parameterized by p, α=E[Tspec]/E[Ttarget] and β=E[Tseg]/E[Ttarget]. The continuous speculation framework is shown to approach the theoretical optimal as k→∞ with large N.

Experimentally, they evaluate on 3 multi-hop QA benchmark datasets: 2WikiMultihopQA, MuSiQue, and DeepResearch-9K, selecting benchmarks with 2-4 hops or fixed 10 hop budgets. The primary generation model M is CoRAG-Llama 3.1 8B multihop QA model; experiments also include GPT-5. Two target tools T are evaluated: (1) E5 neural retrieval over KILT Wikipedia passages and (2) DuckDuckGo web search.

Speculators S include various LLMs (Llama 3.1 8B, Qwen 3 8B, GPT-4o mini, GPT-4o) chosen for speed-accuracy tradeoffs, plus a fast cached retrieval backend from top Wikipedia passages as speculator.

The verifier is deterministic and rule-based using normalization, exact match, and token-set Jaccard similarity to confirm equivalence of speculative and target sub-answers.

They compare standard sequential multi-hop execution (M + T, waiting for each hop) against SpecHop continuous speculation with various k values and speculator models. They also study the full speculation method with only the speculator and no verification, which shows severe accuracy degradation.

Latency is measured as wall-clock time from input question to final answer. Accuracy is Exact Match (EM) and token F1 on normalized answer texts. They perform ablations on thread count k and cache size for cached speculator to study trade-offs.

All experiments are run with fixed hop budgets per dataset, and intensive logging records speculation wins, failures, and runtime metrics. The method preserves verified trajectories identical to standard execution, guaranteeing lossless fidelity.

A single example end-to-end: Given a multi-hop query, SpecHop launches the first hop with both target tool call and a speculative thread predicting the output. Additional speculative threads continue downstream guesses. When the first hop’s true target output returns, the verifier checks if the speculator’s guesses match; if yes, it commits and advances all threads; if no, speculative threads are discarded and the process resumes from known verified state. This pipeline runs concurrently, keeping the system busy and reducing idle waiting during slow external calls.

Technical innovations

• Formulation of lossless multi-hop tool-use speculation with a formal theoretical latency model that bounds achievable speedups based on speculator accuracy, latency, and model decoding time.
• Design of continuous speculation algorithm (SpecHop) maintaining multiple parallel speculative threads with asynchronous verification, generalizing standard single speculative hop methods.
• Introduction of probabilistic analysis to select minimal active thread counts k to approximate optimal latency gains under stochastic latency assumptions.
• Empirical demonstration that fast, low-accuracy speculators (LLMs or retrieval caches) can safely accelerate multi-hop retrieval trajectories without accuracy loss by roll-back verification.

Datasets

• 2WikiMultihopQA — moderate size multi-hop QA benchmark — public
• MuSiQue — multi-hop QA dataset focusing on Wikipedia queries — public
• DeepResearch-9K — multi-hop retrieval QA with 9,000 samples at varying difficulty — public

Baselines vs proposed

• Standard sequential execution: Relative latency = 1.0 vs SpecHop: Reduced to 0.60 (40% latency reduction) on 2WikiMultihopQA with GPT-4o speculator over Web Search.
• Full Speculation (using only speculator without verification): EM drops from 68.7 to 38.7 on 2WikiMultihopQA; SpecHop preserves EM at 69.3.
• SpecHop empirical relative latency (RelLat) closely matches theoretical optimum (RelLat*), e.g., 0.50 theoretical vs 0.60 actual with GPT-4o Web Search.
• Varying thread count k: k=3 reaches similar latency as unbounded with ~0.75 relative latency, balancing overhead and speed (Fig 2).
• Cached E5 as speculator with 25% index: RelLat reduces to 0.64 vs 1.0 baseline on Web Search target tool.

Limitations

• Assumes access to a verifier that reliably decides speculator equivalence with target outputs; real-world verification may be imperfect or costly.
• Requires speculator tool with sufficiently high accuracy and lower latency, which may not be available for all domains or retrieval tasks.
• Empirical evaluation limited to English Wikipedia-based QA datasets; unclear performance on other retrieval domains or languages.
• Speculative thread count k tradeoff means increased computational cost proportional to number of parallel calls; may not be practical in highly resource constrained environments.
• Verification is done rule-based on exact or token overlap matches; does not explore learned or semantic verification which may affect accuracy guarantees.
• Potential for system starvation or slowdown if speculation success probability p or latency gains α degrade, though the theory bounds these effects.

Open questions / follow-ons

• How to design or learn more robust verifiers for equivalence checking beyond token-level matches, potentially improving speculation success rates p while preserving correctness?
• Extension of speculation frameworks to richer multi-modal or multi-tool agent workflows, including code execution or API calls with more complex observations.
• Adaptive speculation thread management balancing latency gain and compute cost dynamically based on real-time speculator reliability or workload conditions.
• Applicability of speculation to non-retrieval tool calls such as database updates or external environment interactions where verification may be more challenging.

Why it matters for bot defense

For bot-defense engineers and CAPTCHA practitioners, SpecHop's methodology offers a principled way to reduce latency in multi-step information retrieval workflows while guaranteeing the final output consistency, which is crucial when accuracy and trustworthiness cannot be compromised. The concept of continuous speculation with asynchronous verification could inspire architectural designs in CAPTCHA verification pipelines that involve multi-stage challenge/response or external API calls, by allowing preemptive speculative processing that speeds interaction without sacrificing correctness.

However, the need for a reliable verifier to prevent error propagation highlights the risks in replacing verified steps with heuristics; unverified speculation can drastically reduce system reliability as observed here. This insight cautions CAPTCHA defenses to maintain rigorous validation even when optimizing for latency. The framework also emphasizes that balancing resource overhead (extra speculative threads and calls) with latency gains is key, which is a practical consideration in deployment scenarios with cost or compute constraints.

Cite

@article{arxiv2605_21965,
  title={ SpecHop: Continuous Speculation for Accelerating Multi-Hop Retrieval Agents },
  author={ Mehrdad Saberi and Keivan Rezaei and Soheil Feizi },
  journal={arXiv preprint arXiv:2605.21965},
  year={ 2026 },
  url={https://arxiv.org/abs/2605.21965}
}

Read the full paper

• arXiv:2605.21965 (abstract)
• arXiv:2605.21965 (PDF)