acceptodds
Under review as a conference paper at ICLR 2027

Double-P: Hierarchical Top-P Sparse Attention for Long-Context LLMs

Abstract

Attention over a growing key-value (KV) cache dominates the cost of long-context decoding. Top- sparse attention keeps the smallest set of tokens whose attention mass reaches a target , so the budget adapts to each head and decoding step. Existing top- methods, however, use top- only to prune: a fixed-budget selector first proposes candidate tokens, and token-level score estimation then removes some of them. Such pipelines cannot recover attention mass that the candidate set misses, and their estimation cost grows with context length. We present Double-P, which uses top- to select. Double-P estimates the attention mass of every KV cluster from size-weighted centroids and applies top- over the entire context, so the attended set is sized by the attention distribution rather than by a budget. A second top- threshold on the same estimates allocates precision: high-mass clusters receive exact token-level attention, and the remaining selected clusters are approximated by their centroids instead of being discarded. Across long-context benchmarks, Double-P consistently achieves near-zero accuracy drop, reducing attention computation overhead by up to 1.8 and delivers up to 1.3 end-to-end decoding speedup over state-of-the-art fixed-budget sparse attention methods.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
sparse attention, long context, LLM

Reviews

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

Double-P is a sparse attention design for long-context LLMs, which uses top-p twice for both selecting and pruning, in contrast to just once in previous work only for pruning. More specifically, Double-P is built upon cluster-based sparse methods, and first identifies the top-p clusters by estimating attention masses between the query and each KV cluster. Then it further applies another top-p on the selected clusters to split them into an exact subset and an approximate subset only using the cluster centroids. Double-P is shown to outperform the baseline that directly uses top-p on top of a cluster-based method.

Critical strengths
  • The key idea of using top-p also for selecting on top of cluster-based methods is promising.
  • The paper has compared with SOTA baselines including traditional top-p and cluster + top-p.
  • Writing is easy to follow.
Critical weaknesses
  • The performance of the proposed design and the baselines would heavily depend on the parameter p, so it would be more convincing to show the overall accuracy-speedup tradeoff curves.
  • It is unclear whether the double top-p construction can be used beyond cluster-based methods.
Questions for authors
  1. The main baseline to compare with is RetroInfer+Twilight. The results show that Double-P has similar accuracy with RetroInfer+Twilight but higher speedup. From Fig 9 the speedup is mainly from the final attention stage, in which Double-P uses the centroids to approximate some attentions while RetroInfer+Twilight would use accurate attention for this part. But how large this part is would depend on the setting of parameter p. Double-P approximates this (1−p2)p1(1-p_2)p_1 region. If RetroInfer+Twilight uses a smaller p, would its performance be better while not sacrificing the accuracy?

  2. Continuing on the question of 1, the choices of parameter p would highly affect the accuracy and speedup of both the baselines and the proposed design. Could you show the accuracy-speedup tradeoff curves (i.e., using accuracy and speedup for the x and y axes, and plot points with different p values for each design as a curve) for them? Double-P and RetroInfer+Twilight would be necessary to include. It would be good if other baselines can also be shown.

  3. If I understand correctly, the key reason that top-p can be used also for selecting in Double-P is that the cluster-based methods provides the unit of clusters as a cheap way to estimate attention scores. While recent works as RetroInfer and ClusterKV show this paradigm is promising, most sparse attention designs are not based on clustering. Can the idea of double top-p be generalized beyond cluster-based methods? For example, can it be built on Quest?

  4. The results in Table 3 miss the most important baseline RetroInfer+Twilight. Can you add it?

3 comments

We thank the reviewer for recognizing the promise of applying top-p to cluster selection, our comparisons with state-of-the-art baselines, and the clarity of our writing. We also appreciate the constructive suggestions and thoughtful concerns, which has helped us clarify and strengthen our work. We address the reviewer’s concerns point by point below.

W1 / Q1 — Can a smaller RetroInfer+Twilight threshold close the gap?

Lowering RetroInfer+Twilight’s pruning threshold does not close the measured latency gap. It reduces the final attention workload, but the same 25% candidate-cluster budget must still be retrieved and scored before pruning. This cost remains even when very few tokens survive.

At 32K, we evaluate across all 13 RULER tasks:

PRULER scoreExact tokens per state
0.7589.022177.2
0.9091.089509.4
0.9590.7081,000.4

