PaperlayerView exact revision on arXiv

Source-linked AI summary

Taking Tokenization off the Host for Agentic LLM Serving

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

arXiv:2610.13325v1cs.DCcs.CLcs.LGcs.PF

TL;DR

Agentic workloads resend long contexts, so prefix caching reduces prefill while tokenization remains necessary before cache lookup. GRAPHTOK runs the complete supported encoding path in a replayable GPU graph while preserving reference token IDs. It reduces cached-prefix TTFT and increases the request capacity of a centralized frontend.

  • Problem

    Prefix caching avoids repeated prefill for long, reused contexts, but each request must still be tokenized before the cache can be queried.

    Source: §1 · p. 1

  • Method

    GRAPHTOK parallelizes tokenizer-specific frontends and BPE merging, then runs the complete encoding path in a fixed-capacity CUDA graph while preserving reference token IDs.

    Source: §4 · pp. 6–7

  • Results

    Within a 2 s P99 target, GRAPHTOK sustains 518 requests/s of 121k-token traffic in one Dynamo frontend, versus 296 with gigatoken and 18.5 with the default tokenizer.

    Source: §1 · p. 2

  • Takeaways & Limitations

    GRAPHTOK’s benefit is most consequential when a centralized frontend tokenizes for a GPU fleet, where its request path rather than tokenization becomes the limit.

    Source: §8 · p. 23

    The Dynamo experiment simulates its GPUs and measures frontend capacity rather than end-to-end TTFT.

    Source: §6.12 · p. 22

Abstract

from arXiv · show

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.

1 INTRODUCTION

Agentic requests repeatedly resend long contexts, so prefix caching can remove most prefill while leaving full tokenization on the critical path. GRAPHTOK moves the complete supported encoding path to a replayable GPU graph, preserving reference token IDs and improving serving latency and frontend capacity.

1 INTRODUCTION

  • Prefix caching skips repeated prefill, but requests still require full tokenization before cache lookup, and appending only a suffix is not generally safe.With a prefix-cache hit, tokenization rises from 2% to 67% of median TTFT for a 130k-token Llama prompt and from 1% to 49% for a 40.5k-token Qwen prompt.Source: §1 · pp. 1–2
  • GRAPHTOK matches reference token IDs across five production tokenizers and tokenizes one million GPT-2 tokens in 1.7–3.2 ms including transfers.On Llama 3 it is 4.7–6.0× faster than gigatoken; on TokTier’s single-request protocol it is 2.6–3.9× faster than gigatoken and 2.0–18.1× faster than released TokTier.Source: §1 · p. 2
  • At 99% prefix reuse, GRAPHTOK improves mean TTFT by 2.1–2.4× for 32k–128k-token prompts, while cold-cache improvement is only 2–4%.For one uncontended request, fast CPU tokenizers come within 4% of GRAPHTOK, making frontend CPU use and capacity the distinguishing benefits.Source: §1 · p. 2
  • Within a 2 s P99 target, one Dynamo frontend sustains 518 requests/s of 121k-token traffic with GRAPHTOK, versus 296 with gigatoken and 18.5 with the default tokenizer.Across 121k to one million tokens, GRAPHTOK sustains 1.75–2.5× gigatoken’s load, with P99 up to 64× lower where gigatoken’s tail breaks.Source: §1 · p. 2
  • A fixed CUDA graph must accommodate input-dependent pre-token counts, lengths, merges, and output sizes, including unusually long pre-tokens, without host-side dispatch.GRAPHTOK separates graph capacity from live occupancy and provides an exact overflow path within captured execution.Source: §1 · p. 3
  • GRAPHTOK parallelizes each supported tokenizer frontend and preserves pre-token boundaries, merge ordering, and reference token IDs.Its complete encoding path includes frontend processing, BPE merging, and token-ID assembly, with host-visible or device-resident output and integrations for unmodified vLLM and NVIDIA Dynamo.Source: §1 · p. 3

2 MOTIVATION

Agent workloads combine long, highly reused contexts with small updates, while token reuse and added CPU resources do not eliminate all encoding work or host-resource constraints. The remaining work is latency-sensitive and can limit the capacity of a centralized frontend.

