acceptodds
Under review as a conference paper at ICLR 2027

LOCKS: Page-Local Compact Key Summaries for Efficient Long-Context Decoding

Abstract

Serving large language models at long context is bottlenecked by the key-value (KV) cache, which is read at every decode step. We find that attention keys are approximately low-rank within pages. A single low-rank projection shared across pages can miss page-specific directions; fitting a basis to each page better identifies the pages receiving the most attention at comparable stored selector cost. LOCKS stores a rank- spectral summary per page, reconstructs its within-page logits, and selects pages by log-sum-exp mass without reading candidate keys or values. It stays within about a point of FullKV on LongBench-v1, tracks the read-every-key exact-LSE oracle on RULER down to the smallest budgets, and retains quality furthest under tight budgets on AIME26 and MATH-500. At a -token budget it matches FullKV aggregate quality beyond K context while attending about % of tokens. Across ranks -, summaries use - of full-KV bytes. On GH200 with GPU-resident KV, LOCKS reduces complete decode-step time by at K context. With full KV offloaded to Grace memory, it reaches - the faster dense backend's aggregate throughput at K-K by serving larger batches.

Primary area:
foundation or frontier models, including LLMs
Keywords:
long-context LLM inference, KV-cache optimization, sparse attention, page-level attention selection, low-rank key summaries

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_da6zOpenReview ↗
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
AuthorsOpenReview ↗

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:

  • R-KV: The 128-token accumulation buffer is additional to the nominal budget b. The retained set grows to b + 128 and then compacts to b before attention. A budget below 128 is therefore valid, although temporary storage exceeds b.
  • LazyEviction: Its published 363-token recent window cannot fit the smallest budgets. We scale it as W = max(1, round(363b/1492)), giving W = 16 and 31 at b = 64 and 128. This is our adaptation. After eviction, each query head retains W recent and b − W older tokens. Attention precedes scheduled eviction, so it also reads tokens accumulated between evictions.
  • TriAttention: The 128-token setting is an update interval. The method preserves the full prompt of length P, selects up to max(1, b − P) older generated tokens, and retains tokens generated since the last update. Attention remains dense while the context is at most b + 128. Thus, b is not a hard cap on its attended set.

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.)

Method / budgetEst. reads (MiB/token)AIME26 (%)MATH-500 (%)
FullKV2,320.959.294.0
Quest (b = 512)332.90.043.5
R-KV (b = 2048)289.624.290.5
TriAttention (b = 2048)297.445.091.5
LazyEviction (b = 2048)322.734.292.0
ParisKV (b = 1024)402.351.789.0
LOCKS r4i4 (b = 256)173.755.090.5
LOCKS r4i4 (b = 512)209.564.292.0

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.

AuthorsOpenReview ↗

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.)

MethodAttentionSelectionKV preparation
FullKV (FA3)3.48 / 12.180 / 00 / 0
FullKV (FlashInfer)3.34 / 11.770 / 00 / 0
Quest1.39 / 1.832.49 / 3.430 / 0
ShadowKV0.33 / 0.344.53 / 5.481.22 / 1.26
ParisKV0.34 / 0.344.03 / 5.880.16 / 0.16
RaBitQCache1.51 / 3.313.51 / 11.970 / 0
Exact LSE0.36 / 0.362.62 / 7.610 / 0
LOCKS r4i40.33 / 0.341.56 / 3.480 / 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.)

MethodAIME26 score (%)AIME26 time (s)LCB-v6 score (%)LCB-v6 time (s)
FullKV (FA3)59.287.147.478.1
Quest (b = 2048)33.3138.320.0127.5
ParisKV (b = 2048)54.2142.945.1131.1
RaBitQCache (p = 0.85)55.0130.343.4105.7
LOCKS r4i4 (b = 2048)65.877.247.464.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.

AuthorsOpenReview ↗

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.)

ContextMethodBatch sizeMean ITL (ms)Throughput (tok/s)Speedup
64KFA32141.0511.70.87×
64KFlashInfer2033.9590.71.00×
64KLOCKS r4i45841.91,385.72.35×
128KFA31034.3291.20.93×
128KFlashInfer1032.0312.41.00×
128KLOCKS r4i43237.0864.22.77×
256KFA3534.4145.10.93×
256KFlashInfer532.2155.21.00×
256KLOCKS r4i41735.8474.23.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.

Reviewer_ndFEOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes LOCKS, a training-free sparse attention framework for efficient long-context LLM decoding. The method constructs compact page-local key summaries using truncated singular value decomposition (SVD). During decoding, it uses these summaries to approximate token-level attention logits and compute page-level log-sum-exp (LSE) scores, which are then used to select important KV pages under a fixed attention budget.

The authors provide theoretical analysis relating attention mass coverage to attention output error, and present experiments on LongBench, RULER, InfiniteBench, AIME26, and MATH-500. They also implement LOCKS as a vLLM attention backend and evaluate its inference efficiency on GH200 hardware.

