GraphTok: tokenization as a replayable CUDA graph — one Dynamo frontend feeds 56 GPUs of agentic traffic where the default feeds 2
KTH's preprint runs regex pre-tokenization and BPE merging on-device at bit-exact fidelity across five tokenizer families — all author-reported, and no code is released yet.
KTH researchers built GraphTok, a GPU tokenizer that runs the full encoding path — regex pre-tokenization, BPE merging, and token-ID assembly — as a single replayable CUDA graph, claiming bit-for-bit token-ID fidelity across five tokenizer families. In NVIDIA Dynamo it cuts mean tokenize-stage time for a 121k-token request from 235 ms to 1.2 ms (at one GPU's load) and lets one frontend sustain 518 requests/s of that traffic — the paper's estimate of the busiest-hour load of 56 GPUs — versus 18.5 requests/s for Dynamo's stock tokenizer (arXiv:2610.13325).
What shipped
GraphTok is a paper, not an artifact: no code release, no repo, and no independent coverage exist as of writing. The preprint describes a complete tokenizer on the GPU — device-resident raw bytes to final token IDs — captured as one CUDA graph replayed per request, with no host dispatch, allocation, or synchronization between stages.
The problem it attacks. Agent loops resend long, slowly-changing contexts. A TraceLab study of roughly 4,300 real coding-agent sessions cited in the paper finds the median model invocation carries about 119k cached-prefix tokens but only 875 newly appended tokens and 214 output tokens; 95.7% of input tokens come from the prefix cache. Prefix caching skips most of the prefill — but the request must still be tokenized in full before the cache can be looked up, because cache lookup requires token IDs and appending text can change tokenization, so concatenating a cached prefix with a freshly tokenized suffix is unsafe.
In unmodified vLLM 0.27 on one H100 NVL (the paper's Figure 1), tokenization is 2% of median TTFT for a 130k-token Llama 3.1 8B prompt on a cold cache — and 67% after a prefix-cache hit. For a 40.5k-token Qwen3 32B prompt the shares are 1% and 49%. Once prefill is cached, the "negligible" CPU stage is the largest thing left before the first token.
The mechanism. Two ideas make a GPU tokenizer competitive. First, the reference regex pre-tokenizer is sequential, but for the supported tokenizer families a pre-token boundary at any position can be decided from local character classes plus compact run information, so boundaries are evaluated in parallel across the input. Second, BPE merges within a pre-token are ordered, but the paper has threads of a warp cooperate to find the next highest-priority merge without changing the reference merge order.
Neither alone is enough: a millisecond-scale device call still pays for kernel launches, per-request allocation, and host sync. GraphTok captures the whole pipeline as one CUDA graph with a fixed capacity — buffers and launch geometry provisioned in advance, counters on the GPU recording live occupancy — so one captured graph serves any request up to its capacity with nothing decided on the host. Short inputs go to a CPU engine, where the GPU "cannot win." The authors report the same ordered token IDs as the reference tokenizers (GPT-2, Llama 3, Qwen 2.5, DeepSeek-V3, Gemma 3) "in every timed cell of the evaluation campaign."
The numbers. One million GPT-2 tokens encode in 1.7–3.2 ms including transfers, depending on tokenizer. On Llama 3 that is 4.7–6.0x faster than gigatoken, an open-source SIMD Rust CPU tokenizer — the strongest CPU baseline the paper measures and the subject of an open vLLM integration RFC. On TokTier's own single-request benchmark, GraphTok is 2.6–3.9x faster than gigatoken (with an empty cache) and 2.0–18.1x faster than the released TokTier across 100k–4.4M characters. Integrated into unmodified vLLM, it improves mean TTFT by only 2–4% on a cold cache, but 2.1–2.4x at 99% prefix reuse for 32k–128k-token prompts.
The capacity result is the headline. In NVIDIA Dynamo one frontend tokenizes for a whole GPU fleet, and a slow tokenizer caps the fleet there. Within a 2 s P99 target, at 9.25 requests/s per GPU (BurstGPT's busiest hour), a single frontend sustains this much 121k-token agentic traffic: 18.5 requests/s (2 GPUs) with Dynamo's default tokenizer, 296 (32) with gigatoken, 111 (12) with TokTier, 518 (56) with GraphTok. At 512k tokens the spread is starker: 4.6 (0.5 GPUs), 18.5 (2), and 129.5 (14) for default, TokTier, and GraphTok respectively. Across 121k–1M tokens that is 1.75–2.5x the load gigatoken sustains, with P99 up to 64x lower where gigatoken's tail breaks.
Why it matters
The frontend, not the GPU, is becoming the fleet-size limit in agentic serving. If a CPU tokenizer can feed only N GPUs' worth of requests, buying more accelerators past that point is wasted. GraphTok's specific trick — making tokenization a replayable device graph — is worth stealing even if you never adopt the system: GPU tokenizers historically lost to CPU ones on per-request host dispatch and sync, and CUDA-graph replay amortizes exactly those costs away. The same move generalizes beyond tokenization: any pure input transform that currently round-trips through the host on every agent turn — chat templating, vision preprocessing, structured-input parsing — is a candidate for the same device-side treatment.
The broader lesson is that "tokenization is negligible" was an assumption priced into serving-stack design when prefill dominated TTFT. Prefix caching invalidated it: the paper's own Figure 1 shows tokenization going from 2% to 67% of median TTFT on a cache hit. Anyone running agents against a prefix-cached engine should re-measure that split before adding CPU tokenizer workers — more CPU cores fix aggregate throughput but not long-request latency, and they compete with retrieval, orchestration, and tool execution for the same cores. Existing mitigations, like Dynamo's reuse of token IDs only up to safe boundaries such as completed chat turns, are partial: the remaining text still gets tokenized on the host.
Caveats
- Everything here is author-reported. GraphTok has no released code, no third-party replication, and no independent coverage found; the paper is an unreviewed preprint. The bit-exactness claim is self-audited ("every timed cell of the evaluation campaign"), not independently verified.
- The TokTier comparison deserves skepticism. The 2.0–18.1x figure comes from TokTier's own single-request benchmark, not the stateful incremental mode TokTier was designed for — TokTier's paper claims its own GPU path encodes a 1M-character request in 0.87 ms. The practical gap to an open-source, released tokenizer is likely smaller than the headline. Also, "developed concurrently and independently" is the GraphTok authors' framing; TokTier's arXiv posting (2026-07-31) predates GraphTok's (2026-10-09) by about two months.
- Scope and hardware. Coverage is the five listed BPE tokenizer families (SentencePiece and other preprocessing schemes are outside the claim), measured on one H100 NVL. The paper flags pathological inputs with very long pre-tokens as a case that "must still be processed correctly rather than rejected."
- Where it does not win. For a single uncontended request in one vLLM engine, fast CPU tokenizers come within 4% of GraphTok in mean TTFT (the paper says so directly). The benefit is frontend CPU relief, fleet capacity, and TTFT at high cache-reuse rates — not per-request latency everywhere.