exatok 0.1.1

Exact GPU-resident BPE tokenizer whose token ids match tiktoken byte for byte
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
//! Host tokenizer: the crate's public entry point. OWNER: Main.
//!
//! [`Tokenizer`] owns a loaded vocabulary and the encoding it belongs to, and it
//! is the whole host path in one type. [`Tokenizer::encode`] turns bytes into
//! token ids and [`Tokenizer::decode`] turns token ids back into bytes. A
//! consumer of this crate needs nothing else to tokenize text.
//!
//! # Why this module exists
//!
//! The host path has three stages in three modules. [`crate::pretokenize`]
//! decides the boundaries, a byte-to-id table seeds each pretoken, and
//! [`crate::incremental`] merges each pretoken to a fixpoint. Before this module
//! the only place those three were joined was [`crate::parity::encode_bytes`],
//! which lives in the module that also carries the parity corpus, and the only
//! decoder was a private helper in `src/main.rs` that no test could reach. A
//! library consumer therefore had to compose the encode stages by hand and had
//! no decoder at all, while the command line owned domain logic.
//!
//! # Two entry points, one algorithm
//!
//! `exatok encode` calls [`Tokenizer::encode`] and nothing else, and
//! `exatok decode` calls [`Tokenizer::decode`] and nothing else. Two entry
//! points to one algorithm is where divergence hides, so
//! `tests/api_shape.rs` compares the binary's printed ids against this type's
//! ids over the whole parity corpus rather than trusting the call graph.
//!
//! # Cost
//!
//! Two properties are contracts, not incidental, and `tests/encode_cost.rs`
//! measures both:
//!
//! 1. Merging goes through [`crate::incremental`], which refreshes only the two
//!    pair ranks adjacent to a merge site instead of rescanning every pair each
//!    pass. That is byte-identical to [`crate::reference::encode`] and costs far
//!    fewer pair-table lookups, which are the dominant cost of the whole
//!    tokenizer. Measured over the parity corpus concatenated into one input,
//!    3635 bytes and 663 pretokens, on real `cl100k_base`: 5948 lookups against
//!    the full rescan's 226328.
//!
//!    That ratio is not a constant. The rescan re-probes every surviving pair on
//!    every pass, so one pretoken of `n` tokens costs about `n^2 / 2` lookups
//!    where this costs about `n + 2m` for `m` merges, and the corpus includes a
//!    deliberate 500-token pretoken that dominates the rescan total on its own.
//!    Per byte over ordinary pretokens the reduction is about half:
//!    `tests/incremental_merge.rs` pins 1.500 lookups per byte against 2.770.
//! 2. The number of heap allocations does not grow with the number of
//!    pretokens. [`crate::parity::pretoken_ids`] materializes one `Vec` per
//!    pretoken, so encoding a gigabyte of prose through it allocates roughly 250
//!    million times. [`Tokenizer::encode`] reuses one start-state buffer and one
//!    [`crate::incremental::MergeState`] across every pretoken of a call, so the
//!    count is the output buffer plus the growth of those two and it does not
//!    move with the input. Measured over the same corpus: 26 allocations against
//!    the oracle's 689, and 26 again for that corpus repeated four times.
//!
//! Neither changes which merge is selected. A rank tie still goes to the
//! leftmost pair, so the ids are the reference ids.

use crate::incremental::MergeState;
use crate::pretokenize::{Span, SplitPattern, pretokens, spans};
use crate::reference::MergeTable;
use crate::vocab::Vocabulary;
use crate::Encoding;
use crate::{TokenId, ExatokError};

/// Bytes reserved per token id when sizing an encode output buffer.
///
/// Real vocabularies average close to four input bytes per token on prose, so
/// three is a deliberate underestimate: the output buffer is sized once and
/// grows only if the input is unusually incompressible, and a byte-per-token
/// reserve would ask for four times the input in ids before encoding a byte.
const BYTES_PER_TOKEN_RESERVE: usize = 3;

/// A loaded vocabulary and the encoding it belongs to.
///
/// Construction resolves the 256 single-byte token ids once. Encoding needs them
/// on every pretoken, so resolving them per call would repeat 256 hash lookups
/// for a table that cannot change.
#[derive(Debug, Clone)]
pub struct Tokenizer {
    encoding: Encoding,
    vocabulary: Vocabulary,
    byte_ids: [TokenId; 256],
}

