Skip to main content

dynamo_tokenizers/cache/
mod.rs

1// SPDX-FileCopyrightText: Copyright (c) 2025-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
2// SPDX-License-Identifier: Apache-2.0
3//
4// SPDX-FileCopyrightText: Copyright (c) 2024 Simo Lin, Chang Su, Keyang Ru (llm-tokenizer authors)
5//
6// Portions adapted from sgl-project/llm-tokenizer v1.3.2 (Apache-2.0).
7// Upstream: https://github.com/lightseekorg/smg
8// Modifications: removed L0 layer, removed `add_special_tokens` plumbing (Dynamo's
9// `Encoder::encode` has no such flag), dropped fingerprinting, retargeted onto
10// `crate::traits::Tokenizer`.
11
12//! Tokenizer caching layer (L1: prefix matching at special-token boundaries).
13//!
14//! Wraps a cache-compatible [`Tokenizer`] in a cache that records prefix
15//! tokenizations at every special-token boundary. On a hit, the cached prefix
16//! tokens are merged with a fresh encode of the trailing suffix only — turning
17//! O(N) tokenization work into O(suffix_len) when prompts share a system prefix.
18//!
19//! # Correctness
20//!
21//! Boundaries are taken **only** at positions immediately following a registered
22//! special token (e.g. `<|im_start|>`, `<|im_end|>`, `<s>`, `</s>`). Special tokens
23//! are atomic in BPE (`special: true, normalized: false`), so splitting there
24//! preserves the invariant `tokenize(prefix) + tokenize(suffix) == tokenize(prefix + suffix)`.
25//! No fallback to whitespace or punctuation — better to miss than to corrupt.
26//! Callers must supply actual atomic special tokens recognized by the inner tokenizer;
27//! adding arbitrary strings to the boundary list is unsafe.
28//!
29//! Atomicity alone is insufficient when registered special-token strings can overlap.
30//! [`CachedTokenizer::new`] disables L1 for such sets because the boundary scanner could
31//! otherwise split inside the token selected by the underlying tokenizer.
32//!
33//! # Storage normalization
34//!
35//! When L1 is enabled, **every** `encode` returns [`Encoding::Sp`] (token-ids only) —
36//! hits merge cached prefix ids with a fresh suffix encode, and misses assemble the ids
37//! from the per-boundary segment encodes (see [`L1Cache::populate_and_encode`]) — even
38//! when the inner tokenizer would have produced [`Encoding::Hf`] (rich offsets/attention/
39//! etc). All current downstream consumers in Dynamo only call [`Encoding::token_ids`], so
40//! this lossy normalization is safe; revisit if a caller starts reading offsets or
41//! attention masks from encodings produced through the cache.
42//!
43//! # Configuration
44//!
45//! - `special_tokens: Vec<String>` — must be supplied at construction (the
46//!   [`Tokenizer`] trait is intentionally minimal and does not expose them).
47//!   An empty list disables L1: `encode`/`encode_batch` short-circuit straight
48//!   to the inner tokenizer with no lookup, no miss-counter bump, and no
49//!   insert attempt. A list whose members can overlap disables L1 identically.
50//! - `encode_segments` caches whole segments instead of prefixes: each segment of at
51//!   least 128 bytes is keyed by its exact text and `allow_special` flag (a key space
52//!   disjoint from prefix keys), so every turn of a multi-turn conversation re-encodes
53//!   only its new segments. Flattening segments for prefix matching would discard their
54//!   special-token trust boundaries, and segment caching never needs to: backends
55//!   encode segments independently. Shorter segments (control markers) are encoded in
56//!   contiguous runs and never cached. Segments are cached only while L1 is active (a
57//!   non-empty, non-overlapping special-token set), so an empty set still disables all
58//!   caching.
59//! - `max_memory_bytes` — token-ID payload byte budget, excluding keys and metadata.
60//!   Moka shares admission and eviction via W-TinyLFU. Deferred maintenance makes the
61//!   capacity approximate; it is not a limit on total process memory.
62//! - [`CachedTokenizer::new`] owns a private cache. [`CachedTokenizer::new_with_cache`]
63//!   shares storage across wrappers; entries survive a wrapper being dropped while
64//!   shared storage remains alive. Equal namespaces must identify identical tokenizer
65//!   behavior, including tokenizer files, backend, and options that affect token IDs.
66//!
67//! # Provenance
68//!
69//! Adapted from `llm-tokenizer` v1.3.2 (`cache/l1.rs`, `cache/mod.rs`). L0 and
70//! upstream fingerprinting were dropped; L1 covers the multi-turn-chat workload.
71//! Shared caches use caller-supplied namespaces to separate tokenizer identities.
72
73mod l1;
74
75use std::sync::Arc;
76
77use l1::PrefixLookup;
78pub use l1::{
79    CacheEventFn, L1Cache, L1CacheStats, SharedTokenizerCache, SharedTokenizerCacheStats,
80};
81
82use crate::{
83    EncodeSegment, Encoding, Result, TokenIdType,
84    traits::{DecodeResult, Decoder, Encoder, Tokenizer},
85};
86
87/// Smallest segment (in bytes) that [`CachedTokenizer::encode_segments`] caches.
88/// Shorter segments, such as control markers, encode faster than an entry pays off.
89const MIN_CACHED_SEGMENT_BYTES: usize = 128;
90
91/// Token-level cache usage for one successful encode.
92///
93/// A partial cache hit reports both cached prefix tokens and uncached suffix tokens.
94/// Their sum always equals the number of tokens returned by the encode operation.
95#[derive(Debug, Clone, Copy, PartialEq, Eq)]
96pub struct CacheTokenUsage {
97    /// Tokens returned from the cached prefix.
98    pub cached_tokens: usize,
99    /// Tokens freshly encoded from the uncached suffix.
100    pub uncached_tokens: usize,
101}
102
103/// Optional observer for token-level cache usage.
104pub type CacheTokenUsageFn = Arc<dyn Fn(CacheTokenUsage) + Send + Sync>;
105
106/// Caching wrapper around an inner tokenizer.
107///
108/// Implements [`Encoder`], [`Decoder`], and [`Tokenizer`]; decode calls pass
109/// through to the inner tokenizer (decoding is fast and rarely repeated).
110pub struct CachedTokenizer {
111    inner: Arc<dyn Tokenizer>,
112    l1: L1Cache,
113    l1_enabled: bool,
114    extend_on_hit: bool,
115    /// Called once after every successful encode while L1 is active.
116    token_observer: Option<CacheTokenUsageFn>,
117}
118
119impl CachedTokenizer {
120    /// Construct a cached tokenizer.
121    ///
122    /// `special_tokens` is the list of atomic special-token strings the inner
123    /// tokenizer recognizes (typically extracted via the HuggingFace tokenizer's
124    /// `get_added_tokens_decoder()` filtering by `special == true`). An empty list
125    /// disables L1 — `encode`/`encode_batch` short-circuit to the inner tokenizer
126    /// without touching the cache or its counters. An overlapping token set also disables
127    /// L1, with a warning, because its boundaries are ambiguous.
128    ///
129    /// `max_memory_bytes` is the private token-ID payload byte budget. Moka defers
130    /// eviction, so the budget is approximate and excludes keys and metadata.
131    ///
132    /// # Errors
133    ///
134    /// Returns the inner tokenizer's compatibility error when it cannot be
135    /// safely wrapped in the prefix cache.
136    pub fn new(
137        inner: Arc<dyn Tokenizer>,
138        special_tokens: Vec<String>,
139        max_memory_bytes: usize,
140    ) -> Result<Self> {
141        Self::build(inner, special_tokens, |tokens| {
142            L1Cache::new(max_memory_bytes, tokens)
143        })
144    }
145
146    /// Construct a tokenizer using shared storage and a caller-supplied namespace.
147    ///
148    /// Equal namespaces share entries and must describe identical tokenizer behavior,
149    /// including tokenizer files, backend, and encoding options. Different namespaces
150    /// compete for the same byte budget but cannot reuse each other's token IDs.
151    /// Entries survive this wrapper being dropped while the shared cache remains alive.
152    /// The eligibility checks are the same as [`Self::new`].
153    ///
154    /// # Errors
155    ///
156    /// Returns the inner tokenizer's compatibility error if prefix caching is unsafe.
157    pub fn new_with_cache(
158        inner: Arc<dyn Tokenizer>,
159        special_tokens: Vec<String>,
160        shared_cache: SharedTokenizerCache,
161        namespace: &[u8],
162    ) -> Result<Self> {
163        Self::build(inner, special_tokens, |tokens| {
164            L1Cache::new_with_cache(shared_cache, tokens, namespace)
165        })
166    }
167
168    fn build(
169        inner: Arc<dyn Tokenizer>,
170        mut special_tokens: Vec<String>,
171        make_cache: impl FnOnce(Vec<String>) -> L1Cache,
172    ) -> Result<Self> {
173        inner.validate_prefix_cache()?;
174        special_tokens.retain(|token| !token.is_empty());
175
176        // Overlapping matches can create a cache boundary inside a token selected by the
177        // inner tokenizer. Preserve correctness by bypassing this optional optimization.
178        let overlapping_specials = match l1::first_unsafe_overlap(&special_tokens) {
179            Some((first, second)) => {
180                tracing::warn!(
181                    target: "tokenizer",
182                    first_token = first,
183                    second_token = second,
184                    special_token_count = special_tokens.len(),
185                    "special tokens can overlap; tokenizer prefix cache disabled"
186                );
187                true
188            }
189            None => false,
190        };
191
192        let l1_enabled = !special_tokens.is_empty() && !overlapping_specials;
193        let cache_tokens = if l1_enabled {
194            special_tokens
195        } else {
196            Vec::new()
197        };
198        Ok(Self {
199            inner,
200            l1: make_cache(cache_tokens),
201            l1_enabled,
202            extend_on_hit: false,
203            token_observer: None,
204        })
205    }
206
207    /// Enable partial-hit extension. When on, a partial cache hit also caches the
208    /// freshly-tokenized suffix at its deepest special-token boundary, so each turn of
209    /// a growing multi-turn conversation hits deeper than the last and per-turn
210    /// tokenization cost stops growing with conversation length. Default off.
211    pub fn with_extend(mut self, enabled: bool) -> Self {
212        self.extend_on_hit = enabled;
213        self
214    }
215
216    /// Install hit/miss callbacks so each L1 lookup pushes an event into the
217    /// supplied closures (e.g. `Prometheus::Counter::inc`). Replaces any
218    /// previously-set observer.
219    pub fn with_observer(mut self, on_hit: CacheEventFn, on_miss: CacheEventFn) -> Self {
220        self.l1.set_observer(on_hit, on_miss);
221        self
222    }
223
224    /// Install a callback that receives exact cached and uncached token counts after each
225    /// successful encode while L1 is active. A partial hit reports both categories, which
226    /// lets consumers maintain token-level cache totals and derive a reuse ratio. Replaces
227    /// any previously-set token observer.
228    ///
229    /// This observer is not called when the special-token set is empty (and L1 is therefore
230    /// disabled) or when encoding returns an error.
231    pub fn with_token_observer(mut self, observer: CacheTokenUsageFn) -> Self {
232        self.token_observer = Some(observer);
233        self
234    }
235
236    fn observe_token_usage(&self, cached_tokens: usize, total_tokens: usize) {
237        if let Some(observer) = &self.token_observer {
238            let uncached_tokens = total_tokens
239                .checked_sub(cached_tokens)
240                .expect("cached token count cannot exceed total token count");
241            observer(CacheTokenUsage {
242                cached_tokens,
243                uncached_tokens,
244            });
245        }
246    }
247
248    /// Wrapper-local hits/misses and namespace-wide entries/token bytes.
249    /// Shared storage statistics scan the namespace; private caches use Moka's totals.
250    /// Results can change under concurrent writes. Disabled wrappers report zeroes.
251    pub fn cache_stats(&self) -> L1CacheStats {
252        if self.l1_enabled {
253            self.l1.stats()
254        } else {
255            L1CacheStats::default()
256        }
257    }
258
259    /// Access the underlying tokenizer (e.g. for downcasting to a concrete type).
260    pub fn inner(&self) -> &Arc<dyn Tokenizer> {
261        &self.inner
262    }
263}
264
265impl Encoder for CachedTokenizer {
266    fn encode(&self, input: &str) -> Result<Encoding> {
267        if !self.l1_enabled {
268            return self.inner.encode(input);
269        }
270
271        let matched = match self.l1.lookup_prefix(input) {
272            PrefixLookup::Hit(matched) => matched,
273            PrefixLookup::Miss(prefix_hashes) => {
274                let encoding = Encoding::Sp(self.l1.populate_and_encode_with_hashes(
275                    input,
276                    prefix_hashes.into_iter(),
277                    self.inner.as_ref(),
278                )?);
279                self.observe_token_usage(0, encoding.token_ids().len());
280                return Ok(encoding);
281            }
282        };
283
284        let cached_tokens = matched.tokens.len();
285        let encoding = if self.extend_on_hit {
286            Encoding::Sp(self.l1.extend_after_match_with_hash(
287                input,
288                matched,
289                self.inner.as_ref(),
290            )?)
291        } else {
292            let suffix_enc = self.inner.encode(&input[matched.prefix_len..])?;
293            // Reserve once to avoid copying the cached prefix during vector growth.
294            let mut merged: Vec<TokenIdType> =
295                Vec::with_capacity(matched.tokens.len() + suffix_enc.token_ids().len());
296            merged.extend_from_slice(&matched.tokens);
297            merged.extend_from_slice(suffix_enc.token_ids());
298            Encoding::Sp(merged)
299        };
300        self.observe_token_usage(cached_tokens, encoding.token_ids().len());
301        Ok(encoding)
302    }
303
304    fn encode_batch(&self, inputs: &[&str]) -> Result<Vec<Encoding>> {
305        // True passthrough when L1 is disabled — delegate to the inner's native
306        // batch path (which may be rayon-parallel for HF) instead of falling
307        // through per-item.
308        if !self.l1_enabled {
309            return self.inner.encode_batch(inputs);
310        }
311
312        // Per-item cache lookup — do NOT delegate to inner.encode_batch, which would
313        // bypass the cache. Sequential iteration is fine; if rayon is added later it
314        // belongs here, not inside `encode`.
315        inputs.iter().map(|&i| self.encode(i)).collect()
316    }
317
318    fn encode_segments(&self, segments: &[EncodeSegment<'_>]) -> Result<Encoding> {
319        if !self.l1_enabled {
320            return self.inner.encode_segments(segments);
321        }
322
323        // Exactness assumes the inner tokenizer applies no truncation or padding to
324        // the joined ids (HF `post_process` and fastokens `encode_segments` do,
325        // whatever `add_special_tokens` says). Prefix caching relies on the same
326        // assumption: HF rejects caching when either is set, and `FastTokenizer`
327        // drops both at load.
328        let mut ids: Vec<TokenIdType> = Vec::new();
329        let mut cached_tokens = 0;
330        let mut looked_up = false;
331        let mut hit = false;
332        let mut run_start = 0;
333        for (index, segment) in segments.iter().enumerate() {
334            if segment.text.len() < MIN_CACHED_SEGMENT_BYTES {
335                continue;
336            }
337            if run_start < index {
338                let run = self.inner.encode_segments(&segments[run_start..index])?;
339                ids.extend_from_slice(run.token_ids());
340            }
341            run_start = index + 1;
342            looked_up = true;
343            let key = self.l1.segment_key(segment.text, segment.allow_special);
344            if let Some(tokens) = self.l1.get(&key) {
345                hit = true;
346                cached_tokens += tokens.len();
347                ids.extend_from_slice(&tokens);
348            } else {
349                let encoding = self.inner.encode_segments(std::slice::from_ref(segment))?;
350                let tokens: Arc<[TokenIdType]> = encoding.token_ids().into();
351                ids.extend_from_slice(&tokens);
352                self.l1.insert(key, tokens);
353            }
354        }
355        if run_start < segments.len() {
356            let run = self.inner.encode_segments(&segments[run_start..])?;
357            ids.extend_from_slice(run.token_ids());
358        }
359        if looked_up {
360            self.l1.record_lookup(hit);
361        }
362        self.observe_token_usage(cached_tokens, ids.len());
363        Ok(Encoding::Sp(ids))
364    }
365}
366
367impl Decoder for CachedTokenizer {
368    fn has_unstable_suffix(&self, token_ids: &[TokenIdType], skip_special_tokens: bool) -> bool {
369        self.inner
370            .has_unstable_suffix(token_ids, skip_special_tokens)
371    }
372
373    fn decode(&self, token_ids: &[TokenIdType], skip_special_tokens: bool) -> Result<DecodeResult> {
374        // Decode is not cached — passthrough to inner.
375        self.inner.decode(token_ids, skip_special_tokens)
376    }
377}
378
379impl Tokenizer for CachedTokenizer {
380    fn vocab_size(&self) -> Option<usize> {
381        self.inner.vocab_size()
382    }
383
384    fn token_to_id(&self, token: &str) -> Result<Option<TokenIdType>> {
385        self.inner.token_to_id(token)
386    }
387
388    fn special_token_ids(&self) -> Result<Vec<TokenIdType>> {
389        self.inner.special_token_ids()
390    }
391
392    fn num_special_tokens_added(&self) -> Result<usize> {
393        Ok(0)
394    }
395}
396
397#[cfg(test)]
398mod tests {
399    use super::*;
400    use crate::HuggingFaceTokenizer;
401    use std::sync::{Mutex, atomic::AtomicU64, atomic::Ordering};
402    use tokenizers::Tokenizer as HfTokenizer;
403
404    struct FailingTokenizer;
405
406    struct SegmentTokenizer;
407
408    impl Encoder for SegmentTokenizer {
409        fn encode(&self, input: &str) -> Result<Encoding> {
410            Ok(Encoding::Sp(vec![input.len() as u32]))
411        }
412
413        fn encode_batch(&self, inputs: &[&str]) -> Result<Vec<Encoding>> {
414            inputs.iter().map(|input| self.encode(input)).collect()
415        }
416
417        fn encode_segments(&self, segments: &[EncodeSegment<'_>]) -> Result<Encoding> {
418            let ids = segments
419                .iter()
420                .flat_map(|segment| [segment.allow_special as u32, segment.text.len() as u32])
421                .collect();
422            Ok(Encoding::Sp(ids))
423        }
424    }
425
426    impl Decoder for SegmentTokenizer {
427        fn decode(
428            &self,
429            _token_ids: &[TokenIdType],
430            _skip_special_tokens: bool,
431        ) -> Result<DecodeResult> {
432            Ok(DecodeResult::Complete(String::new()))
433        }
434    }
435
436    impl Tokenizer for SegmentTokenizer {
437        fn validate_prefix_cache(&self) -> Result<()> {
438            Ok(())
439        }
440    }
441
442    impl Encoder for FailingTokenizer {
443        fn encode(&self, _input: &str) -> Result<Encoding> {
444            Err(anyhow::anyhow!("intentional encode failure"))
445        }
446
447        fn encode_batch(&self, _inputs: &[&str]) -> Result<Vec<Encoding>> {
448            Err(anyhow::anyhow!("intentional encode failure"))
449        }
450    }
451
452    impl Decoder for FailingTokenizer {
453        fn decode(
454            &self,
455            _token_ids: &[TokenIdType],
456            _skip_special_tokens: bool,
457        ) -> Result<DecodeResult> {
458            Err(anyhow::anyhow!("intentional decode failure"))
459        }
460    }
461
462    impl Tokenizer for FailingTokenizer {
463        fn validate_prefix_cache(&self) -> Result<()> {
464            Ok(())
465        }
466
467        fn vocab_size(&self) -> Option<usize> {
468            None
469        }
470    }
471
472    const TINYLLAMA_PATH: &str = concat!(
473        env!("CARGO_MANIFEST_DIR"),
474        "/tests/data/sample-models/TinyLlama_v1.1/tokenizer.json"
475    );
476
477    fn inner() -> Arc<dyn Tokenizer> {
478        Arc::new(HuggingFaceTokenizer::from_file(TINYLLAMA_PATH).expect("load TinyLlama"))
479    }
480
481    fn specials() -> Vec<String> {
482        vec!["<s>".into(), "</s>".into()]
483    }
484
485    fn collect_token_usage(
486        tokenizer: CachedTokenizer,
487    ) -> (CachedTokenizer, Arc<Mutex<Vec<CacheTokenUsage>>>) {
488        let events = Arc::new(Mutex::new(Vec::new()));
489        let observed = events.clone();
490        let tokenizer = tokenizer.with_token_observer(Arc::new(move |usage| {
491            observed.lock().unwrap().push(usage);
492        }));
493        (tokenizer, events)
494    }
495
496    #[test]
497    fn rejects_hf_tokenizer_that_adds_special_tokens() {
498        let tokenizer: Arc<dyn Tokenizer> = Arc::new(
499            HuggingFaceTokenizer::from_file(TINYLLAMA_PATH)
500                .expect("load TinyLlama")
501                .with_options(crate::TokenizerOptions {
502                    add_special_tokens: true,
503                }),
504        );
505
506        let result = CachedTokenizer::new(tokenizer, specials(), 4096);
507        let Err(error) = result else {
508            panic!("add_special_tokens=true must be rejected");
509        };
510        assert_eq!(
511            error.to_string(),
512            "HuggingFace tokenizers configured with add_special_tokens=true must remain uncached"
513        );
514    }
515
516    #[test]
517    fn empty_specials_passes_through_correctly() {
518        // Empty token strings carry no boundary information and must not make L1 active.
519        let tok = inner();
520        let (cached, events) = collect_token_usage(
521            CachedTokenizer::new(tok.clone(), vec![String::new()], 4096)
522                .expect("TinyLlama must support prefix caching"),
523        );
524        let s = "<s>hello world</s>";
525        let a = cached.encode(s).unwrap();
526        let b = tok.encode(s).unwrap();
527        assert_eq!(a.token_ids(), b.token_ids());
528        let stats = cached.cache_stats();
529        assert_eq!(stats.entries, 0);
530        assert_eq!(stats.misses, 0, "empty specials must not increment misses");
531        assert_eq!(stats.hits, 0);
532        assert!(
533            events.lock().unwrap().is_empty(),
534            "empty specials must not emit token usage"
535        );
536    }
537
538    #[test]
539    fn laguna_overlapping_specials_bypass_cache() {
540        const TOKENIZER_JSON: &str = r#"{
541            "version": "1.0",
542            "truncation": null,
543            "padding": null,
544            "added_tokens": [
545                {"id": 0, "content": "<unk>", "special": true, "single_word": false, "lstrip": false, "rstrip": false, "normalized": false},
546                {"id": 2, "content": "〈|EOS|〉", "special": true, "single_word": false, "lstrip": false, "rstrip": false, "normalized": false},
547                {"id": 14, "content": "〈|", "special": true, "single_word": false, "lstrip": false, "rstrip": false, "normalized": false},
548                {"id": 15, "content": "|〉", "special": true, "single_word": false, "lstrip": false, "rstrip": false, "normalized": false}
549            ],
550            "normalizer": null,
551            "pre_tokenizer": null,
552            "post_processor": null,
553            "decoder": null,
554            "model": {
555                "type": "WordLevel",
556                "vocab": {"<unk>": 0, "〈|EOS|〉": 2, "〈|": 14, "|〉": 15, "tail": 16},
557                "unk_token": "<unk>"
558            }
559        }"#;
560
561        let hf = HfTokenizer::from_bytes(TOKENIZER_JSON).expect("load test tokenizer");
562        let tok: Arc<dyn Tokenizer> = Arc::new(HuggingFaceTokenizer::from_tokenizer(hf));
563        let overlapping = vec!["〈|EOS|〉".into(), "〈|".into(), "|〉".into()];
564        let (cached, events) = collect_token_usage(
565            CachedTokenizer::new(tok.clone(), overlapping, 4096)
566                .expect("HuggingFace tokenizer must support prefix caching"),
567        );
568
569        let expected = tok.encode("〈|EOS|〉").unwrap();
570        assert_eq!(expected.token_ids(), &[2]);
571        assert_eq!(
572            cached.encode("〈|EOS|〉").unwrap().token_ids(),
573            expected.token_ids()
574        );
575        let stats = cached.cache_stats();
576        assert_eq!(stats.entries, 0);
577        assert_eq!(
578            stats.misses, 0,
579            "overlapping specials must not increment misses"
580        );
581        assert_eq!(stats.hits, 0);
582        assert!(
583            events.lock().unwrap().is_empty(),
584            "overlapping specials must not emit token usage"
585        );
586    }
587
588    /// `text` repeated past the segment-caching threshold.
589    fn long_text(text: &str) -> String {
590        text.repeat(MIN_CACHED_SEGMENT_BYTES / text.len() + 1)
591    }
592
593    #[test]
594    fn segmented_encoding_without_specials_passes_through() {
595        let inner: Arc<dyn Tokenizer> = Arc::new(SegmentTokenizer);
596        let user = long_text("user content ");
597        let segments = [
598            EncodeSegment::new("<ctl>", true),
599            EncodeSegment::new(&user, false),
600        ];
601        let expected = inner.encode_segments(&segments).unwrap();
602        let (cached, events) = collect_token_usage(
603            CachedTokenizer::new(inner, Vec::new(), 4096)
604                .expect("test tokenizer supports prefix caching"),
605        );
606
607        for _ in 0..2 {
608            let actual = cached.encode_segments(&segments).unwrap();
609            assert_eq!(actual.token_ids(), expected.token_ids());
610        }
611        let stats = cached.cache_stats();
612        assert_eq!((stats.entries, stats.hits, stats.misses), (0, 0, 0));
613        assert!(events.lock().unwrap().is_empty());
614    }
615
616    #[test]
617    fn segmented_encoding_caches_long_segments_and_matches_inner() {
618        let inner: Arc<dyn Tokenizer> = Arc::new(SegmentTokenizer);
619        let user = long_text("user content ");
620        let tool = long_text("<ctl> tool output ");
621        // The same text with and without allow_special encodes differently, so the
622        // flag must be part of the key; short segments are encoded but never cached.
623        let segments = [
624            EncodeSegment::new("<ctl>", true),
625            EncodeSegment::new(&user, false),
626            EncodeSegment::new("<ctl>", true),
627            EncodeSegment::new("short", false),
628            EncodeSegment::new(&tool, false),
629            EncodeSegment::new(&tool, true),
630            EncodeSegment::new("<ctl>", true),
631        ];
632        let expected = inner.encode_segments(&segments).unwrap();
633        let (cached, events) = collect_token_usage(
634            CachedTokenizer::new(inner.clone(), vec!["<ctl>".to_string()], 4096)
635                .expect("test tokenizer supports prefix caching"),
636        );
637
638        let first = cached.encode_segments(&segments).unwrap();
639        let second = cached.encode_segments(&segments).unwrap();
640        assert_eq!(first.token_ids(), expected.token_ids());
641        assert_eq!(second.token_ids(), expected.token_ids());
642
643        let stats = cached.cache_stats();
644        assert_eq!(stats.entries, 3);
645        assert_eq!((stats.hits, stats.misses), (1, 1));
646        // The mock encodes each segment as two ids, so the three long segments are six.
647        let total = expected.token_ids().len();
648        assert_eq!(
649            events.lock().unwrap().as_slice(),
650            &[
651                CacheTokenUsage {
652                    cached_tokens: 0,
653                    uncached_tokens: total,
654                },
655                CacheTokenUsage {
656                    cached_tokens: 6,
657                    uncached_tokens: total - 6,
658                },
659            ]
660        );
661    }
662
663    #[test]
664    fn segment_entries_do_not_collide_with_prefix_entries() {
665        let inner: Arc<dyn Tokenizer> = Arc::new(SegmentTokenizer);
666        let cached = CachedTokenizer::new(inner.clone(), vec!["<ctl>".to_string()], 4096)
667            .expect("test tokenizer supports prefix caching");
668        // `encode` caches the prefix ending at "<ctl>"; a segment with the same text must
669        // still get the segment encoding, not the prefix entry's tokens.
670        let text = long_text("prefix text ") + "<ctl>";
671        cached.encode(&(text.clone() + " suffix")).unwrap();
672        for allow_special in [false, true] {
673            let segment = [EncodeSegment::new(&text, allow_special)];
674            for _ in 0..2 {
675                assert_eq!(
676                    cached.encode_segments(&segment).unwrap().token_ids(),
677                    inner.encode_segments(&segment).unwrap().token_ids()
678                );
679            }
680        }
681    }
682
683    #[test]
684    fn token_observer_reports_full_miss_and_partial_hit_with_and_without_extension() {
685        for extend_on_hit in [false, true] {
686            let tok = inner();
687            let hits = Arc::new(AtomicU64::new(0));
688            let misses = Arc::new(AtomicU64::new(0));
689            let hit_counter = hits.clone();
690            let miss_counter = misses.clone();
691            let cached = CachedTokenizer::new(tok, specials(), 64 * 1024)
692                .expect("TinyLlama must support prefix caching")
693                .with_extend(extend_on_hit)
694                .with_observer(
695                    Arc::new(move || {
696                        hit_counter.fetch_add(1, Ordering::Relaxed);
697                    }),
698                    Arc::new(move || {
699                        miss_counter.fetch_add(1, Ordering::Relaxed);
700                    }),
701                );
702            let (cached, events) = collect_token_usage(cached);
703
704            let shared = "<s>system\nYou are helpful.</s><s>user\n";
705            let first = format!("{shared}First question?</s>");
706            let second = format!("{shared}Second different prompt entirely.</s>");
707
708            let first_encoding = cached.encode(&first).unwrap();
709            let second_encoding = cached.encode(&second).unwrap();
710
711            let events = events.lock().unwrap();
712            assert_eq!(events.len(), 2);
713            assert_eq!(
714                events[0],
715                CacheTokenUsage {
716                    cached_tokens: 0,
717                    uncached_tokens: first_encoding.token_ids().len(),
718                }
719            );
720            assert!(events[1].cached_tokens > 0);
721            assert!(events[1].uncached_tokens > 0);
722            assert_eq!(
723                events[1].cached_tokens + events[1].uncached_tokens,
724                second_encoding.token_ids().len()
725            );
726            assert_eq!(hits.load(Ordering::Relaxed), 1);
727            assert_eq!(misses.load(Ordering::Relaxed), 1);
728        }
729    }
730
731    #[test]
732    fn token_observer_does_not_report_failed_encodes() {
733        let tokenizer: Arc<dyn Tokenizer> = Arc::new(FailingTokenizer);
734        let (cached, events) = collect_token_usage(
735            CachedTokenizer::new(tokenizer, specials(), 4096)
736                .expect("test tokenizer explicitly supports prefix caching"),
737        );
738
739        assert!(cached.encode("<s>this fails</s>").is_err());
740        assert!(events.lock().unwrap().is_empty());
741    }
742
743    #[test]
744    fn two_turn_chat_correctness_and_hit() {
745        let tok = inner();
746        let cached = CachedTokenizer::new(tok.clone(), specials(), 64 * 1024)
747            .expect("TinyLlama must support prefix caching");
748
749        let template = "<s>system\nYou are helpful.</s><s>user\n";
750        let first = format!("{template}First question?</s>");
751        let second = format!("{template}Second different prompt entirely.</s>");
752
753        // Warm the cache.
754        let _ = cached.encode(&first).unwrap();
755
756        // Second request: shared prefix → L1 hit, suffix-only fresh encode.
757        let cached_second = cached.encode(&second).unwrap();
758        let plain_second = tok.encode(&second).unwrap();
759        assert_eq!(
760            cached_second.token_ids(),
761            plain_second.token_ids(),
762            "cached encode must equal plain encode for second turn"
763        );
764
765        let stats = cached.cache_stats();
766        assert!(stats.hits >= 1, "expected L1 hit on second request");
767    }
768
769    #[test]
770    fn decode_passes_through() {
771        let tok = inner();
772        let cached = CachedTokenizer::new(tok.clone(), specials(), 4096)
773            .expect("TinyLlama must support prefix caching");
774        let enc = cached.encode("<s>hello</s>").unwrap();
775        let direct = tok.decode(enc.token_ids(), false).unwrap();
776        let through = cached.decode(enc.token_ids(), false).unwrap();
777        assert_eq!(direct, through);
778    }
779
780    #[test]
781    fn encode_batch_uses_cache() {
782        let tok = inner();
783        let (cached, events) = collect_token_usage(
784            CachedTokenizer::new(tok.clone(), specials(), 64 * 1024)
785                .expect("TinyLlama must support prefix caching"),
786        );
787        let shared = "<s>system\nShared persona.</s><s>user\n";
788        let inputs = [
789            format!("{shared}q1</s>"),
790            format!("{shared}q2</s>"),
791            format!("{shared}q3</s>"),
792        ];
793        let refs: Vec<&str> = inputs.iter().map(String::as_str).collect();
794        let outs = cached.encode_batch(&refs).unwrap();
795        assert_eq!(outs.len(), 3);
796        let events = events.lock().unwrap();
797        assert_eq!(events.len(), outs.len());
798        for (event, output) in events.iter().zip(&outs) {
799            assert_eq!(
800                event.cached_tokens + event.uncached_tokens,
801                output.token_ids().len()
802            );
803        }
804        assert_eq!(events[0].cached_tokens, 0);
805        assert!(events[1..].iter().all(|event| event.cached_tokens > 0));
806        // First call populates, second/third hit.
807        assert!(cached.cache_stats().hits >= 2, "expected hits on q2 and q3");
808    }
809
810    #[test]
811    fn vocab_introspection_forwards_to_inner() {
812        let tok = inner();
813        let cached = CachedTokenizer::new(tok.clone(), specials(), 4096)
814            .expect("TinyLlama must support prefix caching");
815        assert_eq!(cached.vocab_size(), tok.vocab_size());
816        assert_eq!(
817            cached.token_to_id("<s>").unwrap(),
818            tok.token_to_id("<s>").unwrap()
819        );
820        assert_eq!(
821            cached.special_token_ids().unwrap(),
822            tok.special_token_ids().unwrap()
823        );
824    }
825
826    #[test]
827    fn special_token_accounting_matches_cached_encoder_behavior() {
828        let cached = CachedTokenizer::new(inner(), specials(), 4096)
829            .expect("TinyLlama must support prefix caching")
830            .with_options(crate::TokenizerOptions {
831                add_special_tokens: true,
832            });
833        let cached_ids = cached.encode("hello").unwrap();
834        let hf_ids = HuggingFaceTokenizer::from_file(TINYLLAMA_PATH)
835            .expect("load TinyLlama")
836            .with_options(crate::TokenizerOptions {
837                add_special_tokens: true,
838            })
839            .encode("hello")
840            .unwrap();
841
842        assert_eq!(cached.num_special_tokens_added().unwrap(), 0);
843        assert_eq!(hf_ids.token_ids().len(), cached_ids.token_ids().len() + 1);
844        assert_eq!(&hf_ids.token_ids()[1..], cached_ids.token_ids());
845    }
846
847    #[test]
848    fn unoverridden_introspection_methods_use_defaults() {
849        let tokenizer = SegmentTokenizer;
850        assert_eq!(tokenizer.vocab_size(), None);
851        assert!(tokenizer.token_to_id("anything").is_err());
852        assert!(tokenizer.special_token_ids().is_err());
853        assert!(tokenizer.num_special_tokens_added().is_err());
854    }
855}