Critical strengths

S1. Page-local representation with supporting empirical evidence.

The paper provides evidence that page-specific low-rank bases can estimate attention relevance more accurately than shared low-rank projections under comparable summary storage budgets. The matched-storage experiments help motivate the page-local design.

S2. Practical implementation and promising results under tight attention budgets.

The authors implement the method as a vLLM attention backend and demonstrate promising accuracy under aggressive sparse attention budgets. The evaluation includes long-context retrieval, question answering, and long-form reasoning tasks, as well as measured decoding acceleration in very long-context settings.

Critical weaknesses

W1. Limited Algorithmic Novelty and Insufficient Justification of the Proposed Design

The novelty of LOCKS does not lie in low-rank decomposition itself, but rather in applying standard truncated SVD independently to each KV page and using the resulting summaries for approximate page-level attention mass estimation. While the page-local design is intuitive, the overall approach largely combines existing techniques, including low-rank key representations, LSE-based attention scoring, and hard TopK page selection.

Although the authors demonstrate advantages over shared-basis representations, the paper does not sufficiently justify the necessity of its relatively complex design. In particular, it remains unclear whether reconstructing approximate token-level logits and performing LSE aggregation provides substantial benefits over simpler page-local statistical summaries under matched memory and computational budgets.

Furthermore, the theoretical guarantees mainly apply to unquantized low-rank summaries, whereas the practical implementation relies on quantized representations. The relationship between these theoretical results and the actual accuracy improvements is not sufficiently established.

W2. Insufficient Empirical Validation and Limited Practical Efficiency Advantages

The experimental evaluation does not convincingly establish the practical advantages of LOCKS over recent strong KV retrieval and sparse attention systems.

First, the efficiency comparison omits important baselines such as ParisKV (ICML 2026) and ShadowKV (ICML 2025). ShadowKV is already included in the accuracy evaluation but not in the end-to-end latency comparison, making it difficult to assess the claimed efficiency advantages over closely related low-rank retrieval methods.

Second, LOCKS introduces nontrivial overhead from per-page SVD construction, full-summary scanning, approximate token-level attention scoring, LSE aggregation, and hard TopK selection. However, the paper lacks a detailed breakdown of these costs and a systematic analysis of how the one-time summary construction overhead is amortized across different generation lengths.

Third, the reported speedups are highly dependent on the workload. Table B.8 shows only 1.00–1.08× speedup over FlashInfer at 16K–64K contexts, while Table B.9 reports slightly higher decoding latency than Quest during long generation (8.10 vs. 8.04 ms). Moreover, the reported 3.82–4.22× throughput gains largely benefit from KV offloading and larger batch sizes rather than equivalent reductions in per-token decoding latency.

Finally, the evaluation does not fully establish a consistent quality–efficiency advantage across tasks and resource budgets. Some RULER tasks still exhibit substantial degradation under tight attention budgets, even when page selection closely approximates the exact-LSE oracle. Additionally, the nominal token budgets do not always correspond to identical actual KV reads or cache residency across baselines, complicating direct comparisons.

Overall, the paper needs stronger comparisons with recent systems, more comprehensive accuracy–latency–memory tradeoff evaluations, and a detailed analysis of selection overhead to demonstrate that its additional computational complexity is justified.

Questions for authors

The proposed method still estimates token-level attention logits across the entire context before aggregating them into page-level LSE scores and performing TopK selection. Therefore, the selection process remains linear in sequence length.

What is the computational advantage of this design compared with a simpler baseline that directly computes QK dot products for all keys, aggregates them into page-level LSE scores, and selects the TopK pages?

Could the authors provide a direct latency comparison, including the overhead of SVD construction, summary scoring, and TopK selection, to demonstrate whether the additional complexity of the low-rank representation is justified?

7 comments
AuthorsOpenReview ↗

Author Response #1 to Reviewer ndFE

We thank the reviewer for their careful assessment and constructive feedback. We appreciate their recognition of the evidence supporting page-local representations and the practical results under tight attention budgets.


Contribution and comparison with simpler page-local summaries

The core contribution is a compact, page-local key representation for estimating the combined attention mass of a page. SVD, LSE, and TopK are the building blocks. The design uses each page's own key geometry to capture within-page logit variation, enabling mass-based selection without reading every full-dimensional key.

Our theoretical analysis connects reconstruction and page-score errors to retained attention mass and attention-output error, providing a principled connection between summary construction, scoring, and page selection. It also identifies failure cases for fixed shared low-rank projections, motivating the page-local design.

Why reconstruct logits and aggregate with LSE? A page's attention contribution depends on all of its token logits. A mean-key score omits their spread, while a maximum-logit bound does not account for how many tokens contribute substantial attention mass. LOCKS approximates the within-page logits and applies their LSE, retaining this distinction within the low-rank representation.

