TokTier: Exact Stateful Tokenization for Agentic LLM Serving
Zhenyu Zhang, Zhichao Cao
cs.CL, cs.DC, cs.PF
2026-08-01
TokTier brings stateful tokenization to agent serving, repairing each append and running exact GPU tokenization, cutting vLLM first-token latency 16-34% with zero divergence.
Coding agents like Claude Code and Codex resubmit the entire conversation transcript on every model call. Prefix caching already lets the engine reuse the KV state for an unchanged prefix, but tokenization, the step that turns request text into IDs, runs before the cache is consulted, so the front end re-scans the full context on every call. Across 153,951 calls from two agent ecosystems, the median call appends about 1.4K characters and only 1.0-3.6% of calls are true cold starts or rebuilds. The higher the cache hit rate, the larger the slice tokenization takes: at a 94.1% fleet hit rate it reaches 64% of time to first token (TTFT).
The hard part is that tokenization is not compositional. tok(A) followed by tok(B) does not equal tok(AB). A short append can shift boundaries near the end of the prior sequence: if the last turn ended with "pipe" and the next appends "line", the reference tokenizer merges " pipeline" into one token, drifting the tail and, because the token sequence is also the prefix-cache key, silently invalidating reuse for the rest of the session. A fixed overlap radius is not a correctness rule, because digit grouping, whitespace lookahead, and newline absorption push the effect past any chosen radius.
TokTier enforces one contract: the emitted IDs always equal the reference tokenizer's full-text output. It has two paths for two call modes.
Most calls are session continuations and take incremental repair. TokTier keeps the session's prior token sequence, re-tokenizes only a window (512 characters by default) around the append, and splices only when a stable-boundary check passes, finding a character-class transition where the pre-tokenizer's output to the right provably does not depend on text to the left. On failure it doubles the window, retries up to five times, then falls back to full reference tokenization. One continuation costs O(new text plus window), independent of context length. The first 512-character window accepts 99.995% of 56,052 real splices.
Cold starts and rebuilds have no reusable prefix and take exact GPU full tokenization. GPT-family tokenizers specify pre-tokenization as a leftmost-first regex with backtracking, inherently sequential. The authors observe that the production patterns they study never need backtracking, so the regex folds into run-local rules: characters are classified into four classes, grouped into maximal same-class runs, and whether a character starts a piece depends only on its offset in the run, bounded lookback, and a few run-level summaries computed with prefix scans. The piece-start test becomes an independent per-character predicate. Pieces then feed a size-specialized GPU BPE pipeline (thread, warp, or block per piece).
A shadow verifier samples about 5% of live traffic and re-checks it against the reference, catching bugs that depend on execution history and escape fresh-process tests.
For a fleet already pushing cache hit rates above 94%, tokenization is the next piece of latency worth touching. TokTier drops into vLLM without changing the emitted IDs, so existing models and prefix caches keep working. The cost is operational: it needs session-affine state and a GPU for full tokenization, an optimization for medium-to-large deployments rather than a free win for single users.
The GPU path is bounded by the dependency chain of exact BPE merges (chain depth times memory round-trip), not bandwidth or SMs, so a consumer RTX 5090 runs 11-17% faster than the server card. Two of the 17 families are provably outside the predicate class and always take full tokenization. Zero divergence holds for the frozen artifacts tested, not for future tokenizer versions; each new snapshot must rerun admission, and the shadow verifier stays deployed. Appends above 30K characters hold P99 above 10 ms, and the shipped router does not reroute them to the GPU (which would be 6-28x faster); that path awaits certification.