acceptodds
Under review as a conference paper at ICLR 2027

FAD-KV: Adaptive Dictionary KV Caching for Efficient Reasoning Decoding

Abstract

Key-value (KV) caching is a core mechanism in large language models, where intermediate key and value representations are stored to accelerate autoregressive decoding. As generation length increases, KV cache memory and computation grow linearly, making compression critical for efficient long-output reasoning. Dictionary-based sparse KV compression is appealing because it represents each token’s KV states as a sparse combination of learned basis elements, or atoms, in a dictionary, preserving token-level structure without enforcing a global low-rank constraint. However, existing dictionary-based methods face two practical limitations during decoding: iterative sparse coding methods such as Orthogonal Matching Pursuit add decoding-time overhead, and static dictionaries may mismatch evolving KV distributions under test-time generation. While adaptive dictionary updates can reduce this mismatch, naive append-only strategies lead to dictionary growth during generation. We propose FAD-KV, a Fast Adaptive Dictionary KV caching framework for efficient reasoning decoding. FAD-KV integrates two components: a screening-based sparse coding scheme, where a one-shot Top-n selection identifies a small candidate pool followed by lightweight coefficient refinement, and a fixed-size dictionary adaptation mechanism that reuses inactive atoms instead of expanding the dictionary. By controlling both sparse coding cost and adaptive dictionary growth, FAD-KV provides a memory-bounded and computation-efficient KV compression framework for long reasoning workloads. Experiments on reasoning and long-context benchmarks show that FAD-KV achieves a strong quality-efficiency trade-off while avoiding unbounded dictionary growth during decoding.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV Cache Compression, Efficient LLM Inference, Dictionary Learning, Sparse Coding, Long-Context Reasoning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_9gQbOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

FAD-KV addresses sparse-coding latency and dictionary growth in dictionary-based KV compression. It screens atoms by cosine similarity to form a candidate pool. Encoding then uses greedy marginal coding (GM) or a one-shot pool-ridge variant (PL). When reconstruction error is high, fixed-size adaptation replaces an atom that is not referenced by the current cache and re-encodes the incoming vector. This keeps the dictionary bounded without invalidating previously cached representations. Experiments evaluate task quality, decoding efficiency, and memory across several models and benchmarks.

Critical strengths
  1. A practical fixed-memory adaptation rule.

Replacing only currently unreferenced atoms preserves the validity of stored sparse codes and avoids global re-encoding or dictionary growth. This is a useful systems constraint for adaptive dictionary compression.

  1. A reasonably broad and readable evaluation.

The paper reports accuracy, throughput, and memory, along with reconstruction-error and sensitivity analyses. The GM and PL variants expose useful trade-offs rather than presenting only one configuration.

Critical weaknesses
  1. The efficiency contribution of screening and solver changes is not fully isolated.

On the 8B model in Table 4, throughput is 13.22 tok/s for Lexico-ADP, 14.38 for GM, and 17.80 for PL. PL therefore improves over GM by approximately 23.8%, while GM improves over Lexico-ADP by about 8.8%. PL deserves more attention given its speed benefit. GM and PL both use a screened pool. Table 4 does not fully separate screening, support selection, solver, and adaptation. The results therefore do not establish that screening itself is unimportant.

  1. Sustained fixed-size adaptation during longer generation needs direct evidence.

Section 3.2 skips an update when no atom is unreferenced by the current cache. Adaptation could therefore stall, but the experiments do not show whether this occurs in the evaluated runs or whether it explains task-quality losses. Figure 3 reports dictionary size and mean reconstruction error without an inactive-pool or skipped-update trace. In the Qwen3-4B GSM8K setting, FAD-KV (PL) has lower mean reconstruction error yet lower accuracy than PL (61.6% versus 64.4%). This is not a contradiction—mean reconstruction error need not determine task accuracy—but it motivates a more targeted analysis of error location and adaptation behavior.

Overall assessment: I lean toward weak rejection. The practical idea is useful. However, the evidence does not fully isolate efficiency contributions or establish sustained adaptation and task quality during longer generation.

Questions for authors
  1. Please isolate screening and solver contributions using comparable full-dictionary and screened-pool implementations. Report encoding/decoding time, quality, and memory trade-offs.

  2. During longer generation, how do the number of inactive atoms, triggered/skipped updates, and reconstruction or attention-output errors evolve? Is atom exhaustion observed, and does it coincide with any task failures?

  3. What explains the 61.6% versus 64.4% GSM8K gap despite lower mean reconstruction error? A paired failure analysis would help. An append-only switch after exhaustion could serve as a diagnostic. This would relax the fixed-memory constraint and should be labeled accordingly.

3 comments
AuthorsOpenReview ↗

Part 1/2: Separating Screening and Solver Effects

We thank the reviewer for the constructive suggestions. They led us to test screening and solver choices separately, measure atom exhaustion, and improve the allocation strategy. We also fixed a decoding bug: atoms newly referenced during generation could previously be replaced because the unused-atom set was not updated. After fixing it, initial Llama-3.2-3B GSM8K accuracy rose from 24.0% to 28.1% (PL) and 26.0% to 28.5% (GM). We will include the corrections and new analyses in the revised paper.

W1 / Q1. Separate the contributions of screening and the solver.

We evaluated full-dictionary versus screened-pool search, each with greedy or ridge coding. The measured times below are on Llama-3.2-3B (A100, 1K context, batch 1):

