use burn::module::Module;
use burn::nn::{Initializer, Linear, LinearConfig};
use burn::tensor::activation;
use burn::tensor::backend::Backend;
use burn::tensor::{Int, Tensor};
use crate::config::MsaConfig;
#[derive(Module, Debug)]
pub struct SparseAttention<B: Backend> {
pub q_proj: Linear<B>,
pub k_proj: Linear<B>,
pub v_proj: Linear<B>,
pub out_proj: Linear<B>,
pub cfg: MsaConfig,
}
impl<B: Backend> SparseAttention<B> {
pub fn new(cfg: &MsaConfig, device: &B::Device) -> Self {
Self {
q_proj: LinearConfig::new(cfg.d_model, cfg.n_heads_q * cfg.d_head)
.with_bias(false)
.with_initializer(Initializer::XavierUniform { gain: 1.0 })
.init(device),
k_proj: LinearConfig::new(cfg.d_model, cfg.n_heads_kv * cfg.d_head)
.with_bias(false)
.with_initializer(Initializer::XavierUniform { gain: 1.0 })
.init(device),
v_proj: LinearConfig::new(cfg.d_model, cfg.n_heads_kv * cfg.d_head)
.with_bias(false)
.with_initializer(Initializer::XavierUniform { gain: 1.0 })
.init(device),
out_proj: LinearConfig::new(cfg.n_heads_q * cfg.d_head, cfg.d_model)
.with_bias(false)
.with_initializer(Initializer::XavierUniform { gain: 1.0 })
.init(device),
cfg: cfg.clone(),
}
}
fn to_4d(t: Tensor<B, 3>, n_heads: usize, d_head: usize) -> Tensor<B, 4> {
let [batch, seq, _] = t.dims();
t.reshape::<4, _>([batch, seq, n_heads, d_head])
.swap_dims(1, 2)
}
pub fn forward_sparse(
&self,
q: Tensor<B, 3>,
k: Tensor<B, 3>,
v: Tensor<B, 3>,
block_indices: Tensor<B, 4, Int>,
) -> Tensor<B, 3> {
self.forward_sparse_with_weights(q, k, v, block_indices).0
}
pub fn forward_sparse_with_weights(
&self,
q: Tensor<B, 3>,
k: Tensor<B, 3>,
v: Tensor<B, 3>,
block_indices: Tensor<B, 4, Int>,
) -> (Tensor<B, 3>, Tensor<B, 4>) {
let (out_4d, block_attn) = sparse_attn_batched_gqa(
Self::to_4d(q, self.cfg.n_heads_q, self.cfg.d_head),
Self::to_4d(k, self.cfg.n_heads_kv, self.cfg.d_head),
Self::to_4d(v, self.cfg.n_heads_kv, self.cfg.d_head),
block_indices,
(self.cfg.d_head as f64).sqrt(),
self.cfg.block_size,
self.cfg.n_heads_kv,
self.cfg.n_heads_q,
self.cfg.causal,
);
let [b, _, s, _] = out_4d.dims();
let out_3d =
out_4d
.swap_dims(1, 2)
.reshape::<3, _>([b, s, self.cfg.n_heads_q * self.cfg.d_head]);
(self.out_proj.forward(out_3d), block_attn)
}
pub fn forward_dense(&self, q: Tensor<B, 3>, k: Tensor<B, 3>, v: Tensor<B, 3>) -> Tensor<B, 3> {
let cfg = &self.cfg;
let d_head = cfg.d_head;
let n_heads_q = cfg.n_heads_q;
let n_heads_kv = cfg.n_heads_kv;
let scale = (d_head as f64).sqrt();
let q_per_kv = n_heads_q / n_heads_kv;
let q_4d = Self::to_4d(q, n_heads_q, d_head);
let k_4d = Self::to_4d(k, n_heads_kv, d_head);
let v_4d = Self::to_4d(v, n_heads_kv, d_head);
let [_, _, seq_q, _] = q_4d.dims();
let seq_kv = k_4d.dims()[2];
if q_per_kv > 1 {
let k_exp = k_4d.repeat(&[1, q_per_kv, 1, 1]);
let s = q_4d.matmul(k_exp.swap_dims(2, 3)).div_scalar(scale);
let v_exp = v_4d.repeat(&[1, q_per_kv, 1, 1]);
let scores = causal_mask_4d::<B>(s, seq_q, seq_kv, cfg.causal);
let attn = softmax(scores, 3);
let out_4d = attn.matmul(v_exp);
let [b, _, s, _] = out_4d.dims();
let out_3d = out_4d
.swap_dims(1, 2)
.reshape::<3, _>([b, s, n_heads_q * d_head]);
self.out_proj.forward(out_3d)
} else {
let s = q_4d.matmul(k_4d.swap_dims(2, 3)).div_scalar(scale);
let scores = causal_mask_4d::<B>(s, seq_q, seq_kv, cfg.causal);
let attn = softmax(scores, 3);
let out_4d = attn.matmul(v_4d);
let [b, _, s, _] = out_4d.dims();
let out_3d = out_4d
.swap_dims(1, 2)
.reshape::<3, _>([b, s, n_heads_q * d_head]);
self.out_proj.forward(out_3d)
}
}
}
fn causal_mask_4d<B: Backend>(
scores: Tensor<B, 4>,
seq_q: usize,
seq_kv: usize,
causal: bool,
) -> Tensor<B, 4> {
if !causal || seq_q <= 1 {
return scores;
}
let device = scores.device();
let q_pos =
Tensor::<B, 1, Int>::arange(0..seq_q as i64, &device).reshape::<4, _>([1, 1, seq_q, 1]);
let kv_pos =
Tensor::<B, 1, Int>::arange(0..seq_kv as i64, &device).reshape::<4, _>([1, 1, 1, seq_kv]);
scores.add(
kv_pos
.greater(q_pos)
.float()
.mul_scalar(crate::NEG_INF_SAFE),
)
}
#[allow(clippy::too_many_arguments)]
pub fn sparse_attn_batched_gqa<B: Backend>(
q: Tensor<B, 4>,
k: Tensor<B, 4>,
v: Tensor<B, 4>,
block_indices: Tensor<B, 4, Int>,
scale: f64,
block_size: usize,
n_heads_kv: usize,
n_heads_q: usize,
causal: bool,
) -> (Tensor<B, 4>, Tensor<B, 4>) {
let batch = q.dims()[0];
let seq_q = q.dims()[2];
let d_head = q.dims()[3];
let seq_kv = k.dims()[2];
let qpkv = n_heads_q / n_heads_kv;
let topk = block_indices.dims()[3];
let attended = topk * block_size;
let device = q.device();
let offsets = Tensor::<B, 1, Int>::arange(0..block_size as i64, &device)
.reshape::<5, _>([1, 1, 1, 1, block_size]);
let all_idx = block_indices.clone()
.mul_scalar(block_size as i64)
.unsqueeze_dim::<5>(4)
.add(offsets)
.reshape::<4, _>([batch, n_heads_kv, seq_q, attended]);
let n_blocks = seq_kv.div_ceil(block_size);
let block_mask = Tensor::<B, 4, Int>::zeros([batch, n_heads_kv, seq_q, n_blocks], &device)
.scatter(
3,
block_indices,
Tensor::<B, 4, Int>::ones([batch, n_heads_kv, seq_q, topk], &device),
burn::tensor::IndexingUpdateOp::Add,
); let block_of_token = Tensor::<B, 1, Int>::arange(0..seq_kv as i64, &device)
.div_scalar(block_size as i64)
.reshape::<3, _>([1, 1, seq_kv])
.expand([batch, n_heads_kv, seq_q, seq_kv]); let token_mask = block_mask.gather(3, block_of_token); let mask = token_mask
.unsqueeze_dim::<5>(2)
.expand([batch, n_heads_kv, qpkv, seq_q, seq_kv]);
let q_gqa = q.reshape::<5, _>([batch, n_heads_kv, qpkv, seq_q, d_head]);
let k_t = k
.reshape::<5, _>([batch, n_heads_kv, 1, seq_kv, d_head])
.swap_dims(3, 4);
let mut scores = q_gqa.matmul(k_t).div_scalar(scale);
if causal {
let q_pos =
Tensor::<B, 1, Int>::arange(0..seq_q as i64, &device).reshape::<4, _>([1, 1, seq_q, 1]);
scores = scores.add(
all_idx
.clone()
.unsqueeze_dim::<5>(2)
.greater(q_pos.unsqueeze_dim::<5>(2))
.float()
.mul_scalar(crate::NEG_INF_SAFE),
);
}
let m = mask.float();
scores = scores.mul(m.clone()).add(m.neg().add_scalar(1.0).mul_scalar(crate::NEG_INF_SAFE));
let attn = softmax::<B, 5>(scores, 4);
let v_rep = v
.reshape::<5, _>([batch, n_heads_kv, 1, seq_kv, d_head])
.repeat(&[1, 1, qpkv, 1, 1]);
let out_5d = attn
.clone()
.matmul(v_rep) .reshape::<4, _>([batch, n_heads_q, seq_q, d_head]);
let attn_sel = attn.gather(
4,
all_idx
.clone()
.clamp_max((seq_kv - 1) as i64)
.unsqueeze_dim::<5>(2)
.expand([batch, n_heads_kv, qpkv, seq_q, attended]),
); let ba = attn_sel
.reshape::<6, _>([batch, n_heads_kv, qpkv, seq_q, topk, block_size])
.sum_dim(5)
.squeeze_dim::<5>(5)
.mean_dim(2)
.squeeze_dim::<4>(2);
(out_5d, ba)
}
#[inline]
pub fn softmax<B: Backend, const D: usize>(t: Tensor<B, D>, dim: usize) -> Tensor<B, D> {
activation::softmax(t, dim)
}
#[cfg(test)]
mod tests {
use super::*;
use burn::tensor::{Distribution, TensorData};
use burn_ndarray::{NdArray, NdArrayDevice};
fn device() -> NdArrayDevice {
NdArrayDevice::default()
}
fn extract_f32(t: Tensor<NdArray, 4>) -> Vec<f32> {
t.into_data()
.bytes
.chunks_exact(4)
.map(|b| f32::from_le_bytes(b.try_into().unwrap()))
.collect()
}
#[allow(clippy::too_many_arguments)]
fn sparse_attn_per_token<B: Backend>(
q: Tensor<B, 4>,
k: Tensor<B, 4>,
v: Tensor<B, 4>,
block_indices: Tensor<B, 4, Int>,
scale: f64,
block_size: usize,
n_heads_kv: usize,
n_heads_q: usize,
) -> (Tensor<B, 4>, Tensor<B, 4>) {
let batch = q.dims()[0];
let seq_q = q.dims()[2];
let d_head = q.dims()[3];
let seq_kv = k.dims()[2];
let q_per_kv = n_heads_q / n_heads_kv;
let topk = block_indices.dims()[3];
let attended = topk * block_size;
let offsets_5d = Tensor::<B, 1, Int>::arange(0..block_size as i64, &q.device())
.reshape::<5, _>([1, 1, 1, 1, block_size]);
let mut out_rows = Vec::with_capacity(n_heads_kv);
let mut aw_rows = Vec::with_capacity(n_heads_kv);
for h_kv in 0..n_heads_kv {
let k_h = k.clone().slice([0..batch, h_kv..h_kv + 1]);
let v_h = v.clone().slice([0..batch, h_kv..h_kv + 1]);
let mut attn_outputs = Vec::with_capacity(seq_q);
let mut attn_weights = Vec::with_capacity(seq_q);
for t in 0..seq_q {
let blk = block_indices
.clone()
.slice([0..batch, h_kv..h_kv + 1, t..t + 1]);
let blk_scaled = blk.mul_scalar(block_size as i64);
let blk_5d = blk_scaled
.unsqueeze_dim::<5>(4)
.repeat(&[1, 1, 1, 1, block_size]);
let idx = blk_5d
.add(offsets_5d.clone())
.reshape::<4, _>([batch, 1, attended, 1])
.repeat(&[1, 1, 1, d_head])
.clamp_max((seq_kv - 1) as i64);
let k_sel = k_h.clone().gather(2, idx.clone());
let v_sel = v_h.clone().gather(2, idx);
let q_t = q.clone().slice([
0..batch,
(h_kv * q_per_kv)..((h_kv + 1) * q_per_kv),
t..t + 1,
]);
let scores = q_t.matmul(k_sel.swap_dims(2, 3)).div_scalar(scale);
let attn_n = softmax_4d(scores, 3);
let aw = attn_n
.clone()
.reshape::<5, _>([batch, q_per_kv, 1, topk, block_size])
.sum_dim(4)
.squeeze_dim::<4>(4);
attn_outputs.push(attn_n.matmul(v_sel));
attn_weights.push(aw);
}
out_rows.push(Tensor::cat(attn_outputs, 2));
let aw_seq = Tensor::cat(attn_weights, 2);
aw_rows.push(aw_seq.mean_dim(1));
}
let block_attn = Tensor::cat(aw_rows, 1);
(Tensor::cat(out_rows, 1), block_attn)
}
fn softmax_4d<B: Backend>(t: Tensor<B, 4>, dim: usize) -> Tensor<B, 4> {
let mx = t.clone().max_dim(dim);
let shifted = t.sub(mx);
let ex = shifted.exp();
let sum = ex.clone().sum_dim(dim);
ex.div(sum)
}
#[test]
fn batched_matches_per_token() {
let d_head = 8;
for &seq_q in [1usize, 2, 4, 7].iter() {
for &seq_kv in [4usize, 8, 12, 16].iter() { for &n_heads_kv in [1usize, 2].iter() {
for &topk in [1usize, 3].iter() {
let n_heads_q = n_heads_kv * 2;
let block_size = 4;
let scale = (d_head as f64).sqrt();
let batch = 1;
let q = Tensor::<NdArray, 4>::random(
[batch, n_heads_q, seq_q, d_head],
Distribution::Normal(0.0, 1.0),
&device(),
);
let k = Tensor::<NdArray, 4>::random(
[batch, n_heads_kv, seq_kv, d_head],
Distribution::Normal(0.0, 1.0),
&device(),
);
let v = Tensor::<NdArray, 4>::random(
[batch, n_heads_kv, seq_kv, d_head],
Distribution::Normal(0.0, 1.0),
&device(),
);
let n_blocks = seq_kv.div_ceil(block_size);
let topk_actual = topk.min(n_blocks);
let per_group: Vec<i64> = (0..seq_q as i64)
.flat_map(|_| (0..topk_actual as i64).collect::<Vec<_>>())
.collect();
let idx_data: Vec<i64> = per_group.repeat(n_heads_kv);
let bi = Tensor::<NdArray, 4, Int>::from_data(
TensorData::new(idx_data, [batch, n_heads_kv, seq_q, topk_actual]),
&device(),
);
let (ref_out, _) = sparse_attn_per_token(
q.clone(),
k.clone(),
v.clone(),
bi.clone(),
scale,
block_size,
n_heads_kv,
n_heads_q,
);
let (batched_out, _) = sparse_attn_batched_gqa(
q, k, v, bi, scale, block_size, n_heads_kv, n_heads_q, false,
);
let ref_vals = extract_f32(ref_out);
let batched_vals = extract_f32(batched_out);
assert_eq!(ref_vals.len(), batched_vals.len());
for (i, (r, b)) in ref_vals.iter().zip(batched_vals.iter()).enumerate() {
if r.is_nan() && b.is_nan() {
continue;
}
if *r == 0.0 && *b == 0.0 {
continue;
}
let abs_diff = (r - b).abs();
let rel_diff = abs_diff / r.abs().max(b.abs()).max(f32::EPSILON);
assert!(
abs_diff <= 1e-5 || rel_diff <= 1e-4,
"Mismatch idx={} seq_q={} seq_kv={} kh={} tk={}: ref={} got={} abs={:.2e} rel={:.2e}",
i, seq_q, seq_kv, n_heads_kv, topk, r, b, abs_diff, rel_diff
);
}
}
}
}
}
}
}