use alloc::vec::Vec;
use burn::{
Tensor,
config::Config,
module::Module,
prelude::s,
tensor::{
DType,
Device,
Int,
TensorData,
},
};
use crate::contracts::{
assert_shape_contract_periodically,
unpack_shape_contract,
};
pub trait KVCacheMeta {
fn batch_size(&self) -> usize;
fn num_heads(&self) -> usize;
fn seq_len(&self) -> usize;
fn head_dim(&self) -> usize;
fn num_layers(&self) -> usize;
fn chunk_size(&self) -> usize;
fn max_seq_len(&self) -> Option<usize>;
}
pub trait KVCacheModel {
fn kv_cache_config(&self) -> KVCacheConfig;
fn new_kv_cache(
&self,
batch_size: usize,
) -> KVCache {
self.kv_cache_config().with_batch_size(batch_size).init()
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub enum KVCacheStorage {
#[default]
Auto,
Concat,
PerLayer,
MultiLayer,
}
impl KVCacheStorage {
pub fn resolve(
self,
device: &Device,
) -> Self {
match self {
Self::Auto => Self::auto_for(device),
storage => storage,
}
}
pub fn auto_for(device: &Device) -> Self {
let stack = BackendStack::of(device);
match (stack.fused, stack.runtime) {
(true, Runtime::Wgpu) => Self::Concat,
_ => Self::PerLayer,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct BackendStack {
fused: bool,
runtime: Runtime,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Runtime {
Wgpu,
Cuda,
Other,
}
impl BackendStack {
fn of(device: &Device) -> Self {
use burn_backend::Backend;
Self::parse(&burn_dispatch::Dispatch::name(device.as_dispatch()))
}
fn parse(name: &str) -> Self {
let runtime = if name.contains("cubecl<wgpu") {
Runtime::Wgpu
} else if name.contains("cubecl<cuda") {
Runtime::Cuda
} else {
Runtime::Other
};
Self {
fused: name.contains("fusion<"),
runtime,
}
}
}
#[derive(Config, Debug)]
pub struct KVCacheConfig {
pub batch_size: usize,
pub num_heads: usize,
pub seq_len: usize,
pub head_dim: usize,
pub num_layers: usize,
#[config(default = "1024")]
pub chunk_size: usize,
#[config(default = "None")]
pub max_seq_len: Option<usize>,
#[config(default = "KVCacheStorage::Auto")]
pub storage: KVCacheStorage,
#[config(default = "Vec::new()")]
pub layer_windows: Vec<Option<usize>>,
}
impl KVCacheConfig {
pub fn for_decode(
num_heads: usize,
seq_len: usize,
head_dim: usize,
num_layers: usize,
) -> Self {
Self::new(1, num_heads, seq_len, head_dim, num_layers)
}
pub fn with_batch_size(
self,
batch_size: usize,
) -> Self {
Self { batch_size, ..self }
}
pub fn with_seq_len(
self,
seq_len: usize,
) -> Self {
Self { seq_len, ..self }
}
}
impl KVCacheMeta for KVCacheConfig {
fn batch_size(&self) -> usize {
self.batch_size
}
fn num_heads(&self) -> usize {
self.num_heads
}
fn seq_len(&self) -> usize {
self.seq_len
}
fn head_dim(&self) -> usize {
self.head_dim
}
fn num_layers(&self) -> usize {
self.num_layers
}
fn chunk_size(&self) -> usize {
self.chunk_size
}
fn max_seq_len(&self) -> Option<usize> {
self.max_seq_len
}
}
impl KVCacheConfig {
pub fn init(self) -> KVCache {
assert!(
self.chunk_size > 0,
"a KV cache's chunk_size must be positive"
);
if let Some(max) = self.max_seq_len {
assert!(
self.seq_len <= max,
"a KV cache's seq_len ({}) exceeds its max_seq_len ({max})",
self.seq_len
);
}
assert!(
self.layer_windows.is_empty() || self.layer_windows.len() == self.num_layers,
"a KV cache's layer_windows has {} entries for {} layers",
self.layer_windows.len(),
self.num_layers
);
assert!(
self.layer_windows.iter().flatten().all(|&w| w > 0),
"a KV cache layer's window must be positive"
);
let layer_windows = if self.layer_windows.is_empty() {
vec![None; self.num_layers]
} else {
self.layer_windows
};
KVCache {
batch_size: self.batch_size,
num_heads: self.num_heads,
seq_len: self.seq_len,
head_dim: self.head_dim,
num_layers: self.num_layers,
pos: 0,
cache: None,
chunk_size: self.chunk_size,
extra_chunks: 1,
max_seq_len: self.max_seq_len,
storage: self.storage,
resolved: None,
keys: vec![None; self.num_layers],
values: vec![None; self.num_layers],
cross_keys: vec![None; self.num_layers],
cross_values: vec![None; self.num_layers],
group: 1,
window_start: vec![0; self.num_layers],
layer_windows,
}
}
}
#[derive(Module, Debug)]
pub struct KVCache {
batch_size: usize,
num_heads: usize,
seq_len: usize,
head_dim: usize,
num_layers: usize,
chunk_size: usize,
extra_chunks: usize,
max_seq_len: Option<usize>,
#[module(skip)]
storage: KVCacheStorage,
#[module(skip)]
resolved: Option<KVCacheStorage>,
pos: usize,
cache: Option<Tensor<6>>,
keys: Vec<Option<Tensor<4>>>,
values: Vec<Option<Tensor<4>>>,
cross_keys: Vec<Option<Tensor<4>>>,
cross_values: Vec<Option<Tensor<4>>>,
group: usize,
#[module(skip)]
layer_windows: Vec<Option<usize>>,
window_start: Vec<usize>,
}
impl KVCacheMeta for KVCache {
fn batch_size(&self) -> usize {
self.batch_size
}
fn num_heads(&self) -> usize {
self.num_heads
}
fn seq_len(&self) -> usize {
self.seq_len
}
fn head_dim(&self) -> usize {
self.head_dim
}
fn num_layers(&self) -> usize {
self.num_layers
}
fn chunk_size(&self) -> usize {
self.chunk_size
}
fn max_seq_len(&self) -> Option<usize> {
self.max_seq_len
}
}
impl KVCache {
pub fn reset(&mut self) {
self.pos = 0;
self.window_start.fill(0);
}
pub fn truncate(
&mut self,
pos: usize,
) {
assert!(
pos <= self.pos,
"cannot truncate a KV cache at {} to {pos}",
self.pos
);
assert!(
pos == 0 || pos >= self.retained_from(),
"cannot truncate a KV cache to {pos}: a sliding window keeps positions from {} on",
self.retained_from()
);
if pos == 0 {
self.window_start.fill(0);
}
self.pos = pos;
}
pub fn retained_from(&self) -> usize {
self.window_start.iter().copied().max().unwrap_or(0)
}
pub fn can_truncate(
&self,
pos: usize,
) -> bool {
pos <= self.pos && (pos == 0 || pos >= self.retained_from())
}
pub fn layer_windows(&self) -> &[Option<usize>] {
&self.layer_windows
}
pub fn pos(&self) -> usize {
self.pos
}
pub fn storage(&self) -> KVCacheStorage {
self.resolved.unwrap_or(self.storage)
}
pub fn group(&self) -> usize {
self.group
}
pub fn set_cross_kv(
&mut self,
layer: usize,
k: Tensor<4>,
v: Tensor<4>,
) {
let [rows, heads, _, head_dim] = k.dims();
assert_eq!(
k.dims(),
v.dims(),
"cross-attention keys and values differ in shape"
);
assert_eq!(
(heads, head_dim),
(self.num_heads, self.head_dim),
"cross-attention heads and head width are the cache's"
);
assert!(
rows > 0 && self.batch_size.is_multiple_of(rows),
"the cache's batch ({}) is not a whole multiple of the cross-attention rows ({rows})",
self.batch_size
);
let group = self.batch_size / rows;
let others_set = self
.cross_keys
.iter()
.enumerate()
.any(|(l, c)| l != layer && c.is_some());
if others_set {
assert_eq!(
group, self.group,
"every layer's cross-attention shares one group"
);
}
self.group = group;
self.cross_keys[layer] = Some(k);
self.cross_values[layer] = Some(v);
}
pub fn cross_kv(
&self,
layer: usize,
) -> Option<(Tensor<4>, Tensor<4>)> {
Some((
self.cross_keys[layer].clone()?,
self.cross_values[layer].clone()?,
))
}
pub fn dtype(&self) -> Option<DType> {
let tensor = self
.cross_keys
.iter()
.chain(&self.keys)
.flatten()
.next()
.map(Tensor::dtype);
tensor.or_else(|| self.cache.as_ref().map(Tensor::dtype))
}
pub fn reorder(
&mut self,
sources: &[usize],
) {
assert_eq!(
sources.len(),
self.batch_size,
"one source row per batch row"
);
assert!(
sources.iter().all(|&s| s < self.batch_size),
"a source row past the batch"
);
if !self.is_allocated() || sources.iter().enumerate().all(|(r, &s)| r == s) {
return;
}
let device = match (&self.cache, self.keys.iter().flatten().next()) {
(Some(cache), _) => cache.device(),
(None, Some(key)) => key.device(),
(None, None) => return,
};
let indices: Tensor<1, Int> = Tensor::from_data(
TensorData::new(
sources.iter().map(|&s| s as i64).collect::<Vec<_>>(),
[sources.len()],
),
&device,
);
if let Some(cache) = self.cache.take() {
self.cache = Some(cache.select(2, indices.clone()));
}
for slot in self.keys.iter_mut().chain(self.values.iter_mut()) {
if let Some(history) = slot.take() {
*slot = Some(history.select(0, indices.clone()));
}
}
}
fn is_allocated(&self) -> bool {
self.cache.is_some() || self.keys.iter().any(Option::is_some)
}
pub fn prefill(
&mut self,
other: &KVCache,
) {
assert!(!self.is_allocated(), "Cannot prefill a non-empty KV cache.");
assert!(other.is_allocated(), "Cannot prefill from a None KV cache.");
assert_eq!(self.num_layers, other.num_layers);
assert_eq!(self.num_heads, other.num_heads);
assert_eq!(self.head_dim, other.head_dim);
if self.batch_size != other.batch_size && other.batch_size != 1 {
panic!(
"Incompatible pre-fill batch size: {} vs {}",
self.batch_size, other.batch_size
);
}
assert!(self.seq_len >= other.seq_len);
assert_eq!(
self.layer_windows, other.layer_windows,
"a KV cache prefills from one with the same windows"
);
if other.pos > 0 {
for layer in 0..self.num_layers {
let (k, v) = other.history(layer);
let start = other.window_start[layer];
let shape = [
self.batch_size,
self.num_heads,
other.pos - start,
self.head_dim,
];
self.window_start[layer] = start;
self.write(layer, start, k.expand(shape), v.expand(shape));
}
}
self.pos = other.pos;
}
fn history(
&self,
layer: usize,
) -> (Tensor<4>, Tensor<4>) {
let t = self.pos;
if self.layer_windows[layer].is_some() {
let held = t - self.window_start[layer];
let retained = |slot: &Option<Tensor<4>>| {
slot.clone()
.expect("an allocated cache holds every layer")
.slice(s![.., .., ..held])
};
return (retained(&self.keys[layer]), retained(&self.values[layer]));
}
match &self.cache {
Some(cache) => (
cache
.clone()
.slice(s![layer, 0, .., .., ..t])
.squeeze_dims::<4>(&[0, 1]),
cache
.clone()
.slice(s![layer, 1, .., .., ..t])
.squeeze_dims::<4>(&[0, 1]),
),
None => {
let held = |slot: &Option<Tensor<4>>| {
slot.clone()
.expect("an allocated cache holds every layer")
.slice(s![.., .., ..t])
};
(held(&self.keys[layer]), held(&self.values[layer]))
}
}
}
pub fn insert_kv(
&mut self,
layer_idx: usize,
k: Tensor<4>,
v: Tensor<4>,
) -> (Tensor<4>, Tensor<4>) {
let [t_add] = unpack_shape_contract!(
["B", "H_kv", "T_add", "D"],
&k.dims(),
&["T_add"],
&[
("B", self.batch_size),
("H_kv", self.num_heads),
("D", self.head_dim)
]
);
assert_shape_contract_periodically!(
["B", "H_kv", "T_add", "D"],
&v.dims(),
&[
("B", self.batch_size),
("H_kv", self.num_heads),
("T_add", t_add),
("D", self.head_dim)
]
);
let t0 = self.pos;
let t1 = t0 + t_add;
if let Some(max) = self.max_seq_len {
assert!(
t1 <= max,
"a KV cache step past its max_seq_len: {t0} + {t_add} > {max}"
);
}
let history = self.write(layer_idx, t0, k, v);
if layer_idx == self.num_layers - 1 {
self.pos = t1;
}
history
}
fn write(
&mut self,
layer: usize,
t0: usize,
k: Tensor<4>,
v: Tensor<4>,
) -> (Tensor<4>, Tensor<4>) {
if let Some(window) = self.layer_windows[layer] {
return self.write_window(layer, window, t0, k, v);
}
let t1 = t0 + k.dims()[2];
let configured = self.storage;
let storage = *self
.resolved
.get_or_insert_with(|| configured.resolve(&k.device()));
match storage {
KVCacheStorage::MultiLayer => self.write_multi_layer(layer, t0, t1, k, v),
KVCacheStorage::PerLayer => {
let key = self.keys[layer].take();
let value = self.values[layer].take();
let (key, k) = self.write_buffer(key, t0, t1, k);
let (value, v) = self.write_buffer(value, t0, t1, v);
self.keys[layer] = Some(key);
self.values[layer] = Some(value);
(k, v)
}
KVCacheStorage::Concat => {
let k = Self::concat(self.keys[layer].take(), t0, k);
let v = Self::concat(self.values[layer].take(), t0, v);
self.keys[layer] = Some(k.clone());
self.values[layer] = Some(v.clone());
(k, v)
}
KVCacheStorage::Auto => unreachable!("resolved above"),
}
}
fn write_window(
&mut self,
layer: usize,
window: usize,
t0: usize,
k: Tensor<4>,
v: Tensor<4>,
) -> (Tensor<4>, Tensor<4>) {
let start = self.window_start[layer];
assert!(
t0 >= start,
"a KV cache layer's window starts at {start}, past a write at {t0}"
);
let held = t0 - start;
let k = Self::concat(self.keys[layer].take(), held, k);
let v = Self::concat(self.values[layer].take(), held, v);
let len = k.dims()[2];
let keep = len.min(window - 1);
self.window_start[layer] = start + (len - keep);
let tail = |x: &Tensor<4>| x.clone().slice(s![.., .., len - keep..]);
self.keys[layer] = Some(tail(&k));
self.values[layer] = Some(tail(&v));
(k, v)
}
fn write_buffer(
&self,
buffer: Option<Tensor<4>>,
t0: usize,
t1: usize,
x: Tensor<4>,
) -> (Tensor<4>, Tensor<4>) {
let [batch, heads, _, head_dim] = x.dims();
let allocate = |len: usize| {
Tensor::<4>::empty([batch, heads, len, head_dim], &x.device()).cast(x.dtype())
};
let buffer = match buffer {
None if t1 <= self.seq_len => allocate(self.seq_len),
None => allocate(self.allocation_size(t1)),
Some(buffer) if buffer.dims()[2] >= t1 => buffer,
Some(buffer) => {
let held = buffer.dims()[2];
allocate(self.allocation_size(t1)).slice_assign(s![.., .., ..held], buffer)
}
};
let buffer = buffer.slice_assign(s![.., .., t0..t1], x);
let history = buffer.clone().slice(s![.., .., ..t1]);
(buffer, history)
}
fn concat(
history: Option<Tensor<4>>,
t0: usize,
x: Tensor<4>,
) -> Tensor<4> {
match history {
Some(history) if t0 > 0 => {
let history = if history.dims()[2] > t0 {
history.slice(s![.., .., ..t0])
} else {
history
};
Tensor::cat(vec![history, x], 2)
}
None if t0 > 0 => panic!("a KV cache layer has no history to extend at {t0}"),
_ => x,
}
}
fn write_multi_layer(
&mut self,
layer: usize,
t0: usize,
t1: usize,
k: Tensor<4>,
v: Tensor<4>,
) -> (Tensor<4>, Tensor<4>) {
let dtype = k.dtype();
let device = k.device();
let mut cache = match self.cache.take() {
Some(cache) => cache,
None if t1 <= self.seq_len => self.allocate(self.seq_len, dtype, &device),
None => self.allocate(self.allocation_size(t1), dtype, &device),
};
let cached_size = cache.dims()[4];
if t1 > cached_size {
let needed_t = self.allocation_size(t1);
cache = self
.allocate(needed_t, dtype, &device)
.slice_assign(s![.., .., .., .., ..cached_size, ..], cache);
}
cache = cache
.slice_assign(s![layer, 0, .., .., t0..t1], k.unsqueeze())
.slice_assign(s![layer, 1, .., .., t0..t1], v.unsqueeze());
let k = cache
.clone()
.slice(s![layer, 0, .., .., ..t1])
.squeeze_dims::<4>(&[0, 1]);
let v = cache
.clone()
.slice(s![layer, 1, .., .., ..t1])
.squeeze_dims::<4>(&[0, 1]);
self.cache = Some(cache);
(k, v)
}
fn allocate(
&self,
seq_len: usize,
dtype: DType,
device: &Device,
) -> Tensor<6> {
Tensor::<6>::empty(
[
self.num_layers,
2,
self.batch_size,
self.num_heads,
seq_len,
self.head_dim,
],
device,
)
.cast(dtype)
}
pub fn allocation_size(
&self,
required_size: usize,
) -> usize {
let size = (required_size.div_ceil(self.chunk_size) + self.extra_chunks) * self.chunk_size;
match self.max_seq_len {
Some(max) => size.min(max).max(required_size),
None => size,
}
}
#[cfg(test)]
fn held_len(&self) -> Option<usize> {
match &self.cache {
Some(cache) => Some(cache.dims()[4]),
None => self.keys[0].as_ref().map(|k| k.dims()[2]),
}
}
}
#[cfg(test)]
mod tests {
use burn::tensor::Distribution;
use serial_test::serial;
use super::*;
use crate::support::testing::{
DeviceMemoryGuard,
cpu_device,
performance_device,
seeded_tensor,
};
const STORAGES: [KVCacheStorage; 3] = [
KVCacheStorage::Concat,
KVCacheStorage::PerLayer,
KVCacheStorage::MultiLayer,
];
fn fill(
cache: &mut KVCache,
t_add: usize,
device: &Device,
) -> Vec<(Tensor<4>, Tensor<4>)> {
let shape = [
cache.batch_size(),
cache.num_heads(),
t_add,
cache.head_dim(),
];
(0..cache.num_layers())
.map(|layer| {
let seed = 2 * layer as u64;
let k = seeded_tensor::<4>(seed, shape, Distribution::Default, device);
let v = seeded_tensor::<4>(seed + 1, shape, Distribution::Default, device);
cache.insert_kv(layer, k.clone(), v.clone());
(k, v)
})
.collect()
}
fn check_prefill(
source_seq_len: usize,
filled: usize,
) {
for from in STORAGES {
for to in STORAGES {
check_prefill_between(source_seq_len, filled, from, to);
}
}
}
fn check_prefill_between(
source_seq_len: usize,
filled: usize,
from: KVCacheStorage,
to: KVCacheStorage,
) {
let device = performance_device();
let _memory = DeviceMemoryGuard::new(&device);
let [num_heads, head_dim, num_layers] = [2, 4, 2];
let mut source: KVCache =
KVCacheConfig::new(1, num_heads, source_seq_len, head_dim, num_layers)
.with_storage(from)
.init();
let steps = fill(&mut source, filled, &device);
assert_eq!(source.pos(), filled);
let batch = 3;
let mut cache: KVCache =
KVCacheConfig::new(batch, num_heads, source_seq_len, head_dim, num_layers)
.with_storage(to)
.init();
cache.prefill(&source);
assert_eq!(cache.storage(), to, "{from:?} into {to:?}");
assert_eq!(cache.pos(), filled);
let step = [batch, num_heads, 1, head_dim];
let history = [batch, num_heads, filled, head_dim];
for (layer, (k, v)) in steps.into_iter().enumerate() {
let (k_all, v_all) = cache.insert_kv(
layer,
Tensor::zeros(step, &device),
Tensor::zeros(step, &device),
);
assert_eq!(k_all.dims(), [batch, num_heads, filled + 1, head_dim]);
k_all
.slice(s![.., .., ..filled])
.into_data()
.assert_eq(&k.expand(history).into_data(), true);
v_all
.slice(s![.., .., ..filled])
.into_data()
.assert_eq(&v.expand(history).into_data(), true);
}
}
#[test]
#[serial]
fn test_truncate() {
let device = performance_device();
let _memory = DeviceMemoryGuard::new(&device);
let [batch, num_heads, head_dim, num_layers] = [2, 2, 4, 2];
for storage in STORAGES {
let mut cache = KVCacheConfig::new(batch, num_heads, 4, head_dim, num_layers)
.with_chunk_size(2)
.with_storage(storage)
.init();
let first = fill(&mut cache, 6, &device);
cache.truncate(2);
assert_eq!(cache.pos(), 2, "{storage:?}");
let step = [batch, num_heads, 3, head_dim];
for (layer, (k, v)) in first.into_iter().enumerate() {
let k_new = Tensor::<4>::ones(step, &device) * (layer as f32 + 7.0);
let v_new = Tensor::<4>::ones(step, &device) * (layer as f32 + 9.0);
let (k_all, v_all) = cache.insert_kv(layer, k_new.clone(), v_new.clone());
let expected_k = Tensor::cat(vec![k.slice(s![.., .., ..2]), k_new], 2);
let expected_v = Tensor::cat(vec![v.slice(s![.., .., ..2]), v_new], 2);
k_all.into_data().assert_eq(&expected_k.into_data(), true);
v_all.into_data().assert_eq(&expected_v.into_data(), true);
}
assert_eq!(cache.pos(), 5, "{storage:?}");
}
}
#[test]
fn test_window_retention() {
let device = cpu_device();
let [batch, heads, head_dim] = [1, 1, 2];
for storage in STORAGES {
let mut cache = KVCacheConfig::new(batch, heads, 4, head_dim, 2)
.with_storage(storage)
.with_layer_windows(vec![Some(3), None])
.init();
let step = |cache: &mut KVCache, at: usize, n: usize| {
let x = |layer: usize| {
Tensor::<1, Int>::arange(at as i64..(at + n) as i64, &device)
.float()
.add_scalar(100.0 * layer as f32)
.reshape([1, 1, n, 1])
.repeat_dim(3, head_dim)
};
let out: Vec<Vec<f32>> = (0..2)
.map(|layer| {
let (k, _) = cache.insert_kv(layer, x(layer), x(layer));
k.slice(s![.., .., .., 0..1])
.into_data()
.convert::<f32>()
.try_into_vec::<f32>()
.unwrap()
})
.collect();
out
};
let out = step(&mut cache, 0, 4);
assert_eq!(out[0], [0.0, 1.0, 2.0, 3.0], "{storage:?}");
assert_eq!(cache.retained_from(), 2, "{storage:?}: keeps 2, 3");
let out = step(&mut cache, 4, 1);
assert_eq!(out[0], [2.0, 3.0, 4.0], "{storage:?}: the window");
assert_eq!(out[1], [100.0, 101.0, 102.0, 103.0, 104.0], "{storage:?}");
assert_eq!(cache.retained_from(), 3, "{storage:?}");
let out = step(&mut cache, 5, 2);
assert_eq!(out[0], [3.0, 4.0, 5.0, 6.0], "{storage:?}");
assert_eq!(cache.retained_from(), 5, "{storage:?}");
}
}
#[test]
fn test_window_truncate_reorder_prefill() {
let device = cpu_device();
let config = KVCacheConfig::new(2, 1, 4, 2, 1).with_layer_windows(vec![Some(3)]);
let mut cache = config.clone().init();
let rows = |values: [f32; 2], n: usize| {
Tensor::<1>::from_floats(values, &device)
.reshape([2, 1, 1, 1])
.repeat_dim(2, n)
.repeat_dim(3, 2)
};
cache.insert_kv(0, rows([1.0, 2.0], 5), rows([1.0, 2.0], 5));
assert_eq!((cache.pos(), cache.retained_from()), (5, 3));
assert!(cache.can_truncate(4) && cache.can_truncate(3) && cache.can_truncate(0));
assert!(!cache.can_truncate(2) && !cache.can_truncate(6));
cache.reorder(&[1, 1]);
let mut copy = config.clone().with_batch_size(2).init();
copy.prefill(&cache);
assert_eq!((copy.pos(), copy.retained_from()), (5, 3));
let (k, _) = copy.insert_kv(0, rows([7.0, 7.0], 1), rows([7.0, 7.0], 1));
let firsts: Vec<f32> = k
.slice(s![.., .., .., 0..1])
.into_data()
.convert::<f32>()
.try_into_vec::<f32>()
.unwrap();
assert_eq!(firsts, [2.0, 2.0, 7.0, 2.0, 2.0, 7.0], "row 1 in both");
cache.truncate(4);
assert_eq!(cache.pos(), 4);
cache.truncate(0);
assert_eq!((cache.pos(), cache.retained_from()), (0, 0));
}
#[test]
#[should_panic(expected = "a sliding window keeps positions from 3")]
fn test_window_truncate_past_the_window_panics() {
let device = cpu_device();
let mut cache = KVCacheConfig::new(1, 1, 4, 2, 1)
.with_layer_windows(vec![Some(3)])
.init();
let x = Tensor::<4>::zeros([1, 1, 5, 2], &device);
cache.insert_kv(0, x.clone(), x);
cache.truncate(2);
}
#[test]
#[should_panic(expected = "cannot truncate")]
fn test_truncate_past_the_position_panics() {
let mut cache = KVCacheConfig::new(1, 1, 4, 2, 1).init();
cache.truncate(1);
}
#[test]
#[serial]
fn test_prefill_from_partly_filled_cache() {
check_prefill(8, 3);
}
#[test]
#[serial]
fn test_prefill_from_grown_cache() {
check_prefill(4, 6);
}
#[test]
#[serial]
fn test_prefill_from_full_cache() {
check_prefill(5, 5);
}
#[test]
fn test_for_decode() {
let config = KVCacheConfig::for_decode(2, 16, 4, 3);
let full = KVCacheConfig::new(1, 2, 16, 4, 3);
assert_eq!(
(
config.batch_size,
config.num_heads,
config.seq_len,
config.head_dim,
config.num_layers
),
(
full.batch_size,
full.num_heads,
full.seq_len,
full.head_dim,
full.num_layers
)
);
}
#[test]
fn test_config_sizing() {
let config = KVCacheConfig::new(1, 2, 16, 4, 3);
assert_eq!(config.chunk_size(), 1024);
assert_eq!(config.max_seq_len(), None);
let config = config
.with_batch_size(5)
.with_seq_len(32)
.with_chunk_size(8)
.with_max_seq_len(Some(40));
let cache = config.init();
assert_eq!(cache.batch_size(), 5);
assert_eq!(cache.seq_len(), 32);
assert_eq!(cache.chunk_size(), 8);
assert_eq!(cache.max_seq_len(), Some(40));
assert_eq!(cache.allocation_size(33), 40);
assert_eq!(cache.allocation_size(17), 32);
let uncapped = KVCacheConfig::new(1, 2, 16, 4, 3).with_chunk_size(8).init();
assert_eq!(uncapped.allocation_size(33), 48);
}
#[test]
#[should_panic(expected = "exceeds its max_seq_len")]
fn test_config_rejects_a_pre_size_past_its_cap() {
KVCacheConfig::new(1, 2, 16, 4, 3)
.with_max_seq_len(Some(8))
.init();
}
#[test]
#[serial]
fn test_growth_stops_at_the_cap() {
let device = performance_device();
let _memory = DeviceMemoryGuard::new(&device);
for storage in STORAGES {
let mut cache = KVCacheConfig::new(1, 2, 2, 4, 2)
.with_chunk_size(4)
.with_max_seq_len(Some(6))
.with_storage(storage)
.init();
fill(&mut cache, 4, &device);
fill(&mut cache, 2, &device);
assert_eq!(cache.pos(), 6);
assert_eq!(cache.held_len(), Some(6), "{storage:?}");
}
}
#[test]
#[serial]
#[should_panic(expected = "past its max_seq_len")]
fn test_a_step_past_the_cap_panics() {
let device = performance_device();
let mut cache = KVCacheConfig::new(1, 2, 2, 4, 2)
.with_max_seq_len(Some(4))
.init();
fill(&mut cache, 3, &device);
fill(&mut cache, 2, &device);
}
#[test]
fn test_a_model_hands_out_its_cache() {
struct Model;
impl KVCacheModel for Model {
fn kv_cache_config(&self) -> KVCacheConfig {
KVCacheConfig::new(1, 2, 16, 4, 3).with_max_seq_len(Some(64))
}
}
let cache = Model.new_kv_cache(7);
assert_eq!(cache.batch_size(), 7);
assert_eq!(cache.num_layers(), 3);
assert_eq!(cache.seq_len(), 16);
assert_eq!(cache.max_seq_len(), Some(64));
assert_eq!(cache.storage(), KVCacheStorage::Auto);
}
#[test]
#[serial]
fn test_the_storages_agree() {
let device = performance_device();
let _memory = DeviceMemoryGuard::new(&device);
let [batch, heads, head_dim, layers] = [2, 3, 4, 2];
let step = |seed: u64, t: usize| {
seeded_tensor::<4>(
seed,
[batch, heads, t, head_dim],
Distribution::Default,
&device,
)
};
let script = [(3, false), (1, false), (4, false), (2, true), (1, false)];
let run = |storage: KVCacheStorage| {
let mut cache = KVCacheConfig::new(batch, heads, 4, head_dim, layers)
.with_chunk_size(2)
.with_storage(storage)
.init();
let mut histories = Vec::new();
for (i, &(t, reset)) in script.iter().enumerate() {
if reset {
cache.reset();
}
for layer in 0..layers {
let seed = 10 * i as u64 + 2 * layer as u64;
let (k, v) = cache.insert_kv(layer, step(seed, t), step(seed + 1, t));
histories.push((k.into_data(), v.into_data()));
}
}
assert_eq!(cache.storage(), storage);
histories
};
let want = run(KVCacheStorage::MultiLayer);
for storage in [KVCacheStorage::Concat, KVCacheStorage::PerLayer] {
for ((k, v), (want_k, want_v)) in run(storage).iter().zip(&want) {
k.assert_eq(want_k, true);
v.assert_eq(want_v, true);
}
}
}
#[test]
#[serial]
fn test_cross_kv_is_set_once_and_kept() {
let device = performance_device();
let _memory = DeviceMemoryGuard::new(&device);
let [heads, head_dim, layers, cross_len] = [2, 4, 2, 5];
for storage in STORAGES {
let mut cache = KVCacheConfig::new(6, heads, 4, head_dim, layers)
.with_storage(storage)
.init();
assert_eq!(cache.group(), 1);
assert!(cache.cross_kv(0).is_none());
assert_eq!(cache.dtype(), None);
let cross: Vec<(Tensor<4>, Tensor<4>)> = (0..layers)
.map(|layer| {
let seed = 100 + 2 * layer as u64;
let shape = [2, heads, cross_len, head_dim];
(
seeded_tensor::<4>(seed, shape, Distribution::Default, &device),
seeded_tensor::<4>(seed + 1, shape, Distribution::Default, &device),
)
})
.collect();
for (layer, (k, v)) in cross.iter().enumerate() {
cache.set_cross_kv(layer, k.clone(), v.clone());
}
assert_eq!(cache.group(), 3, "6 decode rows over 2 encoder rows");
assert!(cache.dtype().is_some());
fill(&mut cache, 2, &device);
cache.reorder(&[5, 4, 3, 2, 1, 0]);
cache.reset();
for (layer, (k, v)) in cross.iter().enumerate() {
let (got_k, got_v) = cache.cross_kv(layer).expect("set");
got_k.into_data().assert_eq(&k.clone().into_data(), true);
got_v.into_data().assert_eq(&v.clone().into_data(), true);
}
}
}
#[test]
#[should_panic(expected = "not a whole multiple")]
fn test_cross_kv_rows_must_divide_the_batch() {
let device = cpu_device();
let mut cache = KVCacheConfig::new(5, 2, 4, 4, 1).init();
cache.set_cross_kv(
0,
Tensor::zeros([2, 2, 3, 4], &device),
Tensor::zeros([2, 2, 3, 4], &device),
);
}
#[test]
#[should_panic(expected = "shares one group")]
fn test_cross_kv_layers_share_a_group() {
let device = cpu_device();
let mut cache = KVCacheConfig::new(4, 2, 4, 4, 2).init();
cache.set_cross_kv(
0,
Tensor::zeros([2, 2, 3, 4], &device),
Tensor::zeros([2, 2, 3, 4], &device),
);
cache.set_cross_kv(
1,
Tensor::zeros([1, 2, 3, 4], &device),
Tensor::zeros([1, 2, 3, 4], &device),
);
}
#[test]
#[serial]
fn test_reorder_picks_history_rows() {
let device = performance_device();
let _memory = DeviceMemoryGuard::new(&device);
let [batch, heads, head_dim, layers] = [3, 2, 4, 2];
let sources = [2, 0, 2];
let indices = Tensor::<1, Int>::from_data([2i64, 0, 2], &device);
for storage in STORAGES {
let mut cache = KVCacheConfig::new(batch, heads, 2, head_dim, layers)
.with_chunk_size(2)
.with_storage(storage)
.init();
let before: Vec<(Tensor<4>, Tensor<4>)> = (0..layers)
.map(|layer| {
let shape = [batch, heads, 3, head_dim];
let seed = 2 * layer as u64;
let k = seeded_tensor::<4>(seed, shape, Distribution::Default, &device);
let v = seeded_tensor::<4>(seed + 1, shape, Distribution::Default, &device);
cache.insert_kv(layer, k.clone(), v.clone());
(k, v)
})
.collect();
cache.reorder(&sources);
assert_eq!(cache.pos(), 3);
for (layer, (k, v)) in before.into_iter().enumerate() {
let step = [batch, heads, 1, head_dim];
let (k_all, v_all) = cache.insert_kv(
layer,
Tensor::zeros(step, &device),
Tensor::zeros(step, &device),
);
assert_eq!(k_all.dims(), [batch, heads, 4, head_dim], "{storage:?}");
k_all
.slice(s![.., .., ..3])
.into_data()
.assert_eq(&k.select(0, indices.clone()).into_data(), true);
v_all
.slice(s![.., .., ..3])
.into_data()
.assert_eq(&v.select(0, indices.clone()).into_data(), true);
}
}
}
#[test]
#[should_panic(expected = "one source row per batch row")]
fn test_reorder_takes_one_source_per_row() {
let mut cache = KVCacheConfig::new(3, 2, 4, 4, 1).init();
cache.reorder(&[0, 1]);
}
#[test]
fn test_backend_stack_parses_backend_names() {
let parse = BackendStack::parse;
let stack = |fused, runtime| BackendStack { fused, runtime };
assert_eq!(parse("dispatch<flex>"), stack(false, Runtime::Other));
assert_eq!(
parse("dispatch<cubecl<wgpu<spirv>>>"),
stack(false, Runtime::Wgpu)
);
assert_eq!(
parse("dispatch<fusion<cubecl<wgpu<spirv>>>>"),
stack(true, Runtime::Wgpu)
);
assert_eq!(parse("dispatch<cubecl<cuda>>"), stack(false, Runtime::Cuda));
assert_eq!(
parse("dispatch<cubecl<wgpu<msl>>>"),
stack(false, Runtime::Wgpu)
);
assert_eq!(
parse("dispatch<fusion<cubecl<wgpu<msl>>>>"),
stack(true, Runtime::Wgpu)
);
assert_eq!(
parse("dispatch<fusion<cubecl<cuda>>>"),
stack(true, Runtime::Cuda)
);
assert_eq!(
parse("dispatch<autodiff<fusion<cubecl<wgpu<spirv>>>>>"),
stack(true, Runtime::Wgpu)
);
}
#[test]
#[serial]
fn test_backend_stack_reads_the_device() {
use burn_backend::Backend;
let device = performance_device();
let name = burn_dispatch::Dispatch::name(device.as_dispatch());
let stack = BackendStack::of(&device);
println!(
"backend {name}: {stack:?}, Auto is {:?}",
KVCacheStorage::auto_for(&device)
);
assert_eq!(stack.fused, name.contains("fusion<"), "{name}");
if name.contains("cubecl<") {
assert!(
name.contains("cubecl<wgpu")
|| name.contains("cubecl<cuda")
|| stack.runtime == Runtime::Other,
"{name}"
);
}
}
#[test]
fn test_auto_resolves_on_the_first_write() {
let device = cpu_device();
assert_eq!(KVCacheStorage::auto_for(&device), KVCacheStorage::PerLayer);
assert_eq!(
KVCacheStorage::Concat.resolve(&device),
KVCacheStorage::Concat
);
let mut cache = KVCacheConfig::new(1, 2, 4, 4, 1).init();
assert_eq!(cache.storage(), KVCacheStorage::Auto);
cache.insert_kv(
0,
Tensor::zeros([1, 2, 1, 4], &device),
Tensor::zeros([1, 2, 1, 4], &device),
);
assert_eq!(cache.storage(), KVCacheStorage::PerLayer);
}
}