Callo: Serving Cache-Miss Requests with Speculative Decoding on Invalidated KV under Prefill-Decode Disaggregation

Jianjun Ou, Matthew LentzarXiv 2026 · arXiv

TL;DR

Callo is a new serving system that slashes the latency penalty of context edits in LLM agent sessions by using "invalidated" KV caches as a source for speculative decoding. By overlapping the mandatory re-prefill phase with drafting on stale data, Callo achieves up to a 1.19× speedup over vLLM without any loss in output quality.

What Problem Does This Paper Address?

Modern AI agents—like coding assistants—frequently work in long sessions where they edit their own history (e.g., modifying code, summarizing old logs, or masking errors). While "prefix caching" usually speeds up inference by reusing previous computations, even a small edit in the middle of a prompt invalidates the Key-Value (KV) cache for everything that follows.

This leads to a miss penalty: the system must re-compute the KV cache for the entire suffix (re-prefill) before it can start generating the next token. In high-performance "disaggregated" architectures, where prefill and decoding happen on separate GPUs, the decoding instance often sits idle waiting for the prefill instance to finish and transfer the new data. Callo aims to put that idle time to work.

Figure 1. One edited request. (a) vLLM, like other conventional systems supporting P/D, waits on the D-instance for the exact KV. (b) CALLO drafts on invalidated KV meanwhile, then verifies.
Figure 1: While standard systems (a) wait for the exact KV cache to arrive, Callo (b) starts drafting immediately using the invalidated state.

Methods

Callo introduces a "lossless" speculative execution framework designed specifically for disaggregated serving. Its core components include:

  1. Speculative Drafting on Invalidated KV: Instead of waiting, the decode instance repositions the "stale" KV cache from the previous request and uses the target model to start drafting tokens immediately.
  2. Layer-wise KV Streaming: As the prefill instance re-computes the exact KV cache, it streams updates to the decode instance layer-by-layer. This allows the drafting process to "heal" in-place, gradually using more accurate data as it becomes available.
  3. Smart Decode-Side Scheduling: To ensure that speculation doesn't slow down the rest of the system, Callo uses a three-part policy:
  4. Admission: Only speculate if there are spare resources and enough reusable "stale" tokens.
  5. Early Stop: Stop drafting if the model's confidence (logit gap) drops, indicating a high likelihood of a verification failure.
  6. Yielding: Speculative requests immediately give up their slots to non-speculative "ready" requests to prioritize guaranteed progress.

Datasets

The authors evaluated Callo using real-world agentic workflows:

  • SWE-bench Verified: 100 software engineering issues replayed using SWE-agent.
  • Model Families: Evaluation spanned three major models: Llama-3.3-70B (FP8), Gemma-4-31B (bf16), and Mistral-Small-3.2-24B (bf16).
  • Traces: Cluster-level simulations were driven by a week of real-world coding traffic traces from Azure.

Key Insights and Ideas

  • Stale KV is High-Quality Draft State: The most surprising finding is that "invalidated" KV caches are not just noise. Because much of the context remains the same after an edit, the stale cache is structurally very close to the exact one. For Llama-3.3-70B, 65% of 32-token draft windows were accepted in full despite being generated from "invalid" data.
  • The "Healing" Effect: Drafting quality improves as exact KV data arrives. The authors found that delivering updates layer-by-layer (rather than position-by-position) provides a better intermediate state for the drafter.
  • Predicting Failure via Hesitation: Mismatches between draft and exact tokens occur most frequently when the model itself is "hesitant" (i.e., the gap between the top-1 and top-2 logit is small). Callo uses this logit gap to implement an effective early-exit strategy for speculations.
Figure 2. Drafts made on invalidated KV (Llama-3.3-70B-Instruct FP8, SWE-agent L5, 32-token window, offline). (a) Miss steps whose first k drafts are all accepted (240 steps), against drafts on the exact KV and n-gram drafts. (b) Agreement by the draft’s top-1 minus top-2 logit gap (1,400 steps); below, the share of positions in each bin. (c) Accepted drafts when a share f of the invalidated KV’s position–layer cells is replaced by exact KV before drafting: CALLO’s delivery order and two reference orders (240 steps; bands: 95% confidence intervals).
Figure 2: (a) shows that invalidated KV is a much better draft source than n-grams; (b) illustrates how logit gaps predict acceptance.

Key Results

  • Speedups: On a two-GPU testbed, Callo achieved all-request speedups of 1.05–1.19× over vLLM at moderate loads.
  • Latency Reduction: For requests that specifically hit a cache miss, Callo hid roughly 49% of the miss penalty.
  • Efficiency: In cluster-scale simulations (96 GPUs), Callo maintained these gains across various Prefill-to-Decode (P:D) ratios, proving it can scale effectively in production environments.
  • Memory Overhead: Callo is memory-efficient, requiring only a small "scratch" buffer (roughly 0.24% of the KV pool) to manage in-flight speculations.
Latency breakdown showing how Callo shortens the critical path.
Figure 6: Callo shortens the request by 0.8s on average by overlapping prefill with drafting.

Limitations and Future Work

  • Task Specificity: Callo provides the most benefit for tasks with short, latency-sensitive replies (like agent actions). For tasks with extremely long outputs (e.g., long-form reasoning), the decode phase dominates, making the prefill-save a smaller percentage of total time.
  • Session Affinity: The system relies on the previous request's KV cache being resident on the same decode instance. If a load balancer moves a session to a new GPU, the "stale" state is lost.
  • Future Directions: The authors suggest exploring "draft trees" that branch where the model hesitates, or combining Callo with other techniques like "budgeted repair" of KV caches to further improve draft acceptance.

Summary updated

Abstract

Agent sessions may involve frequent context edits, which effectively invalidate cached KV state and force requests to wait for re-prefill before decoding. We present Callo, a disaggregated serving system that leverages invalidated KV for speculative drafts to reduce this latency, while verifying drafts against the exact KV after prefill before committing tokens. Callo makes effective use of decode resources by scheduling speculations during periods of underutilization and preempting speculations when drafts are likely to not be accepted. We evaluated Callo on a two-GPU testbed using SWE-agent sessions across three model families, observing all-request speedups of 1.05-1.19x over vLLM at moderate load. We demonstrate that these gains are also realized at scale through cluster-level simulations driven by real-world traces.
BibTeX
@misc{ou2026callo,
  author = {Jianjun Ou and Matthew Lentz},
  title = {{Callo: Serving Cache-Miss Requests with Speculative Decoding on Invalidated KV under Prefill-Decode Disaggregation}},
  year = {2026},
  eprint = {2611.18459},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.18459},
}
Figure