Perplexity AI Open-Sources Unigram Tokenizer That Achieves 5x Lower p50 Latency Than Hugging Face tokenizers Crate

Perplexity AI’s analysis crew reimplemented their Unigram tokenizer from scratch in Rust and open-sourced the code in pplx-garden, their inference expertise repository.

At manufacturing enter lengths, the brand new encoder cuts p50 latency by roughly 5x versus the Hugging Face tokenizers crate, ~2x versus SentencePiece (C++), and ~1.5x versus IREE’s tokenizer (C), with zero steady-state heap allocations. In manufacturing, it decreased CPU utilization in Perplexity’s inference stack by 5-6x and shaved double-digit milliseconds off reranker latency.

Why Tokenization Became a Bottleneck

LLM inference value is usually framed round GPU work: KV caches, consideration kernels, professional routing. But smaller fashions, reminiscent of embedding fashions, classifiers, and rerankers, inform a distinct story. These fashions are two to 3 orders of magnitude smaller than frontier transformers.

A reranker scoring lots of of candidate paperwork per request is a transparent instance. With a small mannequin, GPU compute usually finishes in single-digit milliseconds. Every enter nonetheless passes by means of CPU-side tokenization first. When batch sizes are massive, tokenization turns into a significant fraction of complete request latency.

Perplexity’s work targets XLM-RoBERTa, a mannequin with a 250K-token Unigram vocabulary skilled with SentencePiece. Fine-tuned RoBERTa-family encoders are a standard manufacturing selection for rating, retrieval, and similarity duties.

What is Unigram Tokenization?

Unigram tokenization was launched by Kudo in 2018 and is carried out in SentencePiece. It frames segmentation as a most-probable-path drawback. Each vocabulary token has a discovered log-probability. The tokenizer picks the segmentation whose token scores sum to the best worth.

The algorithm used to seek out that finest path is the Viterbi algorithm, a dynamic programming method from 1967. Byte positions kind graph layers and vocabulary tokens are edges spanning a contiguous byte vary. The DP recurrence iterates over byte positions and updates the best-scoring path at every place.

The outer loop runs in linear time relative to enter size. The interior loop walks a vocabulary trie (a prefix tree construction) at every byte place. On a 16K-token enter, this interior stroll executes lots of of hundreds of trie transitions. It is the new path.

What was Slow within the Hugging Face Implementation

The Hugging Face tokenizers crate is the default Rust tokenizer most groups attain for. Perplexity used it because the benchmark reference. At 514 tokens (512 + BOS/EOS injection), the reference implementation had three pricey patterns:

Per-token allocation is fixed: roughly 2 KB and ~18 allocations per token, no matter enter dimension. The latency drawback turns into extreme at longer inputs when cumulative allocations overflow the per-core L2 cache.

Establishing a Baseline Before Changing the Trie

Before switching the trie construction, Perplexity first remoted how a lot value got here from pointless work alone. They made a zero-allocation port of the reference: similar HashMap trie, however with a caller-owned scratch struct reused throughout calls and token IDs saved instantly in trie nodes (eradicating the per-match string allocation and secondary hash-map lookup).

This baseline already lower p50 latency to 155 µs at 514 tokens, down from 326 µs within the reference. Instructions retired dropped 2.4x. The remaining value was the HashMap pointer chase itself, which the following step addressed.

The Three Optimizations

Optimization 1: Double-Array Trie

The Hugging Face trie shops kids in a HashMap at each node. Each byte step requires a hash computation, two pointer dereferences, and a heap entry. Perplexity changed this with a double-array trie, the identical construction utilized by SentencePiece and IREE, initially launched by Aoe in 1989.

A double-array trie encodes the whole trie in two flat integer arrays, base and examine. A toddler lookup is: subsequent = base[node] + byte, then confirm examine[next] == node. That is 2 array reads, one integer add, and one comparability, with no hashing and no pointer chasing. For XLM-RoBERTa’s 250K vocab, the entire trie suits in ~9 MB of contiguous reminiscence. The scorching working set per encode is on the order of 100 KB, which inserts in L2 cache.

Unlike SentencePiece and IREE, that are general-purpose libraries with lattice bookkeeping and multi-stage pipelines, Perplexity inlined the trie instantly within the Viterbi loop and dropped that overhead fully.

