FlashPrefill: Instantaneous Pattern Discovery and Thresholding for Ultra-Fast Long-Context Prefilling

Qihang Fan; Huaibo Huang; Zhiying Wu; Juqiu Wang; Bingning Wang; Ran He

cs.CLMar 6, 2026

FlashPrefill: Instantaneous Pattern Discovery and Thresholding for Ultra-Fast Long-Context Prefilling

Authors: Qihang Fan, Huaibo Huang, Zhiying Wu, Juqiu Wang, Bingning Wang, Ran He

Organizations: MAIS&NLPR, CASIA · UCAS · WeChat, Tencent

Abstract

Long-context modeling is a pivotal capability for Large Language Models, yet the quadratic complexity of attention remains a critical bottleneck, particularly during the compute-intensive prefilling phase. While various sparse attention mechanisms have been explored, they typically suffer from either significant search latency or insufficient sparsity. In this paper, we propose FlashPrefill, a framework enabling ultra-fast prefilling via instantaneous pattern discovery and thresholding. FlashPrefill leverages a fast block-searching technique to simultaneously locate dynamic vertical, slash, and block-sparse attention patterns. Crucially, it introduces a dynamic thresholding mechanism that bypasses the prohibitive overhead of sorting or accumulating attention scores while effectively eliminating the long-tail distribution to enhance sparsity. Extensive evaluations demonstrate that FlashPrefill achieves a substantial leap in efficiency, delivering an unprecedented 27.78x speedup on 256K sequences. Notably, unlike existing methods that incur efficiency degradation on shorter contexts, FlashPrefill maintains a 1.71x speedup even at a 4K context length, demonstrating its robustness and practical utility across varying sequence scales.

Figures & tables

Figure 3: Comparative speedup of various operators relative to Flash Attention [ 6 ] on Qwen3-30B-A3B-Instruct-2507. FlashPrefill exhibits a dominant advantage, particularly in long-context scenarios.

Figure 4: Execution time of different parts across different approaches. All results are measured on Qwen3-30B-A3B-Instruct-2507.

Figure 5: Illustration of pattern discovery. Red dashed lines represent the uniformly distributed queries.

Figure 6: Comparison of block scoring methodologies.(Left) Standard kernel with explicit attention score materialization.(Right) Our optimized kernel utilizing block-wise attention approximation. Compared to the standard implementation, our proposed block-level attention score approximation significantly reduces memory access overhead by bypassing the $O(L^{2}/B)$ intermediate memory traffic. Here, $L$ denotes the sequence length, $B$ represents the block size, and $d$ indicates the token dimension.

Method	4K	16K	64K	4K	16K	64K
	63.12	47.23	24.32	0.20ms	0.22ms	0.63ms
	87.69	83.12	73.26	0.68ms	2.48ms	18.26ms
	93.12	87.13	76.08	0.22ms	0.28ms	2.21ms

Table 1: Comparison of different methods for pattern discovery.

Figure 7: Comparison of different thresholding methodologies. (Left) Top- $k$ and Top- $p$ selection strategies. (Right) Our proposed Max-based thresholding. Top- $k$ and Top- $p$ methods are often susceptible to long-tail distributions, as they may include numerous low-significance blocks simply to satisfy the fixed $k$ or $p$ constraints. In contrast, our dynamic thresholding effectively mitigates the impact of the long tail, achieving higher sparsity through a more precise selection of salient blocks.

Density	Method	4K	8K	16K	32K	64K	128K	256K	512K
60%	[ 13 ]	1.27ms	4.16ms	15.29ms	59.39ms	235.67ms	940.09ms	3751.57ms	14990.36ms
60%	Ours	0.72ms	2.80ms	10.81ms	43.01ms	172.05ms	689.80ms	2757.41ms	11256.11ms
6%	[ 13 ]	0.43ms	0.55ms	1.61ms	6.14ms	24.48ms	94.68ms	383.46ms	1513.66ms
6%	Ours	0.14ms	0.23ms	0.98ms	4.20ms	17.31ms	68.48ms	278.69ms	1109.44ms

