Merging Near-Duplicate KV Cache Tokens by Covering Dense Clusters with Cliques

A language model generating text keeps a key-value (KV) cache: stored "key" and "value" vectors for every earlier token, which each new token attends to. In long contexts this cache fills gigabytes, and reading it dominates the cost of each generation step. Current methods shrink the cache by evicting tokens. The tokens they keep, however, are often near-copies of each other. GraphKV reports that highly attended tokens have pairwise cosine similarity near 1.0, so the cache spends its budget on repeats.

We propose to merge groups of near-identical tokens into one cache entry that carries a count, instead of throwing tokens away. A group qualifies only if every pair in it is similar, which makes the error of the merge provably small for any future query. Finding such groups is the same problem that clique-search algorithms handle with "inverse graph branching": when a set of items is almost fully connected, you work on the few missing connections rather than the many present ones. Inside a redundant cluster, only a handful of token pairs are dissimilar. Splitting the cluster into certified groups then reduces to coloring that sparse graph of conflicts, which is cheap.

Core Claim

Build a threshold graph over cached tokens: nodes are tokens, and an edge joins two tokens whose keys are within distance $\epsilon_k$ and whose values are within $\epsilon_v$. Any clique in this graph (a group where every pair is joined) can be replaced by a single entry, the group's mean key $\bar k$ and mean value $\bar v$, with the attention score raised by $\log m$, where $m$ is the group size. For a query $q$ with $\|q\| \le Q$, every original score $q \cdot k_i$ differs from $q \cdot \bar k$ by at most $Q\epsilon_k$. The group's total attention weight is therefore preserved within a factor $e^{\pm Q\epsilon_k}$, and its value contribution within $\epsilon_v$. Eviction, by contrast, discards the group's weight entirely.

The combinatorial point is the following. A dense cluster in which each token is dissimilar to at most $t-1$ others is what the clique literature calls a $t$-plex. Its complement, the graph of dissimilar pairs, has maximum degree at most $t-1$. A proper coloring of that complement uses at most $t$ colors, and each color class is a clique of the original graph. So a $t$-plex of any size can be merged into at most $t$ certified entries, and the work scales with the number of dissimilar pairs rather than with the number of tokens squared.

This transfers the early-termination idea in Efficient k-Clique Listing: An Edge-Oriented Branching Strategy to a new setting. That paper switches from a dense subgraph to its sparse complement when searching for cliques, and reports that this switch drives much of its up-to-100x speedup. We do not list cliques. We use the same switch to cover a dense cluster with few cliques under a time budget.

Relation to Prior Work

GraphKV motivates this work. It identified the redundancy problem and down-weights tokens similar to already-selected ones through a decay propagated over a sparse similarity graph. The file notes that GraphKV's authors call this decay sensitive to its strength and number of rounds, with no principled way to set either. We differ in three ways. We merge rather than evict. We have a single threshold with a direct error meaning. We give a worst-case bound on how much the attention output changes.

Two graph-mining papers supply the cluster-finding step. Density-friendly Graph Decomposition gives GreedyLD, a linear-time peeling method that produces nested dense layers, and shows that plain $k$-core peeling can return an inner core that is less dense than the core enclosing it. We use GreedyLD to propose candidate clusters. Finding Subgraphs with Maximum Total Density and Limited Overlap shows how to extract several dense, low-overlap subgraphs; its "minimal densest subgraph" idea guides how we split overlapping clusters.

ASVD constrains the design and competes with it. It shrinks the KV cache by up to 50% through low-rank key and value projections, which works along the feature dimension. Merging reduces the number of tokens, so the two approaches can be stacked, and we test them together.

The research file contains no KV-cache method that merges tokens with a count correction. We cannot rule out such work outside the file, so our novelty claim is limited to what the file covers.

Research Program

The method has three stages.

The first stage runs periodically, at the end of prefill (processing the prompt) and then every few hundred generated tokens. In each attention head it builds the threshold graph. To keep this near-linear, it compares tokens only within buckets formed by locality-sensitive hashing (a hashing scheme that puts similar vectors in the same bucket), plus a window of recent tokens. This mirrors how GraphKV restricts comparisons to a few source tokens.

The second stage runs GreedyLD on this graph to find dense clusters. It then colors each cluster's complement with a greedy "saturation-degree" rule, which colors the node with the most distinctly colored neighbors first. When a complement is small, an exact branch over its edges finds the minimum number of cliques.