impl Tokenizer {
    /// Build a tokenizer over `vocabulary`, encoding as `encoding` describes.
    ///
    /// # Errors
    ///
    /// [`ExatokError::Artifact`] when `vocabulary` carries no token for some
    /// single byte value. Byte-level encoding starts from one token per input
    /// byte, so a vocabulary missing one has no start state for an input
    /// containing that byte, and no substitute would encode the bytes it was
    /// given.
    pub fn new(vocabulary: Vocabulary, encoding: Encoding) -> Result<Self, ExatokError> {
        let byte_ids = crate::byte_token_ids(encoding.artifact(), &vocabulary)?;
        Ok(Self {
            encoding,
            vocabulary,
            byte_ids,
        })
    }

    /// The encoding this tokenizer was built for.
    #[must_use]
    pub const fn encoding(&self) -> &Encoding {
        &self.encoding
    }

    /// The loaded vocabulary.
    #[must_use]
    pub const fn vocabulary(&self) -> &Vocabulary {
        &self.vocabulary
    }

    /// Token id of each single-byte token, indexed by byte value.
    ///
    /// This is the byte-level start state every pretoken begins from. It is
    /// exposed because a device path needs the identical table: a host and a
    /// device that seeded from two tables would diverge on the first byte whose
    /// id they disagreed about.
    #[must_use]
    pub const fn byte_ids(&self) -> &[TokenId; 256] {
        &self.byte_ids
    }

    /// Encode `input` to its exact token ids.
    ///
    /// Splits `input` into pretokens, seeds each with one id per byte, and
    /// merges each to a fixpoint. Merges never cross a pretoken boundary, so the
    /// state is fully replaced per pretoken and nothing carries between them
    /// except the two reused buffers.
    ///
    /// No special token can appear in the result. Ordinary encoding merges byte
    /// pairs through the merge table and no special token is in it, so the text
    /// `<|endoftext|>` encodes to the ids of its own bytes. That matches the
    /// reference tokenizer's `encode_ordinary`. Use
    /// [`crate::specials::encode_allowed`] for the mode that recognizes a
    /// declared special before pretokenization and emits its single id.
    #[must_use]
    pub fn encode(&self, input: &[u8]) -> Vec<TokenId> {
        encode_bytes(
            self.encoding.pattern(),
            input,
            &self.byte_ids,
            self.vocabulary.merge_table(),
        )
    }

    /// The pretoken spans `input` splits into, before any merging.
    ///
    /// The same split [`Self::encode`] runs, exposed because the split is
    /// observable: it decides which merges are even possible, so a caller
    /// diagnosing an unexpected id stream needs to see it. Reaching for
    /// [`crate::pretokenize::spans`] with a separately obtained pattern is the
    /// alternative, and that is the shape of defect this method exists to
    /// remove, since the pattern would then be chosen twice and can disagree.
    #[must_use]
    pub fn split(&self, input: &[u8]) -> Vec<Span> {
        spans(self.encoding.pattern(), input)
    }

    /// The bytes `id` stands for, ordinary token or registered special.
    ///
    /// Specials live outside the ordinary id space, so an ordinary-only lookup
    /// reports a registered special as unknown. Returns a borrow rather than an
    /// owned buffer: decoding a stream would otherwise allocate once per id.
    #[must_use]
    pub fn bytes_of(&self, id: TokenId) -> Option<&[u8]> {
        if let Some(bytes) = self.vocabulary.bytes_of(id) {
            return Some(bytes);
        }
        self.vocabulary
            .specials()
            .find(|(_, special)| *special == id)
            .map(|(text, _)| text.as_bytes())
    }

    /// Decode `ids` to the bytes they stand for.
    ///
    /// The result is bytes and not text on purpose. A token boundary may fall
    /// inside a UTF-8 sequence, so a decoder returning `String` would have to
    /// either fail on a valid id stream or substitute a replacement character
    /// and corrupt the output.
    ///
    /// # Errors
    ///
    /// [`UnknownTokenId`] naming the first id no token carries, and its position
    /// in `ids`. Decoding stops there rather than skipping the id, because a
    /// skipped id yields plausible bytes that are not the ones the stream
    /// encoded.
    pub fn decode(&self, ids: &[TokenId]) -> Result<Vec<u8>, UnknownTokenId> {
        let mut bytes = Vec::with_capacity(ids.len() * BYTES_PER_TOKEN_RESERVE);
        for (index, id) in ids.iter().enumerate() {
            let Some(token) = self.bytes_of(*id) else {
                return Err(UnknownTokenId {
                    id: *id,
                    index,
                    n_vocab: self.vocabulary.n_vocab(),
                    highest_ordinary: self.vocabulary.max_token_id().map_or(0, |id| id.0),
                });
            };
            bytes.extend_from_slice(token);
        }
        Ok(bytes)
    }
}

