use crate::kernels::quants::f32_to_f16;
use thiserror::Error;
#[derive(Debug, Error, PartialEq, Eq)]
pub enum KvError {
#[error(
"invalid kv cache dims (n_layers {n_layers}, n_kv_heads {n_kv_heads}, \
head_dim {head_dim}, capacity {capacity}): {reason}"
)]
InvalidDims {
n_layers: usize,
n_kv_heads: usize,
head_dim: usize,
capacity: usize,
reason: &'static str,
},
#[error("kv cache layer {layer} out of range: cache has {n_layers} layers")]
LayerOutOfRange {
layer: usize,
n_layers: usize,
},
#[error("kv cache {what} row has {got} floats, expected {expected} (n_kv_heads * head_dim)")]
RowLenMismatch {
what: &'static str,
got: usize,
expected: usize,
},
#[error("kv cache layer {layer} is full: capacity {capacity} positions")]
CapacityExceeded {
layer: usize,
capacity: usize,
},
#[error("kv cache position {pos} out of range: layer {layer} holds {len} positions")]
PositionOutOfRange {
layer: usize,
pos: usize,
len: usize,
},
#[error(
"kv cache layers hold unequal lengths ({shortest} vs {longest}): \
appends must advance every layer once per token"
)]
RaggedLayers {
shortest: usize,
longest: usize,
},
#[error(
"kv cache truncate to {requested} exceeds the {len} positions held: \
truncation only rewinds, it cannot extend"
)]
TruncateBeyondLength {
requested: usize,
len: usize,
},
}
#[derive(Debug)]
pub struct KvCache {
n_layers: usize,
n_kv_heads: usize,
head_dim: usize,
capacity: usize,
kv_dim: usize,
plane: usize,
k: Vec<u16>,
v: Vec<u16>,
lens: Vec<usize>,
}
impl KvCache {
pub fn new(
n_layers: usize,
n_kv_heads: usize,
head_dim: usize,
capacity: usize,
) -> Result<Self, KvError> {
let (kv_dim, plane, total) = Self::geometry(n_layers, n_kv_heads, head_dim, capacity)?;
Ok(Self {
n_layers,
n_kv_heads,
head_dim,
capacity,
kv_dim,
plane,
k: vec![0; total],
v: vec![0; total],
lens: vec![0; n_layers],
})
}
fn geometry(
n_layers: usize,
n_kv_heads: usize,
head_dim: usize,
capacity: usize,
) -> Result<(usize, usize, usize), KvError> {
let invalid = |reason| KvError::InvalidDims {
n_layers,
n_kv_heads,
head_dim,
capacity,
reason,
};
if n_layers == 0 || n_kv_heads == 0 || head_dim == 0 || capacity == 0 {
return Err(invalid("all dims must be nonzero"));
}
let kv_dim = n_kv_heads
.checked_mul(head_dim)
.ok_or_else(|| invalid("row width overflows usize"))?;
let plane = capacity
.checked_mul(kv_dim)
.ok_or_else(|| invalid("plane size overflows usize"))?;
let total = n_layers
.checked_mul(plane)
.ok_or_else(|| invalid("total size overflows usize"))?;
Ok((kv_dim, plane, total))
}
pub fn projected_bytes(
n_layers: usize,
n_kv_heads: usize,
head_dim: usize,
capacity: usize,
) -> Result<u64, KvError> {
let (_, _, total) = Self::geometry(n_layers, n_kv_heads, head_dim, capacity)?;
let invalid = |reason| KvError::InvalidDims {
n_layers,
n_kv_heads,
head_dim,
capacity,
reason,
};
let bytes = total
.checked_mul(2)
.and_then(|elems| elems.checked_mul(size_of::<u16>()))
.ok_or_else(|| invalid("total size in bytes overflows usize"))?;
u64::try_from(bytes).map_err(|_| invalid("total size in bytes overflows u64"))
}
pub fn n_layers(&self) -> usize {
self.n_layers
}
pub fn n_kv_heads(&self) -> usize {
self.n_kv_heads
}
pub fn head_dim(&self) -> usize {
self.head_dim
}
pub fn capacity(&self) -> usize {
self.capacity
}
pub fn kv_dim(&self) -> usize {
self.kv_dim
}
pub fn len(&self, layer: usize) -> Result<usize, KvError> {
self.check_layer(layer)?;
Ok(self.lens[layer])
}
pub fn is_empty(&self) -> bool {
self.lens.iter().all(|&len| len == 0)
}
pub fn seq_len(&self) -> Result<usize, KvError> {
let (shortest, longest) = self
.lens
.iter()
.fold((usize::MAX, 0), |(lo, hi), &len| (lo.min(len), hi.max(len)));
if shortest != longest {
return Err(KvError::RaggedLayers { shortest, longest });
}
Ok(shortest)
}
pub fn append(&mut self, layer: usize, k: &[f32], v: &[f32]) -> Result<(), KvError> {
self.check_layer(layer)?;
if k.len() != self.kv_dim {
return Err(KvError::RowLenMismatch {
what: "k",
got: k.len(),
expected: self.kv_dim,
});
}
if v.len() != self.kv_dim {
return Err(KvError::RowLenMismatch {
what: "v",
got: v.len(),
expected: self.kv_dim,
});
}
let len = self.lens[layer];
if len == self.capacity {
return Err(KvError::CapacityExceeded {
layer,
capacity: self.capacity,
});
}
let base = layer * self.plane + len * self.kv_dim;
for (dst, &src) in self.k[base..base + self.kv_dim].iter_mut().zip(k) {
*dst = f32_to_f16(src);
}
for (dst, &src) in self.v[base..base + self.kv_dim].iter_mut().zip(v) {
*dst = f32_to_f16(src);
}
self.lens[layer] = len + 1;
Ok(())
}
pub fn clear(&mut self) {
self.lens.fill(0);
}
pub fn truncate(&mut self, new_len: usize) -> Result<(), KvError> {
let len = self.seq_len()?;
if new_len > len {
return Err(KvError::TruncateBeyondLength {
requested: new_len,
len,
});
}
self.lens.fill(new_len);
Ok(())
}
pub fn k_row(&self, layer: usize, pos: usize) -> Result<&[u16], KvError> {
self.row(&self.k, layer, pos)
}
pub fn v_row(&self, layer: usize, pos: usize) -> Result<&[u16], KvError> {
self.row(&self.v, layer, pos)
}
pub fn k_layer(&self, layer: usize) -> Result<&[u16], KvError> {
self.layer_view(&self.k, layer)
}
pub fn v_layer(&self, layer: usize) -> Result<&[u16], KvError> {
self.layer_view(&self.v, layer)
}
fn check_layer(&self, layer: usize) -> Result<(), KvError> {
if layer >= self.n_layers {
return Err(KvError::LayerOutOfRange {
layer,
n_layers: self.n_layers,
});
}
Ok(())
}
fn row<'a>(&self, plane: &'a [u16], layer: usize, pos: usize) -> Result<&'a [u16], KvError> {
self.check_layer(layer)?;
let len = self.lens[layer];
if pos >= len {
return Err(KvError::PositionOutOfRange { layer, pos, len });
}
let start = layer * self.plane + pos * self.kv_dim;
Ok(&plane[start..start + self.kv_dim])
}
fn layer_view<'a>(&self, plane: &'a [u16], layer: usize) -> Result<&'a [u16], KvError> {
self.check_layer(layer)?;
let start = layer * self.plane;
Ok(&plane[start..start + self.lens[layer] * self.kv_dim])
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::kernels::quants::f16_to_f32;
fn sample(i: usize) -> f32 {
let h = (i as u32).wrapping_mul(2_654_435_761);
(h % 20_000) as f32 / 10_000.0 - 1.0
}
fn filled_row(tag: usize, kv_dim: usize) -> Vec<f32> {
(0..kv_dim).map(|i| sample(tag * kv_dim + i)).collect()
}
#[test]
fn new_rejects_zero_dims_and_overflow() {
for (l, h, d, c) in [
(0, 4, 128, 8),
(48, 0, 128, 8),
(48, 4, 0, 8),
(48, 4, 128, 0),
] {
assert_eq!(
KvCache::new(l, h, d, c).unwrap_err(),
KvError::InvalidDims {
n_layers: l,
n_kv_heads: h,
head_dim: d,
capacity: c,
reason: "all dims must be nonzero",
}
);
}
assert!(matches!(
KvCache::new(usize::MAX, usize::MAX, 2, 2).unwrap_err(),
KvError::InvalidDims { .. }
));
}
#[test]
fn projected_bytes_is_what_new_actually_allocates() {
for (l, h, d, c) in [(1, 1, 1, 1), (2, 2, 64, 8), (48, 4, 128, 3), (7, 3, 16, 40)] {
let cache = KvCache::new(l, h, d, c).unwrap();
let allocated = (cache.k.len() + cache.v.len()) * size_of::<u16>();
assert_eq!(
KvCache::projected_bytes(l, h, d, c).unwrap(),
allocated as u64,
"geometry {l}x{h}x{d} at capacity {c}"
);
}
}
#[test]
fn projected_bytes_is_ninety_six_kibibytes_a_token_at_the_v0_geometry() {
for cap in [1usize, 512, 4096, 16_384] {
assert_eq!(
KvCache::projected_bytes(48, 4, 128, cap).unwrap(),
cap as u64 * 96 * 1024
);
}
assert_eq!(
KvCache::projected_bytes(48, 4, 128, 4096).unwrap(),
384 << 20
);
}
#[test]
fn projected_bytes_rejects_exactly_what_new_rejects() {
for (l, h, d, c) in [
(0, 4, 128, 8),
(48, 0, 128, 8),
(48, 4, 0, 8),
(48, 4, 128, 0),
(usize::MAX, usize::MAX, 2, 2),
(48, 4, 128, usize::MAX),
] {
assert!(
KvCache::projected_bytes(l, h, d, c).is_err(),
"geometry {l}x{h}x{d} at capacity {c} must not project a number"
);
}
assert!(matches!(
KvCache::projected_bytes(1, 1, 1, usize::MAX / 2).unwrap_err(),
KvError::InvalidDims { .. }
));
}
#[test]
fn f16_round_trip_through_cache() {
let kv_dim = 2 * 8;
let mut cache = KvCache::new(2, 2, 8, 4).unwrap();
let k = filled_row(0, kv_dim);
let v = filled_row(1, kv_dim);
cache.append(0, &k, &v).unwrap();
cache.append(1, &v, &k).unwrap();
let k_bits = cache.k_row(0, 0).unwrap();
let v_bits = cache.v_row(0, 0).unwrap();
for i in 0..kv_dim {
assert_eq!(k_bits[i], f32_to_f16(k[i]));
assert_eq!(v_bits[i], f32_to_f16(v[i]));
let back = f16_to_f32(k_bits[i]);
assert!(
(back - k[i]).abs() <= k[i].abs() * 4.9e-4 + 6.0e-8,
"index {i}: {back} vs {}",
k[i]
);
}
assert_eq!(cache.k_row(1, 0).unwrap()[0], f32_to_f16(v[0]));
}
#[test]
fn append_advances_rows_and_layer_views() {
let kv_dim = 3 * 4;
let mut cache = KvCache::new(1, 3, 4, 8).unwrap();
let rows: Vec<Vec<f32>> = (0..5).map(|t| filled_row(t, kv_dim)).collect();
for row in &rows {
cache.append(0, row, row).unwrap();
}
assert_eq!(cache.len(0).unwrap(), 5);
assert_eq!(cache.seq_len().unwrap(), 5);
assert!(!cache.is_empty());
let k_all = cache.k_layer(0).unwrap();
assert_eq!(k_all.len(), 5 * kv_dim);
for (t, row) in rows.iter().enumerate() {
let via_row = cache.k_row(0, t).unwrap();
assert_eq!(&k_all[t * kv_dim..(t + 1) * kv_dim], via_row);
assert_eq!(via_row[3], f32_to_f16(row[3]));
}
}
#[test]
fn typed_errors_on_misuse() {
let mut cache = KvCache::new(2, 2, 4, 3).unwrap();
let row = vec![0.5f32; 8];
let oor = KvError::LayerOutOfRange {
layer: 2,
n_layers: 2,
};
assert_eq!(cache.append(2, &row, &row).unwrap_err(), oor);
assert_eq!(cache.len(2).unwrap_err(), oor);
assert_eq!(cache.k_row(2, 0).unwrap_err(), oor);
assert_eq!(cache.v_row(2, 0).unwrap_err(), oor);
assert_eq!(cache.k_layer(2).unwrap_err(), oor);
assert_eq!(cache.v_layer(2).unwrap_err(), oor);
assert_eq!(
cache.append(0, &row[..7], &row).unwrap_err(),
KvError::RowLenMismatch {
what: "k",
got: 7,
expected: 8,
}
);
assert_eq!(
cache.append(0, &row, &[]).unwrap_err(),
KvError::RowLenMismatch {
what: "v",
got: 0,
expected: 8,
}
);
cache.append(0, &row, &row).unwrap();
assert_eq!(
cache.k_row(0, 1).unwrap_err(),
KvError::PositionOutOfRange {
layer: 0,
pos: 1,
len: 1,
}
);
assert_eq!(
cache.v_row(1, 0).unwrap_err(),
KvError::PositionOutOfRange {
layer: 1,
pos: 0,
len: 0,
}
);
cache.append(0, &row, &row).unwrap();
cache.append(0, &row, &row).unwrap();
assert_eq!(
cache.append(0, &row, &row).unwrap_err(),
KvError::CapacityExceeded {
layer: 0,
capacity: 3,
}
);
assert_eq!(cache.len(0).unwrap(), 3);
}
#[test]
fn clear_rewinds_every_layer() {
let mut cache = KvCache::new(2, 2, 4, 3).unwrap();
let row = [0.5f32; 8];
cache.append(0, &row, &row).unwrap();
cache.append(0, &row, &row).unwrap();
cache.append(1, &row, &row).unwrap();
assert!(!cache.is_empty());
cache.clear();
assert!(cache.is_empty());
assert_eq!(cache.seq_len().unwrap(), 0);
assert_eq!(cache.len(0).unwrap(), 0);
assert_eq!(cache.k_layer(0).unwrap().len(), 0);
assert_eq!(
cache.k_row(0, 0).unwrap_err(),
KvError::PositionOutOfRange {
layer: 0,
pos: 0,
len: 0,
}
);
cache.append(0, &row, &row).unwrap();
assert!(cache.seq_len().is_err());
cache.clear();
assert_eq!(cache.seq_len().unwrap(), 0);
for _ in 0..3 {
cache.append(0, &row, &row).unwrap();
}
assert_eq!(cache.len(0).unwrap(), 3);
}
#[test]
fn truncate_rewinds_every_layer_to_a_prefix() {
let kv_dim = 2 * 4;
let mut cache = KvCache::new(2, 2, 4, 6).unwrap();
let rows: Vec<Vec<f32>> = (0..5).map(|t| filled_row(t, kv_dim)).collect();
for row in &rows {
cache.append(0, row, row).unwrap();
cache.append(1, row, row).unwrap();
}
assert_eq!(cache.seq_len().unwrap(), 5);
let before: Vec<(Vec<u16>, Vec<u16>)> = (0..3)
.map(|pos| {
(
cache.k_row(0, pos).unwrap().to_vec(),
cache.v_row(1, pos).unwrap().to_vec(),
)
})
.collect();
cache.truncate(3).unwrap();
assert_eq!(cache.seq_len().unwrap(), 3);
assert_eq!(cache.len(0).unwrap(), 3);
assert_eq!(cache.len(1).unwrap(), 3);
assert!(!cache.is_empty());
assert_eq!(cache.k_layer(0).unwrap().len(), 3 * kv_dim);
assert_eq!(cache.v_layer(1).unwrap().len(), 3 * kv_dim);
for (pos, (k, v)) in before.iter().enumerate() {
assert_eq!(cache.k_row(0, pos).unwrap(), &k[..], "k row {pos} moved");
assert_eq!(cache.v_row(1, pos).unwrap(), &v[..], "v row {pos} moved");
}
assert_eq!(
cache.k_row(0, 3).unwrap_err(),
KvError::PositionOutOfRange {
layer: 0,
pos: 3,
len: 3,
}
);
let fresh = filled_row(99, kv_dim);
cache.append(0, &fresh, &fresh).unwrap();
cache.append(1, &fresh, &fresh).unwrap();
assert_eq!(cache.seq_len().unwrap(), 4);
assert_eq!(cache.k_row(0, 3).unwrap()[0], f32_to_f16(fresh[0]));
assert_ne!(
cache.k_row(0, 3).unwrap(),
cache.k_row(0, 2).unwrap(),
"the fixture rows must differ or this test proves nothing"
);
cache.truncate(4).unwrap();
assert_eq!(cache.seq_len().unwrap(), 4);
cache.truncate(0).unwrap();
assert!(cache.is_empty());
assert_eq!(cache.seq_len().unwrap(), 0);
}
#[test]
fn truncate_refuses_ragged_and_upward() {
let mut cache = KvCache::new(2, 2, 4, 4).unwrap();
let row = [0.5f32; 8];
cache.append(0, &row, &row).unwrap();
let ragged = KvError::RaggedLayers {
shortest: 0,
longest: 1,
};
assert_eq!(cache.truncate(0).unwrap_err(), ragged);
assert_eq!(cache.truncate(1).unwrap_err(), ragged);
assert_eq!(
cache.len(0).unwrap(),
1,
"a refused truncate moved a cursor"
);
assert_eq!(cache.len(1).unwrap(), 0);
cache.clear();
assert_eq!(cache.seq_len().unwrap(), 0);
cache.append(0, &row, &row).unwrap();
cache.append(1, &row, &row).unwrap();
cache.append(0, &row, &row).unwrap();
cache.append(1, &row, &row).unwrap();
assert_eq!(
cache.truncate(3).unwrap_err(),
KvError::TruncateBeyondLength {
requested: 3,
len: 2,
}
);
assert_eq!(
cache.truncate(usize::MAX).unwrap_err(),
KvError::TruncateBeyondLength {
requested: usize::MAX,
len: 2,
}
);
assert_eq!(
cache.seq_len().unwrap(),
2,
"a refused truncate moved a cursor"
);
}
#[test]
fn seq_len_rejects_ragged_layers() {
let mut cache = KvCache::new(3, 1, 4, 4).unwrap();
assert_eq!(cache.seq_len().unwrap(), 0);
assert!(cache.is_empty());
let row = [1.0f32; 4];
cache.append(0, &row, &row).unwrap();
assert_eq!(
cache.seq_len().unwrap_err(),
KvError::RaggedLayers {
shortest: 0,
longest: 1,
}
);
cache.append(1, &row, &row).unwrap();
cache.append(2, &row, &row).unwrap();
assert_eq!(cache.seq_len().unwrap(), 1);
}
}