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//! - A segment that allows special tokens also shares `encode`'s prefix entries, where
60//!   the backend encodes it as `encode` does its text
61//!   ([`Tokenizer::validate_segment_prefix_cache`]). A prompt's last such segment grows
62//!   with the conversation, so it is looked up by prefix only; an earlier one that misses
63//!   by its exact text continues from its longest cached prefix.
64//! - `max_memory_bytes` — token-ID payload byte budget, excluding keys and metadata.
65//!   Moka shares admission and eviction via W-TinyLFU. Deferred maintenance makes the
66//!   capacity approximate; it is not a limit on total process memory.
67//! - [`CachedTokenizer::new`] owns a private cache. [`CachedTokenizer::new_with_cache`]
68//!   shares storage across wrappers; entries survive a wrapper being dropped while
69//!   shared storage remains alive. Equal namespaces must identify identical tokenizer
70//!   behavior, including tokenizer files, backend, and options that affect token IDs.
71//!
72//! # Provenance
73//!
74//! Adapted from `llm-tokenizer` v1.3.2 (`cache/l1.rs`, `cache/mod.rs`). L0 and
75//! upstream fingerprinting were dropped; L1 covers the multi-turn-chat workload.
76//! Shared caches use caller-supplied namespaces to separate tokenizer identities.
77
78mod l1;
79
80use std::sync::Arc;
81
82use l1::PrefixLookup;
83pub use l1::{
84    CacheEventFn, L1Cache, L1CacheStats, SharedTokenizerCache, SharedTokenizerCacheStats,
85};
86
87use crate::{
88    EncodeSegment, Encoding, Result, TokenIdType,
89    traits::{DecodeResult, Decoder, Encoder, Tokenizer},
90};
91
92/// Smallest segment (in bytes) that [`CachedTokenizer::encode_segments`] caches.
93/// Shorter segments, such as control markers, encode faster than an entry pays off.
94const MIN_CACHED_SEGMENT_BYTES: usize = 128;
95
96/// Token-level cache usage for one successful encode.
97///
98/// A partial cache hit reports both cached prefix tokens and uncached suffix tokens.
99/// Their sum always equals the number of tokens returned by the encode operation.
100#[derive(Debug, Clone, Copy, PartialEq, Eq)]
101pub struct CacheTokenUsage {
102    /// Tokens returned from the cached prefix.
103    pub cached_tokens: usize,
104    /// Tokens freshly encoded from the uncached suffix.
105    pub uncached_tokens: usize,
106}
107
108/// Optional observer for token-level cache usage.
109pub type CacheTokenUsageFn = Arc<dyn Fn(CacheTokenUsage) + Send + Sync>;
110
111/// Caching wrapper around an inner tokenizer.
112///
113/// Implements [`Encoder`], [`Decoder`], and [`Tokenizer`]; decode calls pass
114/// through to the inner tokenizer (decoding is fast and rarely repeated).
115pub struct CachedTokenizer {
116    inner: Arc<dyn Tokenizer>,
117    l1: L1Cache,
118    l1_enabled: bool,
119    /// Segments that allow special tokens share `encode`'s prefix entries.
120    segment_prefixes: bool,
121    extend_on_hit: bool,
122    /// Called once after every successful encode while L1 is active.
123    token_observer: Option<CacheTokenUsageFn>,
124}
125
126impl CachedTokenizer {
127    /// Construct a cached tokenizer.
128    ///
129    /// `special_tokens` is the list of atomic special-token strings the inner
130    /// tokenizer recognizes (typically extracted via the HuggingFace tokenizer's
131    /// `get_added_tokens_decoder()` filtering by `special == true`). An empty list
132    /// disables L1 — `encode`/`encode_batch` short-circuit to the inner tokenizer
133    /// without touching the cache or its counters. An overlapping token set also disables
134    /// L1, with a warning, because its boundaries are ambiguous.
135    ///
136    /// `max_memory_bytes` is the private token-ID payload byte budget. Moka defers
137    /// eviction, so the budget is approximate and excludes keys and metadata.
138    ///
139    /// # Errors
140    ///
141    /// Returns the inner tokenizer's compatibility error when it cannot be
142    /// safely wrapped in the prefix cache.
143    pub fn new(
144        inner: Arc<dyn Tokenizer>,
145        special_tokens: Vec<String>,
146        max_memory_bytes: usize,
147    ) -> Result<Self> {
148        Self::build(inner, special_tokens, |tokens| {
149            L1Cache::new(max_memory_bytes, tokens)
150        })
151    }
152
153    /// Construct a tokenizer using shared storage and a caller-supplied namespace.
154    ///
155    /// Equal namespaces share entries and must describe identical tokenizer behavior,
156    /// including tokenizer files, backend, and encoding options. Different namespaces
157    /// compete for the same byte budget but cannot reuse each other's token IDs.
158    /// Entries survive this wrapper being dropped while the shared cache remains alive.
159    /// The eligibility checks are the same as [`Self::new`].
160    ///
161    /// # Errors
162    ///
163    /// Returns the inner tokenizer's compatibility error if prefix caching is unsafe.
164    pub fn new_with_cache(
165        inner: Arc<dyn Tokenizer>,
166        special_tokens: Vec<String>,
167        shared_cache: SharedTokenizerCache,
168        namespace: &[u8],
169    ) -> Result<Self> {
170        Self::build(inner, special_tokens, |tokens| {
171            L1Cache::new_with_cache(shared_cache, tokens, namespace)
172        })
173    }
174
175    fn build(
176        inner: Arc<dyn Tokenizer>,
177        mut special_tokens: Vec<String>,
178        make_cache: impl FnOnce(Vec<String>) -> L1Cache,
179    ) -> Result<Self> {
180        inner.validate_prefix_cache()?;
181        special_tokens.retain(|token| !token.is_empty());
182
183        // Overlapping matches can create a cache boundary inside a token selected by the
184        // inner tokenizer. Preserve correctness by bypassing this optional optimization.
185        let overlapping_specials = match l1::first_unsafe_overlap(&special_tokens) {
186            Some((first, second)) => {
187                tracing::warn!(
188                    target: "tokenizer",
189                    first_token = first,
190                    second_token = second,
191                    special_token_count = special_tokens.len(),
192                    "special tokens can overlap; tokenizer prefix cache disabled"
193                );
194                true
195            }
196            None => false,
197        };
198
199        let l1_enabled = !special_tokens.is_empty() && !overlapping_specials;
200        let cache_tokens = if l1_enabled {
201            special_tokens
202        } else {
203            Vec::new()
204        };
205        let segment_prefixes = l1_enabled && inner.validate_segment_prefix_cache().is_ok();
206        Ok(Self {
207            inner,
208            l1: make_cache(cache_tokens),
209            l1_enabled,
210            segment_prefixes,
211            extend_on_hit: false,
212            token_observer: None,
213        })
214    }
215
216    /// Enable partial-hit extension. When on, a partial cache hit also caches the
217    /// freshly-tokenized suffix at its deepest special-token boundary, so each turn of
218    /// a growing multi-turn conversation hits deeper than the last and per-turn
219    /// tokenization cost stops growing with conversation length. Default off.
220    pub fn with_extend(mut self, enabled: bool) -> Self {
221        self.extend_on_hit = enabled;
222        self
223    }
224
225    /// Install hit/miss callbacks so each L1 lookup pushes an event into the
226    /// supplied closures (e.g. `Prometheus::Counter::inc`). Replaces any
227    /// previously-set observer.
228    pub fn with_observer(mut self, on_hit: CacheEventFn, on_miss: CacheEventFn) -> Self {
229        self.l1.set_observer(on_hit, on_miss);
230        self
231    }
232
233    /// Install a callback that receives exact cached and uncached token counts after each
234    /// successful encode while L1 is active. A partial hit reports both categories, which
235    /// lets consumers maintain token-level cache totals and derive a reuse ratio. Replaces
236    /// any previously-set token observer.
237    ///
238    /// This observer is not called when the special-token set is empty (and L1 is therefore
239    /// disabled) or when encoding returns an error.
240    pub fn with_token_observer(mut self, observer: CacheTokenUsageFn) -> Self {
241        self.token_observer = Some(observer);
242        self
243    }
244
245    fn observe_token_usage(&self, cached_tokens: usize, total_tokens: usize) {
246        if let Some(observer) = &self.token_observer {
247            let uncached_tokens = total_tokens
248                .checked_sub(cached_tokens)
249                .expect("cached token count cannot exceed total token count");
250            observer(CacheTokenUsage {
251                cached_tokens,
252                uncached_tokens,
253            });
254        }
255    }
256
257    /// The tokens of `input` after `lookup`, which must be this input's, and how many
258    /// of them the cache held.
259    fn encode_after_lookup(
260        &self,
261        input: &str,
262        lookup: PrefixLookup,
263    ) -> Result<(Vec<TokenIdType>, usize)> {
264        let matched = match lookup {
265            PrefixLookup::Hit(matched) => matched,
266            PrefixLookup::Miss(prefix_hashes) => {
267                let ids = self.l1.populate_and_encode_with_hashes(
268                    input,
269                    prefix_hashes.into_iter(),
270                    self.inner.as_ref(),
271                )?;
272                return Ok((ids, 0));
273            }
274        };
275
276        let cached_tokens = matched.tokens.len();
277        let ids = if self.extend_on_hit {
278            self.l1
279                .extend_after_match_with_hash(input, matched, self.inner.as_ref())?
280        } else {
281            let suffix_enc = self.inner.encode(&input[matched.prefix_len..])?;
282            // Reserve once to avoid copying the cached prefix during vector growth.
283            let mut merged: Vec<TokenIdType> =
284                Vec::with_capacity(matched.tokens.len() + suffix_enc.token_ids().len());
285            merged.extend_from_slice(&matched.tokens);
286            merged.extend_from_slice(suffix_enc.token_ids());
287            merged
288        };
289        Ok((ids, cached_tokens))
290    }
291
292    /// Wrapper-local hits/misses and namespace-wide entries/token bytes.
293    /// Shared storage statistics scan the namespace; private caches use Moka's totals.
294    /// Results can change under concurrent writes. Disabled wrappers report zeroes.
295    pub fn cache_stats(&self) -> L1CacheStats {
296        if self.l1_enabled {
297            self.l1.stats()
298        } else {
299            L1CacheStats::default()
300        }
301    }
302
303    /// Access the underlying tokenizer (e.g. for downcasting to a concrete type).
304    pub fn inner(&self) -> &Arc<dyn Tokenizer> {
305        &self.inner
306    }
307}
308
309impl Encoder for CachedTokenizer {
310    fn encode(&self, input: &str) -> Result<Encoding> {
311        if !self.l1_enabled {
312            return self.inner.encode(input);
313        }
314
315        let (ids, cached_tokens) = self.encode_after_lookup(input, self.l1.lookup_prefix(input))?;
316        self.observe_token_usage(cached_tokens, ids.len());
317        Ok(Encoding::Sp(ids))
318    }
319
320    fn encode_batch(&self, inputs: &[&str]) -> Result<Vec<Encoding>> {
321        // True passthrough when L1 is disabled — delegate to the inner's native
322        // batch path (which may be rayon-parallel for HF) instead of falling
323        // through per-item.
324        if !self.l1_enabled {
325            return self.inner.encode_batch(inputs);
326        }
327
328        // Per-item cache lookup — do NOT delegate to inner.encode_batch, which would
329        // bypass the cache. Sequential iteration is fine; if rayon is added later it
330        // belongs here, not inside `encode`.
331        inputs.iter().map(|&i| self.encode(i)).collect()
332    }
333
334    fn encode_segments(&self, segments: &[EncodeSegment<'_>]) -> Result<Encoding> {
335        if !self.l1_enabled {
336            return self.inner.encode_segments(segments);
337        }
338
339        // Exactness assumes the inner tokenizer applies no truncation or padding to
340        // the joined ids (HF `post_process` and fastokens `encode_segments` do,
341        // whatever `add_special_tokens` says). Prefix caching relies on the same
342        // assumption: HF rejects caching when either is set, and `FastTokenizer`
343        // drops both at load.
344        let mut ids: Vec<TokenIdType> = Vec::new();
345        let mut cached_tokens = 0;
346        let mut looked_up = false;
347        let mut hit = false;
348        let mut run_start = 0;
349        for (index, segment) in segments.iter().enumerate() {
350            if segment.text.len() < MIN_CACHED_SEGMENT_BYTES {
351                continue;
352            }
353            if run_start < index {
354                let run = self.inner.encode_segments(&segments[run_start..index])?;
355                ids.extend_from_slice(run.token_ids());
356            }
357            run_start = index + 1;
358            looked_up = true;
359            let by_prefix = self.segment_prefixes && segment.allow_special;
360            if by_prefix && index + 1 == segments.len() {
361                // The prompt's last segment grows with the conversation: only a
362                // prefix of it repeats, and the whole is not worth an entry.
363                let lookup = self.l1.find_prefix(segment.text);
364                let (tokens, cached) = self.encode_after_lookup(segment.text, lookup)?;
365                hit |= cached > 0;
366                cached_tokens += cached;
367                ids.extend_from_slice(&tokens);
368                continue;
369            }
370            let key = self.l1.segment_key(segment.text, segment.allow_special);
371            if let Some(tokens) = self.l1.get(&key) {
372                hit = true;
373                cached_tokens += tokens.len();
374                ids.extend_from_slice(&tokens);
375            } else {
376                let tokens: Arc<[TokenIdType]> = if by_prefix {
377                    // It may have grown as the last segment of earlier prompts.
378                    let lookup = self.l1.find_prefix(segment.text);
379                    let (tokens, cached) = self.encode_after_lookup(segment.text, lookup)?;
380                    hit |= cached > 0;
381                    cached_tokens += cached;
382                    tokens.into()
383                } else {
384                    let encoding = self.inner.encode_segments(std::slice::from_ref(segment))?;
385                    encoding.token_ids().into()
386                };
387                ids.extend_from_slice(&tokens);
388                self.l1.insert(key, tokens);
389            }
390        }
391        if run_start < segments.len() {
392            let run = self.inner.encode_segments(&segments[run_start..])?;
393            ids.extend_from_slice(run.token_ids());
394        }
395        if looked_up {
396            self.l1.record_lookup(hit);
397        }
398        self.observe_token_usage(cached_tokens, ids.len());
399        Ok(Encoding::Sp(ids))
400    }
401}
402
403impl Decoder for CachedTokenizer {
404    fn has_unstable_suffix(&self, token_ids: &[TokenIdType], skip_special_tokens: bool) -> bool {
405        self.inner
406            .has_unstable_suffix(token_ids, skip_special_tokens)
407    }
408
409    fn decode(&self, token_ids: &[TokenIdType], skip_special_tokens: bool) -> Result<DecodeResult> {
410        // Decode is not cached — passthrough to inner.
411        self.inner.decode(token_ids, skip_special_tokens)
412    }
413}
414
415impl Tokenizer for CachedTokenizer {
416    fn vocab_size(&self) -> Option<usize> {
417        self.inner.vocab_size()
418    }
419
420    fn token_to_id(&self, token: &str) -> Result<Option<TokenIdType>> {
421        self.inner.token_to_id(token)
422    }
423
424    fn special_token_ids(&self) -> Result<Vec<TokenIdType>> {
425        self.inner.special_token_ids()
426    }
427
428    fn num_special_tokens_added(&self) -> Result<usize> {
429        Ok(0)
430    }
431}
432
433#[cfg(test)]
434mod tests {
435    use super::*;
436    use crate::HuggingFaceTokenizer;
437    use std::sync::{Mutex, atomic::AtomicU64, atomic::Ordering};
438    use tokenizers::Tokenizer as HfTokenizer;
439
440    struct FailingTokenizer;
441
442    struct SegmentTokenizer;
443
444    impl Encoder for SegmentTokenizer {
445        fn encode(&self, input: &str) -> Result<Encoding> {
446            Ok(Encoding::Sp(vec![input.len() as u32]))
447        }
448
449        fn encode_batch(&self, inputs: &[&str]) -> Result<Vec<Encoding>> {
450            inputs.iter().map(|input| self.encode(input)).collect()
451        }
452
453        fn encode_segments(&self, segments: &[EncodeSegment<'_>]) -> Result<Encoding> {
454            let ids = segments
455                .iter()
456                .flat_map(|segment| [segment.allow_special as u32, segment.text.len() as u32])
457                .collect();
458            Ok(Encoding::Sp(ids))
459        }
460    }
461
462    impl Decoder for SegmentTokenizer {
463        fn decode(
464            &self,
465            _token_ids: &[TokenIdType],
466            _skip_special_tokens: bool,
467        ) -> Result<DecodeResult> {
468            Ok(DecodeResult::Complete(String::new()))
469        }
470    }
471
472    impl Tokenizer for SegmentTokenizer {
473        fn validate_prefix_cache(&self) -> Result<()> {
474            Ok(())
475        }
476    }
477
478    impl Encoder for FailingTokenizer {
479        fn encode(&self, _input: &str) -> Result<Encoding> {
480            Err(anyhow::anyhow!("intentional encode failure"))
481        }
482
483        fn encode_batch(&self, _inputs: &[&str]) -> Result<Vec<Encoding>> {
484            Err(anyhow::anyhow!("intentional encode failure"))
485        }
486    }
487
488    impl Decoder for FailingTokenizer {
489        fn decode(
490            &self,
491            _token_ids: &[TokenIdType],
492            _skip_special_tokens: bool,
493        ) -> Result<DecodeResult> {
494            Err(anyhow::anyhow!("intentional decode failure"))
495        }
496    }
497
498    impl Tokenizer for FailingTokenizer {
499        fn validate_prefix_cache(&self) -> Result<()> {
500            Ok(())
501        }
502
503        fn vocab_size(&self) -> Option<usize> {
504            None
505        }
506    }
507
508    const TINYLLAMA_PATH: &str = concat!(
509        env!("CARGO_MANIFEST_DIR"),
510        "/tests/data/sample-models/TinyLlama_v1.1/tokenizer.json"
511    );
512
513    fn inner() -> Arc<dyn Tokenizer> {
514        Arc::new(HuggingFaceTokenizer::from_file(TINYLLAMA_PATH).expect("load TinyLlama"))
515    }
516
517    fn specials() -> Vec<String> {
518        vec!["<s>".into(), "</s>".into()]
519    }
520
521    fn collect_token_usage(
522        tokenizer: CachedTokenizer,
523    ) -> (CachedTokenizer, Arc<Mutex<Vec<CacheTokenUsage>>>) {
524        let events = Arc::new(Mutex::new(Vec::new()));
525        let observed = events.clone();
526        let tokenizer = tokenizer.with_token_observer(Arc::new(move |usage| {
527            observed.lock().unwrap().push(usage);
528        }));
529        (tokenizer, events)
530    }
531
532    #[test]
533    fn rejects_hf_tokenizer_that_adds_special_tokens() {
534        let tokenizer: Arc<dyn Tokenizer> = Arc::new(
535            HuggingFaceTokenizer::from_file(TINYLLAMA_PATH)
536                .expect("load TinyLlama")
537                .with_options(crate::TokenizerOptions {
538                    add_special_tokens: true,
539                }),
540        );
541
542        let result = CachedTokenizer::new(tokenizer, specials(), 4096);
543        let Err(error) = result else {
544            panic!("add_special_tokens=true must be rejected");
545        };
546        assert_eq!(
547            error.to_string(),
548            "HuggingFace tokenizers configured with add_special_tokens=true must remain uncached"
549        );
550    }
551
552    #[test]
553    fn empty_specials_passes_through_correctly() {
554        // Empty token strings carry no boundary information and must not make L1 active.
555        let tok = inner();
556        let (cached, events) = collect_token_usage(
557            CachedTokenizer::new(tok.clone(), vec![String::new()], 4096)
558                .expect("TinyLlama must support prefix caching"),
559        );
560        let s = "<s>hello world</s>";
561        let a = cached.encode(s).unwrap();
562        let b = tok.encode(s).unwrap();
563        assert_eq!(a.token_ids(), b.token_ids());
564        let stats = cached.cache_stats();
565        assert_eq!(stats.entries, 0);
566        assert_eq!(stats.misses, 0, "empty specials must not increment misses");
567        assert_eq!(stats.hits, 0);
568        assert!(
569            events.lock().unwrap().is_empty(),
570            "empty specials must not emit token usage"
571        );
572    }
573
574    #[test]
575    fn laguna_overlapping_specials_bypass_cache() {
576        const TOKENIZER_JSON: &str = r#"{
577            "version": "1.0",
578            "truncation": null,
579            "padding": null,
580            "added_tokens": [
581                {"id": 0, "content": "<unk>", "special": true, "single_word": false, "lstrip": false, "rstrip": false, "normalized": false},
582                {"id": 2, "content": "〈|EOS|〉", "special": true, "single_word": false, "lstrip": false, "rstrip": false, "normalized": false},
583                {"id": 14, "content": "〈|", "special": true, "single_word": false, "lstrip": false, "rstrip": false, "normalized": false},
584                {"id": 15, "content": "|〉", "special": true, "single_word": false, "lstrip": false, "rstrip": false, "normalized": false}
585            ],
586            "normalizer": null,
587            "pre_tokenizer": null,
588            "post_processor": null,
589            "decoder": null,
590            "model": {
591                "type": "WordLevel",
592                "vocab": {"<unk>": 0, "〈|EOS|〉": 2, "〈|": 14, "|〉": 15, "tail": 16},
593                "unk_token": "<unk>"
594            }
595        }"#;
596
597        let hf = HfTokenizer::from_bytes(TOKENIZER_JSON).expect("load test tokenizer");
598        let tok: Arc<dyn Tokenizer> = Arc::new(HuggingFaceTokenizer::from_tokenizer(hf));
599        let overlapping = vec!["〈|EOS|〉".into(), "〈|".into(), "|〉".into()];
600        let (cached, events) = collect_token_usage(
601            CachedTokenizer::new(tok.clone(), overlapping, 4096)
602                .expect("HuggingFace tokenizer must support prefix caching"),
603        );
604
605        let expected = tok.encode("〈|EOS|〉").unwrap();
606        assert_eq!(expected.token_ids(), &[2]);
607        assert_eq!(
608            cached.encode("〈|EOS|〉").unwrap().token_ids(),
609            expected.token_ids()
610        );
611        let stats = cached.cache_stats();
612        assert_eq!(stats.entries, 0);
613        assert_eq!(
614            stats.misses, 0,
615            "overlapping specials must not increment misses"
616        );
617        assert_eq!(stats.hits, 0);
618        assert!(
619            events.lock().unwrap().is_empty(),
620            "overlapping specials must not emit token usage"
621        );
622    }
623
624    /// `text` repeated past the segment-caching threshold.
625    fn long_text(text: &str) -> String {
626        text.repeat(MIN_CACHED_SEGMENT_BYTES / text.len() + 1)
627    }
628
629    #[test]
630    fn segmented_encoding_without_specials_passes_through() {
631        let inner: Arc<dyn Tokenizer> = Arc::new(SegmentTokenizer);
632        let user = long_text("user content ");
633        let segments = [
634            EncodeSegment::new("<ctl>", true),
635            EncodeSegment::new(&user, false),
636        ];
637        let expected = inner.encode_segments(&segments).unwrap();
638        let (cached, events) = collect_token_usage(
639            CachedTokenizer::new(inner, Vec::new(), 4096)
640                .expect("test tokenizer supports prefix caching"),
641        );
642
643        for _ in 0..2 {
644            let actual = cached.encode_segments(&segments).unwrap();
645            assert_eq!(actual.token_ids(), expected.token_ids());
646        }
647        let stats = cached.cache_stats();
648        assert_eq!((stats.entries, stats.hits, stats.misses), (0, 0, 0));
649        assert!(events.lock().unwrap().is_empty());
650    }
651
652    #[test]
653    fn segmented_encoding_caches_long_segments_and_matches_inner() {
654        let inner: Arc<dyn Tokenizer> = Arc::new(SegmentTokenizer);
655        let user = long_text("user content ");
656        let tool = long_text("<ctl> tool output ");
657        // The same text with and without allow_special encodes differently, so the
658        // flag must be part of the key; short segments are encoded but never cached.
659        let segments = [
660            EncodeSegment::new("<ctl>", true),
661            EncodeSegment::new(&user, false),
662            EncodeSegment::new("<ctl>", true),
663            EncodeSegment::new("short", false),
664            EncodeSegment::new(&tool, false),
665            EncodeSegment::new(&tool, true),
666            EncodeSegment::new("<ctl>", true),
667        ];
668        let expected = inner.encode_segments(&segments).unwrap();
669        let (cached, events) = collect_token_usage(
670            CachedTokenizer::new(inner.clone(), vec!["<ctl>".to_string()], 4096)
671                .expect("test tokenizer supports prefix caching"),
672        );
673
674        let first = cached.encode_segments(&segments).unwrap();
675        let second = cached.encode_segments(&segments).unwrap();
676        assert_eq!(first.token_ids(), expected.token_ids());
677        assert_eq!(second.token_ids(), expected.token_ids());
678
679        let stats = cached.cache_stats();
680        assert_eq!(stats.entries, 3);
681        assert_eq!((stats.hits, stats.misses), (1, 1));
682        // The mock encodes each segment as two ids, so the three long segments are six.
683        let total = expected.token_ids().len();
684        assert_eq!(
685            events.lock().unwrap().as_slice(),
686            &[
687                CacheTokenUsage {
688                    cached_tokens: 0,
689                    uncached_tokens: total,
690                },
691                CacheTokenUsage {
692                    cached_tokens: 6,
693                    uncached_tokens: total - 6,
694                },
695            ]
696        );
697    }
698
699    #[test]
700    fn segment_entries_do_not_collide_with_prefix_entries() {
701        let inner: Arc<dyn Tokenizer> = Arc::new(SegmentTokenizer);
702        let cached = CachedTokenizer::new(inner.clone(), vec!["<ctl>".to_string()], 4096)
703            .expect("test tokenizer supports prefix caching");
704        // `encode` caches the prefix ending at "<ctl>"; a segment with the same text must
705        // still get the segment encoding, not the prefix entry's tokens.
706        let text = long_text("prefix text ") + "<ctl>";
707        cached.encode(&(text.clone() + " suffix")).unwrap();
708        for allow_special in [false, true] {
709            let segment = [EncodeSegment::new(&text, allow_special)];
710            for _ in 0..2 {
711                assert_eq!(
712                    cached.encode_segments(&segment).unwrap().token_ids(),
713                    inner.encode_segments(&segment).unwrap().token_ids()
714                );
715            }
716        }
717    }
718
719    fn fast_inner() -> Arc<dyn Tokenizer> {
720        Arc::new(crate::FastTokenizer::from_file(TINYLLAMA_PATH).expect("load TinyLlama"))
721    }
722
723    #[test]
724    fn backends_that_share_prefixes_encode_a_special_segment_like_plain_text() {
725        for tokenizer in [inner(), fast_inner()] {
726            tokenizer
727                .validate_segment_prefix_cache()
728                .expect("backend shares prefix entries with segments");
729            for text in [
730                "<s>system\nYou are helpful.</s><s>user\nHi there</s>",
731                "no special tokens here",
732                " leading space</s>",
733                "</s><s>",
734            ] {
735                assert_eq!(
736                    tokenizer
737                        .encode_segments(&[EncodeSegment::control(text)])
738                        .unwrap()
739                        .token_ids(),
740                    tokenizer.encode(text).unwrap().token_ids(),
741                    "{text:?}"
742                );
743            }
744        }
745    }
746
747    #[test]
748    fn growing_last_segment_reuses_its_prefix_and_matches_inner() {
749        for tokenizer in [inner(), fast_inner()] {
750            for extend_on_hit in [false, true] {
751                let (cached, events) = collect_token_usage(
752                    CachedTokenizer::new(tokenizer.clone(), specials(), 1 << 20)
753                        .expect("TinyLlama must support prefix caching")
754                        .with_extend(extend_on_hit),
755                );
756                // A conversation whose first user message typed `</s>`: the text
757                // before it, the typed marker as ordinary text, and all that follows.
758                let before = "<s>system\nYou are helpful.</s><s>user\nWhat does ".repeat(8);
759                let mut after =
760                    " mean in a chat template?</s><s>assistant\nIt ends a turn.</s>".repeat(8);
761                for turn in 0..3 {
762                    after.push_str(&format!(
763                        "<s>user\nQuestion {turn}, a little longer than the last?</s><s>assistant\n"
764                    ));
765                    let segments = [
766                        EncodeSegment::control(&before),
767                        EncodeSegment::ordinary("</s>"),
768                        EncodeSegment::control(&after),
769                    ];
770                    assert_eq!(
771                        cached.encode_segments(&segments).unwrap().token_ids(),
772                        tokenizer.encode_segments(&segments).unwrap().token_ids(),
773                        "turn {turn}"
774                    );
775                    after.push_str("An answer.</s>");
776                }
777
778                let events = events.lock().unwrap();
779                assert_eq!(events[0].cached_tokens, 0);
780                // Later turns encode the new exchanges, not the conversation again.
781                for usage in &events[1..] {
782                    assert!(
783                        usage.uncached_tokens * 2 < usage.cached_tokens,
784                        "extend {extend_on_hit}: {usage:?}"
785                    );
786                }
787                let stats = cached.cache_stats();
788                assert_eq!((stats.hits, stats.misses), (2, 1));
789            }
790        }
791    }
792
793    #[test]
794    fn segment_continues_from_a_prefix_that_encode_cached() {
795        for tokenizer in [inner(), fast_inner()] {
796            let (cached, events) = collect_token_usage(
797                CachedTokenizer::new(tokenizer.clone(), specials(), 1 << 20)
798                    .expect("TinyLlama must support prefix caching"),
799            );
800            // Earlier turns were encoded whole; the new message then types `</s>`.
801            let history = "<s>system\nYou are helpful.</s><s>user\nA first question?</s>\
802                           <s>assistant\nA first answer.</s>"
803                .repeat(4);
804            cached.encode(&history).unwrap();
805            let before = format!("{history}<s>user\nWhat does ");
806            let segments = [
807                EncodeSegment::control(&before),
808                EncodeSegment::ordinary("</s>"),
809                EncodeSegment::control(" mean?</s><s>assistant\n"),
810            ];
811            assert_eq!(
812                cached.encode_segments(&segments).unwrap().token_ids(),
813                tokenizer.encode_segments(&segments).unwrap().token_ids()
814            );
815            let events = events.lock().unwrap();
816            assert!(
817                events[1].cached_tokens > events[1].uncached_tokens,
818                "{:?}",
819                events[1]
820            );
821        }
822    }
823
824    #[test]
825    fn segments_reuse_prefixes_only_where_the_backend_opts_in() {
826        // The mock encodes a segment and plain text differently, and has not opted in.
827        let inner: Arc<dyn Tokenizer> = Arc::new(SegmentTokenizer);
828        let (cached, events) = collect_token_usage(
829            CachedTokenizer::new(inner.clone(), vec!["<ctl>".to_string()], 4096)
830                .expect("test tokenizer supports prefix caching"),
831        );
832        let mut text = long_text("turn one <ctl> ");
833        for _ in 0..2 {
834            let segment = [EncodeSegment::control(&text)];
835            assert_eq!(
836                cached.encode_segments(&segment).unwrap().token_ids(),
837                inner.encode_segments(&segment).unwrap().token_ids()
838            );
839            text.push_str("turn two <ctl> more");
840        }
841        assert!(
842            events
843                .lock()
844                .unwrap()
845                .iter()
846                .all(|usage| usage.cached_tokens == 0)
847        );
848    }
849
850    #[test]
851    fn token_observer_reports_full_miss_and_partial_hit_with_and_without_extension() {
852        for extend_on_hit in [false, true] {
853            let tok = inner();
854            let hits = Arc::new(AtomicU64::new(0));
855            let misses = Arc::new(AtomicU64::new(0));
856            let hit_counter = hits.clone();
857            let miss_counter = misses.clone();
858            let cached = CachedTokenizer::new(tok, specials(), 64 * 1024)
859                .expect("TinyLlama must support prefix caching")
860                .with_extend(extend_on_hit)
861                .with_observer(
862                    Arc::new(move || {
863                        hit_counter.fetch_add(1, Ordering::Relaxed);
864                    }),
865                    Arc::new(move || {
866                        miss_counter.fetch_add(1, Ordering::Relaxed);
867                    }),
868                );
869            let (cached, events) = collect_token_usage(cached);
870
871            let shared = "<s>system\nYou are helpful.</s><s>user\n";
872            let first = format!("{shared}First question?</s>");
873            let second = format!("{shared}Second different prompt entirely.</s>");
874
875            let first_encoding = cached.encode(&first).unwrap();
876            let second_encoding = cached.encode(&second).unwrap();
877
878            let events = events.lock().unwrap();
879            assert_eq!(events.len(), 2);
880            assert_eq!(
881                events[0],
882                CacheTokenUsage {
883                    cached_tokens: 0,
884                    uncached_tokens: first_encoding.token_ids().len(),
885                }
886            );
887            assert!(events[1].cached_tokens > 0);
888            assert!(events[1].uncached_tokens > 0);
889            assert_eq!(
890                events[1].cached_tokens + events[1].uncached_tokens,
891                second_encoding.token_ids().len()
892            );
893            assert_eq!(hits.load(Ordering::Relaxed), 1);
894            assert_eq!(misses.load(Ordering::Relaxed), 1);
895        }
896    }
897
898    #[test]
899    fn token_observer_does_not_report_failed_encodes() {
900        let tokenizer: Arc<dyn Tokenizer> = Arc::new(FailingTokenizer);
901        let (cached, events) = collect_token_usage(
902            CachedTokenizer::new(tokenizer, specials(), 4096)
903                .expect("test tokenizer explicitly supports prefix caching"),
904        );
905
906        assert!(cached.encode("<s>this fails</s>").is_err());
907        assert!(events.lock().unwrap().is_empty());
908    }
909
910    #[test]
911    fn two_turn_chat_correctness_and_hit() {
912        let tok = inner();
913        let cached = CachedTokenizer::new(tok.clone(), specials(), 64 * 1024)
914            .expect("TinyLlama must support prefix caching");
915
916        let template = "<s>system\nYou are helpful.</s><s>user\n";
917        let first = format!("{template}First question?</s>");
918        let second = format!("{template}Second different prompt entirely.</s>");
919
920        // Warm the cache.
921        let _ = cached.encode(&first).unwrap();
922
923        // Second request: shared prefix → L1 hit, suffix-only fresh encode.
924        let cached_second = cached.encode(&second).unwrap();
925        let plain_second = tok.encode(&second).unwrap();
926        assert_eq!(
927            cached_second.token_ids(),
928            plain_second.token_ids(),
929            "cached encode must equal plain encode for second turn"
930        );
931
932        let stats = cached.cache_stats();
933        assert!(stats.hits >= 1, "expected L1 hit on second request");
934    }
935
936    #[test]
937    fn decode_passes_through() {
938        let tok = inner();
939        let cached = CachedTokenizer::new(tok.clone(), specials(), 4096)
940            .expect("TinyLlama must support prefix caching");
941        let enc = cached.encode("<s>hello</s>").unwrap();
942        let direct = tok.decode(enc.token_ids(), false).unwrap();
943        let through = cached.decode(enc.token_ids(), false).unwrap();
944        assert_eq!(direct, through);
945    }
946
947    #[test]
948    fn encode_batch_uses_cache() {
949        let tok = inner();
950        let (cached, events) = collect_token_usage(
951            CachedTokenizer::new(tok.clone(), specials(), 64 * 1024)
952                .expect("TinyLlama must support prefix caching"),
953        );
954        let shared = "<s>system\nShared persona.</s><s>user\n";
955        let inputs = [
956            format!("{shared}q1</s>"),
957            format!("{shared}q2</s>"),
958            format!("{shared}q3</s>"),
959        ];
960        let refs: Vec<&str> = inputs.iter().map(String::as_str).collect();
961        let outs = cached.encode_batch(&refs).unwrap();
962        assert_eq!(outs.len(), 3);
963        let events = events.lock().unwrap();
964        assert_eq!(events.len(), outs.len());
965        for (event, output) in events.iter().zip(&outs) {
966            assert_eq!(
967                event.cached_tokens + event.uncached_tokens,
968                output.token_ids().len()
969            );
970        }
971        assert_eq!(events[0].cached_tokens, 0);
972        assert!(events[1..].iter().all(|event| event.cached_tokens > 0));
973        // First call populates, second/third hit.
974        assert!(cached.cache_stats().hits >= 2, "expected hits on q2 and q3");
975    }
976
977    #[test]
978    fn vocab_introspection_forwards_to_inner() {
979        let tok = inner();
980        let cached = CachedTokenizer::new(tok.clone(), specials(), 4096)
981            .expect("TinyLlama must support prefix caching");
982        assert_eq!(cached.vocab_size(), tok.vocab_size());
983        assert_eq!(
984            cached.token_to_id("<s>").unwrap(),
985            tok.token_to_id("<s>").unwrap()
986        );
987        assert_eq!(
988            cached.special_token_ids().unwrap(),
989            tok.special_token_ids().unwrap()
990        );
991    }
992
993    #[test]
994    fn special_token_accounting_matches_cached_encoder_behavior() {
995        let cached = CachedTokenizer::new(inner(), specials(), 4096)
996            .expect("TinyLlama must support prefix caching")
997            .with_options(crate::TokenizerOptions {
998                add_special_tokens: true,
999            });
1000        let cached_ids = cached.encode("hello").unwrap();
1001        let hf_ids = HuggingFaceTokenizer::from_file(TINYLLAMA_PATH)
1002            .expect("load TinyLlama")
1003            .with_options(crate::TokenizerOptions {
1004                add_special_tokens: true,
1005            })
1006            .encode("hello")
1007            .unwrap();
1008
1009        assert_eq!(cached.num_special_tokens_added().unwrap(), 0);
1010        assert_eq!(hf_ids.token_ids().len(), cached_ids.token_ids().len() + 1);
1011        assert_eq!(&hf_ids.token_ids()[1..], cached_ids.token_ids());
1012    }
1013
1014    #[test]
1015    fn unoverridden_introspection_methods_use_defaults() {
1016        let tokenizer = SegmentTokenizer;
1017        assert_eq!(tokenizer.vocab_size(), None);
1018        assert!(tokenizer.token_to_id("anything").is_err());
1019        assert!(tokenizer.special_token_ids().is_err());
1020        assert!(tokenizer.num_special_tokens_added().is_err());
1021    }
1022}