We separate candidate retrieval/scoring, token pruning, and final attention in the performance comparison below.

PCandidate retrieval + scoringTop-p pruningGather + attention
0.758.8628.4481.648
0.908.8618.4521.921
0.958.8578.4472.067

Reducing P from 0.95 to 0.75 saves only 0.419 ms/token in gather + attention, while candidate retrieval/scoring and pruning still cost approximately 17.3 ms/token. The corresponding accuracy evaluation also shows a 1.686-point loss. The experiment supports applying top-p during group selection: reducing token work before retrieval and scoring addresses an overhead that a lower post-retrieval pruning threshold leaves in place.

W1 / Q2 — Accuracy–speedup curves over threshold settings

Several Double-P settings match full attention’s observed accuracy while reducing decode latency. We have completed the 32K threshold study with 100 inputs per task across all 13 RULER tasks, using the same accuracy cohort at every Double-P point and for full attention.

Threshold settings and latency at 32K.

Method / settingRULERPrefill, sDecode, ms/tokenEnd-to-end, sDecode speedup
Full attention90.9282.41222.1185.2201.000×
Double-P (0.90, 0.70)91.0692.47417.1364.6521.291×
Double-P (0.95, 0.50)90.1092.48017.0474.6501.297×
Double-P (0.95, 0.70) — default91.1622.48219.4214.9501.139×
Double-P (0.95, 0.90)91.5402.47718.2494.7961.212×
Double-P (0.95, 1.00) — all exact91.0512.47519.6184.9681.127×
Double-P (0.99, 0.70)91.4492.47517.3464.6761.275×
RetroInfer+Twilight, P=0.7589.0222.46935.8067.0120.618×
RetroInfer+Twilight, P=0.9091.0892.47435.7287.0120.619×
RetroInfer+Twilight, P=0.9590.7082.48235.4616.9860.624×

Five of the six Double-P settings have observed RULER scores above the full-attention reference and decode speedups of 1.13–1.29×. More aggressive approximation has a measurable quality cost: reducing p2 from 0.70 to 0.50 at p1=0.95 lowers the score from 91.162 to 90.109. The sweep supports the two thresholds as practical controls for the accuracy–compute tradeoff.

W2 / Q3 — Can the construction extend beyond clustering, for example to Quest?

The page experiment demonstrates that Double-P’s two-threshold construction extends beyond clustering. We apply it to 16-token contiguous pages: the first threshold selects pages using estimated attention mass, and the second divides selected pages between exact-token attention and value-summary contributions. This uses Quest’s page organization with our mass estimator in place of its original page-bound ranking.

The table compares results at 32K on Llama-3.1-8B-Instruct. Full attention and both Double-P variants use the same 100 inputs per task across all 13 RULER tasks.

MethodRULER scoreDecode ms/tokenEnd-to-end s
Full attention90.92822.1185.220
Quest85.95017.4944.545
Quest+Twilight86.50038.2727.220
Double-P on Quest-style pages89.73217.5204.590
Clustering-based Double-P91.16219.4214.950

The page extension reaches 89.732, compared with the paper’s Quest score of 85.950 and Quest+Twilight score of 86.500. Its 17.520 ms/token decode latency gives a 1.26× speedup over full attention. These results establish a working page-based extension with strong accuracy and lower decode cost than full attention.

Clustering remains the more accurate grouping choice in this comparison, improving the score by 1.430 points on the same inputs. Similar keys yield more representative group summaries and better attention-mass estimates than contiguous pages.

Q4 — Add RetroInfer+Twilight to Table 3

We have evaluated the missing accuracy evaluations for RetroInfer+Twilight, and will add these results to Table 3.

Adding RetroInfer+Twilight preserves our main conclusion: Double-P remains on par with the strongest sparse baselines in accuracy while providing lower decode latency. The added Qwen3-8B RULER result is close to Double-P’s reported number in Table 3. On Llama-3.1-8B LongBench, Double-P scores 39.06, compared with 38.590 for RetroInfer+Twilight.

In the 32K timing comparison in Q2, Double-P takes 19.421 ms/token versus 35.461 ms/token for RetroInfer+Twilight at P=0.95—a 1.83× decode speedup. Together, the accuracy results and latency measurements support the benefit of selecting by top-p at the group level, which avoids the token-level candidate scoring and pruning overhead discussed in Q1.