Long contexts and high reuse occur together

  • Recent agent workloads combine long contexts with high prefix reuse; Agentix reports per-call prefix-cache hit rates above 90% for chatbot inputs up to about 150k tokens.Source: §2 · p. 3
  • Token reuse and faster tokenization are complementary: reuse reduces text reaching the tokenizer, while GRAPHTOK accelerates the exact encoding work that remains.Safe-boundary reuse does not remove the need to encode parts of requests when reusable state is unavailable or incomplete.Source: §2 · p. 4

CPU resources improve capacity, but remain on the critical path

  • Adding CPU workers raises aggregate throughput but does not reduce individual-request latency in the measured setup, where each worker processes a request on one core.Contention can limit capacity: Hugging Face encoding of 121k-token prompts plateaus at 45 requests/s with 90 CPUs busy on the 96-CPU host.Source: §2 · p. 4
  • During BurstGPT’s busiest hour, one Dynamo frontend with its default tokenizer keeps up with 121k-token agentic traffic from only two GPUs and 512k-token traffic from only half a GPU.Source: §2 · p. 4
  • Co-located retrieval work increases Hugging Face and tiktoken latency by 1.6× and 2.3× on the full host, and by 27.4× and 12.2× on four cores.The measured RAG workload performs embedding, FAISS retrieval, and cross-encoder reranking.Source: §2 · p. 4, Figure 2 · p. 4

Takeaway

  • GRAPHTOK targets the complete encoding operation left after reuse and moves it to the GPU while preserving the reference token sequence.The motivation is to accelerate, not replace, existing reuse mechanisms.Source: §2 · p. 4

3 BACKGROUND

Tokenizer semantics depend on family-specific frontend processing as well as BPE merging, while CUDA graph replay favors fixed execution despite input-dependent workloads.

3 BACKGROUND

  • Modern tokenizers may recognize added tokens, normalize text, split it into pre-tokens, and construct initial symbols before merging; changing these stages can change token IDs.Supported families differ in their splitting and whitespace or byte-fallback rules, requiring family-specific frontend logic.Source: §3 · p. 5

BPE is parallel across pre-tokens but ordered within

  • Different pre-tokens can be processed independently, but merges within one pre-token are ordered and data dependent; CUDA graph replay instead favors fixed execution topology.Each merge changes which neighboring pairs are eligible next.Source: BPE is parallel across pre-tokens but… · p. 5
  • Exactness means matching the reference’s complete ordered token-ID sequence for the same input and special-token settings, not merely the token count or decoded text.Padding and truncation remain outside this encoding contract.Source: BPE is parallel across pre-tokens but… · p. 5

4 DESIGN

GRAPHTOK parallelizes tokenizer-specific frontends and BPE work while preserving reference semantics, then runs variable-length encoding within fixed CUDA graph capacities. It supports both host-returning and device-resident token IDs.

4 DESIGN

  • The shared backend restores document order and compacts per-pre-token results into final token IDs, while batched document offsets prevent cross-document merging.The dataflow separates family-specific frontend processing from shared merging and assembly.Source: §4 · pp. 6–7
  • Three operations remain outside the graph: configuration recognition, request-level policies such as truncation, and Qwen’s Unicode NFC normalization.Unsupported tokenizer structures are rejected rather than assigned approximate semantics.Source: §4 · p. 6
  • Supported frontend patterns become parallel boundary predicates evaluated at each code-point position, with prefix scans supplying run context and ordered pre-token indices.This handles distinct GPT-2, Llama 3, Qwen 2.5, and three-pass DeepSeek-V3 rules without a serial regex cursor; each family needs its own predicate.Source: §4 · p. 6
  • Added-token lookup precedes ordinary pre-tokenization, while Gemma 3 uses a separate frontend for whitespace transformation, known Unicode symbols, and byte fallback.The frontends produce a common ordered symbol-and-boundary representation for the shared merge backend.Source: §4 · p. 6
  • GRAPHTOK assigns independent pre-tokens to merge work and uses warp-cooperative search for the next merge while preserving reference order.For up to 64 initial symbols, lanes compare packed rank-and-position keys; the lowest rank wins and equal ranks resolve leftmost first.Source: §4 · p. 6
  • Pre-tokens longer than 64 symbols use an overflow path within the same launch, rather than host allocation or retry.The shared-memory tournament tree handles up to 512 symbols; still longer repeated-character runs use rounds that reproduce sequential merge order.Source: §4 · pp. 6–7
  • A fixed-capacity graph separates provisioned buffers and launch grids from live request occupancy recorded by device counters and masks.Temporary storage is sized before capture, and no intermediate result returns to the host to select later work.Source: §4 · p. 7
  • The host stages raw text and launches the graph once; a small power-of-two capacity ladder limits fixed inactive work across different request sizes.The graph can return compact token IDs to the host or expose its output buffer directly on the device.Source: §4 · p. 7

