burn-msa - MiniMax Sparse Attention
Block-sparse attention for the Burn deep learning
framework. Reduces attention from O(S_q × S_kv) to O(S_q × topk × block_size)
by selecting the top-K KV blocks per query position via a lightweight index branch.
Algorithm reference: MiniMax Sparse Attention.
Per-GQA-group top-k block selection with GPU-sync-free indexer. 5D batched matmul kernel launches one kernel per KV head instead of per-token per-head. Works on any Burn backend: CUDA, WGPU, NdArray.
Requirements
- Rust: ≥ 1.75
- Burn: 0.21
- GPU (optional): CUDA or Vulkan/Metal via WGPU
Install
Or in Cargo.toml:
[]
= "0.1"
Enable CUDA:
= { = "0.1", = ["cuda"] }
Quick start
use NdArray;
use ;
let device = Defaultdefault;
let cfg = new;
let module = new;
// Self-attention: Q, K, V from the same input
let x = random;
let result = module.forward;
let output = result.output; // [batch, seq, d_model]
// Cross-attention: separate Q and KV inputs
let q = random;
let kv = random;
let result = module.forward_cross;
// Dense GQA fallback (no sparsity)
let output = module.forward_dense;
Architecture
Input [B, T, D] ──→ IndexBranch ──→ TopKSelector ──→ SparseAttention ──→ Output
│ │ │
│ Q·K^T / √d_idx │ topk blocks │ gather K/V
│ per-block max │ per GQA group │ 5D matmul
│ │ │ softmax
│ │ │ output proj
- Index branch projects Q/K into low-dim space (
d_idx), scores each KV block via max-pooling. - TopK selector picks
topkhighest-scoring blocks per GQA group - GPU-sync-free. - Sparse attention gathers K/V from selected blocks via single batched gather, then 5D batched matmul for scores and output.
Configuration
| Field | Default | Description |
|---|---|---|
d_model |
1152 | Hidden size |
n_heads_q |
18 | Query heads |
n_heads_kv |
1 | KV heads (GQA factor) |
d_head |
64 | Head dimension |
d_idx |
32 | Index projection dimension |
block_size |
128 | Tokens per KV block |
topk |
16 | Blocks selected per query |
causal |
true | Causal masking |
use_kl_loss |
true | KL alignment loss for index branch |
kl_coeff |
0.1 | KL loss weight |
Performance
Benchmarked on RTX 5060 Ti, Burn 0.21 vs PyTorch 2.13.
Attention kernel (gather + matmul + softmax + output) is 1.2-8.2× faster across all 21 tested configs. Dense attention: 1.1-1.5× faster.
Full sparse forward (index branch + topk + attention) is faster for small configs and large-scale prefill, but on par or slightly slower for medium configs where the index branch overhead dominates. This gap comes from Burn's cubecl matmul vs PyTorch's cuBLAS for small matrix sizes. For long contexts (>32K) the attention kernel dominates and burn-msa wins decisively.
| Config | Burn CUDA | PyTorch CUDA | Attention speedup | Full sparse |
|---|---|---|---|---|
| small (d=128, seq=256) | 361 µs | 431 µs | 1.26× | 1.19× |
| large (d=512, seq=256, kv=4096) | 1,508 µs | 1,897 µs | 1.26× | 0.70× |
| xl (d=768, seq=512, kv=8192) | 26,028 µs | 29,772 µs | 1.14× | 0.92× |
| decode (d=512, seq=1, kv=64K) | 159 µs | 1,303 µs | 8.2× | 0.57× |
Training with KL alignment
let mut cfg = new;
cfg.use_kl_loss = true;
cfg.kl_coeff = 0.1;
let module = new;
let result = module.forward;
if let Some = result.kl_loss
KV-cache decoding
use MsaCache;
let cache = new;
let cache = cache.update;
Layout
src/
lib.rs Crate root, re-exports
attention.rs SparseAttention, 5D batched GQA kernel
index_branch.rs Low-dim Q/K projections, block scoring
topk.rs GPU-sync-free top-K block selector
module.rs MsaModule: unified forward API
config.rs MsaConfig with validation
loss.rs KL alignment loss
cache.rs KV-cache for incremental decoding
kernel/ Experimental cubecl kernels
tests/
basic.rs 22 unit + integration tests
bench.rs 10-section performance benchmarks
bench_vs_pt.rs Head-to-head PyTorch comparison
examples/
simple_msa.rs Minimal usage example
License
AGPL-3.0. See LICENSE.