LLM Tokenization

What BPE training and encoding actually guarantee: frequency vs rank, merge DAGs, self-overlap, and the freedoms every later optimization exploits.

How tokenshop's linked-list encoder and reverse-index trainer work — and why the trainer's linear argmax is the wrong structure at real vocab sizes.

Pretokenization, special tokens, and the persistence gap — how the GPT-4 regex pattern reshapes BPE, and why the bottleneck moves after a tiny pretoken cache.

Why Zipf's law makes most tokenizer work disappear: cache repeated pretokens and run BPE only for the rare misses.

Why a linear O(n²) scan beats a heap for short pretokens: operating points, dual thresholds, Python vs Rust, and when NEON helps.

Why the pretoken boundary scanner becomes the bottleneck after caching, and how SWAR turns a fixed regex into an eight-byte-at-a-time integer scan.

Why two independent cursors can hide dependency latency in a pretokenizer, why the historical 25% win was narrower than full encoding, and why later production dropped it.

Why a warm pretoken-cache hit is a random memory-access problem, and how cache-line-aware entries, prefetching, and huge pages reduce its cost.

Why the last 100× is core count times a fast single core, and how pretoken-safe chunks plus Amdahl bookkeeping make near-linear scaling real.

How to audit gigatoken's ~1000× claim: what the ratio is made of, when it shrinks, and which row is the honest one.