Taking Tokenization off the Host for Agentic LLM Serving

Mohammad Siavashi; Pascal Schwinte; Ali Banaei; Gerald Q. Maguire; Marco Chiesa; Dejan Kostić

cs.DCOct 9, 2026

Taking Tokenization off the Host for Agentic LLM Serving

Authors: Mohammad Siavashi, Pascal Schwinte, Ali Banaei, Gerald Q. Maguire, Marco Chiesa, Dejan Kostić

Organizations: KTH Royal Institute of Technology, Stockholm, Sweden

Abstract

Agentic workloads resend long contexts that barely change between calls. Prefix caching now skips most of their prefill, yet every request must still be tokenized in full before the cache can even be consulted. Tokenization, a CPU stage long treated as negligible, becomes the largest part of time-to-first-token (TTFT), and a frontend that tokenizes for a whole GPU fleet limits how many GPUs it can feed. We present GraphTok, a GPU tokenizer that runs the entire encoding pipeline, from pre-tokenization through byte-pair encoding (BPE) merging to token-ID assembly, as one replayable CUDA graph. GraphTok reproduces the reference token IDs bit-for-bit on GPT-2, Llama 3, Qwen 2.5, DeepSeek-V3, and Gemma 3, hands short inputs to a CPU engine where the GPU cannot win, and plugs into unmodified vLLM and NVIDIA Dynamo. GraphTok encodes one million GPT-2 tokens in 1.7-3.2 ms including data transfers, and on Llama 3 it is 4.7-6.0x faster than gigatoken, the strongest CPU tokenizer. On TokTier's own single-request benchmark, it is 2.6-3.9x faster than gigatoken and up to 18.1x faster than TokTier. In vLLM with a cached prefix, it lowers mean TTFT by 2.1-2.4x. The largest gain is capacity. Within a 2 s P99 target, one Dynamo frontend with GraphTok sustains 518 requests/s of 121k-token traffic, the busiest-hour load of 56 GPUs, against 296 with gigatoken and 18.5 with the default tokenizer. Across 121k to one million tokens, this is 1.75-2.5x the load gigatoken sustains, with a P99 up to 64x lower where gigatoken's tail breaks.

Figures & tables

Figure 1: TTFT breakdown for a cold cache and a prefix-cache hit in unmodified vLLM. The y-axes are broken, and each model has its own scale.

Figure 2: Latency of tokenizing 1M Llama 3 tokens in isolation and next to a RAG workload, on the full host and on four cores. Bars are medians, and whiskers show the range.

Figure 3: GraphTok encode dataflow. Numbered arrows are handoffs between stages, and 6a and 6b are the host and device return paths.

Figure 4: Complete tokenization latency, one document per call, on the Llama 3 vocabulary (log–log, medians of 20 calls, P95 whiskers on GraphTok and gigatoken). Open markers are inputs that GraphTok serves on its CPU route, where it matches gigatoken. The dotted line marks the first input its GPU graph takes over (the 32k file on books, the 64k file on code and chat). TokTier is shown warm (solid) and cold on never-seen text (dashed). The annotated gap is GraphTok ’s lead over gigatoken and warm TokTier on the largest input.

Figure 5: Aggregate throughput (top) and amortized time per document (bottom) for 8k-token Llama 3 documents (log–log, medians of 20 calls, P95 whiskers on GraphTok and gigatoken). GraphTok trails gigatoken at batch 1, where the call is a single-document call that the router serves on its CPU engine for books and code, while the graph-only series forces the GPU graph, which one document leaves mostly idle. From batch 8 on, GraphTok leads every system. The annotated number is its peak lead over gigatoken.

Figure 6: Ratio of the latency on never-repeated documents to the latency of re-encoding one document, one document per call (Llama 3, log

y

, medians of 20 calls). A ratio of

1\times

means no penalty. The CPU engines’ ratios are lower bounds, because most of their cells re-read text an earlier cell had seen, so the plotted value is the first-sight penalty divided by a warm-cache latency. The open markers are GraphTok cells whose cold arm mixed CPU and GPU routes, and the single point below one is a warm-side variance effect, not a cold-arm speedup.

