Use stack merging for short encoded BPE pretokens

perfloop/fastokens · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_xyayc7b1c6

Verdict

VERIFIED · settled 2026-09-09 · pull request opened as crusoecloud/fastokens#70

Hypothesis

The accepted path structurally spends its cache-miss merge phase seeding and draining a priority queue, whereas the target already uses a bounded linear greedy merger for raw fused input. The paper and tiktoken establish that asymptotic and short-input choices can differ. This is a falsifiable crossover claim, not a claim that the generic path or its end-to-end latency is currently dominant.

Retain the heap as an oracle and differentially compare a candidate encoded-small merger against it for every emitted-symbol count through 32 and the 32/33 boundary, equal-rank overlaps, ByteLevel-form characters, combining marks, byte-fallback expansion, missing fallback-token errors, and pre-populated output buffers. Then benchmark only forced generic cache misses bucketed by emitted-symbol count; reject if any IDs/errors differ or the relevant short buckets do not reduce CPU/cycles.

Architecture-independent portable scalar change only. Restrict it to the generic `split_only`-absent encoded cache-miss route and retain the current heap for larger inputs. Preserve greedy rank/leftmost tie order, exact token IDs, Unicode and byte-fallback behavior, error atomicity, normalization/pretokenization, special-token trust boundaries, decoding, and public APIs; do not alter the raw fused route or cache policy.

Change to test: Add a bounded stack-resident encoded-input BPE merge branch in `merge_all_encoded_into` when the actually emitted initial-symbol count is at most `SMALL_MERGE_MAX`, falling back to the existing priority-queue merger above that bound.

Where it lives

perfloop/fastokens · src/lib.rs

Evidence

forced generic encoded cache miss, merge-dense pretoken with 16 emitted symbols · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 1356 1004 −26.1% (−353.8) −456.9 to −303.9 < −67.78 PASSED
cpu-ns/op 1325 980 −26.4% (−350) −440 to −300 < −66.25 PASSED

forced generic encoded cache miss, merge-dense pretoken with 32 emitted symbols · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2127 1528 −26.3% (−559.2) −665 to −516.2 < −106.4 PASSED
cpu-ns/op 2085 1495 −25.9% (−540) −650 to −510 < −104.3 PASSED

heap guard: forced generic encoded cache miss, merge-dense pretoken with 33 emitted symbols · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2096 2113 −0.6% (−12.72) −76.72 to +60.56 ≤ 104.8 PASSED

Checks: 10 of 10 passed. Verification: no defect found.

Timeline