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:
[]
= { = "path/to/exatok" }
Then load a vocabulary and encode:
use ;
use ;
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:
.tiktokenrank files, throughVocabulary::load_tiktoken.- HuggingFace
vocab.jsonplusmerges.txt, throughVocabulary::load_huggingface. - HuggingFace
tokenizer.json, throughVocabulary::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:
- Split the input into pretokens with a regex-derived pattern.
- Start each pretoken as one token per byte.
- Repeatedly find the leftmost lowest-rank adjacent pair and merge it, using
strict
<so that a tie goes to the leftmost pair. - 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::encodeencodes 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
exatokinvokesvyre, not as an intrinsic property of the tokenizer.vyredelivers 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.exatokreaches 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_ceilingasks 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_dispatchevaluated at 1020 workgroups, andtests/feature_matrix.rsasserts 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
Routingreports how many pretokens took that path. Readrouting().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::Returnnot lowering to PTX, a real defect fixed on correctness grounds) is bounded twice over:MAX_STRIDE_SPREADcaps 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::newat 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
vyreSHARE 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. Totalvyrecost 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_totalaccumulates 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
vyreownership 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 stalechangedbuffer under residency (rebuilt zero-filled per dispatch), an emit-time-bakedgridSize(read from%nctaidin-kernel), and collapsed barrier instances (a four-wave program emits eight barrier sites with distinct increasing multipliers, and aGridSyncinside a loop body is refused at emit time). - THE
tiktokenSPEED MULTIPLIERS ARE WITHDRAWN. An earlier revision claimed the host path ran 1.57x faster thantiktokenon prose, 1.19x on code and 6.10x on short pretokens, and tied on cjk.tiktokenprose 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 withtiktoken18 percent ahead (18.05 MiB/s against the host path's 15.35). On a re-run, single-threadedtiktokenread 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.mdrecords five contractsvyreenforces but does not document. Each one lets a program build clean and fail only on dispatch. Read it before composing anything out ofvyre-primitives.docs/testing-blind-spots.mdrecords defects this crate's tests did not catch, and the mechanism that hid each one.docs/pretokenization-dfa.mdcovers 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.mdcovers how measurements will be taken.
License
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE)
- MIT license (LICENSE-MIT)
at your option.