5 IMPLEMENTATION

GRAPHTOK identifies supported tokenizer configurations from serialized semantics and combines captured GPU encoding with host-side routing and serving adapters. Its implementation also provides reusable graph contexts, batch encoding, and an adaptive CPU/GPU dispatcher.

5 IMPLEMENTATION

  • Structural asset parsing recognizes supported tokenizer families by serialized semantics and rejects configurations with unsupported behavior.Qwen normalization is applied on the host, and added tokens that normalization could alter are rejected.Source: §5 · pp. 7–8
  • Each context preloads merge tables and family-specific metadata, then captures the frontend, three merge paths, and result assembly in one CUDA graph.Kernels use device counts or empty-row sentinels to skip inactive work.Source: §5 · p. 8
  • A ladder of power-of-two contexts reuses graphs sized to each request, while batch offsets keep documents independent within one replay.The current Gemma frontend does not support batching.Source: §5 · p. 8
  • Below a measured crossover, requests use a CPU engine; an adaptive dispatcher can combine waiting requests into one graph replay.The CPU route uses gigatoken when it passes a probe against the host encoder, with a host-encoder fallback.Source: §5 · p. 8
  • A Python adapter integrates with vLLM without modifying its source, while Dynamo adds a native Rust backend that can share an adaptive dispatcher.Both integrations check a probe against reference token IDs at construction and fall back to the reference encoder on failed calls.Source: §5 · pp. 8–9

6 EVALUATION

The evaluation tests exactness and performance across five vocabularies, three corpora, and multiple input and batch sizes. Every reported measurement matches the reference tokenizer, within the stated encode-mode and configuration scope.

6 EVALUATION

  • The evaluation asks whether complete tokenization improves on production tokenizers, whether it benefits serving and frontend capacity, and what graph replay saves.Exactness is established before timing.Source: §6 · p. 9

6.1 Experimental setup

  • Standalone and batch comparisons use three corpora, ten fixed input sizes, and twenty timed calls per cell on one H100 NVL.Complete-call timings include the selected CPU or GPU route, transfers, and output materialization; graph-only timings measure replay with data already on-device.Source: §6.1 · p. 9

6.2 Does GRAPHTOK produce the reference token IDs?

  • The equivalence claim covers evaluated configurations and encode modes, not arbitrary tokenizer files or all inputs; chat templates, truncation, and padding are outside the comparison.Malformed-byte Gemma tests specify fallback tokens rather than equivalence with a Unicode-text reference API.Source: §6.2 · p. 10
  • Every cell in the exactness campaign and every reported measurement matched the reference tokenizer’s ordered token IDs.The campaign covered five vocabularies, three corpora, and batch sizes from 1 to 256; targeted tests also exercised Unicode, added tokens, long pre-tokens, and batch seams.Source: §6.2 · p. 10

6.3 How does GRAPHTOK compare with CPU and GPU tokenizers?

On long Llama 3 inputs, GRAPHTOK’s complete-call latency leads the compared CPU and GPU tokenizers, while its CPU route handles inputs below the GPU crossover. Its advantage depends on workload: batching helps expose GPU work, and the comparison does not establish cost- or power-normalized superiority.