Figure 7: Complete tokenization of one fresh coding-agent context per call, following TokTier’s single-request protocol (SWE-smith Yang et al. (2025) contexts, 20 per size, CPU engines single-threaded, gigatoken with an empty cache, log–log). Markers are medians and whiskers reach the P99. Every engine returns a Python list and matches Hugging Face on every sample. tiktoken, which lacks Qwen’s NFC normalization, is shown for Llama 3.1 only.

	gigatoken, 8 cores		GPU queue		adaptive, $k=2$
req/s	p50	CPU	p50	CPU	p50	CPU
10k	$90\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$79\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$294\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$27\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$95\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$49\text{\,}\mathrm{\SIUnitSymbolMicro s}$
20k	$83\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$71\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$406\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$17\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$98\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$42\text{\,}\mathrm{\SIUnitSymbolMicro s}$
40k	$80\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$69\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$649\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$12\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$192\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$32\text{\,}\mathrm{\SIUnitSymbolMicro s}$
60k	$92\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$69\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$14.7\text{\,}\mathrm{ms}$	$8\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$525\text{\,}\mathrm{\SIUnitSymbolMicro s}$	$25\text{\,}\mathrm{\SIUnitSymbolMicro s}$

Table 1: Concurrent 1–16 KiB requests on 8 CPUs: median latency and host CPU time per request. The GPU queue saturates near 60k requests/s, gigatoken on 8 cores near 80k, the adaptive policy at 77k.

Figure 8: Arrival process derived from BurstGPT: (a) the trace with its busiest hour marked, (b) that hour per second, and (c) concurrent arrivals of the fitted generator against the trace.

Figure 9: Tokenization inside vLLM, one long-context request at a time, never-seen text, 99.85–99.99% of each prompt cached. The left group is Llama-3.1-8B at 32k, 64k, and 131k tokens, the middle group Qwen3-32B (FP8) at 32k to 262k, and the right group Qwen2.5-7B-Instruct-1M at 512k and one million tokens. (a) The server-side tokenizer call per request (log scale). (b) That call’s share of the request’s TTFT. Bars are medians and whiskers the 10th and 90th percentiles over 40 requests per length on Qwen3-32B and 10 on the others. The sweep runs one pass per length without a warm-up call, so the bars are first-sight latencies; every arm sees the same condition. Hugging Face and tiktoken were not run on the 1M-token model, where they take several seconds per request.

Figure 10: gigatoken with a hot and a cold pretoken cache, one request at a time on the Dynamo frontend (Qwen3 tokenizer, median of 40 documents per size, rotating books, code, and multilingual text, log–log). Hot keeps the cache across requests, and cold empties it before every request. GraphTok runs the same documents in its default auto mode, on one H100 NVL and on its CPU route below

16\text{\,}\mathrm{KiB}

. Bottom: GraphTok ’s speedup (ratio of medians) over each gigatoken line, labelled against cold gigatoken. All engines return identical token IDs on every request.

Figure 11: P99 TTFT of one Dynamo frontend against offered load (load expressed in GPUs at 9.25 requests/s each). Every tokenizer is measured at the same loads, up to the first at which it saturates. The dashed line is the

2\text{\,}\mathrm{s}

P99 target; gigatoken runs with its pretoken cache emptied before every request (Figure 10 ). Middle: GraphTok ’s P99 gain, gigatoken’s P99 divided by GraphTok ’s at each load both completed, with the largest gain labelled together with the factor by which GraphTok raises the load sustained within the

2\text{\,}\mathrm{s}

target. Bottom: Dynamo’s tokenize-stage time per request at every completed load.

Figure 12: Coding agents sharing the frontend’s host: Dynamo’s frontend in front of simulated GPUs, and 128 or 256 agents that each work through a long conversation of real SWE-smith trajectories and run real tool calls on the same host. (a, b) CDF of the time to first token of every warm model call. A curve that ends below one shows the fraction of calls served at all. In (b), Hugging Face and TokTier serve only 1–2% of calls, so each is drawn as a bar at the median time to first token of the calls it served, as tall as the share of calls it failed. (c) Dynamo’s tokenize stage per call (mean). (d) Host CPU the tokenizer itself spends per call, from replaying the runs’ prompts through each library on the frontend’s CPUs (bars with nothing else running, ticks with the 128 agents’ tool calls running). Labels in (c) and (d) give gigatoken’s cost relative to GraphTok ’s.