ModelMethodRULER 16KRULER 32KRULER 64KRULER meanLongBench
Qwen3-8BRetroInfer+Twilight91.9590.7079.1987.2833.40
Qwen3-8BDouble-P91.0290.3679.2686.8835.78
Llama-3.1-8BRetroInfer+Twilight92.8389.9585.2189.3338.59
Llama-3.1-8BDouble-P92.8790.3184.5589.2439.06

Thanks for the new experimental results added. I appreciate the authors' efforts for the rebuttal. Most of the results match the expectation. One remaining issue is that the work is heavily based on RetroInfer, making its contributions a bit limited. So I would like to keep the original score, as weak accept.

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

This paper introduces Double-P, a method for making LLMs generate text faster when handling long contexts. The main idea is to adjust how much attention computation is needed at each generation step, instead of always selecting a fixed number of past tokens. Double-P groups similar cached keys into clusters and uses their summaries to estimate how much attention each cluster should receive. It then applies two thresholds: the first selects which clusters to include, and the second decides which selected clusters need exact attention. The remaining selected clusters contribute through their summaries, reducing computation while preserving some of their information. Experiments on Llama and Qwen models show small average accuracy drops compared with full attention. Timing results on Llama also show faster decoding than the evaluated baselines.

Critical strengths
  • The motivation is clear and well supported. The argument that “select then prune” can never recover mass the selector missed is simple but convincing, and the paper backs each of its three observations with its own measurements rather than just asserting them.
  • The method itself is easy to understand and cheap to run. There is no new data structure, no quantized key copy, and both thresholds come from one sorted pass over cluster scores.
  • The comparison with RetroInfer+Twilight is a good experiment. The two methods share the same index and the same goal, and differ only in where top-p is applied, so it isolates the paper’s main claim.
Critical weaknesses
  • The paper discusses Tactic, which also uses clustering and an adaptive attention target, but does not compare against it. Since Double-P builds on several components from RetroInfer, this comparison would help clarify what the new design adds.
  • The headline speedup needs clearer qualification. Appendix B explains that the end-to-end latency of RetroInfer+Twilight is reconstructed by subtracting Double-P’s attention time from its total latency and adding the measured attention time of RetroInfer+Twilight. Therefore, the reported 2.3× speedup is based on an estimated end-to-end latency rather than a direct measurement of the complete optimized baseline.
  • The paper never checks whether the estimated mass matches the real mass. The estimator treats every token in a cluster as if it had the centroid logit, which underestimates the true mass (Jensen’s inequality), and the error depends on how spread out the cluster is. The paper plots actual retained mass for Quest in Figure 3 but never plots it for Double-P. That plot would directly test the central claim and I think it should be in the paper.
  • In Table 5, the fixed policy computes 7.2% of selected clusters exactly, while the adaptive policy’s average fraction is not reported. Double-P might perform better partly because it does more exact computation. Comparing the policies at the same average computation cost would make the conclusion stronger.
  • Appendix C assigns 32 KiB per token to a 4-bit copy of the keys, although the stated BF16 KV-cache size appears to imply 16 KiB before metadata. This should be explained because it affects the memory comparison with Twilight.
Questions for authors
  1. How does Double-P compare against Tactic in accuracy and latency, given that both use clustering with an adaptive attention-mass target?

  2. Can you measure RetroInfer+Twilight's end-to-end latency directly with optimized kernels, rather than reconstructing it, so the 2.3× speedup reflects an actual measurement?

  3. Can you report the attention mass Double-P actually retains versus the target p1 (as in Figure 3 for Quest), since the centroid estimator underestimates true cluster mass?

  4. What fraction of Stage-1 clusters does the adaptive Stage-2 policy compute exactly on average in Table 5, and does its advantage over the fixed policy hold at matched exact computation?

  5. How is 32 KiB/token obtained for Twilight's 4-bit key copy when the stated BF16 KV cache implies 16 KiB for the keys?

2 comments

We thank the reviewer for recognizing our well-supported motivation, the simplicity and low overhead of our method, and the controlled comparison with RetroInfer+Twilight that isolates our main contribution. We also appreciate the constructive suggestions and thoughtful concerns, which has helped us clarify and strengthen our work. We address the reviewer’s concerns point by point below.

W1 / Q1 — Comparison with Tactic

