exatok 0.1.1

Exact GPU-resident BPE tokenizer whose token ids match tiktoken byte for byte
Documentation

exatok

exatok turns text into the token ids a language model expects. It is a byte-pair encoding tokenizer, it is built to run on the GPU through the vyre compute stack, and it is exact.

Exact means one specific thing here: for every input, exatok produces the same ids as tiktoken, byte for byte. Not almost the same, and not the same on typical text. If a tokenizer's ids differ from the model's, every embedding lookup reads the wrong row, so an approximate tokenizer is not a faster tokenizer. It is a broken one. Exactly one divergence is known, it is unreachable from any of the four shipping vocabularies, and it is the case where tiktoken itself is wrong: see "Status of the GPU path" for the rule, the measurement, and the test that fires if a vocabulary edit ever makes it reachable.

The GPU path is held to that same standard. It is not a fast approximation with a CPU fallback for hard cases. It computes the same sequential leftmost lowest-rank merge order the reference does, and it is checked against the reference on real vocabularies and real text.

The device path is callable now. DeviceTokenizer::encode is public, its ids are verified byte for byte against the host reference on a real RTX 5090, and it converges a batch spanning several workgroups in one dispatch. On the publishable paired cells the device path beats one host core on prose, code and cjk and loses to it on short pretokens, so read "Status of the GPU path" below before you plan around it. Everything else described here works today on the host.

Try it

The source lives in a PRIVATE repository at github.com/santhreal/exatok: it is not publicly browseable, and the crate is not on crates.io, so build the binary from a checkout you already have:

cargo build --release -p exatok

The build does not put the binary on your PATH. The examples below invoke it through cargo run --release -p exatok --, which works from the checkout without any PATH edit; the built binary itself is at target/release/exatok under the cargo target directory.

Named vocabularies are read from $EXATOK_VOCAB_DIR, which defaults to ~/.cache/exatok-vocab. The rank files are OpenAI's public blobs, the same files tiktoken itself downloads, one URL per name: https://openaipublic.blob.core.windows.net/encodings/<name>.tiktoken with <name> one of cl100k_base, r50k_base, p50k_base, o200k_base. Fetch the ones you need into the directory, for example:

mkdir -p ~/.cache/exatok-vocab
curl -fL -o ~/.cache/exatok-vocab/cl100k_base.tiktoken \
  https://openaipublic.blob.core.windows.net/encodings/cl100k_base.tiktoken

The SHA-256 tiktoken pins for each file, so you can verify a download: cl100k_base 223921b76ee99bde995b7ff738513eef100fb51d18c93597a113bcffe865b2a7, r50k_base 306cd27f03c1a714eca7108e03d66b7dc042abe8c258b44c199a7ed9838dd930, p50k_base 94b5ca7dff4d00767bc256fdd1b27e5b17361d7b8a5f968547f9f23eb70d2069, o200k_base 446a9538cb6c348e3516120d7c08b09f57c36495e2acfffe59a5bf8b0cfb1a2d. exatok does not check the hash; vocab::load verifies the token and pair counts instead, so a truncated rank file fails to load rather than encoding wrongly.

With a rank file in place, encode some text:

cargo run --release -p exatok -- encode --vocab cl100k_base --text "hello world"

That prints:

15339 1917

Those are the ids tiktoken gives for the same bytes and the same vocabulary.

Use it from Rust

Add the dependency by path while the crate is unpublished:

[dependencies]
exatok = { path = "path/to/exatok" }

Then load a vocabulary and encode:

use exatok::vocab::{self, CL100K_BASE};
use exatok::{Encoding, TokenId, Tokenizer, specials};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Named vocabularies live in $EXATOK_VOCAB_DIR, defaulting to
    // ~/.cache/exatok-vocab.
    let path = vocab::artifact_dir().join("cl100k_base.tiktoken");
    let mut vocabulary = vocab::load(CL100K_BASE, &path)?;
    specials::register(&mut vocabulary, CL100K_BASE.name)?;

    let tokenizer = Tokenizer::new(
        vocabulary,
        Encoding::new(CL100K_BASE.name, CL100K_BASE.pattern),
    )?;

    let ids = tokenizer.encode(b"hello world");
    assert_eq!(ids, vec![TokenId(15339), TokenId(1917)]);
    assert_eq!(tokenizer.decode(&ids)?, b"hello world".to_vec());
    Ok(())
}

Tokenizer is the whole host pipeline: split, map bytes to ids, merge to a fixpoint. The command line calls Tokenizer::encode for every subcommand, so the library and the tool cannot drift apart. vocab::load verifies the artifact's token and pair counts, so a truncated rank file fails to load instead of encoding wrongly. specials::register adds the special tokens, such as <|endoftext|>, that a rank file does not carry.

Tokenizer::encode never emits a special id: ordinary encoding merges byte pairs through the pair table, no special is in that table, and so the text <|endoftext|> encodes to the ids of its own bytes. That matches the reference tokenizer's encode_ordinary. For the mode that recognizes a declared special before pretokenization and emits its single id, use specials::encode_allowed.

Vocabularies

Four vocabularies have names, and a name carries everything needed to encode with it:

