use crate::{
blocks::transformers::decoders::stack::DecoderStackCache,
ops::transformers::attention::KVCache,
};
pub trait RewindableCache {
fn pos(&self) -> usize;
fn rewind_point(
&self,
pos: usize,
) -> usize;
fn truncate(
&mut self,
pos: usize,
);
}
impl RewindableCache for KVCache {
fn pos(&self) -> usize {
KVCache::pos(self)
}
fn rewind_point(
&self,
pos: usize,
) -> usize {
if KVCache::can_truncate(self, pos) {
pos
} else {
0
}
}
fn truncate(
&mut self,
pos: usize,
) {
KVCache::truncate(self, pos);
}
}
impl RewindableCache for DecoderStackCache {
fn pos(&self) -> usize {
DecoderStackCache::pos(self)
}
fn rewind_point(
&self,
pos: usize,
) -> usize {
DecoderStackCache::rewind_point(self, pos)
}
fn truncate(
&mut self,
pos: usize,
) {
DecoderStackCache::truncate(self, pos);
}
}
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct CachedHistory {
tokens: Vec<i64>,
}
impl CachedHistory {
pub fn new() -> Self {
Self::default()
}
pub fn tokens(&self) -> &[i64] {
&self.tokens
}
pub fn extend(
&mut self,
tokens: &[i64],
) {
self.tokens.extend_from_slice(tokens);
}
pub fn rewind<'a>(
&mut self,
cache: &mut impl RewindableCache,
next: &'a [i64],
) -> &'a [i64] {
assert!(!next.is_empty(), "a prompt to prefill");
assert_eq!(
cache.pos(),
self.tokens.len(),
"the cache holds the history"
);
let shared = self
.tokens
.iter()
.zip(next)
.take_while(|(a, b)| a == b)
.count()
.min(next.len() - 1);
let shared = cache.rewind_point(shared);
cache.truncate(shared);
self.tokens.truncate(shared);
&next[shared..]
}
}
#[cfg(test)]
mod tests {
use burn::tensor::Tensor;
use super::*;
use crate::{
ops::transformers::attention::KVCacheConfig,
support::testing::cpu_device,
};
fn advance(
cache: &mut KVCache,
n: usize,
) {
let device = cpu_device();
let t = Tensor::<4>::zeros([1, 1, n, 2], &device);
cache.insert_kv(0, t.clone(), t);
}
#[test]
fn test_rewind_keeps_the_shared_prefix() {
let mut cache = KVCacheConfig::new(1, 1, 8, 2, 1).init();
let mut history = CachedHistory::new();
let first = [1, 2, 3, 4];
let todo = history.rewind(&mut cache, &first);
assert_eq!(todo, first, "nothing cached yet");
advance(&mut cache, todo.len());
history.extend(todo);
let next = [1, 2, 9, 9, 9];
let todo = history.rewind(&mut cache, &next);
assert_eq!(todo, [9, 9, 9]);
assert_eq!(cache.pos(), 2);
assert_eq!(history.tokens(), [1, 2]);
advance(&mut cache, todo.len());
history.extend(todo);
let todo = history.rewind(&mut cache, &next);
assert_eq!(todo, [9]);
assert_eq!(cache.pos(), 4);
}
fn hybrid_cache() -> DecoderStackCache {
use crate::{
blocks::transformers::embedding::{
RotaryEmbeddingConfig,
RotarySet,
},
burner::module::ModuleInit,
ops::transformers::linear_attention::{
DeltaNetCache,
DeltaNetStateConfig,
},
};
let device = cpu_device();
DecoderStackCache {
cache: KVCacheConfig::new(1, 1, 8, 2, 1).init(),
linear: DeltaNetCache::new(vec![
DeltaNetStateConfig::new(1, 3, 2, 1, 2, 2).init(&device),
]),
rotary: RotarySet::from(ModuleInit::init(&RotaryEmbeddingConfig::new(8, 2), &device)),
}
}
fn fill_linear(cache: &mut DecoderStackCache) {
let state = cache.linear.layer_mut(0);
state.recurrent = state.recurrent.ones_like();
}
fn linear_is_zero(cache: &mut DecoderStackCache) -> bool {
let state = cache.linear.layer_mut(0);
state.recurrent.clone().abs().max().into_scalar::<f32>() == 0.0
}
#[test]
fn test_rewind_a_hybrid_cache() {
let mut cache = hybrid_cache();
let mut history = CachedHistory::new();
let first = [1, 2, 3, 4];
let todo = history.rewind(&mut cache, &first);
advance(&mut cache.cache, todo.len());
fill_linear(&mut cache);
history.extend(todo);
let longer = [1, 2, 3, 4, 5, 6];
let todo = history.rewind(&mut cache, &longer);
assert_eq!(todo, [5, 6], "the history extended: nothing rewinds");
assert_eq!(cache.pos(), 4);
assert!(!linear_is_zero(&mut cache), "the states kept");
let parted = [1, 2, 9, 9];
assert!(!cache.can_truncate(2) && cache.can_truncate(4) && cache.can_truncate(0));
let todo = history.rewind(&mut cache, &parted);
assert_eq!(todo, parted, "the linear states cannot rewind to 2");
assert_eq!(cache.pos(), 0);
assert!(linear_is_zero(&mut cache), "the states reset");
assert!(history.tokens().is_empty());
}
#[test]
fn test_rewind_a_hybrid_cache_to_its_snapshot() {
let mut cache = hybrid_cache();
let mut history = CachedHistory::new();
advance(&mut cache.cache, 2);
fill_linear(&mut cache);
cache.snapshot();
history.extend(&[1, 2]);
advance(&mut cache.cache, 2);
cache.linear.layer_mut(0).reset();
history.extend(&[3, 4]);
let next = [1, 2, 3, 9];
let todo = history.rewind(&mut cache, &next);
assert_eq!(todo, [3, 9], "back to the snapshot at 2");
assert_eq!(cache.pos(), 2);
assert!(
!linear_is_zero(&mut cache),
"the snapshot's states restored"
);
assert_eq!(history.tokens(), [1, 2]);
}
#[test]
fn test_rewind_past_a_window_resets() {
let mut cache = KVCacheConfig::new(1, 1, 8, 2, 1)
.with_layer_windows(vec![Some(2)])
.init();
let mut history = CachedHistory::new();
let first = [1, 2, 3, 4];
let todo = history.rewind(&mut cache, &first);
advance(&mut cache, todo.len());
history.extend(todo);
assert_eq!(cache.retained_from(), 3);
let next = [1, 2, 9, 9];
let todo = history.rewind(&mut cache, &next);
assert_eq!(todo, next, "position 2 is gone");
assert_eq!(cache.pos(), 0);
assert!(history.tokens().is_empty());
}
}