Delta Tokenizer: exact delta tokenization cuts agent-session P99 TTFT 9.5× under load, 23× when long requests tie up the front end
ASU's CPU tokenization front end reuses the previous turn's token IDs instead of re-encoding the whole session — ~40× per-turn speedup, 59% median TTFT cut inside SGLang, reference-identical on every checked output.
Arizona State University researchers have released Delta Tokenizer, a CPU tokenization front end that treats each request as a delta of the previous turn in the same session: it keeps the earlier token IDs, re-encodes only the appended text and a short tail, and splices at a boundary the tokenizer's own splitting rules cannot move. In SGLang they report a 59% cut in median TTFT at 100K-token contexts and agent-session P99 TTFT down 9.5× under load — 23× when long stateless requests tie up the front end. The incremental path and a fast encoder are open source (Apache-2.0) in the toktier repo; the chunk-parallel path, the CPU-pool scheduler, and the SGLang adapter are promised in the same repository.
What shipped
Delta Tokenizer (Zhenyu Zhang and Zhichao Cao, Arizona State University) was posted to arXiv on 14 October 2026 as arXiv:2610.19801 — 42 pages, 14 figures, 35 tables. It is a tokenization front end, not a model: an adapter plugs it into a serving engine "with no change to the engine itself," leaving the inference stack untouched.
Three pieces of the design are reported: an incremental path that reuses a session's previous token IDs; a chunk-parallel path that encodes stateless long requests across CPU cores; and a worker-pool scheduler that interleaves the two. Of these, toktier (the repo that hosts the team's earlier TokTier stateful tokenizer, Apache-2.0) currently contains the incremental path and the fast encoder; the arXiv record states that "the chunk-parallel path, the CPU pool scheduler, and the SGLang adapter will be released in the same repository."
Evaluation covers six byte-level BPE tokenizers — including Qwen3, gpt-oss, Llama-3.1, and DeepSeek-V3 — across three CPU platforms, with SGLang serving Qwen3-8B and gpt-oss-120b on web text, code, multilingual text, public coding-agent transcripts, and agent trajectories. The per-session state the incremental path keeps is modest: about one megabyte beyond the text the session already stores at 100K tokens, "four orders of magnitude and more below the KV cache."
Why the tokenizer is now the bottleneck
The KV cache already made repeated model work nearly free: each agent turn resends the whole conversation, but the model only runs over the new tokens. Tokenization has no equivalent — it is the last stateless step in an otherwise stateful stack, and it re-reads the entire history on every turn.
The paper quantifies how much that matters as contexts grow. In the authors' own vLLM sweep, the tokenizer's share of time to first token (TTFT) rose from 10% to 64% as the prefix-cache hit rate approached 0.99. In SGLang, a Qwen3-8B chat turn whose 100K-token prefix is already cached reaches its first token after 145 ms — and 93–99 ms of that is the reference tokenizer running on a single CPU core. The KV cache cannot absorb this work itself, because it "is keyed by exactly the token IDs the tokenizer still has to compute."
How incremental reuse stays exact
Naive concatenation fails because an append can rewrite already-emitted tokens: a request ending in pipe that receives line ends with pipeline as one token. BPE is not the only stage that can shift a boundary — the tokenizer also normalizes characters, matches special-token strings, and pre-tokenizes into pieces, any of which can move a token edge near the append. Wrong IDs matter even when they decode back to readable text: "An incorrect token sequence changes what the model receives and what its KV cache can hit."
Delta Tokenizer re-encodes the appended text together with a short stretch from the tail of the preceding request, finds where the new token sequence agrees with the old one, and splices the two "at a boundary that the splitting rules of the tokenizer itself cannot move, and nowhere else." If the window holds no such boundary, it is enlarged; the final fallback re-encodes everything after the last sealed boundary. The key phrase in the paper: "the check, rather than any fixed overlap, is what makes the reuse exact."
A session turn drops from 93–99 ms to about 2 ms — "roughly 40×" relative to the Hugging Face reference tokenizer SGLang uses by default. The gain comes from the reuse, not the encoder: the fast encoder used without session state is "no quicker than the reference" on 100K-token chat requests.
How parallel full encodes stay exact
Sessions with no reusable state — a fresh start or an edited history — still need a from-scratch encode, and a long one can hold a tokenization worker for hundreds of milliseconds. For arbitrary cuts, parallel encoding of BPE is unsafe: "where a token ends may hinge on text far away." Existing parallel tokenizers cut anywhere and mend seams with overlap plus retries; the paper claims LoPT, the most recent of these, "is not exact in its published form."
Delta Tokenizer exploits structure instead: the pre-tokenizer already breaks text into pieces that BPE never merges across, so the front end cuts only where that split cannot move, leaving special-token strings and Unicode normalization undisturbed across the cut. Chunks (64K characters by default) encode independently on separate cores, and "concatenating the outputs yields the whole request's encoding, with nothing to reconcile at the seams and nothing to retry." On 16 cores, a four-million-character request encodes 8.2× faster than a serial encode and 1.6–2.1× faster than LoPT.
The scheduler treats both job types together: a worker pool gives every session a home worker holding its reuse state, feeds chunks from a shared queue, and lets an incremental update slip in between chunks. With the same FIFO queue and the same workers, scheduling chunks rather than whole requests cuts P99 latency for million-character requests from 374 ms to 103 ms.
The SGLang numbers
The paper's serving results, all through the authors' SGLang adapter:
- Median TTFT through the chat interface down 59% at 100K tokens (the median context of the agents the authors traced).
- Under load — 24 turns per second across sessions — agent P99 TTFT falls from 995 ms to 105 ms (9.5×).
- When long stateless requests exceed the model's context and tie up the front end, agent P99 TTFT falls from 1,441 ms to 63 ms (23×).
- When those long documents are admitted and served from the prefix cache, agent P99 TTFT drops from about half a second to under 70 ms (~7×), and about 20× on a one-core server or a smaller model.
- For comparison, the paper measures fastokens, a backend that also reuses earlier work, as equally fast — but with wrong token IDs on 78 of 279 raw-text requests.
Only when every long document is new does GPU prefill take over the tail; in that regime the three front ends land within 5% of one another.
Why it matters
For anyone serving coding agents or other long-session workloads, tokenization has quietly become the dominant per-turn CPU cost: it grows with the history, repeats on every turn, and sits in front of a model whose cache can no longer help it. Making it incremental — and exact — removes a cost that otherwise widens as contexts do. The correctness rule (a check that finds a boundary the tokenizer cannot move, rather than a fixed overlap) makes both reuse and seam-free parallelism safe, and the adapter design means engines adopt it without internal changes. SGLang already has an open request, issue #41148, to stop re-tokenizing the whole history on every chat turn — a separate, model-agnostic proposal — a sign the default path pays this cost everywhere today.
Caveats
- Every number above is the authors' own measurement; we found no independent replication or third-party benchmark of the paper's results.
- Only the incremental path and fast encoder are released. The headline 8.2×/1.6–2.1×, the scheduler, and the SGLang TTFT results depend on components the arXiv record says "will be released," so they cannot yet be inspected or reproduced from the repo. The SGLang numbers come from an out-of-tree adapter; the paper says the adapter will be released and nothing is merged upstream, so we infer it is not yet available.
- The correctness claims come in two different accountings that the sources do not reconcile: the paper says "41.8 billion documents encoded whole by the fast encoder," while the repo README records "57.0 billion checks across 15 tokenizer artifacts and 3.8 billion real documents (12.33 trillion characters), with zero observed divergence." Both are the authors' own claims; neither has been independently audited.
- The exactness argument leans on the pre-tokenizer's split property, and the evaluation covers six byte-level BPE tokenizers; other tokenizer families are not addressed.
- The assertion that LoPT "is not exact in its published form" is the paper's characterization of a peer-reviewed ACL 2026 system, not an independent finding.