Name Split pattern Tokens Derived pair entries
cl100k_base cl100k-base 100256 233378
r50k_base gpt2 50256 108299
p50k_base gpt2 50280 108599
o200k_base o200k-base 199998 446189

You can also load an artifact from a path. Three formats are supported:

  • .tiktoken rank files, through Vocabulary::load_tiktoken.
  • HuggingFace vocab.json plus merges.txt, through Vocabulary::load_huggingface.
  • HuggingFace tokenizer.json, through Vocabulary::load_tokenizer_json.

The two HuggingFace paths are separate code rather than one path with a switch, because the formats carry rank differently. A merges.txt file gives rank by line index, while a .tiktoken file's rank column doubles as the token id.

The merge table is derived exhaustively. For every token, every split into two in-vocabulary halves becomes a table entry. This is easy to get wrong. cl100k_base has 233378 pair entries. A loader that reads only the canonical split from merges.txt finds roughly 100000 of them, and it still encodes most English prose correctly, which is why the pair count is checked at load time. The token ing, id 287, has two splits, i plus ng and in plus g, and merges.txt records one. Encoding can reach that token by either split, so both are needed. For r50k_base the gap is exact and checked: merges.txt gives 50000 entries where exhaustive derivation gives 108299.

Cross-format agreement is checked on real artifacts. The gpt2 bundle matches r50k_base on all 50256 ids, and Xenova/gpt-4 matches cl100k_base on all 100256, with the HuggingFace rank plus 256 equal to the tiktoken id. That is agreement on precedence, not merely on membership.

How the encoding works

A pretoken is a chunk of the input that merges never cross. A rank is a merge's priority, and a lower rank wins. The reference algorithm is sequential and runs per pretoken:

  1. Split the input into pretokens with a regex-derived pattern.
  2. Start each pretoken as one token per byte.
  3. Repeatedly find the leftmost lowest-rank adjacent pair and merge it, using strict < so that a tie goes to the leftmost pair.
  4. Stop when no adjacent pair is mergeable.

Step 3's tie-breaking is load bearing. Ranks tie in real vocabularies, and a <= slip changes the output.

Parallelism runs across pretokens, not within one. Pretokens are tiny. The median is 3 bytes, over 99% are at most 16 bytes, and the mean pretoken takes 3.05 merges. There is very little parallelism inside one pretoken and a great deal across the roughly 250 million of them per gigabyte.

The merge loop updates ranks incrementally. A merge at position i changes the sequence only at i, so only the two pairs adjacent to the merge site need their ranks refreshed. Every other pair keeps both of its elements and therefore its rank. This reproduces the full-rescan rank array exactly while cutting random memory lookups from 2.77 per byte to 1.50, a 45.8% reduction measured on real cl100k_base pretokens. It removes redundant lookups only. It never changes which merge is selected, so it rests on no assumption about which states are reachable.

Command line

The examples below write the binary as exatok. Run it as cargo run --release -p exatok -- from a checkout, or put target/release/exatok on your PATH.

encode prints space-separated ids. Pass --format json for a JSON array instead. To read a file, use --file, and to read standard input, pass neither:

exatok encode --vocab cl100k_base --file corpus.txt
cat corpus.txt | exatok count --vocab cl100k_base

count prints the token count and nothing else, which is what you want for a context-budget check.

decode takes ids and writes the original bytes to standard output. It writes bytes rather than text, because a token boundary can fall inside a UTF-8 sequence:

exatok decode --vocab cl100k_base --ids "15339, 1917"

split shows the pretokenizer's output, one pretoken per line. Use it when ids look wrong and you want to see whether the split or the merges caused it:

exatok split --vocab cl100k_base --text "don't stop"

info reports a loaded vocabulary's sizes, its split pattern, and its special tokens. parity-status lists the four named vocabularies and tells you which are present on this machine:

exatok info --vocab cl100k_base
exatok parity-status

A name is not a path

These are two different things, and the command line keeps them apart on purpose.

A name is one of cl100k_base, r50k_base, p50k_base, or o200k_base. A name knows its own split pattern, so --pattern is rejected alongside --vocab rather than silently ignored. A name is also loaded with its token and pair counts verified.

A path is loaded by extension. Use --vocab-path with a .tiktoken rank file or a .json tokenizer bundle:

exatok encode --vocab-path ./cl100k_base.tiktoken --pattern cl100k-base --text hi

--pattern is required with a path. A rank file does not record which pretokenizer it belongs to, and the three patterns produce different ids for the same bytes, so guessing would give you a wrong answer that only a parity run would catch. An error is better than a guess here.

The binary exits 0 on success, 2 on a usage or argument error, 3 on a vocabulary error, 4 on an input or stream error, 5 when it cannot write its output, 6 when --device gpu was asked for but no CUDA device is usable or this build has no cuda feature, and 70 on an internal error. A device fault is its own code on purpose: the flag was accepted, and only the machine or this build's feature set could not honor it. On a 6 no ids were produced and nothing was encoded on the host instead, so a device request never degrades into a CPU run you did not ask for. Nothing exits 1, so a script can tell "ran and reported" apart from "could not run". --help prints the same seven codes, and tests/cli.rs asserts that table equals the constant set.

