PuzzleKV: Page-Wise Low-Rank Decomposition for KV Cache Compression

# PuzzleKV: Page-Wise Low-Rank Decomposition for KV Cache Compression
Source: [https://arxiv.org/html/2608.23843](https://arxiv.org/html/2608.23843)
###### Abstract

Long\-context inference in large language models \(LLMs\) is increasingly limited by the memory required for the key\-value \(KV\) cache\. KV cache compression addresses this problem by reducing the storage cost of previous tokens\. Among existing approaches, low\-rank compression is particularly attractive because it represents every token in reduced dimensions\. Previous low\-rank methods typically derive fixed projection spaces from model weights, construct fixed spaces from calibration activations, or construct a shared basis over a broad cache region\. Such representations may not capture detailed but important information\. We partition each per\-head KV cache into fixed\-length logical pages and observe substantial low\-rank structure within individual pages\. Based on this observation, we propose PuzzleKV, a training\- and calibration\-free method that treats each completed page as an independent compression unit\. PuzzleKV decomposes pages within each layer and KV head, computes attention directly over dense and factorized pages, and incrementally compresses newly eligible pages during autoregressive decoding\. Experiments across models, context lengths, and benchmarks demonstrate the effectiveness of PuzzleKV under matched storage budgets\. At approximately 60% of the original KV cache storage, PuzzleKV achieves more than 96% of Full KV performance across both evaluated models and all benchmark settings, with substantial gains over Global SVD on RULER and competitive performance on LongBench\. To achieve a more aggressive compression ratio, PuzzleKV can be further combined with quantization while retaining more than 93% of Full KV performance using only 18\.7% of the original storage\.

## 1Introduction

Large language models increasingly rely on few\-shot demonstrations, chains of thought, and interleaved reasoning and action to solve complex tasks\[[16](https://arxiv.org/html/2608.23843#bib.bib1),[18](https://arxiv.org/html/2608.23843#bib.bib2),[23](https://arxiv.org/html/2608.23843#bib.bib3)\]\. As these inputs grow, longer context windows allow LLMs to access more task\-relevant information, but they also place substantial memory pressure on inference\.

Autoregressive decoders store the attention keys and values of previous tokens in a key\-value \(KV\) cache to avoid recomputing them at every generation step\[[17](https://arxiv.org/html/2608.23843#bib.bib6),[9](https://arxiv.org/html/2608.23843#bib.bib7)\]\. For a model withLLlayers,Hk​vH\_\{kv\}KV heads, head dimensiondd, and context lengthTT, a single request holds2​L​Hk​v​T​d2LH\_\{kv\}TdKV elements before batching\. Qwen3\-32B\[[22](https://arxiv.org/html/2608.23843#bib.bib8)\], for example, has 64 layers, 8 KV heads, and head dimension 128, so under BF16 a single 128K\-token sequence requires about 32 GiB of KV cache\. Because this footprint grows linearly with both context length and serving batch size, KV cache compression is essential for efficient long\-context inference\.

Existing methods reduce KV cache storage through token eviction, quantization, or low\-rank decomposition\. Eviction discards selected tokens\[[27](https://arxiv.org/html/2608.23843#bib.bib15)\]and quantization stores keys and values at lower precision\[[12](https://arxiv.org/html/2608.23843#bib.bib19)\], whereas low\-rank methods represent keys and values in lower\-dimensional spaces\. The latter differ mainly in the source of the compression space: some factorize model projection weights\[[2](https://arxiv.org/html/2608.23843#bib.bib9),[26](https://arxiv.org/html/2608.23843#bib.bib10)\], often requiring calibration or per\-model offline processing, while others build or update a basis from the KV cache produced at inference\[[28](https://arxiv.org/html/2608.23843#bib.bib13),[3](https://arxiv.org/html/2608.23843#bib.bib14)\]\. In either case, a single basis is shared across a broad cache region, favoring directions that dominate overall reconstruction and potentially missing sparse but task\-critical information\.

To capture this local structure at a finer granularity, we take inspiration from the fixed\-size blocks used by PagedAttention to manage KV cache memory\[[9](https://arxiv.org/html/2608.23843#bib.bib7)\]and reinterpret the logical page as a unit of compression\. This choice is well founded: our analysis shows substantial low\-rank redundancy within individual key and value pages across models, layers, and KV heads \(Figure[2](https://arxiv.org/html/2608.23843#S3.F2)\)\. Using the page as the compression unit lets a single abstraction govern both low\-rank representation and incremental cache updates, while the uniform shape and independence of pages allow their decompositions to be processed in batches on GPUs\.

Based on this design, we propose PuzzleKV, a training\- and calibration\-free page\-wise low\-rank KV cache compression method\. PuzzleKV independently decomposes completed pages within each layer and KV head, while keeping a small sink region and recent window in dense form\. Its mixed attention kernel directly processes dense and factorized pages without reconstructing the historical KV cache\. During autoregressive decoding, newly eligible pages are incrementally converted into factor storage\.

Our main contributions are as follows:

- •We introduce PuzzleKV, a training\- and calibration\-free method that independently factorizes completed KV pages within each layer and KV head, preserving every token through page\-local low\-rank representations\.
- •We implement PuzzleKV with batched page decomposition, direct attention over dense and factorized pages without reconstruction, and incremental page conversion during decoding\.
- •We evaluate PuzzleKV on Qwen3\-8B and Llama\-3\.1\-8B\-Instruct across RULER and LongBench\. At approximately 60% of Full KV storage, PuzzleKV achieves more than 96% of Full KV performance across all evaluated settings, establishes substantial gains over Global SVD on RULER, and achieves competitive performance on LongBench\. Combined with per\-factor INT4 quantization, it uses only 18\.7% of the original storage while achieving more than 93% of Full KV performance\.

## 2Related Work

KV cache compression is essential for memory\-efficient LLM inference, and existing methods broadly fall into three categories: low\-rank decomposition, quantization, and eviction\[[10](https://arxiv.org/html/2608.23843#bib.bib23)\]\.

#### Low\-Rank KV Cache Compression\.

Low\-rank methods reduce KV cache storage by representing keys and values in lower\-dimensional spaces\. Palu\[[2](https://arxiv.org/html/2608.23843#bib.bib9)\]and LoRC\[[26](https://arxiv.org/html/2608.23843#bib.bib10)\]factorize the projection matrices, allowing the model to cache low\-dimensional intermediate representations\. ECKVH\[[24](https://arxiv.org/html/2608.23843#bib.bib11)\]and EigenAttention\[[13](https://arxiv.org/html/2608.23843#bib.bib12)\]construct fixed compression bases from activations collected on a calibration dataset\. OjaKV\[[28](https://arxiv.org/html/2608.23843#bib.bib13)\]updates a sequence\-level low\-rank basis online, while xKV\[[3](https://arxiv.org/html/2608.23843#bib.bib14)\]exploits cross\-layer redundancy during prefill\. PuzzleKV instead independently factorizes each completed page within each layer and KV head\.

#### KV Cache Quantization\.

Quantization reduces KV cache memory by storing keys and values at lower numerical precision, using schemes such as asymmetric low\-bit quantization\[[12](https://arxiv.org/html/2608.23843#bib.bib19)\], polar transformations of angular components\[[7](https://arxiv.org/html/2608.23843#bib.bib21)\], and distortion\-aware vector quantization\[[25](https://arxiv.org/html/2608.23843#bib.bib22)\]\. PuzzleKV instead reduces the dimensionality of each KV page via low\-rank decomposition, and remains complementary to quantization, which can be applied to its low\-rank factors\.

#### KV Cache Eviction\.

Eviction methods reduce KV cache storage by keeping only tokens expected to remain useful, but an evicted token is permanently lost for future inference\. H2O\[[27](https://arxiv.org/html/2608.23843#bib.bib15)\]retains heavy\-hitter and recent tokens, StreamingLLM\[[21](https://arxiv.org/html/2608.23843#bib.bib16)\]keeps attention sinks with a local window, and SnapKV\[[11](https://arxiv.org/html/2608.23843#bib.bib18)\]selects important positions from prompt\-time attention\. Unlike eviction methods, PuzzleKV retains every token in compressed form\.

## 3Methodology

Figure 1:Overview of PuzzleKV\. The workflow covers page partitioning and page\-wise decomposition during prefill, followed by mixed paged attention and incremental cache updates during decoding\.### 3\.1Design Principle: Page as a Local Subspace

A key design choice in low\-rank KV compression is the granularity at which tokens share a low\-rank basis\. A single basis spanning the entire prompt maximizes reuse, while the sequence itself spans regions with distinct dominant directions\. Assigning each KV page its own compact basis lets every region be represented by the directions most relevant to it, yielding fine\-grained low\-rank representations that together cover a richer set of directions across the sequence while keeping each page strongly low\-rank\. This design pays off when individual pages are themselves low\-rank, which we confirm by examining how accurately KV pages reconstruct across different ranks and page sizes in Qwen3\-8B and Llama\-3\.1\-8B\-Instruct\. As shown in Figure[2](https://arxiv.org/html/2608.23843#S3.F2), page\-level low\-rank structure is consistently observed across both models and all evaluated page sizes\. AtP=32P=32, although the required ranks vary across layers and KV heads, they remain below the full page rank across all evaluated layers and heads\. Together, these results establish page\-level low\-rank structure as a consistent property across the evaluated models, page sizes, layers, and KV heads\.

### 3\.2Preliminaries: Low\-Rank KV Cache

#### KV Cache and Attention\.

At each Transformer layer, the key and value projections produceK,V∈ℝHk​v×T×dK,V\\in\\mathbb\{R\}^\{H\_\{kv\}\\times T\\times d\}, whereHk​vH\_\{kv\}is the number of KV heads,TTis the sequence length, andddis the head dimension\. During autoregressive decoding, each new key–value pair is appended to the cache along the sequence dimension\. Omitting the head index for clarity, attention for a queryQQis computed as

Attn⁡\(Q,K,V\)=softmax⁡\(Q​K⊤d\)​V\.\\operatorname\{Attn\}\(Q,K,V\)=\\operatorname\{softmax\}\\left\(\\frac\{QK^\{\\top\}\}\{\\sqrt\{d\}\}\\right\)V\.\(1\)

#### Truncated SVD\.

For a matrixX∈ℝn×dX\\in\\mathbb\{R\}^\{n\\times d\}with singular value decompositionX=U​Σ​W⊤X=U\\Sigma W^\{\\top\}, where the singular values inΣ\\Sigmaare arranged in descending order, its rank\-rrtruncated approximation retains the leadingrrcomponents,X^r=Ur​Σr​Wr⊤\.\\widehat\{X\}\_\{r\}=U\_\{r\}\\Sigma\_\{r\}W\_\{r\}^\{\\top\}\.Here,Ur∈ℝn×rU\_\{r\}\\in\\mathbb\{R\}^\{n\\times r\},Σr∈ℝr×r\\Sigma\_\{r\}\\in\\mathbb\{R\}^\{r\\times r\}, andWr∈ℝd×rW\_\{r\}\\in\\mathbb\{R\}^\{d\\times r\}\. By the Eckart–Young–Mirsky theorem,X^r\\widehat\{X\}\_\{r\}minimizes‖X−X^‖F\\\|X\-\\widehat\{X\}\\\|\_\{F\}over all matricesX^\\widehat\{X\}with rank at mostrr\.

### 3\.3Method: PuzzleKV

Figure[1](https://arxiv.org/html/2608.23843#S3.F1)summarizes the PuzzleKV workflow, which spans a prefill stage \(left\) and a decoding stage \(right\) that operate on a single hybrid KV cache\.

During prefill, PuzzleKV ① computes the standard dense KV cache, ② partitions each layer and KV head into fixed\-size pages, and ③ factorizes every completed page while keeping the attention sink and a local window in dense form\. The result is a hybrid cache in which sink and recent pages stay dense while historical pages are stored as low\-rank factors\. During decoding, ④ each query attends jointly over dense and factorized pages and merges their partial results through online softmax without reconstructing the historical cache; then ⑤ the new key–value pair is appended to the most recent dense page, and once that page fills and leaves the local window it is factorized and moved into low\-rank storage\. Steps ④ and ⑤ form the steady\-state decoding loop: the mixed\-attention kernel reads the hybrid cache that the incremental update continually maintains, keeping every token in compressed form throughout generation\.

Figure 2:Page\-level low\-rank structure across models, layers, KV heads, and page sizes\. Left: Reconstruction accuracy under different ranks and page sizes\. Right: Required rank for 80% reconstruction accuracy across layers atP=32P=32, with individual KV heads shown in thin lines and their mean in bold\.#### Page\-Wise Low\-Rank KV Cache Construction ①, ②, ③\.

PuzzleKV treats each completed KV page as an independent low\-rank subspace while retaining every token in compressed form\. During prefill, it computes the standard dense KV cache and partitions the tokens at each layer and KV head into fixed\-size pages ofPPtokens\. PuzzleKV then retains two regions in dense form: an initial*sink page*holding the first tokens, which attract a disproportionate share of attention and are cheap to keep uncompressed\[[21](https://arxiv.org/html/2608.23843#bib.bib16)\], and a moving*local window*of the most recent pages, whose tokens are accessed most frequently and whose current page is still being filled during decoding\. Every other completed page is independently factorized with truncated SVD, replacing each eligible dense page by two factors:

X^p\\displaystyle\\widehat\{X\}\_\{p\}=Lp\(X\)​Rp\(X\),\\displaystyle=L\_\{p\}^\{\(X\)\}R\_\{p\}^\{\(X\)\},\(2\)Lp\(X\)\\displaystyle L\_\{p\}^\{\(X\)\}=Up,rX\(X\),Rp\(X\)=Σp,rX\(X\)\(Wp,rX\(X\)\)⊤,\\displaystyle=U\_\{p,r\_\{X\}\}^\{\(X\)\},\\hskip 18\.49988ptR\_\{p\}^\{\(X\)\}=\\Sigma\_\{p,r\_\{X\}\}^\{\(X\)\}\\left\(W\_\{p,r\_\{X\}\}^\{\(X\)\}\\right\)^\{\\top\},whereX∈\{K,V\}X\\in\\\{K,V\\\}, withrX=rKr\_\{X\}=r\_\{K\}for keys andrX=rVr\_\{X\}=r\_\{V\}for values\. The resulting cache holds dense sink and recent pages alongside factorized historical pages, discarding no token\. Excluding pages stored in dense form, the storage ratio of a factorized key–value page pair is

ρpage=\(rK\+rV\)​\(P\+d\)2​P​d\.\\rho\_\{\\mathrm\{page\}\}=\\frac\{\(r\_\{K\}\+r\_\{V\}\)\(P\+d\)\}\{2Pd\}\.\(3\)
To obtain these factors efficiently, PuzzleKV avoids invoking a separate SVD on everyP×dP\\times dpage\. Because KV pages are short and wide \(P<dP<d\) and share the same shape, it batches them and recovers the leading left singular subspace from the smallerP×PP\\times PGram matrixGp=Xp​Xp⊤G\_\{p\}=X\_\{p\}X\_\{p\}^\{\\top\}, takingLp\(X\)=Qp,rXL\_\{p\}^\{\(X\)\}=Q\_\{p,r\_\{X\}\}as its top\-rXr\_\{X\}eigenvectors andRp\(X\)=Qp,rX⊤​XpR\_\{p\}^\{\(X\)\}=Q\_\{p,r\_\{X\}\}^\{\\top\}X\_\{p\}\. Since the eigenvectors ofXp​Xp⊤X\_\{p\}X\_\{p\}^\{\\top\}are the left singular vectors ofXpX\_\{p\}, this yields exactly the truncated\-SVD factors above while mapping to batched GPU operations\.

#### Attention over Mixed KV Pages ④\.

PuzzleKV computes attention over dense and factorized pages through a custom mixed\-attention path, evaluating each factorized page directly from its stored factors and never reconstructing the historical dense cache\. This avoids the transient dense buffers that explicit reconstruction would create, which prior work identifies as a source of lost memory savings\[[14](https://arxiv.org/html/2608.23843#bib.bib24)\]\. For a queryqqand a factorized pageK^p=Lp\(K\)​Rp\(K\)\\widehat\{K\}\_\{p\}=L\_\{p\}^\{\(K\)\}R\_\{p\}^\{\(K\)\},V^p=Lp\(V\)​Rp\(V\)\\widehat\{V\}\_\{p\}=L\_\{p\}^\{\(V\)\}R\_\{p\}^\{\(V\)\}, PuzzleKV computes the page\-local softmax state

sp=\(q​\(Rp\(K\)\)⊤\)​\(Lp\(K\)\)⊤d,\\displaystyle s\_\{p\}=\\frac\{\\left\(q\(R\_\{p\}^\{\(K\)\}\)^\{\\top\}\\right\)\(L\_\{p\}^\{\(K\)\}\)^\{\\top\}\}\{\\sqrt\{d\}\},\(4\)mp=maxj⁡sp,j,\\displaystyle m\_\{p\}=\\max\_\{j\}s\_\{p,j\},ℓp=∑jexp⁡\(sp,j−mp\),\\displaystyle\\ell\_\{p\}=\\sum\_\{j\}\\exp\(s\_\{p,j\}\-m\_\{p\}\),op=\(exp⁡\(sp−mp\)​Lp\(V\)\)​Rp\(V\)\.\\displaystyle o\_\{p\}=\\left\(\\exp\(s\_\{p\}\-m\_\{p\}\)L\_\{p\}^\{\(V\)\}\\right\)R\_\{p\}^\{\(V\)\}\.wheresps\_\{p\}are the attention scores,mpm\_\{p\}andℓp\\ell\_\{p\}the running maximum and normalizer, andopo\_\{p\}the unnormalized page output\. The parenthesization contractsqqwith the small factors first, so the reconstructedK^p\\widehat\{K\}\_\{p\}andV^p\\widehat\{V\}\_\{p\}are never materialized\. Dense sink and recent pages produce the same state\(mp,ℓp,op\)\(m\_\{p\},\\ell\_\{p\},o\_\{p\}\)from their storedKpK\_\{p\}andVpV\_\{p\}\. PuzzleKV then merges all pages through the online\-softmax reduction of FlashAttention\[[4](https://arxiv.org/html/2608.23843#bib.bib25)\]:

m=maxp⁡mp,\\displaystyle m=\\max\_\{p\}m\_\{p\},\(5\)o=∑pexp⁡\(mp−m\)​op∑pexp⁡\(mp−m\)​ℓp\.\\displaystyle o=\\frac\{\\sum\_\{p\}\\exp\(m\_\{p\}\-m\)o\_\{p\}\}\{\\sum\_\{p\}\\exp\(m\_\{p\}\-m\)\\ell\_\{p\}\}\.This yields globally normalized attention over dense and factorized pages without materializing any factorized historical page\.

#### Incremental Cache Update ⑤\.

PuzzleKV extends compression from prefill to the entire decoding process, keeping the hybrid cache current as generation proceeds rather than compressing only once\. Each new key–value pair is appended to the most recent dense page and immediately participates in attention\. When a decoding step fills that page, it enters the dense local window, and the oldest page leaving the window is factorized once, with its factors written to preallocated storage and its dense slot released\. Previously factorized pages are never revisited, so each step incurs at most one page factorization and every generated token remains in compressed form\.

## 4Experiments

We evaluate PuzzleKV across two models and long\-context benchmarks along three axes: quality preservation under a matched storage budget, sensitivity to its key design choices, and the runtime overhead and logical KV cache footprint of our implementation\. We first present the experimental setup and main accuracy results, followed by quantization compatibility, ablation studies, and runtime and memory measurements\.

### 4\.1Experimental Setup

#### Models and Benchmarks\.

We evaluate PuzzleKV on Qwen3\-8B \(Qwen3;[22](https://arxiv.org/html/2608.23843#bib.bib8)\) and Llama\-3\.1\-8B\-Instruct \(Llama3\.1;[6](https://arxiv.org/html/2608.23843#bib.bib20)\) across two complementary long\-context benchmarks\. RULER\[[8](https://arxiv.org/html/2608.23843#bib.bib5)\], evaluated at input lengths of 16K and 32K, measures compression\-induced degradation on controlled synthetic tasks, while LongBench\[[1](https://arxiv.org/html/2608.23843#bib.bib4)\]assesses performance on real\-world long\-context tasks after compression\.

#### Baselines\.

We compare against two representative compression methods and one controlled baseline\. Palu\[[2](https://arxiv.org/html/2608.23843#bib.bib9)\]represents calibration\-based, weight\-side low\-rank compression, and H2O\[[27](https://arxiv.org/html/2608.23843#bib.bib15)\]represents token eviction\. Global SVD is our controlled baseline for isolating the effect of compression granularity: it applies a single shared basis to the compressible region of each layer and KV head, in contrast to PuzzleKV’s per\-page basis\. We omit xKV\[[3](https://arxiv.org/html/2608.23843#bib.bib14)\], which exploits an orthogonal source of redundancy across layers, while OjaKV\[[28](https://arxiv.org/html/2608.23843#bib.bib13)\]is reported in the supplementary material due to its unstable reproduced performance across models and tasks\.

Table 1:RULER performance of Llama\-3\.1\-8B\-Instruct and Qwen3\-8B at 16K and 32K context lengths under a KV cache storage budget of 60%\.
#### Implementation\.

We implement PuzzleKV and Global SVD in Hugging Face Transformers\[[19](https://arxiv.org/html/2608.23843#bib.bib27)\]and evaluate all methods with lm\-eval\-harness\[[5](https://arxiv.org/html/2608.23843#bib.bib26)\]on NVIDIA GH200 GPUs\. Llama\-3\.1\-8B\-Instruct uses its default chat template, and all evaluations use greedy decoding, so the reported accuracies are deterministic and obtained from a single run\. Unless otherwise stated, PuzzleKV uses a page size ofP=32P=32and ranks\(rK,rV\)=\(16,14\)\(r\_\{K\},r\_\{V\}\)=\(16,14\), giving a KV cache storage ratio of approximately 0\.6\. The uncompressed dense region consists of one sink page \(32 tokens\) together with the most recently completed page and the current incomplete page\.

Table 2:Category\-level LongBench results \(%\) atρ=0\.6\\rho=0\.6\. Complete per\-task results are provided in the supplementary material\.

### 4\.2Main Results

We evaluate PuzzleKV and the baselines on RULER and LongBench under a matched budget ofρ≈0\.6\\rho\\approx 0\.6\. PuzzleKV compresses each completed page and keeps only a few dense sink and recent pages; ignoring these, its factorized\-page storage ratio isρPuzzleKV=\(rK\+rV\)​\(P\+d\)2​P​d≈0\.586\\rho\_\{\\text\{PuzzleKV\{\}\}\}=\\frac\{\(r\_\{K\}\+r\_\{V\}\)\(P\+d\)\}\{2Pd\}\\approx 0\.586at\(rK,rV\)=\(16,14\)\(r\_\{K\},r\_\{V\}\)=\(16,14\),P=32P=32, and head dimensiond=128d=128\(shared by both models\)\. Global SVD instead shares a single basis over the compressible region of each layer and KV head: for an input of lengthSSit storesρglobal=r⁡\(S\+d\)S​d\\rho\_\{\\mathrm\{global\}\}=\\frac\{r\(S\+d\)\}\{Sd\}, and we selectrrper input to match the budget, giving ranks of 76–78\. Both PuzzleKV and Global SVD decompose post\-RoPE keys, which avoids extra RoPE transformations\[[15](https://arxiv.org/html/2608.23843#bib.bib28)\]at cache access; pre\-RoPE keys are slightly more compressible but give only a small accuracy gain in our ablation\. Complete results and configurations are provided in the supplementary material\. For Palu, we use the official G\-LRD variant \(four\-head groups, Fisher\-uniform rank allocation, no quantization\); for H2O, we follow its equal\-split policy, allocating0\.30\.3of the KV budget to heavy\-hitter tokens and0\.30\.3to recent tokens\.

#### Results on RULER\.

Table[1](https://arxiv.org/html/2608.23843#S4.T1)reports RULER results at input lengths of 16K and 32K\. PuzzleKV achieves the highest average among all compressed methods in every model–context setting\. On Llama3\.1, PuzzleKV obtains 88\.82 and 84\.39 at 16K and 32K, corresponding to 96\.2% and 96\.4% of Full KV performance\. It leads Global SVD by 26\.21 and 25\.01 points and H2O by 20\.06 and 22\.64 points, while remaining competitive with Palu \(within 1\.56 and 1\.71 points\)\. On Qwen3, PuzzleKV obtains 90\.73 and 87\.53 at 16K and 32K, corresponding to 99\.3% and 97\.9% of Full KV performance\. It leads Global SVD by 14\.22 and 15\.64 points, H2O by 26\.73 and 24\.58 points, and Palu by 11\.71 and 16\.50 points\. Overall, page\-wise low\-rank compression delivers strong and consistent accuracy across the evaluated models, context lengths, and task types\.

#### Results on LongBench\.

Table[2](https://arxiv.org/html/2608.23843#S4.T2)reports category\-level LongBench results\. PuzzleKV scores 45\.33 on Llama3\.1 and 29\.48 on Qwen3, corresponding to 98\.9% and 98\.7% of Full KV performance\. Among compressed methods it ranks first on Qwen3, leading H2O by 0\.38 points, and second on Llama3\.1, within 0\.28 points of H2O; it further outperforms Global SVD by 1\.07 and 0\.99 points and Palu by 3\.12 and 4\.46 points on Llama3\.1 and Qwen3, respectively\. These results show strong cross\-model accuracy on real\-world tasks and a comparable or consistent advantage over the other low\-rank baselines\.

#### Observations\.

Because RULER consists of controlled synthetic tasks that isolate specific capabilities more cleanly than the real\-world tasks in LongBench, we examine the tasks on which PuzzleKV achieves especially large gains to characterize the benefits of page\-wise compression\.

Page\-wise versus sequence\-level bases\.PuzzleKV shows a pronounced advantage on NIAH\-S1 and Variable Tracking \(VT\), where a sequence\-level basis collapses\. NIAH\-S1 hides a unique key–value pair in a highly repetitive context\[[8](https://arxiv.org/html/2608.23843#bib.bib5)\]: at 16K / 32K, PuzzleKV scores 98\.80 / 99\.80 on Llama3\.1 and 100\.00 / 100\.00 on Qwen3, whereas Global SVD scores 0\.00 / 0\.00 and 3\.60 / 0\.00\. VT requires recovering a five\-variable, four\-hop assignment chain among repeated distractors: PuzzleKV scores 98\.80 / 98\.28 on Llama3\.1 and 99\.96 / 99\.76 on Qwen3, versus 0\.04 / 0\.00 and 41\.40 / 7\.16 for Global SVD\. In both cases,page\-local bases preserve the sparse or intermediate content that a sequence\-level objective discards once repeated background dominates its reconstruction\.

Compression versus eviction\.PuzzleKV also holds a clear advantage on NIAH\-S3, which requires exact recovery of a long UUID\. At 16K / 32K it scores 82\.00 / 83\.00 on Llama3\.1 and 99\.00 / 98\.60 on Qwen3, whereas H2O scores 33\.40 / 31\.60 on both models\.Because PuzzleKV retains every token in compressed form, the full UUID stays available to later queries; H2O, having irreversibly evicted the relevant KV entries, frequently emits incomplete or corrupted UUIDs\.

### 4\.3Quantization Compatibility

We further demonstrate PuzzleKV’s compatibility with low\-bit quantization, following the broader success of post\-training low\-bit quantization\[[20](https://arxiv.org/html/2608.23843#bib.bib17)\]\. For each truncated decomposition, we absorb the singular valuesΣ\\Sigmainto the two page\-wise factors, constructingL~X,p=UX,p​ΣX,p1/2,R~X,p=ΣX,p1/2​VX,p⊤\.\\widetilde\{L\}\_\{X,p\}=U\_\{X,p\}\\Sigma\_\{X,p\}^\{1/2\},\\widetilde\{R\}\_\{X,p\}=\\Sigma\_\{X,p\}^\{1/2\}V\_\{X,p\}^\{\\top\}\.and apply symmetric INT4 quantization to each factor matrix: column\-wise forL~K,p\\widetilde\{L\}\_\{K,p\}andR~K,p\\widetilde\{R\}\_\{K,p\}, row\-wise forL~V,p\\widetilde\{L\}\_\{V,p\}, and column\-wise forR~V,p\\widetilde\{R\}\_\{V,p\}\. For the direct INT3 and INT4 baselines, we apply per\-channel quantization to keys and per\-token quantization to values within each uncompressed KV page\[[12](https://arxiv.org/html/2608.23843#bib.bib19)\]while keeping the same dense sink and local regions\.

Table[3](https://arxiv.org/html/2608.23843#S4.T3)shows that combining PuzzleKV with INT4 reduces the KV storage ratio to 0\.187 while staying within 2\.58 points on Llama3\.1 and 0\.53 points on Qwen3 of the unquantized PuzzleKV results\. At this smallest budget, it remains competitive with direct INT3 on Full KV \(storage ratio 0\.223\) despite a smaller budget, staying close on Qwen3 \(90\.20 vs\. 91\.02\) while trailing on Llama3\.1 \(86\.24 vs\. 88\.51\)\. Direct INT4 \(storage ratio 0\.283\) attains higher accuracy but at a larger budget\. These results show that factor quantization composes with page\-wise low\-rank compression to reach an aggressive 0\.187 storage regime with limited accuracy loss\.

Table 3:Average RULER scores \(%\) at 16K input length under different precision settings\.
### 4\.4Ablation Study

We conduct all ablation studies on RULER using Llama3\.1 with a 16K input length, as this setting more clearly differentiates among compression methods\.

#### Rank Selection\.

We examine how the total rank budget and its allocation between keys and values affect downstream performance\. As shown in Figure[3](https://arxiv.org/html/2608.23843#S4.F3)\(a\), increasing the shared K/V rank consistently improves performance, with diminishing gains beyond rank 16\. Figure[3](https://arxiv.org/html/2608.23843#S4.F3)\(b\) compares different allocations under the fixed budgetrK\+rV=30r\_\{K\}\+r\_\{V\}=30\. The\(16,14\)\(16,14\)configuration outperforms\(14,16\)\(14,16\)in both the overall and Retrieval averages, indicating that an insufficient key rank cannot be offset by assigning more rank to values\. IncreasingrKr\_\{K\}from 16 to 18 provides little additional improvement in the overall average\. We therefore use\(rK,rV\)=\(16,14\)\(r\_\{K\},r\_\{V\}\)=\(16,14\)as the default configuration, allocating slightly more rank to keys without increasing the total storage budget\. Complete ablation results are provided in the supplementary material\.

Figure 3:Overall and Retrieval scores over different KV rank configurations\.†\\daggerdenotes the configuration used in the main experiment\.
#### Page Size Selection\.

Figure[4](https://arxiv.org/html/2608.23843#S4.F4)compares different page sizes under the same compression ratio\. At the same compression ratio, PuzzleKV remains effective across all evaluated page sizes\. As the page size grows from 16 to 32, accuracy improves substantially\. However, when expand the page size to 64, it brings a smaller gain but noticeably higher decomposition latency\. We therefore useP=32P=32in all experiments\.

Figure 4:Full RULER average score and decomposition overhead during prefilling across page sizes \(KV cache budgetρ=0\.6\\rho=0\.6\)\.

### 4\.5System Efficiency

We evaluate PuzzleKV on Qwen3 using sampled NIAH\-S1 inputs\[[8](https://arxiv.org/html/2608.23843#bib.bib5)\]\. Raw KV uses the same paged KV cache implementation as PuzzleKV but without compression, allowing us to measure the overhead introduced specifically by PuzzleKV\. We also include Hugging Face StaticCache\[[19](https://arxiv.org/html/2608.23843#bib.bib27)\]to quantify the overhead of our paged KV cache implementation\. All latency measurements use a batch size of one, with the PyTorch SDPA FlashAttention backend explicitly enabled for dense attention\.

#### Runtime Latency\.

All methods use the same warm\-up schedule\. Figure[5](https://arxiv.org/html/2608.23843#S4.F5)compares the time to first token\(TTFT\) of PuzzleKV with Static KV and Raw KV\. At 32K, PuzzleKV introduces a 20\.9% TTFT overhead relative to Raw KV\. As shown in Table[4](https://arxiv.org/html/2608.23843#S4.T4), its time per output token\(TPOT\) is only 0\.075 ms/token \(0\.18%\) higher than Raw KV\. The runtime cost of PuzzleKV is therefore concentrated in page decomposition during prefill, with negligible additional overhead during decoding\.

Figure 5:TTFT of Static KV, Raw KV, and PuzzleKV across different context lengths\.Table 4:TPOT at 16K context length with 256 generated tokens\.
#### Memory Footprint\.

Table[5](https://arxiv.org/html/2608.23843#S4.T5)reports the logical live KV cache footprint at a 16K context length with 256 generated tokens\. At steady state, PuzzleKV uses 58\.76% of the Raw KV footprint, only 0\.17 percentage points above the theoretical page\-level ratio\. Incremental page conversion adds just 12\.45 MiB at peak\.

Table 5:Logical live KV cache footprint across execution stages\.

## 5Discussion

Beyond accuracy, organizing compression around the page aligns it with the fixed\-size cache blocks of modern serving engines and enables regular, batched GPU decomposition\. Our current implementation is a batch\-one standalone prototype; because it shares this page\-based abstraction, it has strong potential for integration into a batched paged serving engine such as vLLM\[[9](https://arxiv.org/html/2608.23843#bib.bib7)\]\.

## 6Conclusion

We presented PuzzleKV, a training\- and calibration\-free method for page\-wise low\-rank KV cache compression\. PuzzleKV combines batched page decomposition, direct attention over dense and factorized pages, and incremental conversion during decoding\. Experiments across models, context lengths, and benchmarks show that page\-wise decomposition achieves strong accuracy under constrained KV cache budgets, substantially outperforms sequence\-level low\-rank compression, and can be combined with low\-bit quantization to reach more aggressive storage budgets\. More broadly, PuzzleKV shows that compression granularity can jointly shape representation quality, cache management, and GPU execution\.

## References

- \[1\]Y\. Bai, X\. Lv, J\. Zhang, H\. Lyu, J\. Tang, Z\. Huang, Z\. Du, X\. Liu, A\. Zeng, L\. Hou, Y\. Dong, J\. Tang, and J\. Li\(2024\)LongBench: a bilingual, multitask benchmark for long context understanding\.InProceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 3119–3137\.External Links:[Document](https://dx.doi.org/10.18653/v1/2024.acl-long.172),[Link](https://aclanthology.org/2024.acl-long.172/)Cited by:[§4\.1](https://arxiv.org/html/2608.23843#S4.SS1.SSS0.Px1.p1.1)\.
- \[2\]C\. Chang, W\. Lin, C\. Lin, C\. Chen, Y\. Hu, P\. Wang, N\. Huang, L\. Ceze, M\. S\. Abdelfattah, and K\. Wu\(2025\)Palu: KV\-cache compression with low\-rank projection\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2025/hash/7da6e0e00702c60607a6ae05c802ef85-Abstract-Conference.html)Cited by:[§1](https://arxiv.org/html/2608.23843#S1.p3.1),[§2](https://arxiv.org/html/2608.23843#S2.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2608.23843#S4.SS1.SSS0.Px2.p1.1)\.
- \[3\]C\. Chang, W\. Lin, C\. Lin, H\. Chiang, Y\. Akhauri, X\. Dai, H\. Jiang, Y\. Li, L\. Ceze, K\. Wu, and M\. S\. Abdelfattah\(2026\)xKV: cross\-layer KV\-cache compression via aligned singular vector extraction\.InProceedings of the 43rd International Conference on Machine Learning,External Links:2503\.18893,[Link](https://arxiv.org/abs/2503.18893)Cited by:[§1](https://arxiv.org/html/2608.23843#S1.p3.1),[§2](https://arxiv.org/html/2608.23843#S2.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2608.23843#S4.SS1.SSS0.Px2.p1.1)\.
- \[4\]T\. Dao, D\. Fu, S\. Ermon, A\. Rudra, and C\. Ré\(2022\)Flashattention: fast and memory\-efficient exact attention with io\-awareness\.Advances in neural information processing systems35,pp\. 16344–16359\.Cited by:[§3\.3](https://arxiv.org/html/2608.23843#S3.SS3.SSS0.Px2.p1.4)\.
- \[5\]L\. Gao, J\. Tow, B\. Abbasi, S\. Biderman, S\. Black, A\. DiPofi, C\. Foster, L\. Golding, J\. Hsu, A\. L\. Noac’h, H\. Li, K\. McDonell, N\. Muennighoff, C\. Ociepa, J\. Phang, L\. Reynolds, H\. Schoelkopf, A\. Skowron, L\. Sutawika, E\. Tang, A\. Thite, B\. Wang, K\. Wang, and A\. Zou\(2024\)The language model evaluation harness\.Zenodo\.External Links:[Document](https://dx.doi.org/10.5281/zenodo.12608602)Cited by:[§4\.1](https://arxiv.org/html/2608.23843#S4.SS1.SSS0.Px3.p1.1)\.
- \[6\]A\. Grattafiori, A\. Dubey, A\. Jauhri, A\. Pandey, A\. Kadian, A\. Al\-Dahle, A\. Letman, A\. Mathur, A\. Schelten, A\. Vaughan,et al\.\(2024\)The llama 3 herd of models\.arXiv preprint arXiv:2407\.21783\.Cited by:[§4\.1](https://arxiv.org/html/2608.23843#S4.SS1.SSS0.Px1.p1.1)\.
- \[7\]I\. Han, P\. Kacham, A\. Karbasi, V\. Mirrokni, and A\. Zandieh\(2025\)PolarQuant: quantizing KV caches with polar transformation\.External Links:2502\.02617,[Link](https://arxiv.org/abs/2502.02617)Cited by:[§2](https://arxiv.org/html/2608.23843#S2.SS0.SSS0.Px2.p1.1)\.
- \[8\]C\. Hsieh, S\. Sun, S\. Kriman, S\. Acharya, D\. Rekesh, F\. Jia, Y\. Zhang, and B\. Ginsburg\(2024\)RULER: what’s the real context size of your long\-context language models?\.InFirst Conference on Language Modeling,External Links:[Link](https://openreview.net/forum?id=kIoBbc76Sy)Cited by:[§4\.1](https://arxiv.org/html/2608.23843#S4.SS1.SSS0.Px1.p1.1),[§4\.2](https://arxiv.org/html/2608.23843#S4.SS2.SSS0.Px3.p2.1),[§4\.5](https://arxiv.org/html/2608.23843#S4.SS5.p1.1)\.
- \[9\]W\. Kwon, Z\. Li, S\. Zhuang, Y\. Sheng, L\. Zheng, C\. H\. Yu, J\. E\. Gonzalez, H\. Zhang, and I\. Stoica\(2023\)Efficient memory management for large language model serving with PagedAttention\.InProceedings of the 29th Symposium on Operating Systems Principles,pp\. 611–626\.External Links:[Document](https://dx.doi.org/10.1145/3600006.3613165)Cited by:[§1](https://arxiv.org/html/2608.23843#S1.p2.1),[§1](https://arxiv.org/html/2608.23843#S1.p4.1),[§5](https://arxiv.org/html/2608.23843#S5.p1.1)\.
- \[10\]H\. Li, Y\. Li, A\. Tian, T\. Tang, Z\. Xu, X\. Chen, N\. Hu, W\. Dong, Q\. Li, and L\. Chen\(2025\)A survey on large language model acceleration based on KV cache management\.Transactions on Machine Learning Research\.External Links:[Link](https://openreview.net/forum?id=z3JZzu9EA3)Cited by:[§2](https://arxiv.org/html/2608.23843#S2.p1.1)\.
- \[11\]Y\. Li, Y\. Huang, B\. Yang, B\. Venkitesh, A\. Locatelli, H\. Ye, T\. Cai, P\. Lewis, and D\. Chen\(2024\)SnapKV: LLM knows what you are looking for before generation\.InAdvances in Neural Information Processing Systems,Vol\.37,pp\. 22947–22970\.External Links:[Document](https://dx.doi.org/10.52202/079017-0722),[Link](https://proceedings.neurips.cc/paper_files/paper/2024/hash/28ab418242603e0f7323e54185d19bde-Abstract-Conference.html)Cited by:[§2](https://arxiv.org/html/2608.23843#S2.SS0.SSS0.Px3.p1.1)\.
- \[12\]Z\. Liu, J\. Yuan, H\. Jin, S\. Zhong, Z\. Xu, V\. Braverman, B\. Chen, and X\. Hu\(2024\)KIVI: a tuning\-free asymmetric 2bit quantization for KV cache\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 32332–32344\.Cited by:[§1](https://arxiv.org/html/2608.23843#S1.p3.1),[§2](https://arxiv.org/html/2608.23843#S2.SS0.SSS0.Px2.p1.1),[§4\.3](https://arxiv.org/html/2608.23843#S4.SS3.p1.1)\.
- \[13\]U\. Saxena, G\. Saha, S\. Choudhary, and K\. Roy\(2024\)Eigen attention: attention in low\-rank space for KV cache compression\.InFindings of the Association for Computational Linguistics: EMNLP 2024,pp\. 15332–15344\.External Links:[Document](https://dx.doi.org/10.18653/v1/2024.findings-emnlp.899),[Link](https://aclanthology.org/2024.findings-emnlp.899/)Cited by:[§2](https://arxiv.org/html/2608.23843#S2.SS0.SSS0.Px1.p1.1)\.
- \[14\]Z\. Shao, Y\. Wang, Q\. Wang, T\. Jiang, Z\. Du, H\. Ye, D\. Zhuo, Y\. Chen, and H\. Li\(2026\)FlashSVD: memory\-efficient inference with streaming for low\-rank models\.Proceedings of the AAAI Conference on Artificial Intelligence40\(30\),pp\. 25278–25285\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v40i30.39720)Cited by:[§3\.3](https://arxiv.org/html/2608.23843#S3.SS3.SSS0.Px2.p1.3)\.
- \[15\]J\. Su, M\. Ahmed, Y\. Lu, S\. Pan, W\. Bo, and Y\. Liu\(2024\)Roformer: enhanced transformer with rotary position embedding\.Neurocomputing568,pp\. 127063\.Cited by:[§4\.2](https://arxiv.org/html/2608.23843#S4.SS2.p1.1)\.
- \[16\]B\. Tom, M\. Benjamin, R\. Nick, S\. Melanie, D\. Prafulla, N\. Arvind, S\. Pranav, S\. Girish, A\. Amanda, A\. Sandhini,et al\.\(2020\)Language models are few\-shot learners\.Advances in neural information processing systems33\(1\),pp\. 1877–1901\.Cited by:[§1](https://arxiv.org/html/2608.23843#S1.p1.1)\.
- \[17\]A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, Ł\. Kaiser, and I\. Polosukhin\(2017\)Attention is all you need\.Advances in Neural Information Processing Systems30\.Cited by:[§1](https://arxiv.org/html/2608.23843#S1.p2.1)\.
- \[18\]J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, F\. Xia, E\. Chi, Q\. V\. Le, D\. Zhou,et al\.\(2022\)Chain\-of\-thought prompting elicits reasoning in large language models\.Advances in neural information processing systems35,pp\. 24824–24837\.Cited by:[§1](https://arxiv.org/html/2608.23843#S1.p1.1)\.
- \[19\]T\. Wolf, L\. Debut, V\. Sanh, J\. Chaumond, C\. Delangue, A\. Moi, P\. Cistac, T\. Rault, R\. Louf, M\. Funtowicz,et al\.\(2020\)Transformers: state\-of\-the\-art natural language processing\.InProceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations,pp\. 38–45\.External Links:[Document](https://dx.doi.org/10.18653/v1/2020.emnlp-demos.6)Cited by:[§4\.1](https://arxiv.org/html/2608.23843#S4.SS1.SSS0.Px3.p1.1),[§4\.5](https://arxiv.org/html/2608.23843#S4.SS5.p1.1)\.
- \[20\]G\. Xiao, J\. Lin, M\. Seznec, H\. Wu, J\. Demouth, and S\. Han\(2023\)SmoothQuant: accurate and efficient post\-training quantization for large language models\.InProceedings of the 40th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.202,pp\. 38087–38099\.Cited by:[§4\.3](https://arxiv.org/html/2608.23843#S4.SS3.p1.1)\.
- \[21\]G\. Xiao, Y\. Tian, B\. Chen, S\. Han, and M\. Lewis\(2024\)Efficient streaming language models with attention sinks\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=NG7sS51zVF)Cited by:[§2](https://arxiv.org/html/2608.23843#S2.SS0.SSS0.Px3.p1.1),[§3\.3](https://arxiv.org/html/2608.23843#S3.SS3.SSS0.Px1.p1.2)\.
- \[22\]A\. Yang, A\. Li, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Gao, C\. Huang, C\. Lv,et al\.\(2025\)Qwen3 technical report\.arXiv preprint arXiv:2505\.09388\.Cited by:[§1](https://arxiv.org/html/2608.23843#S1.p2.1),[§4\.1](https://arxiv.org/html/2608.23843#S4.SS1.SSS0.Px1.p1.1)\.
- \[23\]S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. Narasimhan, and Y\. Cao\(2023\)ReAct: synergizing reasoning and acting in language models\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=WE_vluYUL-X)Cited by:[§1](https://arxiv.org/html/2608.23843#S1.p1.1)\.
- \[24\]H\. Yu, Z\. Yang, S\. Li, Y\. Li, and J\. Wu\(2024\)Effectively compress kv heads for llm\.External Links:2406\.07056,[Link](https://arxiv.org/abs/2406.07056)Cited by:[§2](https://arxiv.org/html/2608.23843#S2.SS0.SSS0.Px1.p1.1)\.
- \[25\]A\. Zandieh, M\. Daliri, M\. Hadian, and V\. Mirrokni\(2026\)TurboQuant: online vector quantization with near\-optimal distortion rate\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=tO3ASKZlok)Cited by:[§2](https://arxiv.org/html/2608.23843#S2.SS0.SSS0.Px2.p1.1)\.
- \[26\]R\. Zhang, K\. Wang, L\. Liu, S\. Wang, H\. Cheng, C\. Zhang, and Y\. Shen\(2024\)LoRC: low\-rank compression for llms kv cache with a progressive compression strategy\.External Links:2410\.03111,[Link](https://arxiv.org/abs/2410.03111)Cited by:[§1](https://arxiv.org/html/2608.23843#S1.p3.1),[§2](https://arxiv.org/html/2608.23843#S2.SS0.SSS0.Px1.p1.1)\.
- \[27\]Z\. Zhang, Y\. Sheng, T\. Zhou, T\. Chen, L\. Zheng, R\. Cai, Z\. Song, Y\. Tian, C\. Ré, C\. Barrett, Z\. Wang, and B\. Chen\(2023\)H2​OH\_\{2\}O: heavy\-hitter oracle for efficient generative inference of large language models\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 34661–34710\.External Links:[Document](https://dx.doi.org/10.52202/075280-1506)Cited by:[§1](https://arxiv.org/html/2608.23843#S1.p3.1),[§2](https://arxiv.org/html/2608.23843#S2.SS0.SSS0.Px3.p1.1),[§4\.1](https://arxiv.org/html/2608.23843#S4.SS1.SSS0.Px2.p1.1)\.
- \[28\]Y\. Zhu, D\. H\. Yang, M\. M\. Amiri, K\. Murugesan, T\. Pedapati, and P\. Chen\(2026\)OjaKV: context\-aware online low\-rank KV cache compression\.InFindings of the Association for Computational Linguistics: ACL 2026,pp\. 10161–10178\.External Links:[Document](https://dx.doi.org/10.18653/v1/2026.findings-acl.494)Cited by:[§1](https://arxiv.org/html/2608.23843#S1.p3.1),[§2](https://arxiv.org/html/2608.23843#S2.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2608.23843#S4.SS1.SSS0.Px2.p1.1)\.

Appendix

## Appendix AExperimental Setup

### A\.1Additional Evaluation Details

All benchmark evaluations use a fixed random seed of 42\. RULER uses the lm\-eval 0\.4\.12 implementation and contains 13 tasks with 500 examples per task\. LongBench uses thetestsplit ofTHUDM/LongBench; Appendix[B\.2](https://arxiv.org/html/2608.23843#A2.SS2)additionally reports the five Chinese tasks omitted from the main table\. Qwen3 is evaluated without a chat template and with thinking disabled\. For LongBench, Llama\-3\.1\-8B\-Instruct uses raw prompts for six tasks and its default chat template for the other 15 tasks\.

### A\.2Computing Environment

Table 6:Computing environment for accuracy experiments\. The system\-efficiency study uses the same configuration except for CUDA 13\.0 and PyTorch 2\.12\.0\+cu130, because the accuracy environment exhibits an SVD performance issue\.

### A\.3Baseline Configurations

#### Global SVD\.

Global SVD uses the same dense sink and local\-page policy as PuzzleKV\. Its input\-dependent rank is selected by accounting for both its low\-rank factors and these dense regions when matching the target storage budget\.

#### Palu\.

Palu uses theSalesforce/wikitextwikitext\-2\-raw\-v1training split for calibration\. Fisher estimation uses 32 sequences of 1,024 tokens, and whitening uses 256 sequences of 1,024 tokens, both with seed 42\. Due to rank alignment, the realized retained parameter ratio rounds to 0\.60 for both models\.

#### H2O\.

The H2O budget is computed from each tokenized prompt length\. Selection is performed independently per layer and KV head using accumulated post\-softmax attention mass\. For GQA models, attention mass from query heads mapped to the same KV head is summed before selection\. Prefill uses full attention, after which H2O evicts entries from the completed prompt cache before autoregressive decoding\.

#### OjaKV\.

We select OjaKV\-PF, the best\-performing reported variant, because its full\-attention prefill followed by compressed decoding matches PuzzleKV’s high\-level execution pattern; standard OjaKV instead applies compression during prefill\. We evaluate OjaKV\-PF at the same nominal retained KV cache ratio of 0\.60\. We use rankr=77r=77for both keys and values, initialize the basis by SVD on the same WikiText\-2 training split with calibration seed 2, and update the basis online during evaluation\. Our implementation samples at most 256 pooled rows for each online update\.

## Appendix BAdditional Evaluation Results

### B\.1Complete Quantization Compatibility Results

Table[7](https://arxiv.org/html/2608.23843#A2.T7)reports all 13 RULER tasks at 16K; PuzzleKV usesP=32P=32and\(rK,rV\)=\(16,14\)\(r\_\{K\},r\_\{V\}\)=\(16,14\)\.

Table 7:Complete quantization\-compatibility results \(%\) on RULER at 16K\. Storage is reported as a percentage of Full KV storage\.

### B\.2Complete LongBench Results

Table[8](https://arxiv.org/html/2608.23843#A2.T8)gives per\-task scores for the 14 English tasks and two code tasks used in the main paper\. Table[9](https://arxiv.org/html/2608.23843#A2.T9)adds the five Chinese tasks\.

Table 8:Complete per\-task LongBench results on the English\-language and code tasks summarized in the main paper\. All compressed methods use the same KV cache storage ratioρ=0\.60\\rho=0\.60\.
Table 9:Additional LongBench results for the five Chinese tasks\. Avg\.\-16 covers the 14 English\-language and two code tasks; Avg\.\-21 covers the complete benchmark\. All compressed methods useρ=0\.60\\rho=0\.60\.

## Appendix COjaKV\-PF Reproduction Results

We evaluate the OjaKV\-PF variant at the same nominal retained KV cache ratioρ=0\.60\\rho=0\.60used by the compressed methods in the main evaluation\.

Table[10](https://arxiv.org/html/2608.23843#A3.T10)reports the 16K RULER results; zero entries are measured scores rather than missing results\.

Table 10:Complete OjaKV\-PF results \(%\) on RULER at 16K andρ=0\.60\\rho=0\.60\. Each task contains 500 examples\.
Table[11](https://arxiv.org/html/2608.23843#A3.T11)reports the complete 21\-task LongBench results\.

\(a\) English\-language and code tasks

\(b\) Chinese tasks

Table 11:Complete OjaKV\-PF results \(%\) on LongBench atρ=0\.60\\rho=0\.60\. Panel \(a\) reports the 14 English\-language and two code tasks; panel \(b\) reports the five Chinese tasks\. Avg\.\-16 and Avg\.\-21 average over the corresponding task sets\.
Overall, the reproduced OjaKV\-PF performance varies substantially across models and tasks, with particularly large degradation and several zero scores on Qwen3\-8B\.

## Appendix DDesign Ablations

### D\.1Page\-Size Selection

To isolate the effect of page size, we choose a symmetric rankrK=rVr\_\{K\}=r\_\{V\}for each page size so that the factorized\-page storage ratios are closely matched\. For a key–value page pair with head dimensiond=128d=128, the retained ratio is

ρfactor​\(P,rK,rV\)=\(rK\+rV\)​\(P\+d\)2​P​d\.\\rho\_\{\\mathrm\{factor\}\}\(P,r\_\{K\},r\_\{V\}\)=\\frac\{\(r\_\{K\}\+r\_\{V\}\)\(P\+d\)\}\{2Pd\}\.\(6\)The three configurations are therefore\(P,rK,rV\)=\(16,9,9\)\(P,r\_\{K\},r\_\{V\}\)=\(16,9,9\),\(32,16,16\)\(32,16,16\), and\(64,27,27\)\(64,27,27\)\. These ratios apply to factorized pages, and all configurations use the same dense\-page policy\. Table[12](https://arxiv.org/html/2608.23843#A4.T12)reports all 13 RULER task scores and decomposition time\.

Table 12:Page\-size selection on Llama\-3\.1\-8B\-Instruct at 16K\. For each page size, we setrK=rVr\_\{K\}=r\_\{V\}and select the shared rank to keep factorized\-page storage near 63%\. Decomposition time is the mean per sample during prefill;†\\daggermarks the main configuration\.

### D\.2Rank Selection

Table[13](https://arxiv.org/html/2608.23843#A4.T13a)reports the full rank grid while holding page size and the dense\-page policy fixed\. Configurations are grouped by total rankrK\+rVr\_\{K\}\+r\_\{V\}\.

RanksRetrievalMulti\-hopAgg\.QArKr\_\{K\}rVr\_\{V\}S1S2S3MK1MK2MK3MQMVVTCWEFWEQA\-1QA\-2Avg\.121274\.8068\.4015\.6072\.6083\.8046\.8071\.3054\.0571\.4067\.3289\.0067\.4353\.2064\.28121480\.6072\.2028\.6079\.4086\.0063\.8077\.5060\.7576\.8469\.8889\.2769\.0353\.2069\.77141291\.6086\.2037\.6090\.2097\.2075\.6091\.2577\.6591\.7680\.2489\.6069\.1352\.8079\.29121683\.8076\.6040\.6080\.0088\.0070\.8081\.0065\.0582\.2071\.1889\.1369\.5353\.4073\.18141494\.4089\.6061\.4092\.8099\.0085\.4093\.8582\.3595\.6482\.0889\.0770\.8053\.4083\.83161298\.8095\.6060\.0097\.80100\.0086\.8098\.4589\.6097\.8083\.2088\.5370\.4353\.2086\.17121885\.6078\.0049\.6083\.6089\.2074\.2083\.2568\.2083\.5270\.8289\.2069\.4353\.4075\.23141696\.2091\.4073\.8095\.2098\.6089\.2094\.8585\.1596\.7682\.6689\.2071\.0753\.2085\.951614†98\.8095\.8082\.0098\.20100\.0093\.4098\.8591\.1098\.8084\.8488\.4070\.8353\.6088\.82181299\.8098\.6075\.6099\.60100\.0091\.0099\.8094\.9599\.0483\.9288\.2770\.6053\.6088\.83122087\.2080\.8058\.0084\.6088\.4075\.4083\.7070\.3585\.1672\.6489\.3369\.2753\.6076\.80141897\.0092\.8082\.2096\.4098\.8091\.8096\.0086\.5596\.4883\.2088\.9371\.0754\.0087\.33161699\.4097\.2091\.2099\.00100\.0096\.4099\.6092\.1599\.1685\.8688\.4771\.1054\.0090\.271814100\.0099\.2090\.4099\.60100\.0096\.0099\.5095\.6599\.3285\.3688\.3371\.2754\.2090\.682012100\.00100\.0078\.8099\.60100\.0092\.8099\.7096\.1099\.4884\.2488\.6071\.1054\.0089\.57142098\.0093\.0085\.0096\.6098\.8093\.2096\.4587\.3597\.0884\.2889\.2071\.3054\.0088\.02161899\.6098\.0095\.0099\.20100\.0097\.6099\.5593\.1599\.2886\.4488\.3371\.5053\.8090\.881816100\.0099\.6096\.2099\.60100\.0098\.2099\.7094\.8099\.4086\.7888\.2771\.6754\.4091\.432014100\.00100\.0093\.6099\.60100\.0097\.2099\.8097\.4099\.6886\.3488\.3371\.1054\.2091\.33162099\.8098\.6096\.0099\.60100\.0096\.8099\.8593\.3599\.5286\.7488\.5372\.2353\.8091\.141818100\.0099\.8098\.0099\.60100\.0098\.4099\.8596\.3599\.5687\.1888\.3372\.1754\.0091\.792016100\.00100\.0097\.0099\.60100\.0098\.4099\.8097\.7099\.6886\.4688\.4771\.6354\.4091\.781820100\.0099\.8099\.4099\.60100\.0098\.4099\.7095\.9099\.5287\.7088\.5372\.3054\.6091\.962018100\.00100\.0099\.2099\.60100\.0098\.4099\.6597\.6099\.6886\.5889\.0071\.7054\.0091\.952020100\.00100\.0099\.8099\.60100\.0098\.6099\.5097\.5599\.7287\.5288\.6071\.9754\.6092\.11Table 13:Complete RULER rank\-selection results \(%\) for Llama\-3\.1\-8B\-Instruct at 16K\. Every configuration usesP=32P=32and the same dense\-page policy\. Dashed rules group equal total ranksrK\+rVr\_\{K\}\+r\_\{V\};†\\daggermarks the main configuration\.
### D\.3RoPE Key Analysis

Table[14](https://arxiv.org/html/2608.23843#A4.T14)compares pre\- and post\-RoPE keys at 16K,P=32P=32, and\(rK,rV\)=\(16,16\)\(r\_\{K\},r\_\{V\}\)=\(16,16\)\. Pre\-RoPE raises the average score from 90\.40 to 90\.88\.

Table 14:Pre\- versus post\-RoPE key factorization on Llama\-3\.1\-8B\-Instruct at 16K\. Scores are percentages over the 13 RULER tasks; QA\-1 and QA\-2 denote SQuAD and HotpotQA\.