Skip to main content

tpt_gpu_runtime/
kv_cache.rs

1//! Sliding-window KV cache for autoregressive decoding.
2//!
3//! Stores K and V tensors for every transformer layer on the host. When the
4//! sequence length reaches `context_len`, the oldest token's K/V vectors are
5//! dropped (shift-left) so decoding can continue indefinitely.
6
7/// Host-side KV cache with one K and one V buffer per transformer layer.
8///
9/// Layout per layer: contiguous `f32` slice of length
10/// `context_len × num_kv_heads × head_dim`.
11/// Valid data occupies `[0, seq_len × row_size)`.
12#[derive(Debug)]
13pub struct KvCache {
14    keys: Vec<Vec<f32>>,
15    values: Vec<Vec<f32>>,
16    pub seq_len: usize,
17    context_len: usize,
18    num_kv_heads: usize,
19    head_dim: usize,
20}
21
22impl KvCache {
23    /// Allocate a zeroed cache for `num_layers` layers.
24    pub fn new(num_layers: u32, context_len: u32, num_kv_heads: u32, head_dim: u32) -> Self {
25        let nl = num_layers as usize;
26        let cl = context_len as usize;
27        let h = num_kv_heads.max(1) as usize;
28        let d = head_dim.max(1) as usize;
29        let cap = cl * h * d;
30        Self {
31            keys: vec![vec![0.0f32; cap]; nl],
32            values: vec![vec![0.0f32; cap]; nl],
33            seq_len: 0,
34            context_len: cl,
35            num_kv_heads: h,
36            head_dim: d,
37        }
38    }
39
40    /// Append one token's K and V vectors for a given layer.
41    ///
42    /// When the cache is full, the oldest token is evicted (ring-buffer
43    /// shift) before the new vectors are written.
44    pub fn append(&mut self, layer: usize, k_row: &[f32], v_row: &[f32]) {
45        let row_size = self.num_kv_heads * self.head_dim;
46
47        if self.seq_len == self.context_len {
48            // Evict the oldest token: shift all rows left by one.
49            let keys = &mut self.keys[layer];
50            keys.copy_within(row_size.., 0);
51            let values = &mut self.values[layer];
52            values.copy_within(row_size.., 0);
53            // Only decrement once — seq_len is shared across layers, so
54            // only the first layer's append should update it.
55            if layer == 0 {
56                self.seq_len -= 1;
57            }
58        }
59
60        let pos = self.seq_len * row_size;
61        let copy_len = k_row
62            .len()
63            .min(row_size)
64            .min(self.keys[layer].len().saturating_sub(pos));
65        if copy_len > 0 {
66            self.keys[layer][pos..pos + copy_len].copy_from_slice(&k_row[..copy_len]);
67            self.values[layer][pos..pos + copy_len].copy_from_slice(&v_row[..copy_len]);
68        }
69
70        // Advance seq_len only after the last layer has appended.
71        if layer + 1 == self.keys.len() {
72            self.seq_len += 1;
73        }
74    }
75
76    /// Return the valid slice of K vectors for `layer` as `[seq_len, row_size]` data.
77    pub fn get_k(&self, layer: usize) -> &[f32] {
78        let row_size = self.num_kv_heads * self.head_dim;
79        &self.keys[layer][..self.seq_len * row_size]
80    }
81
82    /// Return the valid slice of V vectors for `layer` as `[seq_len, row_size]` data.
83    pub fn get_v(&self, layer: usize) -> &[f32] {
84        let row_size = self.num_kv_heads * self.head_dim;
85        &self.values[layer][..self.seq_len * row_size]
86    }
87
88    /// Return the K slice for `layer` at an explicit token count.
89    ///
90    /// Use this after `append` to include the just-written token whose position
91    /// has been filled but `seq_len` has not yet been incremented (because
92    /// `seq_len` only advances after the final layer has appended).
93    pub fn get_k_at(&self, layer: usize, count: usize) -> &[f32] {
94        let row_size = self.num_kv_heads * self.head_dim;
95        let end = (count * row_size).min(self.keys[layer].len());
96        &self.keys[layer][..end]
97    }
98
99    /// Return the V slice for `layer` at an explicit token count.
100    pub fn get_v_at(&self, layer: usize, count: usize) -> &[f32] {
101        let row_size = self.num_kv_heads * self.head_dim;
102        let end = (count * row_size).min(self.values[layer].len());
103        &self.values[layer][..end]
104    }
105
106    /// Zero out all K/V data and reset the sequence counter.
107    pub fn reset(&mut self) {
108        self.seq_len = 0;
109        for (k, v) in self.keys.iter_mut().zip(self.values.iter_mut()) {
110            k.fill(0.0);
111            v.fill(0.0);
112        }
113    }
114
115    /// Total number of layers.
116    pub fn num_layers(&self) -> usize {
117        self.keys.len()
118    }
119
120    /// Maximum sequence length before eviction occurs.
121    pub fn context_len(&self) -> usize {
122        self.context_len
123    }
124}
125
126// ---------------------------------------------------------------------------
127// Tests
128// ---------------------------------------------------------------------------
129
130#[cfg(test)]
131mod tests {
132    use super::*;
133
134    fn make_row(val: f32, size: usize) -> Vec<f32> {
135        vec![val; size]
136    }
137
138    #[test]
139    fn append_and_retrieve_single_layer() {
140        let mut cache = KvCache::new(1, 4, 1, 8);
141        let row_size = 8; // 1 head × 8 head_dim
142
143        let k0 = make_row(1.0, row_size);
144        let v0 = make_row(2.0, row_size);
145        cache.append(0, &k0, &v0);
146
147        assert_eq!(cache.seq_len, 1);
148        assert!(cache.get_k(0).iter().all(|&x| x == 1.0));
149        assert!(cache.get_v(0).iter().all(|&x| x == 2.0));
150    }
151
152    #[test]
153    fn seq_len_advances_after_all_layers() {
154        let mut cache = KvCache::new(3, 8, 2, 4);
155        let row_size = 8; // 2 × 4
156        let k = make_row(0.5, row_size);
157        let v = make_row(0.5, row_size);
158        // Append for layers 0, 1, 2 → seq_len should advance to 1.
159        cache.append(0, &k, &v);
160        cache.append(1, &k, &v);
161        cache.append(2, &k, &v);
162        assert_eq!(cache.seq_len, 1);
163    }
164
165    #[test]
166    fn eviction_at_context_len() {
167        // context_len = 2, 1 layer
168        let mut cache = KvCache::new(1, 2, 1, 4);
169        let row = 4usize;
170
171        // token 0: K = 1.0
172        cache.append(0, &make_row(1.0, row), &make_row(10.0, row));
173        assert_eq!(cache.seq_len, 1);
174
175        // token 1: K = 2.0
176        cache.append(0, &make_row(2.0, row), &make_row(20.0, row));
177        assert_eq!(cache.seq_len, 2);
178
179        // token 2: K = 3.0 — should evict token 0
180        cache.append(0, &make_row(3.0, row), &make_row(30.0, row));
181        assert_eq!(cache.seq_len, 2);
182
183        // After eviction: get_k should be [2.0×row, 3.0×row]
184        let k = cache.get_k(0);
185        assert!(
186            k[..row].iter().all(|&x| (x - 2.0).abs() < 1e-6),
187            "first row should be 2.0 after eviction"
188        );
189        assert!(
190            k[row..].iter().all(|&x| (x - 3.0).abs() < 1e-6),
191            "second row should be 3.0"
192        );
193    }
194
195    #[test]
196    fn reset_clears_all_data() {
197        let mut cache = KvCache::new(2, 4, 1, 4);
198        let row = 4usize;
199        cache.append(0, &make_row(5.0, row), &make_row(5.0, row));
200        cache.append(1, &make_row(5.0, row), &make_row(5.0, row));
201        cache.reset();
202        assert_eq!(cache.seq_len, 0);
203        assert!(cache.get_k(0).is_empty());
204    }
205
206    #[test]
207    fn context_len_accessor() {
208        let cache = KvCache::new(4, 2048, 8, 128);
209        assert_eq!(cache.context_len(), 2048);
210        assert_eq!(cache.num_layers(), 4);
211    }
212}