tiktoken-encode: GPT-2 BPE encoding speed

A timing project (PER-306): agents make tiktoken's Rust core (src/lib.rs, upstream's file) encode text faster with GPT-2's byte-pair encoding, and the grader times it on held-out documents it never shows, checking every token id against the reference's (wall_ms, minimized). Every improvement here is a patch upstream could take.

File	What it is
autoresearch.toml	the metric (wall_ms, minimized, MMI 15% relative), runner class cpu-s, editable src/**, K = 6; upstream openai/tiktoken, public
PROGRAM.md	instructions for the agents: the encoder, the data, the budget, what counts as cheating
CONTRACT.md	the worker HTTP contract (the template's, plus this project's items)
src/lib.rs	the code being improved: tiktoken 0.14.0's Rust core, upstream's file verbatim to start with
Cargo.toml, Cargo.lock	the workspace: the core's crates (fancy-regex, regex, rustc-hash, bstr) locked, the release profile
harness/worker.py	the frozen HTTP server (Python's standard library): one encoder at startup, then each document's token ids hashed
harness/ffi/	the frozen C interface the server loads (bpe_new, bpe_encode, bpe_free): CoreBPE::new and encode_ordinary
ranks/gpt2.tiktoken	GPT-2's BPE ranks, tiktoken's r50k_base
dockerfile.worker, compose.yaml	Rust 1.99.1 builds the core and the interface; Python 3.13 serves them; worker on core 0, grader on core 1
dockerfile.grader, grader/	the grader (grade.py, standard library only) and the grader SDK (grader/arh_grader, sdk/grader verbatim)
sample/params.json	the public sample: 9 timed and 2 warmup documents of three books, with the reference's answers
LICENSE-tiktoken	tiktoken's MIT licence (src/lib.rs is its code)

The upstream

openai/tiktoken (MIT), release 0.14.0, commit 4e71bbe0c078468e00fefbf94b39849389f346e5: its Rust core src/lib.rs is this project's src/lib.rs unchanged; its Python bindings (src/py.rs, pyo3) are left out, and Cargo.toml is the project's (upstream's crates, its feature python declared but never enabled, a frozen release profile). Why tiktoken rather than Hugging Face's tokenizers (a large crate with a deep dependency tree) or GitHub's rust-gems/bpe (the fast one already: little room left): its core is one 702-line file, its own notes put most of the time in the pre-tokenizer regex, and the algorithmic headroom is on record (rust-gems/bpe reports about 10x over Hugging Face's).

The data

sdk/tiktoken/prepare.py in the platform's repository makes ranks/, sample/ and the held-out set from pinned files (each checked against its sha256), with tiktoken 0.14.0's encode_ordinary as the reference for every answer. The same files give the same bytes.

Source	Licence	Used for
GPT-2's encoder.json and vocab.bpe (openai-community/gpt2: vocab.json, merges.txt, byte for byte the files tiktoken's gpt2 encoding pins)	MIT	ranks/gpt2.tiktoken (equal to tiktoken's r50k_base)
Project Gutenberg: Pride and Prejudice (1342), Alice's Adventures in Wonderland (11), Le rouge et le noir (798)	public domain in the US; the Project Gutenberg header and licence cut off	sample/
Project Gutenberg: Moby Dick (2701), A Tale of Two Cities (98), The Adventures of Sherlock Holmes (1661), Dracula (345), Adventures of Huckleberry Finn (76), La Chartreuse de Parme (796), Faust (2229), Don Quijote (2000), 粉妝樓 (4572, 4573), お目出たき人 (31757), 羅生門 (1982), Λυσιστράτη (17814), Kalevala (7000), La Divina Commedia (1000), Os Lusíadas (3333), Московия в представлении иностранцев (30774), Robinsono Kruso (11511), Az arany szalamandra (18365), בית נכות ההלכות (43740)	public domain in the US; header and licence cut off	held-out: 55 pieces of books, fourteen languages
Django 5.1.2 (whole files)	BSD-3-Clause	held-out
SQLite 3.46.1's amalgamation (pieces)	public domain (SQLite's blessing)	held-out
serde_json 1.0.128 (whole files)	MIT OR Apache-2.0	held-out
lodash 4.17.21 (pieces)	MIT	held-out
generated from seed 306: runs of one character, a word of random letters, scripts without spaces, emoji sequences, combining marks, control characters, whitespace runs, contractions, numbers, base64, hex, minified JSON, URLs, ligatures and full-width forms (23 documents)	made here	held-out

No code the worker's image or its build holds is held out: not Python's standard library (in the image) nor any crate of Cargo.lock (in the build), which the agents' core could read at startup and answer from a table. No Wikipedia text: its CC BY-SA share-alike terms aren't worth carrying for prose the books already cover. The held-out set (projects/tiktoken-encode-heldout/params.json, 98 timed and 2 warmup documents, 9.6 MB, 4.61 million tokens: 55 pieces of books, 22 of code, 23 generated) stays in the platform's repository and the graders' evaluation VMs; no image holds it (tests/projects/test_tiktoken_docker.py scans both).

How a run is scored

/eval/params.json (the held-out set on the platform; the public sample locally) holds the warmup documents, the timed ones and the reference's answer to each. The grader checks the set (the count expect says, documents of at most 200 KiB, answers of a digest and a count), sends the warmup documents untimed, then every timed document once, one a request, in an order drawn from the run's seed, and times each request. wall_ms is the total. Then it checks every answer: one that isn't the reference's (a token off changes the digest; a count off) is wrong, and any wrong or missing answer makes the run invalid. On the platform it then times the public sample the same way and reports it as public.

The baseline encodes the held-out set in about 1.8 s and the sample in about 140 ms (a shared lease's cores: 1806 and 1819 ms in two runs); in an eval VM on the dedicated timing core, about 2.0 to 2.2 s.

Noise and the MMI

A timing evaluation runs on the dedicated timing core (the r630's, PER-205). The MMI is twice the sd of the per-pair gain between two identical workers there, rounded up: 15% relative, and K = floor(0.9 / 0.15) = 6. It also meets PER-209's minimum (2 sigma_d).

Measured on 2026-10-31 with python -m arh_controller.characterize run (docs/noise.md): the baseline against itself on the held-out set (a copy of this directory with tiktoken-encode-heldout/params.json as its settings/heldout/, --setting heldout), --class cpu-s --nodes home-k8s-r630 --dedicated, 3 eval VMs of 10 A-B-B-A pairs each, one after another on the core (30 pairs, 60 runs; docs/noise/data/tiktoken-heldout-cpu-s-dedicated.json):

mean	2,181 ms (runs 1,990 to 2,795 ms)
sigma_d (relative)	7.29% (181 ms); per VM 7.6%, 3.8%, 9.0%
sd of the VMs' means	4.2%
MMI with 80% power for a 2-MMI gain (2/8 pairs, epsilon 0.05)	7.6%
the R630 meanwhile	load1 33 of its 24 threads, CPU pressure 10.4%, IO pressure 5.8% (full 3.9%)

The noise is heavy-tailed: most pairs differ by 0 to 5%, but single runs come out 15 to 28% slow (2,795, 2,627 and 2,477 ms against about 2,050). FizzBuzz (3.2%) and a Python CPU loop (2.2%) are far quieter on the same core: the core is pinned, but its memory bandwidth and last-level cache are the busy host's, and this workload (ten megabytes of text, the ranks' hash map) leans on both. A quieter host (PER-328) could justify a smaller MMI, as a new reward version.

What the MMI must resolve is on record: the faster core in test_tiktoken_cluster.py (GPT-2's pattern through the regex crate, its lookahead done by hand) encodes the held-out set in about 1,150 ms against the baseline's 1,700 (three alternating runs each on the lease, every answer the reference's): a gain of about 32%, 2 MMIs.

The grader image

Built in a build VM by python -m arh_controller.grader_image projects/tiktoken-encode at commit 067358e, from grader/ at git tree e28d8e68b8fdfe373c056f846b239a3740076475, dockerfile.grader blob e3f181ae763e17064123e8d20d1ce096daa5840d and sample/ at git tree ea6cbd7ce807cea1aac153a7500255cf1e1ccd6c: archive digest sha256:55038f2d377f411b50507a77ec5d824b8a7b2194199abd517863917462d39fe8, image (config) id sha256:33cdedacf625ab2b49ff78d7c785e0ba6773e9b0541a1dcd52e5c73bc1f8290b, 134,177,280 bytes. It is the seeded reward version's grader_image_digest (arh_core.seed.TIKTOKEN); a change to any of those files needs a new build and a new reward version.

Running it

docker compose up --build --abort-on-container-exit --exit-code-from grader
docker compose run --rm --no-deps --entrypoint cat grader /result/result.json
docker compose down --volumes

compose.yaml pins the worker to core 0 and the grader to core 1, as runner class cpu-s places them. The first build downloads Rust's and Python's images and the locked crates from crates.io. arh run (the platform's CLI, cli/README.md) runs the same three commands and prints the result; its score is the public sample's, not the held-out set's.

Licences

What	Source	Licence
src/lib.rs	openai/tiktoken 0.14.0, verbatim (LICENSE-tiktoken)	MIT
ranks/gpt2.tiktoken	GPT-2's vocabulary (openai-community/gpt2), as tiktoken writes it	MIT
sample/ and the held-out set	see "The data"	public domain, BSD-3-Clause, MIT, MIT OR Apache-2.0, and ours
fancy-regex, regex, regex-automata, regex-syntax, aho-corasick, memchr, rustc-hash, bstr and their dependencies (Cargo.lock)	crates.io, built into the worker's image, not vendored	MIT OR Apache-2.0 (rustc-hash: Apache-2.0 OR MIT; memchr, aho-corasick also Unlicense)
Rust 1.99.1 (rust:1.99.1-slim-bookworm), Python 3.13 (python:3.13-slim-bookworm)	Docker Hub, the images' bases	MIT OR Apache-2.0; PSF-2.0