acceptodds
Under review as a conference paper at ICLR 2027

RBS-ATTENTION: Radius-Bounded Sparse Prefill for Long-Context Large Language Models

Abstract

Long-context large language model inference is increasingly limited by prefill, where dense self-attention processes the entire prompt before generation begins. Sparse block selection reduces this cost, but a block centroid may hide a highly relevant token among many irrelevant ones. We call this failure mode mean dilution and propose RBS-Attention, a training-free sparse-prefill method with two complementary branches. A centroid base branch captures average relevance, while a rescue branch uses the maximum key-block radius and its prompt-, layer-, and head-dependent distribution to identify blocks at risk of underestimation. Independent thresholds and a mask union focus rescue on dispersed blocks while preserving block-sparse FlashAttention execution. On H100 GPUs, RBS-Attention achieves standalone prefill-attention speedup and end-to-end time-to-first-token speedup at 128K on Qwen3-30B-A3B-Instruct-2507-FP8. On Qwen3-32B, it obtains 88.65 overall RULER accuracy versus 89.52 for dense attention; LongBench-v2, InfiniteBench, and Video-MME provide additional quality evaluation. Matched-density and selector studies further support radius-adaptive rescue as an effective approach to long-context prefill.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Sparse Attention, Long-Context LLM Inference, Prefill Acceleration, Adaptive Block Selection, Training-Free Inference

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_gJTeOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

RBS-Attention is a sparse prefill design that adds a rescue path besides the traditional critique based only on the relevance between the query and the centroid of KV clusters. The rescue path additionally includes a term depending on the radius of the KV cluster, implying that a more diversified cluster may contain a relevant KV even when the centroid seems irrelevant. This term is further weighted by the position of the cluster radius in the overall radius distribution.

Critical strengths
  • A simple and effective extension to sparse prefill method.
  • The evaluation includes SOTA designs and shows high speedups and slightly better accuracy.
Critical weaknesses
  • The key idea is relatively incremental. Also, it may be overly simplified to cover the claimed mean dilution issue, which is a critical limitation. Specifically, by only capturing the radius magnitude in the equation, the rescue path does not consider the direction of the diversification. For a token that is diversified from its cluster mean and goes in the same direction as the query, and another token that goes in the opposite direction, the proposed method would treat them the same, though the second one should not be included.
  • For the results, the accuracy results are evaluated at different sparsity levels, but the speedups are presented without specifying the clear accuracy/sparse conditions. The accuracy and speedup results need to be shown in a better and combined way to understand the tradeoffs.
  • The ablation study vs. the centroid-only baseline needs to be better explained.
Questions for authors
  1. As explained in the weakness part, a critical concern of the proposed method is that it only considers the magnitude of the radius but not the direction of the diversified token. How can your design distinguish the two tokens that both diversify from the centroid but go in opposite directions compared to the query?

  2. What is the accuracy level of Fig 2? Do all the designs achieve the same accuracy at the shown speedups? The speedups are significant, e.g., 2x over the best baseline, in this figure. This speedup should mainly come from the saved KVs, i.e., more sparsity at the same accuracy. But the later tables about the accuracy show that the accuracy gain is slight at each same sparsity level. The two types of results therefore do not come together in a clear way. Please better explain this accuracy vs. speedup tradeoff.

  3. Please add more explanation and analysis against the centroid-only baseline in the ablation study. Table 7 shows only brief results. A more clear comparison should be, when achieving the same accuracy, how many KVs does each method need to include (sparsity), and the corresponding speedups.

  4. In Fig 1(b), RBS improves Q4 and Q5, but it also worsens Q1, Q2, and Q3. What counter-measurements are used to prevent this problem from degrading the performance of RBS?

1 comment

Thank you for highlighting directionality and the quality-cost comparison. Our new experiments connect the selection mechanism to retained information, answer quality, and measured system cost.

1. Centroid at comparable quality

We evaluated a quality-targeted centroid configuration and RBS on full RULER-128K using Qwen3-30B-A3B-Instruct-2507-FP8. Timing uses 2 A100s, TP=2, batch=1, and chunked prefill.

