SpecHop: Continuous Speculation for Accelerating Multi-Hop Retrieval Agents

Large language models increasingly use external tools such as web search and document retrieval to solve information-intensive tasks. However, multi-hop tool use in complex tasks introduces substantial latency, since the model must repeatedly wait for tool observations before continuing. We study how to accelerate such trajectories without changing the final trajectory the model would have taken without acceleration, assuming access to faster but less reliable speculator tools. We develop a theoretical framework for lossless speculation in multi-hop tool-use settings, characterizing the optimal achievable latency gain. We propose SpecHop, a continuous speculation framework that maintains multiple speculative threads, verifies predicted observations asynchronously as target tool outputs arrive, commits correct branches, and rolls back incorrect ones. This preserves task accuracy while reducing wall-clock latency. We show that SpecHop can approach the oracle latency gain with sufficient active threads. Empirically, we evaluate SpecHop on retrieval-augmented multi-hop tasks and find that its latency gains closely match theoretical predictions, reaching up to 40% latency reduction in some settings.