We agree and will add Tactic to the baseline comparison. The distinction is how the attended set and its precision are determined. Tactic uses centroid scores to order tokens, then estimates a token-score distribution using sampled token logits and a fitted curve to choose its token budget. Double-P uses size-weighted centroid masses directly for both boundaries: the first selects clusters globally, and the second divides the selected clusters into exact-token and centroid-approximated contributions. Both contributions share the attention normalizer. In particular, Double-P's second threshold reuses the same estimated cluster masses; it does not require an exact-token prefix-mass calculation.

To reproduce the latency results of Tactic, we use the head-as-subrequest FlashInfer organization discussed in Tactic §4.6. We evaluated three Tactic thresholds and report accuracy and performance together for each context length below, with 128 output tokens. Double-P's observed RULER scores matches evaluated Tactic settings. For decode latency, Double-P achieves 1.32–1.37× at 16K, 1.50–1.54× at 32K, 1.35–1.40× at 64K acceleration comparing to Tactic.

16K context

MethodRULER scoreDecode B=1, ms/tokenEnd-to-end B=1, s
Double-P94.00920.7893.601
Tactic, P=0.7593.99428.3814.572
Tactic, P=0.9094.09928.2254.559
Tactic, P=0.9594.36727.4614.458

32K context

MethodRULER scoreDecode B=1, ms/tokenEnd-to-end B=1, s
Double-P91.16219.4214.950
Tactic, P=0.7590.75329.9956.312
Tactic, P=0.9091.23229.1026.194
Tactic, P=0.9591.52329.3516.218

64K context

MethodRULER scoreDecode B=1, ms/tokenEnd-to-end B=1, s
Double-P85.23520.3279.811
Tactic, P=0.7585.38527.72210.742
Tactic, P=0.9085.91827.49010.717
Tactic, P=0.9586.01828.40410.824

W2 / Q2 — Direct timing of an optimized RetroInfer+Twilight baseline

We evaluate RetroInfer + Twilight at different context length with 128 output tokens, and compare with our Double-P. The implementation performs candidate retrieval, packed INT4 key scoring, token pruning, and final BF16 attention, all with optimized gpu kernels.

We observe similar decode acceleration with direct whole-model timing: Double-P is 1.66×, 1.83×, and 2.26× faster than RetroInfer+Twilight at 16K, 32K, and 64K, respectively. The directly measured 2.26× speedup at 64K is close to the paper’s reported 2.3×. These measurements time the complete integrated baseline, including candidate retrieval, token scoring, pruning, attention, and the rest of the model.

Latency by context length.

ContextMethodPrefill, sDecode, ms/tokenEnd-to-end, s
16KDouble-P0.95920.7893.601
16KRetroInfer+Twilight0.95834.5385.342
32KDouble-P2.48219.4214.950
32KRetroInfer+Twilight2.48235.4616.986
64KDouble-P7.23020.3279.811
64KRetroInfer+Twilight7.20946.02213.054

W3 / Q3 — Achieved attention-mass coverage

Double-P’s Stage-1 selection achieves approximately 95% true attention-mass coverage on average, closely matching the intended p1=0.95 target. We verified this by recomputing exact token-level full-attention weights at captured decode states across all 13 RULER tasks.

Mean true attention-mass coverage.

ContextMean Stage-1 coverageMean coverage including sink + sliding tokens
16K94.926%99.278%
32K95.125%99.221%
64K95.391%99.057%

The measured means range from 94.926% to 95.391%, all within 0.4 percentage points of 95%. Thus, over the evaluated decode states, the target set using centroid estimates translates into approximately 95% coverage of the true token-level attention mass on average. Including sink + sliding tokens raises mean total coverage above 99% at every tested context length.

W4 / Q4 — Adaptive Double-P versus fixed-budget RetroInfer

To isolate the budget policy, we compare adaptive Double-P with fixed RetroInfer budgets in a shared implementation with the same corrected centroid scorer and attention kernels. RetroInfer selects a fixed fraction of all clusters for exact attention and another fixed fraction for centroid approximation. RetroInfer’s default configuration uses 1.8% exact and 23.2% approximated clusters. To address the reviewer’s concern about unequal exact computation, we also evaluate a fixed-budget version whose exact fraction is calibrated on disjoint inputs to match Double-P’s exact-token work; its total selected-cluster budget remains 25%.

For Double-P at 32K, the mean fraction of Stage-1-selected clusters computed exactly is 17.589%. This corresponds to 2,647.5 exact clustered tokens per state, approximately 8.1% of the nominal 32K context. The cluster fraction and token fraction have different denominators; sink + sliding tokens are excluded from this token count.