MethodAccuracy (%)Retained budget (%)TTFT (s)
Centroid78.5114.0477.585
RBS78.164.9503.273

The budget measures retained causal block pairs. At an accuracy difference of only 0.35 pp, RBS uses 35.2% of the centroid configuration's budget and is 2.32x faster end to end, including selection overhead. The extra selection work pays for itself through a substantially smaller retained-attention workload at comparable answer quality.

2. Directionality and the contribution

RBS separates average relevance from mean-dilution risk:

ℓbase=q⊤cb,ℓrescue=q⊤cb+∥q∥2rbβb.\ell_{\mathrm{base}}=q^\top c_b,\qquad \ell_{\mathrm{rescue}}=q^\top c_b+\|q\|_2r_b\beta_b.

The centroid term contains query direction; radius summarizes possible token-level deviations. Blocks with identical centroid/radius can tie despite different internal directions. Radius affects candidate selection only: selected tiles use the original Q/K/V and token-level softmax. A negatively aligned token receives no radius bonus in its actual attention logit.

The contribution is a radius-adaptive dual-path allocation policy. Independent centroid selection preserves ordinary relevance, while rescue gives dispersed blocks another opportunity to contribute. Distribution-adaptive βb\beta_b concentrates the radius correction on blocks with greater mean-dilution risk.

We tested the value of these opportunities on shared dense Q/K traces. Centroid extension and RBS rescue start from the same base/forced mask and add exactly the same number of blocks per query block:

MaskDensity (%)Retained dense mass (%)
Base only1.849175.1509
Base + centroid extension1.946275.7701
Base + RBS rescue1.946279.8069

Centroid extension adds 0.6192 pp of dense probability mass; RBS rescue adds 4.6560 pp. At the same additional budget, rescue recovers 4.0368 pp more actual attention mass. This directly validates the allocation mechanism, and the first table establishes its value in system cost.

3. Fig. 2 and quality-speed comparisons

Original Fig. 2 uses method-specific operating configurations, each normalized to Dense on the same H100 setup; quality and density vary across those configurations. Fixed-budget accuracy and comparable-quality latency examine different directions of the quality-budget relationship. A modest accuracy gap at one density can correspond to a substantial budget gap when targeting comparable quality. The centroid experiment above measures this relationship directly.

We also added a joint LongBench-v2 comparison on Qwen3-30B-A3B-Instruct-2507-FP8, one A100, TP=1. TTFT runs from vLLM engine entry to the first generated token. Same-GPU speedups use Dense as the reference; sparsity is the discarded proportion.

MethodAccuracy (%)Sparsity (%)Same-GPU speedup
Dense43.080.001.00x
FlashPrefill43.3181.992.31x
MInference43.0828.170.99x
XAttn43.3872.101.34x
FlexPrefill43.3857.171.34x
Quest-style42.5477.831.57x
SpargeAttention44.1520.011.10x
RBS43.8893.983.99x

RBS achieves 43.88% accuracy with 93.98% sparsity and the highest same-GPU speedup, 3.99x. Reporting these quantities together directly exhibits the quality-efficiency trade-off.

4. Protecting Q1-Q3

The independent base mask provides explicit protection:

Mfinal=Mbase∪Mrescue∪Mforced.M_{\mathrm{final}}=M_{\mathrm{base}}\cup M_{\mathrm{rescue}}\cup M_{\mathrm{forced}}.

Radius uplift can change the rescue branch's maximum and relative threshold, while the union preserves every block selected by the fixed base branch. Fig. 1(b) describes score-ranking changes; the final algorithm makes its decision through these independently selected masks.

The fixed-base diagnostic measures retained dense-attention mass within each radius quintile:

QuintileBase coverage (%)RBS coverage (%)Gain (pp)
Q172.1872.45+0.27
Q268.9469.83+0.89
Q364.1366.04+1.91
Q453.0557.98+4.93
Q585.0992.79+7.70