EncoderEncoding (ms/token)Total (ms/token)
OMP, full dictionary (Lexico-ADP)16.555.0
GM, screened pool (256 atoms)11.350.4
Greedy, full dictionary116.1163.1
PL, screened ridge (Cholesky)8.148.7
Ridge, full dictionary (exact dual)16.660.9

Screening makes greedy coding practical (11.3 versus 116.1 ms encoding). For PL, replacing sequential selection with one batched solve provides much of the benefit and screening further reduces its cost. On Llama-3.1-8B, removing screening makes GM about 7× slower (80 → 572 ms/token) and PL total latency increases from 56 to 87 ms/token. At the same storage budget and s=8s=8, screened GM without allocation scores 27.2 vs. 31.2 for Lexico on GSM8K, 15.4 vs. 14.8 on MATH-500, and 32.0 vs. 33.7 on RULER-8K. Thus, screening and the cheaper solver improve speed but can also affect accuracy.

W2 / Q2. Does adaptation remain active during long generation?

Not always. We tracked the number of free atoms and triggered, successful, and skipped updates at each decoding step. On Qwen3-4B MATH-500, runs reaching the 1,024-token limit skip 24% (GM) to 46% (PL) of triggered updates and shorter generations skip almost none. After 4K-token prefill, U0U_0 is almost empty and over 96% of triggered updates are skipped from the start of decoding. The fraction of dictionaries with no free atom rises from 36% at 1K to 100% at 16K prefill. We will report this limitation. Exhaustion alone, however, does not explain the remaining accuracy gap (Q3).

AuthorsOpenReview ↗

Part 2/2: Why Lower Reconstruction Error May Not Improve Accuracy

Q3. Why can FAD-KV (PL) trail PL despite lower reconstruction error?

We tested the suggested diagnostic on Llama-3.2-3B GSM8K: use fixed-size replacement until U0U_0 is empty, then allow append within the same cap. This did not reliably improve accuracy (GM: 26.0 versus 25.6; PL: 27.2 versus 30.8, both within run-to-run variation). Reserving 512 atoms for replacement avoids exhaustion but reduces accuracy to 24.0%. Thus, simply allowing more updates does not resolve the gap.

Average reconstruction error is not enough: an error on a highly attended key can affect the attention output more than a larger error elsewhere. We therefore introduced attention-weighted allocation: different keys receive different numbers of nonzeros according to attention-weighted error reduction, but the average remains ss, so memory is unchanged (Proposition 1). At s=8s=8, GM improves from 27.2% to 36.4% on GSM8K (+9.2 points), 15.4% to 22.6% on MATH-500 (+7.2), and 32.0% to 68.0% on RULER-8K (+36.0). PL improves from 33.2% to 69.6% on RULER-8K (+36.4). For reference, Lexico scores 31.2 / 14.8 / 33.7 on these tasks under the same storage budget. This suggests that where reconstruction error occurs matters more than its average alone.

Thank the authors for the detailed and honest response. The new comparisons address my concern in W1/Q1, and the explanation of reconstruction error versus accuracy resolves Q3. I also appreciate the acknowledgment of the long-context limitations in W2/Q2.

However, the bug affected the core adaptation mechanism and may impact much of the reported evidence. The long-context limitations remain, and the new attention-weighted allocation strategy needs further evaluation. I encourage the authors to refine the method and update the experiments and analyses. I therefore maintain my original score.

Reviewer_EnoKOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies the encoding overhead and adaptive dictionary growth of dictionary-based KV-cache compression during decoding. FAD-KV first forms a Top-nn candidate pool through one-shot correlation screening, then applies greedy-marginal (GM) or pool-ridge (PL) coding. During adaptation it replaces only atoms unused by the current cache, keeping dictionary size fixed. Experiments cover three models on reasoning, RULER, and LongBench tasks. Relative to Lexico-ADP, FAD-KV (PL) improves single-sequence throughput by approximately 12.5% and 46.1% on the 3B and 8B models; Full KV retains lower single-sequence latency. The paper also reports concurrent-throughput gains over Full KV under a fixed memory budget.

Critical strengths
  1. S1. A well-defined problem with targeted diagnostics. The paper focuses on per-token full-dictionary OMP overhead and append-only dictionary growth. The candidate-recall and inactive-atom analyses in Figure 1 directly motivate the two designs.
  2. S2. Clear component separation and layered comparisons. Screening and in-pool coding target computation, while fixed-size replacement targets dictionary growth. Reporting GM/PL under both append and fixed-size policies allows the effects of the coding path and adaptation policy to be assessed separately.
  3. S3. A clear condition for preserving existing cache reconstructions. When usage counts cover all caches sharing a dictionary, replacing only zero-usage atoms preserves the reconstructions associated with existing sparse codes without re-encoding historical KV.
Critical weaknesses
  1. The paper provides no uncompressed accuracy reference, and the quality–memory trade-off of fixed-size replacement is not established. Tables 1–3 omit Full KV task results under the same protocol, so the quality cost of compression cannot be located. The corresponding append variant is the direct reference for fixed-size replacement: FAD-KV (PL) versus append PL scores 12.8 versus 19.4 on Llama-3.2-3B / MATH500, 17.0 versus 38.0 on LongReason, and 36.06 versus 51.15 on Qwen3-4B / HotpotQA. The cost varies by configuration; fixed-size and append GM both score 42.8 on 8B / MATH500. Append variants may use more dictionary memory, and lower quality for a fixed-size method is not by itself a defect. The missing element is the memory saving that accompanies the quality loss. Figure 3(a) shows approximately 7%–12% append-dictionary growth over about 1,000 steps on Qwen3-4B / GSM8K, which supports the growth trend but does not quantify the dictionary bytes or fraction of total GPU memory saved by fixed-size replacement. The paper must add the Full KV task reference and jointly report quality, dictionary memory, total memory, and throughput for representative GM/PL settings so that competitive operating points can be identified.

