acceptodds
Under review as a conference paper at ICLR 2027

Iceberg Attention: Sublinear Long-Context Decoding with Mixture-of-Gaussians

29 views

Abstract

Autoregressive decoding over long contexts repeatedly scans the entire KV cache, though only a small fraction of cached tokens strongly influence each query. We introduce Iceberg Attention, a class of attention mechanisms that exploits this asymmetry by attending exactly to a small, query-dependent subset of the KV cache while analytically approximating the contribution of remaining tokens. Unlike sparse or retrieval-based attention, Iceberg Attention does not discard the residual cache; instead, it represents its aggregate contribution using a compact approximation. This formulation decouples the cost of exact attention from the context length and enables sublinear KV-cache access. We present Mixture-of-Gaussians (MoG) Attention, the first Iceberg Attention mechanism. % After prefill, MoG hierarchically partitions the keys of each attention head into clusters and subclusters per cluster, representing each group by a Gaussian distribution. During decoding, the query is scored against these compact representations to identify the most relevant clusters and subclusters, which are attended exactly. The remaining cache is approximated from the means and variances of its Gaussian representations. MoG reduces per-token attention from to without retraining or fine-tuning the model. We implement MoG as a drop-in replacement for attention in vLLM with a custom CUDA implementation that substantially reduces KV-cache data movement. At a context length of 1M tokens, MoG decoding is 27 faster than vLLM with FlashAttention and 2 faster than RetroInfer, a state-of-the-art sparse attention system, on an Nvidia H100 GPU. Across eleven long-context benchmarks using Qwen3-4B, Olmo3-7B, and Qwen3-14B at 8K–128K tokens, MoG matches exact attention while reading less than 5.3% of the KV cache. Ablations show the residual is what makes the method safe, cutting error of attending the top clusters alone from to . These results demonstrate that long-context decoding can avoid reading most of the KV cache without modifying or retraining the underlying model.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
long-context inference, KV cache, sparse attention, approximate attention, efficient decoding, training free cache reduction

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_orWjOpenReview ↗
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
  1. 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.

  2. 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.

  3. 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.

  1. 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.

  2. 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.

  3. 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
  1. 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?

  2. 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?

  3. 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?

  4. How broadly does MoG generalize to models without QK normalization, and what modifications would be required to maintain accuracy?

5 comments

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:

Generated tokensAmortized overheadMoG TPOT (incl. clustering)Exact TPOT
5122.9 ms10.9 ms30 ms
2,0480.7 ms8.7 ms30 ms

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:

BenchmarkExactMoGMoG w/o APPROX
NIAH0.6000.8000.400
NeedleBench0.8830.9000.817
NoLiMa0.4000.4200.400
BICS0.0600.0700.040
RepoQA0.4300.3740.276
MultiHop-RAG0.8110.8080.818
LoCoMo0.4250.4110.412

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)

BenchmarkExactMoGParisKV
NIAH0.600 / 66.80.800 / 51.40.600 / 66.8
NeedleBench0.883 / 67.20.900 / 51.70.950 / 67.2
NoLiMa0.400 / 58.60.420 / 45.10.400 / 58.6
BICS0.060 / 59.50.070 / 45.80.050 / 59.5
RepoQA0.430 / 67.90.374 / 52.20.283 / 67.9

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.

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:

  1. 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.

  2. 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).

  3. 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):

BenchmarkExactMoGParisKV
NIAH0.600 / 50.30.800 / 51.40.600 / 66.8
NeedleBench0.883 / 50.30.900 / 51.70.950 / 67.2
NoLiMa0.400 / 44.50.420 / 45.10.400 / 58.6
BICS0.060 / 56.20.070 / 59.20.050 / 74.7
RepoQA0.430 / 50.90.374 / 52.20.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:

MethodAccuracyMean request time
Dense92.5%13.68 s
MoG92.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.

SetupExact stepMoG stepSaving per tokenOne-time costBreak-even
Attention kernel, 36 layers, 128k (A40, Figure 5)31.9 ms7.6 ms24.3 ms1.08 s clustering / 3.25 s total45 / 134 tokens
Whole model, 100k (2×A40, Appendix B.1)26.2 ms24.0 ms2.2 ms2.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.

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

