burn-msa 0.2.4

MiniMax Sparse Attention (MSA) - block-sparse attention with per-GQA-group top-k block selection for Burn
Documentation
use burn::tensor::backend::Backend;
use burn::tensor::{Int, Tensor};

/// Indices of the `k` largest elements along `dim` of a 3D tensor.
///
/// `argtopk` is a GPU reduce on cubecl backends; `topk_with_indices` must NOT
/// be used there — it falls back to a synchronous host sort (`sort_with_indices`)
/// whose read can fail inside autodiff under async load, panicking and
/// poisoning the CUDA context (subsequent kernels fail with
/// CUDA_ERROR_ILLEGAL_ADDRESS). Host backends (ndarray) keep `topk_with_indices`
/// since they implement no `argtopk`.
fn argtopk3<B: Backend>(x: Tensor<B, 3>, k: usize, dim: usize, device: &B::Device) -> Tensor<B, 3, Int> {
    if B::name(device).contains("cubecl") {
        x.argtopk(k, dim)
    } else {
        x.topk_with_indices(k, dim).1
    }
}

/// GPU-sync-free top-K block selector. Now accepts 4D tensor directly.
#[derive(Debug)]
pub struct TopKSelector {
    pub topk: usize,
    pub block_size: usize,
    pub force_local_block: bool,
}

impl TopKSelector {
    pub fn new(topk: usize, block_size: usize, force_local_block: bool) -> Self {
        Self {
            topk,
            block_size,
            force_local_block,
        }
    }

    /// `block_scores`: [batch, n_heads_kv, seq_q, n_blocks]
    /// Returns: [batch, n_heads_kv, seq_q, topk_actual]
    pub fn select<B: Backend>(&self, block_scores: Tensor<B, 4>) -> Tensor<B, 4, Int> {
        let [batch, h, seq_q, n_blocks] = block_scores.dims();
        let topk = self.topk.min(n_blocks);
        let device = block_scores.device();

        // Flatten batch and heads for topk
        let scores_3d = block_scores
            .permute([0, 1, 3, 2]) // [B, H, Nb, Sq]
            .reshape::<3, _>([batch * h, n_blocks, seq_q])
            .permute([0, 2, 1]); // [B*H, Sq, Nb]

        // `argtopk` is a GPU reduce (burn-cuda 0.21 implements ArgTopK);
        // `topk_with_indices` must NOT be used here — it falls back to a
        // synchronous host sort whose read can fail inside autodiff under
        // async load, panicking and poisoning the CUDA context (subsequent
        // kernels fail with CUDA_ERROR_ILLEGAL_ADDRESS).
        let indices_3d = if topk >= n_blocks {
            // k == size: every block is selected — no topk needed at all.
            Tensor::<B, 1, Int>::arange(0..n_blocks as i64, &device)
                .reshape::<3, _>([1, 1, n_blocks])
                .repeat_dim(0, batch * h)
                .repeat_dim(1, seq_q)
        } else if self.force_local_block && seq_q > 0 && n_blocks > 0 && topk > 1 {
            let q_pos =
                Tensor::<B, 1, Int>::arange(0..seq_q as i64, &device).reshape::<2, _>([seq_q, 1]);
            let local_block = q_pos.div_scalar(self.block_size as i64);
            let block_idx = Tensor::<B, 1, Int>::arange(0..n_blocks as i64, &device)
                .reshape::<2, _>([1, n_blocks]);
            let bias = local_block
                .equal(block_idx)
                .float()
                .mul_scalar(1e4)
                .unsqueeze::<3>();
            argtopk3(scores_3d.add(bias), topk, 2, &device)
        } else {
            argtopk3(scores_3d, topk, 2, &device)
        };

        let actual_topk = indices_3d.dims()[2];
        indices_3d.reshape::<4, _>([batch, h, seq_q, actual_topk])
    }
}