Why Tokenization Latency Can Dominate LLM Inference — And How Perplexity Cut It by 5×

In the race to optimize large language model (LLM) inference, most engineers instinctively focus on GPU performance — kernel fusion, quantization, batching strategies, and memory bandwidth. But in certain high-throughput, low-latency applications, the real bottleneck lies elsewhere: CPU-side tokenization.

This is especially true for workloads like rerankers and classifiers, where model inference itself is relatively cheap. In these systems, tokenization latency can sit squarely on the critical path, quietly dominating end-to-end performance.

A recent engineering effort by Perplexity AI highlights just how significant — and solvable — this problem can be.

The Hidden Bottleneck in “Fast” Models

Consider smaller transformer models such as XLM-RoBERTa rerankers. These models typically run inference in single-digit milliseconds on modern GPUs. At such speeds, even seemingly small preprocessing overheads become consequential.

Tokenization, often treated as a negligible preprocessing step, becomes a major contributor to latency:

• It runs on the CPU, not the GPU
• It involves string processing, trie traversal, and memory access patterns
• It frequently includes heap allocations and hash map lookups

In production pipelines, these factors add up. Tokenization can match — or even exceed — model execution time, limiting throughput and inflating latency budgets.

The Finding: A 5× Tokenization Speedup

Perplexity AI tackled this problem head-on by rewriting their unigram tokenizer in Rust. The results were striking:

• p50 latency dropped from 326 µs to 68 µs at ~514 tokens
• That’s roughly a 5× improvement
• Latency reductions translated directly into double-digit millisecond gains at the system level

More importantly, CPU utilization dropped by 5–6×, significantly improving infrastructure efficiency.

What made this possible? Not a new algorithm — but a rethinking of data structures and memory layout.

The Core Optimization: From Hash Maps to Double-Array Tries

The Hugging Face tokenizer implementation relies heavily on:

• Hash map trie lookups
• Pointer-heavy structures
• Per-token heap allocations

While flexible, this design incurs heavy CPU overhead due to:

• Pointer chasing (cache misses)
• Hash computations
• Fragmented memory access patterns

Perplexity replaced this with a double-array trie, a compact structure with several advantages:

1. Contiguous Memory Layout

Instead of scattered heap allocations, all trie nodes are stored in contiguous arrays. This allows:

• Sequential memory access
• Reduced cache misses
• Improved prefetching efficiency

2. L2 Cache Residency

The working set of the tokenizer was optimized to fit entirely in L2 cache (~100 KB). This is critical because:

• Accessing L2 cache is orders of magnitude faster than main memory
• It eliminates expensive memory stalls during traversal

3. No Pointer Chasing

By eliminating pointers and replacing them with indexed lookups:

• CPU avoids costly memory indirections
• Traversal becomes predictable and branch-friendly

Micro-Optimizations That Add Up

Beyond the structural change, several low-level optimizations played a key role:

Bitmap-Based Child Checks

Instead of maintaining arrays of child pointers, Perplexity used bitmaps to represent child existence:

• Reduces memory footprint
• Enables constant-time existence checks
• Improves branch prediction

Cache-Aligned Nodes

Trie nodes were packed into 64-byte cache-aligned blocks, matching typical CPU cache line sizes:

• Minimizes cache line splits
• Reduces instruction overhead
• Improves locality

Huge Pages

Switching from standard 4 KB pages to huge pages reduced TLB (Translation Lookaside Buffer) misses:

• Fewer page table lookups
• Lower address translation overhead
• Smoother memory access at scale

Why This Matters in Production

In real-world deployments, these changes have profound implications.

1. Latency Gains Are Compounded

If tokenization drops by hundreds of microseconds per request, and your system handles thousands of requests per second:

• You recover milliseconds per request
• You reduce tail latency (p95/p99)
• You improve responsiveness in user-facing systems

2. CPU Becomes a Bottleneck Solver, Not a Bottleneck

Tokenization inefficiencies often:

• Inflate CPU usage
• Limit horizontal scaling
• Compete with other system components

Reducing tokenization overhead by 5–6× frees CPU resources for:

• Request routing
• Post-processing
• Parallel workloads

3. Better GPU Utilization

When tokenization slows down input pipelines, GPUs sit idle waiting for data. Faster tokenization means:

• Higher GPU occupancy
• Better throughput
• Lower cost per inference

The Trade-Off: Memory for Speed

This redesign wasn’t free. The tokenizer’s memory footprint increased significantly:

• From ~9 MB → ~50 MB

However, this trade-off was deliberate:

• The active working set remains small (<100 KB)
• The larger footprint mainly supports the static trie structure
• The performance gains far outweigh the extra RAM cost in most production environments

What’s Still Unresolved

While the results are impressive, this approach comes with limitations:

Static Vocabulary Constraints

Double-array tries are best suited for fixed unigram vocabularies. They struggle with:

• Dynamic vocabularies
• Frequent updates
• Certain multilingual scenarios

Limited Applicability to Other Tokenizers

Modern tokenization schemes like:

• BPE (Byte Pair Encoding)
• WordPiece

have different computational patterns. Applying similar optimizations requires further research and engineering effort.

Infrastructure Limitations

Reliance on huge pages may not be feasible in:

• Containerized environments
• Memory-constrained systems
• Certain cloud configurations

The Bigger Lesson: Data Structures Matter

The key takeaway isn’t just that tokenization can be optimized — it’s how.

This work reinforces a fundamental principle of systems engineering:

Performance is often determined more by data layout and memory access patterns than by algorithmic complexity.

By:

• Choosing cache-friendly structures
• Eliminating unnecessary allocations
• Designing for modern CPU architectures

Perplexity achieved a step-change improvement without changing the underlying tokenization algorithm.

Closing Thoughts

Tokenization is often treated as a solved problem — a preprocessing step unworthy of optimization. But in high-throughput LLM systems, especially those using smaller models, it can become the dominant cost.

Perplexity’s work is a powerful reminder that:

• End-to-end performance matters more than headline model speed
• CPU bottlenecks can rival GPU inefficiencies
• Low-level systems design still delivers massive wins in AI pipelines

As LLM applications continue to scale, optimizing the “boring” parts of the stack — like tokenization — may yield some of the biggest gains.