July 29, 2026 EN #KV Cache #LLM Inference #Attention & MLA

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

Review date: 2026-07-29 Author: Zhongzhu Zhou Paper reviewed: LOCKS: Page-Local Compact Key Summaries for Efficient Long-Context Decoding Paper authors: Junsung Hwang arXiv: 2607.24555 Venue/Status: Preprint, July 28, 2026

1. Why this paper, and what problem is it actually solving

If you have ever tried to serve a long-context LLM in production, you have run into a very specific, very annoying wall: the model’s weights fit comfortably on your GPU, but the KV cache for a single 128K-token request does not. For Llama-3.1-8B in bf16, a 128K-token KV cache occupies roughly 16 GiB — more memory than the model’s own weights. Multiply that by a batch of concurrent requests and you have two separate bottlenecks fighting for the same accelerator: how much KV cache you can hold (capacity), and how many KV bytes you have to read at every single decode step (bandwidth). These are not the same problem, and conflating them is a common mistake. LOCKS is squarely about the second one: it keeps the entire KV cache resident in GPU memory, but at every decode step it only reads a small, carefully chosen fraction of it.

This is not a new idea in isolation — sparse decode-time attention has been studied under many names: Quest, ShadowKV, Loki, H2O-style eviction, RocketKV, and so on. What makes LOCKS interesting is not “yet another selector,” but a specific, falsifiable claim about why previous selectors leave quality on the table at aggressive budgets, backed by a clean theoretical impossibility result and a chain of empirical measurements that isolate exactly where each rival approach breaks down. If you work on KV-cache compression, quantization, or long-context serving, this paper is worth reading closely because its central argument — “representation scope determines fidelity, not representation size” — likely generalizes well beyond this one system.

Prerequisites: what you need to know before diving in

If you are already comfortable with paged KV-cache serving (vLLM-style), query-aware sparse attention, and basic linear algebra (SVD/eigendecomposition), skip to Section 3. Otherwise, here is the background compressed into what you actually need.

Decode-time attention, in one line. During autoregressive generation, each new query token computes attention over all previously cached keys and values: $\mathbf{o} = \sum_i \alpha_i \mathbf{v}_i$ with $\alpha = \mathrm{softmax}(\mathbf{q}^\top \mathbf{k} / \sqrt{d})$ . At prefill time, this is one large batched matrix multiply; at decode time, it happens once per generated token, and the query only ever has one row. That asymmetry is the whole reason KV-cache read bandwidth becomes the bottleneck at long context and large batch: prefill amortizes weight reads across many tokens, but every decode step for every sequence in the batch has to touch its own KV cache in full, and that per-request cost does not amortize.

Paged KV-cache serving. vLLM and its descendants store the KV cache in fixed-size pages (also called blocks) of $B$ consecutive tokens rather than one contiguous per-sequence buffer. This makes memory management flexible (pages can be allocated/freed like a virtual memory system) and, crucially for this paper, gives you a natural unit of granularity at which to make keep or drop decisions during sparse attention: instead of deciding token-by-token, you decide page-by-page.

Why sparse decode attention works at all. Empirically, at any given decode step, only a handful of pages carry almost all of the attention mass for that particular query — the rest of the cache is nearly irrelevant to that step’s output. This has been observed and exploited repeatedly (H2O, StreamingLLM’s sink+window, Quest, and others). If you could cheaply identify which pages matter before reading anything, you could skip reading the rest and get a large speedup with negligible quality loss. The catch is “cheaply identify” — computing the exact answer to that question requires reading every key in the cache, which defeats the purpose. So every practical sparse-decode method needs some compact, resident summary of each page that lets you rank pages by importance without reading the full keys.

Low-rank / eigendecomposition basics. If you stack a set of vectors as the rows of a matrix $D \in \mathbb{R}^{B \times d}$ , the Gram matrix $DD^\top$ (or equivalently, the covariance-like structure of $D$ ) can be eigendecomposed to find the directions of greatest variance in that vector cloud. Keeping only the top $r$ eigenvectors gives you a rank- $r$ approximation: you can reconstruct each row approximately as a linear combination of just $r$ basis vectors, rather than the full $d$ -dimensional original. This is the mathematical tool LOCKS uses to compress each page’s keys into a much smaller “spectral summary.” The core empirical claim of this paper is about where you fit this basis: per-page (this paper), per-sequence (ShadowKV), or globally across the whole cache (Loki) — and it turns out that choice matters enormously.

Log-sum-exp (LSE) as an attention-mass proxy. For a set of unnormalized attention logits $\{z_i\}$ , $\log \sum_i e^{z_i}$ is a smooth, differentiable stand-in for “how much total mass does this set of tokens carry” before you even normalize with softmax. It appears constantly in efficient-attention work because it lets you estimate a page’s share of total attention mass without computing the full softmax over the whole sequence — you just need the LSE of that page’s logits relative to the LSE of all pages combined.

With that vocabulary in hand, the rest of the paper is approachable.

2. Architecture overview: what LOCKS actually builds and does

At a high level, LOCKS is a drop-in attention backend plugin for unmodified vLLM. It requires no changes to model weights, no fine-tuning, no gating network — it is entirely training-free. Its job, once installed, is to intercept the decode-time attention computation and, for every KV head at every decode step, decide which pages of the cache are worth reading in full.

flowchart TD
    A["New token arrives, query q formed"] --> B{"Page just completed?"}
    B -- "Yes" --> C["Build step: eigendecompose page's<br/>centered keys, keep rank-r basis V_j<br/>+ coefficients c_i, quantize to int4/int8"]
    C --> D["Store per-page spectral summary<br/>(~one tenth of page's KV bytes)"]
    B -- "No / already built" --> E["Score step: reconstruct within-page<br/>logits from summary, reduce via log-sum-exp"]
    D --> E
    E --> F["Normalize into page-mass share per query"]
    F --> G["Share-average across GQA group<br/>-> one ranking shared by all heads in group"]
    G --> H["Select sink page + most-recent page<br/>+ top-(k-2) pages by averaged share"]
    H --> I["Fetch full K/V only for selected pages"]
    I --> J["Standard attention over selected pages only"]

Figure 1 (self-drawn, Mermaid): The two-phase LOCKS pipeline — a one-time build step per finished page, and a per-decode-step score/select/attend loop that never touches the full keys/values during selection.

