flash-prefill

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:

1. 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
2. Block Approximation: Computes block-pair importance via fused 2D-reduction kernels, reducing memory traffic from O(L²/B) to O((L/B)²)
3. 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.

# Compute block-level attention scores
 ():
    
    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