Appendix A.6 makes the connection to simpler moment summaries explicit: the quadratic approximation retains the mean contribution and a low-rank variance correction but omits higher-order terms. Reconstructed-logit LSE retains the nonlinear aggregation of the approximate logits. This analysis motivates the scorer; the concrete simpler-summary comparison below uses Quest.

Comparison with a simpler page-local summary. Quest stores coordinate-wise minima and maxima. With 16-token pages and 128-dimensional keys, it uses 512 bytes per page and KV head in each layer using summaries. LOCKS r4i4 uses 490 bytes, including scales.

TABLE A: Llama-3.1-8B, b = 512 for the sparse methods. Scores are percentages. Estimated reads are averaged over the LongBench-v1, RULER-16K, and RULER-32K reference workloads and include attention, selection, and maintenance under ideal reuse.

MethodSummary bytes/page/head/layerEst. reads (MiB/token)LongBench-v1RULER-16KRULER-32K
FullKV—2,477.147.094.388.8
Quest512358.445.979.372.1
LOCKS r4i4490210.347.091.486.0

LOCKS achieves higher accuracy than this simpler summary at comparable per-page representation storage and lower estimated read cost. In the separate GH200 kernel measurements on GLM-4-9B-Chat-1M (batch 1, b = 2048), total selection costs at 128K/512K are 1.56/3.48 ms for LOCKS and 2.49/3.43 ms for Quest, across all 40 layers (revised Table 5). LOCKS therefore has lower selection cost at 128K and comparable selection cost at 512K in this setting.

This accuracy difference also matters for end-to-end efficiency. On AIME26 and LCB-v6 with Qwen3-4B at b = 2048, LOCKS achieves higher accuracy than Quest with fewer generated tokens leading to shorter completion times (revised Fig. 5 and Table B.13; discussed further in Comment 4).

The matched-storage shared-basis experiments in revised Table 1 separately establish the value of fitting locally: at approximately 488–490 bytes per page and KV head, page-local rank-4 fitting achieves 90.5% page recall, versus 81.3–81.9% for shared rank-20 bases retaining page-local centroids. These experiments address fitting scope, while Table A addresses the simpler extrema-summary alternative.

We have clarified these design distinctions in the revised manuscript.

AuthorsOpenReview ↗

Author Response #2 to Reviewer ndFE

Guarantees and measured effects of quantized summaries

The revised analysis explicitly covers quantized summaries. Appendix A.4 extends the score, retained-mass, and attention-output guarantees by separating rank truncation from summary and query quantization. Attention is renormalized over the selected pages using the original queries, keys, and values.

Quantized page-score error. Fix a decode step. Let μj\mu_j be the page centroid, Dj∈RB×dD_j\in\mathbb{R}^{B\times d} its centered-key matrix, and VjV_j the matrix of its top-rr orthonormal right singular vectors. For i∈Pji\in P_j, define the unquantized reconstruction by k~i=μj+VjVj⊤(ki−μj)\tilde{k}_i=\mu_j+V_jV_j^\top(k_i-\mu_j).

A superscript QQ denotes decoded quantized tensors. The key k~iQ\tilde{k}_i^Q is reconstructed from the quantized centroid, basis, and coefficients. Let ρj\rho_j bound ∥k~iQ−k~i∥2\lVert\tilde{k}_i^Q-\tilde{k}_i\rVert_2 for every token in the page, and define MjQ=max⁡i∈Pj∥k~iQ∥2M_j^Q=\max_{i\in P_j}\lVert\tilde{k}_i^Q\rVert_2 and qj⊥=(I−VjVj⊤)qq_j^\perp=(I-V_jV_j^\top)q. Let σj,r+1\sigma_{j,r+1} be the first discarded singular value of DjD_j.

For the exact page LSE sj(q)s_j(q) and reconstructed page LSE sjQ(q)s_j^Q(q) scored with qQq^Q, both using logits scaled by 1/d1/\sqrt{d},