The design splits cleanly into two phases that run at very different frequencies:

Build (once per page, when the page finishes filling). This is cheap: one small $B \times B$ eigendecomposition (recall $B$ is the page size, typically 16 tokens — so this is a tiny $16\times16$ eigenproblem, not something exotic). It runs off the decode critical path, batched at the prefill–decode boundary for the prompt, and incrementally as new pages fill during generation.
Score (every single decode step, per KV head). This is the expensive-in-frequency-but-cheap-in-work part: for every page, reconstruct its within-page logits from the tiny stored summary (a matrix-vector product plus a length- $B$ log-sum-exp), rank pages by estimated attention-mass share, and select the top- $k$ (minus the two reserved slots for the sink page and the most recent page).

The key architectural decision that makes this deployable is that selection itself never reads a single candidate key or value — it only reads the compact resident summaries, which are roughly a tenth the size of the pages they summarize. Only after selection does the engine fetch full K/V for the chosen pages and run ordinary attention over that reduced set.

Data flow at a glance

flowchart LR
    subgraph Resident["Resident (always in GPU memory)"]
        FullKV["Full KV cache<br/>(every page, every token)"]
        Summ["Per-page spectral summaries<br/>(int4 basis + int8 coeffs, ~1/10 size)"]
    end
    Query["Decode query q"] --> Score["Score all pages<br/>via summaries only"]
    Summ --> Score
    Score --> Select["Select top-k pages<br/>(sink + recent + ranked rest)"]
    Select --> Fetch["Fetch full K,V<br/>for selected pages only"]
    FullKV --> Fetch
    Fetch --> Attn["Standard softmax attention<br/>over selected pages"]
    Attn --> Out["Output o"]

Figure 2 (self-drawn, Mermaid): the data-flow view. Notice that the full KV cache is still resident (this is a bandwidth optimization, not a capacity optimization) — the summary only changes what gets read at each step, not what gets stored.

This distinction is worth dwelling on for a second, because it is easy to conflate LOCKS with cache-eviction methods (H2O, StreamingLLM-style window+sink, R-KV) that actually discard tokens permanently to save memory. LOCKS does not evict anything — every token stays in the cache forever, in case a future query needs it. What LOCKS reduces is decode-time read traffic, which is the dominant cost once your cache is large enough that reading it (not storing it) is what limits throughput.

3. The core theoretical claim: representation scope, not size, determines fidelity

This is the intellectual heart of the paper, and it is worth walking through carefully because the argument has two parts: an empirical “locality finding” and a formal impossibility proof.

3.1 The setup: what makes a good page summary

Section 2 of the paper first nails down the target that any summary should approximate. For a page set $S$ kept at a decode step, and the complement $S^c$ dropped, the paper states an exact identity (attributed to concurrent work by Tzachristas et al. and Tian et al.) for how much the attention output changes:

\mathbf{o} - \mathbf{o}_S = \varepsilon(\bar{\mathbf{v}}_{S^c} - \bar{\mathbf{v}}_S), \qquad \varepsilon = 1 - \gamma_S(\mathbf{q}) \tag{1}

where $\gamma_S(\mathbf{q})$ is the fraction of the query’s total attention mass falling inside $S$ , and $\bar{\mathbf{v}}_S, \bar{\mathbf{v}}_{S^c}$ are the mass-weighted mean values of the kept and dropped sets respectively.

Why this matters, and the intuition behind it. This identity says the output error from dropping pages is not simply proportional to how much mass you dropped ( $\varepsilon$ ) — it is that dropped mass times the difference between what you kept and what you threw away. If the dropped pages carry values that look just like the kept pages’ average (i.e., $\bar{\mathbf{v}}_{S^c} \approx \bar{\mathbf{v}}_S$ ), you can drop a lot of mass cheaply, because you are only losing “more of the same.” But if you happen to drop a page holding a single distinctive, rare token — a “carrier” that holds information nothing else in the sequence duplicates — then even though that one token carries tiny raw probability mass, $\bar{\mathbf{v}}_{S^c}$ diverges sharply from $\bar{\mathbf{v}}_S$ , and the error term blows up toward its ceiling. This is exactly the mechanism behind needle-in-a-haystack failures in sparse attention: the needle token often has small softmax weight, so a selector optimizing purely for average retained mass has no signal telling it the needle matters — but dropping it is catastrophic for output quality.

The consequence for selection. Because of this identity, the paper derives (Lemma 1, proof in an appendix) that among deterministic selection rules that don’t read the values $\{\mathbf{v}_i\}$ (i.e., rules that only look at query/key information, not what’s actually stored in each page), ranking pages by their exact log-sum-exp attention mass is worst-case optimal. This gives LOCKS its target quantity: get as close as possible to ranking pages by exact LSE mass, using only a cheap resident summary.

Design-choice discussion: why not just track total captured mass instead of carrier survival? The obvious alternative metric is “how much total attention mass did my selected set capture, on average, across many queries” — and several rival methods (notably Quest, an envelope-based selector) do very well on exactly this metric even at small budgets. The paper’s diagnostic move is to separate this “aggregate mass” metric from a second one: carrier-page retention — specifically, whether the few pages that are decisive for a given task (e.g., the page holding the passkey in a retrieval task) survive selection. The paper shows these two metrics can diverge sharply: Quest tracks the exact-mass oracle closely on aggregate captured mass, yet retains carrier pages less than half as often (Fig. 1b). Average-case fidelity conceals worst-case (carrier) failure. This is a genuinely useful methodological lesson independent of the rest of the paper: if you are evaluating a sparse-attention selector, measure carrier-page recall, not just captured mass, or you will systematically overestimate quality on retrieval-heavy tasks.

3.2 The locality finding: page-local eigenbases capture more energy than shared bases

Given that exact LSE mass requires reading every key (which defeats the point), LOCKS needs a summary that lets you approximate it. The natural approach — used by prior work — is to fit a shared low-rank projection once, either across the whole cache (Loki: an offline-calibrated shared PCA basis) or per-sequence (ShadowKV: one low-rank basis per sequence, refit less frequently than per page). LOCKS instead fits a separate basis for every single page.

