- 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
- 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.
- 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
- 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.
- 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
-
Please isolate screening and solver contributions using comparable full-dictionary and screened-pool implementations. Report encoding/decoding time, quality, and memory trade-offs.
-
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?
-
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
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 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 , so memory is unchanged (Proposition 1). At , 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.
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.
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):
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=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.
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, U0 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).