🤖 machine learning

Faster Than Flash: Exploiting Attention Sparsity for Efficient Long-Context Decoding

Faster Flash Decoding (FFD) is a training-free, hardware-algorithm co-design framework that achieves up to 11.6x kernel-level speedup and scales to 256K context lengths by fusing selection and computation into a single kernel and employing a top-delta strategy for distribution-adaptive sparsity, all while maintaining model accuracy.

Original authors: Zhigeng Liu, Zhiyuan Ning, Ruixiao Li, Xiaoran Liu, Yuerong Song, Min Zhang, Ziwei He, Xipeng Qiu

Published 2026-09-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zhigeng Liu, Zhiyuan Ning, Ruixiao Li, Xiaoran Liu, Yuerong Song, Min Zhang, Ziwei He, Xipeng Qiu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of artificial intelligence, modern computer programs known as large language models have become remarkably skilled at understanding and generating human language. These systems work by predicting the next word in a sentence, one token at a time, building a coherent response step by step. However, as these models grow more capable, they face a significant physical hurdle when asked to process very long documents or conversations. The more context a model needs to remember, the more data it must constantly shuffle between its fast internal memory and its main storage. This constant movement of data creates a bottleneck, much like trying to fill a swimming pool with a garden hose while the drain is wide open. The computer spends most of its time waiting for information to arrive rather than actually thinking, which slows down the entire process and limits how much text a model can handle at once.

To solve this, researchers from Fudan University and the Shanghai Innovation Institute have developed a new method called Faster Flash Decoding. Their approach tackles the problem by changing how the model decides which pieces of information to keep and which to ignore. Instead of trying to read every single word in a massive document to find the relevant ones, the new system uses a clever shortcut. It first creates a tiny, compressed sketch of the entire history of the conversation. This sketch is so small that the computer can scan through it almost instantly. By looking at this sketch, the system can quickly identify which parts of the history are likely to be important and which can be safely ignored. Only after this quick scan does the model retrieve the full, detailed version of the selected parts to perform the final calculation. This two-step process allows the model to skip over vast amounts of irrelevant data without losing the ability to understand the core meaning of the text.

The researchers tested this method on powerful graphics cards, the kind used for high-end gaming and scientific computing, and found it to be dramatically faster than current standard techniques. When processing a context of 256,000 tokens, the new system reduced the time it took to generate a single token from over one millisecond to just a fraction of that. In terms of overall speed, the system generated text up to 2.37 times faster than previous methods while maintaining the same level of accuracy. The team verified this performance across a wide range of tasks, including complex reasoning and retrieving specific facts from long documents, confirming that the speed gains did not come at the cost of intelligence. The system works without needing to retrain the model, meaning it can be plugged into existing artificial intelligence systems immediately to improve their efficiency.

A key innovation in this work is the specific way the system filters information. Traditional methods often rely on fixed rules, such as keeping only the top ten most important words, or complex calculations that require the entire system to pause and synchronize before proceeding. The new method uses a dynamic threshold that adapts to the natural flow of the conversation. It looks for words that are significantly important compared to the most important word in the current context, allowing it to adjust how much it keeps based on how concentrated the attention is. This flexibility, combined with the use of extremely low-precision data for the initial scan, allows the computer to bypass the memory bottleneck that has long held back long-context processing. The result is a system that can handle massive amounts of text with a speed that was previously thought impossible without sacrificing the quality of the answers it provides.

Technical Summary: Faster Than Flash (FFD)

Problem Statement

The deployment of Long-Context Large Language Models (LLMs) is currently hindered by a severe "memory wall" during the autoregressive decoding phase. While the prefill phase is compute-bound, the decoding phase is strictly memory-bandwidth-bound. As sequence lengths grow, the standard attention mechanism requires reloading the entire Key-Value (KV) cache from High-Bandwidth Memory (HBM) for every token generation, creating a linear latency growth that limits throughput.

Existing sparse attention approaches attempt to mitigate this but face two primary dilemmas:

The Metric Dilemma: Methods relying on metadata (e.g., cluster centroids, geometric bounds) to estimate token importance incur additional memory overhead or suffer from information distortion.
The Selection Dilemma: Fixed-budget strategies (Top-k) lack adaptability to varying attention entropy, while distribution-adaptive strategies (Top-p) require global synchronization (softmax) and sorting, which breaks streaming pipelines and introduces significant overhead.

Methodology: Faster Flash Decoding (FFD)

FFD is a hardware-algorithm co-design framework that integrates the selector and computer into a fully fused kernel, eliminating the separation between filtering and computation. It addresses the above dilemmas through three core innovations:

1. Content-Aware Scanning via Low-Bit Quantization

Instead of storing extra metadata indices, FFD partitions the Key (K) cache into:

2-bit Quantized Thumbnails: Used for high-throughput, content-aware scanning to estimate attention scores.
8-bit Residuals: Stored to reconstruct the keys to near-FP16 precision for the final computation.
This approach eliminates the memory overhead of metadata while maintaining high information fidelity. The scanning phase operates at minimal arithmetic intensity, using the 2-bit data as a high-speed proxy for importance estimation.

2. The Top-δ Selection Strategy

FFD introduces a novel selection criterion that avoids the rigidity of Top-k and the global synchronization of Top-p.

Mechanism: A token $j$ is retained if its attention score $s_{ij}$ satisfies $s_{ij} \geq \tilde{m}_i - \delta$ , where $\tilde{m}_i$ is a pseudo-max estimate and $\delta$ is a relative threshold.
Pseudo-Max Approximation: To avoid the global reduction bottleneck of computing the true global maximum ( $m_i$ ), FFD estimates $\tilde{m}_i$ using only "sink tokens" (initial tokens) and local context tokens. Empirical analysis shows that attention distributions are dominated by these subsets, making the approximation robust.
Adaptivity: The threshold $\delta$ (e.g., 5 or 7) controls the allowable drop-off in attention probability mass (e.g., $\delta=5$ retains tokens contributing $>e^{-5}$ of the peak). This allows the sparsity ratio to adapt dynamically to the entropy of the attention distribution without global synchronization.

3. Fused Kernel and System Optimization

FFD is implemented as a fully fused Triton kernel comprising three stages:

Pseudo-max Estimation: Computes the threshold using sink and local tokens.
Top-δ Selection: Streams 2-bit keys, computes tentative scores, and filters blocks against the threshold.
Fine-Grained Refinement: For selected blocks, loads 8-bit residuals and values to compute exact attention scores.
To further reduce latency, the authors employ a Block-wise JIT capture strategy for CUDA Graphs. This allows the entire decoding step (including MLP and normalization) to be captured dynamically, amortizing compilation costs and eliminating CPU launch overheads for small batch sizes.

Key Results

Efficiency and Throughput

Kernel Speedup: On an NVIDIA RTX 4090, FFD achieves up to 11.6× kernel-level speedup compared to FlashAttention-2 at 256K context length.
End-to-End Throughput:
- RTX 4090: FFD achieves 2.37× higher throughput than FlashAttention-2 at 16K context (51.8 tokens/s vs. 21.9 tokens/s).
- H100: FFD achieves 1.96× speedup over FlashAttention-2 at 16K context (87.0 tokens/s vs. 44.5 tokens/s).
Scalability: The method scales effectively to 256K context lengths with linear latency growth but a significantly lower slope than dense attention.

Effectiveness and Accuracy

RULER Benchmark (32K Context): FFD maintains near-perfect performance on "Needle In A Haystack" tasks (100.0 on Single-Key retrieval) and achieves an aggregate score of 89.4 (with $\delta=7$ ), outperforming other sparse methods like Quest (73.9) and KIVI (82.3), and approaching the dense baseline (90.6).
LongBench: FFD achieves the highest aggregate score (26.35) among all sparse methods, surpassing Quest, Twilight, and KIVI, demonstrating that high-ratio sparsity does not sacrifice semantic fidelity.
Generalization: The method was validated on Qwen2.5-7B-Instruct, showing consistent improvements over baselines, indicating architecture-agnostic applicability.

Significance and Claims

The paper claims that FFD represents a paradigm shift in long-context decoding by rethinking sparse attention as geometric filtering rather than metadata indexing. Its primary significance lies in:

Breaking the Memory Wall: By integrating selection and computation, FFD enables the reuse of scanning results, turning the decoding bottleneck from a memory-bound problem into a compute-bound one where low-bit scanning is cheap.
Training-Free and Plug-and-Play: The solution requires no model retraining and functions as a drop-in replacement for standard attention kernels.
Hardware-Algorithm Co-Design: The work demonstrates that optimizing for specific hardware constraints (memory bandwidth) via algorithmic changes (2-bit quantization, pseudo-max approximation) yields superior results compared to purely algorithmic or purely hardware-based optimizations.

The authors conclude that future long-context inference should prioritize "compute-for-IO" trade-offs, leveraging cheap FLOPs on low-bit scanning to save expensive HBM bandwidth.