The paper’s first empirical claim is a “dose-response” pattern: as you shrink the scope of the basis from cache-wide, to per-sequence, to per-page, the fraction of within-page key energy captured at a fixed rank increases sharply. A page’s own rank-8 eigenbasis captures most of that page’s key energy; a per-sequence basis captures a smaller fraction of the same information; a single cache-wide basis captures almost none. Crucially, the paper controls for a natural objection — “maybe the shared basis just needs more state (higher rank) to catch up” — and shows that even when you grow the shared basis to match or exceed the per-page basis’s total stored bytes, it still trails page-local fidelity (Table D.15 in the appendix). This rules out “size” as the explanation and points squarely at “scope.”

3.3 The impossibility proof: why shared bases are provably blind to page content

This is the sharpest piece of the paper, so let’s unpack it in full. Proposition 1 (informally): fix any shared linear projection $W \in \mathbb{R}^{d \times \rho}$ with $\rho < d$ , and any scoring rule that only looks at the query, a page’s centroid $\mu$ , and the sketched keys $\{W^\top \mathbf{k}_i\}$ . Then there exists a $(d-\rho)$ -dimensional family of within-page content changes that this scoring rule cannot see at all — changing the actual keys in a way that dramatically changes the true attention mass produces zero change in the score.

The construction, step by step. Take any unit vector $u$ that is orthogonal to the span of $W$ (this space has dimension $d - \rho$ , hence “exists” is easy — as soon as your shared projection has rank less than the full dimension, such directions exist). Now take a page $P$ with at least two keys, and construct a modified page $P'$ by adding $c\cdot u$ to one key and subtracting $c\cdot u$ from another key (for any scalar $c > 0$ ). Because $u \perp \mathrm{span}(W)$ , the sketch $W^\top \mathbf{k}_i$ of both keys is completely unaffected by this perturbation — the shared summary of $P'$ is byte-for-byte identical to that of $P$ . So any scoring rule built only from this sketch necessarily assigns $P$ and $P'$ the same score, for every query.

But the true log-mass is not the same. For any query $q$ satisfying $q^\top u > 0$ , the actual (exact) log-sum-exp attention mass of $P'$ diverges from that of $P$ without bound as $c \to \infty$ — because the true attention logits do depend on the full key vectors, including their component along $u$ , even though the shared sketch cannot see it.

Why this matters practically, not just as a mathematical curiosity. This isn’t a statement about a bad choice of $W$ ; it holds for every fixed shared $W$ with rank less than $d$ , no matter how it is calibrated. It formalizes the intuition that a “one basis fits all pages” approach necessarily throws away entire dimensions of page-specific variation, and any content that lives predominantly in those blind directions is invisible to the selector — not merely poorly-approximated, but exactly zero-information. Page-local bases don’t have this problem because each page gets its own $\rho$ -dimensional subspace fit to that page’s own content, so there is no fixed blind spot shared across all pages.

Alternative and its boundary. The obvious rebuttal is: “then just adapt $W$ online as the cache grows.” The proposition explicitly does not cover adaptive procedures that refit the shared basis as content changes — those are evaluated only empirically (via the “scope frontier” ablation in the appendix), not ruled out by the theorem. This is an honest boundary condition worth flagging: the impossibility result is a statement about fixed shared bases, and a sufficiently aggressive online-refit scheme is a legitimate escape hatch that the paper does not fully close, though it notes such schemes have not, in practice, matched per-page fidelity in their measurements.

4. The LOCKS construction: building and scoring a per-page basis

Now that we know why per-page scope is necessary, here is exactly how LOCKS builds and uses its per-page summaries.

4.1 Build step — full derivation

For a page $P_j$ with $B$ tokens, let $\mathbf{k}_i$ be the (post-RoPE) key vectors for $i \in P_j$ . First, center the page:

\mathbf{k}_i = \mu_j + \delta_i, \qquad \sum_{i \in P_j} \delta_i = 0 \tag{2}

so $\mu_j$ is simply the mean key of the page, and $\delta_i$ is each key’s deviation from that mean. Stack the deviations as rows of a matrix $D_j \in \mathbb{R}^{B \times d}$ . Because $B$ (the page size, e.g., 16) is typically much smaller than $d$ (the head dimension, e.g., 128), it is far cheaper to eigendecompose the small $B \times B$ Gram matrix than the large $d \times d$ covariance:

D_j D_j^\top = U_j \Sigma_j^2 U_j^\top \in \mathbb{R}^{B \times B} \tag{3}

with eigenvalues $\sigma_{j,1}^2 \geq \sigma_{j,2}^2 \geq \cdots$ (these are exactly the squared singular values of $D_j$ ) and eigenvectors giving the right singular vectors $v_{j,k}$ via the standard SVD-from-Gram-matrix relation. Keep only the top $r$ components. This gives:

Coefficients $c_i \in \mathbb{R}^r$ — the rows of $C_j = U_{j,r}\Sigma_{j,r}$ , equivalently $c_i = V_j^\top \delta_i$ (the projection of each key’s deviation onto the retained basis).
Orthonormal basis $V_j = D_j^\top U_{j,r} \Sigma_{j,r}^{-1} = [v_{j,1} \cdots v_{j,r}] \in \mathbb{R}^{d \times r}$ .

The reconstruction $\delta_i \approx V_j c_i$ is exact whenever $r \geq \mathrm{rank}(D_j)$ (i.e., if the page’s true key-deviation cloud already lives in an $r$ -dimensional subspace, you lose nothing), and otherwise incurs an error bounded by the spectral tail $\tau_{j,r} = \sum_{k>r} \sigma_{j,k}^2$ — literally the sum of the squared singular values you threw away. This spectral-tail quantity reappears in the main theorem below, and it is the natural way to think about reconstruction error in eigen/SVD-based compression generally: the error you incur is exactly the “energy” living in the discarded directions.

Storage. The basis is stored in int4, and the coefficients plus centroid in int8 (with per-column/per-row quantization scales). At the shipped configuration ( $r=8$ , $B=16$ ), the logical payload is about 9.4% of the page’s raw KV bytes — call it roughly a tenth, once quantization-scale overhead is counted. Building the summary is a single small eigendecomposition per finished page, running off the decode critical path; it does not touch the model’s prefill attention path at all.

4.2 Score step — full derivation

At every decode step, for a query $\mathbf{q}$ and page $j$ , LOCKS reconstructs the within-page logits from the summary alone and reduces them with log-sum-exp:

