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
//! `exatok`  -  exact GPU-resident BPE tokenization on the vyre compute stack.
//!
//! # Layering
//!
//! This crate owns everything product-specific: vocabularies, merge tables,
//! pretokenization patterns, parity harnesses, and packaging. Reusable
//! perf-bearing GPU compositions belong upstream in `vyre-libs::subword` so
//! every backend and every IR optimizer pass inherits them.
//!
//! # Exactness contract
//!
//! Token ids MUST be identical to the reference implementation for the
//! declared vocabulary, byte for byte, on every input. "Close enough" is a
//! defect: downstream models are trained against exact ids, and an
//! approximate tokenizer silently shifts every embedding lookup.
//!
//! # Shared vocabulary
//!
//! The types below are the cross-module contract. Both the host reference
//! path and the GPU program path MUST agree on merge-key packing and on the
//! probe hash, or a GPU table lookup diverges from its host oracle.
//!
//! # The algorithm
//!
//! Byte-pair encoding merges the adjacent pair with the lowest rank, where a
//! lower rank wins. The shipping path is sequential and per pretoken: split the
//! input into pretokens, start each as one token per byte, then repeatedly merge
//! the leftmost lowest-rank adjacent pair until none is mergeable. Merges never
//! cross a pretoken boundary.
//!
//! Tie-breaking is load bearing. Ranks tie in real vocabularies, so the
//! comparison is strict `<` and a tie goes to the LEFTMOST pair. A `<=` slip
//! changes the output.
//!
//! Parallelism runs ACROSS pretokens, not within one. The median pretoken is 3
//! bytes and takes about 3 merges, so there is little to exploit inside one and
//! a great deal across the roughly 250 million per gigabyte.
//!
//! # Modules
//!
//! Start here: [`tokenizer`], whose [`Tokenizer`] is the whole host path in one
//! type. It is re-exported at this root and it is what the command line calls.
//! Everything below is a stage of it, useful when you are working on the stage
//! rather than using the tokenizer.
//!
//! Host path, in the order data flows through it:
//!
//! - [`byte_encoder`]: the reversible byte-to-codepoint mapping that vocabulary
//!   artifacts are written in.
//! - [`vocab`]: loads `.tiktoken`, `vocab.json` + `merges.txt`, and
//!   `tokenizer.json`, and derives the merge table EXHAUSTIVELY over every
//!   in-vocabulary split rather than only the canonical one.
//! - [`pretokenize`]: the split patterns, as byte spans and never owned strings.
//! - [`reference`]: the ground-truth sequential encoder. Every other path is
//!   measured against this one.
//! - [`incremental`]: the same result with only the two pairs adjacent to a
//!   merge site refreshed, which is what the device loop implements.
//!
//! Device path:
//!
//! - [`gpu_rank_table`]: the device-resident wide-key merge-rank table and its
//!   probe program.
//! - [`gpu_select`]: segmented leftmost-minimum selection, compaction, and
//!   merge application.
//! - [`gpu_loop`]: the convergence harness that runs a pass body to a fixpoint.
//!
//! Supporting:
//!
//! - [`parity`]: the byte-exact comparison against reference fixtures.
//! - `confluence`, behind the non-default `confluence` feature: the experiment
//!   that refuted single-rank multi-merge, kept as the record of why the merge
//!   loop fuses one pair per pass. You do not need the feature to read the
//!   result: it is in README.md under "Multi-merge is permanently off". Read
//!   that before touching the `multi-merge` feature.
//! - [`bench_support`]: measurement, including the guards that stop a contended
//!   or implausible measurement from being published.
//! - [`specials`]: the special tokens each named vocabulary carries. Rank files
//!   do not contain them, so they are registered separately.
//!
//! # Before you compose device programs
//!
//! `vyre` enforces several contracts it does not document, and each one lets a
//! program build clean, pass structural tests, and fail only on dispatch. They
//! are written up in `docs/vyre-composition-contracts.md`. The one that costs
//! the most time: the `*_child` reduction helpers reference `Expr::var("local")`
//! without binding it, so the composing op must bind exactly that name.
//!
//! Also note those helpers reduce over the WHOLE workgroup. That makes them the
//! wrong tool inside a [`gpu_loop`] pass body, which holds an entire batch of
//! segments in one workgroup, because a workgroup-wide minimum there merges one
//! pair per BATCH instead of one per pretoken.
//!
//! `docs/testing-blind-spots.md` records defects this crate's tests did not
//! catch, and the mechanism that hid each one. It is worth reading before you
//! conclude a suite is sufficient.

