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

Authors: Chuxu Song, Jiuqi Wei, Zhencan Peng

arXiv: 2609.20971 [cs.AI]

Submitted: 17 Sep 2026

DOI: https://doi.org/10.48550/arXiv.2609.20971

Abstract

Long-context large language model (LLM) inference is increasingly limited by the prefill stage, in which dense self-attention must process the entire prompt before generation can begin. Sparse block selection can reduce this cost, but a block centroid may obscure a highly relevant token buried among many irrelevant ones. We term this failure mode mean dilution.

To address it, we propose RBS-Attention, a training-free sparse-prefill method built on two complementary selection branches:

A centroid base branch that captures average relevance.
A rescue branch that uses the maximum key-block radius and its prompt-, layer-, and head-dependent distribution to identify blocks at risk of underestimation.

The two branches are thresholded independently, and their masks are combined to control the contribution of rescue blocks while preserving regular block-sparse FlashAttention execution.

Key Results

On H100 GPUs, RBS-Attention delivers:

20.65× standalone prefill-attention speedup
11.92× vLLM prefill-attention speedup
5.97× end-to-end time-to-first-token speedup at 128K context on Qwen3-30B-A3B-Instruct-2507-FP8

On the dense Qwen3-32B model, RBS-Attention achieves 88.65 overall RULER accuracy, compared with 89.52 for dense attention. Additional quality evaluations are provided on LongBench-v2, InfiniteBench, and Video-MME.

Supporting experiments measure actual retention, compare selectors at matched density, and characterize block-size, threshold, and memory behavior. Together, these results support radius-adaptive dual-branch selection as an effective approach to long-context prefill.

Why This Matters in 2026

As context windows in production LLMs expand past 128K tokens, the prefill stage has become a dominant bottleneck for latency-sensitive applications such as retrieval-augmented generation, agentic workflows, and long-document or video understanding. Training-free sparse-prefill techniques like RBS-Attention offer a practical path to reduce time-to-first-token without retraining or fine-tuning, and their compatibility with block-sparse FlashAttention kernels makes them deployable on existing inference stacks such as vLLM.

Subjects

Artificial Intelligence (cs.AI)

Cite As

arXiv:2609.20971 [cs.AI]

(or arXiv:2609.20971v1 [cs.AI] for this version)

via ArXiv AI

RBS-Attention: Radius-Bounded Sparse Prefill for Long-Context