\hat{s}_j(\mathbf{q}) = \log \sum_{i \in P_j} \exp\!\left( \frac{\mathbf{q}^\top \mu_j + (V_j^\top \mathbf{q})^\top c_i}{\sqrt{d}} \right) \tag{4}

Where this comes from. The true (exact) attention logit for query $\mathbf{q}$ against key $\mathbf{k}_i$ is $\mathbf{q}^\top \mathbf{k}_i / \sqrt{d} = \mathbf{q}^\top(\mu_j + \delta_i)/\sqrt{d} = (\mathbf{q}^\top \mu_j + \mathbf{q}^\top \delta_i)/\sqrt{d}$ . Substituting the reconstruction $\delta_i \approx V_j c_i$ , we get $\mathbf{q}^\top \delta_i \approx \mathbf{q}^\top V_j c_i = (V_j^\top \mathbf{q})^\top c_i$ — i.e., you only ever need the projection of the query onto the page’s own basis, dotted with the stored per-key coefficients. Notice that this projection $V_j^\top \mathbf{q}$ is a cheap $r$ -dimensional operation (here $r=8$ ), done once per page per query, and the sum over $i \in P_j$ (only $B=16$ terms) is the log-sum-exp reduction. This is why the whole scoring step is cheap: an $r$ -dimensional projection plus a length- $B$ LSE, per page, fusible into a single ranking kernel.

The reconstructed score is then normalized into a page-mass share, and the GQA group’s queries are combined. Since Grouped-Query Attention shares one KV cache across a group of $G$ query heads, each query head $g$ in the group computes its own normalized share $\hat{m}_g(j) = e^{\hat{s}_j(q_g)} / \sum_{j'} e^{\hat{s}_{j'}(q_g)}$ , and these are simply averaged across the group:

\bar{\hat{m}}_j = \frac{1}{G}\sum_{g \leq G} \hat{m}_g(j) \tag{5}

The sink page and the most-recently-written page always fill two of the $k$ slots (they are known from prior work to be disproportionately important regardless of measured mass — sink tokens absorb attention “overflow,” and the most recent page is needed for local coherence), and the remaining $k-2$ slots go to the top-ranked pages by $\bar{\hat{m}}_j$ . All $G$ heads in the group then attend the same shared set of pages — a nice practical property, since KV storage itself is already shared per KV head in GQA, so there is no extra memory traffic from computing per-head-different selections.

Design-choice discussion: why average shares across the group instead of, say, taking the max or voting? The paper proves (Cor. 3) that this share-averaging rule maximizes the group-mean coverage among all shared selection rules — i.e., among rules that must pick one set of pages for the whole GQA group to use. The obvious alternatives are group-max (pick pages that any single head in the group ranks highly) or group-mass (some other pooling). Empirically (§5.4 ablation), share-averaging retains more of every measured statistic — mean coverage, worst-head coverage, and the 5th percentile — than either alternative. Interestingly, the paper notes this rule already exists in prior literature as “TokenSelect’s head soft vote”; the contribution here is proving it is optimal for this setting and measuring how close it comes to a much more expensive per-head oracle (only about 2 coverage points worse, despite using $G\times$ less selection work).

4.3 Algorithm 1: Build (per finished page)

Algorithm 1: LOCKS Page Summary Build
Input: page P_j with keys {k_i}_{i in P_j}, target rank r, page size B
Output: basis V_j, coefficients {c_i}, centroid mu_j (quantized)

1:  mu_j <- mean_{i in P_j}(k_i)                      # page centroid
2:  for i in P_j:
3:      delta_i <- k_i - mu_j                         # center each key
4:  D_j <- stack({delta_i}) as rows                   # D_j in R^{B x d}
5:  G_j <- D_j @ D_j.T                                # small B x B Gram matrix
6:  (U_j, Sigma_j^2) <- eigendecompose(G_j)            # sorted descending
7:  U_j_r <- U_j[:, :r]                                # top-r eigenvectors
8:  Sigma_j_r <- Sigma_j[:r, :r]                        # top-r singular values
9:  V_j <- D_j.T @ U_j_r @ inverse(Sigma_j_r)          # orthonormal basis, d x r
10: C_j <- U_j_r @ Sigma_j_r                            # coefficients, B x r
11: tau_j_r <- sum(Sigma_j[r:]^2)                       # spectral tail (diagnostic)
12: V_j_quant <- quantize_int4(V_j)                     # per-column scales
13: C_j_quant, mu_j_quant <- quantize_int8(C_j, mu_j)   # per-row scales
14: return V_j_quant, C_j_quant, mu_j_quant

4.4 Algorithm 2: Score and Select (per decode step, per KV head)

Algorithm 2: LOCKS Score and Select
Input: query group {q_g}_{g<=G}, per-page summaries {(V_j, c_i, mu_j)}, budget k
Output: selected page set S (shared across the G-head GQA group)

1:  S <- {sink_page, most_recent_page}                # always-kept slots
2:  for each candidate page j (not already in S):
3:      for g in 1..G:
4:          proj_g <- V_j.T @ q_g                       # r-dim projection
5:          for i in P_j:
6:              logit_i <- (q_g.T @ mu_j + proj_g.T @ c_i) / sqrt(d)
7:          s_hat_j(q_g) <- logsumexp({logit_i})         # Eq. 4
8:      for g in 1..G:
9:          m_hat_g(j) <- softmax_over_pages(s_hat_j(q_g))  # normalize per head
10:     m_bar_j <- mean_{g<=G}(m_hat_g(j))              # Eq. 5, share-average
11: rank all candidate pages by m_bar_j, descending
12: S <- S union {top (k - 2) pages by m_bar_j}
13: fetch full (K, V) for pages in S only
14: return attention(q_g, K_S, V_S) for all g in group   # standard softmax attention

5. Theorem 1: the retention guarantee, fully derived

This is the theoretical payoff that ties the construction back to the output-error identity of Section 3.1. Let $\eta$ be the worst-case log-mass reconstruction error across every page and every query in a group:

\eta := \max_{g,j} \left| \hat{s}_j(q_g) - s_j(q_g) \right| \tag{6}

Part (i): bounding $\eta$ from the spectral tail. The paper shows

\eta \leq \max_{g,j} \frac{\|(q_g)_\perp\| \sqrt{\tau_{j,r}}}{\sqrt{d}} \tag{7}