Status of the GPU path

Read this before you plan around the device path. The short version: the host path is exact, the device path is exact and public, and on the publishable paired cells it beats one host core on prose, code and cjk, and loses to it on short pretokens. Current figures come first below. The measurement record, including every withdrawn figure and its provenance, sits at the end of the section, and CHANGELOG.md carries the same record under "Verified" and "Known limitations".

Exactness

The host path is complete. exatok is byte-exact against tiktoken 0.12.0 on cl100k_base, r50k_base, p50k_base and o200k_base, over 42 text cases plus 9 byte cases whose inputs are not valid UTF-8. The fixtures are committed, so the test suite never invokes Python. The host path also agreed with tiktoken 0.12.0 on all four corpus shapes over 372,347 tokens on identical bytes. That comparison is a byte comparison, so no amount of machine noise touches it.

ONE CHARACTERIZED DIVERGENCE FROM tiktoken EXISTS, AND NO INPUT TO THESE FOUR VOCABULARIES CAN REACH IT. Given a vocabulary where one special token is a strict PREFIX of another, and a call that allows only the LONGER one, tiktoken 0.12.0 matches the shorter disallowed special, sees that it is not allowed, and resumes at its start plus one byte, which is PAST the offset where the allowed special begins. The allowed special is therefore never matched and is emitted as ordinary text. exatok is leftmost-longest and returns the allowed special's id. This was measured stable across PYTHONHASHSEED 0 through 7 and both special_tokens insertion orders, so it is the matching rule and not hash order.

None of cl100k_base, r50k_base, p50k_base or o200k_base declares a strict prefix pair, so the divergence is unreachable from a shipping vocabulary. The margin is thin in two of them: cl100k_base and o200k_base each declare <|endofprompt|> alongside <|endoftext|>, which share a seven-character prefix without either being a prefix of the other. A test pins that margin per vocabulary, at 7, 0, 0 and 7, and fires on any edit that closes it, because closing it is exactly what would make this divergence reachable. exatok's rule was not changed to match tiktoken, and both rules are pinned from both sides so neither can drift unobserved.

Every device program is individually parity-verified against a host oracle, and those checks run on a real CUDA device as well as on the vyre reference backend. The programs are the merge-rank table probe, segmented leftmost argmin selection, stream compaction, merge application, and the convergence loop. The end-to-end device encode matches the host reference byte for byte on real cl100k_base and o200k_base artifacts.

The device path had two independent exactness defects during development, both root-caused and fixed in vyre, and both fixes are confirmed by evidence rather than by a green run. The multi-workgroup form: the cooperative grid barrier's release counter is module scope, and the resident launch path never zeroed it between launches, so from the second grid-sync launch on each barrier was an immediate pass-through and the loop reported convergence on a partially written state. The single-workgroup form: the in-kernel loop cleared its changed flag across the back edge with no barrier, so one warp could exit early, freeze a partial transfer, and still report convergence. The evidence for the second is a controlled intervention: removing only that barrier reproduces 4 failures in 30 runs, restoring it gives 0 in 60, same binary and machine with a one-line change, Fisher exact p = 0.0087. The fixes, the rate history, and the refuted suspects are in the measurement record below and in CHANGELOG.md under "Known limitations".

What the device path does

  • It is public API. DeviceTokenizer::encode encodes on the device, and its ids are byte-identical to the host reference on every case tested.

  • A batch spanning more than one workgroup converges in a SINGLE dispatch. The convergence flag is ordered by a grid-scope barrier, so one workgroup cannot erase another's signal and no group can retire while another still has work. On CUDA that barrier is a native cooperative launch, which requires every block to be resident on the device at the same time.

    Read that as a property of how exatok invokes vyre, not as an intrinsic property of the tokenizer. vyre delivers the cooperative barrier on its dispatch path, which zeroes the grid barrier counter before each launch, and refuses it on the ahead-of-time compiled-pipeline path, which does not. exatok reaches the device only through dispatch, so it gets the supported path. If you compile the same program ahead of time yourself, you will get an explicit refusal rather than a barrier that does not synchronize.

  • Cooperative residency is the ceiling on BATCH SIZE, and it is QUERIED rather than written down. DeviceTokenizer::queried_block_ceiling asks the backend how many blocks of 256 threads can be co-resident, and a dispatch asks for three quarters of that. The headroom is not tuning: the query answers with a thread residency bound, while the stricter limit that register and shared-memory pressure impose is enforced only at launch, so one register added to the pass body lowers the real limit without moving the query at all. A hardcoded number would also be wrong on the next card.

    On this device the query admits 1020 blocks of 256 threads, which is 261,120 resident threads. Expressed in pretokens per dispatch it depends on pretoken length, because a segment costs its token count plus one word to record that count: 130,560 one-token pretokens, 52,020 four-token pretokens, 16,320 fifteen-token pretokens, and 1,020 at the 255-token maximum. Those four figures are device::segments_per_dispatch evaluated at 1020 workgroups, and tests/feature_matrix.rs asserts them, so this list cannot drift from the packing rule. A batch that exceeds residency is refused with the block count and the limit named. It is not split behind your back, and it is not quietly run on fewer groups.

    A pretoken above 255 tokens, which is 256 bytes since merging starts one token per byte, is not refused and is not split either: splitting it would merge across a boundary the reference never crosses. It is encoded on the HOST, by the same reference loop over the same table, and Routing reports how many pretokens took that path. Read routing().all_on_device() before believing a run was a GPU run.

    Whether cooperative residency affects throughput is unmeasured. An earlier sweep of that question was withdrawn as vacuous: the knob it swept sizes a batch while the grid is derived from the state array, so every row ran the same single-segment dispatch, and at one segment the non-grid-synchronized primitive is selected and no grid barrier executes at all.