pub mod bench_support;
pub mod byte_encoder;
// Off by default: an experiment's search and minimization types are not
// tokenizer surface, and a published crate would owe them semver. This and
// `gpu_pretokenize` below are the two declarations in this block that vary by
// feature, so an input bracket derived from the module tree is
// configuration-dependent.
#[cfg(feature = "confluence")]
pub mod confluence;
pub mod device;
pub mod gpu_loop;
// Off by default: a measured negative result, not a shipped capability. The pass
// is exact but 45x slower than the host splitter, nothing on the shipping path
// calls it, and wiring it would leave two boundary producers to keep
// byte-identical forever. Retained because the code is what keeps the
// measurement reproducible; see the module doc for the numbers and both reasons.
#[cfg(feature = "gpu-pretokenize")]
pub mod gpu_pretokenize;
pub mod gpu_rank_table;
pub mod gpu_select;
pub mod incremental;
pub mod parity;
pub mod pretokenize;
pub mod reference;
pub mod specials;
pub mod tokenizer;
pub mod vocab;

use crate::pretokenize::SplitPattern;
use crate::vocab::Vocabulary;

pub use tokenizer::{Tokenizer, UnknownTokenId};

/// Compiles every Rust block in `README.md` as a doctest.
///
/// A README example that no longer compiles is the most common documentation
/// defect in a Rust crate, and it is invisible to every test: nothing reads the
/// file. This crate's example named `parity::encode_bytes` and
/// `parity::byte_token_ids` after both had moved, so a reader following the
/// README would have hit two unresolved paths on their first build.
///
/// `#[cfg(doctest)]` means the item exists only while rustdoc collects doctests,
/// so the README is not spliced into the rendered crate documentation and this
/// struct never reaches a real build.
///
/// The example itself is `no_run`: it is compiled, not executed, because running
/// it needs a provisioned `$EXATOK_VOCAB_DIR` that a consumer building this
/// crate has no reason to have. The ids it asserts are proven by
/// `tests/parity_tiktoken.rs` against real tiktoken, which is the right place for
/// a value claim.
#[cfg(doctest)]
#[doc = include_str!("../README.md")]
struct ReadmeExamples;

/// Lower an invalid builder shape to an explicit IR trap program.
///
/// Every device-program builder in this crate is infallible and returns
/// [`vyre::ir::Program`]. This mirrors `vyre-primitives`, whose own helper
/// states the rule: "Primitive constructors are intentionally infallible for
/// composition with registry fixtures and generated dialect code. Invalid
/// user-controlled shapes must therefore become explicit IR traps, not host
/// panics."
///
/// That helper is `pub(crate)` upstream and unreachable here, so this is the
/// one shared implementation for the whole crate. Do NOT add a `ExatokError`
/// variant for a bad kernel shape and do NOT return `Result` from a builder:
/// a second convention beside this one would split the crate, and matching the
/// upstream shape keeps promotion into `vyre-libs::subword` a move rather than
/// a rewrite.
///
/// `message` MUST name the offending parameter and carry an actionable
/// `Fix:` clause, because it is the only diagnostic the operator receives.
#[must_use]
pub fn trap_program(
    op_id: &str,
    output: &str,
    data_type: vyre::ir::DataType,
    message: String,
) -> vyre::ir::Program {
    use vyre::ir::{BufferDecl, Expr, Node, Program};
    Program::wrapped(
        vec![BufferDecl::output(output, 0, data_type).with_count(1)],
        [1, 1, 1],
        vec![vyre_libs::region::wrap_anonymous(
            op_id,
            vec![Node::trap(Expr::u32(0), message)],
        )],
    )
}

