Paper deep dive
FlashPrefill: Instantaneous Pattern Discovery and Thresholding for Ultra-Fast Long-Context Prefilling
Qihang Fan, Huaibo Huang, Zhiying Wu, Juqiu Wang, Bingning Wang, Ran He
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/13/2026, 12:17:31 AM
Summary
FlashPrefill is an ultra-fast prefilling framework for Large Language Models that addresses the quadratic complexity of attention by using instantaneous pattern discovery and a Max-based dynamic thresholding mechanism. It utilizes block-level approximation and index-driven physical jumping to achieve significant speedups (up to 27.78x on 256K sequences) while maintaining model performance.
Entities (5)
Relation Signals (3)
FlashPrefill โ performs โ Instantaneous Pattern Discovery
confidence 100% ยท FlashPrefill features an Instantaneous Pattern Discovery stage
FlashPrefill โ utilizes โ Max-based Dynamic Thresholding
confidence 100% ยท it introduces a dynamic thresholding mechanism that bypasses the prohibitive overhead of sorting
FlashPrefill โ accelerates โ Large Language Models
confidence 95% ยท FlashPrefill, an ultra-fast prefill acceleration framework tailored for long-context scenarios.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2603.06199v1
- Canonical: https://arxiv.org/abs/2603.06199v1
Trouble viewing inline? Open PDF directly โ
Full Text
48,745 characters extracted from source content.
Expand or collapse full text
FlashPrefill: Instantaneous Pattern Discovery and Thresholding for Ultra-Fast Long-Context Prefilling Qihang Fan 1,2,3,โ , Huaibo Huang 1,2,โ , Zhiying Wu 3 , Juqiu Wang 2,3,โ , Bingning Wang 3,โก , Ran He 1,2 1 MAIS&NLPR, CASIA 2 UCAS 3 WeChat, Tencent ยง https://github.com/qhfan/FlashPrefill 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 unprecedented27.78รspeedup on 256K sequences. Notably, unlike existing methods that incur efficiency degradation on shorter contexts, FlashPrefill maintains a1.71ร speedup even at a 4K context length, demonstrating its robustness and practical utility across varying sequence scales. 1. Introduction Recent years have witnessed the rapid evolution of Large Language Models (LLMs), with the emergence of numerous highly capable models serving a massive user base across a di- verse range of tasks [7,21,22]. However, due to the inherent quadratic complexity of self- attentionโthe foundational operator of the Transformer architectureโLLMs often incur pro- hibitive time overhead when processing long-context sequences [23]. This bottleneck is particu- larly salient during the compute-intensive prefill stage. To mitigate these challenges, various sparse attention mechanisms have been proposed, most of which adhere to a consistent underlying principle [15,16,27]. These methods typically โ Corresponding Author. โก Project Leader. โ Work done during internship at WeChat. arXiv:2603.06199v1 [cs.CL] 6 Mar 2026 Figure 1|"Needle In A Haystack" evaluation of Qwen3-30B-A3B-Instruct-2507 using Flash- Prefill across context lengths ranging from 2K to 256K. 4K8K16K32K64K128K256K Sequence Length 0 2 4 6 8 TTFT Speedup 1.04x 1.18x 1.47x 1.98x 3.1x 5.02x 7.22x Figure 2|End-to-end Time-to-First-Token (TTFT) speedup relative to full attention on Qwen3-30B-A3B-Instruct-2507 within the vLLM framework. begin with a coarse-grained estimation of attention scores to identify salient blocks or structural patternsโsuch as vertical or diagonal (slash-like) stripesโusing selection strategies like Top- ํor Top-ํ. By subsequently restricting fine-grained attention computation to these critical tokens, they effectively accelerate long-context prefilling while preserving maximum information fidelity. Nevertheless, existing methodologies leave a substantial margin for efficiency improve- ments. First, the preliminary coarse-grained estimation of attention scores often introduces non-negligible computational latency. Second, selection strategies such as Top-ํor Top-ํneces- sitate explicit sorting of attention scoresโeither globally or locallyโincurring high overhead on modern GPU architectures. Top-ํschemes even require a cumulative summation over the score distribution, an inherently sequential process that is resistant to parallelization and leads to significant end-to-end delays. Lastly, Top-ํand Top-ํheuristics struggle to effectively prune the long-tail distribution of tokens with marginal influence, resulting in incomplete sparsity and persistent computational redundancy. In light of these considerations, we propose FlashPrefill, an ultra-fast prefill acceleration framework tailored for long-context scenarios. FlashPrefill features an Instantaneous Pattern Discovery stage that accurately identifies prevalent attention structures, such as vertical, slash, and block-wise patterns. To overcome the high latency typically associated with the discovery phase, we introduce a block-approximation strategy specifically designed to optimize the com- putation kernel. By streamlining memory access and parallelizing the discovery process through this block-level approximation, FlashPrefill reduces the discovery overhead to a negligible level, enabling the model to perceive the global attention landscape with extreme efficiency. Furthermore, FlashPrefill departs from traditional Top-ํor Top-ํblock selection methods, which are often bottlenecked by significant sorting latencies and computational complexity. Instead, it utilizes a more efficient Max-based Dynamic Thresholding mechanism. This approach not only streamlines the identification of salient blocks but also adaptively addresses the "incom- plete sparsity" problem typically caused by the heavy-tailed distribution of attention scores. By effectively filtering out redundant blocks without the need for exhaustive sorting, FlashPrefill ensures a more thorough sparse representation, thereby achieving substantial prefill acceler- ation while maintaining robust model performance across extensive context windows. Fig. 4 illustrates the time breakdown of different components across various methods. FlashPrefill significantly reduces the time spent on each component. We evaluated FlashPrefill across a diverse range of Large Language Models (LLMs) and 2 4K8K16K32K64K128K256K 0 5 10 15 20 25 30 Operator Speedup 0.11 0.16 0.45 0.85 1.39 2.73 3.58 0.12 0.34 0.98 2.31 3.92 5.43 6.01 0.84 1.43 2.02 2.45 2.97 3.45 4.08 0.7 1.13 1.97 3.34 4.7 5.98 7.12 1.71 2.79 4.48 6.94 11.45 18.67 27.78 MInference FlexPrefill XAttention FlashMoBA FlashPrefill (Ours) Figure 3| Comparative speedup of various operators relative to Flash Attention [5] on Qwen3- 30B-A3B-Instruct-2507. FlashPrefill exhibits a dominant advantage, particularly in long-context scenarios. FullFlexPrefillXAttentionFlashMoBAFlashPrefill 0 2 4 6 8 10 12 14 Time (ms) 1.8 14.7 2.1 2.5 1.0 Context: 4K FullFlexPrefillXAttentionFlashMoBAFlashPrefill 0 20 40 60 80 100 97.2 42.1 39.7 29.1 14.0 Context: 32K FullFlexPrefillXAttentionFlashMoBAFlashPrefill 0 1000 2000 3000 4000 5000 6000 6044.1 1005.7 1481.4 848.9 217.6 Context: 256K Pattern DiscoveryThresholdingPattern Discovery + ThresholdingAttention Figure 4|Execution time of different parts across different approaches. All results are measured on Qwen3-30B-A3B-Instruct-2507. Vision Language Models (VLMs), the results of which comprehensively underscore its superior performance. Taking Qwen3-30B-A3B-Instruct-2507 (which supports a maximum context length of 256K) as a representative example, Fig. 3 illustrates the speedup achieved by various operators across different sequence lengths. FlashPrefill demonstrates a significant advantage; even at a relatively short sequence length of 4K, it still delivers a1.71รspeedup. As the sequence length scales to 256K, FlashPrefill achieves a remarkable acceleration of27.78ร.Furthermore, we integrated FlashPrefill into the vLLM inference framework to measure the end-to-end Time to First Token (TTFT). As shown in Fig. 2, FlashPrefill achieves a maximum end-to-end speedup of7.22ร. Crucially, the experimental results on the "Needle In A Haystack" test for Qwen3, depicted in Fig. 1, indicate that FlashPrefill maintains nearly identical model performance with negligible loss in accuracy. Our contributions can be summarized as follows: โข We propose an Instantaneous Pattern Discovery method and introduce a block approxima- tion strategy to accelerate kernel computation and reduce memory access overhead. โขWe propose a Max-based Dynamic Thresholding method, which effectively eliminates the time overhead associated with local sorting in Top-ํor cumulative summation in Top-ํ strategies. Simultaneously, it mitigates the impact of long-tail distributions on sparse attention. โข Leveraging the aforementioned strategies, we introduce FlashPrefill, an efficient approach for accelerating the long-context prefill stage. Its efficacy is demonstrated through rigorous evaluations across a diverse set of models and benchmarks. 3 (a) vertical-slash(b) block-sparse(c) unified detection Figure 5|Illustration of pattern discovery. Red dashed lines represent the uniformly distributed queries. 2. Related Works Large Language Models. In recent years, the emergence of a wide array of Large Language Models (LLMs) has catalyzed rapid advancements across both academia and industry [1,17,28โ 30,34,36]. Furthermore, the rich prior knowledge inherent in LLMs can be leveraged to enhance Vision-Language Models (VLMs), facilitating the construction of intelligent multimodal agents [2, 3,9,18,24]. Beyond the classical Transformer architectures based on full attention, a growing number of novel architectures have emerged in modern LLMs to mitigate the prohibitive computational overhead incurred by full attention when processing long contexts. Such as the models use the sparse attention and linear attention [6, 8, 10, 12, 19, 20, 26, 31โ33, 38]. Sparse Attention.As a pivotal component of the Transformer architecture, the attention mech- anism plays a crucial role in capturing dependencies [23]. However, its quadratic complexity leads to significant computational overhead, especially in long-context scenarios. To address this, numerous sparse attention mechanisms have been proposed to reduce the computational cost of the attention layer [15,16,19,26,27,35,40]. While a portion of these approaches necessitates explicit model training or fine-tuning [35,40], others serve as training-free methods that can be seamlessly integrated into existing LLMs [15, 16, 27]. 3. Method 3.1. Instantaneous Pattern Discovery Drawing from prior research, we identify three primary sparsity patterns inherent in LLMs: vertical, slash, and block-based sparsity [15,16,27]. Most existing methodologies rely on search- based strategies to determine the specific pattern for each attention head, which often introduces additional computational profiling overhead [15,16]. Conversely, non-search-based alternatives typically require more intensive computation and the maintenance of dense attention score matrices, leading to substantial computational and memory access costs [27]. To facilitate the rapid identification of sparsity patterns within attention maps, we perform a qualitative analysis of various sparsity structures. As illustrated in Fig. 5, a skeletal set of uniformly distributed queries is sufficient to concurrently resolve vertical, slash, and block- sparse patterns. We attribute the effectiveness of this approach to the following three structural properties: โขVertical Patterns (Column-wise Invariance): These structures represent global key salience, where specific "anchor" tokens attract significant attention regardless of the queryโs po- 4 sition. Because these features are column-wise invariant, a sparse probing grid acts as a sufficient observer to pinpoint these high-energy columns. โขSlash Patterns (Translational Symmetry): Diagonal motifs typically emerge from local syntactic dependencies and relative positional biases. Due to their translational symmetry across the sequence, uniformly distributed probes can effectively sample these local "slices" and resolve the existence of continuous diagonal structures. โขBlock-sparse Patterns (Spatial Contiguity): These patterns are characterized by localized energy clusters. Leveraging the spatial contiguity of these regions, a uniform sampling strategy ensures a high probability of intersection with these dense clusters, allowing the importance of an entire block to be robustly inferred from a sparse "hit." Based on these insights, we directly employ the full set of queries to compute attention scores against all keys. To ensure maximum accuracy, we opt for this exhaustive approach to precisely identify the salient blocks. However, Direct query-key interaction over long sequences is computationally prohibitive. To optimize, we employ average-pooled keys ฬ ํ= 1 ํ ร ํ ํ โB ํ ํ as block-level proxies. This approach is predicated on the semantic locality and local coherence inherent in LLM embedding spaces, where tokens within a localized block exhibit high feature similarity and redundant attention patterns [4,26,39]. Mathematically, let a blockBconsist ofํkeysํ 1 ,. . .,ํ ํ with logits ํฅ ํ = ํยท ํ ํ . We define the probing scoreฮจ pool and the true contributionฮจ sum as follows: ฮจ pool = exp(ํยท ฬ ํ)= exp 1 ํ ํ โ๏ธ ํ=1 ํฅ ํ ! = ํ ร ํ=1 ํ ํฅ ํ ! 1/ํ = GM(ํ ํฅ 1 , . . . , ํ ํฅ ํ ) ฮจ sum = ํ โ๏ธ ํ=1 ํ ํฅ ํ = ํยท AM(ํ ํฅ 1 , . . . , ํ ํฅ ํ ) whereGM(ยท)andAM(ยท)denote the geometric and arithmetic means, respectively. By the AM-GM Inequality: 1 ํ ฮจ sum โฉพฮจ pool Whileฮจ pool serves as a lower bound, the rank-order invariance across blocks is maintained due to the low intra-block variance (ํ 2 โ 0) characteristic of attention distributions. In this regime, the GM acts as a strictly monotonic proxy for the AM, ensuring that the relative ordering of blocks remains unchanged with negligible rank distortion. Upon computing the attention scores for individual queries, we perform a secondary averaging operation across all queries within each block to derive the aggregate block-level significance. 3.2. Block Approximation for Kernel Optimization However, above approach still entails the storage and computation of a massiveํฟร(ํฟ/ํต) intermediate matrix when calculating intra-block attention averages, whereํตis block size. To address this, we once again leverage the semantic similarity of tokens within the same block [4,26,39]. Given that tokens in a localized block exhibit significant coherence, their resulting attention distributions are highly redundant. Based on this consideration, we depart from the computationally expensive strict attention calculation in favor of a block-wise attention 5 GEMM& Reduction Grid Loop ํ ํํํํํโฒ GEMM Grid Loop InnerLoop ํพ ) ํพ ํ ํํํํํ InnerLoop ํพ ) ํพ load:store:reduction: loop: 2ํฟํ1+ 1 ํต + ํฟ ! ํต ! + 2ํฟ ! ํต ํํํํํํฆ ํดํํํ : 2ํฟํ1+ 1 ํต + 4ํฟ ! ํต ! ํํํํํํฆ ํดํํํ : ํํํฅ ํํํํํ 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ํ(ํฟ 2 /ํต) intermediate memory traffic. Here,ํฟdenotes the sequence length,ํตrepresents the block size, and ํ indicates the token dimension. score approximation. Specifically, we implement a Fused 2D-Reduction kernel that transitions the computation from an explicit "compute-then-pool" sequence to a single-pass fused kernel, significantly reducing global memory traffic. Fig. 6 compares the two methods; we detail our approach below. Fused Block-level Attention Approximation.To avoid the prohibitive cost of strict token-level calculation, we depart from exact attention in favor of a block-wise approximation. By setting the query tile size equal to the block size (ํต), the kernel computes interactions between query tiles and pooled key blocks. We utilize a 1D reduction across the query dimension to compress fine-grained scores into a single approximated scalar per block-pair within the GPUโs SRAM: โขTiled Interaction: For each query tile, the kernel loads pooled key blocks (where each key in the block is represented by a single vectorํ ํฝ ) and computes the interactionํํ โค ํฝ as a representative proxy. โข Stable Online Reduction: To maintain numerical stability while approximating Softmax behavior, we perform a max-reduction and exponentiation along the query axis: ํ ํผ,ํฝ = max ํ ํ โTileํผ (ํ ํ ยท ํ ํฝ )(1) S ํผ,ํฝ = โ๏ธ ํ ํ โTileํผ exp(ํ ํ ยท ํ ํฝ โ ํ ํผ,ํฝ )(2) The kernel executes a sum across the query tile dimension to produce the approximated energy scoreS ํผ,ํฝ and the local maximum ํ ํผ,ํฝ for each block pair(ํผ, ํฝ). 6 Consistency-preserved Global Normalization. While the block-wise approximationS ํผ,ํฝ is stabilized using local maximums, these scores must be aligned to ensure global comparability across the sequence. We perform a global normalization pass to transform these approximated values into a unified importance map: โขMaximum Rescaling: We identify the global maximum for each query tile across all blocks, M ํผ = max ํฝ (ํ ํผ,ํฝ ), and rescale the local approximated scores to a common denominator: S โฒ ํผ,ํฝ =S ํผ,ํฝ ร exp(ํ ํผ,ํฝ โM ํผ )(3) โข Probability Mapping: The final block importance score is derived by normalizing against the total approximated energy of the row: Score ํผ,ํฝ = S โฒ ํผ,ํฝ ร ํพ S โฒ ํผ,ํพ + ํ (4) This fused process ensures that the resulting block-level map accurately reflects the relative at- tention distribution while reducing the memory footprint fromํ(ํฟยท ํฟ/ํต)down toํ((ํฟ/ํต) 2 ). By discarding strict calculation for this high-fidelity approximation, we enable near-instantaneous pattern discovery even for ultra-long sequences. 3.3. Comparison with Previous Methods. Compared to previous pattern discovery methods, our proposed method is both faster and more accurate. Based on Llama-3.1-8B-Instruct, we compared three different pattern discovery methods: 1) applying mean pooling to both query and key blocks followed by calculating inter-block attention scores [15,16]; 2) using the original method described in Sec. 3.1 without any block approximation described in Sec. 3.2 [19,26]; and 3) our proposed method based on block approximation. Method4K16K64K4K16K64K 1)63.1247.2324.320.20ms0.22ms0.63ms 2)87.6983.1273.260.68ms2.48ms18.26ms 3) 93.1287.1376.080.22ms0.28ms2.21ms Table 1| Comparison of different methods for pattern discovery. The results are presented in Tab. 1. We conducted evaluations on the RULER [14] benchmark; to ensure a fair comparison among the different pattern discovery methods, we consistently selected the top-8 highest-scoring blocks. Method 1) suffers from significant performance degradation due to its overly aggressive estimation strategy. In contrast, Method 2) incurs substantial time overhead because of excessive memory access costs. Our proposed Method 3) achieves the optimal balance between efficiency and effectiveness. 3.4. Max-based Dynamic Thresholding Previous methods rely on Top-ํor Top-ํheuristics to select salient tokens or blocks [15,16, 19,26,27]. However, these approaches necessitate relatively expensive sorting and cumulative computations, which is sub-optimal in terms of efficiency. 7 Figure 7|Comparison of different thresholding methodologies. (Left) Top-ํand Top-ํselection strategies. (Right) Our proposed Max-based thresholding. Top-ํand Top-ํmethods are often susceptible to long-tail distributions, as they may include numerous low-significance blocks simply to satisfy the fixedํorํ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. DensityMethod4K8K16K32K64K128K256K512K 60% [13]1.27ms 4.16ms 15.29ms 59.39ms 235.67ms 940.09ms 3751.57ms 14990.36ms Ours0.72ms 2.80ms 10.81ms 43.01ms 172.05ms 689.80ms 2757.41ms 11256.11ms 6% [13]0.43ms 0.55ms 1.61ms6.14ms24.48ms94.68ms383.46ms1513.66ms Ours0.14ms 0.23ms 0.98ms4.20ms17.31ms68.48ms278.69ms1109.44ms Table 2| Latency comparison for block-sparse attention implementations. Furthermore, Top-ํand Top-ํmechanisms suffer from insufficient sparsity due to their high susceptibility to long-tail distributions. As illustrated in Fig. 7, when the attention score distribution follows a long tailโwhich is prevalent in most scenariosโthese methods often necessitate the inclusion of numerous insignificant blocks merely to satisfy the fixedํorํ constraints, thereby failing to achieve optimal pruning efficiency. To circumvent these limitations, we introduce a Max-based Dynamic Thresholding mech- anism. Specifically, for theํผ-th query block, we identify the peak attention score across all candidate key blocks and derive the pruning threshold directly from this maximum value: thresh ํผ = ํผยท max ํฝโคํผ (Score ํผ,ํฝ ) whereํผis a tunable scaling factor. For query blockํผ, any key blockํฝwhose score falls below thresh ํผ is discarded from the computation. Crucially, this approach only requires a single-pass max-reduction instead of computationally expensive global sorting, significantly enhancing execution efficiency. Furthermore, as illustrated in Fig. 7, this dynamic thresholding effectively mitigates the interference of long-tail distributions, enabling superior sparsity compared to traditional heuristics by focusing exclusively on truly salient blocks. 8 MethodEn.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 Full32.0425.9369.0021.0031.7518.0225.1499.3299.6662.0048.39 MInference32.0421.9464.6314.5031.755.3327.4356.6178.3114.0034.65 FlexPrefill30.4224.8268.4115.5032.4616.7531.1495.6499.8344.0045.90 XAttention 30.1024.7968.5615.5032.2813.7127.1492.5493.9039.0043.75 FlashMoBA14.5612.8226.205.0014.292.0311.1444.2443.050.0017.33 FlashPrefill32.0425.0767.6916.5031.2216.7524.8696.1097.9755.0046.32 Qwen2.5-7B-Instruct Full17.485.1344.5415.508.9918.5334.000.3494.240.0023.87 MInference16.503.7039.7412.507.9416.2424.296.7891.360.0021.90 FlexPrefill18.454.8448.479.507.9417.5129.714.4195.590.0023.64 XAttention17.483.9949.7813.506.8818.7830.001.3693.730.0023.55 FlashMoBA2.911.1411.796.002.127.1113.140.0041.190.008.54 FlashPrefill20.394.8447.1610.508.9913.2037.4311.1995.590.0024.93 Qwen3-30B-A3B-Instruct-2507 Full33.0127.3565.9432.5010.0549.2434.8621.19100.004.2037.83 MInference25.2422.7959.8317.507.4133.5030.2922.3792.376.8031.81 FlexPrefill31.0722.2261.5722.508.4737.3133.1427.4698.145.4034.73 XAttention25.2424.7964.1921.005.2932.2334.0029.3296.107.2033.94 FlashMoBA6.808.2627.9512.002.657.6113.1419.1544.240.0014.18 FlashPrefill33.0123.3663.7619.509.5234.7736.5733.22100.008.6036.23 Table 3|Performance comparison of different methods on various models and tasks on In- finiteBench. 3.5. Optimized Block Sparse Attention Kernel After obtaining the sparsity pattern between the query and key blocks, FlashPrefill performs standard block-sparse attention on these blocks. In previous works [25,27], this computation was predominantly implemented based on the Block-Sparse-Attention codebase [13]. However, we observed that the implementation in the Block-Sparse-Attention repository fails to fully capitalize on the potential efficiency of sparse execution. The repository employs a logical skipping strategy for masked blocks: its inner loop indiscriminately iterates through the entire linear range of key blocks, using conditional branches to bypass GEMM operations for masked regions. Even when a block is masked and its matrix multiplication is bypassed, the thread execution flow must still fetch, decode, and execute the loop control logic, pointer arithmetic, and synchronization primitives within that iteration. This redundant instruction stream overhead leads to significant pipeline under-utilization, effectively bottlenecking the kernelโs overall throughput as the sequence length increases. To further push the performance frontiers of block-sparse attention, we have optimized its execution model. Specifically, we depart from the logical skipping strategy, which suffers from instruction stream overhead, and implement an index-driven physical jumping mech- anism. By directly redirecting memory pointers to salient block coordinates, our approach eliminates redundant control-flow processing and synchronization stalls, thereby maximizing hardware throughput and computational intensity in long-sequence scenarios. Tab. 2 bench- marks the efficiency of both methods across varying densities and sequence lengths, where our implementation substantially outpaces existing baseline. 9 Method4K8K16K32K64K128KAvg4K8K16K32K64K128K Llama-3.1-8B-Instruct Full96.0793.9493.5190.6886.2974.2589.121.00ร1.00ร1.00ร1.00ร1.00ร1.00ร MInference96.3493.7993.4889.7684.3271.2888.160.11ร0.16ร0.45ร0.83ร1.34ร2.45ร FlexPrefill95.6393.1491.9290.3685.4973.2388.300.11ร0.33ร0.98ร2.21ร4.16ร5.18ร XAttention95.0192.1691.9190.0685.1771.6887.670.77ร1.27ร1.83ร2.34ร3.19ร3.48ร FlashMoBA93.1483.2379.2872.1360.1231.2669.860.75ร1.16ร1.99ร3.34ร4.70ร5.98ร FlashPrefill97.2796.2094.9792.2184.9375.3190.151.71ร2.81ร4.63ร7.48ร13.62ร22.67ร Qwen2.5-7B-Instruct Full95.2193.1792.1890.1471.8725.2377.971.00ร1.00ร1.00ร1.00ร1.00ร1.00ร MInference95.6193.2191.6290.1668.2224.3877.200.11ร0.16ร0.45ร0.86ร1.39ร2.88ร FlexPrefill95.2793.2191.8189.1270.0626.3377.630.12ร0.34ร0.95ร2.29ร4.00ร5.86ร XAttention94.5292.1489.7286.2166.6526.3675.930.84ร1.56ร2.32ร3.04ร3.64ร4.34ร FlashMoBA 92.3683.6876.1168.1249.3120.1364.950.73ร1.14ร1.97ร3.34ร4.70ร5.98ร FlashPrefill95.3793.6491.9888.2570.4534.1078.971.72ร2.73ร4.51ร6.02ร10.68ร16.87ร Qwen3-30B-A3B-Instruct-2507 Full95.7895.7995.8294.3190.2587.7193.281.00ร1.00ร1.00ร1.00ร1.00ร1.00ร MInference95.5395.1294.8792.6288.6382.1691.480.11ร0.16ร0.45ร0.85ร1.39ร2.73ร FlexPrefill95.6795.4295.2393.6289.6286.1292.610.12ร0.34ร0.98ร2.31ร3.92ร5.43ร XAttention94.7293.6892.3290.4488.1283.6990.500.84ร1.43ร2.02ร2.45ร2.97ร3.45ร FlashMoBA92.1889.1384.2276.1367.1260.1278.150.70ร1.13ร1.97ร3.34ร4.70ร5.98ร FlashPrefill 95.7695.8995.0394.0690.1185.2092.681.71ร2.79ร4.48ร6.94ร11.45ร18.67ร Table 4|Performance vs. efficiency across different models and methods. Evaluation scores (left) and operator speedup relative to full attention (right) are reported. 4. Experiments To substantiate the efficacy of FlashPrefill, we conducted a comprehensive suite of experiments. We validated its performance in LLMs on two widely-recognized long-context benchmarks: RULER [14] and InfiniteBench [37]. Furthermore, we demonstrated its versatile applicability to VLMs through evaluations on the VideoMME [11] benchmark. Additionally, ablation studies were performed to investigate the impact of individual modules on both model effectiveness and execution efficiency. Detailed hyperparameter configurations are provided in the appendix. 4.1. Accuracy and Efficiency Results Baselines. For LLMs, we evaluated the performance of FlashPrefill on three distinct models: Llama-3.1-8B-Instruct [7], Qwen2.5-7B-Instruct [29], and Qwen3-30B-A3B-Instruct-2507 [28]. For comparison, we selected Full Attention [23], MInference [15], FlexPrefill (ํพ=0.9,ํ=0.1) [16], XAttention (ํํกํํํํ=16,ํ=0.9) [27], and FlashMoBA (ํต=128,ํกํํํ=8) [19,26] as baselines. All benchmarks and efficiency metrics were measured under identical hyperparameter settings. For VLMs, we selected Qwen2.5-VL-7B-Instruct and Qwen3-VL-30B-A3B-Instruct for evaluation. The hyperparameters for each baseline remain identical to those used in the LLM evaluations. All efficiency metrics were measured on NVIDIA H20 GPUs. FlashAttention 2.8.3 is utilized as the full-attention baseline in our experiments. InfiniteBench.Tab. 3 presents the results of various models and methods on the InfiniteBench benchmark. It can be observed that FlashPrefill consistently achieves superior performance compared to other baselines across both dense and Mixture-of-Experts (MoE) models. 10 MethodShortMediumLongAvg Qwen2.5-VL-7B-Instruct Full75.7862.3353.1163.74 MInference71.0061.8951.7861.56 FlexPrefill72.4461.3352.6762.15 XAttention74.1160.3050.1361.51 FlashPrefill 74.7861.6753.2263.22 Qwen3-VL-30B-A3B-Instruct Full81.1171.4463.7872.11 MInference79.8970.8962.8971.22 FlexPrefill79.3371.0062.6771.01 XAttention79.6770.1162.0670.61 FlashPrefill80.7871.8963.3372.00 Table 5| Performance comparison of different methods on various models on VideoMME. Method4K8K16K32K64K128K256K FlexPrefill20.4%15.4%14.1%12.3%10.1%8.4%8.4% XAttention57.4%45.3%37.8%31.1%25.6%21.0%18.5% FlashPrefill70.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 RULER.Tab. 4 presents the results of various methods across different models on the RULER benchmark. The left side of the table displays the RULER scores, while the right side reports the operator speedup relative to full attention at different sequence lengths. Compared to prior approaches, FlashPrefill achieves a significant speedup across all tested lengths. Specifically, at a 128K context length, FlashPrefill attains speedups of22.67ร,16.87ร, and18.67รon three representative models, respectively, substantially outperforming existing methods. VideoMME. Tab. 5 presents the performance of various methods on the Video-MME bench- mark. Compared to existing sparse attention approaches, FlashPrefill achieves superior results. Density.Tab. 6 presents the density of various methods on the Qwen3-30B-A3B-Instruct-2507 model. It is observed that FlashPrefill effectively mitigates the impact of the long-tail distribution. As the sequence length increases, the amount of effective information relatively diminishes; consequently, FlashPrefill exhibits a significant reduction in density compared to the other two methods. End-to-End Time-to-First-Toke Speedup. To evaluate the acceleration of FlashPrefill during the full LLM prefilling process, we integrated it into the vLLM inference framework and measured the Time-to-First Token (TTFT). The results, summarized in Tab. 7, demonstrate the end-to-end TTFT speedup across three language models, including both dense and Mixture- of-Experts (MoE) architectures. Compared to Full Attention, FlashPrefill achieves significant performance gains. Notably, on the Qwen3-30B-A3B-Instruct-2507, it delivers a 5.02รspeedup at a sequence length of 128K. 11 Method4K8K16K32K64K128K Llama-3.1-8B-Instruct Full471ms976ms2189ms5398ms14774ms45464ms FlashPrefill447ms913ms1860ms3618ms7481ms15061ms speedup1.05ร1.07ร1.18ร1.49ร1.97ร3.02ร Qwen2.5-7B-Instruct Full423ms912ms2048ms4735ms12563ms37239ms FlashPrefill406ms851ms1707ms3534ms7323ms15213ms speedup 1.04ร1.07ร1.20ร1.34ร1.72ร2.45ร Qwen3-30B-A3B-Instruct-2507 Full267ms613ms1603ms4635ms15203ms53752ms FlashPrefill257ms519ms1090ms2331ms4909ms10702ms speedup 1.04ร1.18ร1.47ร1.98ร3.10ร5.02ร Table 7| End-to-end TTFT speedup achieved by FlashPrefill. Method32K64K128K32K64K128K Top-ํ91.0881.6770.2212.5%12.5%12.5% Top-ํ92.3882.1272.8317.8%15.7%14.0% Ours 92.2184.9375.3116.0%8.2%4.5% Table 8| Performance scores and attention density across various thresholding strategies. 4.2. Ablation Study Pattern Discovery & Thresholding.The combined process of pattern discovery and threshold- ing is a prerequisite for sparse attention computation, governed by two primary considerations: 1) the accuracy in identifying critical tokens to prevent performance degradation, and 2) the simplicity and speed of the execution. We discuss the first objective in Sec. 3.3, where our pro- posed block approximation demonstrates superior performance and achieves a robust balance between efficiency and effectiveness compared to structurally similar methods. Regarding the second consideration, we compared the combined execution time of discovery and thresholding across different approaches, with the results summarized in Fig. 4. It is evident that FlashPrefill is significantly faster than other methods in the process of identifying important tokens. Different Thresholding Approaches.Previous methods predominantly employ Top-ํor Top- ํstrategies for dynamic token selection; however, these approaches are highly susceptible to long-tail distribution effects as sequence lengths increase. In contrast, our Max-based Dynamic Thresholding eliminates the influence of such long-tail distributions, achieving more thorough sparsity in long-context scenarios. Tab. 8 presents the performance of Llama-3.1-8B-Instruct on the RULER benchmark using various thresholding methods. The left side of the table reports model scores, while the right side displays the corresponding attention density. It is evident that our proposed method significantly reduces computational density while preserving the vast majority of the modelโs performance, thereby achieving superior acceleration. 12 5. Conclusion In this paper, we present FlashPrefill, a novel approach designed to significantly accelerate the long-context prefilling stage of Large Language Models (LLMs). FlashPrefill introduces an instantaneous pattern discovery mechanism, further optimized by a block-approximation-based kernel implementation to minimize memory access overhead. Additionally, we propose Max- based Dynamic Thresholding, which obviates the need for sorting and accumulation operations while mitigating the impact of long-tail distributions, thereby achieving a higher degree of sparsity. Our extensive evaluations across various LLMs, VLMs, and diverse benchmarks demonstrate that FlashPrefill effectively enhances prefill efficiency while maintaining superior performance. References [1]J. Bai, S. Bai, Y. Chu, Z. Cui, K. Dang, X. Deng, Y. Fan, W. Ge, Y. Han, F. Huang, B. Hui, L. Ji, M. Li, J. Lin, R. Lin, D. Liu, G. Liu, C. Lu, K. Lu, J. Ma, R. Men, X. Ren, X. Ren, C. Tan, S. Tan, J. Tu, P. Wang, S. Wang, W. Wang, S. Wu, B. Xu, J. Xu, A. Yang, H. Yang, J. Yang, S. Yang, Y. Yao, B. Yu, H. Yuan, Z. Yuan, J. Zhang, X. Zhang, Y. Zhang, Z. Zhang, C. Zhou, J. Zhou, X. Zhou, and T. Zhu. Qwen technical report.arXivpreprintarXiv:2309.16609, 2023. URL https://arxiv.org/abs/2309.16609. [2]S. Bai, Y. Cai, R. Chen, K. Chen, X. Chen, Z. Cheng, L. Deng, W. Ding, C. Gao, C. Ge, W. Ge, Z. Guo, Q. Huang, J. Huang, F. Huang, B. Hui, S. Jiang, Z. Li, M. Li, M. Li, K. Li, Z. Lin, J. Lin, X. Liu, J. Liu, C. Liu, Y. Liu, D. Liu, S. Liu, D. Lu, R. Luo, C. Lv, R. Men, L. Meng, X. Ren, X. Ren, S. Song, Y. Sun, J. Tang, J. Tu, J. Wan, P. Wang, P. Wang, Q. Wang, Y. Wang, T. Xie, Y. Xu, H. Xu, J. Xu, Z. Yang, M. Yang, J. Yang, A. Yang, B. Yu, F. Zhang, H. Zhang, X. Zhang, B. Zheng, H. Zhong, J. Zhou, F. Zhou, J. Zhou, Y. Zhu, and K. Zhu. Qwen3-vl technical report.arXivpreprintarXiv:2511.21631, 2025. URLhttps://arxiv.org/abs/ 2511.21631. [3]S. Bai, K. Chen, X. Liu, J. Wang, W. Ge, S. Song, K. Dang, P. Wang, S. Wang, J. Tang, H. Zhong, Y. Zhu, M. Yang, Z. Li, J. Wan, P. Wang, W. Ding, Z. Fu, Y. Xu, J. Ye, X. Zhang, T. Xie, Z. Cheng, H. Zhang, Z. Yang, H. Xu, and J. Lin. Qwen2.5-vl technical report.arXiv preprintarXiv:2502.13923, 2025. URL https://arxiv.org/abs/2502.13923. [4] I. Beltagy, M. E. Peters, and A. Cohan. Longformer: The long-document transformer.arXiv preprintarXiv:2004.05150, 2020. URL https://arxiv.org/abs/2004.05150. [5]T. Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. arXivpreprintarXiv:2307.08691, 2023. URL https://arxiv.org/abs/2307.08691. [6] T. Dao and A. Gu. Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality. InInternationalConferenceonMachineLearning, 2024. [7]A. Dubey, A. Jauhri, A. Pandey, et al. The llama 3 herd of models.arXivpreprint arXiv:2407.21783, 2024. [8]Q. Fan, H. Huang, Y. Ai, and R. He. Rectifying magnitude neglect in linear attention. In IEEEInternationalConferenceonComputerVision, 2025. 13 [9]Q. Fan, H. Huang, M. Chen, and R. He. Semantic equitable clustering: A simple and effec- tive strategy for clustering vision tokens. InIEEEInternationalConferenceonComputer Vision, 2025. [10]Q. Fan, H. Huang, and R. He. Breaking the low-rank dilemma of linear attention. InIEEE ConferenceonComputerVisionandPatternRecognition, 2025. [11] C. Fu, Y. Dai, Y. Luo, L. Li, S. Ren, R. Zhang, Z. Wang, C. Zhou, Y. Shen, M. Zhang, et al. Video-mme: The first-ever comprehensive evaluation benchmark of multi-modal llms in video analysis. InIEEEConferenceonComputerVisionandPatternRecognition, 2025. [12]A. Gu and T. Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXivpreprintarXiv:2312.00752, 2023. [13]J. Guo, H. Tang, S. Yang, Z. Zhang, Z. Liu, and S. Han. Block Sparse Attention.https: //github.com/mit-han-lab/Block-Sparse-Attention, 2024. [14]C.-P. Hsieh, S. Sun, S. Kriman, S. Acharya, D. Rekesh, F. Jia, Y. Zhang, and B. Ginsburg. Ruler: Whatโs the real context size of your long-context language models?arXivpreprint arXiv:2404.06654, 2024. URL https://arxiv.org/abs/2404.06654. [15] H. Jiang, Y. Li, C. Zhang, Q. Wu, X. Luo, S. Ahn, Z. Han, A. H. Abdi, D. Li, C.-Y. Lin, Y. Yang, and L. Qiu. MInference 1.0: Accelerating pre-filling for long-context LLMs via dynamic sparse attention. InAdvancesinNeuralInformationProcessingSystems, 2024. [16]X. Lai, J. Lu, Y. Luo, Y. Ma, and X. Zhou. Flexprefill: A context-aware sparse attention mechanism for efficient long-sequence inference. InInternationalConferenceonLearning Representations, 2025. [17]A. Li, B. Gong, B. Yang, B. Shan, C. Liu, C. Zhu, C. Zhang, C. Guo, D. Chen, D. Li, E. Jiao, G. Li, G. Zhang, H. Sun, H. Dong, J. Zhu, J. Zhuang, J. Song, J. Zhu, J. Han, J. Li, J. Xie, J. Xu, J. Yan, K. Zhang, K. Xiao, K. Kang, L. Han, L. Wang, L. Yu, L. Feng, L. Zheng, L. Chai, L. Xing, M. Ju, M. Chi, M. Zhang, P. Huang, P. Niu, P. Li, P. Zhao, Q. Yang, Q. Xu, Q. Wang, Q. Wang, Q. Li, R. Leng, S. Shi, S. Yu, S. Li, S. Zhu, T. Huang, T. Liang, W. Sun, W. Sun, W. Cheng, W. Li, X. Song, X. Su, X. Han, X. Zhang, X. Hou, X. Min, X. Zou, X. Shen, Y. Gong, Y. Zhu, Y. Zhou, Y. Zhong, Y. Hu, Y. Fan, Y. Yu, Y. Yang, Y. Li, Y. Huang, Y. Li, Y. Huang, Y. Xu, Y. Mao, Z. Li, Z. Li, Z. Tao, Z. Ying, Z. Cong, Z. Qin, Z. Fan, Z. Yu, Z. Jiang, and Z. Wu. Minimax-01: Scaling foundation models with lightning attention.arXivpreprint arXiv:2501.08313, 2025. URL https://arxiv.org/abs/2501.08313. [18] H. Liu, C. Li, Q. Wu, and Y. J. Lee. Visual instruction tuning. InAdvancesinNeural InformationProcessingSystems, 2023. [19]E. Lu, Z. Jiang, J. Liu, Y. Du, T. Jiang, C. Hong, S. Liu, W. He, E. Yuan, Y. Wang, Z. Huang, H. Yuan, S. Xu, X. Xu, G. Lai, Y. Chen, H. Zheng, J. Yan, J. Su, Y. Wu, N. Y. Zhang, Z. Yang, X. Zhou, M. Zhang, and J. Qiu. Moba: Mixture of block attention for long-context llms. arXivpreprintarXiv:2502.13189, 2025. URL https://arxiv.org/abs/2502.13189. [20]Y. Sun, L. Dong, S. Huang, S. Ma, Y. Xia, J. Xue, J. Wang, and F. Wei. Retentive network: A successor to transformer for large language models.arXivpreprintarXiv:2307.08621, 2023. URL https://arxiv.org/abs/2307.08621. [21]H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Roziรจre, N. Goyal, E. Hambro, F. Azhar, et al. Llama: Open and efficient foundation language models.arXivpreprintarXiv:2302.13971, 2023. 14 [22]H. Touvron, L. Martin, K. Stone, P. Albert, A. Almahairi, Y. Babaei, N. Bashlykov, S. Batra, P. Bhargava, S. Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models.arXiv preprintarXiv:2307.09288, 2023. [23]A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, ล. Kaiser, and I. Polosukhin. Attention is all you need.AdvancesinNeuralInformationProcessing Systems, 30, 2017. [24]P. Wang, S. Bai, S. Tan, S. Wang, Z. Fan, J. Bai, K. Chen, X. Liu, J. Wang, W. Ge, Y. Fan, K. Dang, M. Du, X. Ren, R. Men, D. Liu, C. Zhou, J. Zhou, and J. Lin. Qwen2-vl: Enhanc- ing vision-language modelโs perception of the world at any resolution.arXivpreprint arXiv:2409.12191, 2024. URL https://arxiv.org/abs/2409.12191. [25]Y. Wang, H. He, S. Bao, H. Wu, H. Wang, Q. Zhu, and W. Che. Proxyattn: Guided sparse attention via representative heads.arXivpreprintarXiv:2509.24745, 2025. URL https://arxiv.org/abs/2509.24745. [26] G. Xiao, J. Guo, K. Mazaheri, and S. Han. Optimizing mixture of block attention.arXiv preprintarXiv:2511.11571, 2025. URL https://arxiv.org/abs/2511.11571. [27]R. Xu, G. Xiao, H. Huang, J. Guo, and S. Han. Xattention: Block sparse attention with antidiagonal scoring. InInternationalConferenceonMachineLearning, 2025. [28]A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, C. Zheng, D. Liu, F. Zhou, F. Huang, F. Hu, H. Ge, H. Wei, H. Lin, J. Tang, J. Yang, J. Tu, J. Zhang, J. Yang, J. Yang, J. Zhou, J. Zhou, J. Lin, K. Dang, K. Bao, K. Yang, L. Yu, L. Deng, M. Li, M. Xue, M. Li, P. Zhang, P. Wang, Q. Zhu, R. Men, R. Gao, S. Liu, S. Luo, T. Li, T. Tang, W. Yin, X. Ren, X. Wang, X. Zhang, X. Ren, Y. Fan, Y. Su, Y. Zhang, Y. Zhang, Y. Wan, Y. Liu, Z. Wang, Z. Cui, Z. Zhang, Z. Zhou, and Z. Qiu. Qwen3 technical report.arXivpreprint arXiv:2505.09388, 2025. URL https://arxiv.org/abs/2505.09388. [29] A. Yang, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Li, D. Liu, F. Huang, H. Wei, H. Lin, J. Yang, J. Tu, J. Zhang, J. Yang, J. Y. Parameter, J. Zhou, J. Lin, K. Dang, K. Lu, K. Bao, K. Yang, L. Yu, M. Li, M. Xue, P. Zhang, Q. Zhu, R. Men, R. Lin, T. Li, T. Tang, T. Xia, X. Ren, X. Ren, Y. Fan, Y. Su, Y. Zhang, Y. Wan, Y. Liu, Z. Cui, Z. Zhang, and Z. Qiu. Qwen2.5 technical report.arXivpreprintarXiv:2412.15115, 2025. URLhttps: //arxiv.org/abs/2412.15115. [30] A. Yang, B. Yu, C. Li, D. Liu, F. Huang, H. Huang, J. Jiang, J. Tu, J. Zhang, J. Zhou, J. Lin, K. Dang, K. Yang, L. Yu, M. Li, M. Sun, Q. Zhu, R. Men, T. He, W. Xu, W. Yin, W. Yu, X. Qiu, X. Ren, X. Yang, Y. Li, Z. Xu, and Z. Zhang. Qwen2.5-1m technical report.arXivpreprint arXiv:2501.15383, 2025. [31] S. Yang, B. Wang, Y. Shen, R. Panda, and Y. Kim. Gated linear attention transformers with hardware-efficient training. InInternationalConferenceonMachineLearning, 2024. [32]S. Yang, B. Wang, Y. Zhang, Y. Shen, and Y. Kim. Parallelizing linear transformers with the delta rule over sequence length. InAdvancesinNeuralInformationProcessingSystems, 2024. [33]S. Yang, J. Kautz, and A. Hatamizadeh. Gated delta networks: Improving mamba2 with delta rule. InInternationalConferenceonLearningRepresentations, 2025. 15 [34]A. Young, B. Chen, C. Li, C. Huang, G. Zhang, G. Zhang, G. Wang, H. Li, J. Zhu, J. Chen, J. Chang, K. Yu, P. Liu, Q. Liu, S. Yue, S. Yang, S. Yang, W. Xie, W. Huang, X. Hu, X. Ren, X. Niu, P. Nie, Y. Li, Y. Xu, Y. Liu, Y. Wang, Y. Cai, Z. Gu, Z. Liu, and Z. Dai. Yi: Open foundation models by 01.ai.arXivpreprintarXiv:2403.04652, 2025. URLhttps://arxiv. org/abs/2403.04652. [35] J. Yuan, H. Gao, D. Dai, J. Luo, L. Zhao, Z. Zhang, Z. Xie, Y. Wei, L. Wang, Z. Xiao, Y. Wang, C. Ruan, M. Zhang, W. Liang, and W. Zeng. Native sparse attention: Hardware- aligned and natively trainable sparse attention. InAnnualMeetingoftheAssociationfor ComputationalLinguistics, 2025. [36] A. Zeng, B. Xu, B. Wang, C. Zhang, D. Yin, D. Rojas, G. Feng, H. Zhao, H. Lai, H. Yu, H. Wang, J. Sun, J. Zhang, J. Cheng, J. Gui, J. Tang, J. Zhang, J. Li, L. Zhao, L. Wu, L. Zhong, M. Liu, M. Huang, P. Zhang, Q. Zheng, R. Lu, S. Duan, S. Zhang, S. Cao, S. Yang, W. L. Tam, W. Zhao, X. Liu, X. Xia, X. Zhang, X. Gu, X. Lv, X. Liu, X. Liu, X. Yang, X. Song, X. Zhang, Y. An, Y. Xu, Y. Niu, Y. Yang, Y. Li, Y. Bai, Y. Dong, Z. Qi, Z. Wang, Z. Yang, Z. Du, Z. Hou, and Z. Wang. Chatglm: A family of large language models from glm-130b to glm-4 all tools. arXivpreprintarXiv:2406.12793, 2024. URL https://arxiv.org/abs/2406.12793. [37]X. Zhang, Y. Chen, S. Hu, Z. Xu, J. Chen, M. Hao, X. Han, Z. Thai, S. Wang, Z. Liu, and M. Sun.โBench: Extending long context evaluation beyond 100K tokens. InAnnual MeetingoftheAssociationforComputationalLinguistics, 2024. URLhttps://aclant hology.org/2024.acl-long.814. [38] Y. Zhang, Z. Lin, X. Yao, J. Hu, F. Meng, C. Liu, X. Men, S. Yang, Z. Li, W. Li, E. Lu, W. Liu, Y. Chen, W. Xu, L. Yu, Y. Wang, Y. Fan, L. Zhong, E. Yuan, D. Zhang, Y. Zhang, Y. T. Liu, H. Wang, S. Fang, W. He, S. Liu, Y. Li, J. Su, J. Qiu, B. Pang, J. Yan, Z. Jiang, W. Huang, B. Yin, J. You, C. Wei, Z. Wang, C. Hong, Y. Chen, G. Chen, Y. Wang, H. Zheng, F. Wang, Y. Liu, M. Dong, Z. Zhang, S. Pan, W. Wu, Y. Wu, L. Guan, J. Tao, G. Fu, X. Xu, Y. Wang, G. Lai, Y. Wu, X. Zhou, Z. Yang, and Y. Du. Kimi linear: An expressive, efficient attention architecture.arXivpreprintarXiv:2510.26692, 2025. URLhttps://arxiv.org/abs/25 10.26692. [39]Z. Zhang, Y. Sheng, et al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. InAdvancesinNeuralInformationProcessingSystems, 2023. [40] W. Zhao, Z. Zhou, Z. Su, C. Xiao, Y. Li, Y. Li, Y. Zhang, W. Zhao, Z. Li, Y. Huang, A. Sun, X. Han, and Z. Liu. Infllm-v2: Dense-sparse switchable attention for seamless short-to-long adaptation.arXivpreprintarXiv:2509.24663, 2025. URLhttps://arxiv.org/abs/25 09.24663. 16 A. Hyperparameter Configurations In FlashPrefill, the sole hyperparameter requiring adjustment is theํผvalue used to determine the dynamic threshold. We calibrate this threshold by observing the computational density of different models at a sequence length of 4K. Specifically, we regulateํผto maintain a computa- tional density of approximately 70% for 4K sequences, as summarized in Tab. 6. We employ a uniform block size of 128 across all models. In addition to the blocks selected via Max-based Dynamic Thresholding, we explicitly retain the attention sinks and a local window, with their sizes set to 256 and 512 tokens, respectively. 4K8K16K32K64K128K Llama-3.1-8B-Instruct(ํผ= 0.18) 71.0%45.8%28.0%16.0%8.2%4.5% Qwen2.5-7B-Instruct(ํผ= 0.08) 70.0%46.8%29.2%20.8%10.6%6.6% Qwen3-30B-A3B-Instruct-2507(ํผ= 0.12) 70.4%46.0%29.0%17.6%10.0%5.8% Table 9|Hyperparameter configurations and resulting computational density for various models. B. Detailed Implementation To provide a clearer elucidation of our proposed FlashPrefill, we decompose the framework into three distinct stages: (i) Instantaneous Pattern Discovery, (i) Max-based Dynamic Thresholding and Block Selection, and (i) Block Sparse Attention. The detailed logic for each stage is formalized as pseudocode in Alg. 1, Alg. 2, and Alg. 3, respectively. 17 Algorithm 1 Instantaneous Pattern Discovery Input: Query ํ โR ํฟรํ , Key ํพ โR ํฟรํ , scaling ํ, block size ํต Output: Block-level importance map PโR ํฟ ํต ร ํฟ ํต // Stage 1: Key Block Pre-pooling for ํฝ= 0 to ํฟ ํต โ 1 do ํพ ํํํํํ = ํพ[ํฝยท ํต : (ํฝ+ 1)ยท ํต, :] ฬ ํ ํฝ = Mean(ํพ ํํํํํ , axis= 0) Represent block by a vector end for // Stage 2: Fused Block Approximation for ํผ= 0 to ํฟ ํต โ 1 do ํ ํผ = ํ[ํผยท ํต : (ํผ+ 1)ยท ํต, :] Load query tile for each ฬ ํ ํฝ where ํฝ โค ํผ do qk=(ํ ํผ ยท ฬ ํ โค ํฝ )ยท ํยท log 2 ํ Result size ํตร 1 qk= ApplyCausalMask(qk) ํ ํผ,ํฝ = max ํโ0,...,ํตโ1 (qk ํ ) S ํผ,ํฝ = ร ํตโ1 ํ=0 2 (qk ํ โํ ํผ,ํฝ ) end for end for // Stage 3: Consistency-preserved Global Normalization for ํผ= 0 to ํฟ ํต โ 1 do M ํผ = max ํฝโคํผ (ํ ํผ,ํฝ ) Global max for row ํผ for ํฝ= 0 to ํผ do S โฒ ํผ,ํฝ =S ํผ,ํฝ ร 2 (ํ ํผ,ํฝ โM ํผ ) end for P ํผ,ํฝ =S โฒ ํผ,ํฝ /( ร ํผ ํพ=0 S โฒ ํผ,ํพ + ํ) end for return P 18 Algorithm 2 Max-based Dynamic Thresholding and Block Selection Input: Block scores SโR ํรํรํรํป , sink size ํ, window size ํ, threshold factor ํผ Output: Compact indices I, Active counts C // Step 1: Generate Dynamic and Structural Masks for each batch ํง, query block ํ, and head โ do ํํํฅ_ํฃํํ= max ํโ0,...,ํโ1 S ํง,ํ,ํ,โ for each key block ํโ 0, . . . , ํโ 1 do ํํํ ํ_ํ ํํํํ=(S ํง,ํ,ํ,โ โฅ ํํํฅ_ํฃํํยท ํผ) ํํํ ํ_ํ ํํํ=(ํ < ํ) ํํํ ํ_ํคํํํํํค=(0โค ํโ ํ < ํ) ํํํ ํ_ํํํขํ ํํ=(ํโฅ ํ) // Union of active blocks limited by causality ํํ _ํํํกํํฃํ ํง,ํ,ํ,โ =(ํํํ ํ_ํ ํํํํโจ ํํํ ํ_ํ ํํํโจ ํํํ ํ_ํคํํํํํค)โง ํํํ ํ_ํํํขํ ํํ end for end for // Step 2: Index Compression for each batch ํง, query ํ, and head โ do C ํง,ํ,โ = ร ํโ1 ํ=0 ํํ _ํํํกํํฃํ ํง,ํ,ํ,โ Sum of active blocks for each key block ํ do if ํํ _ํํํกํํฃํ ํง,ํ,ํ,โ is ํํํขํ then ํํํฅ_ํกํ_ํ ํํํก ํง,ํ,ํ,โ = ํ else ํํํฅ_ํกํ_ํ ํํํก ํง,ํ,ํ,โ = ํ Fill inactive with ํ end if end for I[ํง, ํ, :, โ]= Sort(ํํํฅ_ํกํ_ํ ํํํก ํง,ํ,:,โ ) Stable sort to compact indices end for return I, C 19 Algorithm 3 Block Sparse Attention Kernel Input: Query ํ, Key ํพ, Value ํ , Block indices Idx, Valid counts C, scale ํ Output: Output ํ, Log-sum-exp ํฟ for each query tile ํผ โ 0, . . . , ํฟ ํ ํํผํฟํธ โ 1 do // Initialization for Online Softmax ํ ํ =โโ, โ ํ = 0, ํํ= 0 ํ ํผ = Load(ํ, tile ํผ) ํ ํํํกํํฃํ = C[ํผ] Get count of salient blocks // Iterate only through identified salient blocks for ํํํฅ= 0 to ํ ํํํกํํฃํ โ 1 do ํต ํํ = Idx[ํผ, ํํํฅ] Target block index ํํ _ํํํํ=(ํต ํํ == ํผ) Check for diagonal/causal block // Process key/value within the salient block for each key tile ํฝ within block ํต ํํ do ํพ ํฝ ,ํ ํฝ = Load(ํพ,ํ, tile ํฝ) qk=(ํ ํผ ยท ํพ โค ํฝ )ยท ํยท log 2 ํ if ํํ _ํํํํ is ํํํขํ then qk= ApplyCausalMask(qk) end if // Online Softmax Update ํ ํํํค = max(ํ ํ , max(qk, axis= 1)) ํ= 2 (qkโํ ํํํค ) โ ํํํค = โ ํ ยท 2 (ํ ํ โํ ํํํค ) + ร (ํ, axis= 1) ํํ= ํํยท 2 (ํ ํ โํ ํํํค ) + ํยท ํ ํฝ ํ ํ = ํ ํํํค , โ ํ = โ ํํํค end for end for // Final Normalization and Storage ํ[ํผ]= ํํ/โ ํ ํฟ[ํผ]= ํ ํ + log 2 (โ ํ ) end for return ํ, ํฟ 20