The third stage writes one merged entry per color class, storing the count $m$ so the attention kernel can add $\log m$ to that entry's score. Tokens outside any cluster are handled by an ordinary eviction policy (SnapKV), which keeps the overall memory budget fixed.

The analysis has two parts. First, we check whether the bound is tight in practice by measuring the attention-output error of each merged group against $Q\epsilon_k$ and $\epsilon_v$. Second, we measure how compressible the cache actually is: how many tokens fall into dense clusters, and how large $t$ is for those clusters, per layer and per head. That tells us whether redundancy concentrates in particular heads, which would justify giving different heads different budgets.

Baselines

The naive reference points are the full, uncompressed cache, which gives the accuracy ceiling, and SnapKV alone at a 10% budget, which gives the floor.

The strongest existing competitor in the file is SnapKV or PyramidKV combined with GraphKV. On LLaMA-3-8B at a 10% KV budget, GraphKV reports that Needle In A Haystack accuracy rises from 87.7% to 95.9% on top of SnapKV and from 90.3% to 96.9% on top of PyramidKV, and that LongBench QA improves by about 3%. We will reproduce GraphKV with its published settings, then give it the same tuning budget we give our threshold: a grid over decay strength and number of rounds, matched in trials. We will beat it only if we exceed its Needle accuracy and LongBench average at the same memory budget, where memory counts our stored group sizes, and at no worse per-token latency.

Two further baselines address clustering more directly. The first merges groups found by leader clustering or by k-means on concatenated key-value vectors, with the same count correction. It isolates whether the clique structure matters. The second keeps the same clique groups but evicts all but one representative, with no count correction. It isolates whether merging, rather than eviction, is what helps.

An ablation replaces complement coloring with greedy clique extraction applied directly to the dense graph. It measures the runtime benefit of the inverse representation.

Finally, ASVD-style low-rank KV projections, run alone and stacked with merging, test whether the two sources of savings add up. All methods use the same model, calibration-free settings, prompts, and a single A100.

Why not just…?

Why not just tune GraphKV's decay? Tuning can close part of the gap, and the matched tuning budget above allows for that. But decay only re-ranks which tokens to evict: any evicted token's share of attention is gone. Our eviction-versus-merge ablation measures that loss directly. If GraphKV at its best setting matches merging, the conclusion is that the lost attention mass does not matter at a 10% budget, and we will report it that way.

Why not just cluster the keys with leader clustering or k-means and merge? This is the real threat. Keys live in a metric space, so ball-shaped clusters also bound the merge error. Our argument is specific. At a matched certified error, a ball centered on a data point must have half the radius of a clique's diameter. In high dimension, a set of diameter $\epsilon$ generally needs radius close to $\epsilon/\sqrt{2}$ to be covered, which is Jung's theorem. So a clique cover should need fewer entries than leader clustering at the same guarantee. At matched empirical error the advantage may vanish. The experiments therefore report both. If leader clustering ties at matched empirical error, the lasting contributions are count-corrected merging and the per-head compressibility analysis, and the graph solver matters only when a guarantee is required.

Why not just quantize or low-rank the cache instead? ASVD already cuts KV memory by up to 50% through low-rank projections. That reduces the size of each entry and leaves redundancy across tokens untouched. The stacked experiment shows whether the savings compound. If they do not, we will say that merging adds nothing beyond per-entry compression.

Proposed Experiments

All runs use LLaMA-3-8B with KV budgets of 5%, 10%, and 20%, on LongBench's 16 tasks and on Needle In A Haystack up to 8K tokens (the lengths GraphKV evaluated), with a longer-context extension. We report task accuracy, peak cache memory including stored counts, per-token decode latency, and the time spent in the merge stage.

The first decisive check sweeps error level. For each $\epsilon$, it plots the number of cache entries against measured attention-output error for clique cover, leader clustering, and k-means. Clique cover must use fewer entries at matched certified error, or the combinatorial component is unjustified.

The second decisive check compares merge against evict at identical groupings, which shows whether preserving attention mass drives any accuracy gain.

The third decisive check verifies that complement coloring runs in time proportional to the number of dissimilar pairs and stays below 5% of decode time. Otherwise the merge stage undoes the bandwidth savings it was meant to deliver.