Result at 514 tokens: p50 dropped from 155 µs (zero-allocation baseline) to 68 µs. Wall-clock fell 4.8x from the unique reference.

Optimization 2: Bitmap and Inline Packing

The double-array trie nonetheless requires two dependent array hundreds per byte step: first the father or mother’s base offset, then the examine array to substantiate the transition is legitimate. Perplexity changed the examine array with a per-node bitmap (4 64-bit phrases, 32 bytes) that information which of the 256 attainable bytes have legitimate youngster transitions.

A bitmap lookup compiles to a single bit take a look at towards one 64-bit phrase. The examine array is used solely throughout trie development and dropped from the runtime structure fully.

They additionally packed all 4 per-node fields (bitmap, base, token ID, and rating) right into a single 64-byte cache line, matching CPU cache line width precisely. One trie step now hundreds a single cache line protecting the bitmap for the next-byte examine, the bottom offset for the kid slot, and the token ID and rating at terminal nodes.

Trade-off: trie dimension grows from ~9 MB to ~50 MB (780K nodes x 64 bytes). The scorching working set per encode stays ~100 KB.

Result at 514 tokens: Additional 4.5% wall-clock discount. L2 accesses dropped from 4.6K to 1.8K per encode.

Optimization 3: Huge Pages for the Trie

At 50 MB, the trie spans roughly 12,000 digital pages on a default Linux system utilizing 4 KB pages. The first-level information TLB on Intel Sapphire Rapids holds 96 entries. Each Viterbi step touches a distinct 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 price range.

Perplexity backed the trie with 2 MB big pages by way of mmap with the MAP_HUGETLB flag. The similar 50 MB now spans 25 pages, properly inside the TLB. This requires vm.nr_hugepages configured at boot. In manufacturing, 10,561 big pages are reserved; the trie makes use of 24.

Result: 3-12% wall-clock discount relying on enter size. The largest achieve is at 4,098 tokens (-12.0%), the place page-table visitors was actively competing with trie information for L2 bandwidth. Beyond 4K tokens the achieve shrinks as a result of L3 misses dominate.

Final Benchmark Results

All measurements are single-threaded, pinned to at least one core on an Intel Xeon Platinum 8488C, with 10,000 iterations after 1,000 warmup rounds. At 514 tokens:

Across the total optimization sequence, directions per encode fell from 3.66M to 1.04M, a 3.5x discount. Wall-clock matches that ratio at brief inputs and widens at lengthy inputs the place the reference’s per-token allocations overflow L2 and L3.

One extra discovering: off-the-shelf Rust wrapper crates round SentencePiece and IREE add 1.6-1.9x latency overhead in comparison with the native C/C++ binaries. The sentencepiece crate allocates a contemporary listing of token items on every name. The overhead is measurable however amortizes at lengthy inputs.

The ultimate Perplexity encoder produces token-exact output towards the reference. In manufacturing, it makes use of rayon to parallelize throughout cores.

Marktechpost’s Visual Explainer

Key Takeaways

• Perplexity rebuilt their Unigram tokenizer focusing on XLM-RoBERTa's 250K-token SentencePiece vocabulary
• The new encoder achieves zero steady-state heap allocations and ~63 µs p50 at 514 tokens
• Three optimizations: double-array trie, bitmap + 64-byte cache-line packing, and a pair of MB big pages for the trie
• Intermediate consequence: a zero-allocation HashMap port alone lower p50 from 326 µs to 155 µs earlier than the trie was modified
• Production impression: 5-6x CPU utilization discount and double-digit ms discount in reranker latency

Check out the Repo and Technical details. Also, be at liberty to observe us on Twitter and don’t neglect to hitch our 150k+ ML SubReddit and Subscribe to our Newsletter. Wait! are you on telegram? now you can join us on telegram as well.

Need to associate with us for selling your GitHub Repo OR Hugging Face Page OR Product Release OR Webinar and so on.? Connect with us

The publish Perplexity AI Open-Sources Unigram Tokenizer That Achieves 5x Lower p50 Latency Than Hugging Face tokenizers Crate appeared first on MarkTechPost.