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; Dynamo strips both from HF tokenizers at load.
327        let mut ids: Vec<TokenIdType> = Vec::new();
328        let mut cached_tokens = 0;
329        let mut looked_up = false;
330        let mut hit = false;
331        let mut run_start = 0;
332        for (index, segment) in segments.iter().enumerate() {
333            if segment.text.len() < MIN_CACHED_SEGMENT_BYTES {
334                continue;
335            }
336            if run_start < index {
337                let run = self.inner.encode_segments(&segments[run_start..index])?;
338                ids.extend_from_slice(run.token_ids());
339            }
340            run_start = index + 1;
341            looked_up = true;
342            let key = self.l1.segment_key(segment.text, segment.allow_special);
343            if let Some(tokens) = self.l1.get(&key) {
344                hit = true;
345                cached_tokens += tokens.len();
346                ids.extend_from_slice(&tokens);
347            } else {
348                let encoding = self.inner.encode_segments(std::slice::from_ref(segment))?;
349                let tokens: Arc<[TokenIdType]> = encoding.token_ids().into();
350                ids.extend_from_slice(&tokens);
351                self.l1.insert(key, tokens);
352            }
353        }
354        if run_start < segments.len() {
355            let run = self.inner.encode_segments(&segments[run_start..])?;
356            ids.extend_from_slice(run.token_ids());
357        }
358        if looked_up {
359            self.l1.record_lookup(hit);
360        }
361        self.observe_token_usage(cached_tokens, ids.len());
362        Ok(Encoding::Sp(ids))
363    }
364}
365
366impl Decoder for CachedTokenizer {
367    fn has_unstable_suffix(&self, token_ids: &[TokenIdType], skip_special_tokens: bool) -> bool {
368        self.inner
369            .has_unstable_suffix(token_ids, skip_special_tokens)
370    }
371
372    fn decode(&self, token_ids: &[TokenIdType], skip_special_tokens: bool) -> Result<DecodeResult> {
373        // Decode is not cached — passthrough to inner.
374        self.inner.decode(token_ids, skip_special_tokens)
375    }
376}
377
378impl Tokenizer for CachedTokenizer {
379    fn vocab_size(&self) -> Option<usize> {
380        self.inner.vocab_size()
381    }
382
383    fn token_to_id(&self, token: &str) -> Result<Option<TokenIdType>> {
384        self.inner.token_to_id(token)
385    }
386
387    fn special_token_ids(&self) -> Result<Vec<TokenIdType>> {
388        self.inner.special_token_ids()
389    }
390
391    fn num_special_tokens_added(&self) -> Result<usize> {
392        Ok(0)
393    }
394}
395
396#[cfg(test)]
397mod tests {
398    use super::*;
399    use crate::HuggingFaceTokenizer;
400    use std::sync::{Mutex, atomic::AtomicU64, atomic::Ordering};
401    use tokenizers::Tokenizer as HfTokenizer;
402
403    struct FailingTokenizer;
404
405    struct SegmentTokenizer;
406
407    impl Encoder for SegmentTokenizer {
408        fn encode(&self, input: &str) -> Result<Encoding> {
409            Ok(Encoding::Sp(vec![input.len() as u32]))
410        }
411
412        fn encode_batch(&self, inputs: &[&str]) -> Result<Vec<Encoding>> {
413            inputs.iter().map(|input| self.encode(input)).collect()
414        }
415
416        fn encode_segments(&self, segments: &[EncodeSegment<'_>]) -> Result<Encoding> {
417            let ids = segments
418                .iter()
419                .flat_map(|segment| [segment.allow_special as u32, segment.text.len() as u32])
420                .collect();
421            Ok(Encoding::Sp(ids))
422        }
423    }
424
425    impl Decoder for SegmentTokenizer {
426        fn decode(
427            &self,
428            _token_ids: &[TokenIdType],
429            _skip_special_tokens: bool,
430        ) -> Result<DecodeResult> {
431            Ok(DecodeResult::Complete(String::new()))
432        }
433    }
434
435    impl Tokenizer for SegmentTokenizer {
436        fn validate_prefix_cache(&self) -> Result<()> {
437            Ok(())
438        }
439    }
440
441    impl Encoder for FailingTokenizer {
442        fn encode(&self, _input: &str) -> Result<Encoding> {
443            Err(anyhow::anyhow!("intentional encode failure"))
444        }
445
446        fn encode_batch(&self, _inputs: &[&str]) -> Result<Vec<Encoding>> {
447            Err(anyhow::anyhow!("intentional encode failure"))
448        }
449    }
450
451    impl Decoder for FailingTokenizer {
452        fn decode(
453            &self,
454            _token_ids: &[TokenIdType],
455            _skip_special_tokens: bool,
456        ) -> Result<DecodeResult> {
457            Err(anyhow::anyhow!("intentional decode failure"))
458        }
459    }
460
461    impl Tokenizer for FailingTokenizer {
462        fn validate_prefix_cache(&self) -> Result<()> {
463            Ok(())
464        }
465
466        fn vocab_size(&self) -> Option<usize> {
467            None
468        }
469    }
470
471    const TINYLLAMA_PATH: &str = concat!(
472        env!("CARGO_MANIFEST_DIR"),
473        "/tests/data/sample-models/TinyLlama_v1.1/tokenizer.json"
474    );
475
476    fn inner() -> Arc<dyn Tokenizer> {
477        Arc::new(HuggingFaceTokenizer::from_file(TINYLLAMA_PATH).expect("load TinyLlama"))
478    }
479
480    fn specials() -> Vec<String> {
481        vec!["<s>".into(), "</s>".into()]
482    }
483
484    fn collect_token_usage(
485        tokenizer: CachedTokenizer,
486    ) -> (CachedTokenizer, Arc<Mutex<Vec<CacheTokenUsage>>>) {
487        let events = Arc::new(Mutex::new(Vec::new()));
488        let observed = events.clone();
489        let tokenizer = tokenizer.with_token_observer(Arc::new(move |usage| {
490            observed.lock().unwrap().push(usage);
491        }));
492        (tokenizer, events)
493    }
494
495    #[test]
496    fn rejects_hf_tokenizer_that_adds_special_tokens() {
497        let tokenizer: Arc<dyn Tokenizer> = Arc::new(
498            HuggingFaceTokenizer::from_file(TINYLLAMA_PATH)
499                .expect("load TinyLlama")
500                .with_options(crate::TokenizerOptions {
501                    add_special_tokens: true,
502                }),
503        );
504
505        let result = CachedTokenizer::new(tokenizer, specials(), 4096);
506        let Err(error) = result else {
507            panic!("add_special_tokens=true must be rejected");
508        };
509        assert_eq!(
510            error.to_string(),
511            "HuggingFace tokenizers configured with add_special_tokens=true must remain uncached"
512        );
513    }
514
515    #[test]
516    fn empty_specials_passes_through_correctly() {
517        // Empty token strings carry no boundary information and must not make L1 active.
518        let tok = inner();
519        let (cached, events) = collect_token_usage(
520            CachedTokenizer::new(tok.clone(), vec![String::new()], 4096)
521                .expect("TinyLlama must support prefix caching"),
522        );
523        let s = "<s>hello world</s>";
524        let a = cached.encode(s).unwrap();
525        let b = tok.encode(s).unwrap();
526        assert_eq!(a.token_ids(), b.token_ids());
527        let stats = cached.cache_stats();
528        assert_eq!(stats.entries, 0);
529        assert_eq!(stats.misses, 0, "empty specials must not increment misses");
530        assert_eq!(stats.hits, 0);
531        assert!(
532            events.lock().unwrap().is_empty(),
533            "empty specials must not emit token usage"
534        );
535    }
536
537    #[test]
538    fn laguna_overlapping_specials_bypass_cache() {
539        const TOKENIZER_JSON: &str = r#"{
540            "version": "1.0",
541            "truncation": null,
542            "padding": null,
543            "added_tokens": [
544                {"id": 0, "content": "<unk>", "special": true, "single_word": false, "lstrip": false, "rstrip": false, "normalized": false},
545                {"id": 2, "content": "〈|EOS|〉", "special": true, "single_word": false, "lstrip": false, "rstrip": false, "normalized": false},
546                {"id": 14, "content": "〈|", "special": true, "single_word": false, "lstrip": false, "rstrip": false, "normalized": false},
547                {"id": 15, "content": "|〉", "special": true, "single_word": false, "lstrip": false, "rstrip": false, "normalized": false}
548            ],
549            "normalizer": null,
550            "pre_tokenizer": null,
551            "post_processor": null,
552            "decoder": null,
553            "model": {
554                "type": "WordLevel",
555                "vocab": {"<unk>": 0, "〈|EOS|〉": 2, "〈|": 14, "|〉": 15, "tail": 16},
556                "unk_token": "<unk>"
557            }
558        }"#;
559
560        let hf = HfTokenizer::from_bytes(TOKENIZER_JSON).expect("load test tokenizer");
561        let tok: Arc<dyn Tokenizer> = Arc::new(HuggingFaceTokenizer::from_tokenizer(hf));
562        let overlapping = vec!["〈|EOS|〉".into(), "〈|".into(), "|〉".into()];
563        let (cached, events) = collect_token_usage(
564            CachedTokenizer::new(tok.clone(), overlapping, 4096)
565                .expect("HuggingFace tokenizer must support prefix caching"),
566        );
567
568        let expected = tok.encode("〈|EOS|〉").unwrap();
569        assert_eq!(expected.token_ids(), &[2]);
570        assert_eq!(
571            cached.encode("〈|EOS|〉").unwrap().token_ids(),
572            expected.token_ids()
573        );
574        let stats = cached.cache_stats();
575        assert_eq!(stats.entries, 0);
576        assert_eq!(
577            stats.misses, 0,
578            "overlapping specials must not increment misses"
579        );
580        assert_eq!(stats.hits, 0);
581        assert!(
582            events.lock().unwrap().is_empty(),
583            "overlapping specials must not emit token usage"
584        );
585    }
586
587    /// `text` repeated past the segment-caching threshold.
588    fn long_text(text: &str) -> String {
589        text.repeat(MIN_CACHED_SEGMENT_BYTES / text.len() + 1)
590    }
591
592    #[test]
593    fn segmented_encoding_without_specials_passes_through() {
594        let inner: Arc<dyn Tokenizer> = Arc::new(SegmentTokenizer);
595        let user = long_text("user content ");
596        let segments = [
597            EncodeSegment::new("<ctl>", true),
598            EncodeSegment::new(&user, false),
599        ];
600        let expected = inner.encode_segments(&segments).unwrap();
601        let (cached, events) = collect_token_usage(
602            CachedTokenizer::new(inner, Vec::new(), 4096)
603                .expect("test tokenizer supports prefix caching"),
604        );
605
606        for _ in 0..2 {
607            let actual = cached.encode_segments(&segments).unwrap();
608            assert_eq!(actual.token_ids(), expected.token_ids());
609        }
610        let stats = cached.cache_stats();
611        assert_eq!((stats.entries, stats.hits, stats.misses), (0, 0, 0));
612        assert!(events.lock().unwrap().is_empty());
613    }
614
615    #[test]
616    fn segmented_encoding_caches_long_segments_and_matches_inner() {
617        let inner: Arc<dyn Tokenizer> = Arc::new(SegmentTokenizer);
618        let user = long_text("user content ");
619        let tool = long_text("<ctl> tool output ");
620        // The same text with and without allow_special encodes differently, so the
621        // flag must be part of the key; short segments are encoded but never cached.
622        let segments = [
623            EncodeSegment::new("<ctl>", true),
624            EncodeSegment::new(&user, false),
625            EncodeSegment::new("<ctl>", true),
626            EncodeSegment::new("short", false),
627            EncodeSegment::new(&tool, false),
628            EncodeSegment::new(&tool, true),
629            EncodeSegment::new("<ctl>", true),
630        ];
631        let expected = inner.encode_segments(&segments).unwrap();
632        let (cached, events) = collect_token_usage(
633            CachedTokenizer::new(inner.clone(), vec!["<ctl>".to_string()], 4096)
634                .expect("test tokenizer supports prefix caching"),
635        );
636
637        let first = cached.encode_segments(&segments).unwrap();
638        let second = cached.encode_segments(&segments).unwrap();
639        assert_eq!(first.token_ids(), expected.token_ids());
640        assert_eq!(second.token_ids(), expected.token_ids());
641
642        let stats = cached.cache_stats();
643        assert_eq!(stats.entries, 3);
644        assert_eq!((stats.hits, stats.misses), (1, 1));
645        // The mock encodes each segment as two ids, so the three long segments are six.
646        let total = expected.token_ids().len();
647        assert_eq!(
648            events.lock().unwrap().as_slice(),
649            &[
650                CacheTokenUsage {
651                    cached_tokens: 0,
652                    uncached_tokens: total,
653                },
654                CacheTokenUsage {
655                    cached_tokens: 6,
656                    uncached_tokens: total - 6,
657                },
658            ]
659        );
660    }
661
662    #[test]
663    fn segment_entries_do_not_collide_with_prefix_entries() {
664        let inner: Arc<dyn Tokenizer> = Arc::new(SegmentTokenizer);
665        let cached = CachedTokenizer::new(inner.clone(), vec!["<ctl>".to_string()], 4096)
666            .expect("test tokenizer supports prefix caching");
667        // `encode` caches the prefix ending at "<ctl>"; a segment with the same text must
668        // still get the segment encoding, not the prefix entry's tokens.
669        let text = long_text("prefix text ") + "<ctl>";
670        cached.encode(&(text.clone() + " suffix")).unwrap();
671        for allow_special in [false, true] {
672            let segment = [EncodeSegment::new(&text, allow_special)];
673            for _ in 0..2 {
674                assert_eq!(
675                    cached.encode_segments(&segment).unwrap().token_ids(),
676                    inner.encode_segments(&segment).unwrap().token_ids()
677                );
678            }
679        }
680    }
681
682    #[test]
683    fn token_observer_reports_full_miss_and_partial_hit_with_and_without_extension() {
684        for extend_on_hit in [false, true] {
685            let tok = inner();
686            let hits = Arc::new(AtomicU64::new(0));
687            let misses = Arc::new(AtomicU64::new(0));
688            let hit_counter = hits.clone();
689            let miss_counter = misses.clone();
690            let cached = CachedTokenizer::new(tok, specials(), 64 * 1024)
691                .expect("TinyLlama must support prefix caching")
692                .with_extend(extend_on_hit)
693                .with_observer(
694                    Arc::new(move || {
695                        hit_counter.fetch_add(1, Ordering::Relaxed);
696                    }),
697                    Arc::new(move || {
698                        miss_counter.fetch_add(1, Ordering::Relaxed);
699                    }),
700                );
701            let (cached, events) = collect_token_usage(cached);
702
703            let shared = "<s>system\nYou are helpful.</s><s>user\n";
704            let first = format!("{shared}First question?</s>");
705            let second = format!("{shared}Second different prompt entirely.</s>");
706
707            let first_encoding = cached.encode(&first).unwrap();
708            let second_encoding = cached.encode(&second).unwrap();
709
710            let events = events.lock().unwrap();
711            assert_eq!(events.len(), 2);
712            assert_eq!(
713                events[0],
714                CacheTokenUsage {
715                    cached_tokens: 0,
716                    uncached_tokens: first_encoding.token_ids().len(),
717                }
718            );
719            assert!(events[1].cached_tokens > 0);
720            assert!(events[1].uncached_tokens > 0);
721            assert_eq!(
722                events[1].cached_tokens + events[1].uncached_tokens,
723                second_encoding.token_ids().len()
724            );
725            assert_eq!(hits.load(Ordering::Relaxed), 1);
726            assert_eq!(misses.load(Ordering::Relaxed), 1);
727        }
728    }
729
730    #[test]
731    fn token_observer_does_not_report_failed_encodes() {
732        let tokenizer: Arc<dyn Tokenizer> = Arc::new(FailingTokenizer);
733        let (cached, events) = collect_token_usage(
734            CachedTokenizer::new(tokenizer, specials(), 4096)
735                .expect("test tokenizer explicitly supports prefix caching"),
736        );
737
738        assert!(cached.encode("<s>this fails</s>").is_err());
739        assert!(events.lock().unwrap().is_empty());
740    }
741
742    #[test]
743    fn two_turn_chat_correctness_and_hit() {
744        let tok = inner();
745        let cached = CachedTokenizer::new(tok.clone(), specials(), 64 * 1024)
746            .expect("TinyLlama must support prefix caching");
747
748        let template = "<s>system\nYou are helpful.</s><s>user\n";
749        let first = format!("{template}First question?</s>");
750        let second = format!("{template}Second different prompt entirely.</s>");
751
752        // Warm the cache.
753        let _ = cached.encode(&first).unwrap();
754
755        // Second request: shared prefix → L1 hit, suffix-only fresh encode.
756        let cached_second = cached.encode(&second).unwrap();
757        let plain_second = tok.encode(&second).unwrap();
758        assert_eq!(
759            cached_second.token_ids(),
760            plain_second.token_ids(),
761            "cached encode must equal plain encode for second turn"
762        );
763
764        let stats = cached.cache_stats();
765        assert!(stats.hits >= 1, "expected L1 hit on second request");
766    }
767
768    #[test]
769    fn decode_passes_through() {
770        let tok = inner();
771        let cached = CachedTokenizer::new(tok.clone(), specials(), 4096)
772            .expect("TinyLlama must support prefix caching");
773        let enc = cached.encode("<s>hello</s>").unwrap();
774        let direct = tok.decode(enc.token_ids(), false).unwrap();
775        let through = cached.decode(enc.token_ids(), false).unwrap();
776        assert_eq!(direct, through);
777    }
778
779    #[test]
780    fn encode_batch_uses_cache() {
781        let tok = inner();
782        let (cached, events) = collect_token_usage(
783            CachedTokenizer::new(tok.clone(), specials(), 64 * 1024)
784                .expect("TinyLlama must support prefix caching"),
785        );
786        let shared = "<s>system\nShared persona.</s><s>user\n";
787        let inputs = [
788            format!("{shared}q1</s>"),
789            format!("{shared}q2</s>"),
790            format!("{shared}q3</s>"),
791        ];
792        let refs: Vec<&str> = inputs.iter().map(String::as_str).collect();
793        let outs = cached.encode_batch(&refs).unwrap();
794        assert_eq!(outs.len(), 3);
795        let events = events.lock().unwrap();
796        assert_eq!(events.len(), outs.len());
797        for (event, output) in events.iter().zip(&outs) {
798            assert_eq!(
799                event.cached_tokens + event.uncached_tokens,
800                output.token_ids().len()
801            );
802        }
803        assert_eq!(events[0].cached_tokens, 0);
804        assert!(events[1..].iter().all(|event| event.cached_tokens > 0));
805        // First call populates, second/third hit.
806        assert!(cached.cache_stats().hits >= 2, "expected hits on q2 and q3");
807    }
808
809    #[test]
810    fn vocab_introspection_forwards_to_inner() {
811        let tok = inner();
812        let cached = CachedTokenizer::new(tok.clone(), specials(), 4096)
813            .expect("TinyLlama must support prefix caching");
814        assert_eq!(cached.vocab_size(), tok.vocab_size());
815        assert_eq!(
816            cached.token_to_id("<s>").unwrap(),
817            tok.token_to_id("<s>").unwrap()
818        );
819        assert_eq!(
820            cached.special_token_ids().unwrap(),
821            tok.special_token_ids().unwrap()
822        );
823    }
824
825    #[test]
826    fn special_token_accounting_matches_cached_encoder_behavior() {
827        let cached = CachedTokenizer::new(inner(), specials(), 4096)
828            .expect("TinyLlama must support prefix caching")
829            .with_options(crate::TokenizerOptions {
830                add_special_tokens: true,
831            });
832        let cached_ids = cached.encode("hello").unwrap();
833        let hf_ids = HuggingFaceTokenizer::from_file(TINYLLAMA_PATH)
834            .expect("load TinyLlama")
835            .with_options(crate::TokenizerOptions {
836                add_special_tokens: true,
837            })
838            .encode("hello")
839            .unwrap();
840
841        assert_eq!(cached.num_special_tokens_added().unwrap(), 0);
842        assert_eq!(hf_ids.token_ids().len(), cached_ids.token_ids().len() + 1);
843        assert_eq!(&hf_ids.token_ids()[1..], cached_ids.token_ids());
844    }
845
846    #[test]
847    fn unoverridden_introspection_methods_use_defaults() {
848        let tokenizer = SegmentTokenizer;
849        assert_eq!(tokenizer.vocab_size(), None);
850        assert!(tokenizer.token_to_id("anything").is_err());
851        assert!(tokenizer.special_token_ids().is_err());
852        assert!(tokenizer.num_special_tokens_added().is_err());
853    }
854}