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.
// 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.
// 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.
use crateSplitPattern;
use crateVocabulary;
pub use ;
/// 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.
;
/// 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.
/// 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.
;
/// 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.
;
/// 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.
;
/// FNV-1a 32-bit over `bytes`, seeded with `hash`.
pub const
/// 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.
/// Errors surfaced by `exatok`.
/// 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.