where $(q_g)_\perp$ is the component of the query that lies outside page $j$ ‘s retained basis. Intuition: the reconstruction error in the logit is driven by how much of the query points in a direction the page’s basis didn’t keep, times how much “energy” the page has left in its own discarded directions (the spectral tail $\tau_{j,r}$ from Eq. 2 above). If $r \geq \mathrm{rank}(D_j)$ for every page (i.e., you kept enough rank to capture the page exactly), $\eta = 0$ — no error at all. This is a clean, satisfying closed-form dependence: it directly ties the quality knob ( $r$ ) to the error you can expect, mediated by how “spiky” vs. “flat” each page’s key spectrum actually is.

Part (ii): from log-mass error to retained coverage. Given this per-query, per-page score error, the paper shows the shared top- $k$ set selected by the group-averaged estimated shares retains at least

e^{-4\eta} \tag{8}

of the group-average coverage that exact-mass selection would have achieved (always-kept pages included). This is a multiplicative retention guarantee: if $\eta$ is small, $e^{-4\eta} \approx 1 - 4\eta$ , so you retain almost all of the oracle’s coverage; if $\eta$ is large, the guarantee degrades but never becomes vacuous (it just shrinks toward zero as $\eta \to \infty$ , which is the expected worst case).

Part (iii): translating coverage loss into actual output error. Combining with the exact identity of Eq. 1, the paper obtains a full end-to-end bound:

\frac{1}{G}\sum_{g \leq G} \left\| \mathbf{o}_S(q_g) - \mathbf{o}(q_g) \right\| \leq 2R\left(1 - e^{-4\eta}\right)\bar{\gamma}^\star \tag{9}

where $R$ is a bound on value-vector norms and $\bar{\gamma}^\star$ is the exact selection’s group-average coverage. Reading this bound left to right: the group-average attention-output error is controlled by (a) how large your value vectors can be ( $R$ — a property of the model, not the selector), (b) how much coverage the exact oracle itself would have achieved with the given budget ( $\bar\gamma^\star$ — a property of the task’s actual sparsity, not the selector), and (c) how close your quantized-summary retention is to that oracle’s coverage, controlled entirely by $\eta$ . This is the composed proof mentioned earlier: Lipschitz reconstruction bound (how far a reconstructed logit can be from the true logit) $\to$ group-share sandwich (how averaging across heads propagates errors) $\to$ ranking-robustness (how a top- $k$ selection changes when scores are perturbed by at most $2\eta$ ).

A crucial and refreshingly honest caveat. All of the above is proven for the unquantized summary. The actually-deployed int4/int8 quantized summary’s log-mass error is measured, not analytically bounded — and the paper reports this measured error is small at the median but roughly double the unquantized error at matched percentiles, and heavy-tailed at the extremes. Because $\eta$ in the theorem is a maximum over all pages, it is exactly these tail pages that would drive the bound if you tried to naively plug in measured quantization error — so the authors are careful to say the retention constant is “qualitative at measured magnitudes,” and the real evidence for practical quality comes from the empirical measurements in Section 5.4 (carrier retention specifically), not from mechanically plugging measured $\eta$ into Eq. 8. This is good scientific hygiene: distinguishing what is proven from what is merely measured, rather than overclaiming a guarantee the deployed system doesn’t actually enjoy.

5.1 A worked toy example

To make Eq. 4 and Eq. 6-9 concrete, imagine a tiny page with $B=4$ tokens, head dimension $d=4$ , and we keep rank $r=1$ (an extreme, illustrative compression). Suppose the centered key deviations are:

\delta_1 = (1, 0, 0, 0), \ \delta_2 = (0.9, 0.1, 0, 0), \ \delta_3 = (-1, 0, 0, 0), \ \delta_4 = (-0.9, -0.1, 0, 0)

The dominant singular direction here is clearly close to $(1,0,0,0)$ — all four deviations are almost entirely aligned along the first axis, with only a small component in the second axis. A rank-1 basis $V_j \approx (1,0,0,0)^\top$ captures the large first-axis component of every key almost exactly, leaving only the small second-axis component ( $\pm 0.1$ ) as reconstruction error — this is exactly the spectral-tail term $\tau_{j,1}$ , and it will be small because the discarded second singular value is small. Now suppose a query $\mathbf{q}$ happens to point mostly along the second axis (the direction this rank-1 basis discarded). The reconstructed logits for all four keys will look nearly identical (since the retained basis can’t distinguish $\delta_2$ from $\delta_1$ , or $\delta_4$ from $\delta_3$ , along that axis) — even though the true logits, computed against the full 4-dimensional keys, would actually differ. This is precisely how $\eta$ in Eq. 6 arises in practice: whenever a query has a large component orthogonal to a page’s retained basis (the $(q_g)_\perp$ term in Eq. 7), and that page’s spectral tail in that direction is non-trivial, the reconstructed score becomes unreliable for that specific query — even though it might be perfectly fine for a different query pointing along the dominant axis. This toy example is also a compact illustration of why page-local fitting matters: a basis fit separately to this specific 4-key cloud captures its dominant direction cheaply, whereas a basis shared across many pages with different dominant directions could not do this for all of them simultaneously — which is exactly the content of Proposition 1.

6. Experimental results, walked through

The evaluation is organized around the “chain” the paper wants to certify end-to-end: page-local spectral concentration $\Rightarrow$ token-logit fidelity $\Rightarrow$ LSE ranking fidelity $\Rightarrow$ carrier survival $\Rightarrow$ task quality at aggressive sparsity $\Rightarrow$ practical acceleration.

Figure 3 (paper Fig.1): The locality thesis in one figure. Panel (a) plots exact vs. reconstructed page-mass share at matched bytes: the page-local ( $r=8$ , int4, 768 bytes) points hug the diagonal almost perfectly, while the per-sequence basis (ShadowKV-style, 780 bytes — matched storage cost) scatters widely off-diagonal, confirming this is a scope effect, not a storage-budget effect. Panel (b) shows carrier-page retention as a function of per-head budget: LOCKS tracks the exact-selection ceiling closely down to a 0.5% budget, while Quest (envelope-based) and a simple centroid baseline fall well short, especially at small budgets — exactly where it matters most for retrieval tasks. Panel (c) is the “error ladder”: at matched storage bytes, global (shared cache-wide) and per-sequence bases both show much larger logit-MAE, LSE-MAE, and worse ranking correlation than the per-page scope, which is the direct empirical confirmation of the theoretical argument from Section 3. Panel (d) shows a radar chart of RULER-16K task-family scores at a tight 256-token budget: LOCKS traces FullKV almost exactly across every capability (single-needle, multi-key, multi-value, aggregation, state-tracking, open QA), while the implied comparison methods fall inside the polygon on several axes.

