use super::KernelError;
use super::primitives::softmax;
use super::quants::f16_to_f32;
use crate::kv::{KvCache, KvError};
use core::ops::Range;
use thiserror::Error;
#[cfg(target_arch = "x86_64")]
mod x86;
#[cfg(target_arch = "x86_64")]
const MAX_SIMD_HEAD_DIM: usize = 256;
#[inline]
pub fn avx2_f16c_available() -> bool {
#[cfg(target_arch = "x86_64")]
{
std::arch::is_x86_feature_detected!("avx2") && std::arch::is_x86_feature_detected!("f16c")
}
#[cfg(not(target_arch = "x86_64"))]
{
false
}
}
pub fn avx2_f16c_path_covers(head_dim: usize) -> bool {
#[cfg(target_arch = "x86_64")]
{
head_dim <= MAX_SIMD_HEAD_DIM && avx2_f16c_available()
}
#[cfg(not(target_arch = "x86_64"))]
{
let _ = head_dim;
false
}
}
#[derive(Debug, Error, PartialEq, Eq)]
pub enum AttentionError {
#[error(transparent)]
Kv(#[from] KvError),
#[error(transparent)]
Kernel(#[from] KernelError),
#[error("attention: q length {q_len} is not a nonzero multiple of head_dim {head_dim}")]
QLenIndivisible {
q_len: usize,
head_dim: usize,
},
#[error(
"attention: {n_q_heads} query heads do not group evenly over \
{n_kv_heads} kv heads"
)]
GqaGroupMismatch {
n_q_heads: usize,
n_kv_heads: usize,
},
#[error("attention: out length {out_len}, expected {expected} for this call")]
OutLenMismatch {
out_len: usize,
expected: usize,
},
#[error("attention: layer {layer} has no positions to attend over")]
EmptyLayer {
layer: usize,
},
#[error(
"attention: kv head range {start}..{end} is not a sub-range of \
0..{n_kv_heads}"
)]
KvHeadRangeOutOfRange {
start: usize,
end: usize,
n_kv_heads: usize,
},
#[error("attention: scratch length {len}, need {need} f32 for this geometry")]
ScratchTooShort {
len: usize,
need: usize,
},
}
pub fn scratch_len(
n_q_heads: usize,
n_kv_heads: usize,
head_dim: usize,
max_positions: usize,
) -> usize {
let group = n_q_heads.checked_div(n_kv_heads).unwrap_or(0);
scratch_len_of(group, head_dim, max_positions)
}
fn scratch_len_of(group: usize, head_dim: usize, max_positions: usize) -> usize {
group
.saturating_mul(max_positions)
.saturating_add(head_dim.saturating_mul(2))
}
#[derive(Debug, Default)]
pub struct AttentionScratch {
buf: Vec<f32>,
}
impl AttentionScratch {
pub fn new() -> Self {
Self::default()
}
pub fn with_capacity(slots: usize) -> Self {
Self {
buf: Vec::with_capacity(slots),
}
}
fn buf_mut(&mut self, len: usize) -> &mut [f32] {
self.buf.resize(len, 0.0);
&mut self.buf[..len]
}
}
pub fn decode_attention(
q: &[f32],
cache: &KvCache,
layer: usize,
scale: f32,
scratch: &mut AttentionScratch,
out: &mut [f32],
) -> Result<(), AttentionError> {
attention_owned(q, cache, layer, None, scale, scratch, out, false)
}
pub fn decode_attention_dispatch(
q: &[f32],
cache: &KvCache,
layer: usize,
scale: f32,
scratch: &mut AttentionScratch,
out: &mut [f32],
force_scalar: bool,
) -> Result<(), AttentionError> {
attention_owned(q, cache, layer, None, scale, scratch, out, force_scalar)
}
pub fn decode_attention_in(
q: &[f32],
cache: &KvCache,
layer: usize,
scale: f32,
scratch: &mut [f32],
out: &mut [f32],
) -> Result<(), AttentionError> {
attention_borrowed(
q,
cache,
layer,
None,
scale,
0..cache.n_kv_heads(),
scratch,
out,
false,
)
}
pub fn decode_attention_in_dispatch(
q: &[f32],
cache: &KvCache,
layer: usize,
scale: f32,
scratch: &mut [f32],
out: &mut [f32],
force_scalar: bool,
) -> Result<(), AttentionError> {
attention_borrowed(
q,
cache,
layer,
None,
scale,
0..cache.n_kv_heads(),
scratch,
out,
force_scalar,
)
}
pub fn decode_attention_kv_range_in(
q: &[f32],
cache: &KvCache,
layer: usize,
scale: f32,
kv_heads: Range<usize>,
scratch: &mut [f32],
out: &mut [f32],
) -> Result<(), AttentionError> {
attention_borrowed(q, cache, layer, None, scale, kv_heads, scratch, out, false)
}
#[allow(clippy::too_many_arguments)]
pub fn decode_attention_kv_range_in_dispatch(
q: &[f32],
cache: &KvCache,
layer: usize,
scale: f32,
kv_heads: Range<usize>,
scratch: &mut [f32],
out: &mut [f32],
force_scalar: bool,
) -> Result<(), AttentionError> {
attention_borrowed(
q,
cache,
layer,
None,
scale,
kv_heads,
scratch,
out,
force_scalar,
)
}
pub fn attention_at(
q: &[f32],
cache: &KvCache,
layer: usize,
positions: usize,
scale: f32,
scratch: &mut AttentionScratch,
out: &mut [f32],
) -> Result<(), AttentionError> {
attention_owned(q, cache, layer, Some(positions), scale, scratch, out, false)
}
#[allow(clippy::too_many_arguments)]
pub fn attention_at_dispatch(
q: &[f32],
cache: &KvCache,
layer: usize,
positions: usize,
scale: f32,
scratch: &mut AttentionScratch,
out: &mut [f32],
force_scalar: bool,
) -> Result<(), AttentionError> {
attention_owned(
q,
cache,
layer,
Some(positions),
scale,
scratch,
out,
force_scalar,
)
}
pub fn attention_at_in(
q: &[f32],
cache: &KvCache,
layer: usize,
positions: usize,
scale: f32,
scratch: &mut [f32],
out: &mut [f32],
) -> Result<(), AttentionError> {
attention_borrowed(
q,
cache,
layer,
Some(positions),
scale,
0..cache.n_kv_heads(),
scratch,
out,
false,
)
}
#[allow(clippy::too_many_arguments)]
pub fn attention_at_in_dispatch(
q: &[f32],
cache: &KvCache,
layer: usize,
positions: usize,
scale: f32,
scratch: &mut [f32],
out: &mut [f32],
force_scalar: bool,
) -> Result<(), AttentionError> {
attention_borrowed(
q,
cache,
layer,
Some(positions),
scale,
0..cache.n_kv_heads(),
scratch,
out,
force_scalar,
)
}
#[allow(clippy::too_many_arguments)]
pub fn attention_at_kv_range_in(
q: &[f32],
cache: &KvCache,
layer: usize,
positions: usize,
scale: f32,
kv_heads: Range<usize>,
scratch: &mut [f32],
out: &mut [f32],
) -> Result<(), AttentionError> {
attention_borrowed(
q,
cache,
layer,
Some(positions),
scale,
kv_heads,
scratch,
out,
false,
)
}
#[allow(clippy::too_many_arguments)]
pub fn attention_at_kv_range_in_dispatch(
q: &[f32],
cache: &KvCache,
layer: usize,
positions: usize,
scale: f32,
kv_heads: Range<usize>,
scratch: &mut [f32],
out: &mut [f32],
force_scalar: bool,
) -> Result<(), AttentionError> {
attention_borrowed(
q,
cache,
layer,
Some(positions),
scale,
kv_heads,
scratch,
out,
force_scalar,
)
}
struct Plan {
head_dim: usize,
kv_dim: usize,
group: usize,
positions: usize,
kv_heads: Range<usize>,
}
impl Plan {
fn scratch_len(&self) -> usize {
scratch_len_of(self.group, self.head_dim, self.positions)
}
}
fn plan(
q: &[f32],
cache: &KvCache,
layer: usize,
limit: Option<usize>,
kv_heads: Range<usize>,
out: &[f32],
) -> Result<Plan, AttentionError> {
let head_dim = cache.head_dim();
let n_kv_heads = cache.n_kv_heads();
if q.is_empty() || !q.len().is_multiple_of(head_dim) {
return Err(AttentionError::QLenIndivisible {
q_len: q.len(),
head_dim,
});
}
let n_q_heads = q.len() / head_dim;
if !n_q_heads.is_multiple_of(n_kv_heads) {
return Err(AttentionError::GqaGroupMismatch {
n_q_heads,
n_kv_heads,
});
}
let len = cache.len(layer)?;
let positions = limit.unwrap_or(len);
if positions == 0 {
return Err(AttentionError::EmptyLayer { layer });
}
if positions > len {
return Err(AttentionError::Kv(KvError::PositionOutOfRange {
layer,
pos: positions - 1,
len,
}));
}
if kv_heads.start > kv_heads.end || kv_heads.end > n_kv_heads {
return Err(AttentionError::KvHeadRangeOutOfRange {
start: kv_heads.start,
end: kv_heads.end,
n_kv_heads,
});
}
let group = n_q_heads / n_kv_heads;
let expected = kv_heads.len() * group * head_dim;
if out.len() != expected {
return Err(AttentionError::OutLenMismatch {
out_len: out.len(),
expected,
});
}
Ok(Plan {
head_dim,
kv_dim: cache.kv_dim(),
group,
positions,
kv_heads,
})
}
#[allow(clippy::too_many_arguments)]
fn attention_owned(
q: &[f32],
cache: &KvCache,
layer: usize,
limit: Option<usize>,
scale: f32,
scratch: &mut AttentionScratch,
out: &mut [f32],
force_scalar: bool,
) -> Result<(), AttentionError> {
let plan = plan(q, cache, layer, limit, 0..cache.n_kv_heads(), out)?;
let need = scratch_len_of(
plan.group,
plan.head_dim,
cache.capacity().max(plan.positions),
);
let buf = scratch.buf_mut(need);
attention_body(q, cache, layer, &plan, scale, buf, out, force_scalar)
}
#[allow(clippy::too_many_arguments)]
fn attention_borrowed(
q: &[f32],
cache: &KvCache,
layer: usize,
limit: Option<usize>,
scale: f32,
kv_heads: Range<usize>,
scratch: &mut [f32],
out: &mut [f32],
force_scalar: bool,
) -> Result<(), AttentionError> {
let plan = plan(q, cache, layer, limit, kv_heads, out)?;
let need = plan.scratch_len();
if scratch.len() < need {
return Err(AttentionError::ScratchTooShort {
len: scratch.len(),
need,
});
}
attention_body(q, cache, layer, &plan, scale, scratch, out, force_scalar)
}
#[allow(clippy::too_many_arguments)]
fn attention_body(
q: &[f32],
cache: &KvCache,
layer: usize,
plan: &Plan,
scale: f32,
scratch: &mut [f32],
out: &mut [f32],
force_scalar: bool,
) -> Result<(), AttentionError> {
let &Plan {
head_dim,
kv_dim,
group,
positions,
..
} = plan;
let k_rows = &cache.k_layer(layer)?[..positions * kv_dim];
let v_rows = &cache.v_layer(layer)?[..positions * kv_dim];
let (scores, conv) = scratch.split_at_mut(group * positions);
let (kbuf, vbuf) = conv.split_at_mut(head_dim);
let vbuf = &mut vbuf[..head_dim];
let group_dim = group * head_dim;
for (kv_head, out_group) in plan.kv_heads.clone().zip(out.chunks_exact_mut(group_dim)) {
let lo = kv_head * group_dim;
let q_group = &q[lo..lo + group_dim];
let col = kv_head * head_dim;
qk_scores(
q_group,
k_rows,
kv_dim,
col,
head_dim,
group,
positions,
scale,
kbuf,
scores,
force_scalar,
);
for run in scores.chunks_exact_mut(positions) {
softmax(run)?;
}
out_group.fill(0.0);
v_reduce(
v_rows,
kv_dim,
col,
head_dim,
positions,
scores,
vbuf,
out_group,
force_scalar,
);
}
Ok(())
}
#[allow(clippy::too_many_arguments)]
fn qk_scores(
q_group: &[f32],
k_rows: &[u16],
kv_dim: usize,
col: usize,
head_dim: usize,
group: usize,
positions: usize,
scale: f32,
kbuf: &mut [f32],
scores: &mut [f32],
force_scalar: bool,
) {
#[cfg(target_arch = "x86_64")]
if !force_scalar && avx2_f16c_path_covers(head_dim) {
unsafe {
x86::qk_scores(
q_group, k_rows, kv_dim, col, head_dim, group, positions, scale, scores,
);
}
return;
}
#[cfg(not(target_arch = "x86_64"))]
let _ = force_scalar;
qk_scores_scalar(
q_group, k_rows, kv_dim, col, head_dim, positions, scale, kbuf, scores,
);
}
#[allow(clippy::too_many_arguments)]
fn qk_scores_scalar(
q_group: &[f32],
k_rows: &[u16],
kv_dim: usize,
col: usize,
head_dim: usize,
positions: usize,
scale: f32,
kbuf: &mut [f32],
scores: &mut [f32],
) {
for (t, k_row) in k_rows.chunks_exact(kv_dim).take(positions).enumerate() {
let k_th = &k_row[col..col + head_dim];
for (dst, &bits) in kbuf.iter_mut().zip(k_th) {
*dst = f16_to_f32(bits);
}
for (q_h, run) in q_group
.chunks_exact(head_dim)
.zip(scores.chunks_exact_mut(positions))
{
let mut acc = 0.0f32;
for (&qv, &kv) in q_h.iter().zip(kbuf.iter()) {
acc += qv * kv;
}
run[t] = scale * acc;
}
}
}
#[allow(clippy::too_many_arguments)]
fn v_reduce(
v_rows: &[u16],
kv_dim: usize,
col: usize,
head_dim: usize,
positions: usize,
scores: &[f32],
vbuf: &mut [f32],
out_group: &mut [f32],
force_scalar: bool,
) {
#[cfg(target_arch = "x86_64")]
if !force_scalar && avx2_f16c_path_covers(head_dim) {
unsafe {
x86::v_reduce(
v_rows, kv_dim, col, head_dim, positions, scores, vbuf, out_group,
);
}
return;
}
#[cfg(not(target_arch = "x86_64"))]
let _ = force_scalar;
v_reduce_scalar(
v_rows, kv_dim, col, head_dim, positions, scores, vbuf, out_group,
);
}
#[allow(clippy::too_many_arguments)]
fn v_reduce_scalar(
v_rows: &[u16],
kv_dim: usize,
col: usize,
head_dim: usize,
positions: usize,
scores: &[f32],
vbuf: &mut [f32],
out_group: &mut [f32],
) {
for (t, v_row) in v_rows.chunks_exact(kv_dim).take(positions).enumerate() {
let v_th = &v_row[col..col + head_dim];
for (dst, &bits) in vbuf.iter_mut().zip(v_th) {
*dst = f16_to_f32(bits);
}
for (out_h, run) in out_group
.chunks_exact_mut(head_dim)
.zip(scores.chunks_exact(positions))
{
let w = run[t];
for (o, &vv) in out_h.iter_mut().zip(vbuf.iter()) {
*o += w * vv;
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::kernels::quants::f32_to_f16;
use std::io::Write;
struct Rng(u64);
impl Rng {
fn new(seed: u64) -> Self {
Self(seed | 1)
}
fn next_u64(&mut self) -> u64 {
let mut x = self.0;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
self.0 = x;
x.wrapping_mul(0x2545_F491_4F6C_DD1D)
}
fn f32_in(&mut self, lo: f32, hi: f32) -> f32 {
let unit = (self.next_u64() >> 40) as f32 / (1u64 << 24) as f32;
lo + (hi - lo) * unit
}
fn vec_in(&mut self, n: usize, lo: f32, hi: f32) -> Vec<f32> {
(0..n).map(|_| self.f32_in(lo, hi)).collect()
}
}
fn assert_close(actual: f32, expected: f64, rel_tol: f64, abs_tol: f64) {
let diff = (f64::from(actual) - expected).abs();
if diff <= abs_tol {
return;
}
let rel = diff / expected.abs().max(f64::MIN_POSITIVE);
assert!(
rel <= rel_tol,
"actual {actual:e} vs expected {expected:e}: rel err {rel:.3e} > {rel_tol:.1e} \
(abs diff {diff:.3e} > {abs_tol:.1e})"
);
}
fn reference_attention(
q: &[f32],
k_rows: &[Vec<f32>],
v_rows: &[Vec<f32>],
n_kv_heads: usize,
head_dim: usize,
scale: f32,
) -> Vec<f64> {
let n_q_heads = q.len() / head_dim;
let group = n_q_heads / n_kv_heads;
let len = k_rows.len();
let mut out = vec![0.0f64; q.len()];
for h in 0..n_q_heads {
let col = (h / group) * head_dim;
let q_h = &q[h * head_dim..(h + 1) * head_dim];
let mut scores: Vec<f64> = (0..len)
.map(|t| {
let k_th = &k_rows[t][col..col + head_dim];
let dot: f64 = q_h
.iter()
.zip(k_th)
.map(|(&a, &b)| f64::from(a) * f64::from(b))
.sum();
dot * f64::from(scale)
})
.collect();
let max = scores.iter().copied().fold(f64::NEG_INFINITY, f64::max);
let mut sum = 0.0f64;
for s in scores.iter_mut() {
*s = (*s - max).exp();
sum += *s;
}
for s in scores.iter_mut() {
*s /= sum;
}
for (t, &w) in scores.iter().enumerate() {
let v_th = &v_rows[t][col..col + head_dim];
for (i, &v) in v_th.iter().enumerate() {
out[h * head_dim + i] += w * f64::from(v);
}
}
}
out
}
fn round_trip(rows: &[Vec<f32>]) -> Vec<Vec<f32>> {
rows.iter()
.map(|r| r.iter().map(|&x| f16_to_f32(f32_to_f16(x))).collect())
.collect()
}
#[test]
fn matches_f64_reference_across_layers_and_lengths() {
let (n_layers, n_kv, n_q, head_dim, cap) = (3usize, 4usize, 32usize, 128usize, 256usize);
let kv_dim = n_kv * head_dim;
let scale = 1.0 / (head_dim as f32).sqrt();
let mut rng = Rng::new(0xA77E);
let mut cache = KvCache::new(n_layers, n_kv, head_dim, cap).unwrap();
let mut k_exact: Vec<Vec<Vec<f32>>> = vec![Vec::new(); n_layers];
let mut v_exact: Vec<Vec<Vec<f32>>> = vec![Vec::new(); n_layers];
let mut scratch = AttentionScratch::new();
let mut appended = 0usize;
for &target in &[1usize, 2, 17, 256] {
while appended < target {
for layer in 0..n_layers {
let k = rng.vec_in(kv_dim, -1.0, 1.0);
let v = rng.vec_in(kv_dim, -1.0, 1.0);
cache.append(layer, &k, &v).unwrap();
k_exact[layer].push(k);
v_exact[layer].push(v);
}
appended += 1;
}
assert_eq!(cache.seq_len().unwrap(), target);
for layer in 0..n_layers {
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
let mut out = vec![0.0f32; q.len()];
decode_attention(&q, &cache, layer, scale, &mut scratch, &mut out).unwrap();
let want = reference_attention(
&q,
&k_exact[layer],
&v_exact[layer],
n_kv,
head_dim,
scale,
);
for (&got, &w) in out.iter().zip(&want) {
assert_close(got, w, 1e-3, 1.5e-3);
}
let want_rt = reference_attention(
&q,
&round_trip(&k_exact[layer]),
&round_trip(&v_exact[layer]),
n_kv,
head_dim,
scale,
);
for (&got, &w) in out.iter().zip(&want_rt) {
assert_close(got, w, 1e-4, 5e-5);
}
}
}
}
#[test]
fn gqa_maps_query_head_h_to_kv_head_h_div_8() {
let (n_kv, n_q, head_dim) = (4usize, 32usize, 16usize);
let kv_dim = n_kv * head_dim;
let mut cache = KvCache::new(1, n_kv, head_dim, 4).unwrap();
let marker = |j: usize, t: usize| (10 * j + t) as f32 * 0.01;
for t in 0..4 {
let mut k = vec![0.0f32; kv_dim];
let mut v = vec![0.0f32; kv_dim];
for j in 0..n_kv {
let sign = if t == j { 1.0f32 } else { -1.0 };
for i in 0..head_dim {
k[j * head_dim + i] = sign * 8.0 / head_dim as f32;
v[j * head_dim + i] = marker(j, t);
}
}
cache.append(0, &k, &v).unwrap();
}
let q = vec![1.0f32; n_q * head_dim];
let mut out = vec![0.0f32; q.len()];
let mut scratch = AttentionScratch::new();
decode_attention(&q, &cache, 0, 1.0, &mut scratch, &mut out).unwrap();
for h in 0..n_q {
let j = h / 8; let want = marker(j, j); for i in 0..head_dim {
let got = out[h * head_dim + i];
assert!(
(got - want).abs() < 1e-3,
"q head {h} elem {i}: got {got}, want kv head {j} marker {want}"
);
}
}
}
#[test]
fn single_position_returns_v_row() {
let (n_kv, n_q, head_dim) = (4usize, 32usize, 128usize);
let kv_dim = n_kv * head_dim;
let mut rng = Rng::new(0x5EED);
let mut cache = KvCache::new(2, n_kv, head_dim, 8).unwrap();
let mut v_by_layer = Vec::new();
for layer in 0..2 {
let k = rng.vec_in(kv_dim, -1.0, 1.0);
let v = rng.vec_in(kv_dim, -1.0, 1.0);
cache.append(layer, &k, &v).unwrap();
v_by_layer.push(v);
}
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
let mut scratch = AttentionScratch::new();
for (layer, v) in v_by_layer.iter().enumerate() {
let mut out = vec![0.0f32; q.len()];
let scale = 1.0 / (head_dim as f32).sqrt();
decode_attention(&q, &cache, layer, scale, &mut scratch, &mut out).unwrap();
for h in 0..n_q {
let col = (h / 8) * head_dim;
for i in 0..head_dim {
let exact = f16_to_f32(f32_to_f16(v[col + i]));
assert_eq!(
out[h * head_dim + i],
exact,
"layer {layer} head {h} elem {i}"
);
assert_close(out[h * head_dim + i], f64::from(v[col + i]), 4.9e-4, 6e-8);
}
}
}
}
#[test]
fn typed_errors_on_bad_shapes() {
let (n_kv, head_dim) = (4usize, 8usize);
let mut cache = KvCache::new(1, n_kv, head_dim, 4).unwrap();
let mut scratch = AttentionScratch::new();
let q = vec![0.0f32; 32 * head_dim];
let mut out = vec![7.0f32; q.len()];
assert_eq!(
decode_attention(&q, &cache, 0, 1.0, &mut scratch, &mut out).unwrap_err(),
AttentionError::EmptyLayer { layer: 0 }
);
let row = vec![0.5f32; n_kv * head_dim];
cache.append(0, &row, &row).unwrap();
assert_eq!(
decode_attention(&q, &cache, 1, 1.0, &mut scratch, &mut out).unwrap_err(),
AttentionError::Kv(KvError::LayerOutOfRange {
layer: 1,
n_layers: 1,
})
);
assert_eq!(
decode_attention(&q[..13], &cache, 0, 1.0, &mut scratch, &mut out).unwrap_err(),
AttentionError::QLenIndivisible {
q_len: 13,
head_dim,
}
);
assert_eq!(
decode_attention(&[], &cache, 0, 1.0, &mut scratch, &mut out).unwrap_err(),
AttentionError::QLenIndivisible { q_len: 0, head_dim }
);
assert_eq!(
decode_attention(&q[..5 * head_dim], &cache, 0, 1.0, &mut scratch, &mut out)
.unwrap_err(),
AttentionError::GqaGroupMismatch {
n_q_heads: 5,
n_kv_heads: 4,
}
);
assert_eq!(
decode_attention(&q, &cache, 0, 1.0, &mut scratch, &mut out[..7]).unwrap_err(),
AttentionError::OutLenMismatch {
out_len: 7,
expected: q.len(),
}
);
assert!(out.iter().all(|&x| x == 7.0));
}
#[test]
fn error_precedence_is_pinned_from_q_to_out() {
let (n_layers, n_kv, n_q, head_dim, n_pos) = (2usize, 4usize, 8usize, 8usize, 3usize);
let cap = 4usize;
let mut cache = KvCache::new(n_layers, n_kv, head_dim, cap).unwrap();
let row = vec![0.5f32; n_kv * head_dim];
for _ in 0..n_pos {
cache.append(0, &row, &row).unwrap();
}
let q = vec![0.25f32; n_q * head_dim];
let scale = 1.0 / (head_dim as f32).sqrt();
let group_dim = (n_q / n_kv) * head_dim;
let need = scratch_len(n_q, n_kv, head_dim, cap);
const WRONG_OUT: usize = 7;
let bad_range = n_kv + 1..n_kv + 1;
let range_forms = ["decode_attention_kv_range_in", "attention_at_kv_range_in"];
let probe = |q_arg: &[f32],
layer: usize,
positions: usize,
out_len: usize,
kv_heads: Range<usize>|
-> Vec<(&'static str, AttentionError)> {
let mut owned = AttentionScratch::new();
let mut carve = vec![0.0f32; need];
let mut out = vec![f32::NAN; out_len];
let got: Vec<(&'static str, AttentionError)> = vec![
(
"decode_attention",
decode_attention(q_arg, &cache, layer, scale, &mut owned, &mut out)
.unwrap_err(),
),
(
"decode_attention_in",
decode_attention_in(q_arg, &cache, layer, scale, &mut carve, &mut out)
.unwrap_err(),
),
(
"attention_at",
attention_at(q_arg, &cache, layer, positions, scale, &mut owned, &mut out)
.unwrap_err(),
),
(
"attention_at_in",
attention_at_in(q_arg, &cache, layer, positions, scale, &mut carve, &mut out)
.unwrap_err(),
),
(
"decode_attention_kv_range_in",
decode_attention_kv_range_in(
q_arg,
&cache,
layer,
scale,
kv_heads.clone(),
&mut carve,
&mut out,
)
.unwrap_err(),
),
(
"attention_at_kv_range_in",
attention_at_kv_range_in(
q_arg, &cache, layer, positions, scale, kv_heads, &mut carve, &mut out,
)
.unwrap_err(),
),
];
assert!(
out.iter().all(|x| x.is_nan()),
"a rejected call wrote to `out`"
);
got
};
let bad_layer = n_layers + 3;
for (label, q_arg, want) in [
(
"q length",
&q[..13],
AttentionError::QLenIndivisible {
q_len: 13,
head_dim,
},
),
(
"GQA grouping",
&q[..5 * head_dim],
AttentionError::GqaGroupMismatch {
n_q_heads: 5,
n_kv_heads: n_kv,
},
),
(
"layer",
&q[..],
AttentionError::Kv(KvError::LayerOutOfRange {
layer: bad_layer,
n_layers,
}),
),
] {
for (name, err) in probe(q_arg, bad_layer, n_pos + 9, WRONG_OUT, bad_range.clone()) {
assert_eq!(err, want, "{label} beats everything after it: {name}");
}
}
for (name, err) in probe(&q, 1, 0, WRONG_OUT, bad_range.clone()) {
assert_eq!(
err,
AttentionError::EmptyLayer { layer: 1 },
"an empty layer beats the range and `out`: {name}"
);
}
for (name, err) in probe(&q, 0, n_pos + 9, WRONG_OUT, bad_range.clone()) {
let want = match name {
"attention_at" | "attention_at_in" | "attention_at_kv_range_in" => {
AttentionError::Kv(KvError::PositionOutOfRange {
layer: 0,
pos: n_pos + 8,
len: n_pos,
})
}
"decode_attention_kv_range_in" => AttentionError::KvHeadRangeOutOfRange {
start: bad_range.start,
end: bad_range.end,
n_kv_heads: n_kv,
},
_ => AttentionError::OutLenMismatch {
out_len: WRONG_OUT,
expected: q.len(),
},
};
assert_eq!(err, want, "`positions` past the end: {name}");
}
for (name, err) in probe(&q, 0, n_pos, WRONG_OUT, bad_range.clone()) {
let want = if range_forms.contains(&name) {
AttentionError::KvHeadRangeOutOfRange {
start: bad_range.start,
end: bad_range.end,
n_kv_heads: n_kv,
}
} else {
AttentionError::OutLenMismatch {
out_len: WRONG_OUT,
expected: q.len(),
}
};
assert_eq!(err, want, "the range beats `out`: {name}");
}
for (kv_heads, heads) in [(0..n_kv, n_kv), (1..3, 2)] {
for (name, err) in probe(&q, 0, n_pos, WRONG_OUT, kv_heads) {
let expected = if range_forms.contains(&name) {
heads * group_dim
} else {
q.len()
};
assert_eq!(
err,
AttentionError::OutLenMismatch {
out_len: WRONG_OUT,
expected,
},
"`out` is last, over {heads} kv heads: {name}"
);
}
}
let need_at = scratch_len(n_q, n_kv, head_dim, n_pos);
let mut short = vec![0.0f32; need_at - 1];
let mut wrong = vec![f32::NAN; WRONG_OUT];
for (name, err) in [
(
"decode_attention_in",
decode_attention_in(&q, &cache, 0, scale, &mut short, &mut wrong).unwrap_err(),
),
(
"attention_at_in",
attention_at_in(&q, &cache, 0, n_pos, scale, &mut short, &mut wrong).unwrap_err(),
),
] {
assert_eq!(
err,
AttentionError::OutLenMismatch {
out_len: WRONG_OUT,
expected: q.len(),
},
"`out` beats the scratch carve: {name}"
);
}
assert!(wrong.iter().all(|x| x.is_nan()));
let mut right = vec![f32::NAN; q.len()];
for (name, err) in [
(
"decode_attention_in",
decode_attention_in(&q, &cache, 0, scale, &mut short, &mut right).unwrap_err(),
),
(
"attention_at_in",
attention_at_in(&q, &cache, 0, n_pos, scale, &mut short, &mut right).unwrap_err(),
),
] {
assert_eq!(
err,
AttentionError::ScratchTooShort {
len: need_at - 1,
need: need_at,
},
"with `out` right, the scratch is what is reported: {name}"
);
}
assert!(right.iter().all(|x| x.is_nan()));
}
#[test]
fn doubling_scale_squares_the_odds_ratio() {
let head_dim = 4usize;
let mut cache = KvCache::new(1, 1, head_dim, 2).unwrap();
cache.append(0, &[0.0, 0.0, 0.0, 0.0], &[0.0; 4]).unwrap();
cache.append(0, &[1.0, 0.0, 0.0, 0.0], &[1.0; 4]).unwrap();
let q = [1.0f32, 0.0, 0.0, 0.0];
let mut scratch = AttentionScratch::new();
let p_at = |scale: f32, scratch: &mut AttentionScratch| {
let mut out = [0.0f32; 4];
decode_attention(&q, &cache, 0, scale, scratch, &mut out).unwrap();
f64::from(out[0]) };
let s = 0.7f32;
let p1 = p_at(s, &mut scratch);
let p2 = p_at(2.0 * s, &mut scratch);
let sigmoid = |x: f64| 1.0 / (1.0 + (-x).exp());
assert_close(p1 as f32, sigmoid(f64::from(s)), 1e-5, 0.0);
assert_close(p2 as f32, sigmoid(2.0 * f64::from(s)), 1e-5, 0.0);
let odds = |p: f64| p / (1.0 - p);
assert_close(odds(p2) as f32, odds(p1).powi(2), 1e-4, 0.0);
assert!(p2 > p1);
}
#[test]
fn scratch_reuses_allocation() {
let need = scratch_len(32, 4, 8, 17);
assert_eq!(need, 8 * 17 + 2 * 8);
let mut scratch = AttentionScratch::with_capacity(need);
let ptr = scratch.buf.as_ptr();
assert_eq!(scratch.buf_mut(need).len(), need);
assert_eq!(scratch.buf.as_ptr(), ptr);
assert_eq!(scratch.buf_mut(scratch_len(32, 4, 8, 3)).len(), 8 * 3 + 16);
assert_eq!(scratch.buf.as_ptr(), ptr);
assert_eq!(scratch.buf_mut(need).len(), need);
assert_eq!(scratch.buf.as_ptr(), ptr);
assert_eq!(scratch.buf.capacity(), need);
}
#[test]
fn scratch_allocates_once_across_a_growing_sequence() {
let (n_kv, n_q, head_dim, cap) = (2usize, 8usize, 16usize, 32usize);
let mut rng = Rng::new(0x00A1_10C1);
let (cache, _rows) = random_cache(&mut rng, 1, n_kv, head_dim, cap);
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
let mut out = vec![0.0f32; q.len()];
let scale = 1.0 / (head_dim as f32).sqrt();
let need = scratch_len(n_q, n_kv, head_dim, cap);
let mut scratch = AttentionScratch::with_capacity(need);
let ptr = scratch.buf.as_ptr();
for positions in 1..=cap {
attention_at(&q, &cache, 0, positions, scale, &mut scratch, &mut out).unwrap();
assert_eq!(scratch.buf.as_ptr(), ptr, "reallocated at {positions}");
assert_eq!(scratch.buf.len(), need);
}
}
const LIMITED_GEOMETRIES: [(usize, usize, usize, usize, usize); 4] = [
(2, 4, 32, 128, 5),
(1, 2, 2, 16, 9),
(1, 1, 8, 8, 7),
(2, 3, 6, 4, 12),
];
#[allow(clippy::type_complexity)]
fn random_cache(
rng: &mut Rng,
n_layers: usize,
n_kv: usize,
head_dim: usize,
n_pos: usize,
) -> (KvCache, Vec<Vec<(Vec<f32>, Vec<f32>)>>) {
let kv_dim = n_kv * head_dim;
let rows: Vec<Vec<(Vec<f32>, Vec<f32>)>> = (0..n_layers)
.map(|_| {
(0..n_pos)
.map(|_| (rng.vec_in(kv_dim, -1.0, 1.0), rng.vec_in(kv_dim, -1.0, 1.0)))
.collect()
})
.collect();
let mut cache = KvCache::new(n_layers, n_kv, head_dim, n_pos.max(1)).unwrap();
for (layer, layer_rows) in rows.iter().enumerate() {
for (k, v) in layer_rows {
cache.append(layer, k, v).unwrap();
}
}
(cache, rows)
}
#[test]
fn attention_at_is_bit_identical_to_truncated_decode() {
let mut rng = Rng::new(0xB17D_E17E);
let mut scratch = AttentionScratch::new();
for &(n_layers, n_kv, n_q, head_dim, n_pos) in &LIMITED_GEOMETRIES {
let scale = 1.0 / (head_dim as f32).sqrt();
let (full, rows) = random_cache(&mut rng, n_layers, n_kv, head_dim, n_pos);
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
let mut prime = vec![0.0f32; q.len()];
for (layer, layer_rows) in rows.iter().enumerate() {
for n in 1..=n_pos {
let mut trunc = KvCache::new(n_layers, n_kv, head_dim, n).unwrap();
for (k, v) in layer_rows.iter().take(n) {
trunc.append(layer, k, v).unwrap();
}
attention_at(&q, &full, layer, n_pos, scale, &mut scratch, &mut prime).unwrap();
let mut got = vec![0.0f32; q.len()];
attention_at(&q, &full, layer, n, scale, &mut scratch, &mut got).unwrap();
let mut want = vec![0.0f32; q.len()];
decode_attention(&q, &trunc, layer, scale, &mut scratch, &mut want).unwrap();
for (i, (&g, &w)) in got.iter().zip(&want).enumerate() {
assert_eq!(
g.to_bits(),
w.to_bits(),
"geometry ({n_layers}, {n_kv}, {n_q}, {head_dim}) layer {layer} \
positions {n} elem {i}: attention_at {g:e} vs truncated \
decode_attention {w:e}"
);
}
}
}
}
}
#[test]
fn decode_attention_matches_attention_at_at_full_length() {
let (n_kv, n_q, head_dim) = (4usize, 32usize, 128usize);
let kv_dim = n_kv * head_dim;
let scale = 1.0 / (head_dim as f32).sqrt();
let mut rng = Rng::new(0xDE1E_6A7E);
let lens = [3usize, 1, 6];
let mut cache = KvCache::new(lens.len(), n_kv, head_dim, 6).unwrap();
for (layer, &len) in lens.iter().enumerate() {
for _ in 0..len {
let k = rng.vec_in(kv_dim, -1.0, 1.0);
let v = rng.vec_in(kv_dim, -1.0, 1.0);
cache.append(layer, &k, &v).unwrap();
}
}
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
let mut scratch = AttentionScratch::new();
for (layer, &len) in lens.iter().enumerate() {
assert_eq!(cache.len(layer).unwrap(), len);
let mut want = vec![0.0f32; q.len()];
decode_attention(&q, &cache, layer, scale, &mut scratch, &mut want).unwrap();
let mut got = vec![0.0f32; q.len()];
attention_at(&q, &cache, layer, len, scale, &mut scratch, &mut got).unwrap();
for (i, (&g, &w)) in got.iter().zip(&want).enumerate() {
assert_eq!(g.to_bits(), w.to_bits(), "layer {layer} elem {i}");
}
}
}
#[test]
fn attention_at_typed_errors_on_positions() {
let (n_kv, head_dim) = (2usize, 8usize);
let mut cache = KvCache::new(2, n_kv, head_dim, 4).unwrap();
let row = vec![0.5f32; n_kv * head_dim];
for _ in 0..3 {
cache.append(0, &row, &row).unwrap();
}
let q = vec![0.25f32; 4 * head_dim];
let mut out = vec![7.0f32; q.len()];
let mut scratch = AttentionScratch::new();
assert_eq!(
attention_at(&q, &cache, 0, 0, 1.0, &mut scratch, &mut out).unwrap_err(),
AttentionError::EmptyLayer { layer: 0 }
);
for want in [4usize, 9, usize::MAX] {
assert_eq!(
attention_at(&q, &cache, 0, want, 1.0, &mut scratch, &mut out).unwrap_err(),
AttentionError::Kv(KvError::PositionOutOfRange {
layer: 0,
pos: want - 1,
len: 3,
})
);
}
assert_eq!(
attention_at(&q, &cache, 1, 1, 1.0, &mut scratch, &mut out).unwrap_err(),
AttentionError::Kv(KvError::PositionOutOfRange {
layer: 1,
pos: 0,
len: 0,
})
);
assert_eq!(
attention_at(&q, &cache, 1, 0, 1.0, &mut scratch, &mut out).unwrap_err(),
AttentionError::EmptyLayer { layer: 1 }
);
assert_eq!(
attention_at(&q, &cache, 2, 1, 1.0, &mut scratch, &mut out).unwrap_err(),
AttentionError::Kv(KvError::LayerOutOfRange {
layer: 2,
n_layers: 2,
})
);
assert_eq!(
attention_at(&q[..3], &cache, 0, usize::MAX, 1.0, &mut scratch, &mut out).unwrap_err(),
AttentionError::QLenIndivisible { q_len: 3, head_dim }
);
assert!(out.iter().all(|&x| x == 7.0));
}
fn head_major_reference(
q: &[f32],
cache: &KvCache,
layer: usize,
positions: usize,
scale: f32,
out: &mut [f32],
) {
let head_dim = cache.head_dim();
let n_kv_heads = cache.n_kv_heads();
let kv_dim = cache.kv_dim();
let n_q_heads = q.len() / head_dim;
let group = n_q_heads / n_kv_heads;
let k_plane = cache.k_layer(layer).unwrap();
let v_plane = cache.v_layer(layer).unwrap();
let mut scores = vec![0.0f32; positions];
for (h, out_h) in out.chunks_exact_mut(head_dim).enumerate() {
let kv_head = h / group;
let col = kv_head * head_dim;
let q_h = &q[h * head_dim..(h + 1) * head_dim];
for (row, score) in k_plane.chunks_exact(kv_dim).zip(scores.iter_mut()) {
let k_th = &row[col..col + head_dim];
let mut acc = 0.0f32;
for (&qv, &kb) in q_h.iter().zip(k_th) {
acc += qv * f16_to_f32(kb);
}
*score = scale * acc;
}
softmax(&mut scores).unwrap();
out_h.fill(0.0);
for (row, &w) in v_plane.chunks_exact(kv_dim).zip(scores.iter()) {
let v_th = &row[col..col + head_dim];
for (o, &vb) in out_h.iter_mut().zip(v_th) {
*o += w * f16_to_f32(vb);
}
}
}
}
#[test]
fn restructured_kernel_is_bit_identical_to_head_major_reference() {
let mut rng = Rng::new(0x0401_57ED);
let mut geometries = LIMITED_GEOMETRIES.to_vec();
geometries.push((1, 4, 32, 128, 67));
for (n_layers, n_kv, n_q, head_dim, n_pos) in geometries {
let scale = 1.0 / (head_dim as f32).sqrt();
let (cache, _rows) = random_cache(&mut rng, n_layers, n_kv, head_dim, n_pos);
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
let mut owned = AttentionScratch::new();
for layer in 0..n_layers {
for &positions in &dispatch_lengths(n_pos) {
let mut want = vec![0.0f32; q.len()];
head_major_reference(&q, &cache, layer, positions, scale, &mut want);
let mut got = vec![0.0f32; q.len()];
attention_at(&q, &cache, layer, positions, scale, &mut owned, &mut got)
.unwrap();
let need = scratch_len(n_q, n_kv, head_dim, positions);
let mut carve = vec![0.0f32; need];
let mut got_in = vec![0.0f32; q.len()];
attention_at_in(&q, &cache, layer, positions, scale, &mut carve, &mut got_in)
.unwrap();
let mut got_decode = vec![0.0f32; q.len()];
let mut got_decode_in = vec![0.0f32; q.len()];
if positions == n_pos {
decode_attention(&q, &cache, layer, scale, &mut owned, &mut got_decode)
.unwrap();
decode_attention_in(
&q,
&cache,
layer,
scale,
&mut carve,
&mut got_decode_in,
)
.unwrap();
} else {
got_decode.copy_from_slice(&got);
got_decode_in.copy_from_slice(&got);
}
for (i, &w) in want.iter().enumerate() {
let label = format!(
"geometry ({n_layers}, {n_kv}, {n_q}, {head_dim}) layer {layer} \
positions {positions} elem {i}"
);
assert_eq!(
got[i].to_bits(),
w.to_bits(),
"{label}: attention_at {:e} vs head-major reference {w:e}",
got[i]
);
assert_eq!(
got_in[i].to_bits(),
w.to_bits(),
"{label}: attention_at_in {:e} vs head-major reference {w:e}",
got_in[i]
);
assert_eq!(got_decode[i].to_bits(), w.to_bits(), "{label}: decode");
assert_eq!(
got_decode_in[i].to_bits(),
w.to_bits(),
"{label}: decode_in"
);
}
}
}
}
}
#[test]
fn scratch_len_pins_the_carve() {
assert_eq!(scratch_len(32, 4, 128, 4096), 33_024);
assert_eq!(scratch_len(32, 4, 128, 4096) * 4, 132_096);
assert_eq!(scratch_len(8, 8, 64, 100), 100 + 128);
assert_eq!(scratch_len(8, 1, 8, 7), 8 * 7 + 16);
assert_eq!(scratch_len(4, 0, 8, 10), 16);
assert_eq!(scratch_len(usize::MAX, 1, 1, usize::MAX), usize::MAX);
assert_eq!(scratch_len(2, 1, usize::MAX, 4), usize::MAX);
}
#[test]
fn attention_in_typed_errors_on_short_scratch() {
let (n_kv, n_q, head_dim, n_pos) = (2usize, 8usize, 16usize, 5usize);
let mut rng = Rng::new(0x05C2_47C4);
let (cache, _rows) = random_cache(&mut rng, 1, n_kv, head_dim, n_pos);
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
let scale = 1.0 / (head_dim as f32).sqrt();
let mut out = vec![7.0f32; q.len()];
let need = scratch_len(n_q, n_kv, head_dim, n_pos);
assert_eq!(need, 4 * n_pos + 2 * head_dim);
for len in [0usize, 1, need - 1, 4 * n_pos] {
let mut carve = vec![0.0f32; len];
assert_eq!(
attention_at_in(&q, &cache, 0, n_pos, scale, &mut carve, &mut out).unwrap_err(),
AttentionError::ScratchTooShort { len, need }
);
assert_eq!(
decode_attention_in(&q, &cache, 0, scale, &mut carve, &mut out).unwrap_err(),
AttentionError::ScratchTooShort { len, need }
);
}
let mut carve = vec![0.0f32; 4 * 2];
assert_eq!(
attention_at_in(&q, &cache, 0, 2, scale, &mut carve, &mut out).unwrap_err(),
AttentionError::ScratchTooShort {
len: 8,
need: scratch_len(n_q, n_kv, head_dim, 2),
}
);
let mut empty: Vec<f32> = Vec::new();
assert_eq!(
attention_at_in(&q[..3], &cache, 0, n_pos, scale, &mut empty, &mut out).unwrap_err(),
AttentionError::QLenIndivisible { q_len: 3, head_dim }
);
assert_eq!(
attention_at_in(&q, &cache, 0, n_pos + 1, scale, &mut empty, &mut out).unwrap_err(),
AttentionError::Kv(KvError::PositionOutOfRange {
layer: 0,
pos: n_pos,
len: n_pos,
})
);
assert!(out.iter().all(|&x| x == 7.0));
let mut owned = AttentionScratch::new();
let mut want = vec![0.0f32; q.len()];
attention_at(&q, &cache, 0, n_pos, scale, &mut owned, &mut want).unwrap();
for len in [need, need + 1, need * 3] {
let mut carve = vec![-1.0f32; len];
let mut got = vec![0.0f32; q.len()];
attention_at_in(&q, &cache, 0, n_pos, scale, &mut carve, &mut got).unwrap();
for (i, (&g, &w)) in got.iter().zip(&want).enumerate() {
assert_eq!(g.to_bits(), w.to_bits(), "carve {len} elem {i}");
}
}
}
#[test]
fn group_of_one_maps_each_query_head_to_its_own_kv_head() {
let (n_kv, n_q, head_dim, n_pos) = (4usize, 4usize, 8usize, 6usize);
let scale = 1.0 / (head_dim as f32).sqrt();
let mut rng = Rng::new(0x0612_00F1);
let (cache, _rows) = random_cache(&mut rng, 2, n_kv, head_dim, n_pos);
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
assert_eq!(
scratch_len(n_q, n_kv, head_dim, n_pos),
n_pos + 2 * head_dim
);
let mut owned = AttentionScratch::new();
for layer in 0..2 {
for positions in 1..=n_pos {
let mut want = vec![0.0f32; q.len()];
head_major_reference(&q, &cache, layer, positions, scale, &mut want);
let mut got = vec![0.0f32; q.len()];
attention_at(&q, &cache, layer, positions, scale, &mut owned, &mut got).unwrap();
let mut carve = vec![0.0f32; scratch_len(n_q, n_kv, head_dim, positions)];
let mut got_in = vec![0.0f32; q.len()];
attention_at_in(&q, &cache, layer, positions, scale, &mut carve, &mut got_in)
.unwrap();
for (i, &w) in want.iter().enumerate() {
assert_eq!(got[i].to_bits(), w.to_bits(), "layer {layer} elem {i}");
assert_eq!(got_in[i].to_bits(), w.to_bits(), "layer {layer} elem {i}");
}
}
}
let mut marked = KvCache::new(1, n_kv, head_dim, n_kv).unwrap();
let marker = |j: usize, t: usize| (10 * j + t) as f32 * 0.01;
for t in 0..n_kv {
let mut k = vec![0.0f32; n_kv * head_dim];
let mut v = vec![0.0f32; n_kv * head_dim];
for j in 0..n_kv {
let sign = if t == j { 1.0f32 } else { -1.0 };
for i in 0..head_dim {
k[j * head_dim + i] = sign * 8.0 / head_dim as f32;
v[j * head_dim + i] = marker(j, t);
}
}
marked.append(0, &k, &v).unwrap();
}
let ones = vec![1.0f32; n_q * head_dim];
let mut out = vec![0.0f32; ones.len()];
let mut carve = vec![0.0f32; scratch_len(n_q, n_kv, head_dim, n_kv)];
decode_attention_in(&ones, &marked, 0, 1.0, &mut carve, &mut out).unwrap();
for h in 0..n_q {
for i in 0..head_dim {
let got = out[h * head_dim + i];
let want = marker(h, h);
assert!(
(got - want).abs() < 1e-3,
"q head {h} elem {i}: got {got}, want kv head {h} marker {want}"
);
}
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum KernelPaths {
Both,
ScalarOnly,
}
impl KernelPaths {
fn flags(self) -> &'static [bool] {
match self {
KernelPaths::Both => &[false, true],
KernelPaths::ScalarOnly => &[true],
}
}
}
fn kernel_paths(claim: &str) -> KernelPaths {
let dispatch = avx2_f16c_available();
#[cfg(target_arch = "x86_64")]
{
let cpu = std::arch::is_x86_feature_detected!("avx2")
&& std::arch::is_x86_feature_detected!("f16c");
assert_eq!(
dispatch, cpu,
"kernel dispatch disagrees with this x86_64 CPU: CPUID reports \
avx2+f16c = {cpu}, `avx2_f16c_available()` reports {dispatch}. \
Every attention call dispatches on the latter, so this is a \
live mis-dispatch, not an unsupported host."
);
}
if dispatch {
return KernelPaths::Both;
}
let mut err = std::io::stderr();
let _ = writeln!(
err,
"\n\
##########################################################\n\
# NOT PROVEN ON THIS HOST: {claim}\n\
#\n\
# This host has no AVX2+F16C, so `force_scalar = false`\n\
# dispatches to the same scalar kernel as `force_scalar =\n\
# true`. The scalar arithmetic was exercised in full; the\n\
# AVX2-vs-scalar half of phase 7's bit-identity gate was NOT\n\
# tested. A green run here is not evidence for it. Re-run the\n\
# kernel tests on an AVX2+F16C machine before relying on it.\n\
##########################################################\n"
);
let _ = err.flush();
KernelPaths::ScalarOnly
}
fn dispatch_geometries() -> Vec<(usize, usize, usize, usize, usize)> {
let mut g = LIMITED_GEOMETRIES.to_vec();
g.push((1, 4, 32, 128, 67));
g.push((1, 1, 8, 9, 11));
g.push((2, 3, 6, 9, 13));
g.push((1, 1, 32, 128, 9));
g.push((1, 2, 34, 16, 13));
g.push((1, 1, 12, 9, 11));
g.push((1, 1, 8, 256, 5));
g.push((1, 2, 4, 255, 3));
g
}
fn dispatch_lengths(n_pos: usize) -> Vec<usize> {
let mut lengths: Vec<usize> = [
1usize, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 23, 24, 25, 31, 61,
]
.into_iter()
.filter(|&p| p < n_pos)
.collect();
lengths.push(n_pos);
lengths
}
#[cfg(target_arch = "x86_64")]
#[test]
fn dispatch_lengths_cover_every_position_block_remainder() {
let mut seen = [false; x86::T_BLOCK];
for (.., n_pos) in dispatch_geometries() {
for p in dispatch_lengths(n_pos) {
seen[p % x86::T_BLOCK] = true;
}
}
for (class, &hit) in seen.iter().enumerate() {
assert!(
hit,
"no length in the dispatch sweep leaves `positions % {} == {class}`, so \
the rungs `x86::qk_scores` runs for that remainder are pinned by no \
bit-identity gate. The `T_TAIL_BLOCK` rung in particular fires only \
for classes {}..={}.",
x86::T_BLOCK,
x86::T_TAIL_BLOCK,
x86::T_BLOCK - 1
);
}
}
#[test]
fn simd_matches_scalar_bit_for_bit() {
let paths = kernel_paths("the AVX2+F16C attention path vs the scalar reference");
let mut rng = Rng::new(0x5119_D0A7);
for (n_layers, n_kv, n_q, head_dim, n_pos) in dispatch_geometries() {
if paths == KernelPaths::Both {
assert!(
avx2_f16c_path_covers(head_dim),
"geometry ({n_layers}, {n_kv}, {n_q}, {head_dim}) is outside the AVX2 \
envelope, so sweeping `force_scalar` here would run the scalar kernel \
twice and report it as a two-path proof"
);
}
let scale = 1.0 / (head_dim as f32).sqrt();
let (cache, _rows) = random_cache(&mut rng, n_layers, n_kv, head_dim, n_pos);
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
let mut owned = AttentionScratch::new();
for layer in 0..n_layers {
for &positions in &dispatch_lengths(n_pos) {
let mut want = vec![0.0f32; q.len()];
head_major_reference(&q, &cache, layer, positions, scale, &mut want);
let need = scratch_len(n_q, n_kv, head_dim, positions);
let mut by_path: Vec<Vec<f32>> = Vec::new();
for &force_scalar in paths.flags() {
let mut got = vec![0.0f32; q.len()];
attention_at_dispatch(
&q,
&cache,
layer,
positions,
scale,
&mut owned,
&mut got,
force_scalar,
)
.unwrap();
let mut carve = vec![0.0f32; need];
let mut got_in = vec![0.0f32; q.len()];
attention_at_in_dispatch(
&q,
&cache,
layer,
positions,
scale,
&mut carve,
&mut got_in,
force_scalar,
)
.unwrap();
let mut got_decode = got.clone();
let mut got_decode_in = got.clone();
if positions == n_pos {
decode_attention_dispatch(
&q,
&cache,
layer,
scale,
&mut owned,
&mut got_decode,
force_scalar,
)
.unwrap();
decode_attention_in_dispatch(
&q,
&cache,
layer,
scale,
&mut carve,
&mut got_decode_in,
force_scalar,
)
.unwrap();
}
for (i, &w) in want.iter().enumerate() {
let label = format!(
"geometry ({n_layers}, {n_kv}, {n_q}, {head_dim}) layer \
{layer} positions {positions} force_scalar {force_scalar} \
elem {i}"
);
assert_eq!(
got[i].to_bits(),
w.to_bits(),
"{label}: attention_at_dispatch {:e} vs head-major \
reference {w:e}",
got[i]
);
assert_eq!(got_in[i].to_bits(), w.to_bits(), "{label}: at_in");
assert_eq!(got_decode[i].to_bits(), w.to_bits(), "{label}: decode");
assert_eq!(
got_decode_in[i].to_bits(),
w.to_bits(),
"{label}: decode_in"
);
}
by_path.push(got);
}
if paths == KernelPaths::Both {
let (simd, scalar) = (&by_path[0], &by_path[1]);
for (i, (&s, &r)) in simd.iter().zip(scalar).enumerate() {
assert_eq!(
s.to_bits(),
r.to_bits(),
"geometry ({n_layers}, {n_kv}, {n_q}, {head_dim}) layer \
{layer} positions {positions} elem {i}: AVX2 {s:e} vs \
scalar {r:e}"
);
}
}
}
}
}
}
#[test]
fn misaligned_head_slices_match_the_scalar_reference() {
let paths = kernel_paths("the AVX2+F16C path on 2-byte-aligned head slices");
let mut rng = Rng::new(0x0A11_6EDD);
for &(n_kv, n_q, head_dim, n_pos) in &[
(1usize, 8usize, 9usize, 14usize),
(3, 6, 9, 11),
(3, 3, 17, 9),
(5, 5, 17, 13),
] {
let scale = 1.0 / (head_dim as f32).sqrt();
let (cache, _rows) = random_cache(&mut rng, 2, n_kv, head_dim, n_pos);
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
let mut owned = AttentionScratch::new();
for layer in 0..2 {
for positions in 1..=n_pos {
let mut want = vec![0.0f32; q.len()];
attention_at_dispatch(
&q, &cache, layer, positions, scale, &mut owned, &mut want, true,
)
.unwrap();
let mut got = vec![0.0f32; q.len()];
attention_at_dispatch(
&q, &cache, layer, positions, scale, &mut owned, &mut got, false,
)
.unwrap();
for (i, (&g, &w)) in got.iter().zip(&want).enumerate() {
assert_eq!(
g.to_bits(),
w.to_bits(),
"({n_kv}, {n_q}, {head_dim}) layer {layer} positions \
{positions} elem {i}: AVX2 {g:e} vs scalar {w:e}"
);
}
}
}
}
let _ = paths;
}
#[test]
fn simd_envelope_boundary_at_max_simd_head_dim() {
assert_eq!(avx2_f16c_path_covers(256), avx2_f16c_available());
assert!(!avx2_f16c_path_covers(257));
assert!(!avx2_f16c_path_covers(usize::MAX));
let (n_layers, n_kv, n_q, head_dim, n_pos) = (2usize, 2usize, 4usize, 257usize, 3usize);
let scale = 1.0 / (head_dim as f32).sqrt();
let mut rng = Rng::new(0x2011_B0DD);
let (cache, _rows) = random_cache(&mut rng, n_layers, n_kv, head_dim, n_pos);
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
let mut owned = AttentionScratch::new();
for layer in 0..n_layers {
for positions in 1..=n_pos {
let mut want = vec![0.0f32; q.len()];
head_major_reference(&q, &cache, layer, positions, scale, &mut want);
let mut got = vec![0.0f32; q.len()];
attention_at(&q, &cache, layer, positions, scale, &mut owned, &mut got).unwrap();
for (i, (&g, &w)) in got.iter().zip(&want).enumerate() {
assert_eq!(
g.to_bits(),
w.to_bits(),
"head_dim {head_dim} layer {layer} positions {positions} elem {i}: \
fallback {g:e} vs head-major reference {w:e}"
);
}
}
}
}
#[test]
fn kv_range_union_is_bit_identical_to_the_whole_call() {
let paths = kernel_paths("the kv-head range entry points against the AVX2+F16C path");
let mut rng = Rng::new(0x5EA5_0EDF);
const SENTINEL: f32 = -7.5;
for (n_layers, n_kv, n_q, head_dim, n_pos) in dispatch_geometries() {
let scale = 1.0 / (head_dim as f32).sqrt();
let (cache, _rows) = random_cache(&mut rng, n_layers, n_kv, head_dim, n_pos);
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
let group_dim = (n_q / n_kv) * head_dim;
for layer in 0..n_layers {
for &positions in &dispatch_lengths(n_pos) {
let need = scratch_len(n_q, n_kv, head_dim, positions);
for &force_scalar in paths.flags() {
let label = format!(
"geometry ({n_layers}, {n_kv}, {n_q}, {head_dim}) layer {layer} \
positions {positions} force_scalar {force_scalar}"
);
let mut carve = vec![0.0f32; need];
let mut want = vec![0.0f32; q.len()];
attention_at_in_dispatch(
&q,
&cache,
layer,
positions,
scale,
&mut carve,
&mut want,
force_scalar,
)
.unwrap();
for kv_head in 0..n_kv {
let mut shard = vec![0.0f32; need];
let mut got = vec![SENTINEL; q.len()];
let window = kv_head * group_dim..(kv_head + 1) * group_dim;
attention_at_kv_range_in_dispatch(
&q,
&cache,
layer,
positions,
scale,
kv_head..kv_head + 1,
&mut shard,
&mut got[window.clone()],
force_scalar,
)
.unwrap();
for (i, &g) in got.iter().enumerate() {
let w = if window.contains(&i) {
want[i]
} else {
SENTINEL
};
assert_eq!(
g.to_bits(),
w.to_bits(),
"{label} kv head {kv_head} elem {i}: range {g:e} vs \
{} {w:e}",
if window.contains(&i) {
"whole call"
} else {
"untouched sentinel"
}
);
}
}
let split = n_kv / 2;
let mut got = vec![SENTINEL; q.len()];
{
let (lo, hi) = got.split_at_mut(split * group_dim);
for (range, dst) in [(0..split, lo), (split..n_kv, hi)] {
let mut shard = vec![0.0f32; need];
attention_at_kv_range_in_dispatch(
&q,
&cache,
layer,
positions,
scale,
range,
&mut shard,
dst,
force_scalar,
)
.unwrap();
}
}
for (i, (&g, &w)) in got.iter().zip(&want).enumerate() {
assert_eq!(
g.to_bits(),
w.to_bits(),
"{label} split at {split} elem {i}: {g:e} vs whole call {w:e}"
);
}
let mut idle = vec![SENTINEL; q.len()];
let mut shard = vec![0.0f32; need];
for range in [0..0, n_kv..n_kv] {
attention_at_kv_range_in_dispatch(
&q,
&cache,
layer,
positions,
scale,
range.clone(),
&mut shard,
&mut idle[..0],
force_scalar,
)
.unwrap();
attention_at_kv_range_in_dispatch(
&q,
&cache,
layer,
positions,
scale,
range,
&mut shard,
&mut [],
force_scalar,
)
.unwrap();
}
assert!(
idle.iter().all(|&x| x.to_bits() == SENTINEL.to_bits()),
"{label}: an empty kv range wrote to `out`"
);
if positions == n_pos {
let mut want_decode = vec![0.0f32; q.len()];
decode_attention_in_dispatch(
&q,
&cache,
layer,
scale,
&mut carve,
&mut want_decode,
force_scalar,
)
.unwrap();
let mut got_decode = vec![SENTINEL; q.len()];
for (kv_head, dst) in got_decode.chunks_exact_mut(group_dim).enumerate()
{
let mut shard = vec![0.0f32; need];
decode_attention_kv_range_in_dispatch(
&q,
&cache,
layer,
scale,
kv_head..kv_head + 1,
&mut shard,
dst,
force_scalar,
)
.unwrap();
}
for (i, (&g, &w)) in got_decode.iter().zip(&want_decode).enumerate() {
assert_eq!(
g.to_bits(),
w.to_bits(),
"{label} decode elem {i}: concatenated ranges {g:e} vs \
whole call {w:e}"
);
}
}
}
}
}
}
}
#[test]
fn kv_range_derives_group_from_the_full_query() {
let (n_kv, n_q, head_dim) = (4usize, 32usize, 16usize);
let group = n_q / n_kv;
let group_dim = group * head_dim;
let kv_dim = n_kv * head_dim;
let mut cache = KvCache::new(1, n_kv, head_dim, n_kv).unwrap();
let marker = |j: usize, t: usize| (10 * j + t) as f32 * 0.01;
for t in 0..n_kv {
let mut k = vec![0.0f32; kv_dim];
let mut v = vec![0.0f32; kv_dim];
for j in 0..n_kv {
let sign = if t == j { 1.0f32 } else { -1.0 };
for i in 0..head_dim {
k[j * head_dim + i] = sign * 8.0 / head_dim as f32;
v[j * head_dim + i] = marker(j, t);
}
}
cache.append(0, &k, &v).unwrap();
}
let q = vec![1.0f32; n_q * head_dim];
let need = scratch_len(n_q, n_kv, head_dim, n_kv);
for kv_head in 0..n_kv {
let mut carve = vec![0.0f32; need];
let mut out = vec![f32::NAN; q.len()];
decode_attention_kv_range_in(
&q,
&cache,
0,
1.0,
kv_head..kv_head + 1,
&mut carve,
&mut out[kv_head * group_dim..(kv_head + 1) * group_dim],
)
.unwrap();
for h in 0..n_q {
for i in 0..head_dim {
let got = out[h * head_dim + i];
if h / group == kv_head {
let want = marker(kv_head, kv_head);
assert!(
(got - want).abs() < 1e-3,
"kv head {kv_head} q head {h} elem {i}: got {got}, want \
marker {want} — `group` was not derived from the full q"
);
} else {
assert!(
got.is_nan(),
"kv head {kv_head} wrote q head {h} elem {i} ({got}), which \
belongs to kv head {}",
h / group
);
}
}
}
}
}
#[allow(clippy::reversed_empty_ranges)]
#[test]
fn kv_range_typed_errors_and_scratch_contract() {
let (n_layers, n_kv, n_q, head_dim, n_pos) = (2usize, 4usize, 8usize, 8usize, 5usize);
let scale = 1.0 / (head_dim as f32).sqrt();
let mut rng = Rng::new(0x0BAD_2A46);
let (cache, _rows) = random_cache(&mut rng, n_layers, n_kv, head_dim, n_pos);
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
let need = scratch_len(n_q, n_kv, head_dim, n_pos);
let mut carve = vec![0.0f32; need];
let mut out = vec![7.0f32; q.len()];
for range in [3..1, 0..n_kv + 1, n_kv..n_kv + 1, n_kv + 1..n_kv + 1, 1..0] {
let (start, end) = (range.start, range.end);
assert_eq!(
decode_attention_kv_range_in(
&q,
&cache,
0,
scale,
range.clone(),
&mut carve,
&mut out
)
.unwrap_err(),
AttentionError::KvHeadRangeOutOfRange {
start,
end,
n_kv_heads: n_kv,
}
);
assert_eq!(
attention_at_kv_range_in(&q, &cache, 0, n_pos, scale, range, &mut carve, &mut out)
.unwrap_err(),
AttentionError::KvHeadRangeOutOfRange {
start,
end,
n_kv_heads: n_kv,
}
);
}
assert_eq!(
decode_attention_kv_range_in(&q, &cache, 0, scale, usize::MAX..0, &mut carve, &mut out)
.unwrap_err(),
AttentionError::KvHeadRangeOutOfRange {
start: usize::MAX,
end: 0,
n_kv_heads: n_kv,
}
);
let bad = 9..9;
assert_eq!(
decode_attention_kv_range_in(
&q[..3],
&cache,
0,
scale,
bad.clone(),
&mut carve,
&mut out
)
.unwrap_err(),
AttentionError::QLenIndivisible { q_len: 3, head_dim }
);
assert_eq!(
decode_attention_kv_range_in(
&q[..3 * head_dim],
&cache,
0,
scale,
bad.clone(),
&mut carve,
&mut out
)
.unwrap_err(),
AttentionError::GqaGroupMismatch {
n_q_heads: 3,
n_kv_heads: n_kv,
}
);
assert_eq!(
decode_attention_kv_range_in(
&q,
&cache,
0,
scale,
bad.clone(),
&mut carve,
&mut out[..7]
)
.unwrap_err(),
AttentionError::KvHeadRangeOutOfRange {
start: 9,
end: 9,
n_kv_heads: n_kv,
}
);
assert_eq!(
decode_attention_kv_range_in(
&q,
&cache,
n_layers,
scale,
bad.clone(),
&mut carve,
&mut out
)
.unwrap_err(),
AttentionError::Kv(KvError::LayerOutOfRange {
layer: n_layers,
n_layers,
})
);
assert_eq!(
attention_at_kv_range_in(
&q,
&cache,
0,
n_pos + 1,
scale,
bad.clone(),
&mut carve,
&mut out
)
.unwrap_err(),
AttentionError::Kv(KvError::PositionOutOfRange {
layer: 0,
pos: n_pos,
len: n_pos,
})
);
assert_eq!(
attention_at_kv_range_in(&q, &cache, 0, 0, scale, bad.clone(), &mut carve, &mut out)
.unwrap_err(),
AttentionError::EmptyLayer { layer: 0 }
);
let group_dim = (n_q / n_kv) * head_dim;
for range in [0..1, 0..n_kv, 2..2] {
let win = range.len() * group_dim;
for len in [0usize, need - 1] {
let mut short = vec![0.0f32; len];
assert_eq!(
attention_at_kv_range_in(
&q,
&cache,
0,
n_pos,
scale,
range.clone(),
&mut short,
&mut out[..win]
)
.unwrap_err(),
AttentionError::ScratchTooShort { len, need },
"range {range:?} carve {len}"
);
}
let mut exact = vec![0.0f32; need];
let mut sink = vec![0.0f32; win];
attention_at_kv_range_in(&q, &cache, 0, n_pos, scale, range, &mut exact, &mut sink)
.unwrap();
}
assert!(out.iter().all(|&x| x == 7.0));
}
#[test]
fn kv_range_typed_error_on_wrong_length_out() {
let (n_kv, n_q, head_dim, n_pos) = (4usize, 8usize, 8usize, 5usize);
let group_dim = (n_q / n_kv) * head_dim;
let scale = 1.0 / (head_dim as f32).sqrt();
let mut rng = Rng::new(0x0117_0A7E);
let (cache, _rows) = random_cache(&mut rng, 1, n_kv, head_dim, n_pos);
let q = rng.vec_in(n_q * head_dim, -1.0, 1.0);
let need = scratch_len(n_q, n_kv, head_dim, n_pos);
let mut carve = vec![0.0f32; need];
for range in [0..1, 0..2, 1..n_kv, 0..n_kv, 2..2] {
let expected = range.len() * group_dim;
let mut wrong = vec![q.len(), expected + 1, 0, 1];
if expected > 0 {
wrong.push(expected - 1);
}
wrong.retain(|&len| len != expected);
wrong.sort_unstable();
wrong.dedup();
for len in wrong {
let mut out = vec![f32::NAN; len];
assert_eq!(
decode_attention_kv_range_in(
&q,
&cache,
0,
scale,
range.clone(),
&mut carve,
&mut out
)
.unwrap_err(),
AttentionError::OutLenMismatch {
out_len: len,
expected,
},
"decode, range {range:?}, out {len}"
);
assert_eq!(
attention_at_kv_range_in(
&q,
&cache,
0,
n_pos,
scale,
range.clone(),
&mut carve,
&mut out
)
.unwrap_err(),
AttentionError::OutLenMismatch {
out_len: len,
expected,
},
"attention_at, range {range:?}, out {len}"
);
assert!(
out.iter().all(|x| x.is_nan()),
"range {range:?} out {len}: a rejected call wrote to `out`"
);
}
for probe in 0..2 {
let mut out = vec![f32::NAN; expected];
if probe == 0 {
decode_attention_kv_range_in(
&q,
&cache,
0,
scale,
range.clone(),
&mut carve,
&mut out,
)
.unwrap();
} else {
attention_at_kv_range_in(
&q,
&cache,
0,
n_pos,
scale,
range.clone(),
&mut carve,
&mut out,
)
.unwrap();
}
assert!(
out.iter().all(|x| x.is_finite()),
"range {range:?} probe {probe}: an accepted call left `out` unwritten"
);
}
}
}
}