Coverage improves throughout Q1-Q3, with the largest gains in Q4/Q5. This demonstrates the intended division of labor: preserve ordinary relevance and recover more evidence in the mean-dilution regime.

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

This paper proposes RBS-Attention to reduce the high attention computational cost incurred during the prefill stage of long-context LLMs. The authors point out the “mean dilution” problem in existing centroid-based block selection, where some important tokens within a block may be diluted by the mean, potentially leading to the removal of that block. To address this, the authors calculate the centroid and maximum L2 radius for each key block and determine correction weights based on the radius distribution. The proposed method uses two branches.

  • Base Branch: Retains the existing centroid-based importance evaluation.
  • Rescue Branch: Adds a radius-based correction term to the centroid score to additionally select blocks that might be underestimated by the mean.

Both branches select blocks using independent relative thresholds, and the final mask consists of the union of the two results and the mandatory preservation blocks. Subsequently, Block-Sparse FlashAttention is performed only on the selected block pairs. This method can be applied without additional training and leverages the existing attention kernel. Experiments report a 20.65x standalone attention speedup and a 5.97x end-to-end TTFT speedup on a 128K context in an H100 environment. Additionally, accuracy was evaluated using RULER, LongBench-v2, InfiniteBench, and Video-MME, and the method demonstrated higher accuracy than existing sparse attention techniques in Matched-Density experiments.

Critical strengths
  1. This paper clearly identifies the “mean dilution” problem, in which information about important tokens is diluted by the mean in centroid-based block selection. Furthermore, by deriving an upper bound for the maximum QK logit within a block using the centroid and the maximum L2 radius, the paper provides a mathematical basis for radius-based scoring. Another advantage is that this approach is implemented as a training-free method that can be applied without any additional training.

  2. The paper reports end-to-end TTFT, not only FLOPs or standalone attention kernel speed. At 128K context, it reports 20.65x attention speedup and 5.97x end-to-end TTFT speedup. The authors further evaluate the method on RULER, LongBench-v2, InfiniteBench, and Video-MME across dense, MoE, and multimodal models. In particular, the Matched-Density experiments in Table 2 show that RBS achieves higher accuracy while maintaining a similar proportion of blocks actually computed. At matched density, the accuracy difference cannot be explained solely by the number of blocks retained.

Critical weaknesses
  1. The main methodological contribution is the combination of radius-adaptive score correction and an independently thresholded Base/Rescue mask union. However, the controlled selector experiment in Table 7 (expanded in Appendix C) compares only Centroid-only, Full-L2, Quest-style, and the complete RBS policy. As a result, it does not isolate the contribution of the two main components. In particular, two important ablations are missing: (1) adaptive radius scoring without the separate base-mask union, and (2) full-L2 scoring with a separately preserved base mask. Without these comparisons at matched actual density, it is difficult to determine whether the reported gain comes primarily from radius attenuation, from protecting the centroid-selected blocks through mask union, or from their interaction.

This issue is especially important because the selector-level evidence is not statistically conclusive. RBS improves over Centroid-only from 73.63 to 76.67 at approximately 5.34% actual density, but Appendix C states that the paired bootstrap confidence intervals for the differences between RBS and the comparators include zero. Thus, the current controlled experiment does not establish a statistically significant advantage of the proposed adaptive-union policy. A larger evaluation, ideally on the full RULER-128K set, would strengthen this claim.

  1. Several reported numbers also require clarification. First, the “Total” values in Table 3 do not appear to equal the sample-count-weighted average of the Short/Medium/Long scores. For example, using the stated LongBench-v2 category sizes of 180/215/108, the Qwen3-32B Dense score would be approximately 0.3995 rather than the reported 0.394, and XAttn would be approximately 0.3819 rather than 0.376. Please clarify the aggregation rule for the Total column and whether the category scores and total were computed over exactly the same evaluation set.

  2. Table 2 states that all measured densities are within 0.10 percentage point of their anchors, but XAttn has a density of 1.802% at the 2.03% anchor, a deviation of 0.228 percentage points. This appears inconsistent with the table caption and should be corrected or explained.

  3. RBS appears highly sensitive to block size. At approximately the same 5.34% density, its accuracy drops from 80.28% at B=128 to 71.86% at B=64 and 70.73% at B=256. Moreover, at both B=64 and B=256, RBS underperforms the centroid-only selector. This raises concerns about whether the benefit of radius-based rescue is robust across block granularities.