Figure 4 (paper Fig.2): Retrieval and long-document QA vs. budget. Across LongBench-v1, RULER-16K, and RULER-32K, LOCKS (green) tracks the exact-LSE oracle (dashed) almost exactly across the entire budget sweep, while four competitive baselines — Quest, KVzip, ShadowKV, RocketKV — all show a visible drop-off as the budget shrinks, with the gap widening most dramatically on retrieval-dense RULER at small budgets. This is the task-quality payoff of the carrier-retention property demonstrated in Figure 3(b): tasks that hinge on finding a few specific tokens are exactly where average-mass-preserving selectors fail hardest, and LOCKS’s carrier-aware fidelity shows up as a much flatter degradation curve.

Baseline/prior-art comparison — InfiniteBench at 100K+ context (paper Table 1).

At a tight budget ( $b=512$ ) on GLM-4-9B-Chat-1M with 100K+-token context, LOCKS scores 41.1 average (vs. 43.0 for FullKV and 42.3 for the exact-LSE oracle) — noticeably ahead of RocketKV (38.5), ShadowKV (36.0), and Quest (34.7). At a more generous budget ( $b=2048$ ), LOCKS actually exceeds the exact-LSE oracle on the reported average (43.6 vs 43.9, within noise given the reported confidence intervals), essentially matching FullKV. This is a genuinely striking result: a training-free, resident-summary-based selector achieving parity with reading the entire cache, at roughly 2% of the read traffic.

Figure 5 (paper Fig.3): Long-form reasoning vs. budget. This is arguably the most interesting quality result because reasoning traces behave differently from retrieval/QA — the model is decoding thousands of tokens itself, so the “working set” it needs to attend over grows as generation proceeds, rather than being a fixed fraction of a static prompt. The result is a budget floor: below a certain per-head budget, every method (including the exact-LSE oracle) collapses in accuracy on AIME26 and MATH-500, because the true attention mass genuinely needs that many tokens’ worth of budget to answer correctly — this is a property of the task, not of any particular selector’s fidelity. What differentiates LOCKS from Quest, R-KV, TriAttention, and LazyEviction is how it behaves once the budget clears that floor: LOCKS’s curve tracks the oracle almost exactly, while the baselines continue trailing well past the point where the oracle (and LOCKS) have already recovered full quality.

Figure 6 (paper Fig.4): Decode efficiency at extreme context. Measured on an H200 NVL node in real vLLM 0.24, at the shipped budget where LOCKS matches full-cache quality: per-token latency (TPOT) is 2.0× lower than dense FlashAttention-3/FlashInfer baselines at 1M-token context (panel a); prefill time-to-first-token stays at parity, since selection only affects decode (panel b); and bytes-read-per-decode-step drops 9.8× at 1M-token context (panel c), which is the direct mechanism behind the latency win. Table 2 in the paper additionally shows the speedup grows with batch size — at 256K context, the speedup goes from 1.30× at batch size 1 to 1.80× at batch size 4 (batch sizes above that OOM for the dense baseline but not for LOCKS) — because the dense engine’s per-request cache read scales linearly with batch, while LOCKS’s selected read does not scale the same way.

Ablations worth flagging

The paper also carefully ablates its own two remaining design knobs. Rank and quantization precision: int8 tracks the unquantized (bf16) basis closely; int4 costs a few recall points and stops improving past moderate rank (i.e., you cannot compensate for quantization noise by throwing more rank at the problem — the quantization floor dominates); int2 collapses toward “centroid-level” ranking regardless of rank (i.e., a rank-any int2 basis is barely better than just using the page mean, which is a striking demonstration of how sensitive fine per-key structure is to bit-width). This is why the shipped configuration is $r{=}8$ , int4 — it is the cheapest point past which added rank stops paying for itself. GQA combine rule: share-averaging beats group-max and group-mass on every measured statistic (mean, worst-head, 5th-percentile coverage), and trails a per-head oracle (costing $G\times$ the selection work) by only about 2 coverage points.

7. Design choices worth interrogating

Beyond the two already discussed above (share-average combine, and int4/r=8 as the shipped configuration), a few more design decisions deserve explicit why/alternative/boundary treatment.

Why fixed page size $B=16$ , and not adaptive page sizes? The obvious alternative is to let pages vary in size — larger pages where key content is homogeneous (cheap to summarize with low rank), smaller pages where content is heterogeneous (needs more rank per token to capture faithfully). The paper’s own rank-precision ablation (Fig. 5, discussed above) shows exactly this tension: larger pages need more rank at the same attended-token budget to hit the same fidelity, which is consistent with larger pages containing more within-page diversity to capture. The paper does not explore adaptive page sizing; the boundary here is that a fixed $B=16$ was presumably chosen to match vLLM’s native paging granularity for engineering simplicity, and it is a reasonable default, but it leaves an unexplored axis where a content-adaptive scheme might do meaningfully better, especially in the small-budget regime where every extra bit of rank efficiency matters most.

Why fixed per-head token budget $b$ , rather than a fixed fraction of context? The paper explicitly argues this is a feature, not a limitation: a fixed absolute budget gives a serving system a context-independent memory/compute footprint to provision, whereas a fixed-fraction budget grows unboundedly with context length, defeating the purpose of a sparse-attention system in the first place. The boundary condition is the reasoning-task budget floor discussed in Section 6 — a fixed budget that comfortably covers short reasoning traces may simply be insufficient for a much longer trace on a harder problem, and there is no adaptive mechanism in LOCKS to detect and respond to this at runtime; a practitioner would need to pick $b$ conservatively for their hardest expected workload, at the cost of some efficiency on easier workloads.