W2. Concurrent-run configurations, memory accounting, and adaptive-dictionary behavior are not fully reported. The batch-1 measurements in Table 4 and Appendix C.4 assess single-sequence cost only; Section 5.5 provides the direct evidence of concurrent-throughput gains at the largest batch fitting a 24 GB budget. The paper must report the actual batch sizes, total peak GPU memory, and major memory components for FAD-KV and Full KV at 4K and 16K, including weights, KV caches, dictionaries, and temporary workspaces, and must define the reported 9.3 GB and 21.7 GB values. Appendix C.4 lists devices with 96 GB of memory, and the paper does not explain how the 24 GB budget is enforced and measured. The KV computation path and whether adaptive dictionaries are shared across sequences or maintained separately are also unspecified; the former determines the size of temporary workspaces, and the latter determines the scope of usage counts and the memory accounting for dictionary copies.

Questions for authors

NA

3 comments
AuthorsOpenReview ↗

Part 1/3: Method Changes and Accuracy-Memory Trade-off

We thank the reviewer for the questions about accuracy, memory, and throughput. We fixed an implementation bug and developed attention-weighted allocation; we will incorporate the results and corrections below into the revised paper.

Method updates. The set of unreferenced dictionary atoms U0U_0 was not updated during decoding, allowing newly referenced atoms to be replaced. Fixing this improved initial Llama-3.2-3B GSM8K results from 24.0% to 28.1% (PL) and 26.0% to 28.5% (GM). We also allow different keys to use different numbers of coefficients according to attention-weighted reconstruction error reduction, while keeping the total number of stored coefficients, and thus memory, unchanged. We refer to FAD-KV below as the bug-fixed method with this allocation; and w/o allocation to refer to the bug-fixed submitted method.

Table R1. Llama-3.2-3B, s=8s=8, N=4096N=4096, under the same storage budget. Parentheses give differences from Lexico.

MethodGSM8KMATH-500RULER-8K
Full KV72.444.496.1
Lexico31.214.833.7
FAD-KV (PL), w/o allocation34.0 (+2.8)18.0 (+3.2)33.2 (−0.5)
FAD-KV (PL)36.0 (+4.8)20.2 (+5.4)69.6 (+36.0)
FAD-KV (GM), w/o allocation27.2 (−4.0)15.4 (+0.6)32.0 (−1.7)
FAD-KV (GM)36.4 (+5.2)22.6 (+7.8)68.0 (+34.3)

Allocation improves RULER-8K by roughly 36 points at the same memory, and the improved method beats Lexico in all six comparisons.

W1. Full KV reference, quality-memory trade-off, and append-only baseline.

The original accuracy gap to Full KV has two main contributors: s=8s=8 is a very small sparsity budget, and only 18–33 recent tokens remain uncompressed. Increasing ss to 24 brings GM within 4.6 points of Full KV across all three tasks (Table R2). Increasing the full-precision window to 128 tokens (about 14 MiB extra per sequence) raises GSM8K 26.6% → 58.0% for Lexico and 30.8% → 65.2% for FAD-KV (PL) without allocation.

We agree that fixed-size replacement saves little memory over our capped append baseline: append uses at most 1,024 extra atoms per layer and per K/V dictionary, or 14 / 16 / 18 MiB for the three models. This cap was missing from Table 5. We will state it and emphasize how our approach enables a bounded dictionary size without an append cap, rather than the small memory savings over this baseline.

After long prefill, few unused atoms remain, so append can keep growing but fixed-size replacement cannot. This explains some LongReason/HotpotQA losses and is a real limitation we will discuss in Section 6. On Qwen3-4B HotpotQA, encoder choice also matters: GM scores 50.75 versus 49.85 for Lexico. On Llama-3.2-3B MATH-500, the bug-fixed PL without allocation scores 20.0, above append's 16.0. Allocation improves accuracy even after dictionary replacement stops (Table R1).

AuthorsOpenReview ↗

Part 2/3: Joint Results and Batched Throughput

Table R2. Llama-3.2-3B with dictionaries trained separately at each ss, each using 56 MiB. KV memory is after an 8K prompt (excluding dictionary), speed-up is over Lexico at the same ss, measured at 1K context on one A100-80GB (batch 1, two runs). Lexico uses the matched sparsity storage budget.

MethodssGSM8KMATH-500RULER-8KKV at 8K (MiB)Speed-up vs Lexico (1K)
Full KV–72.444.496.1896–
Lexico831.214.833.71301.00×
FAD-KV (PL)836.020.269.61301.10×
FAD-KV (GM)836.422.668.01301.04×
Lexico1664.838.491.72441.00×
FAD-KV (PL)1659.637.093.92441.47×
FAD-KV (GM)1660.438.093.72441.14×
Lexico2469.641.895.33571.00×
FAD-KV (PL)2465.640.695.43571.70×
FAD-KV (GM)2470.439.895.93571.11×

