# TokTier: Exact Stateful CPU+GPU Tokenization for Agentic LLM Serving

arXiv: https://arxiv.org/abs/2607.29678 · HTML: https://mlsanity.com/paper/2607.29678/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 35 references that are in the map.
- First posted on arXiv 31 Jul 2026.

## Builds on (most cited first, 10 of 10)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://mlsanity.com/paper/2401.09670/) (2024)
- [Splitwise: Efficient generative LLM inference using phase splitting](https://mlsanity.com/paper/2311.18677/) (2023)
- [CacheGen: KV Cache Compression and Streaming for Fast Large Language Model Serving](https://mlsanity.com/paper/2310.07240/) (2023)
- [BurstGPT: A Real-world Workload Dataset to Optimize LLM Serving Systems](https://mlsanity.com/paper/2401.17644/) (2024)
- [TraceLab: Characterizing Coding Agent Workloads for LLM Serving](https://mlsanity.com/paper/2606.30560/) (2026)
- [CacheWise: Understanding Workloads and Optimizing KVCache Management for Efficiently Serving LLM Coding Agents](https://mlsanity.com/paper/2606.16824/) (2026)
- [GPUTOK: GPU Accelerated Byte Level BPE Tokenization](https://mlsanity.com/paper/2603.02597/) (2026)

## Built on by (most cited first, 4 of 4)

- [Taking Tokenization off the Host for Agentic LLM Serving](https://mlsanity.com/paper/2610.13325/) (2026)
- [Ready Cohorts: Bounding GPU Opportunity and Avoiding Host Round Trips in LLM-Agent Control](https://mlsanity.com/paper/2608.12123/) (2026)
- [Component-Weighted Centroid Search for Exact Incremental BPE](https://mlsanity.com/paper/2609.40016/) (2026)
- [Delta Tokenizer: Reference-Identical Tokenization of Session Deltas and Segment-Parallelism for Long Prompts on Multicore CPUs](https://mlsanity.com/paper/2610.19801/) (2026)

## Abstract (arXiv)

LLM serving caches prompt KV state, yet most front ends still re-tokenize the full request on every call. Coding agents pay most: sessions repeatedly submit a long transcript after a small append, which can shift token boundaries near the end of the prior sequence. Across 153,951 calls the median append is ~1.4K characters; only 1.0-3.6% of calls start or rebuild a session, yet those carrymulti-million-character contexts. Fleet prompt-cache hit rate is 94.1%, and as it approaches 0.99, tokenization grows from 10% to 64% of time to first token (TTFT) in component measurements. TokTier is a stateful CPU+GPU tokenization service for this two-mode workload, under one contract: emitted token IDs are always identical to full reference tokenization. For session continuations it re-tokenizes a small window around the append and splices only when a per-request check finds a stable pre-tokenization boundary; failed checks widen the window or fall back to full reference tokenization. For calls without a reusable prefix it runs exact GPT-family regex pre-tokenization and BPE on a GPU. A sampled shadow verifier re-checks live traffic. Across 17 production tokenizer families, differential campaigns cover 1.5x10^10 split checks, a 12.4 TB real-text corpus, and 93,000+ replayed agent steps, with zero divergence. Incremental repair takes 0.5-1.1 ms from 100K to 3M characters, up to 437x faster than HF tokenization and 2.1x faster at 1M characters than the strongest cache-based baseline (Gigatoken) fully prewarmed. GPU tokenization encodes a 1M-character request in 0.87 ms, up to 491x below HF and 23.4x below the fastest published CPU method on the same protocol. With vLLM, median TTFT drops 16-34% and P99 TTFT 23% under recorded bursts. Under a 50 ms P99 objective, a four-core repair pool plus one GPU sustains 1,821 requests/s, where a 16-core stateless front end saturates at 40 requests/s.