TokTier: The Hidden Bottleneck in Agent Inference Is Tokenization

When prompt-cache hit rates have already reached 94.1%, why can an agent still take a long time to produce its first token? A paper submitted on July 31 offers a counterintuitive answer: the GPU may not be waiting on model computation at all. It may be waiting for the CPU to tokenize millions of characters again.

KV cache reuse does not remove repeated frontend work

A normal chat request usually contains a new piece of text. Coding agents generate a very different traffic pattern. They retain a long history of actions and observations, append a small tool result after each step, and submit the entire context again.

The TokTier authors analyzed 153,951 calls from two agent ecosystems. The median continuation appended roughly 1,400 characters. Only 1.0%–3.6% of calls started or rebuilt a session, yet the complete contexts in those calls could reach millions of characters. The serving backend may reuse the KV cache, while the frontend tokenizer still scans the full request from scratch. In the paper's component measurements, as the prompt-cache hit rate approaches 99%, tokenization grows from about 10% to 64% of time to first token.

Simply replacing a tokenizer with a faster Rust implementation does not solve the entire problem. The defining pattern is “a huge old prefix plus a short new suffix.” The serving stack needs to reuse the previous tokenization state instead of repeating work on the same prefix at every turn.

Recompute the boundary, but preserve exact token IDs

The difficult part is that BPE tokenization is not a simple append operation. New characters can change token boundaries near the end of the previous text. If a system concatenates token sequences naively, its token IDs may differ from a full reference tokenization, breaking the alignment required for KV-cache reuse.

TokTier stores the previous token sequence for a session and re-tokenizes only a window around the newly appended text. It then performs a per-request stable-boundary check. If the boundary is safe, the new result is spliced into the existing sequence. If not, the window is widened; if the result is still unsafe, the system falls back to full tokenization.

The goal is not an approximation. TokTier makes a strict promise: the emitted token IDs must be identical to those produced by the reference tokenizer when it processes the complete request from the beginning. For requests without a reusable prefix, the system decomposes GPT-family regular-expression pre-tokenization into run-local rules and runs exact pre-tokenization and BPE on a GPU. A sampled shadow verifier checks live traffic for divergence.

The paper reports 15 billion split checks across 17 tokenizer families, a 12.4-terabyte real-text corpus, and more than 93,000 replayed agent steps, with zero divergence in those campaigns. Incremental repair takes 0.5–1.1 milliseconds for contexts ranging from 100,000 to 3 million characters, up to 437 times faster than the Hugging Face tokenizer. GPU-based full tokenization processes a 1-million-character request in 0.87 milliseconds.

The metric that matters is end-to-end latency

After integration with vLLM, TokTier reduced median time to first token by 16%–34% and lowered P99 latency by 23% under bursty traffic. Under a 50-millisecond P99 target, four repair CPU cores plus one GPU sustained 1,821 requests per second, while a 16-core stateless frontend saturated at 40 requests per second.

These numbers still need to be read carefully. The work is a preprint, and its evaluation is based on two agent ecosystems and a particular hardware configuration. A stateful tokenization service also introduces session routing, state consistency, GPU-utilization, and failure-recovery costs. That does not mean every chat API should add a GPU tokenizer.

The more important lesson is that the optimization target changes as the stack gets faster. Earlier work focused on model computation, KV-cache compression, and speculative decoding. Once those components improve, an ordinary CPU preprocessing step can become the longest pole in the request path.

For agent serving, inference optimization is no longer only about making the model calculate faster. It is about eliminating repeated work across the entire request pipeline. The next latency win may not come from a larger GPU or a new decoding trick; it may come from refusing to tokenize the same history twice.