Skip to main content
Vansh Verma
← Lab

bpelatency

confirmedC++ · llama.cppSystems & data structuresJuly 6, 2026

the question

Naive BPE tokenizer merging is O(L^2) -- where does that quadratic cost actually bite?

what came out

It scales exactly as predicted: naive ~L^2.0, heap ~L^1.1, and the naive/heap ratio grows unbounded -- 46-58x by L=1024 (a single ~1 KB piece). But naive still wins the common case (short real pieces), with a crossover in [8,64]. Validated against llama.cpp's tokenizer as a differential oracle; all predictions held.

method & receipts

  • Result: confirmed
  • Pre-registered — the prediction was written down and committed before the run.
  • Reproducible — one script re-runs the whole thing from scratch.
  • Independently reviewed — an adversarial review pass, kept in the repo.
  • Machine-readable claims — every reported number, in a checkable file.
  • Tested — a correctness/benchmark suite ships alongside the code.

→ read the code and re-run it

github.com/v-code01/bpelatency