- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes Iceberg Attention and its training-free implementation, Mixture-of-Gaussians (MoG) Attention, for efficient long-context decoding. The method combines exact attention over query-dependent token clusters with analytical approximation of the remaining attention contributions using Gaussian statistics. With custom CUDA kernels and vLLM integration, the authors demonstrate sublinear KV-cache access and substantial decoding speedups at very long contexts, while maintaining competitive accuracy on multiple benchmarks.
Critical strengths
-
Unlike conventional sparse or retrieval-based attention that discards unselected tokens, MoG analytically approximates their aggregate contribution. Combining exact attention with a Gaussian-based residual provides an interesting approach to reducing KV-cache accesses without retraining.
-
The authors implement custom CUDA kernels and integrate MoG into vLLM. The reported reductions in data movement and decoding latency are impressive, particularly for million-token contexts where KV-cache access becomes a major bottleneck.
-
The experiments cover multiple GPUs, language models, and long-context benchmarks. The analyses of approximation accuracy and individual attention tiers provide useful evidence supporting the proposed design.
Critical weaknesses
1.The headline speedups mainly reflect steady-state decoding and exclude the one-time clustering cost. Appendix B.1 reports an initialization cost of 11.5 seconds at 100K tokens, requiring approximately 5,000 generated tokens to break even in the tested configuration. This considerably limits the benefits for typical generation workloads. A clearer end-to-end latency analysis would strengthen the practical claims.
-
Appendix G shows that APPROX reduces the attention-output error from approximately 17% to 13% compared with HOT+WARM. However, it is unclear how much this improvement translates into downstream accuracy gains. Moreover, the approximation relies on Gaussian modeling and replacing token values with their subcluster mean, whose limitations deserve further analysis.
-
MoG exhibits noticeable degradation on REPOQA and AA-LCR, especially at longer contexts. For example, Qwen3-14B drops from 0.430 to 0.344 on REPOQA and from 0.411 to 0.350 on AA-LCR. These results suggest that the approximation may struggle with tasks requiring precise retrieval or complex cross-document reasoning.
-
The evaluation primarily compares against RetroInfer, whose implementation encounters failures at longer contexts. Other closely related clustering-based approaches, such as Tactic, are not directly evaluated. Furthermore, Appendix E indicates that MoG performs noticeably worse on models without QK normalization, which limits its applicability as a general drop-in attention mechanism.
Questions for authors
-
Can the authors clarify the expected end-to-end speedups for more typical generation lengths, such as 512 or 2,048 tokens, including clustering overhead?
-
How much does the APPROX tier improve downstream accuracy over HOT+WARM alone under the same exact-attention budget, particularly on REPOQA and AA-LCR?
-
Could the authors further clarify the differences from Tactic and other clustering-based attention methods, and discuss the accuracy degradation observed on challenging long-context tasks?
-
How broadly does MoG generalize to models without QK normalization, and what modifications would be required to maintain accuracy?
5 comments
Thank you for the response and the new experiments. The with/without-APPROX ablation (especially RepoQA, 0.374 vs. 0.276) and the per-sample wall times are helpful. A few inconsistencies need clarification:
-
ParisKV timing. In the new table, ParisKV's wall time equals Exact's on every benchmark (66.8, 67.2, 58.6, 59.5, 67.9 s). Please confirm that these timings were measured separately for ParisKV.
-
Changed numbers. AA-LCR is now 0.21 vs. 0.25 (Qwen3-14B) and 0.13 vs. 0.13 (Qwen3-4B), whereas Table 4 reports 0.350 vs. 0.411 and 0.297 vs. 0.379. Exact-attention scores also changed (e.g., BICS at 128k: 0.040 → 0.060). Sink handling should not affect exact attention, so please explain what changed (scoring, hardware, or sample set).
-
Clustering overhead. The amortization table uses 8 ms vs. 30 ms TPOT, but Appendix B.1 reports whole-model steps of 24.0 vs. 26.2 ms at 100k, a saving of only 2.2 ms. With a 1.5 s fit, that implies a break-even of roughly 700 tokens, not a clear gain at 512. Please report fit time and whole-model TPOT from the same setup (the fit is quoted on both an A40 and an A5000).
I will keep my current score for now and revisit it once these points are clarified.
Thank you for the careful follow-up. We address each point below.
1. Exact and ParisKV timing
The Exact times in our previous table were wrong. There was an error in formatting/copying the data into markdown. We apologies for the confusion. We have now measured exact attention on 4×A5000 setup and harness as MoG (Qwen3-14B, 128k, tensor parallelism 4, 5-sample subset per benchmark). Accuracy / wall time per sample (s):
| Benchmark | Exact | MoG | ParisKV |
|---|---|---|---|
| NIAH | 0.600 / 50.3 | 0.800 / 51.4 | 0.600 / 66.8 |
| NeedleBench | 0.883 / 50.3 | 0.900 / 51.7 | 0.950 / 67.2 |
| NoLiMa | 0.400 / 44.5 | 0.420 / 45.1 | 0.400 / 58.6 |
| BICS | 0.060 / 56.2 | 0.070 / 59.2 | 0.050 / 74.7 |
| RepoQA | 0.430 / 50.9 | 0.374 / 52.2 | 0.283 / 67.9 |
At 128k with short answers (≤64 tokens), the per-sample time is dominated by the dense prefill, which is identical for all methods, so MoG and exact attention are within a few percent. Decode cost is compared in point 3. (Note: These numbers are now all on the same 4×A5000 setup. In the initial table the BICS time for MoG and ParisKV was on A6000)
We also ran Qwen3-8B at its native 32k context on 200 Python RepoQA cases. Within each case, the inputs and the physical A6000 GPU are the same for all methods, with a common 1,024-token generation cap and natural EOS:
| Method | Accuracy | Mean request time |
|---|---|---|
| Dense | 92.5% | 13.68 s |
| MoG | 92.0% | 15.55 s |
| ParisKV (GPU-resident) | 91.0% | 18.12 s |
2. Changed numbers
BICS. The BICS row in the paper came from an earlier run whose few-shot prompt demonstrated only 2 of the 7 bug types, which biased all methods toward predicting "missing_colon". The prompt is fixed in the new runs (one example per bug type) and reran all methods with the same model and the same 100 samples. Exact attention at 128k changes from 0.04 to 0.06. We will update the BICS row at all lengths accordingly.
AA-LCR. The scoring changed. Table 4 used our original harness's proxy score, based on coverage of the reference answer's elements. The new numbers use the official AA-LCR v1.1 judged evaluation (100 questions, 1,024-token cap), which gives lower absolute scores for both methods. Under this evaluation, Qwen3-14B scores 0.21 (MoG) vs 0.25 (exact), with a paired 95% interval of [−11.57, 3.23] points that includes zero, and Qwen3-4B scores 0.13 vs 0.13. We will update Table 4 to the official scoring.
3. Clustering overhead
The amortization table in our previous response combined numbers from different setups. All numbers below are from a single GPU type (A40).
A whole-model decode step consists of the weight operations (bounded by moving the model weights), the attention operations (bounded by moving the KV cache), and engine overheads. vLLM's pipeline, in particular its memory management, is optimized for its own FlashAttention backend. MoG replaces the attention layer, so this path is not optimized for it, and the end-to-end decode gain becomes less visible. Optimizing vLLM's memory management for MoG is a separate engineering effort that we are pursuing for the full release. For a fair comparison of the attention mechanism itself, the kernel-level time is the relevant measure.
| Setup | Exact step | MoG step | Saving per token | One-time cost | Break-even |
|---|---|---|---|---|---|
| Attention kernel, 36 layers, 128k (A40, Figure 5) | 31.9 ms | 7.6 ms | 24.3 ms | 1.08 s clustering / 3.25 s total | 45 / 134 tokens |
| Whole model, 100k (2×A40, Appendix B.1) | 26.2 ms | 24.0 ms | 2.2 ms | 2.84 s total | ~1,290 tokens |
The total one-time cost covers clustering, cluster statistics, store reordering, calibration and CUDA-graph capture. With the new GPU clustering, it drops from 11.5 s (Appendix B.1) to 2.84 s at 100k, which lowers the end-to-end break-even from ~5,000 to ~1,290 tokens. At the kernel level, MoG repays its one-time cost within 134 generated tokens.
Thank you for your time and careful review. We appreciate your informative feedback. Please find our responses below. We hope our clarifications address your concerns and would appreciate it if you would consider revising your evaluation. If any concerns remain, we would be happy to address them.
W1 / Q1. Clustering overhead and end-to-end latency
MoG does not affect TTFT: the first token uses regular attention, and clustering only affects decoding from the second token onward (Section 4). The 11.5 s in Appendix B.1 comes from the non-optimized implementation. We now run k-means fully on the GPU, parallelized across heads and clusters, during the first decode step. This takes ~1.5 s at 128k on an A5000. The one-time cost is amortized over all generated tokens:
We will update Figure 3 to include the clustering overhead.
W2 / Q2. Downstream effect of APPROX
We ran the pipeline with and without APPROX (HOT+WARM only) under identical selection on Qwen3-14B at 128k:
APPROX gives meaningful downstream improvements, complementing the attention-output error reduction in Appendix G.
W3. RepoQA and AA-LCR
With attention-sink handling added since submission, Qwen3-14B RepoQA at 128k improves from 0.344 to 0.374 (exact: 0.430). On AA-LCR, Qwen3-14B scores 0.21 vs 0.25 for exact; the paired difference has a 95% interval of [−11.57, 3.23] points, which includes zero. Qwen3-4B matches exact (0.13 vs 0.13).
W4 / Q3. Other baselines and RetroInfer's failures We have added a comparison with ParisKV on Qwen3-14B at 128k. ParisKV is slower than MoG on every benchmark while having a less accuracy. Specifically, at RepoQA ParisKV scores 0.283 with 67s of wall-clock time per sample, whereas MoG scores 0.373 with 52s.
(accuracy / wall time per sample in seconds, same hardware)
SqueezedAttention, ClusterKV and Tactic select clusters or tokens and drop the rest. MagicPIG and vAttention sample the long tail, which introduces sampling noise. RetroInfer, the closest prior work, approximates unselected clusters from centroid scores. All of these rely on cluster selection or ANN search, which is inherently noisy in high dimensions: some high-attention tokens are always missed, and the mass of unselected clusters is lost. MoG instead approximates the unselected clusters analytically. This rests on two findings: keys are well represented as a Mixture of Gaussians, and the attention mass of a Gaussian cluster equals its MGF, which has a closed form. Each unselected cluster thus becomes a pseudo-token carrying its estimated mass and aggregate value, compensating for selection errors.
RetroInfer's failures at 100k–128k stem from empty clusters in its k-means index (Appendix B.3).
Q4. Models without QK normalization
In our evaluation of the Qwen2.5 family, which does not use QK normalization, performance degrades on benchmarks beyond 100k tokens. We attribute this to heavier tails in the attention distribution: without normalization, q·k is unbounded. Independently of MoG, QK normalization has been shown to improve stability and has been adopted by most recent models.