\leq \frac{\lVert q_j^\perp\rVert_2\\,\sigma_{j,r+1}}{\sqrt{d}} +\frac{\lVert q\rVert_2\\,\rho_j}{\sqrt{d}} +\frac{\lVert q^Q-q\rVert_2\\,M_j^Q}{\sqrt{d}} =:\epsilon_j^Q(q).$$ The terms account for **rank truncation, summary quantization, and query quantization**, respectively. The last term vanishes when $q^Q=q$. Cauchy–Schwarz bounds the logit perturbations, and log-sum-exp's 1-Lipschitz property transfers the bound to page scores. Appendix A.4 bounds the summary perturbation using quantization steps and stored scales, including interactions between basis and coefficient errors. The decoded quantized basis need not be orthonormal. **Consequence for the deployed selection rule.** For $G$ query heads sharing a KV head, let $\eta_Q=\max_{g,j}\epsilon_j^Q(q_g)$. Normalize each head's estimated page masses and average them across the group. Let $S_Q$ contain the mandatory pages and fill its remaining slots with the pages having the **largest averaged estimated masses**. Then $$\bar{\gamma}(S_Q)\geq e^{-4\eta_Q}\bar{\gamma}^{\star}.$$ Here, $\bar{\gamma}$ is the exact group-mean retained mass, and $\bar{\gamma}^{\star}$ is its optimum under the same page budget and mandatory-page constraints. If every value vector has Euclidean norm at most $R$, the mean Euclidean attention-output error across the $G$ heads, relative to full attention, is at most $2R(1-e^{-4\eta_Q}\bar{\gamma}^{\star})$. Full statements and proofs appear in Appendix A.4, Theorem 2 and Corollary 3. **Measured effect of quantization.** To isolate quantization, we hold the page-local construction, rank, page size, attended-token budget, and selection rule fixed. **TABLE B: Llama-3.1-8B, B = 16, r = 4, b = 1024.** Storage is per page, KV head, and layer. | Summary precision | Bytes/page | Page recall (%) | Retained mass (%) | |:--|--:|--:|--:| | Unquantized reference | 1,408 | 85.48 | 85.11 | | r4i8 | 746 | 85.37 | 85.11 | | **r4i4** | **490** | **83.92** | **85.02** | The deployed r4i4 summary reduces the bf16-equivalent payload from **1,408 to 490 bytes**, a **2.9-fold reduction**, with decreases of **1.56 percentage points in recall** and **0.09 percentage points in retained mass**. The extension establishes how quantization enters the guarantee, while this control measures its effect on selection in the evaluated configuration.
AuthorsOpenReview ↗

Author Response #3 to Reviewer ndFE

Computational cost analysis and advantage over direct QK–LSE selection

LOCKS still scans the context linearly. Its advantage is lower input traffic and arithmetic per page. Direct Exact-LSE selection reads every full-dimensional key, computes QK logits, aggregates page LSE, and selects TopK pages. LOCKS performs the same type of aggregation using compact page summaries.

For each completed page, a query is projected into its rank-r basis and combined with token coefficients and the centroid. Scoring work changes from O(Bd) to O(dr + Br + d) per query and page. With B = 16, d = 128, and r = 4, the stored scoring input is 490 bytes per page and KV head for r4i4, versus 4,096 bytes for the original bf16 keys.

The compact summaries provide a further practical advantage over direct QK–LSE selection by enabling page selection while the backing KV cache is offloaded. Direct QK–LSE selection requires accessing every full-dimensional key at each decoding step. LOCKS instead selects pages using GPU-resident summaries, fetching only selected pages missing from the GPU hot cache. This reduces GPU memory requirements per request and enables larger batches, yielding 3.84–4.60× the aggregate decoding throughput of the faster dense backend (revised Table 4).

Direct latency comparison. We include the exact baseline requested by the reviewer.

TABLE C: GLM-4-9B-Chat-1M, GH200, batch 1, b = 2048. Entries show 128K/512K context. Selection and attention are GPU kernel times in ms/token summed across all 40 layers. ITL is complete decoding-step latency (revised Table 5 and Table B.11).

MethodSelection (ms)Attention (ms)Complete ITL (ms)
Exact LSE2.62/7.610.36/0.3610.31/15.13
LOCKS r4i41.56/3.480.33/0.349.34/10.95

At 512K, LOCKS reduces selection time by 54% and complete decoding-step latency by 28% relative to exact-LSE selection. Selection plus attention takes 3.82 ms, versus 7.97 ms for Exact LSE.

Selection-cost breakdown. The page-summary scoring row includes the summary scan, approximate token-logit computation, and LSE aggregation in the scorer.

TABLE D: LOCKS r4i4, same model, hardware, batch, and budget. GPU kernel times in ms/token across all 40 layers, averaged over decode steps (revised Table 5(b)).

Component128K512K
Page-summary scoring0.7662.485
Current-page scoring0.1050.112
GQA aggregation0.1940.266
TopK and indices0.4710.583
Summary build/update0.0280.036

Each completed page is fitted once using its 16 × 16 Gram matrix, and its summary is reused. During generation, the build/update row includes constructing new summaries as pages fill and quantizing them; the current page is scored directly until completion.

Added prefill cost and amortization. For a reference generation length T, including the first generated token, the additional prefill cost per generated token is added TTFT divided by T.

TABLE E: Added TTFT and decoding savings relative to FA3, from the GH200 batch-1 measurements. Times are in milliseconds. Decode saving is FA3 ITL minus LOCKS ITL. Estimated offset steps divide added TTFT by decode saving using full-precision timings, rounded up to a whole decode step.

ContextAdded TTFTAdded cost/token, T = 128Added cost/token, T = 1024Decode saving/stepEst. decode steps to offset
64K178.81.3970.1750.45398
128K345.72.7010.3381.34259
512K1,225.69.5751.1978.49145

