{"id":987,"date":"2026-05-28T17:08:20","date_gmt":"2026-05-28T09:08:20","guid":{"rendered":"https:\/\/connectword.dpdns.org\/?p=987"},"modified":"2026-05-28T17:08:20","modified_gmt":"2026-05-28T09:08:20","slug":"perplexity-ai-open-sources-unigram-tokenizer-that-achieves-5x-lower-p50-latency-than-hugging-face-tokenizers-crate","status":"publish","type":"post","link":"https:\/\/connectword.dpdns.org\/?p=987","title":{"rendered":"Perplexity AI Open-Sources Unigram Tokenizer That Achieves 5x Lower p50 Latency Than Hugging Face tokenizers Crate"},"content":{"rendered":"

Perplexity AI\u2019s research team reimplemented their Unigram tokenizer from scratch in Rust and open-sourced the code in pplx-garden<\/a>, their inference technology repository.<\/p>\n

At production input lengths, the new encoder cuts p50 latency by roughly 5x versus the Hugging Face tokenizers<\/code> crate, ~2x versus SentencePiece (C++), and ~1.5x versus IREE\u2019s tokenizer (C), with zero steady-state heap allocations. In production, it reduced CPU utilization in Perplexity\u2019s inference stack by 5-6x and shaved double-digit milliseconds off reranker latency.<\/p>\n

Why Tokenization Became a Bottleneck<\/strong><\/h2>\n

LLM inference cost is typically framed around GPU work: KV caches, attention kernels, expert routing. But smaller models, such as embedding models, classifiers, and rerankers, tell a different story. These models are two to three orders of magnitude smaller than frontier transformers.<\/p>\n

A reranker scoring hundreds of candidate documents per request is a clear example. With a small model, GPU compute often finishes in single-digit milliseconds. Every input still passes through CPU-side tokenization first. When batch sizes are large, tokenization becomes a meaningful fraction of total request latency.<\/p>\n

Perplexity\u2019s work targets XLM-RoBERTa<\/strong>, a model with a 250K-token Unigram vocabulary trained with SentencePiece. Fine-tuned RoBERTa-family encoders are a common production choice for ranking, retrieval, and similarity tasks.<\/p>\n

What is Unigram Tokenization?<\/strong><\/h2>\n

Unigram tokenization was introduced by Kudo in 2018 and is implemented in SentencePiece. It frames segmentation as a most-probable-path problem<\/strong>. Each vocabulary token has a learned log-probability. The tokenizer picks the segmentation whose token scores sum to the highest value.<\/p>\n

The algorithm used to find that best path is the Viterbi algorithm<\/strong>, a dynamic programming technique from 1967. Byte positions form graph layers and vocabulary tokens are edges spanning a contiguous byte range. The DP recurrence iterates over byte positions and updates the best-scoring path at each position.<\/p>\n

The outer loop runs in linear time relative to input length. The inner loop walks a vocabulary trie<\/strong> (a prefix tree structure) at each byte position. On a 16K-token input, this inner walk executes hundreds of thousands of trie transitions. It is the hot path.<\/p>\n

What was Slow in the Hugging Face Implementation<\/strong><\/h2>\n

The Hugging Face tokenizers<\/code> crate is the default Rust tokenizer most teams reach for. Perplexity used it as the benchmark reference. At 514 tokens (512 + BOS\/EOS injection), the reference implementation had three costly patterns:<\/strong><\/p>\n

\n\n\n\n\n\n\n\n
Bottleneck<\/th>\nMechanism<\/th>\nMeasured impact<\/th>\n<\/tr>\n<\/thead>\n
Allocation per match<\/td>\nString::from_utf8<\/code> + AHashMap<\/code> lookup per trie match<\/td>\n7,295 allocations at 514 tokens; 299,171 at 16K<\/td>\n<\/tr>\n
Pointer chase per byte<\/td>\nAHashMap<\/code> at every trie node; 4 dependent loads per byte step<\/td>\nDependent-load latency dominates the hot path<\/td>\n<\/tr>\n
L2 thrashing on long inputs<\/td>\nDP table and output buffers freshly allocated each call<\/td>\nL2 miss rate climbs from 8% at 128 tokens to 50% at 16K<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n

Per-token allocation is constant: roughly 2 KB and ~18 allocations per token, regardless of input size. The latency problem becomes severe at longer inputs when cumulative allocations overflow the per-core L2 cache.<\/p>\n

Establishing a Baseline Before Changing the Trie<\/strong><\/h2>\n

Before switching the trie structure, Perplexity first isolated how much cost came from unnecessary work alone. They made a zero-allocation port of the reference: same HashMap trie, but with a caller-owned scratch struct reused across calls and token IDs stored directly in trie nodes (removing the per-match string allocation and secondary hash-map lookup).<\/p>\n

This baseline already cut p50 latency to 155 \u00b5s at 514 tokens, down from 326 \u00b5s in the reference. Instructions retired dropped 2.4x. The remaining cost was the HashMap pointer chase itself, which the next step addressed.<\/p>\n

The Three Optimizations<\/strong><\/h2>\n

Optimization 1: Double-Array Trie<\/strong><\/h3>\n

The Hugging Face trie stores children in a HashMap<\/code> at every node. Each byte step requires a hash computation, two pointer dereferences, and a heap access. Perplexity replaced this with a double-array trie<\/strong>, the same structure used by SentencePiece and IREE, originally introduced by Aoe in 1989.<\/p>\n

A double-array trie encodes the entire trie in two flat integer arrays, base<\/code> and check<\/code>. A child lookup is: next = base[node] + byte<\/code>, then verify check[next] == node<\/code>. That is two array reads, one integer add, and one comparison, with no hashing and no pointer chasing. For XLM-RoBERTa\u2019s 250K vocab, the whole trie fits in ~9 MB of contiguous memory. The hot working set per encode is on the order of 100 KB, which fits in L2 cache.<\/p>\n

Unlike SentencePiece and IREE, which are general-purpose libraries with lattice bookkeeping and multi-stage pipelines, Perplexity inlined the trie directly in the Viterbi loop and dropped that overhead entirely.<\/p>\n

Result at 514 tokens:<\/strong> p50 dropped from 155 \u00b5s (zero-allocation baseline) to 68 \u00b5s. Wall-clock fell 4.8x from the original reference.<\/p>\n

Optimization 2: Bitmap and Inline Packing<\/strong><\/h3>\n

The double-array trie still requires two dependent array loads per byte step: first the parent\u2019s base<\/code> offset, then the check<\/code> array to confirm the transition is valid. Perplexity replaced the check array with a per-node bitmap<\/strong> (four 64-bit words, 32 bytes) that records which of the 256 possible bytes have valid child transitions.<\/p>\n

A bitmap lookup compiles to a single bit test against one 64-bit word. The check array is used only during trie construction and dropped from the runtime layout entirely.<\/p>\n

They also packed all four per-node fields (bitmap, base, token ID, and score) into a single 64-byte cache line<\/strong>, matching CPU cache line width exactly. One trie step now loads a single cache line covering the bitmap for the next-byte check, the base offset for the child slot, and the token ID and score at terminal nodes.<\/p>\n

Trade-off: trie size grows from ~9 MB to ~50 MB (780K nodes x 64 bytes). The hot working set per encode remains ~100 KB.<\/p>\n

Result at 514 tokens:<\/strong> Additional 4.5% wall-clock reduction. L2 accesses dropped from 4.6K to 1.8K per encode.<\/p>\n

Optimization 3: Huge Pages for the Trie<\/strong><\/h3>\n

At 50 MB, the trie spans roughly 12,000 virtual pages on a default Linux system using 4 KB pages. The first-level data TLB on Intel Sapphire Rapids holds 96 entries. Each Viterbi step touches a different trie node, so TLB misses accumulate. Over a 512-token encode, Perplexity estimated roughly 9,000 cycles spent in page-table walks, about 3% of per-encode budget.<\/p>\n

Perplexity backed the trie with 2 MB huge pages<\/strong> via mmap<\/code> with the MAP_HUGETLB<\/code> flag. The same 50 MB now spans 25 pages, well within the TLB. This requires vm.nr_hugepages<\/code> configured at boot. In production, 10,561 huge pages are reserved; the trie uses 24.<\/p>\n

Result:<\/strong> 3-12% wall-clock reduction depending on input length. The largest gain is at 4,098 tokens (-12.0%), where page-table traffic was actively competing with trie data for L2 bandwidth. Beyond 4K tokens the gain shrinks because L3 misses dominate.<\/p>\n

Final Benchmark Results<\/strong><\/h2>\n

All measurements are single-threaded, pinned to one core on an Intel Xeon Platinum 8488C, with 10,000 iterations after 1,000 warmup rounds. At 514 tokens:<\/strong><\/p>\n

\n\n\n\n\n\n\n\n\n
Engine<\/th>\np50 Latency<\/th>\nInstructions<\/th>\nAllocations<\/th>\n<\/tr>\n<\/thead>\n
Hugging Face (tokenizers<\/code> crate)<\/td>\n349 \u00b5s<\/td>\n3.60M<\/td>\n7,295<\/td>\n<\/tr>\n
SentencePiece (C++)<\/td>\n128 \u00b5s<\/td>\n1.83M<\/td>\n1,559<\/td>\n<\/tr>\n
IREE tokenizer (C)<\/td>\n112 \u00b5s<\/td>\n2.28M<\/td>\n1<\/td>\n<\/tr>\n
Perplexity (final, all 3 optimizations)<\/td>\n~63 \u00b5s<\/td>\n1.04M<\/td>\n0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n

Across the full optimization sequence, instructions per encode fell from 3.66M to 1.04M, a 3.5x reduction. Wall-clock matches that ratio at short inputs and widens at long inputs where the reference\u2019s per-token allocations overflow L2 and L3.<\/p>\n

One additional finding: off-the-shelf Rust wrapper crates around SentencePiece and IREE add 1.6-1.9x latency overhead compared to the native C\/C++ binaries. The sentencepiece crate allocates a fresh list of token pieces on each call. The overhead is measurable but amortizes at long inputs.<\/p>\n

The final Perplexity encoder produces token-exact output against the reference. In production, it uses rayon<\/code> to parallelize across cores.<\/p>\n

Marktechpost\u2019s Visual Explainer<\/strong><\/h2>\n
\n
\n

<\/p>\n

\n
Open Source Release<\/div>\n

Perplexity AI Rewrites Its Unigram Tokenizer, Cuts CPU Utilization 5-6x<\/h2>\n

Perplexity reimplemented their Unigram tokenizer from scratch in Rust and open-sourced it in pplx-garden<\/code>. Three targeted optimizations removed wasted work from the hot path.<\/p>\n

\n
5x<\/span>Lower p50 vs HuggingFace tokenizers crate<\/span><\/div>\n
5-6x<\/span>CPU utilization reduction in production<\/span><\/div>\n
0<\/span>Heap allocations on the hot path<\/span><\/div>\n<\/div>\n

Source: research.perplexity.ai<\/p>\n<\/div>\n

<\/p>\n

\n
The Problem<\/div>\n

Why CPU Tokenization Became a Bottleneck<\/h2>\n

LLM inference cost is usually framed around GPU work: KV caches, attention kernels, expert routing. But small models tell a different story.<\/p>\n

\n
\n
1<\/div>\n
\n
Rerankers and embedders are small<\/div>\n
Two to three orders of magnitude smaller than frontier transformers. GPU compute finishes in single-digit milliseconds.<\/div>\n<\/div><\/div>\n
\n
2<\/div>\n
\n
Tokenization runs on CPU before each call<\/div>\n
Every input passes through CPU-side tokenization first, turning text into vocabulary IDs.<\/div>\n<\/div><\/div>\n
\n
3<\/div>\n
\n
Batch size amplifies the cost<\/div>\n
A reranker scoring hundreds of documents per request means tokenization runs hundreds of times per query.<\/div>\n<\/div><\/div>\n<\/div>\n<\/div>\n

<\/p>\n

\n
Background<\/div>\n

What Is Unigram Tokenization?<\/h2>\n

Introduced by Kudo (2018), implemented in SentencePiece. Perplexity targets XLM-RoBERTa<\/strong> with a 250K-token Unigram vocabulary.<\/p>\n

\n
\n
Most-probable-path problem<\/div>\n
Each vocabulary token carries a learned log-probability. The tokenizer picks the segmentation whose token scores sum highest.<\/div>\n<\/div>\n
\n
Viterbi algorithm (1967)<\/div>\n
A dynamic programming method that finds the best path. Byte positions are graph layers; vocabulary tokens are edges.<\/div>\n<\/div>\n<\/div>\n
\n

The hot path is the inner trie walk at each byte position. On a 16K-token input, this executes hundreds of thousands of trie transitions and retires tens of millions of instructions per encode.<\/p>\n<\/div>\n<\/div>\n

<\/p>\n

\n
Root Cause<\/div>\n

Three Bottlenecks in the Hugging Face Reference<\/h2>\n

Measured at 514 tokens (512 + BOS\/EOS) on Intel Xeon Platinum 8488C:<\/p>\n\n\n\n\n\n\n\n
Bottleneck<\/th>\nMechanism<\/th>\nImpact<\/th>\n<\/tr>\n<\/thead>\n
Allocation per match<\/td>\nString::from_utf8<\/code> + AHashMap<\/code> lookup per trie match<\/td>\n7,295 allocs at 514 tokens; 299,171 at 16K<\/td>\n<\/tr>\n
Pointer chase per byte<\/td>\nAHashMap<\/code> at every trie node; 4 dependent loads per step<\/td>\nDependent-load latency dominates<\/td>\n<\/tr>\n
L2 thrashing<\/td>\nDP table and output buffers freshly allocated each call<\/td>\nL2 miss rate: 8% at 128 tokens, 50% at 16K<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\n

Per-token allocation is constant: ~2 KB and ~18 allocations per token regardless of input size.<\/p>\n<\/div>\n<\/div>\n

<\/p>\n

\n
Step 0: Baseline<\/div>\n

Zero-Allocation Port Before Changing the Trie<\/h2>\n

Before touching the trie structure, Perplexity isolated how much cost came from unnecessary allocations alone. They kept the same HashMap trie but made two changes:<\/p>\n