6.3 How does GRAPHTOK compare with CPU and GPU tokenizers?

  • 4.7–6.0× faster than gigatoken across three corpora on the largest single document.Figure 4 shows complete-call latency; on the largest Llama 3 inputs, GRAPHTOK takes 1.70–1.76 ms.Source: Figure 4 · p. 11, §6.3 · p. 11
  • Below the crossover, GRAPHTOK uses its CPU route; the GPU graph takes over at 32k tokens for books and 64k for code and chat, with its lead growing on larger inputs.The CPU route is within 8% of gigatoken on every cell except the 128-token multilingual input.Source: §6.3 · p. 11, Figure 4 · p. 11
  • The latency comparison is not normalized for cost or power; gigatoken reaches 5.3 GB s−1 in warm batch throughput using all 96 host hardware threads.That measurement repeats a 13 MB corpus and is an upper bound for a cache-dependent engine on repeated text.Source: §6.3 · p. 11
  • A graph replay has a 0.06–0.08 ms floor on the smallest input, while the complete call on one million GPT-2 tokens ranges from 1.7 ms on Llama 3 to 3.2 ms on Qwen 2.5.The floor consists of one launch, one synchronization, and fixed kernel work; Qwen’s complete call includes host NFC normalization.Source: §6.3 · p. 11
  • For 8k-token documents, GRAPHTOK trails gigatoken at batch 1 but leads every system from batch 8 onward.The batch-1 router uses its CPU engine for books and code, while one forced GPU-graph document leaves the graph mostly idle.Source: Figure 5 · p. 12
  • On never-repeated documents, GRAPHTOK’s graph has a 1.03× penalty, while gigatoken’s median penalty is 4.5× and TokTier’s fast CPU engine’s is 2.6×.The CPU engines cache pre-tokens, and the sweep’s ratios are lower bounds on their first-sight penalty.Source: §6.3 · p. 12

6.4 What do the CPU route and the dispatcher add?

GRAPHTOK routes short inputs to an exact CPU engine and uses adaptive dispatch to trade some latency for lower host CPU use. With batching, it becomes fastest from batch 8 onward across the evaluated corpora, while gains level off beyond batch 64.

6.4 What do the CPU route and the dispatcher add?

  • The CPU route handles inputs up to 16 KiB for mostly-ASCII text or 4 KiB when more than 1/64 of bytes start non-ASCII characters; beyond that, routing adapts to observed costs.Source: §6.4 · pp. 12–13
  • At 40k requests/s, adaptive dispatch uses 2.2× less CPU per request than gigatoken, with 0.19 ms median latency, and sustains 77k requests/s.Source: §6.4 · p. 13

6.5 How does throughput scale with batch size?

  • At batch 256, GRAPHTOK leads TokTier by 10–13×, tiktoken by 36–47×, and Hugging Face by 45–59×.Source: §6.5 · p. 14
  • Throughput changes by only −20% to +11% from batch 64 to 256, and the benchmark excludes batch-fill delay that could add online queueing.Source: §6.5 · p. 14
  • From batch 8, GRAPHTOK is fastest on every corpus; its lead over gigatoken peaks at 2.9–3.8× at batches 32–64.Source: §6.5 · p. 14

6.6 How does GRAPHTOK compare with TokTier on TokTier’s own benchmark?

Across TokTier’s single-request benchmark and cached-prefix vLLM tests, GRAPHTOK is fastest or lowers TTFT; inside one engine, the larger distinction is frontend CPU and capacity.

6.6 How does GRAPHTOK compare with TokTier on TokTier’s own benchmark?

  • On TokTier’s own single-request benchmark, GRAPHTOK has the lowest median latency at every size in both families and the lowest P99 from one million characters up.Its median is 2.7–3.7× and 2.6–3.9× faster than gigatoken on Llama 3.1 and Qwen, respectively.Source: §6.6 · p. 15

6.7 Does the speedup reach the serving critical path?

  • At 99% prefix reuse, replacing vLLM’s stock tokenizer with GRAPHTOK lowers mean TTFT by 2.06–2.43× for 32k–128k-token prompts.The tokenization-only gain is 1.76× to 1.91×; gigatoken and TokTier come within 4% of GRAPHTOK in mean TTFT.Source: §6.7 · p. 15

6.8 How much of vLLM’s time to first token is tokenization?

  • Within vLLM, GRAPHTOK is the fastest tokenizer at every length and has the lowest median TTFT at every length.It takes 1.4–2.5% of TTFT versus 56–76% for the stock tokenizer; its median TTFT is 3.5–9.8× below stock, with the gap growing with length.Source: §6.8 · p. 16
  • Under load on one H100, the engine completes about 9 requests/s, while GRAPHTOK and gigatoken median TTFT stay within 15% of each other.The tokenizer choice is not the binding cost in that single-engine setting.Source: §6.8 · p. 16

6.9 How many GPUs can one frontend feed?

With a 2 s P99 target, one Dynamo frontend sustains more offered load with GRAPHTOK than with gigatoken or the default tokenizer. At the measured context lengths, Dynamo’s own request path becomes the limit.