The added prefill cost can outweigh decoding savings for short generations and is amortized over longer ones.

Reviewer_GRHLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes LOCKS, a training-free sparse attention method for efficient long-context LLM decoding. The main idea is to exploit the approximately low-rank structure of attention keys within individual KV-cache pages. Rather than using a shared low-rank projection, LOCKS constructs a separate spectral basis for each page and uses the resulting compact representation to approximate token-level attention logits and estimate page attention mass through log-sum-exp (LSE). This allows the method to select relevant pages without reading the full KV cache. The paper also provides theoretical justification for page-local representations and establishes bounds relating reconstruction error to attention coverage and output error.

The authors evaluate LOCKS on long-context retrieval, question answering, and reasoning benchmarks, including LongBench, RULER, InfiniteBench, AIME26, and MATH-500. The results show that LOCKS generally outperforms existing sparse attention methods under tight attention budgets while maintaining accuracy close to full attention. The method is integrated into vLLM and achieves a 1.8× decoding speedup at 512K context and 3.82–4.22× higher aggregate throughput with KV offloading on GH200 hardware.

Critical strengths

The paper identifies a limitation of shared low-rank projections, which may fail to capture important directions that vary across KV-cache pages. Fitting a separate spectral basis to each page is a reasonable approach. The experiments show page-local representations improve attention-mass estimation and page-selection accuracy.

The paper establishes a connection between exact-LSE page selection and worst-case attention-output error. It also characterizes limitations of fixed shared projections and provides error bounds for page-local low-rank approximations.

The experiments cover diverse tasks, including retrieval, long-document QA, and mathematical reasoning. LOCKS performs particularly well under restrictive attention budgets, where several competing methods suffer substantial accuracy degradation.

The method requires no model retraining and integrates with vLLM. The reported decoding speedups and throughput improvements demonstrate practical potential. The ablation studies are comprehensive.

Critical weaknesses

Low-rank KV representations have been explored in prior work. Although page-local fitting improves selection accuracy, it is unclear whether independently fitting each page is necessary or whether simpler shared or clustered alternatives could perform similarly.

SVD minimizes key reconstruction error rather than attention-mass estimation error. It is unclear whether this is the best representation for page selection.

Constructing and storing separate low-rank summaries for every page introduces costs that are not fully characterized relative to shared-basis alternatives.

Questions for authors

Could cluster-shared or locally shared bases achieve comparable accuracy with lower overhead?

Have the authors considered directly optimizing attention-mass estimation rather than key reconstruction error?

2 comments
AuthorsOpenReview ↗

Author Response #1 to Reviewer GRHL

We thank the reviewer for their careful assessment and for recognizing the motivation for page-local representations, the theoretical analysis, and the breadth of our evaluation.


Page-local versus shared bases: accuracy and cost

The tested neighboring and cluster-shared bases do not match page-local selection quality at the same rank. Their selection times are similar, while their amortized initial construction costs are higher in our microbenchmarks.

Direct comparison with the proposed alternatives. We compare a separate basis per page against a basis shared across consecutive pages or across clusters of pages with similar centered-key covariance. All variants retain page-local centroids. We fix rank at 4 and attended-token budget at 128.

TABLE A: Llama-3.1-8B, RULER-32K. Here, s denotes the number of neighboring pages or the target mean cluster size. Both timing columns report ms per decode step for one layer. Construction time is amortized over a generation length of 128 decode steps.

Basis sharingPage recall (%)RULER score (%)Amortized build (ms/step)Selection (ms/step)
Page-local LOCKS90.580.10.01480.0179
Neighbor (s = 4)84.273.00.03150.0180
Neighbor (s = 8)82.368.80.03750.0170
Neighbor (s = 16)81.169.10.02990.0166
Cluster (s = 4)83.773.80.18720.0180
Cluster (s = 8)81.971.90.16560.0174
Cluster (s = 16)80.670.90.15870.0169

Page-local fitting has higher recall and task accuracy than every tested shared alternative. The fastest shared selector saves approximately 7.3% in selection time, while losing 9.4 percentage points of page recall. Thus, the measured selection-time savings come with a loss of selection quality.

Separately, Table 1 and Appendix B.1 of the revised manuscript compare representations at approximately matched storage. Page-local rank-4 summaries use 490 bytes per page and KV head, while sequence-wide and globally shared rank-20 bases with page-local centroids use 487.8 bytes. Even with this higher shared rank, their page recall is 81.3–81.9%, compared with 90.5% for page-local fitting, and retained attention mass is 84.4–84.6%, compared with 85.8%. This complements the fixed-rank neighbor/cluster comparison by testing whether a larger shared rank closes the gap at comparable storage.