/// FNV-1a 32-bit offset basis.
///
/// Matches `vyre_primitives::hash::fnv1a`, which the GPU probe uses. Both
/// sides MUST derive the probe slot from the identical function.
pub const FNV1A32_OFFSET_BASIS: u32 = 0x811c_9dc5;

/// FNV-1a 32-bit prime.
pub const FNV1A32_PRIME: u32 = 0x0100_0193;

/// A vocabulary token id.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct TokenId(pub u32);

/// A merge-table rank. Lower ranks merge first.
///
/// [`Rank::ABSENT`] is the miss sentinel and MUST compare greater than every
/// real rank so a single unsigned minimum reduction over a pair array finds
/// the best mergeable pair without a separate presence mask.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Rank(pub u32);

impl Rank {
    /// Sentinel written when a pair is not in the merge table.
    ///
    /// Deliberately `u32::MAX` so `min` over ranks ignores absent pairs.
    /// This mirrors `vyre_primitives::hash::table::MISS_VALUE`.
    pub const ABSENT: Self = Self(u32::MAX);

    /// True when this rank denotes a mergeable pair.
    #[must_use]
    pub const fn is_present(self) -> bool {
        self.0 != Self::ABSENT.0
    }
}

/// An adjacent token pair, packed as the merge-table key.
///
/// Layout is `(left << 32) | right`, matching the packing published by prior
/// GPU BPE work so the merge table is directly comparable across
/// implementations.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct PairKey(u64);

impl PairKey {
    /// Pack an adjacent pair into its table key.
    #[must_use]
    pub const fn new(left: TokenId, right: TokenId) -> Self {
        Self(((left.0 as u64) << 32) | (right.0 as u64))
    }

    /// Left element of the pair.
    #[must_use]
    pub const fn left(self) -> TokenId {
        TokenId((self.0 >> 32) as u32)
    }

    /// Right element of the pair.
    #[must_use]
    pub const fn right(self) -> TokenId {
        TokenId(self.0 as u32)
    }

    /// Raw packed bits, for upload into a device-side key column.
    #[must_use]
    pub const fn bits(self) -> u64 {
        self.0
    }

    /// Reconstruct from raw packed bits read back from a device buffer.
    #[must_use]
    pub const fn from_bits(bits: u64) -> Self {
        Self(bits)
    }

    /// Open-addressing probe slot for a table of `capacity` slots.
    ///
    /// A pair key needs 36+ bits, so it cannot be the u32 key of
    /// `vyre_primitives::hash::table` directly. The table therefore probes on
    /// this u32 hash and verifies the full 64-bit key on hit.
    #[must_use]
    pub const fn probe_hash(self) -> u32 {
        fnv1a32(FNV1A32_OFFSET_BASIS, &self.0.to_le_bytes())
    }
}

/// FNV-1a 32-bit over `bytes`, seeded with `hash`.
#[must_use]
pub const fn fnv1a32(mut hash: u32, bytes: &[u8]) -> u32 {
    let mut index = 0;
    while index < bytes.len() {
        hash ^= bytes[index] as u32;
        hash = hash.wrapping_mul(FNV1A32_PRIME);
        index += 1;
    }
    hash
}