At s=24s=24, GM uses 2.5× less KV memory than Full KV while staying within 4.6 accuracy points; PL is 1.70× faster than Lexico at 1K, as its batched solve replaces sequential OMP steps. This speed-up is relative to Lexico, not Full KV: at batch 1, dictionary methods are slower per token than Full KV. Prompt-side allocation also increases prefill time, up to 1.3× Lexico at 8K and 1.9× at 1K (s=24s=24). The benefit of smaller KV memory becomes clearer in batched decoding, where we compare against Full KV eager attention rather than Lexico.

W2. Batched configuration, throughput, and memory accounting.

We measured aggregate decoding throughput (tokens/s across the batch, excluding prefill) for Llama-3.2-3B-Instruct BF16 on one H100 NVL (80 GB). These runs use the bug-fixed method without allocation, matching Section 5.5, with s=8s=8 and N=4096N=4096. We use greedy decoding, 4 warm-up steps, and 32 timed decoding steps. For each method, we sweep batch sizes and choose the highest aggregate decoding throughput within the same memory budget. Peak memory is torch.cuda.max_memory_allocated during decoding (including model weights, not temporary prefill allocations). Each method runs in its own process, with the allocator capped at 79 GiB.

Table R3. Maximum decoding-only throughput under 24 GB and 80 GB memory budgets on one H100 NVL. Batch size is selected separately for each method and budget. Throughput is aggregate tokens/s; peak GPU allocation is in GiB. Speed-up is relative to Full KV with HuggingFace eager decoding, not Lexico or an optimized fused Full KV implementation.

ContextBudgetFull KV tok/s (batch)FAD-KV PL tok/s (batch)FAD-KV GM tok/s (batch)Speed-up vs Full KV (PL / GM)Peak GiB (Full / PL / GM)
4K24 GB308 (32)539 (128)602 (128)1.75× / 1.96×21.7 / 15.0 / 15.3
4K80 GB316 (128)539 (128)602 (128)1.70× / 1.90×68.7 / 15.0 / 15.3
16K24 GB74.6 (8)246 (64)258 (64)3.30× / 3.46×21.6 / 21.8 / 22.0
16K80 GB77.0 (16)246 (64)258 (64)3.19× / 3.35×37.2 / 21.8 / 22.0
32K24 GB37.6 (4)140 (32)144 (32)3.72× / 3.85×21.6 / 21.7 / 21.9
32K80 GB38.9 (16)143 (64)148 (64)3.68× / 3.81×68.2 / 36.5 / 36.5

The decoding memory breakdown is mainly 6.0 GiB model weights, KV cache, and small overheads. For example, at 4K, Full KV uses 14.1 GiB KV + 1.6 GiB other, while FAD-KV (PL) uses 7.3 GiB KV + 0.05 GiB dictionary + 1.6 GiB other, in addition to the same weights. The shared dictionary stays at about 0.05 GiB regardless of batch size.

Why include both budgets? We initially used 24 GB to compare throughput under a common, practical memory limit. To check whether this unfairly restricts Full KV, we also swept batch sizes with the full 80 GB available. As Table R3 shows, the best throughput rises by at most 3.5% for any method or context. FAD-KV still achieves up to 3.81× higher aggregate decoding throughput than Full KV eager at 80 GB. Larger batches eventually stop helping because each step reads more KV data. These are decoding-only results, not end-to-end prefill-plus-decode speed-ups.

AuthorsOpenReview ↗

Part 3/3: Prefill and Implementation Details

W2 (continued). Prefill, attention kernels, and shared dictionaries.

Why we use shared prompts and cache copying. Our goal in Table R3 is to measure steady-state decoding throughput at a fixed GPU-memory budget, not prefill throughput or end-to-end latency. A full prefill of a large batch creates temporary activations that can exhaust GPU memory even when the resulting KV cache and decoding workload fit. This would restrict the tested batch size for reasons unrelated to decoding. To separate these effects, we use the same synthetic prompt for every sequence, prefill a smaller chunk, and copy its resulting KV cache to the remaining sequences. Since the prompts are identical, each sequence starts decoding from the same cache it would have obtained from a full prefill All sequences are still decoded, and we time only the decoding steps. Cache copying is therefore a measurement setup, not a claimed prefill optimization.

Checks against full prefill and different prompts. Wherever full prefill fits, decoding peak memory is the same and throughput differs by at most 3.2%. We also ran full prefill with different LongBench documents per sequence (PL at 4K, batch 128; and 16K, batch 32) and throughput changes by at most 3.1%. Relative to Full KV eager decoding at the corresponding batch sizes, PL achieves 1.72× / 3.14× on different prompts versus 1.75× / 3.15× on shared prompts (4K / 16K). These checks suggest that neither prompt repetition nor cache copying explains the observed decoding gains. We do not claim these ratios for end-to-end prefill-plus-decode serving, and we will make this scope explicit in the revision.

Attention implementation and comparison scope. Full KV uses HuggingFace eager attention during decoding and FlashAttention-2 during prefill. FAD-KV operates directly on sparse codes: key scores gather selected entries of qDkqD_k; for values, attention-weighted coefficients are accumulated before one multiplication by DvD_v. Each stored nonzero uses 4 bytes for its index and coefficient. Neither decoding path uses a custom fused attention kernel: FAD-KV uses PyTorch gather/scatter operations, and Full KV uses PyTorch eager attention. The reported throughput speed-ups are relative to this eager Full KV baseline. We will state this implementation choice and its limitation explicitly.

