Expand description
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, andtokenizer.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-defaultconfluencefeature: 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 themulti-mergefeature.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.
Re-exports§
pub use tokenizer::Tokenizer;pub use tokenizer::UnknownTokenId;
Modules§
- bench_
support - Benchmark harness support. OWNER: Bench.
- byte_
encoder - GPT-2 byte-to-unicode encoder. OWNER: VocabLoad.
- device
- The public GPU-resident encode path. OWNER: DeviceApi.
- gpu_
loop - Device-side convergence loop. OWNER: GpuLoop.
- gpu_
rank_ table - Device-resident merge-rank table. OWNER: GpuHash.
- gpu_
select - Merge selection and compaction programs. OWNER: GpuSelect.
- incremental
- Incremental merge with maintained pair ranks. OWNER: IncrementalMerge.
- parity
- Reference-tokenizer parity support. OWNER: ParityGate.
- pretokenize
- Pretokenization patterns. OWNER: Pretok.
- reference
- Host reference BPE. OWNER: CpuRef.
- specials
- Special-token registration for named vocabularies. OWNER: Main.
- tokenizer
- Host tokenizer: the crate’s public entry point. OWNER: Main.
- vocab
- Vocabulary and merge-table loading. OWNER: VocabLoad.
Structs§
- Encoding
- A tokenizer’s identity: the artifact its ranks came from and the split pattern that belongs to it.
- PairKey
- An adjacent token pair, packed as the merge-table key.
- Rank
- A merge-table rank. Lower ranks merge first.
- TokenId
- A vocabulary token id.
Enums§
- Exatok
Error - Errors surfaced by
exatok.
Constants§
- FNV1
A32_ OFFSET_ BASIS - FNV-1a 32-bit offset basis.
- FNV1
A32_ PRIME - FNV-1a 32-bit prime.
Functions§
- byte_
token_ ids - The 256 single-byte token ids of
vocabulary, indexed by byte value. - fnv1a32
- FNV-1a 32-bit over
bytes, seeded withhash. - trap_
program - Lower an invalid builder shape to an explicit IR trap program.