Pretokenization stays on the host

The split into pretokens runs on the host in every configuration, including device encodes. A device boundary pass exists, and it is not part of the shipping path. Read this before you propose moving the split to the device.

The non-default gpu-pretokenize feature adds the public exatok::gpu_pretokenize module: a pointer-doubling pass that reproduces the host splitter's cl100k_base offset vector exactly, proven by a 21-case parity suite that compares whole offset vectors on a real CUDA device, plus five host-side unit tests. Nothing on the shipping path calls it, and no command line flag is gated on it. Its status is experiment, not capability: it is a measured negative result, kept runnable so the measurement re-runs on later hardware.

Two reasons it is not wired in, decisive first. The pass implements cl100k_base only, while the crate serves three split patterns, so wiring it would fork boundary production by encoding and leave two producers that must agree byte for byte forever, on the exactness claim that is the product. That argument does not expire with faster hardware. The supporting reason is measured: 45x slower than the host splitter at 256 KiB on an RTX 5090, and the loss is in the kernel, so no dispatch or residency work can reach break-even. The numbers, their method, and the full argument are in the src/gpu_pretokenize.rs module documentation; the design analysis the pass was built from is docs/pretokenization-dfa.md.

Re-run the verdict with both features, since the suite dispatches on a real device:

cargo test -p exatok --features cuda,gpu-pretokenize --test gpu_pretokenize_parity

What the measurements say

Two caveats decide whether any figure here may be quoted. FIRST, EVERY GPU ABSOLUTE WAS CAPTURED WITH AN EXTERNAL CONSUMER ON THE CARD. An unrelated llama-server process held 24,204 MiB of a 32,607 MiB RTX 5090 for the whole measurement effort, with all layers resident, and was observed at up to 52 percent GPU utilisation. Captures labelled "quiet box" were quiet on load average, which measures CPU and says nothing about GPU contention, so treat every absolute millisecond and MiB/s below as an upper bound on what this machine can do, not a measurement of it. Anyone measuring here should record nvidia-smi --query-gpu=utilization.gpu,memory.used --format=csv beside load average. SECOND, A SINGLE WARM ENCODE IS NOT A MEASUREMENT. Device prose encodes of the same bytes in the same process vary by 1.337x between fastest and slowest of seven, so any margin smaller than that spread is a draw from a band, not a result. What survives both caveats is anything measured as a within-run ratio, because a common-mode contaminant cancels, plus exactness, which is a byte comparison.

A certified third-party host table is not possible on a shared box, and that is measured rather than suspected. Across 56 baseline cells the foreign-load ratio ran from 1.607 to 14.163 cores' worth of work belonging to other processes, median 8.062; all 56 exceeded the certification gate, and 39 still exceeded a hundredfold looser one. The timed region was not the problem: the shortest best-case cell was 0.428 s against a 0.25 s floor, and clock drift over the sweep was 0.011. Single-threaded cells kept essentially their whole core (minimum achieved parallelism 0.9938) while 1.6 to 14.2 foreign cores ran alongside, so a per-thread efficiency check was blind to all of it. Correctness was untouched, since every measured library still produced ids identical to the reference: contention corrupts timing, not answers. A quiet machine is a precondition for a certified host table, not a nicety.

THE CURRENT STANDING. Paired captures under the interleaved harness (benches/throughput/device.rs, 8 interleaved rounds per cell, a cell publishable only at delta spread at or under 0.20 and host-load drift at or under 0.25) put the device against the host on 256 KiB per shape, before and after the host-cost wave recorded in CHANGELOG.md. After the wave, publishable cells: prose device by 2.6034x (drift 0.1894, corroborated by a refused capture at 2.7494x and a second publishable cell at 2.9107x with drift 0.2481), code device by 1.4601x (drift 0.1679, corroborated at 1.6887x and 1.5428x), cjk device by 1.1455x (drift 0.1760, corroborated at 1.2274x and 1.1804x), the first certified cjk cell after three pre-wave refusals agreeing at 1.12 to 1.21x. Short pretokens is host-faster by 1.8365x, 1.9200x and 1.9533x across three refused post-wave captures (drifts 0.2527, 0.5140 and 0.2947, agreeing to 6 percent); its last publishable cell, 2.6372x host, predates the wave. Before the wave the publishable cells were prose 2.4593x, code 1.2790x and short pretokens 2.6372x host, so the wave moved every shape toward the device and cjk across the line. A pre-registered prediction, written down before any capture ran, had cjk and code flipping to the device and prose and short pretokens holding still; the flips appeared at about half the predicted magnitudes and prose moved instead, so the prediction is directionally confirmed and numerically refuted. The full review is the first entry under "Verified" in CHANGELOG.md.