Dictionary sharing and hardware. One K dictionary and one V dictionary per layer are shared across the batch. An atom can be replaced only if no cached code references it. iIn these large-batch runs all atoms were referenced, so the speed gains do not depend on online adaptation. The paper's 4K batch-32 peaks (9.3 GB FAD-KV PL, 21.7 GB Full KV eager) came from the original shared-node run while the new measurements were taken under consistent conditions on a single H100.

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

This paper addresses two inference-time bottlenecks in dictionary-based sparse KV cache compression (building primarily upon Lexico) during long-output reasoning: the per-token decoding latency of full-dictionary Orthogonal Matching Pursuit (OMP) and the unbounded dictionary growth caused by append-only online adaptation under test-time distribution shift.

To mitigate these issues, the authors propose FAD-KV, which introduces two main inference-time mechanisms:

  1. Candidate-Screened Sparse Coding: A one-shot inner-product screening step prunes the full NN-atom dictionary to a smaller candidate pool C\mathcal{C} of size n≪Nn \ll N (with a fallback threshold τc\tau_c to full OMP). Within this pool, the sparse code is computed via either sequential Greedy Marginal (GM) selection or a one-shot Pool-Ridge (PL) regression solver.
  2. Fixed-Size Adaptive Dictionary Replacement: When the relative reconstruction error exceeds a threshold δ\delta, instead of appending a new atom, FAD-KV replaces an inactive atom (one with zero reference count uj=0u_j = 0 across all currently cached sparse codes) with the normalized reconstruction residual. This keeps the dictionary size strictly fixed at NN without invalidating previously encoded KV representations.

The authors provide theoretical analyses covering complexity, attention perturbation bounds under KV reconstruction error, and a weak-submodularity perspective on greedy atom selection. Empirical evaluations are conducted on Llama-3.2-3B-Instruct, Llama-3.1-8B-Instruct, and Qwen3-4B-Instruct across reasoning benchmarks (GSM8K, MATH500, GPQA-D, LongReason) and long-context benchmarks (RULER at 8K/16K, LongBench).

Critical strengths
  1. Insightful Empirical Diagnostics Motivating the Algorithmic Design (Section 1, Figure 1): The paper provides clear and well-designed preliminary diagnostics on Llama-3.2-3B that justify both components of FAD-KV. Specifically, showing that one-shot inner-product scores are heavily head-concentrated—where screening just 6.25% of the dictionary (Top-256 out of 4096) recalls 85.7% of the full-OMP support—strongly motivates candidate pruning. Furthermore, demonstrating that ~22.9% of offline-learned dictionary atoms remain completely unreferenced (uj=0u_j = 0) after prefilling provides a solid empirical basis for recycling dead dictionary capacity during test-time adaptation.

  2. Zero-Invalidation Fixed-Size Dictionary Update Rule (Section 3.2): Restricting online atom replacement strictly to the inactive set U0={j∣uj=0}\mathcal{U}_0 = \{j \mid u_j = 0\} is a clean and practical design choice. Unlike naive LRU/LFU eviction over dictionary atoms—which would either corrupt historical sparse codes referencing the evicted atom or trigger expensive re-encoding of the entire KV cache—replacing only unreferenced atoms guarantees a strictly bounded O(Nd)O(Nd) dictionary footprint with zero re-encoding overhead for past tokens.

Critical weaknesses
  1. Unconvincing Memory-Accuracy Trade-off and Omission of Essential Baselines (Section 5, Tables 1–4, Figure 3):
  • Minimal memory savings at the cost of notable accuracy degradation: A central premise of the paper is that append-only adaptation (Lexico-ADP) suffers from problematic dictionary growth. However, Figure 3(a) shows that after 1,000 decoding steps, the dictionary size grows by only ~6% for Lexico-ADP (and ~8–11.5% for GM/PL). In Table 4, the actual per-sequence memory difference between Lexico-ADP and FAD-KV is completely negligible: 0.040 GB vs. 0.040 GB on Llama-3.1-8B (0 MB saved) and 0.024 GB vs. 0.020 GB on Llama-3.2-3B (only 4 MB saved). Yet, enforcing fixed-size replacement causes substantial accuracy drops compared to append-only adaptation across benchmarks (e.g., in Table 1, Llama-3.2-3B on LongReason drops from 44.0% to 32.0%/17.0%; in Table 2, Qwen3-4B on RULER 8K MQ drops from 54.0% to 30.5%).
  • Degradation below the static dictionary baseline: Even more concerning, FAD-KV frequently underperforms the static Lexico baseline (which performs no adaptation at all). For instance, on Llama-3.2-3B GSM8K (Table 1), static Lexico achieves 28.4% while FAD-KV (GM) drops to 22.0%. On Qwen3-4B LongBench (Table 3), FAD-KV (PL) suffers catastrophic degradation compared to static Lexico on HotpotQA (36.06 vs. 49.85), 2WikiMultihopQA (21.70 vs. 31.63), and Musique (12.04 vs. 16.61). This contradicts the claim that replacing strictly unused atoms safely improves test-time adaptability.
  • Missing uncompressed (Full KV) and competing compression baselines: Tables 1, 2, and 3 omit the uncompressed Full KV accuracy entirely, making it impossible to gauge the absolute quality loss of dictionary compression (especially given anomalously low scores, such as ~22–32% on GSM8K for Llama-3.2-3B-Instruct). Moreover, no comparisons are made against standard non-dictionary KV compression baselines (e.g., KIVI, SnapKV, Quest) under matched memory budgets.
  1. Systems-Level Contradictions in Sparse Solver Complexity and Batched Decoding Scalability (Section 3.1, 4.1, 5.5):
  • Theoretical vs. empirical paradox in Pool-Ridge (PL): In Section 4.1, screened GM requires O(Nd+snd)O(Nd + snd) operations, whereas PL requires forming the Gram matrix DC⊤DCD_{\mathcal{C}}^\top D_{\mathcal{C}} and solving an n×nn \times n linear system in O(Nd+n2d+n3)O(Nd + n^2d + n^3). Under the default hyperparameters (n=256n=256 or 512512, d=128d=128, s=8s=8 or 1616), n2d+n3n^2d + n^3 is orders of magnitude larger in FLOPs than sndsnd. The only reason PL achieves lower wall-clock latency than GM in Table 4 (e.g., 51.76 ms vs. 66.61 ms on 8B) is that ss sequential steps in GM incur Python/CUDA kernel launch overhead, rather than PL being computationally cheaper. Furthermore, all dictionary methods remain ~1.7x–2.5x slower in per-token latency than Full KV during single-sequence decoding.
  • Dictionary duplication bottleneck in batched decoding: The paper claims superior throughput under large batch sizes (Section 5.5). However, online dictionary adaptation modifies atoms in-place based on sequence-specific residuals and sequence-specific reference counts U0\mathcal{U}_0. In a batched decoding setting (B>1B > 1), different sequences have different active sets U0\mathcal{U}_0 and different residual shifts. If each sequence in the batch must maintain its own private mutated copy of the dictionaries Dk,DvD_k, D_v in GPU memory, the dictionary memory overhead scales as O(B⋅L⋅Nd)O(B \cdot L \cdot N d), which would rapidly exhaust GPU memory and negate the KV cache compression savings. The paper fails to explain how adaptive dictionaries are shared or isolated across batch items.
