Skip to main content

Crate exatok

Crate exatok 

Source
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, 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.

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§

ExatokError
Errors surfaced by exatok.

Constants§

FNV1A32_OFFSET_BASIS
FNV-1a 32-bit offset basis.
FNV1A32_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 with hash.
trap_program
Lower an invalid builder shape to an explicit IR trap program.