Further characterization of low-rank summary costs. For B = 16 and d = 128, we recover the SVD factors of the page's 16 × 128 centered-key matrix by eigendecomposing its 16 × 16 Gram matrix, instead of the 128 × 128 covariance matrix over key coordinates. Sharing reduces the number of bases, but each basis is fitted to keys from multiple pages. Clustering additionally incurs assignment costs. These costs can offset the savings from fitting fewer bases, consistent with our measured construction times.

Together, these results support page-local fitting as a practical accuracy–cost tradeoff: it achieves higher selection quality with lower initial construction cost and similar selection time in the tested implementations.

AuthorsOpenReview ↗

Author Response #2 to Reviewer GRHL

Why SVD for attention-mass estimation?

We use SVD because it minimizes reconstruction error, which controls page-LSE error and, consequently, attention-mass estimation error. The fitting objective and the downstream selection objective are different; the connection between them motivates our choice.

From reconstruction error to attention-mass error. Let Dj∈RB×dD_j \in \mathbb{R}^{B \times d} contain a page's centered keys, and let D~j\widetilde{D}_j be a rank-rr approximation. For an unquantized summary retaining the exact centroid, denote the original and reconstructed page-LSE scores by sj(q)s_j(q) and s^j(q)\hat{s}_j(q), respectively. With logits scaled by 1/d1/\sqrt{d},

\leq \frac{\lVert(D_j-\widetilde{D}_j)q\rVert_\infty}{\sqrt{d}} \leq \frac{\lVert q\rVert_2\\,\lVert D_j-\widetilde{D}_j\rVert_2}{\sqrt{d}}.$$ The first inequality follows from log-sum-exp's 1-Lipschitz property in the infinity norm. Here, the matrix norm is the spectral norm and the query norm is Euclidean. Truncated SVD minimizes the residual spectral norm among rank-$r$ approximations, so it minimizes the query-independent residual factor in this upper bound. Normalizing the exact and reconstructed page-LSE scores over pages gives attention-mass shares $m_j$ and $\hat{m}_j$. If every page-LSE error is at most $\eta$, then $$e^{-2\eta}m_j \leq \hat{m}_j \leq e^{2\eta}m_j.$$ Thus, reducing reconstruction error provides control over the error in the quantity used for selection. This connection underlies the analysis in Section 4 and Appendix A.3. **Directly optimizing attention mass.** Direct fitting is a natural alternative. An empirical objective could minimize page-LSE or normalized-mass error over calibration queries, making the fitted representation depend on that query set. LOCKS instead fits each completed page once from its keys and evaluates the resulting representation with the actual decoding query, without requiring calibration queries. Our rationale is its combination of a reusable, query-independent fit and an explicit bound connecting reconstruction error to attention-mass error.
Reviewer_P7w8OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes LOCKS, a training-free method for selecting KV-cache pages during long-context decoding. For each completed page, LOCKS computes a centroid and a rank-r SVD basis for its centered keys, stores a quantized summary, and uses reconstructed key logits to estimate the page’s log-sum-exp (LSE) attention mass. The paper presents theoretical results connecting score approximation and page coverage to attention-output error, and evaluates both model quality and decoding efficiency across long-context retrieval, question answering, reasoning, and GH200 serving settings.

Critical strengths
  • The problem is important, and the approach is promising. LOCKS achieves competitive performance under tight per-head token budgets.
  • The experimental evaluation is comprehensive. It measures both selection quality relative to the exact-LSE oracle and end-to-end performance.
Critical weaknesses
  • The distinction from prior page-level KV retrieval methods is unclear. For example, the paper should explain more clearly how LOCKS differs from ShadowKV’s low-rank projection approach and identify which aspects constitute its main contributions.
  • The presentation is unclear in places. The paper does not provide comparisons with methods such as Quest under comparable memory footprints. It also does not sufficiently explain the rationale for using int4 quantization or its impact on performance.
Questions for authors
  • How does LOCKS compare with Quest and ShadowKV under comparable storage or memory budgets? Since LOCKS stores per-page low-rank key summaries, comparing methods only by attended-token budget may not be fair. Could the comparisons use total storage as the x-axis?
  • Could the authors disentangle the effects of page selection and quantization, and clarify how LOCKS differs from the existing methods?
3 comments
AuthorsOpenReview ↗

Author Response #1 to Reviewer P7w8

We thank the reviewer for their time and effort in evaluating our submission. We appreciate their recognition of the importance of the problem, LOCKS’s competitive performance under tight token budgets, and the comprehensiveness of our experimental evaluation.


Differences from Quest and ShadowKV

Comparison with Quest. Quest uses coordinate extrema to bound a page’s largest token logit. LOCKS instead estimates page log-sum-exp (LSE), which accounts for the combined attention contribution of all tokens in a page.

For fixed keys, query, and page budget, exact-LSE selection minimizes worst-case attention-output error over bounded values among deterministic value-blind selectors. Our contribution is a compact, page-local key representation for approximating this attention-mass target.

