Skip to main content

hyprstream_inference/runtime/
kv_cache.rs

1//! Key-Value cache implementation for efficient autoregressive generation
2//!
3//! This module implements KV caching to avoid recomputing past key and value
4//! states during inference, providing 10-50x speedup for long sequences.
5//!
6//! ## Memory Optimization
7//!
8//! The cache uses a chunked growth strategy instead of pre-allocating the full
9//! max_seq_len. This saves ~4GB+ VRAM for models with large context windows.
10//!
11//! ## Quantization Support
12//!
13//! Supports optional quantization via bitsandbytes:
14//! - `None`: Full precision (FP16/BF16) - default
15//! - `Int8`: 8-bit quantization
16//! - `Nf4`: 4-bit NormalFloat (best quality for 4-bit)
17//! - `Fp4`: 4-bit FloatingPoint
18//!
19//! Quantization uses a hybrid approach:
20//! - Historical tokens are stored quantized (memory savings)
21//! - Recent tokens stay in a full-precision buffer (fast updates)
22//! - Dequantized view is cached across layers (avoids repeated dequantization)
23
24use anyhow::{anyhow, Result};
25use dashmap::DashMap;
26use parking_lot::Mutex;
27use std::sync::atomic::{AtomicU64, Ordering};
28use std::sync::Arc;
29use std::time::{SystemTime, UNIX_EPOCH};
30#[cfg(any(feature = "bnb", test))]
31use tch::Device;
32use tch::{Kind as DType, Tensor};
33
34use super::kv_compat::{decide_cache_reuse, CacheReuseDecision, KvCompatFingerprint};
35use super::torch_utils::{estimate_tensor_size_mb, safe_zeros};
36use hyprstream_rpc_std::model_client::KVQuantType;
37
38// ============================================================================
39// Cache Owner and Registry Types (for multi-session support)
40// ============================================================================
41
42/// Identifies the owner of a KV cache instance for session isolation.
43///
44/// Each owner gets their own isolated cache, enabling concurrent inference
45/// without interference between different conversations/sessions.
46#[derive(Clone, Hash, Eq, PartialEq, Debug)]
47pub enum CacheOwner {
48    /// Session-based inference - multiple requests share cache for context continuity.
49    /// Use this for conversational AI where context should persist across requests.
50    Session(String),
51
52    /// Stateless inference - one-off completions where cache is discarded after use.
53    /// Use this for standard OpenAI-compatible API requests without session tracking.
54    Stateless(u64),
55
56    /// Training validation inference - for evaluating model during training.
57    Training { adapter: String, run_id: u64 },
58}
59
60impl CacheOwner {
61    /// Create a new stateless owner with a random ID
62    pub fn new_stateless() -> Self {
63        let id = SystemTime::now()
64            .duration_since(UNIX_EPOCH)
65            .map(|d| d.as_nanos() as u64)
66            .unwrap_or(0);
67        CacheOwner::Stateless(id)
68    }
69
70    /// Create a session owner
71    pub fn session(session_id: impl Into<String>) -> Self {
72        CacheOwner::Session(session_id.into())
73    }
74
75    /// Create a training owner
76    pub fn training(adapter: impl Into<String>, run_id: u64) -> Self {
77        CacheOwner::Training {
78            adapter: adapter.into(),
79            run_id,
80        }
81    }
82}
83
84/// Configuration for KV cache instances
85#[derive(Clone, Debug)]
86pub struct CacheConfig {
87    /// Number of transformer layers
88    pub num_layers: usize,
89    /// Maximum sequence length (context window)
90    pub max_seq_len: usize,
91    /// Quantization type for memory efficiency
92    pub quant_type: KVQuantType,
93    /// Use paged block storage (PagedAttention-style) instead of contiguous tensors.
94    /// Requires a BlockPool to be initialized on the registry.
95    pub paged: bool,
96}
97
98impl CacheConfig {
99    /// Create a new cache configuration
100    pub fn new(num_layers: usize, max_seq_len: usize) -> Self {
101        Self {
102            num_layers,
103            max_seq_len,
104            quant_type: KVQuantType::None,
105            paged: false,
106        }
107    }
108
109    /// Set quantization type
110    pub fn with_quant_type(mut self, quant_type: KVQuantType) -> Self {
111        self.quant_type = quant_type;
112        self
113    }
114
115    /// Enable paged block storage (requires BlockPool on the registry)
116    pub fn with_paged(mut self, paged: bool) -> Self {
117        self.paged = paged;
118        self
119    }
120}
121
122/// Registry managing multiple KV cache instances for concurrent sessions.
123///
124/// Each `CacheOwner` gets their own isolated `KVCacheManager` wrapped in a Mutex.
125/// The registry uses DashMap for lock-free access to different sessions, while
126/// each individual cache uses Mutex for thread-safe layer access (required because
127/// tch-rs Tensor contains raw pointers that aren't `Sync`).
128///
129/// # Concurrency Model
130///
131/// ```text
132/// Request A ──► Registry.get_or_create(Session("abc")) ──► Cache A (Mutex)
133/// Request B ──► Registry.get_or_create(Session("xyz")) ──► Cache B (Mutex)
134///                                                          ↑
135///                                                No contention between A and B!
136/// ```
137pub struct KVCacheRegistry {
138    /// Active caches indexed by owner (lock-free access to different owners)
139    caches: DashMap<CacheOwner, Arc<Mutex<KVCacheManager>>>,
140    /// Default configuration for new caches
141    default_config: CacheConfig,
142    /// Memory budget in bytes (None = unlimited)
143    memory_budget_bytes: Option<usize>,
144    /// Maps cache owners to the subject delta that was active when the cache was computed.
145    /// The value is `(tenant_id, weight_epoch)`: the tenant whose delta contributed to
146    /// the KV, plus the delta's weight epoch at compute time. When a delta is evicted
147    /// or reset, dependent caches must be invalidated; when the epoch has advanced
148    /// (in-place re-adaptation under the same tenant), the cached KV is weight-stale.
149    delta_dependencies: DashMap<CacheOwner, Option<(String, u64)>>,
150    /// Shared block pool for paged KV cache storage (None if paged mode not enabled)
151    block_pool: Option<Arc<Mutex<BlockPool>>>,
152}
153
154impl KVCacheRegistry {
155    /// Create a new KV cache registry
156    pub fn new(default_config: CacheConfig, memory_budget: Option<usize>) -> Self {
157        tracing::info!(
158            "[KVCacheRegistry::new] Creating registry with {} layers, max_seq_len={}, quant={:?}, budget={:?}, paged={}",
159            default_config.num_layers,
160            default_config.max_seq_len,
161            default_config.quant_type,
162            memory_budget,
163            default_config.paged
164        );
165
166        Self {
167            caches: DashMap::new(),
168            default_config,
169            memory_budget_bytes: memory_budget,
170            delta_dependencies: DashMap::new(),
171            block_pool: None,
172        }
173    }
174
175    /// Initialize the shared block pool for paged KV cache storage.
176    ///
177    /// Must be called before any paged caches are created. `num_blocks` determines
178    /// the total KV cache capacity across all sessions. `num_kv_heads` and `head_dim`
179    /// must match the model's attention configuration.
180    pub fn init_block_pool(
181        &mut self,
182        num_blocks: usize,
183        num_kv_heads: usize,
184        head_dim: usize,
185        device: tch::Device,
186        dtype: DType,
187    ) -> Result<()> {
188        let pool = BlockPool::new(num_blocks, num_kv_heads, head_dim, device, dtype)?;
189        self.block_pool = Some(Arc::new(Mutex::new(pool)));
190        Ok(())
191    }
192
193    /// Get the shared block pool (for metrics/debugging).
194    pub fn block_pool(&self) -> Option<&Arc<Mutex<BlockPool>>> {
195        self.block_pool.as_ref()
196    }
197
198    /// Get or create a cache for the given owner.
199    ///
200    /// If the cache doesn't exist, creates a new one with the default config.
201    /// Returns `Arc<Mutex<KVCacheManager>>` - caller must lock() to use.
202    pub fn get_or_create(&self, owner: CacheOwner) -> Arc<Mutex<KVCacheManager>> {
203        // Try to get existing cache first (fast path)
204        if let Some(cache) = self.caches.get(&owner) {
205            let mut guard = cache.lock();
206            guard.touch();
207
208            // Transparently restore CPU-offloaded caches back to GPU
209            if guard.location() == CacheLocation::Cpu {
210                // Determine the GPU device from the engine config
211                let device = tch::Device::cuda_if_available();
212                guard.restore_to_gpu(device);
213            }
214
215            drop(guard);
216            return cache.clone();
217        }
218
219        // Slow path: create new cache (paged or contiguous based on config)
220        let cache = if self.default_config.paged {
221            if let Some(pool) = &self.block_pool {
222                Arc::new(Mutex::new(KVCacheManager::new_paged(
223                    self.default_config.num_layers,
224                    self.default_config.max_seq_len,
225                    pool.clone(),
226                    owner.clone(),
227                )))
228            } else {
229                tracing::warn!("Paged mode requested but block pool not initialized, falling back to contiguous");
230                Arc::new(Mutex::new(KVCacheManager::new(
231                    self.default_config.num_layers,
232                    self.default_config.max_seq_len,
233                    self.default_config.quant_type,
234                )))
235            }
236        } else {
237            Arc::new(Mutex::new(KVCacheManager::new(
238                self.default_config.num_layers,
239                self.default_config.max_seq_len,
240                self.default_config.quant_type,
241            )))
242        };
243
244        // Insert and return (handles race condition - returns existing if another thread inserted)
245        self.caches.entry(owner).or_insert(cache.clone()).clone()
246    }
247
248    /// Release a cache when the session is done.
249    ///
250    /// For `Stateless` owners, this removes the cache immediately.
251    /// For `Session` owners, the cache is kept for potential reuse.
252    pub fn release(&self, owner: &CacheOwner) {
253        match owner {
254            CacheOwner::Stateless(_) => {
255                // Stateless caches (and their delta dependency) are removed immediately.
256                self.caches.remove(owner);
257                self.delta_dependencies.remove(owner);
258                tracing::debug!("Released stateless cache: {:?}", owner);
259            }
260            CacheOwner::Session(_) | CacheOwner::Training { .. } => {
261                // Session and training caches are kept for reuse; their delta
262                // dependency is retained so a later tenant-delta eviction can
263                // still invalidate them. They fall to LRU eviction under memory pressure.
264                tracing::debug!("Marked session cache for potential reuse: {:?}", owner);
265            }
266        }
267    }
268
269    /// Evict least-recently-used caches to stay within memory budget.
270    pub fn evict_to_budget(&self) {
271        let budget = match self.memory_budget_bytes {
272            Some(b) => b,
273            None => return, // No budget = no eviction
274        };
275
276        let current_usage = self.total_memory_usage();
277        if current_usage <= budget {
278            return;
279        }
280
281        // Collect eviction candidates. `CacheOwner::Training` caches are exempt
282        // from eviction by rule — they hold validation/eval state for an active
283        // training run and must survive memory pressure (the run owns their
284        // lifecycle). All other owners (Stateless/Session) are evictable.
285        let mut candidates: Vec<(CacheOwner, u64, usize)> = self
286            .caches
287            .iter()
288            .filter_map(|entry| {
289                let owner = entry.key().clone();
290
291                // Skip training caches (exempt by rule — see comment above).
292                if matches!(owner, CacheOwner::Training { .. }) {
293                    return None;
294                }
295
296                let guard = entry.value().lock();
297                let last_access = guard.last_access();
298                let memory = guard.memory_usage();
299                Some((owner, last_access, memory))
300            })
301            .collect();
302
303        // Sort by last access (oldest first)
304        candidates.sort_by_key(|(_, last_access, _)| *last_access);
305
306        // Two-tier eviction: first offload to CPU, then remove if still over budget.
307        let mut freed = 0;
308
309        // Tier 1: Offload GPU caches to CPU (frees GPU memory, preserves data)
310        for (owner, _, size) in &candidates {
311            if current_usage - freed <= budget {
312                break;
313            }
314            if let Some(cache) = self.caches.get(owner) {
315                let mut guard = cache.lock();
316                if guard.location() == CacheLocation::Gpu {
317                    guard.offload_to_cpu();
318                    freed += size;
319                    tracing::info!(
320                        "Offloaded cache {:?} to CPU, freed {} GPU bytes",
321                        owner,
322                        size
323                    );
324                }
325            }
326        }
327
328        // Tier 2: If still over budget, remove offloaded caches entirely
329        if current_usage - freed > budget {
330            for (owner, _, size) in candidates {
331                if current_usage - freed <= budget {
332                    break;
333                }
334                if let Some(cache) = self.caches.get(&owner) {
335                    let guard = cache.lock();
336                    if guard.location() == CacheLocation::Cpu {
337                        drop(guard);
338                        self.caches.remove(&owner);
339                        self.delta_dependencies.remove(&owner);
340                        freed += size;
341                        tracing::info!("Evicted CPU cache {:?}, freed {} bytes", owner, size);
342                    }
343                }
344            }
345        }
346    }
347
348    /// Get total memory usage across all caches in bytes
349    pub fn total_memory_usage(&self) -> usize {
350        self.caches
351            .iter()
352            .map(|entry| entry.value().lock().memory_usage())
353            .sum()
354    }
355
356    /// Get number of active caches
357    pub fn cache_count(&self) -> usize {
358        self.caches.len()
359    }
360
361    /// Clear all caches (useful for cleanup)
362    pub fn clear_all(&self) {
363        self.caches.clear();
364        self.delta_dependencies.clear();
365        tracing::info!("Cleared all KV caches from registry");
366    }
367
368    /// Register the tenant delta that produced a cache owner's KV.
369    ///
370    /// Records `(tenant_id, weight_epoch)` as the effective tenant whose delta
371    /// contributed to the cache's weights, along with that delta's weight epoch
372    /// at compute time — pass `None` when no tenant delta contributes (bare
373    /// base model or base-delta-only inference; the epoch is then irrelevant).
374    /// When that tenant's delta is later evicted, reset, or removed,
375    /// [`Self::invalidate_for_tenant`] clears every cache recorded under it.
376    ///
377    /// **Stale-weight guard:** if the effective `(tenant_id, weight_epoch)`
378    /// differs from the value recorded the last time this owner's cache was
379    /// computed, the existing KV was produced under different weights and is
380    /// cleared in place (cached token IDs + every layer cache) before the new
381    /// dependency is recorded, so generation can never reuse it. Returns `true`
382    /// when such a stale cache was cleared. This is the barrier that stops a
383    /// session cache from crossing a weight boundary — no-delta↔delta,
384    /// tenant-A↔tenant-B, *and* same-tenant in-place re-adaptation (the epoch
385    /// advances while the tenant id stays the same): the next request
386    /// re-`register`s with the now-effective tenant and epoch, the mismatch is
387    /// detected, and the stale KV is dropped, forcing a full recompute. Both
388    /// the bump (at adapt/train/rollback/reset time) and this comparison are
389    /// O(1) — no per-adaptation scan of the dependency map. A cache with no
390    /// prior record (fresh, or just invalidated) is never treated as stale.
391    pub fn register_delta_dependency(
392        &self,
393        owner: &CacheOwner,
394        tenant_id: Option<String>,
395        weight_epoch: u64,
396    ) -> bool {
397        let dependency = tenant_id.map(|t| (t, weight_epoch));
398        let stale = match self.delta_dependencies.get(owner) {
399            Some(prev) => *prev != dependency,
400            None => false,
401        };
402        self.delta_dependencies.insert(owner.clone(), dependency);
403
404        if stale {
405            if let Some(cache) = self.caches.get(owner) {
406                let mut guard = cache.lock();
407                // Mirror invalidate_for_tenant's cleanup: wipe both the prefix
408                // tokens and the layer caches so neither prefix-matching nor a
409                // retained tensor can resurrect the stale values.
410                guard.set_cached_tokens(Vec::new());
411                guard.clear_all();
412                tracing::info!(
413                    "Cleared stale KV cache for {:?}: effective tenant or weight epoch changed since last compute",
414                    owner
415                );
416            }
417        }
418
419        stale
420    }
421
422    /// Invalidate all KV caches that depend on a specific subject's delta.
423    ///
424    /// Called when a subject's delta is evicted, reset, or significantly modified.
425    /// Returns the number of caches invalidated.
426    pub fn invalidate_for_tenant(&self, tenant_id: &str) -> usize {
427        let mut invalidated = 0;
428        let to_remove: Vec<CacheOwner> = self
429            .delta_dependencies
430            .iter()
431            .filter_map(|entry| {
432                if entry.value().as_ref().map(|(t, _)| t.as_str()) == Some(tenant_id) {
433                    Some(entry.key().clone())
434                } else {
435                    None
436                }
437            })
438            .collect();
439
440        for owner in to_remove {
441            // Clear cached token IDs before removing — ensures prefix matching
442            // won't reuse stale KV values if the cache is somehow retained.
443            if let Some(cache) = self.caches.get(&owner) {
444                let mut guard = cache.lock();
445                guard.set_cached_tokens(Vec::new());
446                guard.clear_all();
447            }
448            self.caches.remove(&owner);
449            self.delta_dependencies.remove(&owner);
450            invalidated += 1;
451        }
452
453        if invalidated > 0 {
454            // Never log the raw tenant subject (#1253/#1261 review): emit the
455            // same opaque keyed-hash id used for metric attributes.
456            let opaque =
457                crate::runtime::token_metrics::opaque_tenant_id(&Some(tenant_id.to_owned()));
458            tracing::info!(
459                "Invalidated {} KV caches dependent on subject delta (tenant {})",
460                invalidated,
461                opaque.map_or_else(|| "anonymous".to_owned(), |h| format!("tenant:{h:016x}"))
462            );
463        }
464
465        invalidated
466    }
467}
468
469// ============================================================================
470// Paged Block Pool (PagedAttention-style memory management)
471// ============================================================================
472
473/// Number of tokens per block in the paged KV cache.
474/// 256 balances fragmentation overhead vs block reuse granularity.
475pub const BLOCK_SIZE: usize = 256;
476
477/// Opaque handle to a block in the pool.
478pub type BlockId = usize;
479
480/// Failure to allocate a block from the shared pool because no free blocks remain.
481///
482/// This is a *fail-soft* signal — distinct from a real error — so a scheduler can
483/// turn it into admission-defer (retry the sequence on a later step once other
484/// sequences release blocks) rather than failing the request outright. Callers
485/// that receive an [`anyhow::Error`] from cache `update` can recover the typed
486/// reason via `err.downcast_ref::<BlockPoolExhausted>()`.
487#[derive(Debug, Clone, Copy, PartialEq, Eq)]
488pub struct BlockPoolExhausted {
489    /// Number of blocks the pool can hold in total.
490    pub total_blocks: usize,
491}
492
493impl std::fmt::Display for BlockPoolExhausted {
494    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
495        write!(
496            f,
497            "block pool exhausted (all {} blocks in use)",
498            self.total_blocks
499        )
500    }
501}
502
503impl std::error::Error for BlockPoolExhausted {}
504
505/// Shared pool of fixed-size GPU tensor blocks for KV cache storage.
506///
507/// All KV cache memory is pre-allocated in this pool at startup. Sessions
508/// allocate and free blocks from the pool — no per-session `cudaMalloc` calls,
509/// zero fragmentation, and instant block reuse across sessions.
510///
511/// Each block stores `BLOCK_SIZE` tokens of K or V for a single attention layer.
512/// Shape: `[1, BLOCK_SIZE, num_kv_heads, head_dim]`.
513pub struct BlockPool {
514    /// Pre-allocated tensor blocks on GPU (one per block ID).
515    /// Each tensor has shape [1, BLOCK_SIZE, num_kv_heads, head_dim].
516    blocks: Vec<Tensor>,
517    /// Free block IDs available for allocation (LIFO stack for cache locality).
518    free_list: Vec<BlockId>,
519    /// Current owner of each block (indexed by `BlockId`); `None` when free.
520    ///
521    /// Enforces tenant isolation in the shared pool: a block allocated by one
522    /// [`CacheOwner`] cannot be freed or used by another (see [`BlockPool::free`]).
523    block_owner: Vec<Option<CacheOwner>>,
524    /// Block tensor shape: [1, BLOCK_SIZE, num_kv_heads, head_dim]
525    block_shape: [i64; 4],
526    /// Device the blocks are allocated on
527    device: tch::Device,
528    /// Data type of the blocks
529    dtype: DType,
530    /// Total number of blocks in the pool
531    total_blocks: usize,
532}
533
534impl BlockPool {
535    /// Create a new block pool with `num_blocks` pre-allocated blocks.
536    ///
537    /// All blocks are allocated on `device` with dtype `dtype`.
538    /// `num_kv_heads` and `head_dim` define the per-head tensor dimensions.
539    pub fn new(
540        num_blocks: usize,
541        num_kv_heads: usize,
542        head_dim: usize,
543        device: tch::Device,
544        dtype: DType,
545    ) -> Result<Self> {
546        let block_shape = [1, BLOCK_SIZE as i64, num_kv_heads as i64, head_dim as i64];
547
548        tracing::info!(
549            "Allocating block pool: {} blocks x {:?} ({:.1} MB total)",
550            num_blocks,
551            block_shape,
552            (num_blocks as f64
553                * BLOCK_SIZE as f64
554                * num_kv_heads as f64
555                * head_dim as f64
556                * match dtype {
557                    DType::Half | DType::BFloat16 => 2.0,
558                    _ => 4.0,
559                })
560                / (1024.0 * 1024.0),
561        );
562
563        let mut blocks = Vec::with_capacity(num_blocks);
564        let mut free_list = Vec::with_capacity(num_blocks);
565
566        for id in 0..num_blocks {
567            let block = safe_zeros(&block_shape, (dtype, device))?;
568            blocks.push(block);
569            free_list.push(id);
570        }
571
572        Ok(Self {
573            blocks,
574            free_list,
575            block_owner: vec![None; num_blocks],
576            block_shape,
577            device,
578            dtype,
579            total_blocks: num_blocks,
580        })
581    }
582
583    /// Allocate a block from the pool on behalf of `owner`.
584    ///
585    /// Returns [`BlockPoolExhausted`] (a fail-soft signal a scheduler can turn
586    /// into admission-defer) when no free blocks remain. The allocated block is
587    /// tagged with `owner` so it can only be freed/used by that same owner.
588    pub fn allocate(&mut self, owner: &CacheOwner) -> Result<BlockId, BlockPoolExhausted> {
589        match self.free_list.pop() {
590            Some(id) => {
591                self.block_owner[id] = Some(owner.clone());
592                Ok(id)
593            }
594            None => Err(BlockPoolExhausted {
595                total_blocks: self.total_blocks,
596            }),
597        }
598    }
599
600    /// Return a block to the pool.
601    ///
602    /// Panics (in debug) / logs and refuses (in release) if `owner` does not
603    /// match the owner the block was allocated to — this enforces tenant
604    /// isolation: one [`CacheOwner`] can never free another's block.
605    pub fn free(&mut self, owner: &CacheOwner, id: BlockId) {
606        debug_assert!(id < self.total_blocks, "Invalid block ID: {}", id);
607        if id >= self.total_blocks {
608            return;
609        }
610        match &self.block_owner[id] {
611            Some(current) if current == owner => {
612                self.block_owner[id] = None;
613                self.free_list.push(id);
614            }
615            Some(current) => {
616                debug_assert!(
617                    false,
618                    "cross-owner block free rejected: block {} owned by {:?}, freed by {:?}",
619                    id, current, owner
620                );
621                tracing::error!(
622                    "cross-owner block free rejected: block {} owned by {:?}, freed by {:?}",
623                    id,
624                    current,
625                    owner
626                );
627            }
628            None => {
629                debug_assert!(false, "double-free of block {}", id);
630                tracing::error!("double-free of block {} (already in free list)", id);
631            }
632        }
633    }
634
635    /// Owner currently holding `id`, if any (for tests/metrics).
636    pub fn owner_of(&self, id: BlockId) -> Option<&CacheOwner> {
637        self.block_owner.get(id).and_then(|o| o.as_ref())
638    }
639
640    /// Get a reference to a block's tensor.
641    pub fn get_block(&self, id: BlockId) -> &Tensor {
642        &self.blocks[id]
643    }
644
645    /// Number of blocks currently in use.
646    pub fn used_blocks(&self) -> usize {
647        self.total_blocks - self.free_list.len()
648    }
649
650    /// Number of blocks available for allocation.
651    pub fn free_block_count(&self) -> usize {
652        self.free_list.len()
653    }
654
655    /// Total number of blocks in the pool.
656    pub fn total_blocks(&self) -> usize {
657        self.total_blocks
658    }
659
660    /// Memory used by allocated blocks (approximate, in bytes).
661    pub fn used_memory(&self) -> usize {
662        let elem_size = match self.dtype {
663            DType::Half | DType::BFloat16 => 2,
664            _ => 4,
665        };
666        let per_block =
667            BLOCK_SIZE * self.block_shape[2] as usize * self.block_shape[3] as usize * elem_size;
668        self.used_blocks() * per_block
669    }
670
671    /// Block shape: [1, BLOCK_SIZE, num_kv_heads, head_dim]
672    pub fn block_shape(&self) -> &[i64; 4] {
673        &self.block_shape
674    }
675
676    /// Device the pool is allocated on.
677    pub fn device(&self) -> tch::Device {
678        self.device
679    }
680
681    /// Data type of the pool's tensors.
682    pub fn dtype(&self) -> DType {
683        self.dtype
684    }
685}
686
687impl std::fmt::Debug for BlockPool {
688    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
689        f.debug_struct("BlockPool")
690            .field("total_blocks", &self.total_blocks)
691            .field("used_blocks", &self.used_blocks())
692            .field("free_blocks", &self.free_block_count())
693            .field("block_shape", &self.block_shape)
694            .field("device", &self.device)
695            .field("dtype", &self.dtype)
696            .finish()
697    }
698}
699
700// ============================================================================
701// Original KV Cache Implementation
702// ============================================================================
703
704/// Default chunk size for KV cache growth (in tokens)
705const DEFAULT_CHUNK_SIZE: usize = 1024;
706
707/// Default blocksize for bitsandbytes quantization
708#[cfg(feature = "bnb")]
709const QUANT_BLOCKSIZE: usize = 64;
710
711/// Number of tokens to accumulate before flushing to quantized storage
712#[cfg(feature = "bnb")]
713const BUFFER_FLUSH_THRESHOLD: usize = 64;
714
715/// Get byte size per element for a dtype
716fn dtype_element_size(dtype: DType) -> usize {
717    match dtype {
718        DType::Half | DType::BFloat16 => 2,
719        _ => 4, // Float, Double, Int, etc.
720    }
721}
722
723/// Quantized tensor storage - stores a contiguous quantized tensor
724#[cfg(feature = "bnb")]
725#[derive(Debug)]
726struct QuantizedTensor {
727    /// Quantized data bytes
728    data: Vec<u8>,
729    /// Quantization state (codebook, absmax, etc.)
730    state: bitsandbytes_sys::QuantState,
731    /// Original tensor shape for reconstruction
732    shape: Vec<i64>,
733    /// Original dtype for reconstruction
734    dtype: DType,
735    /// Target device for reconstruction
736    device: Device,
737}
738
739#[cfg(feature = "bnb")]
740impl QuantizedTensor {
741    /// Quantize a tensor using the specified quantization type.
742    ///
743    /// If the tensor is on a GPU (CUDA/ROCm) and is BF16 or FP16, uses the
744    /// GPU-native bitsandbytes kernels directly — no CPU round-trip. For CPU
745    /// tensors or f32 dtype, falls back to the CPU quantization path.
746    fn from_tensor(tensor: &Tensor, quant_type: KVQuantType) -> Result<Self> {
747        let shape = tensor.size();
748        let dtype = tensor.kind();
749        let device = tensor.device();
750
751        if quant_type == KVQuantType::None {
752            return Err(anyhow!(
753                "Cannot create QuantizedTensor with KVQuantType::None"
754            ));
755        }
756
757        // GPU-native path: BF16/FP16 on CUDA/ROCm → quantize directly on GPU
758        let use_gpu_path = device != Device::Cpu
759            && (dtype == DType::BFloat16 || dtype == DType::Half)
760            && quant_type == KVQuantType::Int8;
761
762        if use_gpu_path {
763            return Self::from_tensor_gpu(tensor, &shape, dtype, device);
764        }
765
766        // CPU fallback path: copy to CPU, convert to f32, quantize
767        let cpu_tensor = tensor
768            .to_device(Device::Cpu)
769            .to_kind(DType::Float)
770            .contiguous();
771        let numel = cpu_tensor.numel();
772
773        let mut f32_data = vec![0.0f32; numel];
774        cpu_tensor
775            .f_copy_data(&mut f32_data, numel)
776            .map_err(|e| anyhow!("Failed to copy tensor data: {:?}", e))?;
777
778        let (data, state) = match quant_type {
779            KVQuantType::Int8 => {
780                bitsandbytes_sys::quantize_blockwise_fp32(&f32_data, QUANT_BLOCKSIZE)
781                    .map_err(|e| anyhow!("Int8 quantization failed: {:?}", e))?
782            }
783            KVQuantType::Nf4 => {
784                bitsandbytes_sys::quantize_4bit_nf4_fp32(&f32_data, QUANT_BLOCKSIZE)
785                    .map_err(|e| anyhow!("NF4 quantization failed: {:?}", e))?
786            }
787            KVQuantType::Fp4 => {
788                bitsandbytes_sys::quantize_4bit_fp4_fp32(&f32_data, QUANT_BLOCKSIZE)
789                    .map_err(|e| anyhow!("FP4 quantization failed: {:?}", e))?
790            }
791            KVQuantType::None => unreachable!(),
792        };
793
794        tracing::trace!(
795            "Quantized tensor (CPU path): {} elements, shape {:?} -> {} bytes ({:.1}% of f32)",
796            numel,
797            shape,
798            data.len(),
799            (data.len() as f64 / (numel * 4) as f64) * 100.0
800        );
801
802        Ok(Self {
803            data,
804            state,
805            shape,
806            dtype,
807            device,
808        })
809    }
810
811    /// GPU-native quantization: operates directly on GPU BF16/FP16 tensors.
812    ///
813    /// Uses bitsandbytes CUDA/HIP kernels. The code/absmax arrays are created
814    /// as CPU Vecs (they're small metadata), while the quantization kernel reads
815    /// from GPU input and writes to a GPU-resident output tensor. We then copy
816    /// the small quantized result back to CPU for storage (the quantized data
817    /// is ~8x smaller than the original, so this copy is cheap).
818    fn from_tensor_gpu(
819        tensor: &Tensor,
820        shape: &[i64],
821        dtype: DType,
822        device: Device,
823    ) -> Result<Self> {
824        let numel = tensor.numel();
825        let contiguous = tensor.contiguous();
826
827        // Create quantization state (CPU — small metadata)
828        let mut state = bitsandbytes_sys::QuantState::new_8bit(numel, QUANT_BLOCKSIZE);
829
830        // Allocate GPU output tensor for quantized data
831        let output_tensor = Tensor::zeros([numel as i64], (DType::Uint8, device));
832
833        // Allocate GPU tensors for code and absmax
834        let code_tensor = Tensor::from_slice(&state.code).to_device(device);
835        let absmax_tensor = Tensor::zeros([state.absmax.len() as i64], (DType::Float, device));
836
837        // Call GPU-native kernel
838        unsafe {
839            let input_ptr = contiguous.data_ptr() as *mut std::ffi::c_void;
840            let code_ptr = code_tensor.data_ptr() as *mut f32;
841            let absmax_ptr = absmax_tensor.data_ptr() as *mut f32;
842            let output_ptr = output_tensor.data_ptr() as *mut u8;
843
844            match dtype {
845                DType::BFloat16 => bitsandbytes_sys::quantize_blockwise_bf16_gpu(
846                    code_ptr,
847                    input_ptr,
848                    absmax_ptr,
849                    output_ptr,
850                    QUANT_BLOCKSIZE as i32,
851                    numel as i32,
852                ),
853                DType::Half => bitsandbytes_sys::quantize_blockwise_fp16_gpu(
854                    code_ptr,
855                    input_ptr,
856                    absmax_ptr,
857                    output_ptr,
858                    QUANT_BLOCKSIZE as i32,
859                    numel as i32,
860                ),
861                _ => unreachable!("GPU path only for BF16/FP16"),
862            }
863        }
864
865        // Copy small results back to CPU for storage
866        // quantized data: numel bytes (8x smaller than BF16 input)
867        // absmax: n_blocks * 4 bytes (tiny)
868        let mut data = vec![0u8; numel];
869        output_tensor
870            .to_device(Device::Cpu)
871            .f_copy_data(&mut data, numel)
872            .map_err(|e| anyhow!("Failed to copy quantized data: {:?}", e))?;
873
874        let mut absmax = vec![0.0f32; state.absmax.len()];
875        absmax_tensor
876            .to_device(Device::Cpu)
877            .f_copy_data(&mut absmax, state.absmax.len())
878            .map_err(|e| anyhow!("Failed to copy absmax: {:?}", e))?;
879        state.absmax = absmax;
880
881        tracing::trace!(
882            "Quantized tensor (GPU path, {:?}): {} elements -> {} bytes ({:.1}% of original)",
883            dtype,
884            numel,
885            data.len(),
886            (data.len() as f64 / (numel as f64 * dtype_element_size(dtype) as f64)) * 100.0
887        );
888
889        Ok(Self {
890            data,
891            state,
892            shape: shape.to_vec(),
893            dtype,
894            device,
895        })
896    }
897
898    /// Dequantize back to a tensor.
899    ///
900    /// If the target device is GPU and dtype is BF16/FP16, uses GPU-native
901    /// dequantization to avoid the CPU→f32→GPU round-trip.
902    fn to_tensor(&self) -> Result<Tensor> {
903        // GPU-native dequant path
904        let use_gpu_path = self.device != Device::Cpu
905            && (self.dtype == DType::BFloat16 || self.dtype == DType::Half)
906            && !self.state.is_4bit;
907
908        if use_gpu_path {
909            return self.to_tensor_gpu();
910        }
911
912        // CPU fallback path
913        let f32_data = if self.state.is_4bit {
914            match self.state.quant_type {
915                Some(bitsandbytes_sys::QuantType::Nf4) => {
916                    bitsandbytes_sys::dequantize_4bit_nf4_fp32(&self.data, &self.state)
917                        .map_err(|e| anyhow!("NF4 dequantization failed: {:?}", e))?
918                }
919                Some(bitsandbytes_sys::QuantType::Fp4) => {
920                    bitsandbytes_sys::dequantize_4bit_fp4_fp32(&self.data, &self.state)
921                        .map_err(|e| anyhow!("FP4 dequantization failed: {:?}", e))?
922                }
923                _ => {
924                    return Err(anyhow!("Unknown 4-bit quantization type"));
925                }
926            }
927        } else {
928            bitsandbytes_sys::dequantize_blockwise_fp32(&self.data, &self.state)
929                .map_err(|e| anyhow!("Int8 dequantization failed: {:?}", e))?
930        };
931
932        // Create tensor from f32 data
933        let cpu_tensor = Tensor::from_slice(&f32_data).reshape(&self.shape);
934
935        // Convert to original dtype and move to original device
936        let tensor = cpu_tensor.to_kind(self.dtype).to_device(self.device);
937
938        Ok(tensor)
939    }
940
941    /// GPU-native dequantization: produces BF16/FP16 tensor directly on GPU.
942    ///
943    /// Copies the small quantized data + absmax to GPU, then calls the
944    /// bitsandbytes BF16/FP16 dequant kernel. Output is GPU-resident in the
945    /// original dtype — no f32 intermediate, no CPU→GPU dtype conversion.
946    fn to_tensor_gpu(&self) -> Result<Tensor> {
947        let numel = self.state.n_elements;
948
949        // Copy quantized data and absmax to GPU (small: ~numel bytes + n_blocks*4 bytes)
950        let quant_tensor = Tensor::from_slice(&self.data).to_device(self.device);
951        let code_tensor = Tensor::from_slice(&self.state.code).to_device(self.device);
952        let absmax_tensor = Tensor::from_slice(&self.state.absmax).to_device(self.device);
953
954        // Allocate output tensor on GPU in original dtype
955        let output_tensor = Tensor::zeros([numel as i64], (self.dtype, self.device));
956
957        unsafe {
958            let quant_ptr = quant_tensor.data_ptr() as *mut u8;
959            let code_ptr = code_tensor.data_ptr() as *mut f32;
960            let absmax_ptr = absmax_tensor.data_ptr() as *mut f32;
961            let output_ptr = output_tensor.data_ptr() as *mut std::ffi::c_void;
962
963            match self.dtype {
964                DType::BFloat16 => bitsandbytes_sys::dequantize_blockwise_bf16_gpu(
965                    code_ptr,
966                    quant_ptr,
967                    absmax_ptr,
968                    output_ptr,
969                    self.state.blocksize as i32,
970                    numel as i32,
971                ),
972                DType::Half => bitsandbytes_sys::dequantize_blockwise_fp16_gpu(
973                    code_ptr,
974                    quant_ptr,
975                    absmax_ptr,
976                    output_ptr,
977                    self.state.blocksize as i32,
978                    numel as i32,
979                ),
980                _ => unreachable!("GPU dequant path only for BF16/FP16"),
981            }
982        }
983
984        // Reshape to original shape
985        let result = output_tensor.reshape(&self.shape);
986
987        tracing::trace!(
988            "Dequantized tensor (GPU path, {:?}): {} bytes -> {} elements",
989            self.dtype,
990            self.data.len(),
991            numel
992        );
993
994        Ok(result)
995    }
996
997    /// Get memory usage in bytes
998    fn memory_usage(&self) -> usize {
999        self.data.len() + self.state.code.len() * 4 + self.state.absmax.len() * 4
1000    }
1001}
1002
1003/// Storage for KV cache - either full precision tensors or quantized
1004#[derive(Debug)]
1005enum KVStorage {
1006    /// Full precision tensor storage
1007    FullPrecision {
1008        keys: Option<Tensor>,
1009        values: Option<Tensor>,
1010    },
1011    /// Quantized storage with buffer for recent tokens (requires `bnb` feature)
1012    #[cfg(feature = "bnb")]
1013    Quantized {
1014        /// Quantized historical keys (contiguous)
1015        keys_quantized: Option<QuantizedTensor>,
1016        /// Quantized historical values (contiguous)
1017        values_quantized: Option<QuantizedTensor>,
1018        /// Number of tokens in quantized storage
1019        quantized_len: usize,
1020
1021        /// Buffer for recent tokens (full precision) - not yet quantized
1022        keys_buffer: Option<Tensor>,
1023        /// Buffer for recent values (full precision)
1024        values_buffer: Option<Tensor>,
1025        /// Number of tokens in buffer
1026        buffer_len: usize,
1027
1028        /// Cached dequantized view (valid for current forward pass)
1029        /// This avoids re-dequantizing for each layer
1030        dequant_keys: Option<Tensor>,
1031        dequant_values: Option<Tensor>,
1032        /// Position up to which dequant cache is valid
1033        dequant_valid_len: usize,
1034
1035        /// Quantization type
1036        quant_type: KVQuantType,
1037        /// Template info for tensor creation
1038        dtype: Option<DType>,
1039        device: Option<Device>,
1040    },
1041    /// Paged block storage — fixed-size blocks from a shared pool.
1042    ///
1043    /// Eliminates GPU memory fragmentation by allocating from a pre-allocated
1044    /// pool of fixed-size blocks. `get()` assembles blocks into a contiguous
1045    /// view via `torch.cat`. Inspired by PagedAttention (vLLM, SOSP 2023).
1046    Paged {
1047        /// Owner of the blocks held here (for pool ownership assertions).
1048        owner: CacheOwner,
1049        /// Block IDs for key tensors (one per BLOCK_SIZE tokens)
1050        key_blocks: Vec<BlockId>,
1051        /// Block IDs for value tensors
1052        value_blocks: Vec<BlockId>,
1053        /// Reference to the shared block pool
1054        pool: Arc<Mutex<BlockPool>>,
1055        /// Cached contiguous view (invalidated on update)
1056        cached_keys: Option<Tensor>,
1057        cached_values: Option<Tensor>,
1058        /// Position up to which the cached view is valid
1059        cached_valid_len: usize,
1060    },
1061}
1062
1063/// KV cache for a single attention layer
1064#[derive(Debug)]
1065pub struct LayerKVCache {
1066    /// Storage for keys and values
1067    storage: KVStorage,
1068    /// Current sequence position (number of cached tokens)
1069    pub seq_pos: usize,
1070    /// Maximum sequence length
1071    pub max_seq_len: usize,
1072    /// Currently allocated capacity (grows in chunks up to max_seq_len)
1073    allocated_capacity: usize,
1074    /// Quantization type
1075    quant_type: KVQuantType,
1076}
1077
1078impl LayerKVCache {
1079    /// Create a new layer KV cache
1080    #[cfg(feature = "bnb")]
1081    pub fn new(max_seq_len: usize, quant_type: KVQuantType) -> Self {
1082        let storage = match quant_type {
1083            KVQuantType::None => KVStorage::FullPrecision {
1084                keys: None,
1085                values: None,
1086            },
1087            _ => KVStorage::Quantized {
1088                keys_quantized: None,
1089                values_quantized: None,
1090                quantized_len: 0,
1091                keys_buffer: None,
1092                values_buffer: None,
1093                buffer_len: 0,
1094                dequant_keys: None,
1095                dequant_values: None,
1096                dequant_valid_len: 0,
1097                quant_type,
1098                dtype: None,
1099                device: None,
1100            },
1101        };
1102
1103        Self {
1104            storage,
1105            seq_pos: 0,
1106            max_seq_len,
1107            allocated_capacity: 0,
1108            quant_type,
1109        }
1110    }
1111
1112    /// Create a new layer KV cache (without bnb feature - quantization disabled)
1113    #[cfg(not(feature = "bnb"))]
1114    pub fn new(max_seq_len: usize, quant_type: KVQuantType) -> Self {
1115        if quant_type != KVQuantType::None {
1116            tracing::warn!(
1117                "KV cache quantization requested ({:?}) but 'bnb' feature not enabled. Falling back to full precision.",
1118                quant_type
1119            );
1120        }
1121
1122        Self {
1123            storage: KVStorage::FullPrecision {
1124                keys: None,
1125                values: None,
1126            },
1127            seq_pos: 0,
1128            max_seq_len,
1129            allocated_capacity: 0,
1130            quant_type: KVQuantType::None,
1131        }
1132    }
1133
1134    /// Create a new layer KV cache using paged block storage owned by `owner`.
1135    pub fn new_paged(max_seq_len: usize, pool: Arc<Mutex<BlockPool>>, owner: CacheOwner) -> Self {
1136        Self {
1137            storage: KVStorage::Paged {
1138                owner,
1139                key_blocks: Vec::new(),
1140                value_blocks: Vec::new(),
1141                pool,
1142                cached_keys: None,
1143                cached_values: None,
1144                cached_valid_len: 0,
1145            },
1146            seq_pos: 0,
1147            max_seq_len,
1148            allocated_capacity: 0,
1149            quant_type: KVQuantType::None,
1150        }
1151    }
1152
1153    /// Release any paged blocks held by this layer back to the shared pool.
1154    ///
1155    /// Shared by [`LayerKVCache::clear`] and the [`Drop`] impl so that blocks
1156    /// always return to the [`BlockPool`] free list — even when the cache is
1157    /// dropped via registry eviction (`caches.remove`) without an explicit
1158    /// `clear()` (the source of the original paged-pool leak).
1159    fn release_paged_blocks(&mut self) {
1160        if let KVStorage::Paged {
1161            owner,
1162            key_blocks,
1163            value_blocks,
1164            pool,
1165            ..
1166        } = &mut self.storage
1167        {
1168            if key_blocks.is_empty() && value_blocks.is_empty() {
1169                return;
1170            }
1171            let mut pool_guard = pool.lock();
1172            for &id in key_blocks.iter() {
1173                pool_guard.free(owner, id);
1174            }
1175            for &id in value_blocks.iter() {
1176                pool_guard.free(owner, id);
1177            }
1178            key_blocks.clear();
1179            value_blocks.clear();
1180        }
1181    }
1182
1183    /// Ensure cache has capacity for required_len tokens (full precision only)
1184    fn ensure_capacity_fp(&mut self, required_len: usize, template: &Tensor) -> Result<()> {
1185        if required_len <= self.allocated_capacity {
1186            return Ok(());
1187        }
1188
1189        // Round up to chunk boundary
1190        let new_capacity = required_len.div_ceil(DEFAULT_CHUNK_SIZE) * DEFAULT_CHUNK_SIZE;
1191        let new_capacity = new_capacity.min(self.max_seq_len);
1192
1193        let shape = template.size();
1194        if shape.len() != 4 {
1195            return Err(anyhow!("Expected 4D tensor, got {:?}", shape));
1196        }
1197        let (batch_size, num_heads, head_dim) = (shape[0], shape[2], shape[3]);
1198
1199        let device = template.device();
1200        let dtype = template.kind();
1201        let new_shape = [batch_size, new_capacity as i64, num_heads, head_dim];
1202
1203        let cache_size_mb = estimate_tensor_size_mb(&new_shape, dtype);
1204        tracing::debug!(
1205            "Growing KV cache: {} -> {} tokens ({:.1} MB per tensor)",
1206            self.allocated_capacity,
1207            new_capacity,
1208            cache_size_mb
1209        );
1210
1211        let new_keys = safe_zeros(&new_shape, (dtype, device))?;
1212        let new_values = safe_zeros(&new_shape, (dtype, device))?;
1213
1214        // Copy existing data if any
1215        if let KVStorage::FullPrecision {
1216            keys: Some(old_keys),
1217            values: Some(old_values),
1218        } = &self.storage
1219        {
1220            if self.seq_pos > 0 {
1221                new_keys
1222                    .narrow(1, 0, self.seq_pos as i64)
1223                    .copy_(&old_keys.narrow(1, 0, self.seq_pos as i64));
1224                new_values
1225                    .narrow(1, 0, self.seq_pos as i64)
1226                    .copy_(&old_values.narrow(1, 0, self.seq_pos as i64));
1227            }
1228        }
1229
1230        self.storage = KVStorage::FullPrecision {
1231            keys: Some(new_keys),
1232            values: Some(new_values),
1233        };
1234        self.allocated_capacity = new_capacity;
1235
1236        Ok(())
1237    }
1238
1239    /// Flush buffer to quantized storage
1240    #[cfg(feature = "bnb")]
1241    fn flush_buffer(&mut self) -> Result<()> {
1242        if let KVStorage::Quantized {
1243            keys_quantized,
1244            values_quantized,
1245            quantized_len,
1246            keys_buffer,
1247            values_buffer,
1248            buffer_len,
1249            dequant_keys,
1250            dequant_values,
1251            dequant_valid_len,
1252            quant_type,
1253            ..
1254        } = &mut self.storage
1255        {
1256            if *buffer_len == 0 {
1257                return Ok(());
1258            }
1259
1260            let kb = keys_buffer
1261                .as_ref()
1262                .ok_or_else(|| anyhow!("Buffer keys missing"))?;
1263            let vb = values_buffer
1264                .as_ref()
1265                .ok_or_else(|| anyhow!("Buffer values missing"))?;
1266
1267            // Get just the valid portion of the buffer
1268            let keys_to_quantize = kb.narrow(1, 0, *buffer_len as i64);
1269            let values_to_quantize = vb.narrow(1, 0, *buffer_len as i64);
1270
1271            if let (Some(kq), Some(vq)) = (keys_quantized.as_ref(), values_quantized.as_ref()) {
1272                // Merge: dequantize existing + concat buffer + requantize
1273                let existing_keys = kq.to_tensor()?;
1274                let existing_values = vq.to_tensor()?;
1275
1276                let merged_keys = Tensor::cat(&[existing_keys, keys_to_quantize], 1);
1277                let merged_values = Tensor::cat(&[existing_values, values_to_quantize], 1);
1278
1279                *keys_quantized = Some(QuantizedTensor::from_tensor(&merged_keys, *quant_type)?);
1280                *values_quantized =
1281                    Some(QuantizedTensor::from_tensor(&merged_values, *quant_type)?);
1282
1283                tracing::debug!(
1284                    "Flushed buffer: merged {} + {} = {} tokens",
1285                    *quantized_len,
1286                    *buffer_len,
1287                    *quantized_len + *buffer_len
1288                );
1289            } else {
1290                // First flush - just quantize the buffer
1291                *keys_quantized = Some(QuantizedTensor::from_tensor(
1292                    &keys_to_quantize,
1293                    *quant_type,
1294                )?);
1295                *values_quantized = Some(QuantizedTensor::from_tensor(
1296                    &values_to_quantize,
1297                    *quant_type,
1298                )?);
1299
1300                tracing::debug!("Initial quantization: {} tokens", *buffer_len);
1301            }
1302
1303            *quantized_len += *buffer_len;
1304            *buffer_len = 0;
1305
1306            // Invalidate dequant cache since quantized data changed
1307            *dequant_keys = None;
1308            *dequant_values = None;
1309            *dequant_valid_len = 0;
1310        }
1311
1312        Ok(())
1313    }
1314
1315    /// Update cache with new keys and values
1316    pub fn update(
1317        &mut self,
1318        new_keys: &Tensor,
1319        new_values: &Tensor,
1320        start_pos: usize,
1321    ) -> Result<()> {
1322        let k_size = new_keys.size();
1323        if k_size.len() != 4 {
1324            return Err(anyhow!("Expected 4D tensor for keys, got {:?}", k_size));
1325        }
1326        let seq_len = k_size[1] as usize;
1327
1328        // Check bounds against hard limit
1329        let end_pos = start_pos + seq_len;
1330        if end_pos > self.max_seq_len {
1331            return Err(anyhow!(
1332                "Cache overflow: trying to cache {} tokens starting at position {}, but max_seq_len is {}",
1333                seq_len, start_pos, self.max_seq_len
1334            ));
1335        }
1336
1337        match &mut self.storage {
1338            KVStorage::FullPrecision { .. } => {
1339                // Grow cache if needed (chunked allocation)
1340                self.ensure_capacity_fp(end_pos, new_keys)?;
1341
1342                // Re-borrow after potential reallocation
1343                if let KVStorage::FullPrecision {
1344                    keys: Some(cached_keys),
1345                    values: Some(cached_values),
1346                } = &self.storage
1347                {
1348                    cached_keys
1349                        .narrow(1, start_pos as i64, seq_len as i64)
1350                        .copy_(new_keys);
1351                    cached_values
1352                        .narrow(1, start_pos as i64, seq_len as i64)
1353                        .copy_(new_values);
1354                }
1355            }
1356            #[cfg(feature = "bnb")]
1357            KVStorage::Quantized {
1358                keys_quantized,
1359                values_quantized,
1360                quantized_len,
1361                keys_buffer,
1362                values_buffer,
1363                buffer_len,
1364                dequant_keys,
1365                dequant_values,
1366                dequant_valid_len,
1367                dtype,
1368                device,
1369                ..
1370            } => {
1371                // Store template info on first update
1372                if dtype.is_none() {
1373                    *dtype = Some(new_keys.kind());
1374                    *device = Some(new_keys.device());
1375                }
1376
1377                // Invalidate dequant cache
1378                *dequant_keys = None;
1379                *dequant_values = None;
1380                *dequant_valid_len = 0;
1381
1382                if start_pos == 0 {
1383                    // Fresh prompt - put everything in buffer, will be quantized on flush
1384                    *keys_quantized = None;
1385                    *values_quantized = None;
1386                    *quantized_len = 0;
1387
1388                    *keys_buffer = Some(new_keys.shallow_clone());
1389                    *values_buffer = Some(new_values.shallow_clone());
1390                    *buffer_len = seq_len;
1391
1392                    // Flush immediately if large prompt
1393                    if seq_len >= BUFFER_FLUSH_THRESHOLD {
1394                        self.flush_buffer()?;
1395                    }
1396                } else {
1397                    // Incremental update - append to buffer
1398                    let dt = dtype.ok_or_else(|| anyhow!("dtype not set"))?;
1399                    let dev = device.ok_or_else(|| anyhow!("device not set"))?;
1400
1401                    // Ensure buffer exists and has capacity
1402                    let shape = new_keys.size();
1403                    let (batch_size, num_heads, head_dim) = (shape[0], shape[2], shape[3]);
1404
1405                    if keys_buffer.is_none() {
1406                        // Create buffer with capacity for threshold + some extra
1407                        let buf_capacity = (BUFFER_FLUSH_THRESHOLD + 64) as i64;
1408                        *keys_buffer = Some(Tensor::zeros(
1409                            [batch_size, buf_capacity, num_heads, head_dim],
1410                            (dt, dev),
1411                        ));
1412                        *values_buffer = Some(Tensor::zeros(
1413                            [batch_size, buf_capacity, num_heads, head_dim],
1414                            (dt, dev),
1415                        ));
1416                    }
1417
1418                    let kb = keys_buffer.as_ref().ok_or_else(|| {
1419                        anyhow::anyhow!("Internal error: keys buffer not initialized")
1420                    })?;
1421
1422                    // Check if buffer needs to grow
1423                    let buf_capacity = kb.size()[1] as usize;
1424                    if *buffer_len + seq_len > buf_capacity {
1425                        // Flush current buffer first
1426                        self.flush_buffer()?;
1427
1428                        // Re-borrow after flush
1429                        if let KVStorage::Quantized {
1430                            keys_buffer,
1431                            values_buffer,
1432                            buffer_len,
1433                            ..
1434                        } = &mut self.storage
1435                        {
1436                            // Create fresh buffer
1437                            let buf_capacity = (BUFFER_FLUSH_THRESHOLD + 64) as i64;
1438                            *keys_buffer = Some(Tensor::zeros(
1439                                [batch_size, buf_capacity, num_heads, head_dim],
1440                                (dt, dev),
1441                            ));
1442                            *values_buffer = Some(Tensor::zeros(
1443                                [batch_size, buf_capacity, num_heads, head_dim],
1444                                (dt, dev),
1445                            ));
1446                            *buffer_len = 0;
1447                        }
1448                    }
1449
1450                    // Re-borrow for the actual copy
1451                    if let KVStorage::Quantized {
1452                        keys_buffer: Some(kb),
1453                        values_buffer: Some(vb),
1454                        buffer_len,
1455                        ..
1456                    } = &mut self.storage
1457                    {
1458                        // Copy new data into buffer
1459                        kb.narrow(1, *buffer_len as i64, seq_len as i64)
1460                            .copy_(new_keys);
1461                        vb.narrow(1, *buffer_len as i64, seq_len as i64)
1462                            .copy_(new_values);
1463                        *buffer_len += seq_len;
1464                    }
1465
1466                    // Check if we should flush
1467                    if let KVStorage::Quantized { buffer_len, .. } = &self.storage {
1468                        if *buffer_len >= BUFFER_FLUSH_THRESHOLD {
1469                            self.flush_buffer()?;
1470                        }
1471                    }
1472                }
1473            }
1474            KVStorage::Paged {
1475                owner,
1476                key_blocks,
1477                value_blocks,
1478                pool,
1479                cached_keys,
1480                cached_values,
1481                cached_valid_len,
1482            } => {
1483                // Invalidate cached contiguous view
1484                *cached_keys = None;
1485                *cached_values = None;
1486                *cached_valid_len = 0;
1487
1488                let mut pool_guard = pool.lock();
1489
1490                // Write K/V into blocks, allocating new blocks as needed
1491                let mut pos = start_pos;
1492                let mut token_offset = 0;
1493                while token_offset < seq_len {
1494                    let block_idx = pos / BLOCK_SIZE;
1495                    let offset_in_block = pos % BLOCK_SIZE;
1496                    let tokens_this_block =
1497                        (BLOCK_SIZE - offset_in_block).min(seq_len - token_offset);
1498
1499                    // Ensure we have enough blocks allocated. Allocation failure
1500                    // surfaces as the typed `BlockPoolExhausted` (fail-soft) so a
1501                    // scheduler can admission-defer this sequence rather than fail it.
1502                    while key_blocks.len() <= block_idx {
1503                        let kid = pool_guard.allocate(owner)?;
1504                        let vid = match pool_guard.allocate(owner) {
1505                            Ok(vid) => vid,
1506                            Err(e) => {
1507                                // Roll back the just-allocated key block so the pair
1508                                // stays balanced and the key block isn't leaked.
1509                                pool_guard.free(owner, kid);
1510                                return Err(e.into());
1511                            }
1512                        };
1513                        key_blocks.push(kid);
1514                        value_blocks.push(vid);
1515                    }
1516
1517                    // Copy K/V slice into the block at the right offset
1518                    let k_block = pool_guard.get_block(key_blocks[block_idx]);
1519                    let v_block = pool_guard.get_block(value_blocks[block_idx]);
1520
1521                    k_block
1522                        .narrow(1, offset_in_block as i64, tokens_this_block as i64)
1523                        .copy_(&new_keys.narrow(1, token_offset as i64, tokens_this_block as i64));
1524                    v_block
1525                        .narrow(1, offset_in_block as i64, tokens_this_block as i64)
1526                        .copy_(&new_values.narrow(
1527                            1,
1528                            token_offset as i64,
1529                            tokens_this_block as i64,
1530                        ));
1531
1532                    pos += tokens_this_block;
1533                    token_offset += tokens_this_block;
1534                }
1535            }
1536        }
1537
1538        // Update position
1539        self.seq_pos = end_pos;
1540
1541        Ok(())
1542    }
1543
1544    /// Get cached keys and values up to current position
1545    pub fn get(&mut self) -> Result<(Tensor, Tensor)> {
1546        if self.seq_pos == 0 {
1547            return Err(anyhow!("Cache is empty"));
1548        }
1549
1550        match &mut self.storage {
1551            KVStorage::FullPrecision {
1552                keys: Some(cached_keys),
1553                values: Some(cached_values),
1554            } => {
1555                // Return views only - the .contiguous() in attention (after transposes)
1556                // will handle memory layout. Avoids double-copying K/V per layer.
1557                let keys_slice = cached_keys.narrow(1, 0, self.seq_pos as i64);
1558                let values_slice = cached_values.narrow(1, 0, self.seq_pos as i64);
1559                Ok((keys_slice, values_slice))
1560            }
1561            KVStorage::FullPrecision { .. } => Err(anyhow!("Keys/values cache not initialized")),
1562            #[cfg(feature = "bnb")]
1563            KVStorage::Quantized {
1564                keys_quantized,
1565                values_quantized,
1566                quantized_len,
1567                keys_buffer,
1568                values_buffer,
1569                buffer_len,
1570                dequant_keys,
1571                dequant_values,
1572                dequant_valid_len,
1573                ..
1574            } => {
1575                let total_len = *quantized_len + *buffer_len;
1576
1577                // Check if we have a valid cached dequantized view
1578                if let (true, Some(dk), Some(dv)) = (
1579                    *dequant_valid_len == total_len,
1580                    dequant_keys.as_ref(),
1581                    dequant_values.as_ref(),
1582                ) {
1583                    return Ok((dk.shallow_clone(), dv.shallow_clone()));
1584                }
1585
1586                // Need to build the full view
1587                let mut key_parts: Vec<Tensor> = Vec::new();
1588                let mut value_parts: Vec<Tensor> = Vec::new();
1589
1590                // Part 1: Dequantized historical data
1591                if let (Some(kq), Some(vq)) = (keys_quantized.as_ref(), values_quantized.as_ref()) {
1592                    key_parts.push(kq.to_tensor()?);
1593                    value_parts.push(vq.to_tensor()?);
1594                }
1595
1596                // Part 2: Buffer data
1597                if *buffer_len > 0 {
1598                    if let Some(kb) = keys_buffer.as_ref() {
1599                        key_parts.push(kb.narrow(1, 0, *buffer_len as i64));
1600                    }
1601                    if let Some(vb) = values_buffer.as_ref() {
1602                        value_parts.push(vb.narrow(1, 0, *buffer_len as i64));
1603                    }
1604                }
1605
1606                let (keys, values) = if key_parts.is_empty() {
1607                    return Err(anyhow!("No data in cache"));
1608                } else if key_parts.len() == 1 {
1609                    (key_parts.remove(0), value_parts.remove(0))
1610                } else {
1611                    (Tensor::cat(&key_parts, 1), Tensor::cat(&value_parts, 1))
1612                };
1613
1614                // Cache the dequantized view
1615                let keys_clone = keys.shallow_clone();
1616                let values_clone = values.shallow_clone();
1617
1618                *dequant_keys = Some(keys_clone);
1619                *dequant_values = Some(values_clone);
1620                *dequant_valid_len = total_len;
1621
1622                Ok((keys, values))
1623            }
1624            KVStorage::Paged {
1625                key_blocks,
1626                value_blocks,
1627                pool,
1628                cached_keys,
1629                cached_values,
1630                cached_valid_len,
1631                ..
1632            } => {
1633                // Return cached view if still valid
1634                if *cached_valid_len == self.seq_pos {
1635                    if let (Some(ck), Some(cv)) = (cached_keys.as_ref(), cached_values.as_ref()) {
1636                        return Ok((ck.shallow_clone(), cv.shallow_clone()));
1637                    }
1638                }
1639
1640                let pool_guard = pool.lock();
1641                let num_full_blocks = self.seq_pos / BLOCK_SIZE;
1642                let remainder = self.seq_pos % BLOCK_SIZE;
1643                let total_blocks_used = if remainder > 0 {
1644                    num_full_blocks + 1
1645                } else {
1646                    num_full_blocks
1647                };
1648
1649                if total_blocks_used == 0 || key_blocks.is_empty() {
1650                    return Err(anyhow!("No data in paged cache"));
1651                }
1652
1653                // Gather block tensors
1654                let mut key_parts: Vec<Tensor> = Vec::with_capacity(total_blocks_used);
1655                let mut value_parts: Vec<Tensor> = Vec::with_capacity(total_blocks_used);
1656
1657                for i in 0..total_blocks_used {
1658                    let k = pool_guard.get_block(key_blocks[i]);
1659                    let v = pool_guard.get_block(value_blocks[i]);
1660
1661                    if i == total_blocks_used - 1 && remainder > 0 {
1662                        // Last block: narrow to actual token count
1663                        key_parts.push(k.narrow(1, 0, remainder as i64));
1664                        value_parts.push(v.narrow(1, 0, remainder as i64));
1665                    } else {
1666                        key_parts.push(k.shallow_clone());
1667                        value_parts.push(v.shallow_clone());
1668                    }
1669                }
1670
1671                let keys = if key_parts.len() == 1 {
1672                    key_parts.remove(0)
1673                } else {
1674                    Tensor::cat(&key_parts, 1)
1675                };
1676                let values = if value_parts.len() == 1 {
1677                    value_parts.remove(0)
1678                } else {
1679                    Tensor::cat(&value_parts, 1)
1680                };
1681
1682                // Cache the assembled view
1683                *cached_keys = Some(keys.shallow_clone());
1684                *cached_values = Some(values.shallow_clone());
1685                *cached_valid_len = self.seq_pos;
1686
1687                Ok((keys, values))
1688            }
1689        }
1690    }
1691
1692    /// Clear the cache
1693    pub fn clear(&mut self) {
1694        match &mut self.storage {
1695            KVStorage::FullPrecision { keys, values } => {
1696                *keys = None;
1697                *values = None;
1698            }
1699            #[cfg(feature = "bnb")]
1700            KVStorage::Quantized {
1701                keys_quantized,
1702                values_quantized,
1703                quantized_len,
1704                keys_buffer,
1705                values_buffer,
1706                buffer_len,
1707                dequant_keys,
1708                dequant_values,
1709                dequant_valid_len,
1710                dtype,
1711                device,
1712                ..
1713            } => {
1714                *keys_quantized = None;
1715                *values_quantized = None;
1716                *quantized_len = 0;
1717                *keys_buffer = None;
1718                *values_buffer = None;
1719                *buffer_len = 0;
1720                *dequant_keys = None;
1721                *dequant_values = None;
1722                *dequant_valid_len = 0;
1723                *dtype = None;
1724                *device = None;
1725            }
1726            KVStorage::Paged { .. } => {
1727                // Return all blocks to the pool, then reset the cached view.
1728                self.release_paged_blocks();
1729                if let KVStorage::Paged {
1730                    cached_keys,
1731                    cached_values,
1732                    cached_valid_len,
1733                    ..
1734                } = &mut self.storage
1735                {
1736                    *cached_keys = None;
1737                    *cached_values = None;
1738                    *cached_valid_len = 0;
1739                }
1740            }
1741        }
1742        self.seq_pos = 0;
1743        self.allocated_capacity = 0;
1744    }
1745
1746    /// Truncate cache to keep only tokens at positions 0..pos.
1747    ///
1748    /// For FullPrecision and Paged, this adjusts position markers — allocated
1749    /// capacity/blocks remain and will be reused. For Paged, excess blocks
1750    /// beyond the last needed block are freed back to the pool.
1751    ///
1752    /// For Quantized, this falls back to a full clear since truncation within
1753    /// quantized blocks is complex.
1754    pub fn truncate_to(&mut self, pos: usize) {
1755        if pos >= self.seq_pos {
1756            return; // Nothing to truncate
1757        }
1758        match &mut self.storage {
1759            KVStorage::FullPrecision { .. } => {
1760                // Just move the position marker back. Allocated capacity stays.
1761                self.seq_pos = pos;
1762            }
1763            #[cfg(feature = "bnb")]
1764            KVStorage::Quantized { .. } => {
1765                // Truncation within quantized storage is complex — clear and recompute.
1766                self.clear();
1767            }
1768            KVStorage::Paged {
1769                owner,
1770                key_blocks,
1771                value_blocks,
1772                pool,
1773                cached_keys,
1774                cached_values,
1775                cached_valid_len,
1776            } => {
1777                // Free blocks beyond the last needed block
1778                let blocks_needed = if pos == 0 {
1779                    0
1780                } else {
1781                    (pos - 1) / BLOCK_SIZE + 1
1782                };
1783                if key_blocks.len() > blocks_needed {
1784                    let mut pool_guard = pool.lock();
1785                    for &id in &key_blocks[blocks_needed..] {
1786                        pool_guard.free(owner, id);
1787                    }
1788                    for &id in &value_blocks[blocks_needed..] {
1789                        pool_guard.free(owner, id);
1790                    }
1791                    key_blocks.truncate(blocks_needed);
1792                    value_blocks.truncate(blocks_needed);
1793                }
1794                // Invalidate cached view
1795                *cached_keys = None;
1796                *cached_values = None;
1797                *cached_valid_len = 0;
1798                self.seq_pos = pos;
1799            }
1800        }
1801    }
1802
1803    /// Check if cache is initialized
1804    pub fn is_initialized(&self) -> bool {
1805        match &self.storage {
1806            KVStorage::FullPrecision { keys, values } => keys.is_some() && values.is_some(),
1807            #[cfg(feature = "bnb")]
1808            KVStorage::Quantized {
1809                quantized_len,
1810                buffer_len,
1811                ..
1812            } => *quantized_len > 0 || *buffer_len > 0,
1813            KVStorage::Paged { key_blocks, .. } => !key_blocks.is_empty(),
1814        }
1815    }
1816
1817    /// Get memory usage in bytes (approximate)
1818    pub fn memory_usage(&self) -> usize {
1819        match &self.storage {
1820            KVStorage::FullPrecision { keys, values } => {
1821                let mut total = 0;
1822                if let Some(k) = keys {
1823                    total += k.numel() * dtype_element_size(k.kind());
1824                }
1825                if let Some(v) = values {
1826                    total += v.numel() * dtype_element_size(v.kind());
1827                }
1828                total
1829            }
1830            #[cfg(feature = "bnb")]
1831            KVStorage::Quantized {
1832                keys_quantized,
1833                values_quantized,
1834                keys_buffer,
1835                values_buffer,
1836                buffer_len,
1837                ..
1838            } => {
1839                let mut total = 0;
1840
1841                // Quantized storage
1842                if let Some(kq) = keys_quantized {
1843                    total += kq.memory_usage();
1844                }
1845                if let Some(vq) = values_quantized {
1846                    total += vq.memory_usage();
1847                }
1848
1849                // Buffer (only count used portion)
1850                if let Some(kb) = keys_buffer {
1851                    if *buffer_len > 0 {
1852                        let shape = kb.size();
1853                        let per_token = shape[0] * shape[2] * shape[3];
1854                        total += (*buffer_len as i64 * per_token) as usize
1855                            * dtype_element_size(kb.kind());
1856                    }
1857                }
1858                if let Some(vb) = values_buffer {
1859                    if *buffer_len > 0 {
1860                        let shape = vb.size();
1861                        let per_token = shape[0] * shape[2] * shape[3];
1862                        total += (*buffer_len as i64 * per_token) as usize
1863                            * dtype_element_size(vb.kind());
1864                    }
1865                }
1866
1867                // Note: dequant cache is temporary and not counted
1868                total
1869            }
1870            KVStorage::Paged {
1871                key_blocks, pool, ..
1872            } => {
1873                // Count blocks owned by this layer (K + V)
1874                let pool_guard = pool.lock();
1875                let elem_size = match pool_guard.dtype() {
1876                    DType::Half | DType::BFloat16 => 2,
1877                    _ => 4,
1878                };
1879                let shape = pool_guard.block_shape();
1880                let per_block = BLOCK_SIZE * shape[2] as usize * shape[3] as usize * elem_size;
1881                key_blocks.len() * 2 * per_block // K + V blocks
1882            }
1883        }
1884    }
1885
1886    /// Move tensors to a different device (for CPU offload/restore).
1887    ///
1888    /// For FullPrecision: moves K/V tensors via `Tensor::to_device()`.
1889    /// For Paged: no-op (blocks are managed by the pool).
1890    /// For Quantized: no-op (quantized data is already on CPU).
1891    pub fn to_device(&mut self, device: tch::Device) {
1892        match &mut self.storage {
1893            KVStorage::FullPrecision { keys, values } => {
1894                if let Some(k) = keys {
1895                    *k = k.to_device(device);
1896                }
1897                if let Some(v) = values {
1898                    *v = v.to_device(device);
1899                }
1900            }
1901            #[cfg(feature = "bnb")]
1902            KVStorage::Quantized { .. } => {
1903                // Quantized data lives on CPU already; dequant cache will be
1904                // regenerated on next get(). No action needed.
1905            }
1906            KVStorage::Paged { .. } => {
1907                // Paged blocks are managed by the pool. Offloading individual
1908                // layers is not supported — use block pool eviction instead.
1909            }
1910        }
1911    }
1912
1913    /// Get the quantization type
1914    pub fn quant_type(&self) -> KVQuantType {
1915        self.quant_type
1916    }
1917}
1918
1919// Backwards compatibility: expose keys/values for code that accesses them directly
1920impl LayerKVCache {
1921    /// Get keys tensor (only for full precision mode)
1922    pub fn keys(&self) -> Option<&Tensor> {
1923        match &self.storage {
1924            KVStorage::FullPrecision { keys, .. } => keys.as_ref(),
1925            #[cfg(feature = "bnb")]
1926            KVStorage::Quantized { .. } => None,
1927            KVStorage::Paged { .. } => None, // Use get() for paged mode
1928        }
1929    }
1930
1931    /// Get values tensor (only for full precision mode)
1932    pub fn values(&self) -> Option<&Tensor> {
1933        match &self.storage {
1934            KVStorage::FullPrecision { values, .. } => values.as_ref(),
1935            #[cfg(feature = "bnb")]
1936            KVStorage::Quantized { .. } => None,
1937            KVStorage::Paged { .. } => None, // Use get() for paged mode
1938        }
1939    }
1940}
1941
1942impl Drop for LayerKVCache {
1943    /// Return paged blocks to the shared pool when the cache is dropped.
1944    ///
1945    /// Without this, registry eviction (`caches.remove`) would drop paged caches
1946    /// without returning their blocks, leaking pool capacity until restart.
1947    /// Non-paged storage owns its own tensors and needs no special handling.
1948    fn drop(&mut self) {
1949        self.release_paged_blocks();
1950    }
1951}
1952
1953/// Get current timestamp in milliseconds since UNIX_EPOCH
1954fn current_timestamp_ms() -> u64 {
1955    SystemTime::now()
1956        .duration_since(UNIX_EPOCH)
1957        .map(|d| d.as_millis() as u64)
1958        .unwrap_or(0)
1959}
1960
1961/// Where a KV cache's tensors are currently stored.
1962#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1963pub enum CacheLocation {
1964    /// Tensors are on GPU (active, ready for inference)
1965    Gpu,
1966    /// Tensors have been offloaded to CPU RAM (idle, must restore before use)
1967    Cpu,
1968}
1969
1970/// KV cache manager for all layers in a model
1971pub struct KVCacheManager {
1972    /// Backend and tenant ownership retained for lazily added auxiliary layers.
1973    paged_backend: Option<(Arc<Mutex<BlockPool>>, CacheOwner)>,
1974    /// Cache for each layer (lock-free concurrent access)
1975    layer_caches: DashMap<usize, LayerKVCache>,
1976    /// Maximum sequence length
1977    max_seq_len: usize,
1978    /// Whether caching is enabled
1979    enabled: bool,
1980    /// Quantization type
1981    quant_type: KVQuantType,
1982    /// Last access timestamp in milliseconds (for LRU eviction)
1983    last_access_ms: AtomicU64,
1984    /// Access count (for metrics)
1985    access_count: AtomicU64,
1986    /// Token IDs this cache was computed for (for prefix matching across turns)
1987    cached_token_ids: Vec<i64>,
1988    /// Recurrent-state (SSM conv/rec) snapshot for hybrid models (Qwen3.5 GDN),
1989    /// captured at the end of the prefill that produced `cached_token_ids`.
1990    ///
1991    /// Unlike KV, recurrent state is Markovian and cannot be truncated to an
1992    /// arbitrary prefix position — a prefix hit is only exact when the FULL
1993    /// cached token sequence matched and this snapshot is restored alongside
1994    /// the KV truncation. One snapshot per cache, overwritten each turn;
1995    /// `None` for pure-attention models. Tensors are deep copies, independent
1996    /// of subsequent forward-pass mutations of the live model state.
1997    ssm_snapshot: Option<(Vec<Option<Tensor>>, Vec<Option<Tensor>>)>,
1998    /// Owning device per snapshot slot (per layer, index-aligned with the
1999    /// conv/rec lists), recorded from the slots' own tensors when the
2000    /// snapshot is stored. A CPU-offloaded cache restores each slot to this
2001    /// device instead of `restore_to_gpu`'s single argument: under a multi-GPU
2002    /// `LayerDeviceMap` the recurrent state belongs to its layer's device,
2003    /// and moving every slot to one device (normally CUDA 0) makes the next
2004    /// GDN forward fail on a device mismatch. Layers without slots record the
2005    /// CPU fallback; a snapshot-less cache records nothing.
2006    ssm_slot_devices: Vec<tch::Device>,
2007    /// Where this cache's tensors currently reside
2008    location: CacheLocation,
2009    /// Compatibility fingerprint under which this cache's KV was produced
2010    /// (#1277). `None` until the cache is first populated; the engine stamps it
2011    /// at reuse time and rejects (clears + recomputes) on mismatch against the
2012    /// current expected fingerprint.
2013    compat_fingerprint: Option<KvCompatFingerprint>,
2014}
2015
2016impl KVCacheManager {
2017    /// Create a new KV cache manager
2018    pub fn new(num_layers: usize, max_seq_len: usize, quant_type: KVQuantType) -> Self {
2019        tracing::info!(
2020            "[KVCacheManager::new] Creating cache for {} layers, max_seq_len={}, quant={:?}",
2021            num_layers,
2022            max_seq_len,
2023            quant_type
2024        );
2025
2026        let layer_caches = DashMap::new();
2027        for layer_idx in 0..num_layers {
2028            layer_caches.insert(layer_idx, LayerKVCache::new(max_seq_len, quant_type));
2029        }
2030
2031        Self {
2032            layer_caches,
2033            max_seq_len,
2034            enabled: true,
2035            quant_type,
2036            paged_backend: None,
2037            last_access_ms: AtomicU64::new(current_timestamp_ms()),
2038            access_count: AtomicU64::new(0),
2039            cached_token_ids: Vec::new(),
2040            ssm_snapshot: None,
2041            ssm_slot_devices: Vec::new(),
2042            location: CacheLocation::Gpu,
2043            compat_fingerprint: None,
2044        }
2045    }
2046
2047    /// Create a new KV cache manager using paged block storage.
2048    ///
2049    /// All layers share the same `BlockPool` for zero-fragmentation memory management.
2050    pub fn new_paged(
2051        num_layers: usize,
2052        max_seq_len: usize,
2053        pool: Arc<Mutex<BlockPool>>,
2054        owner: CacheOwner,
2055    ) -> Self {
2056        tracing::info!(
2057            "[KVCacheManager::new_paged] Creating paged cache for {} layers, max_seq_len={}, owner={:?}",
2058            num_layers, max_seq_len, owner,
2059        );
2060
2061        let layer_caches = DashMap::new();
2062        for layer_idx in 0..num_layers {
2063            layer_caches.insert(
2064                layer_idx,
2065                LayerKVCache::new_paged(max_seq_len, pool.clone(), owner.clone()),
2066            );
2067        }
2068
2069        Self {
2070            layer_caches,
2071            max_seq_len,
2072            enabled: true,
2073            quant_type: KVQuantType::None,
2074            paged_backend: Some((pool, owner)),
2075            last_access_ms: AtomicU64::new(current_timestamp_ms()),
2076            access_count: AtomicU64::new(0),
2077            cached_token_ids: Vec::new(),
2078            ssm_snapshot: None,
2079            ssm_slot_devices: Vec::new(),
2080            location: CacheLocation::Gpu,
2081            compat_fingerprint: None,
2082        }
2083    }
2084
2085    /// Get cache for a specific layer with a closure
2086    pub fn with_layer_cache<F, R>(&self, layer_idx: usize, f: F) -> Option<R>
2087    where
2088        F: FnOnce(&mut LayerKVCache) -> R,
2089    {
2090        if !self.enabled {
2091            return None;
2092        }
2093        self.layer_caches
2094            .get_mut(&layer_idx)
2095            .map(|mut cache_ref| f(&mut cache_ref))
2096    }
2097
2098    /// Borrow a layer's cache directly as a `RefMut` (for the batched decode path,
2099    /// which needs to hold one mutable layer-cache borrow per sequence across a
2100    /// batched attention call). Each sequence has its own manager, so the borrows
2101    /// never alias. Returns `None` when caching is disabled or the layer is absent.
2102    pub fn layer_cache_ref(
2103        &self,
2104        layer_idx: usize,
2105    ) -> Option<dashmap::mapref::one::RefMut<'_, usize, LayerKVCache>> {
2106        if !self.enabled {
2107            return None;
2108        }
2109        self.layer_caches.get_mut(&layer_idx)
2110    }
2111
2112    /// Check if a layer cache exists (for testing)
2113    #[cfg(test)]
2114    #[allow(clippy::expect_used, clippy::unwrap_used, clippy::print_stdout)]
2115    fn get_layer_cache(&self, layer_idx: usize) -> Option<()> {
2116        if !self.enabled {
2117            return None;
2118        }
2119        self.layer_caches.contains_key(&layer_idx).then_some(())
2120    }
2121
2122    /// Clear all KV tensors together with the metadata that describes them.
2123    ///
2124    /// `cached_token_ids`, the SSM snapshot, and its slot-device record only
2125    /// have meaning alongside the layer tensors they were computed with. A
2126    /// cleared cache that retained them would let a later extending prompt
2127    /// claim a `prefix_len` — or restore a stale snapshot — against KV that
2128    /// no longer exists (e.g. a session turn cancelled before its first
2129    /// prefill: the set-up clear runs at generation setup, and the drop
2130    /// records nothing new).
2131    pub fn clear_all(&mut self) {
2132        self.cached_token_ids = Vec::new();
2133        self.ssm_snapshot = None;
2134        self.ssm_slot_devices = Vec::new();
2135        for mut cache_ref in self.layer_caches.iter_mut() {
2136            cache_ref.clear();
2137        }
2138    }
2139
2140    /// Insert a fresh cache for `layer_idx` if none exists yet.
2141    ///
2142    /// Architectures with auxiliary KV-consuming modules beyond the main
2143    /// decoder layers (the Qwen3.5 MTP draft head, whose slot sits at index
2144    /// `num_hidden_layers`) call this when a session cache is swapped in: the
2145    /// registry may have created the manager with only the main layer count.
2146    pub fn ensure_layer_cache(&self, layer_idx: usize) {
2147        self.layer_caches
2148            .entry(layer_idx)
2149            .or_insert_with(|| match &self.paged_backend {
2150                Some((pool, owner)) => {
2151                    LayerKVCache::new_paged(self.max_seq_len, Arc::clone(pool), owner.clone())
2152                }
2153                None => LayerKVCache::new(self.max_seq_len, self.quant_type),
2154            });
2155    }
2156
2157    /// Maximum sequence length every layer cache is bounded by
2158    /// (`LayerKVCache::update` errors past it).
2159    pub fn max_seq_len(&self) -> usize {
2160        self.max_seq_len
2161    }
2162
2163    /// The compatibility fingerprint stamped on this cache, or `None` until the
2164    /// cache is first populated (#1277).
2165    pub fn compat_fingerprint(&self) -> Option<KvCompatFingerprint> {
2166        self.compat_fingerprint
2167    }
2168
2169    /// Stamp (or re-stamp) the compatibility fingerprint under which this
2170    /// cache's KV is being produced. Called by the engine at reuse time: a fresh
2171    /// cache is stamped with the current config; an incompatible cache is
2172    /// cleared and re-stamped after its stale KV is discarded.
2173    pub fn set_compat_fingerprint(&mut self, fp: KvCompatFingerprint) {
2174        self.compat_fingerprint = Some(fp);
2175    }
2176
2177    /// Apply the fail-closed KV compatibility policy to this real cache.
2178    ///
2179    /// This is the production state-transition boundary for #1277. A compatible
2180    /// stamped cache is retained. A fresh empty cache is stamped before prefill.
2181    /// Every incompatible or unproven cache has both its token IDs and layer
2182    /// tensors discarded, then is re-stamped only when an authoritative expected
2183    /// fingerprint is available.
2184    pub fn apply_reuse_policy(
2185        &mut self,
2186        expected: Option<KvCompatFingerprint>,
2187    ) -> CacheReuseDecision {
2188        let stored = self.compat_fingerprint();
2189        let cache_is_empty = self.cached_token_count() == 0;
2190        let decision = decide_cache_reuse(expected.as_ref(), stored.as_ref(), cache_is_empty);
2191
2192        match decision {
2193            CacheReuseDecision::Reuse => {
2194                tracing::debug!(target: "kv_compat", "KV cache reuse: compatible");
2195            }
2196            CacheReuseDecision::StampFresh => {
2197                if let Some(expected) = expected {
2198                    self.set_compat_fingerprint(expected);
2199                }
2200            }
2201            CacheReuseDecision::DiscardAndRecompute => {
2202                let reason = match stored {
2203                    Some(stored) => format!(
2204                        "stamp mismatch (stored={}, expected={})",
2205                        stored.to_hex(),
2206                        expected
2207                            .map(|fingerprint| fingerprint.to_hex())
2208                            .unwrap_or_else(|| "<none>".to_owned())
2209                    ),
2210                    None if !cache_is_empty => {
2211                        "populated cache with no compatibility stamp".to_owned()
2212                    }
2213                    None => "no authoritative compatibility identity".to_owned(),
2214                };
2215                tracing::info!(
2216                    target: "kv_compat",
2217                    reason = %reason,
2218                    "KV cache not reusable: discarding and recomputing (fail-closed)"
2219                );
2220
2221                self.set_cached_tokens(Vec::new());
2222                self.clear_all();
2223                if let Some(expected) = expected {
2224                    self.set_compat_fingerprint(expected);
2225                }
2226            }
2227        }
2228
2229        decision
2230    }
2231
2232    /// Enable or disable caching
2233    pub fn set_enabled(&mut self, enabled: bool) {
2234        self.enabled = enabled;
2235        if !enabled {
2236            self.clear_all();
2237        }
2238    }
2239
2240    /// Get total memory usage in bytes (approximate)
2241    pub fn memory_usage(&self) -> usize {
2242        if !self.enabled {
2243            return 0;
2244        }
2245
2246        // Include the SSM snapshot (Qwen3.5 GDN conv/rec state): it holds
2247        // device tensors and must count toward the eviction budget, or
2248        // `evict_to_budget` undercounts and skips offloading.
2249        let ssm_bytes: usize = self
2250            .ssm_snapshot
2251            .as_ref()
2252            .map(|(conv, rec)| {
2253                conv.iter()
2254                    .chain(rec.iter())
2255                    .flatten()
2256                    .map(|t| t.numel() * dtype_element_size(t.kind()))
2257                    .sum()
2258            })
2259            .unwrap_or(0);
2260
2261        self.layer_caches
2262            .iter()
2263            .map(|c| c.memory_usage())
2264            .sum::<usize>()
2265            + ssm_bytes
2266    }
2267
2268    /// Get the quantization type
2269    pub fn quant_type(&self) -> KVQuantType {
2270        self.quant_type
2271    }
2272
2273    /// Update last access timestamp (for LRU eviction)
2274    pub fn touch(&self) {
2275        self.last_access_ms
2276            .store(current_timestamp_ms(), Ordering::Relaxed);
2277        self.access_count.fetch_add(1, Ordering::Relaxed);
2278    }
2279
2280    /// Get last access timestamp in milliseconds
2281    pub fn last_access(&self) -> u64 {
2282        self.last_access_ms.load(Ordering::Relaxed)
2283    }
2284
2285    /// Get access count
2286    pub fn access_count(&self) -> u64 {
2287        self.access_count.load(Ordering::Relaxed)
2288    }
2289
2290    /// Find the length of the common prefix between cached tokens and new tokens.
2291    ///
2292    /// Returns the number of tokens whose KV values can be reused from the cache.
2293    /// A return value of 0 means no prefix match (full recomputation needed).
2294    pub fn prefix_match_len(&self, new_tokens: &[i64]) -> usize {
2295        self.cached_token_ids
2296            .iter()
2297            .zip(new_tokens.iter())
2298            .take_while(|(a, b)| a == b)
2299            .count()
2300    }
2301
2302    /// Record which tokens this cache was computed for.
2303    ///
2304    /// Called after generation completes so the next turn can detect prefix overlap.
2305    /// Any prior SSM snapshot is dropped: tokens recorded without a known
2306    /// recurrent state must not resurrect a stale one.
2307    pub fn set_cached_tokens(&mut self, tokens: Vec<i64>) {
2308        self.set_cached_tokens_with_ssm(tokens, None);
2309    }
2310
2311    /// Record which tokens this cache was computed for, together with the
2312    /// recurrent-state (SSM conv/rec) snapshot as of the end of the prefill
2313    /// that produced them (hybrid models only; `None` for pure attention).
2314    ///
2315    /// The snapshot is what makes a later prefix hit rewindable for recurrent
2316    /// layers: KV truncates to the matched prefix, the snapshot restores the
2317    /// GDN conv/rec state to the end of the cached sequence.
2318    pub fn set_cached_tokens_with_ssm(
2319        &mut self,
2320        tokens: Vec<i64>,
2321        ssm_snapshot: Option<(Vec<Option<Tensor>>, Vec<Option<Tensor>>)>,
2322    ) {
2323        self.cached_token_ids = tokens;
2324        // Record each slot's owning device from its own tensor: the snapshot
2325        // is what a later CPU-offload/restore round trip must reproduce
2326        // device-wise (per-layer under a multi-GPU LayerDeviceMap). Layers
2327        // with no slots record the CPU fallback (irrelevant — nothing to
2328        // move); a snapshot-less recording clears the devices with it.
2329        self.ssm_slot_devices = match &ssm_snapshot {
2330            Some((conv, rec)) => conv
2331                .iter()
2332                .zip(rec.iter())
2333                .map(|(c, r)| {
2334                    c.as_ref()
2335                        .or(r.as_ref())
2336                        .map(Tensor::device)
2337                        .unwrap_or(tch::Device::Cpu)
2338                })
2339                .collect(),
2340            None => Vec::new(),
2341        };
2342        self.ssm_snapshot = ssm_snapshot;
2343    }
2344
2345    /// Deep-copied SSM snapshot for restore on a prefix hit.
2346    ///
2347    /// Returns deep copies (same `.copy()` discipline as
2348    /// `Qwen3_5Model::snapshot_ssm_states`) so that restoring into the live
2349    /// model state never aliases — and cannot mutate — the stored snapshot.
2350    pub fn ssm_snapshot(&self) -> Option<(Vec<Option<Tensor>>, Vec<Option<Tensor>>)> {
2351        self.ssm_snapshot.as_ref().map(|(conv, rec)| {
2352            (
2353                conv.iter()
2354                    .map(|opt| opt.as_ref().map(Tensor::copy))
2355                    .collect(),
2356                rec.iter()
2357                    .map(|opt| opt.as_ref().map(Tensor::copy))
2358                    .collect(),
2359            )
2360        })
2361    }
2362
2363    /// Get the cached token IDs (for debugging/metrics).
2364    pub fn cached_token_count(&self) -> usize {
2365        self.cached_token_ids.len()
2366    }
2367
2368    /// Truncate the cache to a given token position.
2369    ///
2370    /// Keeps KV values for tokens 0..pos and discards everything after.
2371    /// Used when a prefix matches but the suffix has changed (new turn).
2372    pub fn truncate_to(&self, pos: usize) {
2373        for mut cache_ref in self.layer_caches.iter_mut() {
2374            cache_ref.truncate_to(pos);
2375        }
2376    }
2377
2378    /// Current storage location of this cache's tensors.
2379    pub fn location(&self) -> CacheLocation {
2380        self.location
2381    }
2382
2383    /// Offload all layer caches from GPU to CPU RAM.
2384    ///
2385    /// Frees GPU memory while preserving the cached data for later restore.
2386    /// Only works for FullPrecision storage — Paged caches free blocks to the
2387    /// pool instead (handled by evict_to_budget), and Quantized data is already
2388    /// partially on CPU.
2389    pub fn offload_to_cpu(&mut self) {
2390        if self.location == CacheLocation::Cpu {
2391            return; // Already offloaded
2392        }
2393        for mut cache_ref in self.layer_caches.iter_mut() {
2394            cache_ref.to_device(tch::Device::Cpu);
2395        }
2396        // Carry the SSM snapshot with the cache so a later restore + prefix
2397        // hit still finds matching-device state.
2398        if let Some((conv, rec)) = &mut self.ssm_snapshot {
2399            for t in conv.iter_mut().chain(rec.iter_mut()).flatten() {
2400                *t = t.to_device(tch::Device::Cpu);
2401            }
2402        }
2403        self.location = CacheLocation::Cpu;
2404        tracing::debug!(
2405            "Offloaded KV cache to CPU ({} tokens, {} layers)",
2406            self.cached_token_ids.len(),
2407            self.layer_caches.len()
2408        );
2409    }
2410
2411    /// Restore all layer caches from CPU back to GPU.
2412    ///
2413    /// Must be called before using the cache for inference.
2414    pub fn restore_to_gpu(&mut self, device: tch::Device) {
2415        if self.location == CacheLocation::Gpu {
2416            return; // Already on GPU
2417        }
2418        for mut cache_ref in self.layer_caches.iter_mut() {
2419            cache_ref.to_device(device);
2420        }
2421        if let Some((conv, rec)) = &mut self.ssm_snapshot {
2422            // Each slot returns to its recorded owning device (its layer's
2423            // device under a multi-GPU LayerDeviceMap), falling back to the
2424            // argument only when a snapshot predates recording. Restoring
2425            // every slot to one device would leave states on the wrong side
2426            // of a device boundary and break the next GDN forward.
2427            let slot_devices = self.ssm_slot_devices.clone();
2428            let restore_slot = |t: &mut Option<Tensor>, i: usize| {
2429                if let Some(t) = t {
2430                    let dst = slot_devices.get(i).copied().unwrap_or(device);
2431                    *t = t.to_device(dst);
2432                }
2433            };
2434            for (i, t) in conv.iter_mut().enumerate() {
2435                restore_slot(t, i);
2436            }
2437            for (i, t) in rec.iter_mut().enumerate() {
2438                restore_slot(t, i);
2439            }
2440        }
2441        self.location = CacheLocation::Gpu;
2442        tracing::debug!(
2443            "Restored KV cache to GPU ({} tokens, {} layers)",
2444            self.cached_token_ids.len(),
2445            self.layer_caches.len()
2446        );
2447    }
2448}
2449
2450#[cfg(test)]
2451#[allow(clippy::expect_used, clippy::unwrap_used, clippy::print_stdout)]
2452mod tests {
2453    use super::*;
2454
2455    #[test]
2456    fn test_layer_kv_cache_unquantized() -> Result<()> {
2457        let device = Device::Cpu;
2458        let dtype = DType::Float;
2459
2460        let mut cache = LayerKVCache::new(100, KVQuantType::None);
2461
2462        let batch_size = 2;
2463        let seq_len = 10;
2464        let num_heads = 8;
2465        let head_dim = 64;
2466
2467        let keys = Tensor::randn(
2468            [batch_size, seq_len as i64, num_heads, head_dim],
2469            (dtype, device),
2470        );
2471        let values = Tensor::randn(
2472            [batch_size, seq_len as i64, num_heads, head_dim],
2473            (dtype, device),
2474        );
2475
2476        cache.update(&keys, &values, 0)?;
2477        assert_eq!(cache.seq_pos, 10);
2478
2479        let (cached_keys, cached_values) = cache.get()?;
2480        assert_eq!(
2481            cached_keys.size(),
2482            vec![batch_size, 10, num_heads, head_dim]
2483        );
2484        assert_eq!(
2485            cached_values.size(),
2486            vec![batch_size, 10, num_heads, head_dim]
2487        );
2488
2489        Ok(())
2490    }
2491
2492    #[test]
2493    #[cfg(feature = "bnb")]
2494    fn test_layer_kv_cache_quantized_int8() -> Result<()> {
2495        // Skip if bitsandbytes library is not available (stub mode)
2496        if !bitsandbytes_sys::is_available() {
2497            eprintln!("Skipping quantized test: bitsandbytes library not available");
2498            return Ok(());
2499        }
2500
2501        let device = Device::Cpu;
2502        let dtype = DType::Float;
2503
2504        let mut cache = LayerKVCache::new(1000, KVQuantType::Int8);
2505
2506        let batch_size: i64 = 1;
2507        let seq_len: i64 = 100; // Large enough to trigger flush
2508        let num_heads: i64 = 2;
2509        let head_dim: i64 = 64;
2510
2511        let keys = Tensor::randn([batch_size, seq_len, num_heads, head_dim], (dtype, device));
2512        let values = Tensor::randn([batch_size, seq_len, num_heads, head_dim], (dtype, device));
2513
2514        // Initial prompt
2515        cache.update(&keys, &values, 0)?;
2516        assert_eq!(cache.seq_pos, seq_len as usize);
2517
2518        // Get should work
2519        let (cached_keys, cached_values) = cache.get()?;
2520        assert_eq!(
2521            cached_keys.size(),
2522            vec![batch_size, seq_len, num_heads, head_dim]
2523        );
2524        assert_eq!(
2525            cached_values.size(),
2526            vec![batch_size, seq_len, num_heads, head_dim]
2527        );
2528
2529        // Second get should use cache
2530        let (cached_keys2, _) = cache.get()?;
2531        assert_eq!(cached_keys2.size(), cached_keys.size());
2532
2533        // Add more tokens
2534        let new_keys = Tensor::randn([batch_size, 1, num_heads, head_dim], (dtype, device));
2535        let new_values = Tensor::randn([batch_size, 1, num_heads, head_dim], (dtype, device));
2536        cache.update(&new_keys, &new_values, seq_len as usize)?;
2537
2538        let (final_keys, _) = cache.get()?;
2539        assert_eq!(
2540            final_keys.size(),
2541            vec![batch_size, seq_len + 1, num_heads, head_dim]
2542        );
2543
2544        Ok(())
2545    }
2546
2547    #[test]
2548    fn test_kv_cache_manager() {
2549        let num_layers = 32;
2550        let max_seq_len = 2048;
2551
2552        let mut manager = KVCacheManager::new(num_layers, max_seq_len, KVQuantType::None);
2553
2554        for layer_idx in 0..num_layers {
2555            assert!(manager.get_layer_cache(layer_idx).is_some());
2556        }
2557
2558        manager.set_enabled(false);
2559        assert!(manager.get_layer_cache(0).is_none());
2560
2561        manager.set_enabled(true);
2562        assert!(manager.get_layer_cache(0).is_some());
2563    }
2564
2565    #[test]
2566    fn test_kv_cache_manager_quantized() {
2567        let num_layers = 4;
2568        let max_seq_len = 512;
2569
2570        let manager = KVCacheManager::new(num_layers, max_seq_len, KVQuantType::Nf4);
2571
2572        assert_eq!(manager.quant_type(), KVQuantType::Nf4);
2573    }
2574
2575    /// The SSM snapshot (Qwen3.5 GDN conv/rec state) holds device tensors and
2576    /// must count toward the eviction budget: `memory_usage` grows when a
2577    /// snapshot is recorded and shrinks back when it is dropped.
2578    #[test]
2579    fn test_memory_usage_includes_ssm_snapshot() {
2580        let mut manager = KVCacheManager::new(2, 100, KVQuantType::None);
2581        let baseline = manager.memory_usage();
2582
2583        let opt = (DType::Float, Device::Cpu);
2584        let conv = vec![Some(Tensor::zeros([2, 3], opt)), None];
2585        let rec = vec![Some(Tensor::zeros([4], opt)), None];
2586        let expected = (2 * 3 + 4) * dtype_element_size(DType::Float);
2587
2588        manager.set_cached_tokens_with_ssm(vec![1, 2, 3], Some((conv, rec)));
2589        assert_eq!(manager.memory_usage(), baseline + expected);
2590
2591        // Recording tokens without a snapshot drops it (no stale state) and
2592        // the budget accounting shrinks back.
2593        manager.set_cached_tokens(vec![1, 2, 3, 4]);
2594        assert_eq!(manager.memory_usage(), baseline);
2595    }
2596
2597    /// Storing an SSM snapshot must record each slot's owning device from its
2598    /// own tensor — the record a later CPU-offload/restore round trip uses to
2599    /// put slots back on their layer devices (multi-GPU LayerDeviceMap).
2600    /// Token-only recording drops the snapshot and its device record with it.
2601    #[test]
2602    fn test_ssm_snapshot_records_owning_devices() {
2603        let mut manager = KVCacheManager::new(2, 100, KVQuantType::None);
2604        assert!(
2605            manager.ssm_slot_devices.is_empty(),
2606            "fresh cache records nothing"
2607        );
2608
2609        let opt = (DType::Float, Device::Cpu);
2610        let conv = vec![Some(Tensor::zeros([2, 3], opt)), None];
2611        let rec = vec![Some(Tensor::zeros([4], opt)), None];
2612        manager.set_cached_tokens_with_ssm(vec![1, 2], Some((conv, rec)));
2613        // One record per layer; layers without slots record the fallback.
2614        assert_eq!(manager.ssm_slot_devices.len(), 2);
2615        assert_eq!(manager.ssm_slot_devices, vec![Device::Cpu, Device::Cpu]);
2616
2617        // Token-only recording clears the device record with the snapshot.
2618        manager.set_cached_tokens(vec![3]);
2619        assert!(manager.ssm_slot_devices.is_empty());
2620    }
2621
2622    /// Restore must send each SSM snapshot slot back to its recorded owning
2623    /// device — NOT `restore_to_gpu`'s single argument. Mixed Cuda(0)/Cpu
2624    /// owning devices reproduce the multi-GPU LayerDeviceMap hazard: the
2625    /// registry restores an offloaded cache with one device (normally CUDA 0),
2626    /// and moving every slot there leaves layer-1 recurrent state on the wrong
2627    /// device for the next GDN forward. Gated on a CUDA build (a CPU-only host
2628    /// has no second device to discriminate).
2629    #[test]
2630    fn test_restore_moves_snapshot_slots_to_owning_devices() {
2631        let cuda = Device::cuda_if_available();
2632        if cuda == Device::Cpu {
2633            // No CUDA on this host: single-device restore is trivially
2634            // correct, and the mixed-device fixture cannot be constructed.
2635            return;
2636        }
2637
2638        let mut manager = KVCacheManager::new(2, 100, KVQuantType::None);
2639        // Layer 0 owns CUDA state, layer 1 owns CPU state (as a pipeline
2640        // split places each layer's stage-local state on its own device).
2641        let conv = vec![
2642            Some(Tensor::ones([2, 3], (DType::Float, cuda)) * 7.0),
2643            Some(Tensor::ones([2, 3], (DType::Float, Device::Cpu)) * 9.0),
2644        ];
2645        let rec = vec![
2646            Some(Tensor::ones([4], (DType::Float, cuda)) * 11.0),
2647            Some(Tensor::ones([4], (DType::Float, Device::Cpu)) * 13.0),
2648        ];
2649        manager.set_cached_tokens_with_ssm(vec![1, 2, 3], Some((conv, rec)));
2650
2651        manager.offload_to_cpu();
2652        // The registry's single-device restore call (`cuda_if_available`,
2653        // normally CUDA 0) — the exact pre-fix call shape.
2654        manager.restore_to_gpu(cuda);
2655
2656        let (conv_restored, rec_restored) = manager.ssm_snapshot().unwrap();
2657        for (layer, expected) in [(0usize, cuda), (1, Device::Cpu)] {
2658            if let Some(c) = &conv_restored[layer] {
2659                assert_eq!(
2660                    c.device(),
2661                    expected,
2662                    "conv slot {layer} must return to its owning device"
2663                );
2664            }
2665            if let Some(r) = &rec_restored[layer] {
2666                assert_eq!(
2667                    r.device(),
2668                    expected,
2669                    "rec slot {layer} must return to its owning device"
2670                );
2671            }
2672        }
2673        // Values survived the offload/restore round trip.
2674        assert_eq!(
2675            conv_restored[0].as_ref().unwrap().double_value(&[1, 2]),
2676            7.0
2677        );
2678        assert_eq!(
2679            conv_restored[1].as_ref().unwrap().double_value(&[1, 2]),
2680            9.0
2681        );
2682        assert_eq!(rec_restored[0].as_ref().unwrap().double_value(&[3]), 11.0);
2683        assert_eq!(rec_restored[1].as_ref().unwrap().double_value(&[3]), 13.0);
2684    }
2685
2686    /// `clear_all` must drop the cached token IDs, the SSM snapshot, and its
2687    /// slot-device record together with the layer tensors: metadata that
2688    /// survives a tensor clear lets a later extending prompt claim a prefix
2689    /// — or restore a stale snapshot — against KV that no longer exists
2690    /// (set-up clear on an exact hit/miss, then cancellation before the
2691    /// first poll leaves nothing to re-record over it).
2692    #[test]
2693    fn clear_all_drops_cached_token_and_ssm_metadata() {
2694        let mut manager = KVCacheManager::new(2, 100, KVQuantType::None);
2695        let opt = (DType::Float, Device::Cpu);
2696        let conv = vec![Some(Tensor::zeros([2, 3], opt)), None];
2697        let rec = vec![Some(Tensor::zeros([4], opt)), None];
2698        manager.set_cached_tokens_with_ssm(vec![9, 9, 9], Some((conv, rec)));
2699        assert_eq!(manager.cached_token_count(), 3);
2700        assert!(manager.ssm_snapshot().is_some());
2701
2702        manager.clear_all();
2703
2704        assert_eq!(
2705            manager.cached_token_count(),
2706            0,
2707            "token IDs must go with the tensors"
2708        );
2709        assert!(
2710            manager.ssm_snapshot().is_none(),
2711            "stale snapshot must not survive a clear"
2712        );
2713        assert!(
2714            manager.ssm_slot_devices.is_empty(),
2715            "slot-device record must go with the snapshot"
2716        );
2717        assert_eq!(
2718            manager.prefix_match_len(&[9, 9, 9, 4]),
2719            0,
2720            "an extending prompt must not claim a prefix over cleared KV"
2721        );
2722    }
2723
2724    #[test]
2725    fn test_prefix_match_len() {
2726        let mut manager = KVCacheManager::new(2, 100, KVQuantType::None);
2727
2728        // No cached tokens — no match
2729        assert_eq!(manager.prefix_match_len(&[1, 2, 3]), 0);
2730
2731        // Set cached tokens
2732        manager.set_cached_tokens(vec![1, 2, 3, 4, 5]);
2733
2734        // Full prefix match
2735        assert_eq!(manager.prefix_match_len(&[1, 2, 3, 4, 5, 6, 7]), 5);
2736
2737        // Partial prefix match
2738        assert_eq!(manager.prefix_match_len(&[1, 2, 3, 99, 100]), 3);
2739
2740        // No match (different first token)
2741        assert_eq!(manager.prefix_match_len(&[99, 2, 3]), 0);
2742
2743        // Exact match (entire prompt is cached)
2744        assert_eq!(manager.prefix_match_len(&[1, 2, 3, 4, 5]), 5);
2745
2746        // Empty input
2747        assert_eq!(manager.prefix_match_len(&[]), 0);
2748    }
2749
2750    #[test]
2751    fn test_truncate_to_full_precision() -> Result<()> {
2752        let device = Device::Cpu;
2753        let dtype = DType::Float;
2754        let mut cache = LayerKVCache::new(100, KVQuantType::None);
2755
2756        let batch_size = 1;
2757        let num_heads = 4;
2758        let head_dim = 8;
2759
2760        // Write 10 tokens
2761        let keys = Tensor::ones([batch_size, 10, num_heads, head_dim], (dtype, device));
2762        let values = Tensor::ones([batch_size, 10, num_heads, head_dim], (dtype, device)) * 2.0;
2763        cache.update(&keys, &values, 0)?;
2764        assert_eq!(cache.seq_pos, 10);
2765
2766        // Truncate to 5
2767        cache.truncate_to(5);
2768        assert_eq!(cache.seq_pos, 5);
2769
2770        // get() should return only 5 tokens
2771        let (k, v) = cache.get()?;
2772        assert_eq!(k.size()[1], 5);
2773        assert_eq!(v.size()[1], 5);
2774
2775        // Writing new tokens at position 5 should work
2776        let new_keys = Tensor::ones([batch_size, 3, num_heads, head_dim], (dtype, device)) * 3.0;
2777        let new_values = Tensor::ones([batch_size, 3, num_heads, head_dim], (dtype, device)) * 4.0;
2778        cache.update(&new_keys, &new_values, 5)?;
2779        assert_eq!(cache.seq_pos, 8);
2780
2781        let (k, _v) = cache.get()?;
2782        assert_eq!(k.size()[1], 8);
2783
2784        Ok(())
2785    }
2786
2787    #[test]
2788    fn test_block_pool_allocate_free() -> Result<()> {
2789        let device = Device::Cpu;
2790        let dtype = DType::Float;
2791        let mut pool = BlockPool::new(4, 2, 8, device, dtype)?;
2792        let owner = CacheOwner::Stateless(1);
2793
2794        assert_eq!(pool.total_blocks(), 4);
2795        assert_eq!(pool.free_block_count(), 4);
2796        assert_eq!(pool.used_blocks(), 0);
2797
2798        // Allocate 3 blocks
2799        let b0 = pool.allocate(&owner).expect("should allocate");
2800        let b1 = pool.allocate(&owner).expect("should allocate");
2801        let b2 = pool.allocate(&owner).expect("should allocate");
2802        assert_eq!(pool.used_blocks(), 3);
2803        assert_eq!(pool.free_block_count(), 1);
2804
2805        // Allocate last block
2806        let _b3 = pool.allocate(&owner).expect("should allocate");
2807        assert_eq!(pool.free_block_count(), 0);
2808
2809        // Pool exhausted — fail-soft typed error, not a generic failure
2810        let exhausted = pool.allocate(&owner);
2811        assert_eq!(exhausted, Err(BlockPoolExhausted { total_blocks: 4 }));
2812
2813        // Free a block — now one available
2814        pool.free(&owner, b1);
2815        assert_eq!(pool.free_block_count(), 1);
2816
2817        let reused = pool.allocate(&owner).expect("should allocate freed block");
2818        assert_eq!(reused, b1); // LIFO: should get back the same block
2819
2820        // Free all
2821        pool.free(&owner, b0);
2822        pool.free(&owner, reused);
2823        pool.free(&owner, b2);
2824        pool.free(&owner, _b3);
2825        assert_eq!(pool.free_block_count(), 4);
2826
2827        Ok(())
2828    }
2829
2830    #[test]
2831    fn test_paged_kv_cache_update_and_get() -> Result<()> {
2832        let device = Device::Cpu;
2833        let dtype = DType::Float;
2834        let num_kv_heads = 2;
2835        let head_dim = 4;
2836
2837        // Create pool with enough blocks for the test
2838        let pool = Arc::new(Mutex::new(BlockPool::new(
2839            8,
2840            num_kv_heads,
2841            head_dim,
2842            device,
2843            dtype,
2844        )?));
2845
2846        let mut cache = LayerKVCache::new_paged(1024, pool.clone(), CacheOwner::Stateless(1));
2847
2848        // Write 10 tokens (less than one block of 256)
2849        let keys = Tensor::ones(
2850            [1, 10, num_kv_heads as i64, head_dim as i64],
2851            (dtype, device),
2852        );
2853        let values = Tensor::ones(
2854            [1, 10, num_kv_heads as i64, head_dim as i64],
2855            (dtype, device),
2856        ) * 2.0;
2857        cache.update(&keys, &values, 0)?;
2858        assert_eq!(cache.seq_pos, 10);
2859
2860        // Get should return 10 tokens
2861        let (k, v) = cache.get()?;
2862        assert_eq!(k.size()[1], 10);
2863        assert_eq!(v.size()[1], 10);
2864
2865        // Append 5 more tokens
2866        let more_keys = Tensor::ones(
2867            [1, 5, num_kv_heads as i64, head_dim as i64],
2868            (dtype, device),
2869        ) * 3.0;
2870        let more_values = Tensor::ones(
2871            [1, 5, num_kv_heads as i64, head_dim as i64],
2872            (dtype, device),
2873        ) * 4.0;
2874        cache.update(&more_keys, &more_values, 10)?;
2875        assert_eq!(cache.seq_pos, 15);
2876
2877        let (k, _v) = cache.get()?;
2878        assert_eq!(k.size()[1], 15);
2879
2880        // Clear should free blocks back to pool
2881        let used_before = pool.lock().used_blocks();
2882        assert!(used_before > 0);
2883        cache.clear();
2884        assert_eq!(pool.lock().used_blocks(), used_before - 2); // 2 blocks freed (K + V)
2885        assert_eq!(cache.seq_pos, 0);
2886
2887        Ok(())
2888    }
2889
2890    #[test]
2891    fn test_cpu_offload_restore() -> Result<()> {
2892        let device = Device::Cpu; // Use CPU as "GPU" for test
2893        let dtype = DType::Float;
2894
2895        let mut manager = KVCacheManager::new(2, 100, KVQuantType::None);
2896        assert_eq!(manager.location(), CacheLocation::Gpu);
2897
2898        // Write some data via with_layer_cache
2899        manager.with_layer_cache(0, |cache| {
2900            let keys = Tensor::ones([1, 5, 4, 8], (dtype, device));
2901            let values = Tensor::ones([1, 5, 4, 8], (dtype, device)) * 2.0;
2902            cache.update(&keys, &values, 0).unwrap();
2903        });
2904
2905        // Offload to CPU (no-op on CPU device, but tests the state machine)
2906        manager.offload_to_cpu();
2907        assert_eq!(manager.location(), CacheLocation::Cpu);
2908
2909        // Restore back
2910        manager.restore_to_gpu(device);
2911        assert_eq!(manager.location(), CacheLocation::Gpu);
2912
2913        // Data should still be accessible
2914        let result = manager.with_layer_cache(0, |cache| {
2915            let (k, _v) = cache.get().unwrap();
2916            k.size()[1]
2917        });
2918        assert_eq!(result, Some(5));
2919
2920        Ok(())
2921    }
2922
2923    #[test]
2924    fn test_eviction_with_budget() {
2925        let config = CacheConfig::new(2, 100);
2926        let registry = KVCacheRegistry::new(config, Some(1)); // 1 byte budget = always evict
2927
2928        // Create two session caches
2929        let _cache_a = registry.get_or_create(CacheOwner::Session("a".into()));
2930        let _cache_b = registry.get_or_create(CacheOwner::Session("b".into()));
2931        assert_eq!(registry.cache_count(), 2);
2932
2933        // Eviction should try to free caches (offload first, then remove)
2934        registry.evict_to_budget();
2935
2936        // With a 1-byte budget and no actual GPU memory, both should be offloaded/removed
2937        // The exact behavior depends on memory_usage() returning >0 for non-empty caches
2938    }
2939
2940    // ========================================================================
2941    // Multi-turn prefix matching simulation tests
2942    // ========================================================================
2943
2944    #[test]
2945    fn test_prefix_match_multi_turn_simulation() {
2946        let mut manager = KVCacheManager::new(2, 1024, KVQuantType::None);
2947
2948        // Simulate tokenized prompts growing across conversation turns.
2949        // Each turn's prompt includes all prior history + new message.
2950
2951        // Turn 1: [sys sys sys user1 user1]
2952        let turn1_tokens = vec![10, 20, 30, 100, 101];
2953        manager.set_cached_tokens(turn1_tokens.clone());
2954
2955        // Turn 2: [sys sys sys user1 user1 asst1 asst1 user2]
2956        // The first 5 tokens match turn 1
2957        let turn2_tokens = vec![10, 20, 30, 100, 101, 200, 201, 102];
2958        assert_eq!(manager.prefix_match_len(&turn2_tokens), 5);
2959
2960        // After turn 2 completes, update cached tokens
2961        manager.set_cached_tokens(turn2_tokens.clone());
2962
2963        // Turn 3: [sys sys sys user1 user1 asst1 asst1 user2 asst2 user3]
2964        // The first 8 tokens match turn 2
2965        let turn3_tokens = vec![10, 20, 30, 100, 101, 200, 201, 102, 202, 103];
2966        assert_eq!(manager.prefix_match_len(&turn3_tokens), 8);
2967
2968        // Verify no match if conversation diverges at the start
2969        let divergent = vec![99, 20, 30, 100, 101];
2970        manager.set_cached_tokens(turn3_tokens);
2971        assert_eq!(manager.prefix_match_len(&divergent), 0);
2972    }
2973
2974    #[test]
2975    fn test_prefix_match_with_tool_call_in_history() {
2976        let mut manager = KVCacheManager::new(2, 1024, KVQuantType::None);
2977
2978        // Turn 1: [sys user1_ask_weather]
2979        let turn1_tokens = vec![10, 100, 101];
2980        manager.set_cached_tokens(turn1_tokens);
2981
2982        // Turn 2 includes tool call and response in history:
2983        // [sys user1_ask_weather asst_toolcall tool_resp user2_followup]
2984        // Prefix match = 3 (sys + user1 tokens)
2985        let turn2_tokens = vec![10, 100, 101, 200, 201, 202, 300, 301, 110, 111];
2986        assert_eq!(manager.prefix_match_len(&turn2_tokens), 3);
2987
2988        // After turn 2, cache the full sequence
2989        manager.set_cached_tokens(turn2_tokens.clone());
2990
2991        // Turn 3: same prefix as turn 2 + new user message
2992        // [sys user1_ask_weather asst_toolcall tool_resp user2_followup asst2 user3]
2993        let turn3_tokens = vec![10, 100, 101, 200, 201, 202, 300, 301, 110, 111, 210, 120];
2994        assert_eq!(manager.prefix_match_len(&turn3_tokens), 10);
2995    }
2996
2997    // ========================================================================
2998    // PR-0: paged-pool correctness (free-on-drop, fail-soft, ownership)
2999    // ========================================================================
3000
3001    /// Dropping a paged cache (e.g. via registry eviction) must return its
3002    /// blocks to the pool free list — the original leak was no `Drop` impl.
3003    #[test]
3004    fn test_paged_cache_frees_blocks_on_drop() -> Result<()> {
3005        let device = Device::Cpu;
3006        let dtype = DType::Float;
3007        let pool = Arc::new(Mutex::new(BlockPool::new(8, 2, 4, device, dtype)?));
3008        assert_eq!(pool.lock().used_blocks(), 0);
3009
3010        {
3011            let mut cache = LayerKVCache::new_paged(1024, pool.clone(), CacheOwner::Stateless(7));
3012            let keys = Tensor::ones([1, 10, 2, 4], (dtype, device));
3013            let values = Tensor::ones([1, 10, 2, 4], (dtype, device));
3014            cache.update(&keys, &values, 0)?;
3015            assert_eq!(pool.lock().used_blocks(), 2); // 1 K + 1 V block
3016                                                      // `cache` dropped here WITHOUT an explicit clear()
3017        }
3018
3019        // Drop must have returned both blocks to the pool.
3020        assert_eq!(pool.lock().used_blocks(), 0);
3021        assert_eq!(pool.lock().free_block_count(), 8);
3022        Ok(())
3023    }
3024
3025    /// A `KVCacheManager` dropped via the registry (`caches.remove`) must not
3026    /// leak its layers' blocks.
3027    #[test]
3028    fn test_paged_manager_frees_blocks_on_drop() -> Result<()> {
3029        let device = Device::Cpu;
3030        let dtype = DType::Float;
3031        let pool = Arc::new(Mutex::new(BlockPool::new(16, 2, 4, device, dtype)?));
3032
3033        {
3034            let manager =
3035                KVCacheManager::new_paged(3, 1024, pool.clone(), CacheOwner::Session("s".into()));
3036            for layer in 0..3 {
3037                manager.with_layer_cache(layer, |c| {
3038                    let k = Tensor::ones([1, 5, 2, 4], (dtype, device));
3039                    let v = Tensor::ones([1, 5, 2, 4], (dtype, device));
3040                    c.update(&k, &v, 0).unwrap();
3041                });
3042            }
3043            assert_eq!(pool.lock().used_blocks(), 6); // 3 layers x (1 K + 1 V)
3044        }
3045
3046        assert_eq!(pool.lock().used_blocks(), 0);
3047        Ok(())
3048    }
3049
3050    #[test]
3051    fn mtp_auxiliary_cache_retains_paged_pool_and_owner() -> Result<()> {
3052        for main_layers in [0, 1] {
3053            let pool = Arc::new(Mutex::new(BlockPool::new(
3054                2,
3055                2,
3056                4,
3057                Device::Cpu,
3058                DType::Float,
3059            )?));
3060            let alice = CacheOwner::Session("mtp-alice".into());
3061            let manager = KVCacheManager::new_paged(main_layers, 64, pool.clone(), alice.clone());
3062            let keys = Tensor::ones([1, 1, 2, 4], (DType::Float, Device::Cpu));
3063            manager.ensure_layer_cache(main_layers);
3064            manager
3065                .with_layer_cache(main_layers, |cache| cache.update(&keys, &keys, 0))
3066                .expect("auxiliary slot")?;
3067            assert_eq!(pool.lock().used_blocks(), 2);
3068            for block in 0..2 {
3069                assert_eq!(pool.lock().owner_of(block), Some(&alice));
3070            }
3071            // Re-admission must retain the existing cache and its blocks.
3072            manager.ensure_layer_cache(main_layers);
3073            assert_eq!(pool.lock().used_blocks(), 2);
3074            manager.ensure_layer_cache(main_layers + 1);
3075            let error = manager
3076                .with_layer_cache(main_layers + 1, |cache| cache.update(&keys, &keys, 0))
3077                .expect("second auxiliary slot")
3078                .expect_err("shared pool is full");
3079            assert!(error.downcast_ref::<BlockPoolExhausted>().is_some());
3080            assert_eq!(pool.lock().used_blocks(), 2);
3081            let bob = CacheOwner::Session("mtp-bob".into());
3082            let other = KVCacheManager::new_paged(0, 64, pool.clone(), bob.clone());
3083            other.ensure_layer_cache(0);
3084            assert!(other
3085                .with_layer_cache(0, |cache| cache.update(&keys, &keys, 0))
3086                .expect("other owner's auxiliary slot")
3087                .is_err());
3088            drop(manager);
3089            assert_eq!(pool.lock().used_blocks(), 0);
3090            other
3091                .with_layer_cache(0, |cache| cache.update(&keys, &keys, 0))
3092                .expect("other owner's auxiliary slot")?;
3093            for block in 0..2 {
3094                assert_eq!(pool.lock().owner_of(block), Some(&bob));
3095            }
3096            drop(other);
3097            assert_eq!(pool.lock().used_blocks(), 0);
3098        }
3099        Ok(())
3100    }
3101
3102    /// Exhaustion surfaces as the typed, downcastable `BlockPoolExhausted`
3103    /// (fail-soft) rather than an opaque error — a scheduler can admission-defer.
3104    #[test]
3105    fn test_paged_update_exhaustion_is_fail_soft() -> Result<()> {
3106        let device = Device::Cpu;
3107        let dtype = DType::Float;
3108        // Only 1 block: cannot satisfy even a single (K + V) pair.
3109        let pool = Arc::new(Mutex::new(BlockPool::new(1, 2, 4, device, dtype)?));
3110        let mut cache = LayerKVCache::new_paged(1024, pool.clone(), CacheOwner::Stateless(1));
3111
3112        let keys = Tensor::ones([1, 10, 2, 4], (dtype, device));
3113        let values = Tensor::ones([1, 10, 2, 4], (dtype, device));
3114        let err = cache
3115            .update(&keys, &values, 0)
3116            .expect_err("should fail-soft on exhaustion");
3117
3118        let exhausted = err.downcast_ref::<BlockPoolExhausted>();
3119        assert!(
3120            exhausted.is_some(),
3121            "expected BlockPoolExhausted, got: {err:?}"
3122        );
3123        assert_eq!(exhausted.unwrap().total_blocks, 1);
3124
3125        // The key block allocated before the value alloc failed must be rolled
3126        // back so the pool is not partially consumed by a failed admission.
3127        assert_eq!(pool.lock().used_blocks(), 0);
3128        Ok(())
3129    }
3130
3131    /// A block allocated by one owner cannot be freed by another (tenant
3132    /// isolation). In debug builds the impl panics via `debug_assert!`; in
3133    /// release builds it logs and silently returns without mutating pool state.
3134    /// Both cases must leave block ownership and used-count unchanged.
3135    #[test]
3136    fn test_cross_owner_free_is_rejected() -> Result<()> {
3137        let device = Device::Cpu;
3138        let dtype = DType::Float;
3139        let mut pool = BlockPool::new(4, 2, 4, device, dtype)?;
3140
3141        let alice = CacheOwner::Session("alice".into());
3142        let bob = CacheOwner::Session("bob".into());
3143
3144        let block = pool.allocate(&alice).expect("alice allocates");
3145        assert_eq!(pool.owner_of(block), Some(&alice));
3146
3147        // In debug builds, `debug_assert!` fires and the call panics.
3148        // In release builds, the impl logs and returns without changing state.
3149        // Either way, the security invariant must hold: ownership is preserved
3150        // and the block stays in use. Use catch_unwind so the test body can
3151        // continue in both profiles to verify the post-condition.
3152        let _ = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
3153            pool.free(&bob, block);
3154        }));
3155
3156        // Security invariant: block is still owned by Alice and still in use
3157        // regardless of whether a panic occurred.
3158        assert_eq!(
3159            pool.owner_of(block),
3160            Some(&alice),
3161            "cross-owner free must not transfer or clear block ownership"
3162        );
3163        assert_eq!(
3164            pool.used_blocks(),
3165            1,
3166            "cross-owner free must not return block to free list"
3167        );
3168
3169        // Alice can free her own block.
3170        pool.free(&alice, block);
3171        assert_eq!(pool.used_blocks(), 0);
3172        assert_eq!(pool.owner_of(block), None);
3173        Ok(())
3174    }
3175
3176    fn compat_test_fingerprint(base_revision: &str) -> KvCompatFingerprint {
3177        use crate::runtime::kv_compat::{
3178            KvCompatDescriptor, WeightIdentity, KV_COMPAT_FORMAT_VERSION,
3179        };
3180
3181        KvCompatDescriptor {
3182            format_version: KV_COMPAT_FORMAT_VERSION,
3183            weights: WeightIdentity::base_only(base_revision),
3184            tokenizer_hash: Some("deadbeef".to_owned()),
3185            ..Default::default()
3186        }
3187        .fingerprint()
3188    }
3189
3190    /// Populate both reuse signals on a real manager: token IDs used by prefix
3191    /// matching and layer tensors used by attention.
3192    fn populate_compat_test_cache(manager: &mut KVCacheManager) {
3193        manager.set_cached_tokens(vec![1, 2, 3, 4]);
3194        let updated = manager.with_layer_cache(0, |cache| {
3195            let keys = Tensor::ones([1, 4, 2, 4], (DType::Float, Device::Cpu));
3196            let values = Tensor::ones([1, 4, 2, 4], (DType::Float, Device::Cpu));
3197            cache
3198                .update(&keys, &values, 0)
3199                .expect("populate layer cache");
3200        });
3201        assert_eq!(updated, Some(()));
3202    }
3203
3204    fn compat_test_layer_seq_pos(manager: &KVCacheManager) -> usize {
3205        manager
3206            .with_layer_cache(0, |cache| cache.seq_pos)
3207            .expect("layer 0 exists")
3208    }
3209
3210    #[test]
3211    fn apply_reuse_policy_retains_compatible_real_cache() {
3212        let expected = compat_test_fingerprint("sha256:base");
3213        let mut manager = KVCacheManager::new(2, 64, KVQuantType::None);
3214
3215        assert_eq!(
3216            manager.apply_reuse_policy(Some(expected)),
3217            CacheReuseDecision::StampFresh
3218        );
3219        assert_eq!(manager.compat_fingerprint(), Some(expected));
3220
3221        populate_compat_test_cache(&mut manager);
3222        assert_eq!(
3223            manager.apply_reuse_policy(Some(expected)),
3224            CacheReuseDecision::Reuse
3225        );
3226        assert_eq!(manager.cached_token_count(), 4);
3227        assert_eq!(compat_test_layer_seq_pos(&manager), 4);
3228        assert_eq!(manager.compat_fingerprint(), Some(expected));
3229    }
3230
3231    #[test]
3232    fn apply_reuse_policy_discards_and_restamps_incompatible_real_cache() {
3233        let original = compat_test_fingerprint("sha256:old");
3234        let expected = compat_test_fingerprint("sha256:new");
3235        let mut manager = KVCacheManager::new(2, 64, KVQuantType::None);
3236
3237        assert_eq!(
3238            manager.apply_reuse_policy(Some(original)),
3239            CacheReuseDecision::StampFresh
3240        );
3241        populate_compat_test_cache(&mut manager);
3242
3243        assert_eq!(
3244            manager.apply_reuse_policy(Some(expected)),
3245            CacheReuseDecision::DiscardAndRecompute
3246        );
3247        assert_eq!(manager.cached_token_count(), 0);
3248        assert_eq!(compat_test_layer_seq_pos(&manager), 0);
3249        assert_eq!(manager.compat_fingerprint(), Some(expected));
3250    }
3251
3252    #[test]
3253    fn apply_reuse_policy_discards_populated_unstamped_real_cache() {
3254        let expected = compat_test_fingerprint("sha256:base");
3255        let mut manager = KVCacheManager::new(2, 64, KVQuantType::None);
3256        populate_compat_test_cache(&mut manager);
3257        assert!(manager.compat_fingerprint().is_none());
3258
3259        assert_eq!(
3260            manager.apply_reuse_policy(Some(expected)),
3261            CacheReuseDecision::DiscardAndRecompute
3262        );
3263        assert_eq!(manager.cached_token_count(), 0);
3264        assert_eq!(compat_test_layer_seq_pos(&manager), 0);
3265        assert_eq!(manager.compat_fingerprint(), Some(expected));
3266    }
3267
3268    // ========================================================================
3269    // TTT → KV invalidation wiring (#1254, epic #1246)
3270    // ========================================================================
3271
3272    /// Write 4 cached token IDs + a 4-token KV entry into layer 0 of a cache,
3273    /// so "cleared" is observable as both empty token IDs (cached_token_count)
3274    /// and an empty layer (seq_pos == 0).
3275    fn populate_cache(cache: &Arc<Mutex<KVCacheManager>>) {
3276        let mut g = cache.lock();
3277        g.set_cached_tokens(vec![10, 20, 30, 40]);
3278        g.with_layer_cache(0, |c| {
3279            let k = Tensor::ones([1, 4, 2, 4], (DType::Float, Device::Cpu));
3280            let v = Tensor::ones([1, 4, 2, 4], (DType::Float, Device::Cpu));
3281            c.update(&k, &v, 0).expect("layer 0 update");
3282        });
3283    }
3284
3285    /// seq_pos of layer 0 (None when caching disabled / layer absent).
3286    fn layer0_seq_pos(cache: &Arc<Mutex<KVCacheManager>>) -> Option<usize> {
3287        cache.lock().with_layer_cache(0, |c| c.seq_pos)
3288    }
3289
3290    /// Invalidating one tenant's delta clears that tenant's cache while every
3291    /// other tenant's cache is left intact — the core cross-tenant isolation
3292    /// invariant the missing `register_delta_dependency` call broke (#1254).
3293    #[test]
3294    fn test_invalidate_for_tenant_isolates_tenants() {
3295        let registry = KVCacheRegistry::new(CacheConfig::new(2, 128), None);
3296
3297        let owner_a = CacheOwner::Session("session-a".into());
3298        let owner_b = CacheOwner::Session("session-b".into());
3299
3300        let cache_a = registry.get_or_create(owner_a.clone());
3301        let cache_b = registry.get_or_create(owner_b.clone());
3302        populate_cache(&cache_a);
3303        populate_cache(&cache_b);
3304
3305        // Register each cache under its own tenant delta.
3306        registry.register_delta_dependency(&owner_a, Some("tenant-a".into()), 1);
3307        registry.register_delta_dependency(&owner_b, Some("tenant-b".into()), 1);
3308
3309        assert_eq!(registry.cache_count(), 2);
3310        assert_eq!(cache_a.lock().cached_token_count(), 4);
3311        assert_eq!(cache_b.lock().cached_token_count(), 4);
3312
3313        // Evict tenant-a's delta: only A's cache is invalidated; B is untouched.
3314        let invalidated = registry.invalidate_for_tenant("tenant-a");
3315        assert_eq!(invalidated, 1);
3316        assert_eq!(
3317            registry.cache_count(),
3318            1,
3319            "only tenant-a's cache is removed"
3320        );
3321
3322        // A's cache (Arc still held by the test) was cleared in place.
3323        assert_eq!(
3324            cache_a.lock().cached_token_count(),
3325            0,
3326            "tenant-a cache cleared"
3327        );
3328        assert_eq!(
3329            layer0_seq_pos(&cache_a),
3330            Some(0),
3331            "tenant-a layer KV cleared"
3332        );
3333
3334        // B's cache survives with its KV intact.
3335        assert_eq!(
3336            cache_b.lock().cached_token_count(),
3337            4,
3338            "tenant-b cache intact"
3339        );
3340        assert_eq!(
3341            layer0_seq_pos(&cache_b),
3342            Some(4),
3343            "tenant-b layer KV intact"
3344        );
3345    }
3346
3347    /// A session cache must not survive a weight-version change: no-delta↔delta
3348    /// and tenant-A↔tenant-B transitions all clear the stale KV; re-registering
3349    /// the SAME tenant preserves it. This is the stale-cache-crossing-weight-
3350    /// versions guard the serving path now enforces via register_delta_dependency.
3351    #[test]
3352    fn test_register_clears_stale_kv_on_tenant_transition() {
3353        let registry = KVCacheRegistry::new(CacheConfig::new(2, 128), None);
3354        let owner = CacheOwner::Session("session-x".into());
3355        let cache = registry.get_or_create(owner.clone());
3356        populate_cache(&cache);
3357
3358        // 1. First compute under NO tenant delta — fresh, nothing stale.
3359        assert!(
3360            !registry.register_delta_dependency(&owner, None, 0),
3361            "fresh cache is not stale"
3362        );
3363        assert_eq!(
3364            cache.lock().cached_token_count(),
3365            4,
3366            "KV preserved on first register"
3367        );
3368
3369        // 2. no-delta → tenant delta: weights changed, KV is stale and cleared.
3370        assert!(
3371            registry.register_delta_dependency(&owner, Some("tenant-1".into()), 1),
3372            "no-delta → delta must clear stale KV"
3373        );
3374        assert_eq!(
3375            cache.lock().cached_token_count(),
3376            0,
3377            "KV cleared across weight version"
3378        );
3379        assert_eq!(layer0_seq_pos(&cache), Some(0));
3380
3381        // Repopulate to simulate a fresh compute under tenant-1.
3382        populate_cache(&cache);
3383        assert_eq!(cache.lock().cached_token_count(), 4);
3384
3385        // 3. Same tenant, same weight epoch — NOT stale, KV preserved.
3386        assert!(
3387            !registry.register_delta_dependency(&owner, Some("tenant-1".into()), 1),
3388            "same tenant at the same epoch is not stale"
3389        );
3390        assert_eq!(
3391            cache.lock().cached_token_count(),
3392            4,
3393            "KV preserved for same tenant"
3394        );
3395
3396        // 4. delta → no-delta: weights changed again, stale and cleared.
3397        assert!(
3398            registry.register_delta_dependency(&owner, None, 0),
3399            "delta → no-delta must clear stale KV"
3400        );
3401        assert_eq!(cache.lock().cached_token_count(), 0);
3402
3403        // 5. Repopulate, then switch tenants (tenant-1 effective → tenant-2): stale.
3404        populate_cache(&cache);
3405        assert!(
3406            registry.register_delta_dependency(&owner, Some("tenant-2".into()), 1),
3407            "tenant change must clear stale KV"
3408        );
3409        assert_eq!(cache.lock().cached_token_count(), 0);
3410
3411        // 6. After a clear, the recorded tenant is tenant-2; invalidating
3412        //    tenant-2 still finds (and removes) the owner entry.
3413        assert_eq!(registry.invalidate_for_tenant("tenant-2"), 1);
3414    }
3415
3416    /// Same-tenant in-place re-adaptation (adapt_tenant/train_step/rollback/reset
3417    /// bumps the delta's weight epoch while the tenant id stays the same) must
3418    /// clear the stale KV on the next reuse; reusing at the SAME epoch (no
3419    /// re-adaptation) must preserve it. This is the F1 regression test: the
3420    /// recorded `(tenant_id, weight_epoch)` pair detects weight staleness that a
3421    /// tenant-id-only comparison cannot (#1254).
3422    #[test]
3423    fn test_register_clears_stale_kv_on_weight_epoch_advance() {
3424        let registry = KVCacheRegistry::new(CacheConfig::new(2, 128), None);
3425        let owner = CacheOwner::Session("session-ttt".into());
3426        let cache = registry.get_or_create(owner.clone());
3427        populate_cache(&cache);
3428
3429        // Compute under tenant-1 at weight epoch 1 — fresh, nothing stale.
3430        assert!(
3431            !registry.register_delta_dependency(&owner, Some("tenant-1".into()), 1),
3432            "fresh cache is not stale"
3433        );
3434        assert_eq!(cache.lock().cached_token_count(), 4);
3435
3436        // No re-adaptation: same tenant, same epoch → KV preserved.
3437        assert!(
3438            !registry.register_delta_dependency(&owner, Some("tenant-1".into()), 1),
3439            "same tenant at the same epoch must preserve KV"
3440        );
3441        assert_eq!(
3442            cache.lock().cached_token_count(),
3443            4,
3444            "KV preserved within a weight epoch"
3445        );
3446        assert_eq!(layer0_seq_pos(&cache), Some(4));
3447
3448        // In-place re-adaptation: tenant id unchanged, epoch bumped 1 → 2.
3449        // The cached KV was computed under the old weights → stale, cleared.
3450        assert!(
3451            registry.register_delta_dependency(&owner, Some("tenant-1".into()), 2),
3452            "same tenant at an advanced epoch must clear stale KV"
3453        );
3454        assert_eq!(
3455            cache.lock().cached_token_count(),
3456            0,
3457            "weight-stale KV cleared"
3458        );
3459        assert_eq!(layer0_seq_pos(&cache), Some(0));
3460
3461        // Repopulate under the new weights; the new epoch is now recorded.
3462        populate_cache(&cache);
3463        assert!(
3464            !registry.register_delta_dependency(&owner, Some("tenant-1".into()), 2),
3465            "post-clear reuse at the recorded epoch is not stale"
3466        );
3467        assert_eq!(
3468            cache.lock().cached_token_count(),
3469            4,
3470            "KV preserved after recompute"
3471        );
3472
3473        // A reset/rollback bumps the epoch again → stale again.
3474        assert!(
3475            registry.register_delta_dependency(&owner, Some("tenant-1".into()), 3),
3476            "further epoch advance (reset/rollback) must clear stale KV"
3477        );
3478        assert_eq!(cache.lock().cached_token_count(), 0);
3479    }
3480
3481    /// Releasing or evicting a cache must drop its delta dependency so the map
3482    /// has no orphan entries that a later invalidation would chase. Covers the
3483    /// Stateless release path; evict_to_budget mirrors the same removal.
3484    #[test]
3485    fn test_release_clears_delta_dependency() {
3486        let registry = KVCacheRegistry::new(CacheConfig::new(2, 128), None);
3487
3488        let owner = CacheOwner::Stateless(42);
3489        let _cache = registry.get_or_create(owner.clone());
3490        registry.register_delta_dependency(&owner, Some("tenant-s".into()), 1);
3491        assert!(registry.delta_dependencies.contains_key(&owner));
3492
3493        // Releasing a stateless cache removes both the cache and its dependency.
3494        registry.release(&owner);
3495        assert!(
3496            !registry.caches.contains_key(&owner),
3497            "stateless cache removed"
3498        );
3499        assert!(
3500            !registry.delta_dependencies.contains_key(&owner),
3501            "delta dependency removed on release"
3502        );
3503
3504        // No orphan dependency → a later invalidation finds nothing.
3505        assert_eq!(registry.invalidate_for_tenant("tenant-s"), 0);
3506    }
3507
3508    /// A no-tenant cache (registered `None`) must NOT be cleared by any tenant's
3509    /// invalidation — it carries no tenant dependency.
3510    #[test]
3511    fn test_no_tenant_cache_survives_any_invalidation() {
3512        let registry = KVCacheRegistry::new(CacheConfig::new(2, 128), None);
3513        let owner = CacheOwner::Session("base-only".into());
3514        let cache = registry.get_or_create(owner.clone());
3515        populate_cache(&cache);
3516        registry.register_delta_dependency(&owner, None, 0);
3517
3518        // Invalidating any tenant leaves the no-tenant cache untouched.
3519        assert_eq!(registry.invalidate_for_tenant("anyone"), 0);
3520        assert_eq!(registry.cache_count(), 1);
3521        assert_eq!(
3522            cache.lock().cached_token_count(),
3523            4,
3524            "no-tenant cache intact"
3525        );
3526    }
3527}