Speculating on the Past: Lossless Reuse of Stale KV Caches via Self-Speculative Verification

Non-append edits in agentic LLM serving invalidate the cached suffix, forcing a choice between exact refresh, which delays generation, and approximate reuse, which can change the generated action. StaleSpec instead treats the position-aligned stale cache as a self-speculative proposal: the model decodes from the stale view while the exact post-edit suffix is recomputed in parallel, then commits only after fresh verification. The committed distribution is identical to refreshed-context decoding regardless of proposal quality; staleness affects only acceptance and latency. Across controlled 8K–32K edited turns, StaleSpec reduces committed latency by $3$–$13\%$, and under KV-packed prefill–decode serving it improves queue-inclusive throughput by $11$–$19\%$ across three MoE deployments. A cost-aware gate selects profitable turns, and StaleSpec composes with lossless decode-side acceleration. Approximate stale reuse changes $64$–$99\%$ of tokens and preserves only $0$–$19\%$ of next actions, while StaleSpec remains exact.