tiktoken-encode: GPT-2 BPE encoding in fewer instructions

A count project (PER-306, counted since PER-378): agents make tiktoken's Rust core (src/, upstream's src/lib.rs to start with) encode text with GPT-2's byte-pair encoding in fewer instructions, and the grader runs the encoder itself on held-out documents it never shows, under an emulator that counts every instruction, checking every token id against the reference's (instruction_ratio, minimized). Every improvement here is a patch upstream could take.

File	What it is
autoresearch.toml	the metric (instruction_ratio, a count, minimized, MMI 1% relative), runner class cpu-s, editable src/**, K = 30; upstream openai/tiktoken, public
PROGRAM.md	instructions for the agents: the encoder, the budget, the data, what counts as cheating
CONTRACT.md	the worker HTTP contract (the template's, plus this project's item)
src/lib.rs	the code being improved: tiktoken 0.14.0's Rust core, upstream's file with one change ("The upstream")
Cargo.toml, Cargo.lock	the workspace: the core's crates (fancy-regex, regex, rustc-hash, bstr) locked, the release profile, unsafe_code = "forbid"
harness/arh-bpe/	the frozen program the grader runs: GPT-2's ranks built in, CoreBPE::new once, then encode_ordinary on each document (PROGRAM.md, "How your encoder runs")
harness/worker.py	the frozen HTTP server (Python's standard library): hands the program to the grader, runs none of it
ranks/gpt2.tiktoken	GPT-2's BPE ranks, tiktoken's r50k_base
dockerfile.worker, compose.yaml	Rust 1.99.1 on Alpine builds the program for musl, static; Python 3.13 serves it; worker on core 0, grader on core 1
dockerfile.grader, grader/	the grader (grade.py, measure.py), its sandbox and the emulator with its counting plugin (sandbox.py, native/: the instruction-count kit, sdk/insncap verbatim), and the grader SDK (grader/arh_grader, sdk/grader release 6 verbatim)
sample/items.jsonl	the public sample: 11 documents of three books, with the reference's answers and the incumbent's counts
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 with one change: hash_current_thread, which picks a thread's regex out of the core's 128 copies, hashes the thread's id with ThreadId's own Hash where upstream transmutes it to read its private u64, because src/ forbids unsafe code (PER-378). 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, the lints). 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/items.jsonl, 100 documents, 9.8 MB, 4.68 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). The sets were the timing project's, two of their documents warmup: here every document counts.

How a run is scored

/eval/items.jsonl (the held-out set on the platform; the public sample locally) lists the documents in the order they are sent, each with the reference's answer and the incumbent's count: {"doc", "sha256", "tokens", "instructions"}. The grader checks the set (the count expect says, documents of at most 200 KiB, answers of a digest and a count), gets the program from the worker and runs it once, in its sandbox, under QEMU 11.1.2's user-mode emulator with the instruction-count kit's plugin, on framed items each sent once the program has answered the one before: go, every document, the end. The plugin reports the count at each item's first read: the encoder's making (CoreBPE::new, I) runs from go to the first document, document i's encoding (P_i) from its first read to the next item's; the program's parsing of its ranks, before its first read, isn't counted. Then every answer is checked against the reference's: one that isn't (a token off changes the digest; a count off) is wrong, and any wrong or missing answer makes the run invalid.

Document i scores (n_items * P_i + I) / r_i, its count with an even share of the making over the incumbent's (r_i, items.jsonl's instructions), and instruction_ratio is their mean. A document over 4 r_i is over_item_budget; the plugin stops a run past 4 times the incumbent's whole count plus 10 billion instructions (the ranks' parsing, about 0.1 billion, and room) as over_budget. PROGRAM.md lists the other failure kinds.

The refs

The instructions of both sets are the live incumbent's, attempt 34 (the project's repository on the platform, commit fca3a561929f6b8cb90616c5cacb9335b5bc4b2f, with this directory's change to hash_current_thread), measured with grader/measure.py in the grader's image. Its source is kept in projects/tiktoken-encode-intake/ with how to measure them again; two measurements gave the same bytes. This directory's src/ is still upstream's core, which the refs don't count: against them it is over the per-document budget (about 4 times attempt 34's count on average, 9 on the worst document).

On the held-out set	I (making)	sum P (encoding)	I + sum P
upstream's core	0.09 G	8.61 G	8.69 G
attempt 34 (the refs)	0.76 G	1.68 G	2.44 G

Attempt 34 makes its encoder at about 9 times upstream's cost (its own tables of the ranks) and encodes at a fifth of it. On the sample, I is shared by 11 documents rather than 100, so it is 87% of the incumbent's count there and 31% on the held-out set.

The metric and the MMI

The count is exact: the same program on the same documents counts the same on every run and every machine, so the metric is deterministic and its noise floor is the platform's minimum, 0.1%. The MMI is 1%, a change that saves one instruction in a hundred, and K = 30 (an encoder 30% cheaper at once is held for the author's review).

Replayed under the counter on the held-out set, each accepted attempt scored against its parent's counts ((n_items * P_i + I) / r_i, the parent's as r_i):

	instruction_ratio	gain	per document
attempt 32 (the regex crate, GPT-2's lookahead by hand) against upstream	0.627	37%	0.37 to 1.97
attempt 34 (merges over token ids, a word-keyed heap) against attempt 32	0.474	53%	0.24 to 0.83

Both resolve at 37 and 52 MMIs, and both would have been held at K = 30. Timed, attempt 32 had measured 32% (about 2 MMIs at the timing project's 15%).

Budget and time

The emulator ran at about 350 million instructions a second on a shared 48-core build host (load 25 to 35): upstream's core on the held-out set (8.7 billion instructions) in 27 s, attempt 34 (2.4 billion) in 11 s, the sample in 6 s each, start to finish. A run at its cap is 4 times the incumbent's 2.4 billion plus 10 billion, about 20 billion instructions: a minute of emulation on that host, a few on a far busier one. run_timeout_s is 7200 s (the score doesn't depend on speed, so the deadline leaves room for a contended pool).

Measuring

The grader's image measures any encoder the way a run does, without the budget (grader/measure.py): its count on each document, every answer checked.

docker build -f dockerfile.worker -t tiktoken-encode-worker .
docker build -f dockerfile.grader -t tiktoken-encode-grader .
docker create --name w tiktoken-encode-worker && docker cp w:/app/bin/arh-bpe . && docker rm w
docker run --rm -v "$PWD/arh-bpe:/w/arh-bpe:ro" -v "$PWD/sample:/w/set:ro" tiktoken-encode-grader \
  python measure.py /w/arh-bpe /w/set > counts.jsonl

It prints the set again with each document's instructions your encoder's n_items * P + I; set them against sample/items.jsonl's: their ratio is the document's score, and 4 is its cap. The counts are exact, so this is the run's own answer.

The grader image

Built from grader/ and dockerfile.grader. It builds QEMU 11.1.2's user-mode emulator from the release tarball, pinned by its SHA-256 and fetched from download.qemu.org ([build] egress), with the kit's patch (grader/native/qemu.patch), and the plugin (grader/native/insncap.c) against it; the rest is Python's standard library. The counted reward version's image is built by the conformance report of its patch (the console's patch flow), which records its digest. The timing version's was sha256:55038f2d377f411b50507a77ec5d824b8a7b2194199abd517863917462d39fe8.

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, Debian's and Python's images, the locked crates from crates.io and QEMU's source from download.qemu.org. 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, one function changed ("The upstream"; LICENSE-tiktoken)	MIT
grader/native/qemu.patch, the emulator built from it	QEMU 11.1.2 (download.qemu.org), patched	GPL-2.0-only
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-alpine3.23), Debian 12 (debian:bookworm-slim), Python 3.13 (python:3.13-slim-bookworm)	Docker Hub, the images' bases	MIT OR Apache-2.0; Debian's; PSF-2.0