PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2609.00097v1cs.LGcs.AI

TL;DR

Long-context decoding is limited by KV-cache memory traffic and the trade-offs of metadata-based importance estimation and adaptive selection. FFD addresses these issues with fused content-aware scanning, low-bit quantization, and top-δ filtering. It reports preserved accuracy with up to 11.6× kernel-level speedup and up to 2.37× end-to-end throughput improvement, while limitations remain for MLA architectures and broader causal validation.

  • Problem

    Long-context decoding is constrained by memory bandwidth, while sparse-attention methods trade metadata overhead or information distortion against adaptive-selection inefficiency.

  • Method

    FFD fuses selection and computation, uses low-bit K-cache representations for content-aware scanning, and applies top-δ filtering for distribution-adaptive sparsity.

  • Results

    FFD maintains LLM performance on RULER and LongBench while achieving up to 11.6× kernel-level speedup, scaling to 256K context, and up to 2.37× end-to-end throughput increase.

  • Takeaways & Limitations

    FFD supports training-free, plug-and-play long-context decoding with high-ratio sparsity without sacrificing reported accuracy.

  • Takeaways & Limitations

    Validation covers Llama and Qwen architectures with GQA; applicability to MLA architectures has not yet been assessed.

Abstract

from arXiv · show

The development of long-context Large Language Models (LLMs) is constrained by the memory bandwidth bottleneck and quadratic complexity of the attention mechanism during decoding. To overcome the inherent trade-offs between the memory overhead of metadata-based metrics and the computational inefficiency of adaptive selection strategies, we present Faster Flash Decoding (FFD), a novel hardware-algorithm co-design framework designed to break the memory wall in long-context decoding. FFD integrates the selector and computer into a fully fused kernel, replacing external metadata indices with content-aware scanning via low-bit quantization. Furthermore, we introduce the top-delta strategy, which dynamically filters blocks to achieve distribution-adaptive sparsity without global synchronization. Offering a training-free and plug-and-play solution, FFD also enables the reuse of scanning results for computation, achieving up to 11.6x kernel-level speedup and scaling to 256K context length, with 2.37x end-to-end throughput improvement. Empirical validation on RULER and LongBench confirms that FFD maintains model accuracy while delivering high-ratio sparsity, with code available at https://github.com/qluoluo/faster-flash-decoding

1 Introduction

FFD targets the memory-bandwidth bottleneck of long-context decoding by fusing selection and computation, replacing metadata-based indexing with low-bit content-aware scanning and adaptive top-δ filtering.

  • Motivation: Long-context decoding is constrained by quadratic attention complexity, linear KV-cache growth, and HBM bandwidth requirements.Each generated token reloads the KV cache, making IO the primary bottleneck during autoregressive decoding.
  • Motivation: Existing sparse-attention methods separate selection from computation and face trade-offs between metadata overhead, information distortion, and adaptive-selection inefficiency.The selector’s intermediate computations cannot be reused by the computer in the decoupled workflow.
  • FFD framework: FFD fuses the selector and computer, using low-bit K-cache representations for content-aware scanning and reusing scan results during computation.The framework replaces extra metadata with quantized representations and residuals.
  • FFD framework: Top-δ dynamically filters attention blocks by relative contribution, combining distribution adaptivity with parallel-execution efficiency.It avoids the fixed budget of top-k and the global synchronization and sorting overhead of top-p.
  • Results: 11.6× kernel-level speedup and up to 2.37× end-to-end throughput increase are reported, with scaling to 256K context and preserved benchmark performance.The reported solution is training-free and plug-and-play, with validation on RULER and LongBench.

2 Related Work

Prior work addresses long-context attention through IO-aware exact attention, dynamic sparsity, and KV-cache quantization, but each line emphasizes different efficiency or fidelity trade-offs.

  • Hardware-Aware Exact Attention: FlashAttention, FlashDecoding, and FlashDecoding++ reduce HBM access and parallelize attention computation, forming the hardware-aware foundation for FFD.FFD inherits the spirit of kernel fusion from these exact-attention systems.
  • Dynamic Sparse Attention: Dynamic sparse-attention methods face separate challenges in estimating token importance and filtering subsets efficiently.History-based methods can discard tokens that become relevant later, while dynamic retrieval methods pursue alternative importance estimates.
  • KV Cache Quantization: KV-cache quantization compresses keys and values primarily for memory capacity, typically dequantizing them before higher-precision attention computation.FFD instead repurposes low-bit representations as scanning proxies for sparse retrieval.

3 Method