Questions for authors

Clarification Requests (Material to Assessment):

  1. Dictionary Granularity and Batch-Level Memory Scaling (Section 2.1, 3.2, 5.5 & Appendix C.2): There is a direct contradiction between Section 2.1, which defines per-layer, per-head dictionaries Dk(l,h),Dv(l,h)D_k^{(l,h)}, D_v^{(l,h)}, and Appendix C.2 (lines 1074–1076), which states that dictionaries are layer-specific ("each layer has one key dictionary and one value dictionary"). (a) Which granularity is actually used in the experiments, and what is the exact total memory footprint (in MB/GB) of the dictionaries themselves? (b) In the batched throughput experiments (lines 450–453), how is online atom replacement handled across concurrent sequences in a batch? Does each sequence maintain an independent copy of the dictionary, or is a single dictionary mutated globally across the batch?

  2. Why Does FAD-KV Underperform Static Lexico on Multiple Benchmarks? (Tables 1 & 3): Since FAD-KV only replaces inactive atoms (uj=0u_j = 0) that were never used by cached tokens, why does it degrade accuracy substantially compared to static Lexico in several settings (e.g., Llama-3.2-3B GSM8K dropping from 28.4% to 22.0% in Table 1; Qwen3-4B FAD-KV (PL) dropping by 10–13 points on LongBench Multi-Doc QA in Table 3)? Does inserting normalized residual vectors introduce noisy directions that mislead the greedy/ridge encoder on subsequent decoding steps?

  3. Omission of Full KV Accuracy and Low GSM8K Scores (Tables 1–3): Could the authors provide the uncompressed Full KV accuracy across all benchmarks in Tables 1, 2, and 3? Furthermore, why do all methods on Llama-3.2-3B-Instruct achieve only 22.0%–32.8% on GSM8K (where standard zero-shot/few-shot instruct performance is >75%)?

  4. Availability of Inactive Atoms (U0\mathcal{U}_0) in Long-Context Workloads (Section 3.2 & 5.3): Figure 1(c) measures the fraction of inactive atoms (22.9%) after prefilling on MATH-500, where prompts are relatively short. In 16K context benchmarks like RULER and LongBench, each layer/head encodes 16,000 KV vectors with sparsity s=8s=8 or 1616 over N=4096N=4096 or 81928192 atoms. What percentage of dictionary atoms remain in U0\mathcal{U}_0 (uj=0u_j=0) after prefilling 16K tokens? Does U0\mathcal{U}_0 become completely empty during long-context tasks, effectively reducing FAD-KV to a static dictionary?

  5. Implementation Details of GM vs. PL and Corrupted Table Entries (Section 4.1, Tables 4 & 5): (a) How are GM and PL implemented (e.g., native PyTorch vs. fused Triton/CUDA kernels)? Given that O(n2d+n3)≫O(snd)O(n^2d + n^3) \gg O(snd) for n=512,d=128,s=16n=512, d=128, s=16, please clarify the exact FLOPs vs. kernel launch overhead of both solvers. (b) Please fix and clarify the corrupted entries in Table 4 (for Llama-3.1-8B Full KV, Latency shows 30.22 39.23, Decode tok/s shows 336, and Per-seq KV is blank) and Table 5 (symbols for Sparsity budget and Candidate-pool size are printed as N and 71 instead of ss and nn).

4 comments
AuthorsOpenReview ↗

Part 1/4: Corrections and Improved Results

We thank the reviewer for the detailed feedback. It helped us identify an implementation bug and improve FAD-KV. We summarize the new results first, then address each concern. We will include these changes and clarifications in the revised paper.