Questions for authors
  1. Can the authors isolate the respective contributions of radius adaptation and mask union? Please evaluate (i) adaptive radius scoring without a separate base-mask union and (ii) full-L2 scoring with a separately preserved base mask, under matched actual density. Since the paired bootstrap difference intervals in Appendix C include zero, it would also be helpful to repeat the comparison on a substantially larger evaluation set.

  2. How predictive is the rescue score of actual dense-attention mass? The geometric motivation bounds the maximum token-level QK logit within a block, whereas sparse-attention quality ultimately depends on the attention mass removed or retained. Please report the attention-mass distribution of blocks selected only by the rescue branch, or their precision/recall for high-attention-mass blocks. This would more directly validate whether radius-based rescue identifies blocks that matter to the dense attention computation.

  3. How does RBS compare with closely related heterogeneity-aware sparse-attention methods such as SpargeAttention? SpargeAttention also attempts to protect blocks whose summaries are unreliable, but no direct controlled comparison is provided. A matched-density comparison of accuracy and latency would help establish whether radius-adaptive rescue offers a meaningful advantage over prior approaches addressing a similar failure mode.

3 comments

Thank you for the suggestions on component attribution, attention mass, and reporting. We added full-RULER component controls and a same-base rescue experiment.

1. Component attribution and full-RULER evaluation

We expanded the comparison to full RULER-128K using Qwen3-30B-A3B-Instruct-2507-FP8, the same prefill backend, B=128, and approximately 5% retained budget.

SelectorAdaptive radiusBase unionAccuracy (%)
Centroid-only--74.49
Full-L2 onlyNoNo71.33
Adaptive-onlyYesNo70.49
Full-L2 + baseNoYes73.44
RBSYesYes78.16

The base path improves Full-L2 by 2.11 pp and adaptive scoring by 7.67 pp; RBS exceeds Full-L2 + base by 4.72 pp. Their combination is strongest: base protection preserves ordinary relevance while adaptive rescue targets dispersed blocks. These results extend the original 130-example diagnostic to full RULER. We will include paired bootstrap intervals recomputed from the full-set predictions.

This selection advantage also translates into practical cost savings. A quality-targeted centroid configuration reaches 78.51% accuracy at 14.047% retention, versus RBS's 78.16% at 4.950%. On 2 A100s, TP=2, batch=1 with chunked prefill, their TTFTs are 7.585 s and 3.273 s: RBS is 2.32x faster including selection overhead.

2. Rescue recovers actual dense-attention mass

On shared dense Q/K traces from 13 prompts, both extensions start from the identical base/forced mask and add the same number of blocks per query block. Their final density is 1.9462%.

MaskRetained dense mass (%)Added mass over base (pp)
Base only75.15090.0000
Base + centroid extension75.77010.6192
Base + RBS rescue79.80694.6560

Mass uses the common dense attention distribution normalized over all causal keys. Rescue adds 4.6560 pp of actual probability mass versus centroid's 0.6192 pp. Its 4.0368 pp advantage at the same additional block budget validates radius-adaptive allocation for recovering information hidden by mean dilution.

3. Block size and the recommended operating configuration

Block size changes token summaries, radii, query-block aggregation, and branch overlap. Matching total density controls the number of retained pairs; branch thresholds still determine which pairs survive. B should therefore be selected jointly with thresholds and budget.

The reported configuration performs best at B=128: 80.28% task accuracy versus centroid's 74.73%, a 5.55 pp gain. Additional trace diagnostics give:

Block size BDensity (%)Retained dense mass (%)
641.59178.32
1282.17281.01
2563.45480.20

