Flash-MSA: Accelerating Million-Token Training With Sparse Attention Kernels

[Github] [MiniMax Paper] [Trainer]

Flash-MSA vs Flash-Attention isolated train step.¹

I implemented training kernels for Minimax Sparse Attention in CuTeDSL for Hopper and Blackwell GPUs. All of the dev work was done on Spheron H100 and B200 rentals and with the help of referencing FA4, MSA inference, and Codex.

Disclaimer: This is not an official implementation and I am not affiliated with MiniMax

About MSA

MSA is similar to Deepseek Sparse Attention, with some core changes

Fig. 1 from the MSA Paper

1. Blockwise sparsity

Instead of the proxy attention selecting individual KVs for the main attention, it selects them in blocks of 128 using max-pooling over the proxy scores. This introduces some nice caching properties for the kernels.

2. GQA instead of MLA for the main attention

This one is particularly important because no western labs, to the best of my knowledge, have adopted MLA into their training, making the prevailing sparse attention formulation in frontier models like GLM-5.2, DSv4, which are fit to MLA, inaccessible to models here.

3. Group-wise specialization of proxy heads

Replacing MLA with GQA introduces independent groups of queries within each layer, giving us the option to select a different subset of KVs with each proxy head instead of summing and scoring for the entire attention layer like DSA does. There is some evidence suggesting attention heads organically attend to different tokens, so this change should increase main attention expressivity.

Kernel Design

High level overview of kernel sequence

To run MSA efficiently we need to repeat as little work as possible and not overload the registers / shared memory too much. In addition to regular flash registers (Q tile, KV tile, O accumulator, LSE accumulator), we have to take into account streaming top-k accumulators in the forward. In the backward, we have to make space for a double-attention combined pass so we can calculate main attention grads and proxy attention grads, since proxy grads require access to both proxy and main attn probs. One nice benefit of block-sparsity is that since we only have to cache the indices of blocks instead of individual tokens like in DSA, it is feasible to store block indices all the way through until the backward - meaning in the entire train step, only the proxy forward is quadratic w.r.t. context length, everything else uses the cached sparse blocks from the proxy forward.

Forward

Order of operations is proxy attention -> sparse main attention -> send main attention output to next layer, save main LSE for backward.

Proxy attention

The proxy dot-product is a little different from regular Flash Attn as we don’t have to accumulate output anymore, but we do have to keep track of the top k attention scores and their respective indices as we stream across keys. Unlike Flash I also do not accumulate LSE for the backward and instead run a very cheap recompute of proxy dot-product over sparse activations to get the LSE during the backward. This was faster than fusing LSE+topk in the forward for me in practice. As each tile of QK^T is calculated, I grab the causal local max score for each chunk and do an insertion sort into the current top-k values for each query row, held in registers. I had to slice key blocks in half to make space for these top-k registers. Also, MSA dictates that the local block for each token must be unmasked (sliding-window style), so I set the attention scores for the local KV block for each query to inf.

Main attention

The main attention is just a block-sparse typical SDPA forward. This has been done before in MoBA, so I copied their clever trick to re-parameterize block sparse attention into varlen flash and converted this code to CuTeDSL.

Backward

Since we saved block indices from the forward and only train both attentions on the sparse KV activations, the backward can be run in linear time. First we pull our cached block_indices and invert the mapping of $B$[batch,proxy head,query,top_k_slot]->[key block] into $B^{\ast}$[batch,proxy head,key block]->[queries that use this block]. We use $B^{\ast}$ to schedule query chunks to optimize for reuse of shared sparse KV blocks.

Then we run a quick proxy attention pass over the block_indices to get the proxy LSE, then we stream tasks to load chunks of QKV, Q_proxy, K_proxy, and the main lse stashed from the forward. To account for loading so many heads into the registers we have to reduce the size of Q chunks and KV chunks we use at a time. In each stream calculate main attn and proxy attn scaled dot-product scores, compute dQ,dK,dV, then compute proxy dQ,dK from the KL training term.

KL Divergence Loss

Recall the original KL loss term from DSA is $L^\iota = \sum_t{D_{KL}(p_t,s_t \Vert Softmax(I_t, s_t))}$

Materializing both indexer and main attn prob. distributions to accumulate KL divergence would require many read/writes to shared mem and usage of additional registers that would significantly slow down training. Fortunately, there is a trick we can use to backprop atomically and still be mathematically equivalent to a full KL loss.

With the proxy attn prob as $p_{px}$ and main attn prob as $p$, expand the KL term:

Use log rules to expand again:

We want to calculate grads into the next latent which is the pre-softmax attention score at position i (not t), $z_{px,i}$

Main probs $p_t$ are detached from the KL-loss graph, so they are constant in this partial.