Bug fix. The set of unreferenced atoms, U0U_0, was initialized after prefill but not updated during decoding. A newly referenced atom could therefore be replaced, changing a stored code's reconstruction. We fixed the bookkeeping so that referenced atoms cannot be replaced. In initial Llama-3.2-3B GSM8K tests, this raised PL from 24.0% to 28.1% and GM from 26.0% to 28.5%, versus 27.2% for Lexico (three-run averages). Table R1 reports results rerun under the final evaluation setup.

Attention-weighted allocation. The original method gives every key exactly ss coefficients. However, some keys matter more to attention than others. We now allocate different numbers of coefficients across nn keys while keeping the total budget at nsns. Following Proposition 1, allocation is based on attention-weighted reduction in key reconstruction error. We build up to 3s3s candidate coefficients per key, allocate the budget across these encoding paths, and refit the selected coefficients by least squares. This applies to prompt and generated keys. At s=8s=8, each key still uses eight coefficients on average, so compressed-cache memory is unchanged.

For the following, we refer to FAD-KV as the bug-fixed method with allocation; and w/o allocation to mean the bug-fixed submitted method.

Table R1. Llama-3.2-3B, s=8s=8, N=4096N=4096. All compressed methods are evaluated under the same storage budget. Parentheses give differences from Lexico (GSM8K: 250; MATH-500: 500; RULER-8K: 400 questions).

MethodGSM8KMATH-500RULER-8K
Full KV72.444.496.1
Lexico31.214.833.7
FAD-KV (PL), w/o allocation34.0 (+2.8)18.0 (+3.2)33.2 (−0.5)
FAD-KV (PL)36.0 (+4.8)20.2 (+5.4)69.6 (+36.0)
FAD-KV (GM), w/o allocation27.2 (−4.0)15.4 (+0.6)32.0 (−1.7)
FAD-KV (GM)36.4 (+5.2)22.6 (+7.8)68.0 (+34.3)

Allocation improves FAD-KV, especially on RULER-8K (+36.4 points for PL and +36.0 for GM). The improved method exceeds Lexico in all six comparisons.

AuthorsOpenReview ↗

Part 2/4: Memory and Accuracy

W1(a). Memory saving vs. accuracy.

We agree that savings over our capped append baseline are small. Append was limited to 1,024 extra atoms per layer and per K/V dictionary, a detail missing from Table 5. Thus, fixed-size replacement saves at most 14 / 16 / 18 MiB for Llama-3.2-3B / Llama-3.1-8B / Qwen3-4B. We will correct the table and no longer present this saving as the main benefit. The primary benefit is bounded dictionary size without tuning an append cap, while recovering much of append's accuracy gain when free atoms remain.

LongReason and RULER MQ use 8K prompts. By the end of processing, nearly all atoms have been referenced (Q4), so replacement stops while append can still grow. We agree that this limits adaptation on long prompts and will state it in Section 6. Allocation addresses a different issue: even with no free atoms, it raises RULER-8K PL accuracy from 33.2% to 69.6% (Table R1). On shorter prompts, replacement helps: on GSM8K, static PL / replacement / append score 16.0 / 28.1 / 32.8, and on Qwen3-4B GSM8K, 18.8 / 60.8 / 64.8.

W1(b) / Q2. Why can FAD-KV fall below static Lexico?

The comparison mixes dictionary policy with encoder choice. Lexico uses full-dictionary OMP while FAD-KV uses screened GM or PL, trading some reconstruction quality for speed. After the bug fix, replacement itself does not invalidate stored codes. With the same PL encoder, replacement improves GSM8K from 16.0% (static) to 28.1% and MATH-500 from 11.6% to 20.0%.

The reported GSM8K gap was largely due to the bug. In Table R1, the bug-fixed method without allocation gives mixed results relative to Lexico. GM trails by 4.0 points on GSM8K and 1.7 on RULER-8K, while PL is ahead on GSM8K and MATH-500. On Qwen3-4B HotpotQA, the larger drop comes mainly from PL (36.06); GM reaches 50.75, versus 49.85 for Lexico. Allocation targets this encoder limitation by spending coefficients where their errors affect attention most.

W1(c) / Q3. Full KV and the accuracy-memory trade-off.

We measured Full KV under the same evaluation protocol. The gap at s=8s=8 can be explained by two factors: very sparse codes (8 atoms per 128-dimensional vector) and a short full-precision window (32 recent tokens). Training dictionaries at s=16s=16 and s=24s=24 with the same recipe greatly reduces the gap (Table R2). Separately, expanding the window to 128 tokens (about 14 MiB extra per sequence) raises GSM8K from 26.6% to 58.0% for Lexico and from 30.8% to 65.2% for FAD-KV (PL) without allocation.

Table R2. Llama-3.2-3B with a separately trained dictionary at each ss (56 MiB shared dictionary). KV memory is after an 8K prompt, excluding the dictionary. Speed-up is over Lexico at the same ss, measured at 1K context (A100-80GB, batch 1, two runs). Lexico uses the matched sparsity storage budget.

MethodssGSM8KMATH-500RULER-8KKV at 8K (MiB)Speed-up vs Lexico (1K)
Full KV–72.444.496.1896–
Lexico831.214.833.71301.00×
FAD-KV (PL)836.020.269.61301.10×
FAD-KV (GM)836.422.668.01301.04×
Lexico1664.838.491.72441.00×
FAD-KV (PL)1659.637.093.92441.47×
FAD-KV (GM)1660.438.093.72441.14×
Lexico2469.641.895.33571.00×
FAD-KV (PL)2465.640.695.43571.70×
FAD-KV (GM)2470.439.895.93571.11×