Comparison with ShadowKV. LOCKS and ShadowKV differ in where and how the low-rank representation is used. LOCKS fits a separate basis to each page’s centered post-RoPE keys, whereas ShadowKV fits pre-RoPE keys across the sequence.

LOCKS uses its factors to approximate within-page token logits, aggregate them into page-LSE scores, and select pages; attention then uses the original keys and values. ShadowKV uses its low-rank factors to reconstruct selected keys, while selecting chunks through mean-key landmarks and retaining outliers separately.

We have revised the introduction to make these distinctions explicit.

AuthorsOpenReview ↗

Author Response #2 to Reviewer P7w8

Comparisons at comparable storage

We agree that attended-token budgets alone do not account for the stored representations. We therefore report selection/reconstruction storage alongside accuracy and estimated reads to address whether LOCKS's quality gains require a larger stored representation.

Storage accounting. We use Llama-3.1-8B, with 32 layers, eight KV heads, 128-dimensional keys, and a 16-token page as the accounting unit. We count stored selection/reconstruction tensors, excluding original KV and temporary workspace.

  • Quest: Each page stores coordinate-wise minima and maxima in bf16: 2 × 128 × 2 = 512 bytes per page and KV head in each layer using these summaries.
  • LOCKS r4i4: Each page stores a 128 × 4 int4 basis (256 bytes), 16 × 4 int8 coefficients (64 bytes), a 128-dimensional int8 centroid (128 bytes), and bf16 scales (2 × (4 + 16 + 1) = 42 bytes). The total is 490 bytes per page and KV head per layer.
  • ShadowKV: At 32K context, each layer stores rank-160 bf16 factors comprising 32,768 × 160 token coefficients, shared across KV heads and counted once, plus 8 × 160 × 128 basis entries. Across 32 layers, these occupy 330 MiB. Landmarks and index maps add 252.75 MiB and 8.65 MiB, respectively, totaling 591.4 MiB. Dividing by 32 layers, eight KV heads, and 2,048 16-token pages gives 1,182.8 bytes per page and KV head per layer. This is a normalized equivalent of sequence-wide storage, not a separate summary stored for each page.

Table A: Selection/reconstruction state at the three reference context lengths. Units are bytes per 16-token page and KV head in each layer storing the representation. ShadowKV's sequence-wide state is normalized to this unit; its fixed basis contributes more per page at shorter lengths.

MethodLongBench-v1RULER-16KRULER-32K
Quest512512512
ShadowKV1,212.11,197.61,182.8
LOCKS r4i4490490490

Quality and read cost. We estimate logical reads of KV, selection state, reconstruction factors, and updates with ideal reuse to reduce dependence on kernel implementation. Table B reports accuracy and read cost at the same attended-token budget.

Table B: Llama-3.1-8B, attended-token budget b = 512 Scores are percentages. Estimated reads are averaged over the LongBench-v1, RULER-16K, and RULER-32K reference workloads.

MethodEst. reads (MiB/token)LongBench-v1RULER-16KRULER-32K
FullKV2,477.147.094.388.8
Quest358.445.979.372.1
ShadowKV226.646.384.577.7
LOCKS r4i4210.347.091.486.0

LOCKS achieves higher scores than Quest and ShadowKV across all three benchmarks, with comparable per-page representation storage to Quest, smaller normalized selection/reconstruction state than ShadowKV, and fewer estimated reads.

AuthorsOpenReview ↗

Author Response #3 to Reviewer P7w8

Rationale and effects of int4 quantization

Quantization reduces summary storage and selection reads. In r4i4, the page-local basis is stored in int4, while coefficients and centroids are stored in int8, with bf16 scales. These quantized summaries are used for page selection while attention on the selected pages uses the original bf16 keys and values.

Separating quantization from page selection. We hold the page-local construction, rank, page size, attended-token budget, and selection rule fixed, and vary only summary precision. This isolates the effect of quantization on the same page-selection method.

Table C: Controlled summary-precision comparison. Llama-3.1-8B, page size B = 16, rank r = 4, and attended-token budget b = 1024.

Summary precisionBytes/pagePage recall (%)Retained attention mass (%)
Unquantized reference1,40885.4885.11
r4i874685.3785.11
r4i449083.9285.02

Relative to the unquantized reference, r4i4 reduces the summary payload from 1,408 to 490 bytes, a 2.9× reduction, with decreases of 1.56 percentage points in page recall and 0.09 percentage points in retained attention mass. Relative to r4i8, it uses 34.3% fewer summary bytes. The same payload reduction applies when scanning the stored summaries for selection.

These results motivate int4 as a practical storage–selection-quality tradeoff. Figure 6 in the revised manuscript further reports the precision comparison across ranks and page sizes.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response by Authors #2

Summary of rebuttal responses and revisions

Response numbers below refer to the comments in each reviewer's thread.