Why exact log-sum-exp mass as the target, rather than some other proxy? The alternative the paper explicitly contrasts against is the second-moment / block-moment family (COBS, SPLA — concurrent work), which is exact for Gaussian-distributed page content but has “its weakest worst-case control on the high-dynamic-range, peaky pages a carrier lives on.” In plain language: if attention logits within a page are roughly bell-curve distributed, matching the mean and variance (second moment) of that distribution is nearly as good as matching the full distribution. But carrier tokens are, by definition, outliers — a peaky, non-Gaussian spike in an otherwise flat distribution — and a summary that only captures mean/variance is specifically blind to exactly the kind of rare, extreme structure that carriers represent. LSE reconstruction (what LOCKS does) captures the entire logit distribution’s shape (via a per-key coefficient, not just two summary statistics), which is why it handles carriers better, at the cost of needing more bits per page than a pure second-moment summary would.

8. Limitations, as stated and as I see them

The paper is admirably direct about its own limitations, but let me lay them out and add commentary on what I think is understated.

As stated by the authors:

The retention guarantee (Theorem 1) is proven for the unquantized summary; the deployed int4/int8 summary’s actual retention is measured empirically, not certified per decode step.
The summary costs roughly a tenth of the cache it summarizes; page size is fixed at $B=16$ .
Since selection never reads keys/values, a fully offloaded serving path (keeping only summaries resident on the accelerator, with full KV offloaded to host memory or disk) is explicitly left as future work.
The page-level measurements characterizing the estimator in depth (App. B) use “a small number of records per model,” so they characterize the estimator’s behavior in detail rather than establishing broad coverage across many tasks and model families.
All optimality claims are explicitly class-relative: mass-ranking is minimax-optimal only among deterministic, value-blind selectors; the spectral basis is residual-optimal only among orthogonal rank- $r$ per-page linear reconstructions. Methods outside these classes (e.g., stochastic selectors like vAttention, which unifies top-k with sampling under statistical guarantees) are explicitly acknowledged as complementary, not dominated.

9. Critical analysis

Weaknesses and flaws specific to this paper. First, the headline efficiency numbers (2.0× TPOT reduction, 9.8× bytes-read reduction at 1M context) are measured on a single hardware target (H200 NVL) and a single model (GLM-4-9B-Chat-1M); it is not established how these numbers shift on different accelerators with different memory-bandwidth-to-compute ratios, or on models with different head dimensions/GQA group sizes, where the relative cost of the per-page eigendecomposition build step (which scales with $B^2 d$ roughly, not with context length) versus the KV-read savings could shift the crossover point at which LOCKS becomes worthwhile. Second, the paper reports the deployed quantized summary’s fidelity is “heavy-tailed at the extremes” but does not give a systematic characterization of which pages fall into that heavy tail — is it predictable from page content (e.g., pages with unusually high-dynamic-range keys), or effectively unpredictable per-page noise? If it is predictable, an adaptive per-page rank or precision scheme (spend more bits exactly on the pages likely to be in the heavy tail) seems like low-hanging fruit the paper does not pursue. Third, the retrieval/QA results (Fig. 2/Table 1) and the reasoning results (Fig. 3) are evaluated on different model families (Llama-3.1-8B / GLM-4-9B-Chat-1M for retrieval, Qwen3-4B for reasoning) — the paper does not report reasoning-task results on the retrieval models or vice versa, so we cannot directly compare whether the “budget floor” phenomenon in reasoning is a property of the task or interacts with model-specific attention-head behavior.

Limitations the authors understate or omit. The paper is careful about theoretical scope but somewhat less careful about systems scope: the per-page build step introduces a small but non-zero latency/compute cost every time a page finishes filling during generation (not just at the prefill boundary), and while the paper states this “runs off the decode critical path,” it does not report what fraction of total GPU compute this incremental building consumes at high generation throughput or in a heavily-batched serving scenario with many concurrent sequences each finishing pages at different times — this could matter more than the paper’s framing suggests once you are running dozens of concurrent long-generation reasoning traces simultaneously, each incrementally building new page summaries. Additionally, the shared, single set-of-selected-pages-per-GQA-group design (share-averaging) is presented as a clean win over per-head selection, but the paper’s own numbers show it trails a per-head oracle by “only” 2 coverage points on average — averages can mask a distribution where a minority of heads (e.g., specialized retrieval heads identified in prior work like DuoAttention) are disproportionately hurt by being forced to share a selection tuned to the group average rather than their own individual needs; the paper’s own related-work section acknowledges DuoAttention’s finding that different heads have very different retrieval-vs-streaming roles, but does not cross the two ideas to check whether LOCKS’s group-shared selection specifically underserves the “retrieval head” minority within a GQA group.

Concrete, specific improvement suggestions. (1) Report a per-page, per-quantization-tail characterization: bucket pages by measured reconstruction error and check whether error correlates with measurable page properties (dynamic range of key norms, spectral gap between the $r$ -th and $(r{+}1)$ -th singular value) — if it does, ship an adaptive-rank variant that spends extra bits only on high-tail-risk pages, likely recovering some of the quality gap at the same average byte budget. (2) Report incremental page-build overhead as a fraction of total decode-step compute under realistic multi-sequence batched serving (not just isolated per-step TPOT), since this is the number that determines whether LOCKS’s “off-critical-path” framing holds up under production load with continuous long-generation traffic. (3) Cross-validate the share-averaging design against DuoAttention’s retrieval-head/streaming-head distinction directly: measure per-head coverage loss from group-shared selection specifically for heads independently identified as “retrieval-type,” to check whether the average 2-point gap versus per-head oracle hides a much larger gap concentrated on the small subset of heads that matter most for exactly the tasks (retrieval, needle-in-haystack) this paper cares about. (4) Extend the reasoning-task evaluation (Qwen3-4B) to at least one of the retrieval-task models (Llama-3.1-8B, GLM-4-9B-Chat-1M) to disentangle whether the reasoning “budget floor” phenomenon is task-intrinsic or model-family-dependent. (5) Provide an explicit ablation of fixed vs. adaptive page size, since the paper’s own rank-vs-page-size ablation already shows the tension (larger pages need proportionally more rank), suggesting content-adaptive page sizing is a natural and currently-unexplored extension that could improve the rank-efficiency frontier directly.

10. Reproducibility notes