/// Encode `input` end to end: split, seed one id per byte, merge per pretoken.
///
/// This is the shipping join of the three host stages, and [`Tokenizer::encode`]
/// is a thin wrapper that supplies the three pieces from one loaded vocabulary.
/// The pieces are taken separately so a caller holding a deliberately corrupted
/// table can drive the identical path as a loaded one.
///
/// [`crate::parity::encode_bytes`] is the same function over
/// [`crate::reference`]'s full-rescan merge loop and exists as this one's
/// oracle. Two joins is the same arrangement [`crate::reference::encode`] and
/// [`crate::incremental::encode`] already use one level down: the slow one is
/// auditable, the fast one ships, and a test pins them equal.
/// `tests/api_shape.rs` pins them equal over the whole parity corpus on all four
/// named vocabularies, so a divergence fails rather than hides.
///
/// Allocation does not grow with the pretoken count. One start-state buffer and
/// one [`MergeState`] are reused across every pretoken, where
/// [`crate::parity::pretoken_ids`] materializes a `Vec` per pretoken.
#[must_use]
pub fn encode_bytes(
    pattern: SplitPattern,
    input: &[u8],
    byte_ids: &[TokenId; 256],
    table: &impl MergeTable,
) -> Vec<TokenId> {
    let mut ids = Vec::with_capacity(input.len() / BYTES_PER_TOKEN_RESERVE + 1);
    let mut start = Vec::new();
    let mut state = MergeState::new();
    for span in pretokens(pattern, input) {
        // `pretokens` partitions `input`: the spans are contiguous, gapless, and
        // end at `input.len()`, so this range is in bounds by construction.
        // `crate::parity::pretoken_ids` slices on the same guarantee.
        let pretoken = &input[span.start..span.end];
        start.clear();
        start.extend(pretoken.iter().map(|&byte| byte_ids[byte as usize]));
        state.load(&start, table);
        state.run(table);
        ids.extend_from_slice(state.tokens());
    }
    ids
}

/// A token id that this vocabulary carries no bytes for.
///
/// Carries the position as well as the id. A stream of a thousand ids reports
/// which one offended, so the caller does not bisect the stream to find it.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct UnknownTokenId {
    /// The id that could not be decoded.
    pub id: TokenId,
    /// Its index in the id stream that was passed to [`Tokenizer::decode`].
    pub index: usize,
    /// Exclusive upper bound over every decodable id, specials included.
    pub n_vocab: usize,
    /// Highest ordinary token id, so a caller can tell one case from the other.
    ///
    /// An id above [`UnknownTokenId::n_vocab`] came from a different vocabulary.
    /// An id between this and that bound fell in a reserved hole: `p50k_base`
    /// reserves 50256 for `<|endoftext|>` while its ordinary entries reach
    /// 50280, so ids exist below the ceiling that decode to nothing.
    pub highest_ordinary: u32,
}

impl std::fmt::Display for UnknownTokenId {
    fn fmt(&self, out: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            out,
            "token id {} at position {} is not in this vocabulary, whose highest decodable id is \
             {} ({} ordinary, the rest special)",
            self.id.0,
            self.index,
            self.n_vocab.saturating_sub(1),
            self.highest_ordinary
        )
    }
}

/// Without this, `UnknownTokenId` cannot cross a `Box<dyn Error>` or an
/// `anyhow::Error` boundary, and every consumer has to hand-convert a type this
/// crate already calls an error. `Display` alone is not enough: `?` into a boxed
/// error requires the `Error` trait itself.
///
/// The default `source` is correct here. There is no underlying cause to chain:
/// the id simply is not in the vocabulary, and the full account of what happened
/// is in [`UnknownTokenId`]'s own fields.
impl std::error::Error for UnknownTokenId {}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
mod tests {
    use super::{Tokenizer, UnknownTokenId};
    use crate::Encoding;
    use crate::pretokenize::SplitPattern;
    use crate::vocab::{Source, Vocabulary};
    use crate::{Rank, TokenId};