/// A tokenizer's identity: the artifact its ranks came from and the split
/// pattern that belongs to it.
///
/// The two travel together deliberately. Pairing a vocabulary with the wrong
/// pattern changes pretoken boundaries and therefore every id, and it is silent:
/// most short inputs split identically under all three patterns, so a mismatched
/// pair encodes plausibly and diverges on the first contraction or digit run.
///
/// The artifact name is not derivable from the pattern, which is why it is
/// carried rather than looked up. `gpt2`, `r50k_base`, `p50k_base` and
/// `p50k_edit` all share [`SplitPattern::Gpt2`], so
/// [`SplitPattern::name`] would report `gpt2` for a `p50k_base` table and every
/// diagnostic would cite the wrong file.
///
/// This lives at the crate root rather than beside either tokenizer because
/// both name it. [`Tokenizer`] and [`device::DeviceTokenizer`] are built from
/// the same value, which is what lets a parity test hand one `Encoding` to both
/// and compare their ids.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Encoding {
    artifact: String,
    pattern: SplitPattern,
}

impl Encoding {
    /// Name an encoding explicitly. Use this for the `gpt2`-pattern family,
    /// where the artifact stem and the pattern name differ.
    #[must_use]
    pub fn new(artifact: impl Into<String>, pattern: SplitPattern) -> Self {
        Self {
            artifact: artifact.into(),
            pattern,
        }
    }

    /// `cl100k_base`: GPT-4 era, its own split pattern, three-digit number cap.
    #[must_use]
    pub fn cl100k_base() -> Self {
        Self::from_pattern(SplitPattern::Cl100kBase)
    }

    /// `o200k_base`: GPT-4o era, letter-class-led alternatives.
    #[must_use]
    pub fn o200k_base() -> Self {
        Self::from_pattern(SplitPattern::O200kBase)
    }

    /// An encoding whose artifact stem IS its pattern name.
    ///
    /// Correct for `cl100k_base` and `o200k_base`, and correct for `gpt2`
    /// itself. Wrong for the other three members of the `gpt2` pattern family,
    /// which must use [`Encoding::new`].
    #[must_use]
    pub fn from_pattern(pattern: SplitPattern) -> Self {
        Self {
            artifact: pattern.name().to_owned(),
            pattern,
        }
    }

    /// Artifact stem, for example `cl100k_base`. Diagnostics cite this.
    #[must_use]
    pub fn artifact(&self) -> &str {
        &self.artifact
    }

    /// Split pattern that decides pretoken boundaries.
    #[must_use]
    pub const fn pattern(&self) -> SplitPattern {
        self.pattern
    }
}

/// Errors surfaced by `exatok`.
#[derive(Debug, thiserror::Error)]
#[non_exhaustive]
pub enum ExatokError {
    /// A vocabulary or merge-table artifact could not be parsed.
    #[error("{artifact} is malformed at {location}: {detail}. Fix: {fix}")]
    Artifact {
        /// Artifact name, for example `cl100k_base.tiktoken`.
        artifact: String,
        /// Where the parse failed, for example a line number.
        location: String,
        /// What was wrong.
        detail: String,
        /// Actionable remedy.
        fix: String,
    },

    /// Device output disagreed with the host reference oracle.
    #[error(
        "token id divergence at input byte {byte_offset}: host {host:?}, device {device:?}. \
         Fix: {fix}"
    )]
    Divergence {
        /// Byte offset in the input where ids first differ.
        byte_offset: usize,
        /// Reference id at that position.
        host: Option<TokenId>,
        /// Device id at that position.
        device: Option<TokenId>,
        /// Actionable remedy.
        fix: String,
    },

    /// A vyre backend dispatch failed.
    #[error("vyre backend dispatch failed: {0}")]
    Backend(String),
}

