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

• URL: http://arxiv.org/abs/2603.06199v1
• Date: Fri, 06 Mar 2026 12:12:46 GMT
• Title: FlashPrefill: Instantaneous Pattern Discovery and Thresholding for Ultra-Fast Long-Context Prefilling
• Abstract summary: FlashPrefill is a framework enabling ultra-fast prefilling via instantaneous pattern discovery and thresholding.<n>FlashPrefill achieves a substantial leap in efficiency, delivering an unprecedented 27.78x speedup on 256K sequences.<n>Unlike existing methods that incur efficiency degradation on shorter contexts, FlashPrefill maintains a 1.71x speedup even at a 4K context length.
• Score: 43.057651076580264
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• FlashPrefill V2: Block-Sparse Prefill Attention for Long-Context LLM Serving [45.624568309628756]
  Long-context modeling is a pivotal capability for Large Language Models.<n>Our previous work, FlashPrefill, mitigates this cost through instantaneous pattern discovery and max-based dynamic thresholding.<n>FlashPrefill V2 evolves FlashPrefill from a prototype toward practical long-context serving along three dimensions.
  arXiv  Detail & Related papers  (2026-08-20T08:02:55Z)
• PulseCol: Periodically Refreshed Column-Sparse Attention for Accelerating Diffusion Language Models [61.39458217121294]
  Inference in diffusion large language models (dLLMs) is computationally expensive.<n>Recent sparse attention methods for dLLMs mitigate this cost via block-sparse computation.<n>We introduce PulseCol, a periodically refreshed column-sparse attention method.
  arXiv  Detail & Related papers  (2026-05-20T07:06:54Z)
• Training-free Context-adaptive Attention for Efficient Long Context Modeling [57.703159205740185]
  Training-free Context-adaptive Attention (TCA-Attention) is a training-free sparse attention mechanism that selectively attends to only the informative tokens for efficient long-context inference.<n>TCA-Attention achieves a 2.8$times$ speedup and reduces KV cache by 61% at 128K context length while maintaining performance comparable to full attention.
  arXiv  Detail & Related papers  (2025-12-10T01:54:57Z)
• LiteAttention: A Temporal Sparse Attention for Diffusion Transformers [1.3471268811218626]
  LiteAttention exploits temporal coherence to enable evolutionary computation skips across the denoising sequence.<n>We implement a highly optimized LiteAttention kernel on top of FlashAttention and demonstrate substantial speedups on production video diffusion models.
  arXiv  Detail & Related papers  (2025-11-14T08:26:55Z)
• InfLLM-V2: Dense-Sparse Switchable Attention for Seamless Short-to-Long Adaptation [56.694702609077495]
  Long-sequence processing is a critical capability for modern large language models.<n>InfLLM-V2 is a trainable sparse attention framework that seamlessly adapts models from short to long sequences.<n>In experiments, InfLLM-V2 is 4$times$ faster than dense attention while retaining 98.1% and 99.7% of the performance.
  arXiv  Detail & Related papers  (2025-09-29T12:08:33Z)
• SpecExtend: A Drop-in Enhancement for Speculative Decoding of Long Sequences [11.225649178057695]
  SpecExtend improves speculative decoding on long sequences without additional training.<n>To improve both draft accuracy and speed on long inputs without retraining, we propose Cross-model Retrieval.<n>SpecExtend accelerates speculative decoding by up to 2.84x on 16K-token long summarization and up to 3.86x on long reasoning.
  arXiv  Detail & Related papers  (2025-05-27T06:30:00Z)
• FlashBias: Fast Computation of Attention with Bias [70.44379606190569]
  Attention with bias has been widely deployed in vision, language, protein-folding and other advanced scientific models.<n>It disrupts the tightly fused memory-compute pipeline that underlies the speed of accelerators like FlashAttention.<n>This paper presents FlashBias based on the low-rank compressed sensing theory, which can provide fast-exact computation for many widely used attention biases.
  arXiv  Detail & Related papers  (2025-05-17T15:12:50Z)
• Faster Causal Attention Over Large Sequences Through Sparse Flash Attention [45.18552512844457]
  We extend FlashAttention to accommodate a large class of attention sparsity patterns. We increase the training speed of a transformer language model by $2.0times$ and $3.3times$ for sequences of respectively $8k$ and $16k$ tokens.
  arXiv  Detail & Related papers  (2023-06-01T21:33:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.