Abstract
We evaluate semantics-preserving optimizations to byte-pair encoding (BPE) fitting and inference in a standard-library Python implementation. Incremental pair-frequency maintenance and rank-ordered local merging replace repeated full-sequence scans. On fixed local workloads, the optimized implementations reduced median fitting time by a factor of 111.79 and increased warm encoding throughput by a factor of 137.51 relative to our full-scan references.
Compatibility was assessed through canonical artifact equality and exact token-ID comparisons. The largest paired fitting case increased peak traced Python allocations by approximately 6.9×. The results establish an implementation-level time–memory tradeoff on the evaluated workloads, not an improvement in the tokenization objective or downstream model quality.
1. Tokenization specification and equivalence criteria
The tokenizer maps UTF-8 input to 256 initial byte IDs and assigns subsequent IDs to learned pairs. Text normalization is disabled. At each fitting step, the algorithm selects the most frequent within-document adjacent pair, resolves equal frequencies by lexicographic token-ID order, and applies nonoverlapping replacements from left to right.
Pair frequency counts overlapping occurrences even though replacement is nonoverlapping. For example, aaaaa contains four occurrences of aa, but one replacement pass performs two merges. Preserving this distinction is necessary for both pair selection and the resulting merge sequence.
For fitting, equivalence requires identical canonical serialized artifacts under the same corpus and configuration. For encoding, equivalence requires an identical ordered token-ID sequence for each input and fixed merge table. Decode round-trip equality alone is insufficient: different token sequences may reconstruct the same text while presenting different inputs to a model. Merge rank, rather than longest-match selection, determines the reference encoding.
2. Incremental fitting and rank-ordered encoding
The reference fitter recounts corpus-wide adjacent pairs after every merge. The optimized fitter instead maintains an occurrence set for each pair, linked live positions, and a heap prioritized by negative frequency and numeric pair order. Each replacement removes obsolete local edges and inserts the newly formed neighboring edges.
Selected occurrences are processed in original positional order; invalidated overlaps are skipped. Document sentinels prohibit cross-document merges. Heap entries are validated against current counts before selection, and the heap is rebuilt when obsolete priorities exceed a fixed threshold. These operations preserve the reference selection and replacement rules without rescanning unaffected token positions.
The optimized encoder maintains candidate edges in a heap ordered by merge rank and original left position. Before each replacement, it verifies that the endpoints remain live, their adjacency is unchanged, and the pair still has the queued rank. Only the two neighboring edges require reconsideration after a merge.
The merge table permits references only to earlier token IDs. Consequently, an edge involving a newly created token cannot have a rank earlier than the merge that created it. Together with leftmost tie resolution, this property supports equivalence to the reference’s rank-by-rank, left-to-right replay. The implementation retains the original byte representation, learning objective, and artifact schema.
3. Experimental design
Measurements used Python 3.12.10 on Windows 11. Each case comprised three paired, uninstrumented passes in alternating reference/optimized order. Speedup is the ratio of the corresponding median measurements. Reference modules were archived without modification and identified by cryptographic hashes.
Fitting timings include UTF-8 preparation, index construction, merge learning, and final tokenizer construction; file I/O, serialization, and validation are excluded. No full-fit warmup was performed. Encoding timings follow one warm call per document and backend, and exclude artifact loading, decoding, and parity checks. The implementation uses no text-result cache. The selected encoding evaluation comprises two documents totaling 49,767 UTF-8 bytes.
4. Runtime and memory results
| Operation and sample | Reference | Optimized | Ratio |
|---|---|---|---|
| Fit: 82,257 training bytes, 4,096 vocabulary entries | 21.971 s | 0.1965 s | 111.79× |
| Encode: 49,767 held-out bytes, 2,048-entry artifact | 9.22 KiB/s | 1,267.54 KiB/s | 137.51× |
The fitting comparison uses 82,257 training bytes and a 4,096-entry vocabulary. The encoding comparison uses a separate 2,048-entry artifact and held-out text. The two ratios therefore describe distinct operations and workloads; they must not be multiplied or interpreted as an end-to-end pipeline speedup.
For the largest paired fitting case, peak traced Python allocations increased from 2.28 MiB to 15.75 MiB, approximately 6.9×. These measurements came from separate tracemalloc runs and exclude preloaded text, native allocations, and untraced process memory. They quantify traced allocation overhead, not total resident memory.
A separate 32K vocabulary study used approximately 1.95 MB of training text. Its selected fit recorded a median of 7.37 seconds and a maximum Windows process peak working set of 504.20 MiB. Because that study changed both corpus and vocabulary, and used a different memory measure, it is not a continuation of the paired speedup comparison or a directly comparable allocation ratio.
5. Differential validation and replay
Across seven fixed fitting recipes, every timed, memory-profiled, and replay fit reproduced its corresponding original artifact bytes. The encoder comparison covered four artifacts across nine documents, with identical token-ID sequences and exact round trips for all 36 document–artifact pairs.
Additional regression tests covered overlapping occurrences, stale heap entries, neighbor invalidation, frequency ties, Unicode and layout preservation, empty inputs, and deterministic serialization. These checks address failure modes that decoded-text equivalence alone would not detect.
Source-and-input snapshots were replayed in fresh isolated Python processes on the same machine. This establishes repeatability within the recorded environment, not independent-machine or cross-platform reproduction. All numerical results in this note derive from the retained experiment records; the editorial revision introduced no new benchmark run.
6. Limitations and interpretation
The evaluation uses small convenience samples and three timing repetitions per case. It does not provide confidence intervals, cold-start performance, sustained service throughput, or a comparison against established optimized libraries. The magnitude of the reported ratios depends on the full-scan baseline and should not be generalized to other implementations.
The optimized paths preserve the fitted representation on the evaluated cases. Accordingly, the measured benefit is reduced computational cost at increased working-memory overhead. No improvement in token counts, compression, or downstream model accuracy follows from this equivalence-preserving change.
A broader evaluation would require larger heterogeneous corpora, additional hardware and operating systems, and external baselines with aligned normalization, boundary, and merge-order semantics. Within the present scope, exact artifact and token-ID checks provide the basis for separating implementation optimization from a change to the experimental representation.
7. Data availability and references
The public measurement summary (JSON) contains recorded paired timings, allocation measurements, execution order, and scope annotations. Corpus text, implementation snapshots, and full private experiment records are not included. This summary is not a standalone reproduction package.
Relevant background includes Neural Machine Translation of Rare Words with Subword Units and the educational byte-level implementation minbpe. These references provide context; neither was evaluated as a performance baseline in this study.