At these measured densities, retained mass remains high, spanning only 2.69 pp. The B=64/256 task scores (71.86/70.73 versus centroid's 74.17/72.15) further motivate the validated B=128 default. The proposed joint configuration preserves useful information while delivering the strongest task result.

4. Direct comparison with SpargeAttention

We added the complete LongBench-v2 quality-efficiency comparison below. It uses the same Qwen3 model on one A100, TP=1. TTFT runs from vLLM engine entry to the first generated token. Same-GPU speedups are relative to Dense; sparsity is the discarded proportion.

MethodAccuracy (%)Sparsity (%)Same-GPU speedup
Dense43.080.001.00x
FlashPrefill43.3181.992.31x
MInference43.0828.170.99x
XAttn43.3872.101.34x
FlexPrefill43.3857.171.34x
Quest-style42.5477.831.57x
SpargeAttention44.1520.011.10x
RBS43.8893.983.99x

At these near-quality operating points, RBS is within 0.27 pp of Sparge's accuracy, with same-GPU speedups of 3.99x versus 1.10x. Sparge uses self-similarity gating and online softmax filtering; RBS uses continuous radius-adaptive rescue plus an independent base path. The comparison demonstrates a strong quality-efficiency operating point for this design.

5. Reporting corrections

We corrected the density caption and accompanying text: XAttn's 1.802% at the 2.03% anchor is explicitly identified as the 0.228 pp exception. All other listed points satisfy the stated 0.10 pp tolerance.

For the original LongBench-v2 grouped table, we will verify the sample-ID correspondence and regenerate grouped scores and Total from one evaluation record, reporting the aggregation rule and group counts together. The new full-RULER, controlled-mass, and quality-efficiency experiments provide direct evidence for the selection and system conclusions discussed above.

Thank you for the detailed response and additional experiments. While the rebuttal addresses some of my concerns, several experimental limitations remain, particularly regarding statistical significance, block-size sensitivity, and consistency of the reported results. Therefore, I have decided to maintain my original score.

Thank you for reviewing the additional experiments and specifying your remaining concerns. We would like to provide the full-RULER paired confidence intervals and clarify how the configuration and reporting questions relate to the evidence for RBS.

1. Statistical evidence on full RULER

The expanded evaluation uses full RULER-128K, Qwen3-30B-A3B-Instruct-2507-FP8, the same prefill backend, B=128, and approximately 5% retained budget. RBS achieves 78.16% accuracy. Below, gains and paired 95% confidence intervals are expressed as RBS minus the comparator, in percentage points.

ComparatorAccuracy (%)RBS gain (pp)Paired 95% CI (pp)
Centroid-only74.49+3.67[-1.74, 3.06]
Full-L2 only71.33+6.83[0.42, 7.15]
Adaptive-only70.49+7.67[1.67, 7.62]
Full-L2 + base73.44+4.72[-0.13, 3.54]

The paired intervals exclude zero against Full-L2 and Adaptive-only. These comparisons provide statistical support for the complete design over the unattenuated-bound-only policy and over adaptive scoring without independent base preservation. RBS also has higher point estimates than Centroid and Full-L2 + base. The strongest statistical evidence therefore concerns the complete dual-path policy, which is the method proposed in the paper.

The mechanism is also tested directly: on shared dense Q/K traces, the two extensions start from the same base mask and add the same number of blocks per query block, reaching identical 1.9462% final density.

MaskRetained dense mass (%)Added mass over base (pp)
Base only75.15090.0000
Base + centroid extension75.77010.6192
Base + RBS rescue79.80694.6560

At the same additional budget, RBS recovers 4.0368 pp more actual attention mass. This directly supports the mean-dilution motivation: rescue finds useful interactions beyond those recovered by extending centroid selection.

2. Block size and the validated operating configuration

Our original block-size sweep already calibrated actual density near 5.34%. It identifies B=128 as the strongest tested configuration: 80.28% task accuracy versus 74.73% for centroid-only, a 5.55 pp gain.

Changing B changes the token partition, centroids, radii, query-block aggregation, and overlap between the two selected masks. Similar block-pair density aligns the normalized retention budget, while branch allocation and selected interactions can still differ. Block size and the base/rescue thresholds are therefore coupled configuration choices. Our recommendation is B=128 with its calibrated selection policy. The lower task scores at B=64/256 motivate specifying this joint configuration rather than treating block sizes as interchangeable.

The additional trace diagnostics show substantial information coverage across all three tested granularities:

BMeasured density (%)Retained dense mass (%)
641.59178.32
1282.17281.01
2563.45480.20

At their reported densities, retained mass spans only 2.69 pp. These diagnostics complement the task-level evidence for our recommended configuration. Its practical value is measured by the full-RULER quality-targeted comparison:

MethodAccuracy (%)Retained budget (%)TTFT (s)
Centroid78.5114.0477.585
RBS78.164.9503.273

Timing uses 2 A100s, TP=2, batch=1, and chunked prefill. At a 0.35 pp accuracy difference, RBS uses 35.2% of the centroid configuration's retained causal-block-pair budget and is 2.32x faster end to end, including selection overhead. This demonstrates the deployment benefit of the validated configuration.

3. Reporting consistency and overall assessment

We have corrected the XAttn density caption: 1.802% at the 2.03% anchor is explicitly identified as a 0.228 pp exception. For the original LongBench-v2 subgroup/Total table, we will provide the sample correspondence, group counts, and aggregation rule explicitly. That reporting question is separate from the full-RULER component evaluation and shared-trace comparison above, which directly test the proposed selection mechanism.

Together, the paired statistical evidence, equal-count rescue comparison, and comparable-quality latency results support a concrete contribution: adaptive rescue and independent base preservation allocate sparse prefill computation more effectively, with measurable task and system benefits. We respectfully ask whether this evidence would support reconsidering your overall assessment.

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

This paper presents RBS-Attention, a training-free sparse prefill method for accelerating long-context LLM inference. The key observation is that centroid-based block selection may overlook important tokens due to mean dilution. To address this, the authors propose a dual-branch mechanism combining centroid-based relevance scoring with radius-adaptive rescue to recover potentially important blocks. The method integrates with block-sparse FlashAttention and reports substantial speedups, including 20.65× standalone attention acceleration and 5.97× end-to-end time-to-first-token speedup at 128K context length, while maintaining competitive accuracy across several long-context benchmarks.

Critical strengths

The paper studies a meaningful problem. Averaging key vectors can obscure important tokens.

The proposed radius-based rescue mechanism provides a simple and intuitive way to address this issue. The method is training-free, introduces relatively low computational overhead, and integrates with block-sparse FlashAttention. The reported speedups are substantial, particularly for long contexts.

The paper evaluates multiple models and benchmarks, including RULER, LongBench-v2, InfiniteBench, and Video-MME. The matched-density comparisons are particularly useful for assessing selection quality under comparable computational budgets.

Critical weaknesses

The main components, including centroid-based scoring, radius-based geometric bounds, and sparse block selection, are closely related to existing approaches. The novelty primarily lies in their combination and the adaptive weighting mechanism. A clearer differentiation from Quest and SpargeAttention would strengthen the contribution.

The proposed weighting relies on the median and 90th percentile of block radii. Is there a theoretical justification for these choices? Moreover, a large radius does not necessarily indicate high query relevance, since the dispersion may occur in directions unrelated to the query.

The primary speedup results focus on a specific MoE model and H100 hardware. Additional experiments on dense models, other hardware platforms, and different workloads would help establish the robustness of the method.

Questions for authors

How does RBS-Attention compare with existing methods in end-to-end latency at matched accuracy? Do the reported speedups generalize to dense models and other GPU architectures?

1 comment

Thank you for recognizing the mean-dilution motivation and training-free design. We added full-RULER ablations, rescue diagnostics, and quality-targeted system comparisons.

1. Contribution beyond existing block summaries

RBS separates average relevance from the risk that a summary hides useful tokens. Its base and radius-adaptive rescue branches use independent relative thresholds, followed by a mask union. Increasing rescue scores also changes their threshold reference; preserving an independent base path therefore has a distinct algorithmic role.

Quest uses coordinate-wise min/max bounds to select top-K KV pages for a decoding query. RBS targets prefill, aggregates token-query evidence into query-block scores, and applies two independently thresholded selection paths. SpargeAttention uses self-similarity gating and online softmax filtering; RBS continuously weights radius-based rescue while explicitly preserving the centroid path.

On full RULER-128K, with the same prefill backend and approximately 5% retained budget:

SelectorAccuracy (%)
Centroid-only74.49
Full-L2 only71.33
Adaptive-only70.49
Full-L2 + base73.44
RBS78.16

The independent base path improves adaptive scoring by 7.67 pp; RBS exceeds Full-L2 + base by 4.72 pp. Their combination achieves the highest accuracy, demonstrating the complementary roles of adaptive allocation and base protection.

2. Radius and median/p90 weighting

The centroid-radius inequality motivates the radius correction. Median/p90 weighting implements distribution-based allocation: blocks below the median receive no uplift, the middle range receives increasing weight, and the upper tail reaches full weight. Quantile normalization avoids scaling by an extreme maximum. The quantile levels are fixed, while their values adapt to each prompt/layer/KV head.

At B=128, the trace diagnostic gives:

QuantilesDensity (%)Retained dense mass (%)
(0.4, 0.8)2.17279.01
(0.5, 0.9), default2.17281.01
(0.6, 0.95)2.17180.98

At almost identical density, retained mass varies by at most 2.00 pp; the higher-quantile setting differs from the default by only 0.03 pp. This supports a stable default across nearby quantile choices.

For directionality, q⊤cbq^\top c_b captures average directional relevance, while radius measures possible deviations hidden by that average. Equal centroid/radius summaries can tie despite different internal directions. Radius affects selection only; the original token-level QK products and softmax determine actual attention weights.

We directly tested the value of the added computation. Starting from the same base mask and adding the same number of blocks, both extensions reach 1.9462% density. Centroid extension retains 75.7701% of dense attention mass, whereas RBS retains 79.8069%, a 4.0368 pp gain. Thus, radius-adaptive rescue allocates the same additional budget to more valuable interactions.

3. End-to-end efficiency at comparable quality

On full RULER-128K, the quality-targeted comparison is:

MethodAccuracy (%)Retained budget (%)TTFT (s)
Centroid78.5114.0477.585
RBS78.164.9503.273

Budget measures retained causal block pairs. Timing uses 2 A100s, TP=2, batch=1, and chunked prefill. At a 0.35 pp accuracy difference, RBS uses 35.2% of the centroid budget and is 2.32x faster, including selection overhead.

We also added the following LongBench-v2 comparison using Qwen3-30B-A3B-Instruct-2507-FP8 on one A100 (TP=1). Same-GPU speedups use Dense as the reference. TTFT runs from entry into the vLLM engine to the first generated token. Sparsity is the discarded proportion.

MethodAccuracy (%)Sparsity (%)Same-GPU speedup
Dense43.080.001.00x
FlashPrefill43.3181.992.31x
MInference43.0828.170.99x
XAttn43.3872.101.34x
FlexPrefill43.3857.171.34x
Quest-style42.5477.831.57x
SpargeAttention44.1520.011.10x
RBS43.8893.983.99x

RBS combines competitive answer quality with the highest measured acceleration in this comparison.

4. Dense models and broader workloads

On dense Qwen3-32B, RBS/Dense achieve 88.65/89.52 overall RULER accuracy and 80.57/80.70 at 128K. InfiniteBench (0.362/0.372) and Video-MME (65.98/66.16) extend quality evaluation beyond synthetic retrieval. The A100 results complement the H100 measurements; existing A100 experiments cover 32K-128K and batch sizes 1/4, including 3.85x throughput at 128K/batch 4. Together, these results support quality preservation across model/task types and practical prefill gains beyond H100.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.