- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper proposes LOCKS, which stores a rank-r svd summary for each KV page, reconstructs within-page logits to estimate page LSE, and selects pages without reading keys. It tracks the exact-LSE oracle at very small budgets on ruler, longbench and aime, and on gh200 it speeds up decode and allows larger batches when KV is offloaded.
Critical strengths
- The page-local vs shared basis analysis is convincing.
- Results at tight budgets are strong, especially on reasoning where quest and eviction methods collapse.
- Training-free and integrated into vLLM with CUDA graphs, easy to deploy.
Critical weaknesses
- The offloading results depend on gh200 c2c. On a normal pcie server the speedup may look very different, and this is not evaluated.
- The summary scan is still linear in context length, and there is no breakdown of scan time vs attention time.
Questions for authors
- How are the eviction baselines configured at small b, e.g. when their fixed buffer is larger than b?
- Any results with pcie offloading?
5 comments
Author Response #2 to Reviewer da6z
Summary-scan cost and practical decoding performance
The summary scan remains linear in context length. LOCKS reduces the work per candidate page and performs attention on the selected token budget. For B = 16 and d = 128, an r4i4 summary occupies 490 bytes per page, KV head, and layer, compared with 4,096 bytes for the corresponding bf16 keys. We now report the scan and attention costs separately.
TABLE B: Selection, attention, and KV preparation. GLM-4-9B-Chat-1M on GH200, batch size 1. GPU kernel times are ms/token across all 40 layers, shown as 128K / 512K. Fixed-budget methods use b = 2048, and RaBitQCache uses p = 0.65. Selection includes scoring, GQA aggregation, top-k, and updates. KV preparation includes gathering, transfers, and key reconstruction. These are optimized implementations. (Updated Table 5(a), with upstream and optimized comparisons in Appendix B.5.1.)
| Method | Attention | Selection | KV preparation |
|---|---|---|---|
| FullKV (FA3) | 3.48 / 12.18 | 0 / 0 | 0 / 0 |
| FullKV (FlashInfer) | 3.34 / 11.77 | 0 / 0 | 0 / 0 |
| Quest | 1.39 / 1.83 | 2.49 / 3.43 | 0 / 0 |
| ShadowKV | 0.33 / 0.34 | 4.53 / 5.48 | 1.22 / 1.26 |
| ParisKV | 0.34 / 0.34 | 4.03 / 5.88 | 0.16 / 0.16 |
| RaBitQCache | 1.51 / 3.31 | 3.51 / 11.97 | 0 / 0 |
| Exact LSE | 0.36 / 0.36 | 2.62 / 7.61 | 0 / 0 |
| LOCKS r4i4 | 0.33 / 0.34 | 1.56 / 3.48 | 0 / 0 |
Scan cost grows with context, while selected-page attention stays nearly constant. Within LOCKS, page-summary scoring takes 0.766 and 2.485 ms/token at 128K and 512K, respectively, while selected-page attention takes 0.334 and 0.339 ms/token. At 512K, selection plus attention totals 3.82 ms/token, compared with 11.77 for FlashInfer and 7.97 for exact-LSE selection plus attention. Complete model decode steps take 10.95 ms for LOCKS versus 19.22 ms for FlashInfer. (Updated Table 5(b) and Figure 4(b).)
The additional retrieval baselines also permit a comparison of quality and completion time. Table C accounts for each method's output lengths, since faster individual steps alone need not produce faster completed answers.
TABLE C: Accuracy and mean completion time. Qwen3-4B on GH200, batch size 1, GPU-resident KV. (Updated Figure 5 and Table B.13.)
| Method | AIME26 score (%) | AIME26 time (s) | LCB-v6 score (%) | LCB-v6 time (s) |
|---|---|---|---|---|
| FullKV (FA3) | 59.2 | 87.1 | 47.4 | 78.1 |
| Quest (b = 2048) | 33.3 | 138.3 | 20.0 | 127.5 |
| ParisKV (b = 2048) | 54.2 | 142.9 | 45.1 | 131.1 |
| RaBitQCache (p = 0.85) | 55.0 | 130.3 | 43.4 | 105.7 |
| LOCKS r4i4 (b = 2048) | 65.8 | 77.2 | 47.4 | 64.3 |
LOCKS achieves higher AIME26 accuracy and matches FullKV's LCB-v6 accuracy, with 11% and 18% shorter mean completion times, respectively. It also improves accuracy and completion time over the listed retrieval baselines. These batch-size-1 results establish practical benefits with GPU-resident KV.
Author Response #3 to Reviewer da6z
Offloading over PCIe
We added PCIe 5.0 host-memory offloading measurements on one H200 NVL GPU. LOCKS keeps KV in host memory and uses a GPU hot cache for retrieved pages. This evaluates the CPU–GPU connection raised by the reviewer without relying on GH200's NVLink-C2C link.
TABLE D: Batched serving with PCIe KV offloading. GLM-4-9B-Chat-1M, LOCKS r4i4 at b = 2048. Dense backends keep KV in GPU memory. Mean inter-token latency (ITL) and aggregate throughput are reported at the shown batch sizes. Speedup is relative to FlashInfer, the faster dense backend at each context. (Updated Appendix C.7, Table C.9.)
| Context | Method | Batch size | Mean ITL (ms) | Throughput (tok/s) | Speedup |
|---|---|---|---|---|---|
| 64K | FA3 | 21 | 41.0 | 511.7 | 0.87× |
| 64K | FlashInfer | 20 | 33.9 | 590.7 | 1.00× |
| 64K | LOCKS r4i4 | 58 | 41.9 | 1,385.7 | 2.35× |
| 128K | FA3 | 10 | 34.3 | 291.2 | 0.93× |
| 128K | FlashInfer | 10 | 32.0 | 312.4 | 1.00× |
| 128K | LOCKS r4i4 | 32 | 37.0 | 864.2 | 2.77× |
| 256K | FA3 | 5 | 34.4 | 145.1 | 0.93× |
| 256K | FlashInfer | 5 | 32.2 | 155.2 | 1.00× |
| 256K | LOCKS r4i4 | 17 | 35.8 | 474.2 | 3.06× |
Offloading frees GPU memory for larger batches while the hot cache reduces repeated host transfers. At 128K, LOCKS serves 32 sequences versus 10 for FlashInfer, yielding 2.77× aggregate throughput, with mean ITL of 37.0 versus 32.0 ms. Across 64K–256K, the throughput advantage is 2.35–3.06×. The table reports both latency and batch size explicitly, showing that the throughput gain comes from greater serving capacity. These measurements demonstrate that useful offloading gains also persist on the evaluated PCIe system.
Author Response #1 to Reviewer da6z
We thank the reviewer for the careful review and concrete questions about resource accounting, baseline settings, and PCIe serving.
Resource accounting and small-budget baseline settings
Equal attended-token budgets do not imply equal storage or read costs. Our sweeps over the attended-token budget b evaluate selection quality. We now complement them with an explicit read-cost comparison and additional selection-based baselines, ParisKV and RaBitQCache (ICML 26).
The small-budget configurations account for buffers and protected tokens as follows:
TABLE A: Quality with read costs accounted for. Qwen3-4B. Estimated reads include attended KV, selection state, and maintenance, including protected tokens, buffers, and dense phases. We use the mean input length of AIME26 and MATH-500 and a common 32K-token reference generation. (Updated Table 3 and Appendix B.4.)
We count each persistent input once per operation to reduce dependence on kernel implementation. For Quest and LazyEviction, we assume fully overlapping selections within each GQA group, favoring their read estimates. At b = 512, LOCKS matches or exceeds the listed sparse baselines' accuracy with 28–48% fewer estimated reads. This comparison accounts for costs beyond the nominal token budget while keeping read volume distinct from retained storage.