Figure 13: GraphTok overlaps the H100 capacity that steady-state vLLM inference leaves stranded. (a) Twelve milliseconds of the Nsight Systems hardware counters (10 kHz) captured on one clock while vLLM (Qwen3-32B) serves its peak steady-state load (32 streams) and GraphTok tokenizes 590k-token agentic prompts on the same H100, both under MPS; the shaded band is GraphTok ’s real 1.0 ms call, and because MPS co-schedules the two contexts the model’s tensor activity stays up through the burst while GraphTok adds issue, warp, and DRAM demand. (b) Mean share of each resource that vLLM uses and leaves unused at that peak load, against the time-averaged demand of GraphTok tokenizing 10.8 calls/s of 569k-token prompts (6.2M tokens/s).

Figure 14: Stage profile at the largest books input: profiled GPU time per stage (upper bars) and the complete call as graph replay plus transfers (lower bars).

Tokenization

See all 44 papers

Jul 31, 2026

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

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.

Zhenyu Zhang, Zhichao Cao

Arizona State University · Tempe, Arizona, USA

LLM Serving LLM Inference Acceleration Subword Tokenization Tokenization Tokenization in Language Models

Ask PDF

Oct 14, 2026

Delta Tokenizer: Reference-Identical Tokenization of Session Deltas and Segment-Parallelism for Long Prompts on Multicore CPUs

An agent that drives an LLM sends the model the same conversation again and again, and each turn adds only a little text at the end. Inference engines reuse the KV cache of the shared prefix, so only the new tokens pass through the model. However, tokenization has no such shortcut. The CPU front end of the serving engine converts every request back into token IDs from its first character, which lengthens the time to first token (TTFT) and consumes CPU on every turn. We present Delta Tokenizer, a CPU tokenization front end that tokenizes only the delta between a request and the previous request of the same session. It retains the earlier token sequence, encodes again only the appended text and the short tail whose tokens the append could affect, and joins the two only at a position the tokenizer's splitting rules themselves cannot move, which keeps the result exact. For long requests with no state to reuse, it cuts the text where practical tokenizers already keep neighboring pieces independent, encodes the pieces on several cores at once, and concatenates the outputs into the reference encoding, exactly. A shared CPU pool schedules these chunks together with the short incremental updates, so an update runs between two chunks rather than behind an entire long job. The incremental path shortens the tokenization of a session turn by roughly 40x relative to the Hugging Face reference tokenizer, and on 16 cores the chunk-parallel path encodes a four-million-character request 8.2x faster than a serial encode and 1.6-2.1x faster than LoPT. Inside SGLang, Delta Tokenizer reduces the median TTFT through the chat interface by 59% at 100K tokens and brings the P99 TTFT of agent sessions down 9.5x under load and 23x when long requests tie up the front end. Every output we checked matches the reference, among them 41.8 billion documents encoded by its fast encoder.

Zhenyu Zhang, Zhichao Cao

Arizona State University

Tokenization Tokenization in Language Models LLM Inference Acceleration Subword Tokenization

Ask PDF

Mar 3, 2026

GPUTOK: GPU Accelerated Byte Level BPE Tokenization

As large language models move toward million-token context windows, CPU tokenizers become a major slowdown because they process text one step at a time while powerful GPUs sit unused. We built a GPU-based byte-level BPE tokenizer that follows GPT-2's merge rules. It includes a basic BlockBPE-style kernel and a faster, optimized version that uses cuCollections static map, CUB reductions, and a pybind11 interface for Python. On WikiText103 sequences up to 131k tokens, the optimized GPU tokenizer produces the same tokens as a CPU version and, for the longest inputs, is about 1.7x faster than tiktoken and about 7.6x faster than the HuggingFace GPT-2 tokenizer. Nsight profiling shows that 70-80% of CUDA API time goes to memory allocation, so adding memory pooling should give the biggest speed boost next. Tests on generation tasks using WikiText103 prompts show that our GPU tokenizer's outputs stay within about one percentage point of tiktoken and HuggingFace GPT-2 on similarity and overlap metrics, meaning it keeps output quality while making long-context inference more practical.

Venu Gopal Kadamba, Kanishkha Jaisankar

M.S. in Data Science, New York University

Subword Tokenization LLM Inference Acceleration GPU Kernel Optimization

Ask PDF

Abstract

Tokenization

Explore similar work

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

Delta Tokenizer: Reference-Identical Tokenization of Session Deltas and Segment-Parallelism for Long Prompts on Multicore CPUs

GPUTOK: GPU Accelerated Byte Level BPE Tokenization