    /// A vocabulary with all 256 single bytes plus one merge, small enough to
    /// state every expected id by hand.
    ///
    /// Ranks 0 to 255 are the raw bytes, matching the real artifact layout, and
    /// rank 256 is `hi`, so `hi` merges and `ih` does not.
    fn tiny() -> Vocabulary {
        let mut text = String::new();
        for byte in 0..=u8::MAX {
            text.push_str(&base64(&[byte]));
            text.push(' ');
            text.push_str(&format!("{byte}\n"));
        }
        text.push_str(&base64(b"hi"));
        text.push_str(" 256\n");
        Vocabulary::load_tiktoken(Source::new("tiny", &text)).expect("tiny artifact must load")
    }

    fn base64(bytes: &[u8]) -> String {
        const ALPHABET: &[u8; 64] =
            b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
        let mut out = String::new();
        for chunk in bytes.chunks(3) {
            let mut word = 0_u32;
            for (index, byte) in chunk.iter().enumerate() {
                word |= u32::from(*byte) << (16 - 8 * index);
            }
            for index in 0..4 {
                if index <= chunk.len() {
                    let slot = (word >> (18 - 6 * index)) & 0x3F;
                    out.push(char::from(ALPHABET[slot as usize]));
                } else {
                    out.push('=');
                }
            }
        }
        out
    }

    fn tokenizer() -> Tokenizer {
        Tokenizer::new(tiny(), Encoding::new("tiny", SplitPattern::Gpt2))
            .expect("every single byte is present")
    }

    /// Encoding merges the one pair the table holds and leaves the other alone.
    ///
    /// If the byte-to-id seeding were wrong, or the merge table were consulted
    /// with the halves swapped, `hi` would come back as two ids and `ih` as one.
    /// Both directions are asserted because a symmetric key would pass either
    /// one alone.
    #[test]
    fn encode_merges_the_pair_the_table_holds_and_not_its_reverse() {
        let tokenizer = tokenizer();
        assert_eq!(tokenizer.encode(b"hi"), vec![TokenId(256)]);
        assert_eq!(
            tokenizer.encode(b"ih"),
            vec![TokenId(u32::from(b'i')), TokenId(u32::from(b'h'))]
        );
    }

    /// A merge never crosses a pretoken boundary.
    ///
    /// `h` and `i` here are in separate pretokens under the `gpt2` pattern, so
    /// the pair is adjacent in the input and must still not merge. An encoder
    /// that merged the flat byte stream instead of merging per pretoken returns
    /// one id and passes any test whose input has no boundary in the middle.
    #[test]
    fn a_pair_split_across_pretokens_does_not_merge() {
        let tokenizer = tokenizer();
        let ids = tokenizer.encode(b"h i");
        assert_eq!(
            ids,
            vec![
                TokenId(u32::from(b'h')),
                TokenId(u32::from(b' ')),
                TokenId(u32::from(b'i')),
            ]
        );
    }

    /// Decoding concatenates token bytes, so it inverts encoding exactly.
    ///
    /// Asserts the recovered bytes, not merely a length. A decoder that emitted
    /// the id's decimal text, or that dropped the second byte of a merged token,
    /// would keep the count and lose the content.
    #[test]
    fn decode_recovers_the_exact_bytes_encode_consumed() {
        let tokenizer = tokenizer();
        let input = b"hi h i hi";
        let ids = tokenizer.encode(input);
        assert_eq!(tokenizer.decode(&ids).unwrap(), input.to_vec());
    }

    /// An undecodable id is reported with its position and both bounds.
    ///
    /// Position matters: without it a thousand-id stream says only that
    /// something in it was wrong. The id chosen is above every id the tiny
    /// vocabulary carries, so the failure cannot be a lookup that happened to
    /// land in a hole.
    #[test]
    fn decode_names_the_offending_id_and_where_it_sat() {
        let tokenizer = tokenizer();
        let error = tokenizer
            .decode(&[TokenId(0), TokenId(9999), TokenId(1)])
            .expect_err("9999 is not a token in the tiny vocabulary");
        assert_eq!(
            error,
            UnknownTokenId {
                id: TokenId(9999),
                index: 1,
                n_vocab: 257,
                highest_ordinary: 256,
            }
        );
        assert!(
            error.to_string().contains("at position 1"),
            "the message must carry the position: {error}"
        );
    }

