Callo: Serving Cache-Miss Requests with Speculative Decoding on Invalidated KV under Prefill-Decode Disaggregation
Organizations: Duke University
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.
Figures & tables
| Per miss request | |||||
| Workload | Prompt | Reply | Miss | Prefill | Reusable |
| mean | mean | rate | p50/p90 | p50/p90 | |
| Llama L5 | 13.5k | 117 | 79% | 3.1k/8.9k | 2.5k/7.4k |
| Llama L10 | 15.3k | 121 | 58% | 8.3k/18.3k | 7.6k/16.8k |
| Gemma L5 | 15.4k | 199 | 74% | 5.2k/8.3k | 4.2k/7.2k |
| Gemma L10 | 17.5k | 189 | 53% | 10.9k/15.5k | 9.8k/14.5k |
| Property of invalidated KV | Design choice |
|---|---|
| Close to the exact KV | Inherit and reposition (§ 4.2 ) |
| Near-exact acceptance (Fig. 2 a) | Target-model drafting (§ 4.1 ) |
| Errors at near-ties (Fig. 2 b) | Cumulative early stop (§ 4.5 ) |
| Heals layer by layer (Fig. 2 c) | Layer-wise streaming (§ 4.3 ) |
| Mixing never hurts (Fig. 2 c) | Lock-free drafting (§ 4.3 ) |
| Light (12%) | Moderate (52%) | Full (100%) | ||||
|---|---|---|---|---|---|---|
| Workload | Miss | All | Miss | All | Miss | All |
| Llama L5 | 1.13 | 1.10 | 1.19 | 1.14 | 1.32 | 1.27 |
| Llama L10 | 1.24 | 1.17 | 1.24 | 1.19 | 1.21 | 1.17 |
| Gemma L5 | 1.07 | 1.05 | 1.06 | 1.05 | 1.10 | 1.09 |
| Gemma L10 | 1.11 | 1.07 | 1.11 | 1.08 | 1.12 | 1.10 |
| Mistral L5 | 1.15 | 1.14 | 1.16 | 1.14 | 1.16 | 1.15 |
| Variant | Folded | Speedup | Accepted |
|---|---|---|---|
| Callo (fixed-tie greedy) | 49% | 1.15 | 22.6 |
| Callo -Stream | 4.5% | 1.01 | – |
| any-max greedy verification | 54% | 1.17 | 24.4 |
| speculative sampling, | 45% | 1.14 | 21.4 |
| n-gram drafts | 18% | 1.05 | 7.5 |
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
| Sessions | Requests | Accepted (of 32) | Whole window |
|---|---|---|---|
| 3 looping at the limit | 183 | 30.2 | 81% |
| 6 others at the limit | 392 | 25.5 | 64% |
| 86 below the limit | 825 | 24.2 | 58% |
| All | 1,400 | 25.4 | 62.5% |
| All but the 3 looping | 1,217 | 24.6 | 59.7% |
| Logit gap | .25 | .25–.5 | .5–1 | 1–2 | 2–4 | 4–8 | 8 |
|---|---|---|---|---|---|---|---|
| Llama-3.3-70B | 0.63 | 0.69 | 0.89 | 0.97 | 1.00 | 1.00 | 1.00 |
| Mistral-Small-3.2 | 0.70 | 0.92 | 0.99 | 1.00 | 1.00 | 1.00 | 1.00 |
| Gemma-4-31B | 0.57 | 0.78 | 0.86 | 0.95 | 1.00 | 1.00 | 1.00 |
| Refused | |||||||
|---|---|---|---|---|---|---|---|
| Load | Misses | Spec. | Budget | Evicted | Scratch | Slot | Cut |
| Light | 280 | 274 | 6 | 0 | 0 | 0 | 1.8% |
| Moderate | 1,247 | 1,070 | 173 | 4 | 0 | 0 | 4.3% |
| Full | 1,103 | 755 | 344 | 4 | 0 | 0 | 4.0% |
| Past cap. | 1,271 | 652 | 402 | 54 | 163 | 0 | 3.5% |
| Moderate load | 90% load | |||
|---|---|---|---|---|
| Setting | Miss | Others | Miss | Others |
| 1.162 | 1.024 | 1.193 | 1.071 | |
| 1.161 | 1.026 | 1.194 | 1.076 | |
| 1.155 | 1.024 | 1.195 | 1.083 | |
| No early stop | 1.164 | 1.027 | 1.194 | 1.074 |
| 1.134 | 1.048 | 1.182 | 1.091 | |
| P:D | Load | Discarded | Total accepted | Accepted/spec. |
|---|---|---|---|---|
| reduced by | retained | default / disabled | ||
| 1:2 | Moderate | 35.4% | 98.1% | 22.3 / 22.5 |
| 90% | 34.1% | 96.7% | 26.0 / 26.7 | |
| 1:1 | Moderate | 30.3% | 99.1% | 19.7 / 19.8 |
| 90% | 28.5% | 96.2% | 22.7 / 23.2 | |
| 2:1 | Moderate | 29.3% | 94.5% | 16.0 / 16.3 |
| 0.045 sessions/s | 0.04 | ||
| vLLM | Callo | vLLM | |
| P-instance cache hit rate | 47.7% | 60.4% | 70.6% |
| P-instance tokens computed | 7.64M | 7.11M | 5.20M |
| Sessions in flight | 13 29 | 11 12 | 11 11 |
| Measured sessions finished | 23 of 27 | 26 of 27 | 24 of 24 |
| Measured requests unissued | 90 | 3 | 0 |
| D-instance batch limit | 16 | 2 | 4 | 6 |
| vLLM latency error | 2.2% | 2.2% | 3.2% | 5.7% |
| Gain inside testbed CI | 7/8 | 6/8 | 6/8 | 7/8 |
| Gain error | ||||
| Speculating requests | % | % | % | % |
| Accepted drafts | % | % | % | % |
| P:D | Load | vLLM+CD | Callo | Callo +CD | Callo +budget |
|---|---|---|---|---|---|
| 1:2 | 12% | 1.00 | 1.11 | 1.10 | 1.05 |
| 52% | 1.03 | 1.16 | 1.17 | 1.15 | |
| 90% | 1.14 | 1.26 | 1.32 | 1.31 | |
| 1:1 | 12% | 1.00 | 1.12 | 1.09 | 1.05 |
| 52% | 1.02 | 1.13 | 1.11 | 1.12 | |
| 90% | 1.08 | 1.18 | 1.19 | 1.21 |
LLM Inference Serving
Large language model inference serving studies how to run model requests efficiently while meeting latency, throughput, cost, and energy goals.
See all 78 papers