This paper proposes Iceberg Attention and its Mixture-of-Gaussians (MoG) implementation for long-context decoding. MoG combines exact attention over selected KV clusters with Gaussian-MGF-based approximations of the remaining attention contribution. The method requires no retraining and achieves substantial reductions in steady-state KV-cache traffic.

Critical strengths
  1. The Gaussian-MGF formulation provides an interesting and efficient approach to estimating cluster attention mass.
  2. The hierarchical HOT/WARM/APPROX design and optimized CUDA implementation demonstrate meaningful algorithmic and systems engineering.
  3. Evaluations across multiple models and long-context benchmarks show promising accuracy preservation and substantial memory-traffic reductions.
Critical weaknesses
  1. Novelty relative to existing residual-estimation methods is insufficiently established. RetroInfer already incorporates an estimation zone that approximates unselected clusters using centroid-based attention weights and aggregated values. Thus, the exact-selection-plus-residual paradigm is not entirely new. The paper should better isolate the contribution of Gaussian-MGF estimation through controlled comparisons with centroid-based residual estimation, particularly by ablating the variance term while keeping the selected tokens fixed.

  2. Baseline comparisons are insufficient to establish a clear accuracy–efficiency advantage. RetroInfer is the principal competing retrieval system evaluated experimentally, but its dense fallback at short contexts and implementation failures at longer contexts complicate interpretation. Additional comparisons with Tactic, ParisKV, and related clustering-based approaches would strengthen the evaluation. More importantly, matched-budget quality–latency comparisons should account for total memory traffic, preprocessing overhead, and retrieval budgets.

  3. The residual approximation requires stronger validation. The Gaussian-MGF formulation approximates residual attention mass, while the mean-value approximation neglects correlations between attention logits and values. The resulting errors are not sufficiently characterized. Appendix G shows that APPROX reduces relative attention-output L2 error from 17% to 13%, but this ablation covers a limited set of decoding queries and does not establish corresponding downstream-task improvements. Notable quality drops on REPOQA and AA-LCR further motivate analysis of estimation errors, budget sensitivity, and model dependence.

Questions for authors

none

4 comments

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

We identify that:

  1. The keys can be well represented as a Mixture of Gaussians (MoG) in high dimensions, and
  2. The attention contribution for each cluster under the assumption that they follow a Gaussian distribution can be represented by its MGF, which has a closed-form solution.

We will run additional experiments to determine the contribution of this estimation (see W3).

W2

Comparison with ParisKV: We have run benchmarks to compare with ParisKV on a matched budget. Most of the results at 128K for Qwen3-14B are ready and are provided in the next comment,. We will update the results as more become available, and the full results will be ready for the camera-ready version. In summary, ParisKV achieves lower accuracy while incurring a significantly higher inference time (with the prefill overhead amortized over generated tokens). Specifically, for RepoQA, ParisKV scores 0.283 with 67s of wall-clock time per sample, whereas MoG scores 0.373 with 52s.

Other Baselines & Our Contribution: Regarding other baselines and our contribution, these methods differ mainly in how they treat the part of the KV cache that is not selected for exact attention. SqueezedAttention and ClusterKV use centroids to pick top clusters and drop the rest. MagicPIG and vAttention sample the long tail (MagicPIG through LSH-based importance sampling, vAttention through top-k selection plus random sampling of the residual with an adaptive budget, and both introduce sampling noise). RetroInfer is the closest prior work; it approximates non-retrieved clusters from centroid scores, cluster sizes and aggregated values. All of the methods rely on selecting clusters or running an ANN search, and in high dimensions both are noisy. Whatever selection method is used, some high-attention tokens are missed, and the attention mass of every unselected cluster is dropped. MoG’s contribution is to approximate the unselected clusters analytically instead of ignoring them. This is based on our two findings (see W1). Each unselected cluster is a distribution, and its contribution to the softmax is obtained from the closed-form Gaussian moment-generating function. The resulting pseudo-token contains the estimated attention mass and aggregate value of the entire group, compensating the error introduced cluster selection.

Comparison with RetroInfer & Preprocessing Overhead: Regarding RetroInfer, its failures at 100k–128k stem from empty clusters in its k-means index (Appendix B.3). Furthermore, MoG reads fewer tokens exactly and moves less data than both RetroInfer and exact attention while being faster (Fig. 4 and Table 1) and maintaining the same accuracy. Regarding preprocessing, the clustering overhead is approximately 1.5s for a 128k context on an A40 (the 11.5s in Appendix B.1 stems from a non-optimized implementation and will be updated). Assuming a conservative response length of 1k tokens, this amounts to approximately 1.5 ms per token. Since the TPOT of MoG and exact attention is roughly 8 ms and 30 ms, this overhead is negligible.