MethodExact / all clustersApproximated / all clustersExact clustered tokens / stateRULER score
Adaptive Double-PAdaptiveAdaptive2,647.591.162
RetroInfer1.8%23.2%675.489.213
RetroInfer, matched exact work7.7%17.3%2,727.290.596
MethodExact-budget settingDecode, ms/token
Double-PAdaptive19.421
RetroInfer1.8%21.592
RetroInfer7.7%22.026

These results show that adaptive Double-P achieves both higher accuracy and lower decoding latency than either fixed-budget configuration. Compared with default RetroInfer, Double-P improves the RULER score by 1.949 points while reducing latency by 10.1%. Even when RetroInfer’s exact computation is approximately matched—and slightly exceeds Double-P’s measured exact-token work—Double-P retains a 0.566-point accuracy advantage and 11.8% lower latency. Thus adapting the allocation of exact and approximated attention provides a better accuracy–latency than the evaluated fixed-budget policies.

W5 / Q5 — Correcting the INT4 key-copy memory calculation

Thank you for pointing out this error. Our calculation incorrectly counted both keys and values for Twilight’s additional INT4 copy, although only keys are stored. For Llama-3.1-8B (32 layers, 8 KV heads, head dimension 128), the corrected accounting is:

Storage componentKiB per tokenAdditional overhead relative to BF16 K+V
BF16 K+V cache, reference1280%
Packed INT4 key copy1612.50%
FP16 scale + FP16 offset10.78%
Total additional key copy + metadata1713.28%

The metadata assumes one FP16 scale and one FP16 offset per token per KV head in each layer. Thus, Twilight’s additional key copy costs 17 KiB/token, or 13.28125% of the BF16 KV cache.

Per-token memory footprint across the five methods. All storage columns are KiB/token, summed over all 32 layers of Llama-3.1-8B, under the same analytical accounting as Appendix C.

MethodBF16 KVIndex + workspacesINT4 keys + metadataTotal footprintOverhead vs. full attention
Full attention128.00.00.0128.00.0%
RetroInfer128.012.60.0140.6+9.8%
Double-P128.012.60.0140.6+9.8%
Twilight128.00.017.0≥ 145.0≥ +13.3%
RetroInfer+Twilight128.012.617.0≥ 157.6≥ +23.1%

We will correct Appendix C, the affected tables, and the related claims in the revised paper.

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

The KV cache has become a major bottleneck for modern LLMs. Existing top-P selection methods are based on Quest pre-selection, incur extra memory overhead, and can miss tokens in the first round of selection. Instead, Double-P performs clustering at prefill time and first selects the top-P clusters. It then examines those selected clusters and uses exact prefix attention mass to refine a second top-P selection. It only performs full attention for tokens that pass both selections and uses centroid attention for tokens that pass the first top-P selection. Evaluations demonstrate good accuracy with considerable speedup.

Critical strengths
  • The second pass of top P is novel and can indeed save attention compute
  • The flow of the paper is very clear and easy to follow
Critical weaknesses
  • The paper does not compare to Tactic in the main sections despite it being the most relevant related work.
Questions for authors

Thanks for submitting the paper. The analysis and the second top P selection is interesting. However, I have the following concerns.

  1. Tactic should be mentioned much earlier. It uses the same clustering-based estimation. The authors hide this in the related work, while the main discussion in the paper uses Twilight, which is less similar. Given that you do the clustering anyway, comparing against Tactic or its variants should not be a hard task. Indeed, clustering, Q*centroid, sorting by cluster score, and cluster pruning are exactly the same as in Tactic; even the prefix xijx_{ij} computation is identical to Tactic's. The difference is that this paper applies top-P again to reduce computation for those top-P clusters. I would suggest discussing Tactic much earlier in the paper.
  2. In the ablation study, “Computing every Stage-1 cluster exactly raises the mean by only 0.19 points while requiring about 5× more exact-cluster computation.” How about applying top-P just once using your p1*p2? That is much simpler; do you see a significant accuracy loss? Additionally, does the 5× increase in exact computation change the end-to-end decoding latency enough to require a second top-P pass?
  3. While the paper claims top-P selection, do the selected tokens actually achieve the target P value in the evaluation? The overall attention mass seems to be estimated only from cluster centroids, which can deviate significantly from the exact sum of token attention masses.