Reviewer P7w8

  1. Differences from Quest and ShadowKV and the main contribution.

    • Clarified in Response 1 and the revised Introduction.
  2. Comparisons at comparable storage or memory budgets.

    • Response 2, Tables A–B report representation storage, accuracy, and read costs for Quest, ShadowKV, and LOCKS, with explicit storage accounting.
  3. Rationale for int4 and separation of selection and quantization effects.

    • Response 3 provides the rationale and a controlled precision ablation with the page-local construction and selection rule fixed.

Reviewer GRHL

  1. Could neighboring or cluster-shared bases offer comparable accuracy with lower overhead?

    • Added comparisons of accuracy, construction cost, and selection time in Response 1.
    • Table 1 and Appendix B.1 provide the complementary matched-storage comparison.
  2. Why use SVD rather than directly optimize attention-mass estimation?

    • Response 2 explains the surrogate objective and discusses direct fitting. Supporting analysis is in Section 4 and Appendix A.3.

Reviewer ndFE

  1. Contribution and comparison with simpler page-local summaries.

    • Response 1 clarifies the contribution and compares with Quest. Appendix A.6 explains the connection to moment summaries.
  2. Applicability of the guarantees to quantized summaries.

    • Extended the guarantees in Appendix A.4. Response 2 presents the extension and the controlled quantization ablation.
  3. Computational advantage over direct QK–LSE and amortization of construction costs.

    • Response 3 provides the direct comparison, added prefill cost, and amortization analysis.
    • Table 5 gives the component breakdown; Table B.11 reports complete decoding-step latency.
  4. Recent baselines and practical quality–efficiency tradeoffs.

    • Added ParisKV, RaBitQCache, and ShadowKV efficiency comparisons; see Response 4, Figures 4–5, and Appendix B.5.
    • Response 4 also discusses short-context and long-generation results and distinguishes batch-1 latency from larger-batch offloading throughput.
  5. RULER degradation at the tightest budget.

    • Response 5 discusses the CWE results and the exact-LSE control at the same budget; see Table B.3.

Reviewer da6z

  1. Read reduction versus stored memory and eviction-baseline settings at small budgets.

    • Response 1 clarifies the resource distinctions, additional selection-based comparisons, and configurations of R-KV, LazyEviction, and TriAttention.
    • Table 3 and Appendix B.4 account for reads beyond the nominal token budget.
  2. Breakdown of the linear summary scan versus attention.

    • Provided in Response 2 and Table 5, including summary scoring, selection, updates, and attention.
  3. Offloading performance on PCIe hardware.

    • Added H200 NVL PCIe 5.0 measurements in Appendix C.7, Table C.9, reporting batch sizes, latency, and throughput; see Response 3.

We sincerely thank the reviewers for their careful assessments and constructive feedback, which helped strengthen the clarity and rigor of this work.

Sincerely,
The Authors

AuthorsOpenReview ↗

General Response by Authors #1

Dear Reviewers, Area Chair, Senior Area Chair, and Program Chairs,

We sincerely appreciate your time and effort in overseeing the review process, and we value the thoughtful and constructive feedback provided by all reviewers, as well as their recognition of the theoretical and empirical strengths of our work. In the following two comments, we summarize the strengths highlighted by the reviewers, explain how we have addressed their concerns, and outline the revisions incorporated into the manuscript. The reviewers’ feedback has helped us strengthen both the clarity and substance of our work.


Strengths recognized by the reviewers

  1. A page-local design supported by direct empirical evidence. Reviewers GRHL, ndFE, and da6z recognized the motivation for fitting a separate basis to each page and the evidence that it improves attention-mass estimation and page selection over shared projections. Reviewer ndFE specifically highlighted the comparisons at matched summary storage, while da6z found the page-local versus shared-basis analysis in Table 1 and Proposition 1 convincing.

  2. A theoretical foundation connecting representation, selection, and output error. Reviewer GRHL highlighted the connection between exact-LSE selection and worst-case attention-output error, the characterization of limitations of fixed shared projections, and the error bounds for page-local approximations. Reviewer da6z also recognized the supporting analysis of page-local versus shared representations.

  3. Strong quality under tight attention budgets. Reviewers P7w8, GRHL, ndFE, and da6z recognized LOCKS's competitive or strong performance under restrictive budgets. Reviewers GRHL and da6z particularly noted the reasoning results in settings where competing methods suffer substantial accuracy degradation.

  4. A training-free implementation with practical deployment potential. Reviewers GRHL, ndFE, and da6z recognized the vLLM implementation and its practical relevance. Reviewer da6z specifically noted CUDA-graph integration and ease of deployment, while GRHL and ndFE highlighted the decoding acceleration and serving results at long contexts.

  5. Broad evaluation with complementary diagnostics. Reviewers P7w8 and GRHL recognized the comprehensive evaluation. It combines selection quality relative to exact-LSE selection with model-level quality and decoding performance across retrieval, long-document QA, and reasoning. Reviewer GRHL also highlighted the breadth of the ablation studies.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.