Accelerating Attention with Basis Decomposition

Jialin Zhao

cs.LGOct 2, 2025

Accelerating Attention with Basis Decomposition

Authors: Jialin Zhao

Organizations: Department of Computer Science Tsinghua University

Abstract

Attention is a core operation in large language models (LLMs). We present BD Attention (BDA), a lossless algorithmic reformulation of attention. BDA is enabled by a simple matrix identity from Basis Decomposition (BD), which restructures multi-head projections into a compact form while preserving exact outputs. Unlike I/O-aware system optimizations such as FlashAttention, BDA provides a mathematically guaranteed acceleration that is architecture-agnostic. On DeepSeek-V2-Lite (16B, FP16), BDA requires only 4s of offline preparation with no retraining required and, on modern GPUs, achieves 34% faster key/value projections and 25% smaller weights, while increasing perplexity (PPL) by just 0.02% (FP16) or 0.0004% (FP32), a negligible effect on model performance. These results position BDA as a theoretically exact method for lossless attention acceleration that is complementary to existing engineering-level optimizations. Our code is available at https://github.com/abcbdf/basis-decomposition-official.

Explore similar work

SparDA: Sparse Decoupled Attention for Efficient Long-Context LLM Inference
Jun 3, 2026Yaosheng Fu, Guangxuan Xiao, Xin Dong +2Dynamic Sparse Attention LLM Inference Efficiency
Kascade: A Practical Sparse Attention Method for Long-Context LLM Inference
Dec 18, 2025Dhruv Deshmukh, Saurabh Goyal, Nipun Kwatra +1Dynamic Sparse Attention LLM Inference Efficiency
Approaching I/O-optimality for Approximate Attention
May 22, 2026Pál András Papp, Aleksandros Sobczyk, Anastasios ZouziasQuadratic Attention Matrix Multiplication

Jun 3, 2026 · cs.CLJ/K move · Enter open · S save

SparDA: Sparse Decoupled Attention for Efficient Long-Context LLM Inference

Yaosheng Fu, Guangxuan Xiao, Xin Dong, Song Han+1

1NVIDIA · 2Thinking Machines Lab · 3ByteDance Seed · 4MIT

Sparse attention reduces compute and memory bandwidth for long-context LLM inference. However, two key challenges remain: (1) KV cache capacity still grows with sequence length, and offloading to CPU memory introduces a PCIe transfer bottleneck; (2) the sparse selection step itself retains

O(T^2)

complexity and can dominate attention cost at long contexts. We propose SparDA, a decoupled sparse attention architecture that introduces a fourth per-layer projection, the Forecast, alongside Query, Key, and Value. The Forecast predicts the KV blocks needed by the next layer, enabling lookahead selection that overlaps CPU-to-GPU prefetch with current-layer execution. Because Forecast is decoupled from the attention query, our GQA implementation uses one Forecast head per GQA group, reducing selection overhead versus the original multi-head selector. SparDA adds

<

0.5% parameters and trains only the Forecast projections by matching the original selector's attention distribution. On two sparse-pretrained 8B models, SparDA matches or slightly improves accuracy and delivers up to 1.25

\times

prefill speedup and 1.7

\times

decode speedup over the sparse-attention offload baseline. By enabling larger feasible batch sizes on a single GPU, SparDA further reaches up to 5.3

\times

higher decode throughput than the non-offload sparse baseline. Our source code is available at https://github.com/NVlabs/SparDA.

Dynamic Sparse Attention LLM Inference Efficiency Throughput

Open paper Ask about it PDF

Abstract

Explore similar work

SparDA: Sparse Decoupled Attention for Efficient Long-Context LLM Inference

Kascade: A Practical Sparse Attention Method for Long-Context LLM Inference

Approaching I/O-optimality for Approximate Attention