    /// A registered special decodes to its own text.
    ///
    /// Specials sit outside the ordinary id space, so a decoder that only
    /// consulted the ordinary table would reject an id the same vocabulary
    /// just registered.
    #[test]
    fn decode_resolves_a_registered_special_token() {
        let mut vocabulary = tiny();
        vocabulary
            .register_special("<|endoftext|>", TokenId(300))
            .expect("300 is representable and unused");
        let tokenizer = Tokenizer::new(vocabulary, Encoding::new("tiny", SplitPattern::Gpt2))
            .expect("every single byte is present");
        assert_eq!(
            tokenizer.decode(&[TokenId(300)]).unwrap(),
            b"<|endoftext|>".to_vec()
        );
        assert_eq!(tokenizer.bytes_of(TokenId(300)), Some(&b"<|endoftext|>"[..]));
    }

    /// Ordinary encoding cannot produce a special id.
    ///
    /// The literal text of a special encodes to the ids of its bytes, because no
    /// special is in the merge table. A path that matched specials during
    /// ordinary encoding would silently change the ids of any document that
    /// mentions one.
    #[test]
    fn ordinary_encoding_of_a_special_literal_yields_its_byte_ids() {
        let mut vocabulary = tiny();
        vocabulary
            .register_special("<|endoftext|>", TokenId(300))
            .expect("300 is representable and unused");
        let tokenizer = Tokenizer::new(vocabulary, Encoding::new("tiny", SplitPattern::Gpt2))
            .expect("every single byte is present");
        let ids = tokenizer.encode(b"<|endoftext|>");
        assert!(
            !ids.contains(&TokenId(300)),
            "ordinary encoding must not emit a special id: {ids:?}"
        );
        assert_eq!(tokenizer.decode(&ids).unwrap(), b"<|endoftext|>".to_vec());
    }

    /// The byte-id table is the raw byte values for a real-shaped artifact.
    ///
    /// Rank equals id in a `.tiktoken` file and the 256 single bytes occupy
    /// ranks 0 to 255, so byte `n` must have id `n`. A loader that synthesized
    /// the single bytes instead of reading them would shift every rank above
    /// 255, and this is the cheapest place that shows.
    #[test]
    fn byte_ids_are_the_byte_values_for_a_rank_ordered_artifact() {
        let tokenizer = tokenizer();
        for byte in 0..=u8::MAX {
            assert_eq!(
                tokenizer.byte_ids()[byte as usize],
                TokenId(u32::from(byte)),
                "byte {byte}"
            );
        }
    }

    /// A vocabulary missing a single-byte token is refused at construction.
    ///
    /// Deferring the check to encode time would make an input containing that
    /// byte fail while every other input succeeded, which reports a data problem
    /// as an intermittent one.
    #[test]
    fn a_vocabulary_without_every_single_byte_is_refused_at_construction() {
        let mut text = String::new();
        for byte in 0..=254_u8 {
            text.push_str(&base64(&[byte]));
            text.push(' ');
            text.push_str(&format!("{byte}\n"));
        }
        let vocabulary =
            Vocabulary::load_tiktoken(Source::new("holed", &text)).expect("artifact must load");
        let error = Tokenizer::new(vocabulary, Encoding::new("holed", SplitPattern::Gpt2))
            .expect_err("byte 0xff has no token");
        let message = error.to_string();
        assert!(message.contains("0xff"), "must name the byte: {message}");
        assert!(message.contains("Fix:"), "must say what to do: {message}");
    }

    /// The sentinel rank can never be a real rank, so selection needs no
    /// presence mask.
    ///
    /// [`crate::incremental::MergeState::select`] is a plain unsigned minimum
    /// over the rank column with [`Rank::ABSENT`] as the running best. A table
    /// that admitted a mergeable pair at `u32::MAX` would be invisible to it
    /// while [`crate::reference::encode`] still merged the pair, so the two host
    /// paths would diverge. The loader rejects it, and this pins that.
    #[test]
    fn a_merge_at_the_absent_sentinel_rank_is_rejected_by_the_loader() {
        let mut table = crate::reference::HostMergeTable::new();
        let error = table
            .insert(
                "sentinel.tiktoken",
                crate::PairKey::new(TokenId(1), TokenId(2)),
                TokenId(3),
                Rank::ABSENT,
            )
            .expect_err("the sentinel rank must be refused");
        assert!(
            error.to_string().contains("Fix:"),
            "must say what to do: {error}"
        );
    }
}