/// The 256 single-byte token ids of `vocabulary`, indexed by byte value.
///
/// Byte-level BPE starts from one token per input byte, so this table IS the
/// byte-to-id stage, and it is the start state every pretoken begins from.
///
/// It lives at this root because the host path and the device path must seed
/// from the identical table. Two paths that disagreed about one byte's id would
/// diverge on the first input containing that byte, and the divergence would
/// read as a kernel defect rather than as a lookup one.
///
/// A missing single-byte token is reported rather than substituted. Without it
/// one input byte has no starting id at all, and any fallback would encode a
/// different string than the one supplied.
///
/// # Errors
///
/// [`ExatokError::Artifact`] naming the byte value that carries no token.
pub fn byte_token_ids(
    artifact: &str,
    vocabulary: &Vocabulary,
) -> Result<[TokenId; 256], ExatokError> {
    let mut ids = [TokenId(0); 256];
    for byte in 0..=u8::MAX {
        let Some(id) = vocabulary.id_of(&[byte]) else {
            return Err(ExatokError::Artifact {
                artifact: artifact.to_owned(),
                location: format!("byte 0x{byte:02x}"),
                detail: "no single-byte token for this byte value".to_owned(),
                fix: "load a complete .tiktoken artifact: all 256 single bytes are ordinary \
                      entries at ranks 0 to 255 and must not be synthesized, or every rank above \
                      255 shifts"
                    .to_owned(),
            });
        };
        ids[byte as usize] = id;
    }
    Ok(ids)
}

#[cfg(test)]
mod tests {
    use super::{PairKey, Rank, TokenId, fnv1a32, FNV1A32_OFFSET_BASIS};

    /// Locks the merge-key layout. The GPU key column and the host oracle
    /// index the same table; if packing drifts on one side, every lookup
    /// silently misses and the tokenizer degrades to byte-level output
    /// instead of failing. Asserts the exact bit layout, not a round trip
    /// alone, so a "fix" that swaps the halves cannot pass.
    #[test]
    fn pair_key_packs_left_into_high_word_and_right_into_low_word() {
        let key = PairKey::new(TokenId(0x0000_1234), TokenId(0x0000_5678));
        assert_eq!(key.bits(), 0x0000_1234_0000_5678);
        assert_eq!(key.left(), TokenId(0x1234));
        assert_eq!(key.right(), TokenId(0x5678));
    }

    /// A pair key is asymmetric: `(a, b)` and `(b, a)` are different merges
    /// with different ranks. A hash or packing that collapsed them would
    /// merge tokens in the wrong order and still look plausible on English
    /// text, so pin the asymmetry directly.
    #[test]
    fn pair_key_is_asymmetric_in_both_bits_and_probe_hash() {
        let forward = PairKey::new(TokenId(7), TokenId(9));
        let reverse = PairKey::new(TokenId(9), TokenId(7));
        assert_ne!(forward.bits(), reverse.bits());
        assert_ne!(forward.probe_hash(), reverse.probe_hash());
    }

    /// Round-trips the raw bit form used to upload and read back device key
    /// columns. Readback that loses the high word would alias every pair
    /// whose left element differs only above bit 32.
    #[test]
    fn pair_key_round_trips_through_raw_device_bits() {
        let key = PairKey::new(TokenId(u32::MAX), TokenId(1));
        assert_eq!(PairKey::from_bits(key.bits()), key);
    }

    /// The absent sentinel MUST be the unsigned maximum so a plain `min`
    /// reduction over a rank array skips unmergeable pairs. If `ABSENT` were
    /// zero or any small value it would win every reduction and the merge
    /// loop would pick a pair that does not exist.
    #[test]
    fn absent_rank_loses_every_unsigned_minimum_against_a_real_rank() {
        let real = Rank(50_000);
        assert!(real < Rank::ABSENT);
        assert!(real.is_present());
        assert!(!Rank::ABSENT.is_present());
        assert_eq!(Rank::ABSENT.0, u32::MAX);
    }

    /// Pins FNV-1a against the published test vector. The GPU probe uses
    /// `vyre_primitives::hash::fnv1a`; if this host copy drifted by one
    /// constant, host and device would probe different slots and parity
    /// failures would look like kernel bugs rather than a hash mismatch.
    #[test]
    fn fnv1a32_matches_published_vector_for_ascii_a() {
        assert_eq!(fnv1a32(FNV1A32_OFFSET_BASIS, b"a"), 0xe40c_292c);
        assert_eq!(fnv1a32(FNV1A32_OFFSET_BASIS, b""), FNV1A32_OFFSET_BASIS);
    }
}