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.
Methods
Callo introduces a "lossless" speculative execution framework designed specifically for disaggregated serving. Its core components include:
- 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.
- 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.
- Smart Decode-Side Scheduling: To ensure that speculation doesn't slow down the rest of the system, Callo uses a three-part policy:
- Admission: Only speculate if there are spare resources and enough reusable "stale" tokens.
- Early Stop: Stop drafting if the model's confidence (logit gap) drops, indicating a high likelihood of a verification failure.
- 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.
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.
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