Skip to main content

spec_stream_cache/
lib.rs

1//! # spec-stream-cache
2//!
3//! Paged KV-cache memory manager for Large Language Models.
4//! Implements virtual-to-physical block tables, prefix caching (prompt sharing),
5//! and O(1) rollbacks for speculative decoding branch pruning.
6
7pub mod allocator;
8pub mod block;
9pub mod error;
10pub mod eviction;
11pub mod manager;
12pub mod snapshot;
13pub mod table;
14
15pub use allocator::BlockAllocator;
16pub use block::{PhysicalBlock, PhysicalBlockId, DEFAULT_BLOCK_SIZE};
17pub use error::CacheError;
18pub use eviction::{EvictionPolicy, LruEvictionPolicy};
19pub use manager::PagedKvCacheManager;
20pub use snapshot::{PrefixCacheSnapshot, PrefixSnapshotEntry};
21pub use table::BlockTable;
22
23#[cfg(test)]
24mod tests {
25    use super::*;
26
27    #[test]
28    fn test_paged_allocation_and_rollback() {
29        let block_size = 4;
30        let mut allocator = BlockAllocator::new(10, block_size);
31        let mut table = BlockTable::new(block_size);
32
33        assert_eq!(allocator.num_free_blocks(), 10);
34
35        // Append 7 tokens -> should occupy 2 physical blocks (ceil(7/4) = 2)
36        let tokens: Vec<u32> = (1..=7).collect();
37        table.append_tokens(&tokens, &mut allocator).unwrap();
38
39        assert_eq!(table.seq_len, 7);
40        assert_eq!(table.physical_blocks.len(), 2);
41        assert_eq!(allocator.num_free_blocks(), 8);
42
43        // Speculative decoding rejected the last 4 tokens -> roll back to valid count = 3
44        // 3 tokens fit inside 1 physical block (ceil(3/4) = 1)
45        // The second physical block must be immediately returned to the free list!
46        let discarded = table.rollback(3, &mut allocator).unwrap();
47        assert_eq!(discarded, 4);
48        assert_eq!(table.seq_len, 3);
49        assert_eq!(table.physical_blocks.len(), 1);
50        assert_eq!(allocator.num_free_blocks(), 9); // Block was properly recycled!
51
52        // Free remaining sequence
53        table.free_all(&mut allocator).unwrap();
54        assert_eq!(allocator.num_free_blocks(), 10);
55    }
56}