THE MONOTONE ORDERING IS THE ONE PERFORMANCE CONCLUSION THAT HAS SURVIVED EVERYTHING. It has reproduced across four captures, three box states and two sampling methods: the device is best where pretokens are LONGEST and degrades monotonically as they shorten, an ordering that spans 5.4x against within-run spreads of 1.13x to 1.34x, far larger than its own noise.

CRITERION MEDIAN over a sustained back-to-back loop, which keeps the device saturated in a way no caller does, and is the right figure for a serving loop: 1.59x to 8.20x slower. Host, then device, in milliseconds: prose 15.83 and 25.24, code 13.47 and 42.60, cjk 9.86 and 46.46, short pretokens 4.14 and 33.95. The device plateaus around 25 MiB/s on this contract. Reported alongside the warm wall because quoting one contract as the other once caused a 1.89x phantom disagreement between two independent measurements of the same corpus. These figures are PAIRED: host, device, and tiktoken ran the same corpus bytes, verified by digest, and EXATOK_BENCH_CORPUS pins a written corpus directory so a rerun cannot silently measure a different tree.

WHERE THE TIME GOES. A dispatch is ONE cooperative kernel launch with in-kernel grid barriers, flat in the pass budget: 88 cuLaunchCooperativeKernel calls and zero cuLaunchKernel for 22 prose encodes of 4 dispatches each, with one synchronization point per dispatch and no per-pass host round trip. Barriers are measured and cheap: a bare cg::this_grid().sync() is 1.82 us at 765 blocks and this project's lowering is 2.36 us. Host work dominates every shape, but the device share is NOT uniform: kernel over wall as median over median on the post-fix paired capture (kernel 0.7916, 2.3846, 2.6780 and 0.2915 ms against walls 6.4540, 9.5091, 8.3161 and 9.0165 ms) is prose 12.27 percent, code 25.08, cjk 32.20, short pretokens 3.23. Kernel work is a rounding error only on short pretokens; on cjk the kernel is a genuine second lane, so cjk must not be called host bound. The re-taken host decomposition, median of 15 counted encodes at load average 11.3 on a shared box, puts the dispatch row at 3.85 ms on prose and 3.37 on short pretokens, and vyre's share of the wall at 27.2 to 41.5 percent across the four shapes; the walls those rows divide are contended medians, not the publishable paired figures above. There is NO dominant cost: the largest single row is about 30 percent and is itself a composite, which is a property of the workload and the reason five earlier single-mechanism theories each explained so little. Short pretokens is the shape that locates host problems, since its kernel is 3.23 percent of the wall; prose is the worst shape to judge a change on, since it sits close enough to the host reference that box state alone swamps any delta.

Three fixes landed on counted evidence rather than walls, and a count does not move with box state. The 16 MiB merge table is uploaded once per encode through vyre's resident-buffer API instead of once per dispatch: merge table copies charged per dispatch fell from 2.09 to 0.02, and the remaining single upload is about 1.9 ms at the measured transfer rate. The PTX cache digest is memoized on the caller's long-lived program instead of recomputed on a per-dispatch clone: digest computations per warm encode fell 6 to 0 on cjk and code, 4 to 0 on prose, and 3 to 0 on short pretokens, and per-dispatch host allocations on short pretokens fell about 16x, from roughly 1600 calls to roughly 100. Residency is scoped to the ENCODE, not the tokenizer, deliberately: vyre resolves a resident handle by bare id with no owner check, so a handle cached on a long-lived tokenizer could name a live buffer belonging to a different backend instance, same size, different contents, wrong merges, plausible ids.

The SPEED comparison against tiktoken is unsettled, and this README claims no GPU speedup over a CPU tokenizer as a general result. The multipliers once quoted here are withdrawn, for the structural reason that tiktoken runs in a separate process and cannot be paired in-process; the record is below. On paired captures the device prose path and tiktoken are close enough that neither is established as faster: one capture had the device ahead by 1.3 percent (18.29 against 18.05 MiB/s) and another had tiktoken ahead by 7 percent. It was recorded as a tie.

Measurement record