Table 2: Latency comparison for block-sparse attention implementations.

Method	En.Sum	En.QA	En.MC	En.Dia	Zh.QA	Code.Debug	Math.Find	Retr.PassKey	Retr.Number	Retr.KV	Avg
Llama-3.1-8B-Instruct
Full	32.04	25.93	69.00	21.00	31.75	18.02	25.14	99.32	99.66	62.00	48.39
MInference	32.04	21.94	64.63	14.50	31.75	5.33	27.43	56.61	78.31	14.00	34.65
FlexPrefill	30.42	24.82	68.41	15.50	32.46	16.75	31.14	95.64	99.83	44.00	45.90
XAttention	30.10	24.79	68.56	15.50	32.28	13.71	27.14	92.54	93.90	39.00	43.75
FlashMoBA	14.56	12.82	26.20	5.00	14.29	2.03	11.14	44.24	43.05	0.00	17.33

Table 3: Performance comparison of different methods on various models and tasks on InfiniteBench.

Method	4K	8K	16K	32K	64K	128K	Avg	4K	8K	16K	32K	64K	128K
Llama-3.1-8B-Instruct
Full	96.07	93.94	93.51	90.68	86.29	74.25	89.12	$1.00\times$	$1.00\times$	$1.00\times$	$1.00\times$	$1.00\times$	$1.00\times$
MInference	96.34	93.79	93.48	89.76	84.32	71.28	88.16	$0.11\times$	$0.16\times$	$0.45\times$	$0.83\times$	$1.34\times$	$2.45\times$
FlexPrefill	95.63	93.14	91.92	90.36	85.49	73.23	88.30	$0.11\times$	$0.33\times$	$0.98\times$	$2.21\times$	$4.16\times$	$5.18\times$
XAttention	95.01	92.16	91.91	90.06	85.17	71.68	87.67	$0.77\times$	$1.27\times$	$1.83\times$	$2.34\times$	$3.19\times$	$3.48\times$
FlashMoBA	93.14	83.23	79.28	72.13	60.12	31.26	69.86	$0.75\times$	$1.16\times$	$1.99\times$	$3.34\times$	$4.70\times$	$5.98\times$

Table 4: Performance vs. efficiency across different models and methods. Evaluation scores (left) and operator speedup relative to full attention (right) are reported.

Method	Short	Medium	Long	Avg
Qwen2.5-VL-7B-Instruct
Full	75.78	62.33	53.11	63.74
MInference	71.00	61.89	51.78	61.56
FlexPrefill	72.44	61.33	52.67	62.15
XAttention	74.11	60.30	50.13	61.51
FlashPrefill	74.78	61.67	53.22	63.22

Table 5: Performance comparison of different methods on various models on VideoMME.

Method	4K	8K	16K	32K	64K	128K	256K
FlexPrefill	20.4%	15.4%	14.1%	12.3%	10.1%	8.4%	8.4%
XAttention	57.4%	45.3%	37.8%	31.1%	25.6%	21.0%	18.5%
FlashPrefill	70.4%	46.0%	29.0%	17.6%	10.0%	5.8%	3.5%

Table 6: Density of various methods on the Qwen3-30B-A3B-Instruct-2507

Method	4K	8K	16K	32K	64K	128K
Llama-3.1-8B-Instruct
Full	471ms	976ms	2189ms	5398ms	14774ms	45464ms
FlashPrefill	447ms	913ms	1860ms	3618ms	7481ms	15061ms
speedup	$1.05\times$	$1.07\times$	$1.18\times$	$1.49\times$	$1.97\times$	$3.02\times$
Qwen2.5-7B-Instruct
Full	423ms	912ms	2048ms	4735ms	12563ms	37239ms