W3

To isolate the effect of the residual on downstream accuracy, we are running the pipeline without APPROX (HOT and WARM only) against the full pipeline with identical selection on Qwen3-14B at 128K. The results that are currently ready are provided in the next comment, where the APPROX provides meaningful improvements. We will update the results as more become available, and the full results will be included in the camera-ready version. This corresponds to the ablation study in Table 9, measured on task scores rather than attention-output error.

Qwen3-14B, 128k (accuracy / wall time per sample, s)

 Benchmark   Exact    MoG   MoG w/o APPROX   ParisKV  
NIAH0.600 / 50.30.800 / 51.40.400 / 53.00.600 / 66.8
NeedleBench0.883 / 50.30.900 / 51.70.817 / 51.50.950 / 67.2
NoLiMa0.400 / 44.50.420 / 45.10.400 / 45.10.400 / 58.6
BICS0.060 / 56.20.070 / 59.20.040 / 59.00.050 / 74.7
RepoQA0.430 / 50.90.374 / 52.20.276 / 52.30.283 / 67.9
MultiHop‑RAG0.811 /  43.00.808 / 42.00.818 / 41.80.804 / 53.0
LoCoMo0.425 / 38.70.411 / 49.90.412 / 50.00.394 / 64.7

(Hardware: 4× NVIDIA RTX A5000 for NIAH, NeedleBench, NoLiMa, BICS, RepoQA and 4× NVIDIA RTX A6000 for MultiHop, LoCoMo)

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:

MethodAccuracyMean request time
Dense92.5%13.68 s
MoG92.0%15.55 s
ParisKV (GPU-resident)91.0%18.12 s

Note: Since the initial submission, we made a minor refinement (handling attention sinks), which resulted in slight improvements in the benchmark scores shared above.

I thank the authors for their detailed response and additional experiments. The newly added comparison with ParisKV and the ablation study on APPROX have addressed some of my previous concerns; however, I still have the following two concerns:

Novelty of Gaussian-MGF. The new ablation demonstrates the effectiveness of residual estimation but does not quantify the additional gains provided by Gaussian-MGF over the centroid-based estimation used in RetroInfer. I suggest removing only the variance term in APPROX for comparison, while keeping the HOT/WARM selection unchanged, to more clearly define the core innovation and practical contribution of this method.

End-to-end inference efficiency. The new experiments show that, on Qwen3-8B at 32K, MoG's average request latency remains higher than that of Dense Attention (15.55s vs. 13.68s). Furthermore, the authors report that under a whole-model setup with a context length of 100K on two A40 GPUs, the break-even point is approximately 1,290 generated tokens. Given that clustering overhead varies with context length, it remains unclear whether this method can achieve significant end-to-end acceleration at longer context lengths and under realistic generation lengths.

Overall, I acknowledge the value of the authors' supplementary experiments. However, I believe that the aforementioned issues remain crucial for verifying the novelty and practical efficiency of the proposed method. Therefore, I will maintain my original score.

Thank you for your follow-up.

Why the variance term matters. A centroid estimate, as in RetroInfer, treats a cluster as if every key sat at its mean. Because attention is exponential, this always underestimates the cluster's attention mass: E[eq⊤k]≥eq⊤μ\mathbb{E}[e^{q^\top k}] \ge e^{q^\top \mu}. The missing mass comes from the few keys that align best with the query, which are exactly the keys softmax weights most. For a Gaussian cluster this mass has a closed form, eq⊤μ+12q⊤Σqe^{q^\top \mu + \frac{1}{2} q^\top \Sigma q}, so the variance term is precisely what the centroid misses. Two clusters with the same centroid score but different spread look identical to a centroid estimate, but MoG tells them apart from statistics stored once per cluster, without reading a single extra key. MoG uses this both to choose which keys to read exactly and to weight the clusters it skips. Under a tight budget, these two choices decide the output.

Variance vs. centroid only, at the same budget

Only the APPROX weights changed (the ablation you suggested). The selected tokens are identical, at 128k:

ModelAttention-output error, centroid onlyAttention-output error, MoG
Qwen3-4B16.1%13.0%
Qwen3-14B17.6%14.7%

Relative L2 error against exact attention.

End-task accuracy at 128k:

BenchmarkModelCentroid onlyMoGGain [95% CI]
RULERQwen3-4B0.7300.793+6.3 [4.3, 8.3]
RepoQAQwen3-14B0.3410.374+3.3 [1.2, 5.4]
BICSQwen3-14B0.0100.070+6.0 [1.0, 12.0]

Gains in points. On the other five benchmarks, the two are within noise.

The variance term reduces attention error on its own, and its largest effect comes when it also guides which keys are read. This is MoG's contribution beyond centroid-based estimation.

Efficiency at longer contexts

The one-time clustering cost and the per-token saving both grow linearly with context length. As a result, the break-even point, measured in generated tokens, stays flat as the context grows:

ContextClustering (A40, 36 layers)Break-even (attention kernel)
128k1.08 s45 tokens
1M9.46 s42 tokens

At 32k the cache is small and exact attention is already cheap. MoG targets long contexts, where the KV cache no longer fits on the GPU. There, MoG gives a clear end-to-end gain (128k, CPU-backed KV cache, Qwen3-14B, 75 RepoQA cases):

MethodMean time per complete request
Dense offload108.5 s
MoG96.4 s
Saving12.1 s [6.1, 19.2]

Requests averaged about 195 generated tokens. This is a realistic length, far below the 1,290 tokens of the GPU-resident 100k setup. Dense offload streams each layer's cache on demand without prefetching. Both methods used one H200 with the prompt KV cache in CPU RAM. Dense transferred about 20.96 GB of prompt KV per decode step, compared with 2.56 GB for MoG at the 20/80 budget.

We hope this information has addressed your concerns.

Reviewer_srS1OpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper tackles the LLM decoding efficiency issue. The authors design a sparse attention algorithm, that partition the keys into clusters and subcluters and represent each group with a Gaussian distribution. At decoding, a query attend exactly to the selected groups and attend to the summaries of the unselected groups. Experiments show that MoG outperformances RetroInfer, especially when sequence is short.

Critical strengths

S1. The paper seems to be well presented. The intuitions are relatively easy to follow.

Critical weaknesses

W1. The intuition of clustering and attending to the summaries of the unselected clusters have been extensively studied in the literature respectively, even in the RetroInfer work that MoG compared against. Despite algorithmic details, the main intuitions largely overlap. Other similar works including MagicPIG, vAttention, SqueezedAttention, ClusterKV, etc. I suggest the authors to explicitly and clearly discuss the intuition differences against them.

W2. MoG requires indexing building, which is an extra overhead that is not included into TTFT or TPOT neither. I like that the authors have reported this time, but it is a significant overhead ,e.g., 11.5s for 100k sequence. I suggest the authors to explicitly discuss why this is an overhead that can be tolerated or amortized.

Questions for authors

Q1. How’s the performance in the RULER dataset?

Q2. How’s the clustering algorithm designed and implemented? It seems that it is a gpu algorithm, which is non-trivial.

Q3. Will the code be open-sourced?

Comments on the paper

4 comments

Questions

  • Q1. Using Qwen3-4B-Instruct-2507 at 128k, MoG scores 79.27%. For context, exact attention scores 80.54%.
  • Q2. Thank you for highlighting this point. We agree that efficiently constructing the clustering hierarchy on the GPU is a non-trivial part of Iceberg.

Our clustering implementation exploits the structure of the KV cache. Within each layer, it processes KV heads and independent partitions in parallel on the GPU. Construction has two stages. First, a PCA-based tree divides each head's keys into balanced partitions. Independent nodes at the same tree level are processed in parallel, using Tensor-Core matrix products to build Gram matrices and GPU-local power iterations to compute split directions. Second, each partition is refined into smaller subclusters using k-means. Each local k-means problem runs within a GPU block, retaining centroids and processing keys in on-chip tiles. Tensor-Core matrix products compute assignments and centroid sums. The iterations and convergence check run entirely on the GPU, without host synchronization inside the local k-means loop.

During the first decode step, we achieve a 23×23\times speedup (29.4 ms29.4\text{ ms} vs. 680.8 ms680.8\text{ ms} per layer) on Qwen3-4B at 128K context with zero quality loss.