Everything withdrawn or superseded, kept with its provenance so none of it has to be re-measured to be believed. CHANGELOG.md under "Known limitations" carries the same record with the full narrative.

  • THE PRE-RE-TAKE WARM TABLE, superseded by the publishable cells above. Median of 7 alternated repetitions per cell, device and host paired one repetition at a time in one process, load average 2.25. Device ms, host ms, ratio, device max/min: prose 15.99 and 16.13, 0.991x, spread 1.337x; code 30.24 and 13.68, 2.210x, spread 1.233x; cjk 27.97 and 10.07, 2.779x, spread 1.259x; short pretokens 23.01 and 4.28, 5.372x, spread 1.129x. Both columns are this crate, the device path against this crate's own host path; they do not come from the third-party baseline sweep, which contains no row for this crate and gives the host leg no independent corroboration. Run-to-run variance exceeds within-run variance: cjk moved from 2.106x to 2.779x between two captures that both used medians, beyond what its 1.259x within-run spread accounts for, so settling a magnitude needs repeated captures, not more samples per capture.
  • EARLIER REVISIONS CLAIMED A DEVICE WIN ON PROSE of 19 percent, then of 10 to 16 percent across three observations of 0.839, 0.839 and 0.900. Both are WITHDRAWN: each was a single encode drawn from the 1.337x band, so a 16 percent margin sits inside the noise, and the four-digit agreement between the first two observations was coincidence.
  • A PER-PASS COST MODEL IS FALSIFIED, not merely unmeasured. The per-pass cost the remainder would require spans 20x across shapes: 352.8 us on prose, 180.3 on code, 185.5 on cjk, and 3531 on short pretokens. Against data volume the same remainders spread only 2.0x to 2.7x, so the cost tracks ELEMENTS SWEPT over the padded state array rather than passes taken. The early exit (Node::Return not lowering to PTX, a real defect fixed on correctness grounds) is bounded twice over: MAX_STRIDE_SPREAD caps a dispatch's longest member at twice its shortest, bounding wasted passes at 2x by construction, and the measured effect is 1.155x to 1.540x fewer pass SLOTS, which does not predict time on these shapes. The gap between the two timing contracts on prose (13.67 ms warm against 25.24 sustained) is real and is itself evidence: a sustained loop degrades host-side allocator and cache state, which is consistent with the cost being host work rather than kernel work.
  • THE PRE-FIX PHASE DECOMPOSITION, kept because the decomposition method is what a reader should reproduce; its absolutes are superseded by the re-take above. Prose, median of three captures, 19.656 ms observed against 19.649 ms named: dispatch 6.308 (30.7 percent), table upload 2.816 (15.1), output assembly 2.787 (14.3), teardown 1.436 (7.3), batching 1.153 (6.1), loop batch build 1.143 (6.1), byte encode 1.053 (5.4), pretokenize 0.950 (4.8), caller inputs 0.266 (1.4), id assembly 0.148 (0.8), table free 0.140 (0.7), and residency query plus table pack plus plan lookup under 0.003 combined. Short pretokens, 23.114 ms observed: dispatch 4.889, teardown 3.522, batching 2.876, table upload 2.817, byte encode 2.359, output assembly 2.306, pretokenize 1.467, loop batch build 0.778, id assembly 0.376, caller inputs 0.371, table free 0.088. Instrumenting the encode into named phases cut unattributed time from 3.45 ms on short pretokens and 1.34 ms on prose to 0.007 to 0.009 ms on all four shapes. The largest single identified item was teardown of the per-pretoken vectors, 22.94 ns per pretoken on prose and 23.59 on short pretokens, which earlier measurements dropped at end of frame into the remainder by construction. An earlier attribution named packing, staging, readback, unpacking and id assembly as the per-element cost at 0.27 ms and concluded that moving state construction to the device "would have bought a quarter of a millisecond". Measured, those five come to 1.253 ms on a prose encode and padded state construction alone (loop batch build, LoopBatch::new at src/device.rs:981) is 1.143 ms, so that redesign was worth roughly 1.1 ms, about 4.5x what was claimed; packing and unpacking together are 0.11 ms and host routing is zero on all four shapes.
  • THE vyre SHARE PRE-FIX, priced as table upload and free measured in path plus its timed dispatch window minus CUDA event time plus resident staging fitted in-run: 20.7 to 24.5 percent on short pretokens, 27.0 to 33.3 on prose, 45.9 to 54.3 on cjk, and 36.8 to 52.0 on code. Total vyre cost per prose encode measured 5.3 to 6.6 ms, of which the 16 MiB resident table upload plus free was 2.96 ms. One limit is stated rather than hidden: vyre's own counters put 99.8 percent of the timed window in enqueue, and that counter contains kernel execution and the 4.5 MB readback as well as launch preparation, which neither its counters nor an outside observer can split. The floor arithmetic from the same pre-fix capture still holds as arithmetic on measured components, not as a measurement: 1.181 pretokenize plus 0.339 kernel plus 0.173 readback plus 0.12 launch is about 1.8 ms, roughly 9.5x faster than one core.
  • THE KERNEL-SHARE INSTRUMENT. An earlier revision said 0.38 ms and 2.5 percent, and that is WITHDRAWN, not averaged into the figures above: the table it came from fits neither the per-encode nor the per-dispatch convention against the current instrument (ratio spreads of 3.667x and 7.334x), so its provenance is unestablished. The nsys-derived 11 to 16 percent that reading had itself withdrawn is approximately corroborated by the current 10 to 12 percent on prose, and prose is corroborated by two independent instruments: a paired harness reads 10.35 percent (median kernel over median wall) and 11.97 (median over best wall), and a separate profiling example reads 8.26 and 11.80 on its own two runs. The instrument's span is settled from source: timed_device_ns_total accumulates once per timed dispatch, so a delta taken around one encode is the sum over every dispatch that encode issued, and coverage counters rule out a subset explanation (zero timed dispatches missing device time on every run, timed dispatches equal to kernel launches exactly). Pre-fix bands for the same quantity: short pretokens 2.4 to 3.3 percent, prose 8.3 to 11.8, code 14.7 to 17.5, cjk 22.3 to 23.5. Per-encode kernel medians, two captures, prose then code then cjk then short pretokens in ms: 0.8275, 2.4527, 2.5842, 0.2844 and 0.8873, 2.2844, 2.5954, 0.3290. Older figures, kernel then H2D then D2H in ms, kept only for the transfer breakdown: prose 0.335, 3.458, 0.263; code 0.945, 5.100, 0.311; cjk 1.620, 5.136, 0.215; short pretokens 0.056, 2.764, 0.389.
  • THE DIGEST MEMO WALL EFFECT, cross-checked by two independent accountings. The count itself reads off a bimodal split between a 741 to 1083 us computation on a 12,146 node program and a 0.02 to 0.6 us memo hit, so it is not a threshold anyone chose. The phase probe predicted an enqueue saving of 7.620 ms on cjk and 5.797 on code, and the vyre ownership row, computed by a different route, fell 7.732 and 5.671; they agree to 1.4 and 2.2 percent. Prose and short pretokens agreed only to 31 and 61 percent, both terms being sub-millisecond and measured across two processes, so nothing is claimed for those two.
  • THE TWO EXACTNESS DEFECTS, RATE AND REFUTATIONS. Rate history: about 5 failures in 10 before any fix; 2 in 22 after the grid-counter fix, the genuine residual; one 16-of-16 clean stretch that was luck rather than evidence (about 22 percent likely at that rate, and the change landing between those sweeps proved to be debug-gated stderr instrumentation with no behavior change); then 0 in 60 after the back-edge barrier fix. One 40-run sweep is excluded entirely: 24 of its runs were build breaks from unrelated concurrent edits, and a guard separating compile failure from test failure is the only reason those 24 were not recorded as a catastrophic regression. Two independently captured failures corroborate the mechanism, both concurrent_encode_matches_serial_encode_exactly, both segment 11 after exactly 8 passes, with 4 and 1 live tokens; both are now known to have been taken while the barrier-removing probe was in the tree, so they document the barrier's absence rather than a residual, and across failures the victim segment moves (15, 11, 4, 4, 8 observed, and 11 twice more), which distinguishes a scheduling race from a fixed pass-body defect. The fix moved one barrier rather than adding one, at an unchanged three barriers per iteration, and structural contracts assert that a barrier stands between the exit read and every write to the changed flag in back-edge order. Refuted along the way, recorded so none is re-investigated: resident buffer id reuse (ids never recycle, and a stale handle fails closed), recycled device pointers through the bucket pool (resident buffers bypass the pool entirely), a stale changed buffer under residency (rebuilt zero-filled per dispatch), an emit-time-baked gridSize (read from %nctaid in-kernel), and collapsed barrier instances (a four-wave program emits eight barrier sites with distinct increasing multipliers, and a GridSync inside a loop body is refused at emit time).
  • THE tiktoken SPEED MULTIPLIERS ARE WITHDRAWN. An earlier revision claimed the host path ran 1.57x faster than tiktoken on prose, 1.19x on code and 6.10x on short pretokens, and tied on cjk. tiktoken prose measured 10.03 MiB/s in the capture behind the 1.57x and 18.05 MiB/s in a later one, so the baseline moved 1.80x, more than the margin claimed, and on the later capture the comparison inverts with tiktoken 18 percent ahead (18.05 MiB/s against the host path's 15.35). On a re-run, single-threaded tiktoken read 13.05 to 25.07 MB/s against an earlier 17.62 to 25.04, a 26 percent drop at the low end. One direction survives qualitatively: short pretokens favours this crate heavily (60.83 MiB/s against 10.12), stated as a direction and not published to two digits.

Multi-merge is permanently off

exatok has a multi-merge feature that applies every merge at the winning rank in one pass. It is off by default and it stays off. Do not enable it.

The shipping merge loop fuses one pair per pass instead. That looks more expensive than it needs to be, and it is not. This section is the reason, so read it before you propose a faster pass that merges more than one pair.

The counterexample

Start with the whole refutation, because it is four tokens long. A state is a sequence of token ids. An initial state is what raw input looks like before any merge has happened: one token per byte. Take a table with two entries, and feed it four copies of one byte:

table  (0,0) -> 1 @rank 1     (1,0) -> 2 @rank 0
input  [0, 0, 0, 0]
  one pair per pass -> [2, 0]     multi-merge -> [1, 1]

Read the two answers. They differ, so one of them is wrong, and the reference algorithm defines which. Multi-merge commits to rank 1, the lowest rank present, and fuses both (0,0) occurrences in the same pass. One pair per pass fuses the left (0,0) alone, and that exposes (1,0) at rank 0. Rank 0 is below the rank 1 that multi-merge already committed to, so the sequential rule takes it, and taking it consumes the token the second rank-1 occurrence needed.

Three tokens cannot diverge, and neither of the two entries can be dropped, so this is the smallest counterexample that exists. Note what kind of state it is: an initial one. Restricting multi-merge to raw input therefore does not rescue it.

Real cl100k_base diverges too, on states it can never reach

You might expect a real vocabulary to be safe. cl100k_base is not, and the shape of its failure is the part to understand.

1917 four-token cl100k_base states diverge. Here is the smallest, with the ids exactly as shipped:

state ['e', 'nc', 'e', 'nc'] = [68, 1031, 68, 1031]
  one pair per pass -> [768, 1031]     multi-merge -> [967, 967]

That runs on a real rank inversion. 'enc' ranks 967 and 'ence' ranks 768, so the merge that consumes 'enc' is cheaper than the merge that mints it.

Now the qualifier, and it is the load-bearing half of the finding. None of those 1917 states is REACHABLE. A state is reachable when the tokenizer can actually produce it from raw bytes on its way to an answer. Feed the bytes of every one of the 130 distinct divergent states back in as single bytes, and both paths agree on all 130. "encenc" gives [967, 967] either way, because 'en' ranks 268, below 'nc' at 1031, so the greedy rule fuses 'en' first and never assembles the dangerous state.

Do not read that as a reprieve. It says the ids this crate ships today happen to be safe. It does not say multi-merge is exact, and the counterexample above is an initial state, so reachability is not the property doing the work.

The danger hunt was exhaustive, so you do not need to redo it

The search for dangerous shapes covered the real table completely. It was not sampled. The method is short. Take every entry (a, b) -> X at rank r in cl100k_base, and for every token c in the vocabulary, check both (X, c) and (c, X) for a rank below r.

Those two pairs are the complete set of local shapes that can lower the minimum rank, which is what makes the search exhaustive rather than merely large. A fusion rewrites only two adjacent positions, so the only new pairs it can create are (prev, X) and (X, next). Nothing outside that window can undercut the rank the pass committed to.

The counts, in order: 560 danger triples, meaning entries that have such a c; 304 of those diverge when the four-token state [a, b, a, b] is fed in directly as an arbitrary state; 0 of those are reachable from raw bytes, checked by re-encoding the bytes of all 130 distinct divergent states.

There is an exact criterion, and real vocabularies fail it

Multi-merge is exact on arbitrary states if and only if the vocabulary has parent order: for every (a,b)->X@r and every c, both rank(X,c) > r and rank(c,X) > r. Real vocabularies violate this at a rate far above zero. Over cl100k_base's 233378 pair combinations, counting on the consumer side, which is the direction the proof uses, 56048 combinations violate it.

Two escape routes remain, and both close. Forbidding rank inversions while allowing equality does not help, because two entries at the same rank diverge as well, which makes the strict inequality load bearing. And real cl100k_base survives only because its ids correlate with token length, since ids follow training frequency and shorter pieces are more frequent. Hold the vocabulary structure fixed, change only the id order, and a sweep flips from clean to failing.

That correlation is a fact about how a vocabulary was trained, not an invariant a loader can check. A custom or adversarially ordered vocabulary can break exactness while passing every structural check.

Reading and running the evidence

The full argument, the proof sketch for parent order, and the provenance of every figure above are in the src/confluence.rs module documentation. Reading that file needs nothing.

Running it needs a feature. The module and its differential suite sit behind the non-default confluence feature, because they are evidence rather than tokenizer functionality, and their search and minimization types are not surface this crate wants to stabilize. Enabling it adds the public exatok::confluence module and makes the 22-case differential suite runnable; no command line flag is gated on it and nothing on the shipping path reads it, so it costs compile time and public surface and changes no token id.

cargo test -p exatok --features confluence --test confluence_equivalence

Name the feature. Do not reach for --all-features, which also switches on multi-merge, the one feature this section tells you never to enable.

Tests

cargo test -p exatok

Add --features cuda for the tests that dispatch on a real device:

cargo test -p exatok --features cuda

Those tests are skipped without the feature, so a green run on a machine with no GPU does not tell you the hardware path works.

Add --features confluence for the multi-merge refutation suite:

cargo test -p exatok --features confluence --test confluence_equivalence

That suite is the reproduction path for the section above, and it does not run without the feature. The plain cargo test -p exatok line skips it, so a green run there does not tell you the refutation still reproduces.

Add --features cuda,gpu-pretokenize for the device pretokenization parity suite:

cargo test -p exatok --features cuda,gpu-pretokenize --test gpu_pretokenize_parity

Both features are needed: gpu-pretokenize declares the module and cuda dispatches it. That pass is a measured negative result, kept default-off because it is 45x slower than the host splitter and nothing on the shipping path calls it, so this is the only command that runs it. Note that naming --features cuda alone does not fail, it reports zero tests, which is the same shape as a green run. Gating it also moves five host-side unit tests out of the default cargo test -p exatok; --features gpu-pretokenize restores them without needing a GPU.

Reading further

  • docs/vyre-composition-contracts.md records five contracts vyre enforces but does not document. Each one lets a program build clean and fail only on dispatch. Read it before composing anything out of vyre-primitives.
  • docs/testing-blind-spots.md records defects this crate's tests did not catch, and the mechanism that hid each one.
  • docs/pretokenization-dfa.md covers the split patterns, why the NFA primitives cannot compile them, the host determinization used instead, and the device boundary pass built from that analysis together with the measured verdict against wiring it in.
  • docs/benchmark-method.md covers how measurements will be taken.

License

Licensed under either of

at your option.