1 comment

We thank the reviewer for recognizing the novelty of our second-stage top-p selection and its potential to reduce attention computation, as well as the clarity of our presentation. We also appreciate the constructive suggestions and thoughtful concerns, which has helped us clarify and strengthen our work. We address the reviewer’s concerns point by point below.

W1 / Q1 — Comparison with Tactic

We agree and will move the Tactic discussion much earlier and add it to the baseline comparison. The distinction is how the attended set and its precision are determined. Tactic uses centroid scores to order tokens, then estimates a token-score distribution using sampled token logits and a fitted curve to choose its token budget. Double-P uses size-weighted centroid masses directly for both boundaries: the first selects clusters globally, and the second divides the selected clusters into exact-token and centroid-approximated contributions. Both contributions share the attention normalizer. In particular, Double-P's second threshold reuses the same estimated cluster masses; it does not require an exact-token prefix-mass calculation.

To reproduce the latency results of Tactic, we use the head-as-subrequest FlashInfer organization discussed in Tactic §4.6. We evaluated three Tactic thresholds and report accuracy and performance together for each context length below, with 128 output tokens. Double-P's observed RULER scores matches evaluated Tactic settings. For decode latency, Double-P achieves 1.32–1.37× at 16K, 1.50–1.54× at 32K, 1.35–1.40× at 64K acceleration comparing to Tactic.

16K context

MethodRULER scoreDecode B=1, ms/tokenEnd-to-end B=1, s
Double-P94.00920.7893.601
Tactic, P=0.7593.99428.3814.572
Tactic, P=0.9094.09928.2254.559
Tactic, P=0.9594.36727.4614.458

32K context

MethodRULER scoreDecode B=1, ms/tokenEnd-to-end B=1, s
Double-P91.16219.4214.950
Tactic, P=0.7590.75329.9956.312
Tactic, P=0.9091.23229.1026.194
Tactic, P=0.9591.52329.3516.218

64K context

MethodRULER scoreDecode B=1, ms/tokenEnd-to-end B=1, s
Double-P85.23520.3279.811
Tactic, P=0.7585.38527.72210.742
Tactic, P=0.9085.91827.49010.717
Tactic, P=0.9586.01828.40410.824

Q2 — A single threshold p1×p2, and the actual latency benefit of Stage 2

Stage-2 Ablation.

PolicyRULER scoreExact attended clustered tokensDecode B=1, ms/tokenDecode B=4, ms/step
Double-P, p1=0.95, p2=0.7091.1622,647.519.42122.229
Single threshold, p=0.66590.5452,862.417.20721.819
All Stage-1 clusters exact, p1=0.9591.05112,675.519.61829.954

Our 32K ablation shows the tradeoff: collapsing the two thresholds into a single p=0.665 loses accuracy, while computing every cluster selected by p1=0.95 exactly increases batch-4 decode latency by 35%. Double-P retains intermediate-mass clusters through centroid summaries, achieving similar observed accuracy to the all-exact policy with substantially less exact attention work.

The single-threshold policy lowers RULER accuracy. It discards the intermediate-mass clusters that Double-P preserves through centroid contributions. The all-exact policy achieves similar observed accuracy but attends exactly to 4.79× as many clustered tokens. At batch 4, its decode latency rises from 22.229 to 29.954 ms/step: 35% higher latency, giving Double-P a 1.35× speedup.

Q3 — Does p1=95% select clusters containing 95% of the true attention mass?

Double-P’s Stage-1 selection achieves approximately 95% true attention-mass coverage on average, closely matching the intended p1=0.95 target. We verified this by recomputing exact token-level full-attention weights at captured decode states across all 13 RULER tasks.

Mean true attention-mass coverage.

ContextMean Stage-1 coverageMean coverage including sink + sliding tokens
16K94.926%99.278%
32K95.125%99.221%
64K95.391%99.057%

The measured means range from 94.926% to 95.391%, all within 0.4 percentage points of 95%. Thus, over the evaluated decode states, the target set using centroid estimates translates into approximately 95% coverage of the true token-level attention mass on average. Including sink + sliding tokens raises mean total coverage above 99% at every tested context length.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the rebuttal (for the AC and all reviewers)