At s=24s=24, GM is within 4.6 points of Full KV on all tasks using 2.5× less KV memory. PL reaches 1.70× faster decoding than Lexico at 1K because it avoids ss sequential OMP selections. This speed-up is relative to Lexico, not Full KV: at batch 1, dictionary methods are slower per token than Full KV. Allocation also increases prefill time, up to 1.3× Lexico at 8K and 1.9× at 1K (s=24s=24). We will report these trade-offs in the revision.

AuthorsOpenReview ↗

Part 3/4: Other Baselines and Encoding Cost

W1(c) / Q3 (continued). KIVI and token-selection baselines.

We evaluate KIVI using its official quantization policy (group size 32, 32-token full-precision window), including generated-token compression. For KIVI-1, we use an equivalent PyTorch implementation validated against the official arithmetic at supported precisions. We include both FAD-KV encoders (PL and GM) for each sparsity setting.

Table R3. Llama-3.2-3B, same evaluation as Table R1. Each group compares KIVI, Lexico, FAD-KV (PL), and FAD-KV (GM) at the corresponding sparsity setting. The best accuracy within each group is bolded.

MethodGSM8KMATH-500RULER-8K
KIVI-10.01.42.3
Lexico, s=8s=831.214.833.7
FAD-KV (PL), s=8s=836.020.269.6
FAD-KV (GM), s=8s=836.422.668.0
KIVI-271.232.694.5
Lexico, s=16s=1664.838.491.7
FAD-KV (PL), s=16s=1659.637.093.9
FAD-KV (GM), s=16s=1660.438.093.7
KIVI-470.043.095.8
Lexico, s=24s=2469.641.895.3
FAD-KV (PL), s=24s=2465.640.695.4
FAD-KV (GM), s=24s=2470.439.895.9

At the lowest memory setting, both FAD-KV encoders outperform KIVI-1 and Lexico. At the middle setting, KIVI-2 leads on GSM8K and RULER-8K, while Lexico slightly leads on MATH-500. At the highest setting, results are close across methods, with FAD-KV (GM) leading on GSM8K and RULER-8K. We will include this comparison without claiming that dictionary coding always outperforms quantization.

SnapKV and Quest select which tokens or pages to access, rather than compress every stored token. In particular, SnapKV keeps generated tokens uncompressed and Quest keeps the full KV cache resident, so their GPU memory use is not directly comparable at equal compressed-cache budgets. Their selection mechanisms can also be combined with dictionary compression.

W2(a) / Q5(a). Why is PL faster despite higher arithmetic cost?

The reviewer is correct about FLOPs: at pool size 256, d=128d=128, s=8s=8, the PL solve uses about 14M multiply-adds per vector, versus 0.26M for GM's correlation scans. But GM has ss sequential select-and-refit steps, while PL uses batched dense operations (Gram product and Cholesky solve). On Llama-3.1-8B, encoding one token across all K/V layers takes 31.2 ms (OMP), 23.5 ms (GM), and 8.6 ms (PL). No method uses custom fused kernels.

Our batched solve uses (DC⊤DC+λI)−1DC⊤x=DC⊤(DCDC⊤+λI)−1x(D_C^\top D_C+\lambda I)^{-1}D_C^\top x=D_C^\top(D_CD_C^\top+\lambda I)^{-1}x when beneficial, reducing the cost to O(nd2+d3)O(nd^2+d^3). We will clarify that Table 4's “Cost” column counts correlation scans, not total FLOPs, and add measured latency.

AuthorsOpenReview ↗

Part 4/4: Dictionary Sharing and Corrections

W2(b) / Q1. Dictionary granularity and batched memory.

There is no per-sequence dictionary. Each layer has one shared key dictionary and one shared value dictionary, each D∈R128×ND\in\mathbb{R}^{128\times N}, shared across KV heads and batch sequences. An atom can be replaced only if no stored code in the batch references it. Dictionary memory is independent of batch size: 56 / 128 / 72 MiB for Llama-3.2-3B / Llama-3.1-8B / Qwen3-4B. The per-head notation in Section 2.1 is incorrect and we will fix it in the updated paper. At batch 64, U0U_0 is exhausted, so large-batch benefits come from compression and encoding, not ongoing adaptation. For example, at 16K context under a 24 GB limit, FAD-KV (PL) without allocation reaches 246 tok/s (batch 64), versus 74.6 tok/s for Full KV with eager decoding (batch 8), or 3.30× higher aggregate decoding throughput relative to Full KV eager.

Q4. How many inactive atoms remain after 16K prefill?

We measured unused atoms on Llama-3.2-3B using eight LongBench prompts per length:

Prefill5121K2K4K8K16K
Unreferenced atoms (U0/NU_0/N)0.97%0.12%0.01%0%0%0%
Dictionaries with none left0%36%79%97%99.8%100%

The other models show the same pattern: after roughly 1–2K prompt tokens, adaptation becomes limited, and by 16K no free atoms remain. We will add this limitation to Section 6. Allocation still works because it reallocates coefficients, not dictionary atoms.

Q5(b). Table rendering.

We have double-checked the PDF and could not reproduce the reported rendering issues. In our version, Table 4 correctly displays 30.22 ms/token, 33.09 tokens/s, and 0.142 GB KV memory for the Llama-3.1-8B Full KV row. The symbols ss and nn in Table 5 also appear correctly. These issues may be related to the PDF viewer or font rendering. Could the reviewer kindly check the PDF using a different viewer? We would be happy to adjust the formatting if the issues persist.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.