We know the softmax logprob partial of a softmax output at position t ($p_{px,t}$) w.r.t. pre-softmax logit ($z_{px,i}$) is $\frac{\partial log(p_{px,t})}{\partial{z_{px,i}}} = \delta_{it}-p_{px,i}$

Kronecker delta function $\delta_{it}$ is only nonzero at i==t, so $\sum_t{p_t\delta_{it}}=p_i$.

Because $p_t$ is a probability distribution, $\sum_t{p_t}=1$.

In other words, gradient to proxy score from KL loss = proxy prob - main prob. This is the term I use in the kernel to calculate proxy gradients without needing to ever fully materialize KL.

Note about scheduler: For clarity I will refer to an “MSA group” of attention heads as the subset of main attn query heads assigned to each proxy query head. Note this is different than the GQA groups which are the main attn query heads grouped to their respective main attn key head. Since I schedule by mapping each proxy head to its respective main attention GQA group, the current kernels require that MSA groups >= GQA groups. There is probably a simple way to invert the mapping for the scheduler/fused backward, but this is necessary in cases where the model has more KV heads than proxy heads. However I expect stable training to require at least 4 MSA groups and in this current regime of transformers I have a strong contempt for models with >1024 KV cache/layer so I am not interested in implementing this path.

Warmup kernels

In warmup mode, the main attention forward is dense and does not use block_indices, so the proxy forward can be skipped entirely. For the main attention warmup forward kernel I just call flash and save its returned output and lse, and return a placeholder KL. In the backward I call dense flash on the indexer just to get the LSE, then reuse the fused proxy+main attention backward from the sparse MSA kernels.

Correctness

To verify correctness of the the kernel forward and backward, I implemented MSA in eager Pytorch and swept for cosine similarity between both implementations' forward outputs and backward grads over several configs. The sweep is run in bf16 precision and the backwards include both target output loss and the internal KL loss. Typically for bf16 the tolerance for precision is ±0.02.

What’s next

Optimal tiling

There is probably some optimal tiling algorithm to order the query rows in a way that minimizes the number of tiles required to cover the entire SxS attention matrix. Or rather, since it does not matter which position inside a chunk a query row is in as long as it’s in the chunk, there should be a optimal grouping algorithm to group query rows, within a query head, such that the area of the its block-sparse attention mask is minimized. I think this is an NP-hard problem to completely solve but there can be some fuzzier ways of saving time here, maybe k-means or some hypergraph partitioning approach could work.

Faster top-k selection

Perhaps the biggest returns will come from optimizing the only quadratic kernel in the training suite, which is the indexer selection. Right now it suffers from register spillage to shared memory and low thread occupancy from its memory demands.

Router architectural speedups

GLM has already proved it is stable and much faster to use IndexCache to share proxy heads across layers. Also, the indexer seems to always be served in low-precision during inference, so training it in low precision could help address train-inference matching and speed up training greatly if it was stable.

Context parallelism

To scale LLM training at 1M+ context, some form of CP is mandatory or the trainer will quickly run out of memory. There are a few options here

1. Headwise all-gather

Since MSA groups run independently of each other in both fwd/bwd, it is trivial to use TP-style CP folding for CP rank up to num_proxy_heads, where each device holds (Seq len / CP rank) tokens and its MSA group(s), then does an A2A comm of the full sequence before calling MSA. In fact, you could probably do this right now in the current Megatron MSA fork.

2. Ring

Implementing Ring-style parallelism here is more difficult but probably the optimal way of doing CP for MSA as it allows for better overlap and higher CP rank than a2a. Ring would require something like overlap-exchange within the proxy forward with a way to stream the top-k values and indices across devices, then broadcast back to all devices, then a clever sparse-key host device lookup and retrieval for the main attention across devices. I do not know how to wire this into the kernel so I will have to contact my local CP expert before putting out this core feature, but if anything this will be the next blog post.

Note about joint indexer-main attention training

While the paper does include a formulation of MSA where a value and output proj are added to the proxy head then the proxy output is added to the main attention’s output to introduce grads from CE loss into the proxy weights and allegedly boost knowledge-type evals, I think implementing this will slow down training greatly. Adding new heads and accumulators to the fwd/bwd threads would increase register and shared memory pressure, increase FLOPs and decrease parallelizability. MSA also states themselves in Table 6 of their paper that proper warmup can make up for not training the indexer with CE loss.

Sweep across Top-k

I thought it would be interesting to visualize the sparsity benefit as blocks decrease. I want to do some more sweeps across GQA and proxy MQA configurations when I get compute. I would also like to continued pre-train an existing GQA base model like Qwen3 on MSA to test the conversion, this will require some more compute.