FFD combines hybrid K-cache quantization, pseudo-max-based top-δ filtering, fine-grained refinement, and fused execution to support adaptive sparse decoding without global synchronization.

  • 3.1 Content-Aware Scanning via Low-Bit Quantization: FFD decomposes each key into a 2-bit quantized thumbnail for high-throughput scanning and an 8-bit residual for refinement.Selected candidates are reconstructed to near-FP16 precision for exact computation.
  • 3.2 Top-δ Selection Criterion: The top-δ criterion retains tokens whose scores lie within δ of the maximum attention score, adapting the retrieval budget to attention-distribution sharpness.For δ = 5, discarded tokens contribute less than e^-5 ≈0.67% of the peak attention mass.
  • 3.2 Top-δ Selection Criterion: A pseudo-max estimated from sink tokens and local context replaces the global maximum, enabling locally computed thresholds and independent parallel KV-block processing.This bypasses the global reduction bottleneck associated with strict top-δ evaluation.
  • System optimization: FFD uses fused kernels and full-chain CUDA graphs, with block-wise recapture to accommodate dynamic KV-cache growth.The implementation keeps 99% of steps within a CUDA Graph and recaptures only when the number of full KV blocks changes.
  • Execution pipeline: The decoding pipeline scans quantized keys, filters blocks against the pseudo-max threshold, and loads residual keys and values only for passing blocks.Fine-grained refinement computes selected-token scores with near-FP16 precision.

4 Experiments

FFD is evaluated for efficiency, scalability, and long-context quality across GPUs, context lengths, and benchmarks. It delivers substantial kernel and end-to-end speedups while preserving strong downstream performance.

  • Evaluation Setup: FFD is evaluated on RTX 4090 and H100 GPUs using δ values of 5 and 7, with kernel latency, throughput, and downstream quality measurements.The evaluation covers kernel microbenchmarks, end-to-end generation, RULER, and LongBench.
  • Kernel Efficiency: 11.6× kernel-level speedup and scaling to 256K context demonstrate FFD’s efficiency advantage over FlashAttention-2.At 256K, FFD δ = 5 and δ = 7 average 0.17 ms and 0.21 ms versus 1.12 ms for FlashAttention-2.
  • End-to-End Throughput: 2.37× throughput improvement over FlashAttention-2 is achieved on RTX 4090 at 16K context, where FFD reaches 51.8 tokens/s.On H100, FFD reaches 87.0 tokens/s at 16K and achieves 1.96× speedup over FlashAttention-2.
  • Downstream Performance: FFD maintains near-baseline RULER performance at 32K context, including 100.0 on SK-1/SK-2, 99.0 on SK-3, and 98.4 versus 99.6 on VT.These results cover retrieval and reasoning tasks against the dense Llama-3.1-8B-Instruct baseline.
  • Downstream Performance: FFD (δ = 7) achieves the highest LongBench aggregate score among compared methods, with an overall average of 26.35 across six categories.LongBench evaluates 21 datasets spanning six long-context understanding categories.
  • Ablation and Generalization: At matched ∼27.3% keep ratios, top-δ is 2× faster than top-k and 25× faster than top-p, while FFD also generalizes to Qwen2.5.On Qwen2.5-7B-Instruct, FFD reaches 85.90 RULER AVG and 30.11 LongBench AVG, exceeding the listed baselines.

5 Discussion

FFD improves retrieval quality and preserves attention structure while achieving adaptive, high-ratio sparsity. Its evaluation also identifies architectural and validation boundaries for the method.

  • Retrieval Quality: FFD achieves higher recall than Quest across sparsity ratios and minimizes LSE error, preserving retrieved-token quality and softmax stability.Recall compares sparse and dense attention outputs; LSE error measures maximum absolute error in the normalization term.
  • Attention Structure: FFD consistently maintains higher Spearman correlation than Quest across layers, preserving the relative ordering of attention scores.The layer-wise comparison indicates less degradation than Quest’s bounding-box approximation.
  • Threshold Approximation: FFD estimates its threshold with a Pseudo-Max from sink and local tokens, avoiding a global reduction.Rare underestimation is described as fail-safe because the resulting lower threshold retains tokens selected by the ideal global maximum.
  • Sparsity Analysis: 82% and 73% average sparsity are achieved under δ = 5 and δ = 7 respectively, with no reported accuracy sacrifice.Sparsity is layer-wise adaptive and operates with a lower compute budget than dense attention.
  • Limitations: Head-wise sparsity adaptation has not been systematically validated across diverse task distributions.The current characterization uses controlled single-sample statistics.
  • Limitations: FFD’s applicability to MLA-style architectures remains unassessed, and fine-grained latency within the fused execution path is deferred.Validation covers Llama and Qwen architectures using grouped-query attention, while the internal fused-path breakdown remains future work.

6 Conclusion

FFD reframes sparse attention as geometric filtering rather than metadata indexing. Its 2-bit scanning and attention-sink thresholding support adaptive selection and a compute-for-I/O trade-off for long-context inference.

  • Conclusion: FFD uses 2-bit quantization for high-fidelity scanning and attention sinks for adaptive thresholding instead of rigid top-k budgets.The conclusion characterizes this design as geometric filtering rather than metadata indexing.
  • Conclusion: FFD suggests prioritizing compute-for-I/O trade-offs by spending inexpensive FLOPs on low-bit scanning to reduce HBM bandwidth demands.This conclusion frames bandwidth reduction as the practical implication for future long-context inference.