6.9 How many GPUs can one frontend feed?

  • GRAPHTOK needs no cross-request cache for its speed, outperforming gigatoken from 16k tokens on both new text and text its cache has seen.The measured speedups are 2.9–9.0× on new text and 1.6–4.7× on previously seen text.Source: §6.9 · p. 18
  • At 512k tokens and 111 requests/s, gigatoken’s P99 is 14.4 s against GRAPHTOK’s 226 ms, a 64× difference after gigatoken passes its knee.The paper identifies sustained-load ratios as the primary result and cautions that tail ratios depend on the load grid and measurement window.Source: §6.9 · p. 18
  • With GRAPHTOK, Dynamo’s request path rather than tokenization limits frontend capacity; a no-tokenization stub sustains rates within one load step of GRAPHTOK.The stub runs at a per-request cost similar to GRAPHTOK and sustains 444, 111, and 37 requests/s at the three context lengths.Source: §6.9 · pp. 18–19
  • Within the 2 s P99 target, one frontend sustains 518 requests/s at 121k tokens with GRAPHTOK, versus 296 with gigatoken and 18.5 with Dynamo’s default tokenizer.Across 121k to one million tokens, GRAPHTOK sustains 1.75–2.5× gigatoken’s load.Source: §6.9 · pp. 18–19, Figure 11 · p. 19

6.10 Does it hold on a host shared with coding agents?

On a host shared with coding agents, GRAPHTOK serves long agentic prompts while reducing tokenizer CPU demand. Even where existing tokenizers fail to serve most calls, it sustains all calls, and sharing the H100 does not measurably slow the model.

6.10 Does it hold on a host shared with coding agents?

  • At 130k tokens, GRAPHTOK’s median, 90th, and 99th percentile TTFTs are 29, 54, and 93 ms, 14–17% below gigatoken’s 33, 65, and 109 ms.Dynamo’s default tokenizer is 23× slower at the median, while TokTier serves only 66% of calls.Source: §6.10 · p. 20, Figure 12 · p. 20
  • At 590k tokens, the default tokenizer and TokTier serve only 1% and 2% of calls, while GRAPHTOK and gigatoken serve every call with medians of 365 and 373 ms.GRAPHTOK tokenizes 2.2× faster (17.7 against 38.9 ms), although templating and sending token IDs dominate the frontend path at this length.Source: §6.10 · p. 20, Figure 12 · p. 20
  • At 590k tokens, GRAPHTOK uses 1.18 ms of host CPU per call versus gigatoken’s 7.90 ms, or 6.7× less.With agents’ tool calls running, the gap is 8.2×; GRAPHTOK’s CPU time rises to 1.7 ms while gigatoken’s rises to 14.1 ms.Source: Figure 12 · p. 20, §6.10 · p. 21
  • At 130k tokens, the whole Dynamo frontend uses 13% less CPU per call with GRAPHTOK: 23.8 versus 27.5 ms.At 1,000 calls/s, tokenization occupies 1.7–1.8 host cores with gigatoken and 0.2–0.4 with GRAPHTOK.Source: §6.10 · p. 21
  • At 32 streams, vLLM leaves 76% of issue slots, 82% of warp slots, and 43% of tensor-core capacity unused, while GRAPHTOK’s demand is at least 10× below headroom on every resource it uses.At that load, vLLM sustains 434 tokens/s alongside GRAPHTOK versus 436 tokens/s alone, with no measurable slowdown.Source: §6.10 · pp. 21–22, Figure 13 · p. 21
  • At the largest books input, upper bars show profiled GPU time per stage, while lower bars show the complete call as graph replay plus transfers.Source: Figure 14 · p. 22

6.11 Where does the time go, and how much does graph replay save?

The stage profile identifies BPE merging, rather than pre-tokenization, as the largest contributor across all five tokenizers. Graph replay reduces complete-call latency most at short inputs, where dispatch is a larger share of the call.

6.11 Where does the time go, and how much does graph replay save?

  • BPE merging is the largest stage for all five tokenizers, while output compaction is consistently the smallest.Pre-tokenization is not where the time goes; frontend cost varies with each tokenizer family’s normalization and pre-tokenization rules.Source: §6.11 · p. 22
  • The profiled stages sum to 1.08–2.07 ms, 4–7% above unprofiled graph replay because the sum counts concurrently running graph nodes.The complete host-returning call takes 1.74–2.72 ms, with the remainder over graph replay due to transfer and output materialization.Source: §6.11 · p. 22
  • Graph replay reduces median complete-call latency by 21–23% from 128 to 2k tokens, 20% at 8k, and 12% at 32k and 100k.The comparison uses the same GPT-2 pipeline and host-returning interface, with capacity-specific launch plans prepared during warmup.Source: §6.11 · p. 22