Table 7: End-to-end TTFT speedup achieved by FlashPrefill.

Method	32K	64K	128K	32K	64K	128K
Top- $k$	91.08	81.67	70.22	12.5%	12.5%	12.5%
Top- $p$	92.38	82.12	72.83	17.8%	15.7%	14.0%
Ours	92.21	84.93	75.31	16.0%	8.2%	4.5%

Table 8: Performance scores and attention density across various thresholding strategies.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

4K	8K	16K	32K	64K	128K
Llama-3.1-8B-Instruct( $\alpha=0.18$ )
71.0%	45.8%	28.0%	16.0%	8.2%	4.5%
Qwen2.5-7B-Instruct( $\alpha=0.08$ )
70.0%	46.8%	29.2%	20.8%	10.6%	6.6%
Qwen3-30B-A3B-Instruct-2507( $\alpha=0.12$ )
70.4%	46.0%	29.0%	17.6%	10.0%	5.8%

Appendix

Table 9: Hyperparameter configurations and resulting computational density for various models.

Explore similar work

FlashPrefill V2: Block-Sparse Prefill Attention for Long-Context LLM Serving
Aug 20, 2026Qihang Fan, Huaibo Huang, Zhiying Wu +2LLM Inference Acceleration Long-Context Language Model Inference
MAIS&NLPR, CASIA · UCAS · WeChat, Tencent
VSPrefill: Vertical-Slash Sparse Attention with Lightweight Indexing for Long-Context Prefilling
Mar 3, 2026Chen GuanzhongLong-Context Language Model Inference LLM Inference Acceleration
School of Computer Science and Technology, Tongji University
RBS-Attention: Radius-Bounded Sparse Prefill for Long-Context Large Language Models
Sep 17, 2026Chuxu Song, Jiuqi Wei, Zhencan PengLong-Context Language Model Inference LLM Inference Acceleration
Department of Computer Science, Rutgers University · OceanBase, Ant Group

Aug 20, 2026J/K move · Enter open · S save

FlashPrefill V2: Block-Sparse Prefill Attention for Long-Context LLM Serving

Qihang Fan, Huaibo Huang, Zhiying Wu, Bingning Wang+1

MAIS&NLPR, CASIA · UCAS · WeChat, Tencent

LLM Inference Acceleration Long-Context Language Model Inference Block-Sparse Attention

Open paper AskPDF arXiv

Long-context modeling is a pivotal capability for Large Language Models, yet the quadratic complexity of attention remains a critical bottleneck, particularly during the compute-intensive prefilling phase. Our previous work, FlashPrefill, mitigates this cost through instantaneous pattern discovery and max-based dynamic thresholding; however, it remains an algorithmic prototype that is still distant from production deployment. In this paper, we present FlashPrefill V2, which evolves FlashPrefill from a prototype toward practical long-context serving along three dimensions. First, we introduce a mean correction term that effectively suppresses the approximation error, keeping performance degradation manageable even at extreme sparsity levels. Second, we redesign the sparse attention operator with PackGQA memory access, warp specialization, and pingpong pipelining, fully aligning with the latest FlashAttention-3/4 implementations and supporting FP8 inference to meet practical quantization requirements. Third, FlashPrefill V2 natively supports paged KV cache and continuous batching, allowing integration as an attention backend in modern inference frameworks such as SGLang. Extensive evaluations on NVIDIA H20 GPUs---among the most widely deployed inference accelerators---demonstrate that FlashPrefill V2 delivers up to 47.26x and 27.19x speedups over FlashAttention-2 at 128K context length under FP8 and BF16 precision, respectively, and, in FP8, still achieves a 30.49x speedup against an FA3/4-aligned dense baseline.

Abstract

Explore similar work

FlashPrefill V2: Block-Sparse Prefill Attention for Long-Context LLM Serving

VSPrefill: Vertical-Slash Sparse Attention with Lightweight Indexing for Long-Context Prefilling

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