Impact Statement

FFD uses a non-zero 2-bit mid-rise quantizer and theoretical error bounds to support content-aware scanning, while optimizing decode for memory bandwidth. Its 2+8 configuration improves kernel speed and is presented without additional ethical concerns.

  • Impact: The work reports no additional ethical concerns because it involves neither human subjects, personal information, nor sensitive content.
  • Quantization Design: FFD’s 2-bit mid-rise quantizer uses a non-zero codebook to maximize limited representational capacity for dense LLM key vectors.The scheme avoids wasting a quantization bin on zero and aims to prevent information collapse.
  • Error Analysis: As head dimension increases, the probability that quantization error exceeds the selection safety margin decays exponentially.FFD sets an operational threshold above the ideal threshold using a safety buffer.
  • Error Analysis: The scanner approximates attention scores with 2-bit quantized keys, modeling quantization noise as independent mean-zero sub-Gaussian variables.The approximation uses the exact query and key vectors plus a quantization-noise term.
  • Decode Efficiency: 11.6× kernel-level speedup is achieved with fused decode processing, while the 2+8 configuration is motivated as bandwidth-optimal for long-context decoding.The 2-bit scan uses one-quarter the I/O of 8-bit scanning and half that of 4-bit scanning.

D Head-Wise Variation under Fixed Delta

Under a fixed δ, FFD exhibits substantial head-wise variation rather than uniform sparsity, and its selection becomes more conservative in proxy-error cases. These statistics are mechanistic rather than worst-case claims across task distributions.

  • Head-Wise Variation: 0.62% to 100% keep ratios across 1024 layer-head pairs show that FFD does not impose uniform sparsity.The standard deviation is 14.14 percentage points, while mean salient hit rate remains 87.45%.
  • Head-Wise Variation: FFD requires no early-layer full-precision KV-cache exception, unlike Quest and Twilight, which retain the first two layers to avoid accuracy collapse.
  • Scope: The head-wise statistics come from one LongBench sample with δ = 5 and should not be interpreted as worst-case behavior across all task distributions.
  • Failure-Prone Conditions: 13.15% mean keep ratio in proxy-error cases rises from 2.43% in regular cases, while salient hit rate increases from 63.74% to 74.67%.The response is conservative retrieval: threshold deviations lead selection to retain more blocks rather than drop salient ones.

F Cross-Architecture Generalization: Qwen2.5

FFD generalizes beyond the Llama architecture to Qwen2.5-7B-Instruct without architecture-specific tuning. It outperforms the compared sparse baselines on RULER and LongBench averages and retains strong retrieval performance.

  • Qwen2.5 Generalization: FFD maintains a clear accuracy advantage over sparse baselines on Qwen, confirming generalization beyond Llama without architecture-specific tuning.
  • Task-Level Results: FFD leads Twilight on key Qwen RULER retrieval subtasks, including MK-3 at 87 versus 44 and MQ at 98.3 versus 66.3.Its stronger LongBench average is largely driven by the M-Doc and Syn categories.

G Component-wise Ablation Study

A controlled ablation isolates scan precision, selection rule, and execution path, showing that top-δ and system-level fusion jointly improve accuracy and throughput. The results indicate that quantization is beneficial when paired with top-δ, while fusion gains are amplified by the adaptive selector.

  • Scan precision: 2-bit scanning reduces throughput from 17.4 to 14.8 tok/s under top-k because compute-bound sorting overhead outweighs its memory savings.The quantized scan becomes beneficial when paired with top-δ, which reduces selection to a scalar comparison.
  • Scan precision: Pairing 2-bit scanning with top-δ increases throughput from 21.6 to 24.7 tok/s, making the reduced memory footprint an asset.This is the V2 versus V4 comparison in the component ablation.
  • Execution path: Fusion alone provides a 1.4× gain under top-k, but the same system optimizations provide a 2.2× boost when combined with top-δ.The comparison shows synergistic amplification between the algorithmic selection rule and fused execution with CUDA Graph capture.

H Component Accuracy Ablation on RULER

The RULER breakdown shows that fixed-budget top-k selection severely harms CWE, whereas top-δ substantially restores performance. This pattern reflects CWE’s need for distribution-aware sparsity when counting word frequencies across the full context.

  • RULER subtask results: CWE scores only 24.6 and 25.8 with fixed-budget top-k selection, but top-δ restores scores to 68.2–69.5.The breakdown covers four non-fused variants from the component ablation study.
  • RULER subtask results: CWE requires distribution-aware adaptive sparsity because it counts word frequencies across the full context.The passage identifies this requirement as the explanation for top-k’s degradation and top-δ’s recovery.
Loading 2609.00097v1…