6.12 Limitations

The evaluation covers five concrete tokenizer configurations, not arbitrary tokenizer.json files, and does not establish hardware scaling. Serving and frontend experiments also use specific single-GPU or simulated settings.

6.12 Limitations

  • GRAPHTOK supports five concrete tokenizer configurations rather than arbitrary tokenizer.json files; adding a family requires a new frontend predicate.All experiments use one H100 NVL, so hardware scaling is not established.Source: §6.12 · p. 22
  • The vLLM serving experiments use one model on one lightly loaded GPU and do not measure a saturated multi-GPU engine.The CPU-route crossover is tuned on never-repeated text; on repeated short documents, the router can keep the graph where a warm CPU engine would be faster by up to 2.4× at batch 1.Source: §6.12 · p. 22
  • The Dynamo experiment simulates GPUs, runs with its prefix tokenizer cache off, and measures frontend capacity rather than end-to-end TTFT.The agentic-host tokenizer CPU cost is measured by replay outside Dynamo, and the GPU-sharing measurement covers one model, one load, and two tokenization rates.Source: §6.12 · pp. 22–23

7 RELATED WORK

Related work accelerates tokenization on CPUs or GPUs, or reduces repeated work through token and model-state reuse. GRAPHTOK complements reuse by accelerating encoding for new text and any remainder that still needs tokenization.

7.1 Tokenization acceleration

  • CPU approaches accelerate BPE with parallelism, SIMD, caches, or overlapping input regions, while keeping token IDs on the host; GRAPHTOK produces them on the accelerator and supports device-resident output.Fast WordPiece targets a different algorithm, while Fastokens, gigatoken, and LoPT address BPE tokenization on CPUs (Song et al., 2021; Kejzman et al., 2026; Rød, 2026; Shao et al., 2026).Source: §7.1 · p. 23
  • Prior GPU tokenizers either target WordPiece or omit parts of the byte-level BPE frontend; GRAPHTOK preserves family-specific frontends and captures the complete pipeline in one preallocated graph.TokTier is concurrent, independent work compared against its released package.Source: §7.1 · p. 23

7.2 Reusing tokenization and prompt state

  • Token-ID caching can bypass repeated text, but arbitrary fragments are unsafe reuse units because BPE merges and pre-token boundaries can change at a join.Dynamo reuses IDs only at safe boundaries and must still encode after a cache miss or edit (NVIDIA, 2026b).Source: §7.2 · p. 23
  • Incremental and streaming algorithms reuse state or a growing stream, complementing GRAPHTOK, which accelerates new text and whatever remainder still needs encoding.Jiang and Gong maintain BPE tokenization as text grows; Mamouras et al. bound lookahead for emitting a canonical token stream (Jiang & Gong, 2026; Mamouras et al., 2026).Source: §7.2 · p. 23
  • Prefix caches retain KV state but need token IDs before matching begins, leaving tokenization cost in the request path.Examples include SGLang’s RadixAttention and vLLM’s automatic prefix caching (Zheng et al., 2024; vLLM Team, 2026).Source: §7.2 · p. 23

8 CONCLUSION

GraphTok matches reference token IDs across five production tokenizers and leads measured engines above the CPU-route crossover; its fleet-scale benefit is capacity, where Dynamo’s request path becomes the limit.

8 CONCLUSION

  • Above the CPU-route crossover, GraphTok is the fastest measured engine across standalone, batched, and TokTier single-request protocols, while matching five production tokenizers bit-for-bit.The reference token IDs match in every evaluated cell.Source: §8 · p. 23
  • In unmodified vLLM, fast CPU tokenizers come within 3–18% of GraphTok on a single uncontended request, and its latency benefit appears after prefix reuse exposes frontend cost.Source: §8 · p. 23
  • With fleet-scale tokenization, the benefit becomes capacity; GraphTok shifts Dynamo’s limit from tokenization to its request path, motivating device-resident token IDs to remove remaining transfer and synchronization.Source: §8 · p. 23
Loading 2610.13325v1…