We thank the reviewers for their constructive feedback. Below is an overview of the new experiments, clarifications, and corrections provided in our rebuttal. We will incorporate these results and the corresponding discussion into the revised manuscript.

  1. Comparison with Tactic (R77P Q1, fFcZ Q1). We evaluated Tactic at three thresholds across 16K, 32K, and 64K contexts. Double-P achieves comparable observed RULER accuracy with 1.32–1.54× faster decoding across the evaluated settings. We also clarified the methodological distinction: Double-P reuses the same estimated cluster masses for both selection and precision allocation, without requiring sampled token logits, distribution fitting, or an exact-token prefix-mass calculation. We will move the Tactic discussion earlier in the paper.

  2. Direct measurement of RetroInfer+Twilight (fFcZ Q2). We directly timed the complete integrated baseline with optimized GPU kernels for candidate retrieval, INT4 key scoring, pruning, and BF16 attention. Double-P achieves 1.66×, 1.83×, and 2.26× decode speedups at 16K, 32K, and 64K, respectively. Including prefill and 128 output tokens, the corresponding end-to-end speedups are 1.48×, 1.41×, and 1.33×. These measurements replace reliance on reconstructed baseline latency and distinguish decoding gains from total execution gains.

  3. Validation of actual attention-mass coverage (R77P Q3, fFcZ Q3). We recomputed exact full-attention weights at captured decoding states across all 13 RULER tasks. With p1=0.95p_1=0.95, mean Stage-1 coverage is 94.926%, 95.125%, and 95.391% at 16K, 32K, and 64K—within 0.4 percentage points of the target. Including sink and sliding-window tokens raises mean total coverage above 99% at every tested length. These results validate the estimator’s achieved coverage on average.

  4. Why two thresholds are useful (R77P Q2). At 32K, replacing the two stages with a single threshold p=p1p2=0.665p=p_1p_2=0.665 reduces latency but lowers RULER accuracy from 91.162 to 90.545. Computing all Stage-1 clusters exactly yields similar observed accuracy while requiring 4.79× more exact clustered-token computation and increasing batch-4 decode latency by 35%. Preserving intermediate-mass clusters through centroid contributions therefore provides a useful accuracy–latency tradeoff.

  5. Adaptive allocation at matched exact computation (fFcZ Q4). We report that Double-P computes 17.589% of Stage-1-selected clusters exactly at 32K. Using shared scoring and attention kernels, we compare against a fixed RetroInfer budget calibrated on disjoint inputs to approximately match exact-token work. Double-P processes 2,647.5 exact clustered tokens per state versus 2,727.2 for the matched baseline, while achieving 0.566 points higher RULER accuracy and 11.8% lower decode latency.

  6. Threshold sensitivity and the cost of post-selection pruning (AEaa Q1–Q2). We evaluated six Double-P settings and three RetroInfer+Twilight thresholds at 32K. Five Double-P settings achieve observed RULER scores above the full-attention reference with 1.13–1.29× decode speedups. Lowering RetroInfer+Twilight’s threshold from 0.95 to 0.75 saves only 0.419 ms/token in final gather and attention, while retrieval, scoring, and pruning still cost approximately 17.3 ms/token and accuracy decreases by 1.686 points.

  7. Extension beyond clustering (AEaa Q3). We implemented the two-threshold construction over 16-token contiguous pages, using Quest-style grouping with our mass estimator. At 32K, this extension achieves 89.732 RULER accuracy and 1.26× faster decoding than full attention. Clustering-based Double-P remains more accurate at 91.162, demonstrating both the construction’s applicability beyond clustering and the benefit of grouping similar keys.

  8. Additional RetroInfer+Twilight accuracy results (AEaa Q4). We completed the missing RULER and LongBench evaluations for Qwen3-8B and Llama-3.1-8B. The results show comparable aggregate RULER accuracy. Double-P obtains higher LongBench scores: 35.78 versus 33.40 on Qwen3-8B and 39.06 versus 38.59 on Llama-3.1-8B. We will add these results to Table 3.

  9. Correction of memory accounting (fFcZ Q5). We corrected Twilight’s additional INT4 storage to count keys only: 16 KiB/token, plus 1 KiB/token of scale and offset metadata. Under the stated accounting, the additional overhead is 9.8% for Double-P, at least 13.3% for Twilight, and at least 23.1% for RetroInfer+Twilight. We will update Appendix C, the affected tables, and the related claims.

We thank the reviewers and chairs again for their time and thoughtful feedback, and we are happy to address any remaining questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.