Key Architecture & Kernel Optimizations

  • Massive Concurrency: Tree nodes and clusters run as lock-free, independent GPU programs (∼4,096\sim 4,096 concurrent kernels), keeping all 64 SMs on an RTX A5000 fully saturated with zero host synchronization.
  • PCA Tree Stage: Gram matrix construction uses a single tensor-core pass (bf16 input, fp32 accumulation). Power iterations run in registers, limiting key reads to twice per tree level.
  • kk-Means Stage: Keys (250250) and centroids (1717) remain on-chip per block. Tensor-core matrix products drive updates, converging bit-for-bit in 9.29.2 iterations on average (vs. 1515 max).
  • Hardware Utilization: Sustains 57%57\% of peak memory bandwidth overall (and up to 90%90\% in the projection kernel) while moving 12.4 GB12.4\text{ GB}/layer.

End-to-End Latency & Context Scaling Each 4×4\times increase in sequence length adds only one tree level, maintaining linear scaling across 36 layers:

  • 128K tokens: 1.06 s1.06\text{ s}
  • 512K tokens: 4.67 s4.67\text{ s}
  • 1M tokens: 9.60 s9.60\text{ s}
  • Q3. Yes

Additional Comparison with Recent Work

We have run benchmarks to compare with ParisKV on a matched budget at 128K for Qwen3-14B. We will update the results as more become available. In summary, ParisKV achieves lower accuracy while incurring a significantly higher inference time (with the prefill overhead amortized over generated tokens). Specifically, for 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, s)

 Benchmark   Exact    MoG   MoG w/o APPROX   ParisKV  
NIAH0.600 / 50.30.800 / 51.40.400 / 53.00.600 / 66.8
NeedleBench0.883 / 50.30.900 / 51.70.817 / 51.50.950 / 67.2
NoLiMa0.400 / 44.50.420 / 45.10.400 / 45.10.400 / 58.6
BICS0.060 / 56.20.070 / 59.20.040 / 59.00.050 / 74.7
RepoQA0.430 / 50.90.374 / 52.20.276 / 52.30.283 / 67.9
MultiHop‑RAG0.811 /  43.00.808 / 42.00.818 / 41.80.804 / 53.0
LoCoMo0.425 / 38.70.411 / 49.90.412 / 50.00.394 / 64.7

(Hardware: 4× NVIDIA RTX A5000 for NIAH, NeedleBench, NoLiMa, BICS, RepoQA and 4× NVIDIA RTX A6000 for MultiHop, LoCoMo)

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:

MethodAccuracyMean request time
Dense92.5%13.68 s
MoG92.0%15.55 s
ParisKV (GPU-resident)91.0%18.12 s

Note: Since the initial submission, we made a minor refinement (handling attention sinks), which resulted in slight improvements in the benchmark scores shared above.

Dear Reviewers,

As we are approaching the end of reviewer-author discussions, please go through authors' responses and raise questions that you would like authors to reply.

Thanks,

AC

I appreciate the authors' rebuttal. The addition explanation and new experiments help to clarify the design and the advantage of the approaches. However, I am still not convinced by the motivation of the design, i.e., why mixture of gaussian is intuitively a better design than the others. The additional pariskv baseline helps but overall the number of baselines is still insufficient.

I decided to increase my overall rate to 2, despite my honest rate would be between 1 and 2.

Thank you for your response and revised score.

To clarify the intuition, the general idea is to approximate the clusters ignored by the top cluster selection mechanisms (e.g., ParisKV or Tactic). One baseline approach would be to use each cluster's centroid as a single pseudo-token (as in RetroInfer); however, this reduces the representation to a simple mean and ignores the underlying cluster structure. Our goal is to provide a finer approximation that captures this structure as well.

To achieve this, we leverage two observations:

  1. The standard attention formula (a sum of exponentials) shares a mathematical structure with the moment-generating function (MGF) of a Gaussian (an integral of exponentials), where the sum converges to the integral as the number of tokens increases.
  2. Keys within a cluster are naturally well-represented as a mixture of Gaussians.

Putting these two together, the attention sum over a cluster of tokens maps to the MGF, which carries per-dimension variance alongside the mean. As a result, we use the MGF to accurately approximate the contribution of ignored clusters.

We hope this clarification is helpful.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.