The paper states that proofs are in an appendix (App. A), the full evaluation protocol and budget accounting are documented (App. C), and code, kernels, container stacks, and measurement harnesses are released (App. F) — this is a genuinely strong reproducibility posture for a systems paper, going beyond just releasing a model checkpoint or a script, to releasing the actual measurement harness used to generate the reported numbers. Practically, if you want to reproduce or build on this work: (a) the shipped configuration is rank $r=8$ , page size $B=16$ , int4 basis / int8 coefficients — start there rather than re-deriving hyperparameters from scratch; (b) the vLLM version pinned in the paper is 0.24, installed as a pip-installable general plugin with no engine fork or patch required, which should make integration relatively low-friction if your serving stack is already on a compatible vLLM version; (c) the InfiniteBench, LongBench-v1, and RULER results all use identical records across every compared method within the same engine and the same FullKV reference, which is exactly the right methodological discipline for a fair sparse-attention comparison — worth checking that any comparison you run yourself preserves this (mismatched records or engines between “your method” and “baseline” numbers is a classic and easy-to-miss source of unfair comparisons in this literature).

11. Where LOCKS sits relative to other KV-cache efficiency work

It is worth placing LOCKS on the broader map of KV-cache efficiency techniques, because the field has genuinely fragmented into several largely orthogonal axes, and it is easy to conflate methods that solve different problems.

Eviction (H2O, StreamingLLM sink+window, R-KV) permanently discards tokens to save memory. LOCKS keeps everything and only skips reads. These are complementary — you could imagine running LOCKS-style selective reads over a cache that has also been shrunk via eviction, to attack both bottlenecks (capacity and bandwidth) simultaneously, though the paper does not evaluate this combination.
Quantization (GPTQ-style, KVQuant, and others) reduces bits-per-entry for every token, orthogonal to which tokens get attended. LOCKS’s own summary already uses quantization internally (int4/int8), but this is a distinct concern from cache quantization, which would additionally shrink the resident full-precision KV itself.
Query-aware selection (Quest, ShadowKV, Loki, RocketKV) is the direct comparison class, and the paper’s central contribution is a specific, falsifiable claim about why these methods leave quality on the table: representation scope. If you have read any of these prior papers, LOCKS is best understood as “the same overall recipe, but insisting the summary be fit per-page rather than per-sequence or per-cache, with a proof for why that choice is not merely an empirical tweak but structurally necessary.”
Trained sparsity / distilled gates (SeerAttention) bakes selection into the model via extra training. LOCKS’s training-free property is a genuine practical advantage if you cannot afford to fine-tune or distill a gate onto every model you want to accelerate, at the cost of not being able to learn task-specific selection patterns the way a trained gate potentially could.

12. Practical takeaways

If you are building or evaluating a long-context serving stack, three things from this paper are worth carrying forward regardless of whether you adopt LOCKS specifically. First, measure carrier-page retention, not just aggregate captured mass, when evaluating any sparse-attention selector — the two metrics can diverge sharply and aggregate mass alone will systematically overestimate quality on retrieval-heavy workloads. Second, if you are building a compact per-token or per-page summary for any KV-cache purpose (selection, eviction scoring, or otherwise), scope matters more than size — a small per-page-fit representation can beat a much larger shared representation, and Proposition 1 gives you a concrete reason to expect this rather than just an empirical curiosity. Third, when picking a sparse-decode budget for production, remember the budget-floor phenomenon from the reasoning evaluation: there is no free lunch below a task-dependent minimum budget, and no selector — however good — recovers quality the exact oracle itself cannot achieve at that budget; the practical lesson is to size your budget to your hardest expected reasoning workloads, not your average one.

13. A decision framework for adopting LOCKS-style summaries

If you are deciding whether a page-local spectral summary is the right tool for your own long-context serving stack, it helps to work through a short checklist rather than adopting the idea wholesale.

Is your bottleneck reads or capacity? If your KV cache comfortably fits in memory but decode throughput is limited by how many bytes you read per step (large batch, long context, memory-bandwidth-bound accelerator), LOCKS’s read-side optimization is directly applicable. If your bottleneck is that the cache itself does not fit at all, you need an eviction or offload strategy first (or in combination), since LOCKS does not shrink resident memory.
How carrier-sensitive is your workload? Retrieval-style tasks (needle-in-haystack, passkey retrieval, structured multi-key/multi-value lookups) are exactly where the carrier-retention property matters most, and where cheaper average-mass selectors (Quest-style envelopes) are most likely to silently fail. If your workload is closer to smooth long-document summarization, where no single token is individually decisive, a coarser and cheaper selector may be an acceptable trade.
Can you tolerate a fixed absolute budget? LOCKS’s context-independent per-head token budget is a deliberate design choice with a real boundary: reasoning workloads with a per-task budget floor (Section 6, Figure 5) need that floor identified and provisioned for in advance; there is no online adaptive mechanism here.
Is your serving stack already on a compatible vLLM version? The practical integration cost is close to zero if so (pip-installable plugin, no fork), which changes the cost-benefit calculus considerably compared to a method that requires patching or forking the serving engine.
Do you need a certified worst-case bound, or is measured empirical fidelity sufficient? Theorem 1’s guarantee applies to the unquantized summary; the deployed int4/int8 version is validated empirically rather than certified per step. For workloads with hard correctness requirements (as opposed to “mostly right, mostly of the time” quality targets), this distinction is worth taking seriously rather than treating the theorem as covering the shipped system unconditionally.

Working through this checklist before adopting any sparse-decode method (not just LOCKS) is a useful habit, since the KV-cache efficiency literature spans genuinely different problem settings (capacity vs. bandwidth, average-case vs. carrier-sensitive, static vs. growing working sets) that a single benchmark number rarely captures in full.

Conclusion

LOCKS makes a narrow but well-substantiated claim: when building a compact resident summary for sparse decode-time attention, the scope at which you fit your low-rank representation — per-page rather than per-sequence or cache-wide — is what determines whether the summary preserves the fidelity needed for good selection, and this is provable, not just an empirical tuning choice. The paper backs this claim with a clean impossibility theorem (Proposition 1), a composed retention guarantee tying reconstruction error all the way through to attention-output error (Theorem 1), and a genuinely comprehensive empirical evaluation that isolates exactly where rival methods break down link-by-link. The result — a training-free vLLM plugin achieving near-oracle quality at roughly 2% of read traffic, with measured 2.0-9.8× decode-time gains at extreme context — is a strong practical outcome, but the more durable contribution for the field is the “representation scope, not size” lens itself, which is likely to inform how the next generation of KV-cache summaries gets designed, regardless of whether they use exactly this eigendecomposition-based construction.