RBS-Attention: Accelerating Long-Prompt Prefill by Searching for Underestimated Blocks

14 October 20260 views

The article presents a method that supplements block selection based on average similarity with a search for candidates that may hide important tokens. At a 128K context length, the authors report up to 20.65× faster attention during prefill; on Qwen3-32B, the RULER score was 88.65, compared with 89.52 for dense attention.

RBS-Attention: Accelerating Long-Prompt Prefill by Searching for Underestimated Blocks

Which Part of Inference Does the Method Accelerate

Prefill processes the prompt before generation begins. Dense self-attention runs over the entire input, so a longer context increases the computational load of this stage.

RBS-Attention sparsely selects blocks for prefill and can reduce computational costs. But a block centroid averages token relevance and can hide an important token among irrelevant ones. The authors call this failure mode mean dilution.

The method’s practical purpose is to accelerate prefill without relying solely on the average relevance of an entire block.

How Block Selection Works

The method requires no training and uses two complementary branches:

  • Base branch estimates a block’s average relevance using its centroid.
  • Recovery branch takes into account a key block’s maximum radius and its distribution, which depends on the prompt, layer, and head. This helps identify blocks whose relevance may be underestimated.

Each branch applies a threshold to its own selection separately. The method then combines the masks and controls the contribution of recovery blocks. Execution remains on regular block-sparse FlashAttention.

This design is suited to scenarios where centroid-based selection might miss individual relevant tokens, while block-sparse execution still needs to be preserved.

What Speed Results Are Reported

Measurements were taken on an H100 with a 128K context. For Qwen3-30B-A3B-Instruct-2507-FP8, the paper reports the following speedups:

StageSpeedup
Standalone prefill-attention20.65×
Prefill-attention in vLLM11.92×
End-to-end time-to-first-token5.97×

These results are for a specific configuration. They should be considered separately from quality evaluations and not extrapolated to other models without corresponding measurements.

What Is Known About Quality and Evaluations

On the dense Qwen3-32B model, the overall RULER accuracy was 88.65. Dense attention scored 89.52.

Additional quality evaluations were conducted on LongBench-v2, InfiniteBench, and Video-MME. Supporting experiments measured retention of relevant data, compared selectors at the same sparsity level, and tested different block sizes, thresholds, and memory budgets.

When choosing a method, speed and quality should be evaluated separately: the reported RULER results do not replace testing on tasks that matter for a specific application.

Frequently asked questions

Related materials

All materials
RBS-Attention: Accelerating Long-Prompt Prefill by Searching for Underestimated Blocks