| name | flash-prefill |
| title | FlashPrefill: Instantaneous Pattern Discovery for Ultra-Fast Long-Context Prefilling |
| version | 0.0.2 |
| engine | skillxiv-v0.0.2-claude-opus-4.6 |
| license | MIT |
| url | https://arxiv.org/abs/2603.06199 |
| keywords | ["LLM Inference","Attention","Sparse Attention","Long Context","Prefilling"] |
| description | Accelerates long-context LLM prefilling by identifying sparse attention patterns without expensive scoring, using block-level approximations and dynamic thresholding. Achieves 27.78x speedup at 256K tokens while maintaining accuracy. |
FlashPrefill: Achieving 27x Speedup via Instant Sparse Attention Pattern Discovery
Long-context LLM inference suffers from quadratic attention complexity during prefilling. Computing full attention over sequences of 100K+ tokens incurs enormous memory and compute costs. Existing sparse attention methods like Top-k and Top-p require expensive score computation, sorting operations, and handle long-tail distributions poorly, creating additional overhead that partially cancels efficiency gains.
FlashPrefill eliminates this overhead through instantaneous pattern discovery: identifying which attention blocks matter without materializing full score matrices. By using block-level proxies and max-based thresholding, it achieves 27.78x speedup on 256K sequences while maintaining near-identical accuracy.
Core Concept
Rather than computing all Q-K dot products then sorting (O(L²) or worse), FlashPrefill:
- Instant Pattern Recognition: Uses uniformly distributed query probes to simultaneously identify vertical (column-sparse), slash (diagonal), and block-sparse patterns from block-level statistics alone
- Block Approximation: Computes block-pair importance via fused 2D-reduction kernels, reducing memory traffic from O(L²/B) to O((L/B)²)
- Dynamic Thresholding: Replaces sorting with single-pass max reduction to determine pruning thresholds, avoiding cumulative summation overhead
The key insight: attention patterns are often predictable at block granularity without computing token-level scores. Vertical patterns (attending to few positions) and slash patterns (attending to sliding windows) can be identified from approximate block interactions.
Architecture Overview
- Block-Level Proxy Computation: Compute block-level attention scores using average-pooled keys/queries within each block
- Three Pattern Types Detected: Vertical (few columns), Slash (diagonal bands), Block (rectangular dense regions)
- Fused Kernel Implementation: Single-pass kernel computes all block interactions without intermediate materialization
- Physical Index Jumping: Use identified sparse block indices to implement block-sparse attention efficiently
Implementation Steps
The algorithm operates in three stages executed sequentially in a fused manner.
Stage 1: Block-Level Attention Approximation
Compute approximate block importance scores using pooled features. For a sequence of length L with block size B, create L/B "block queries" by averaging queries in each block.
():
seq_len = Q.shape[]
num_blocks = (seq_len + block_size - ) // block_size
Q_blocks = []
K_blocks = []
i (num_blocks):
start = i * block_size
end = ((i + ) * block_size, seq_len)
Q_blocks.append(Q[start:end].mean(dim=, keepdim=))
K_blocks.append(K[start:end].mean(dim=, keepdim=))
Q_blocks = torch.cat(Q_blocks, dim=)
K_blocks = torch.cat(K_blocks, dim=)
block_scores = torch.matmul(Q_blocks, K_blocks.t()) / math.sqrt(Q.shape[-])
block_scores
