TokTier: Exact Stateful Tokenization for Agentic LLM Serving

Overview§

TokTier targets the tokenization bottleneck in agentic LLM serving, where long conversational transcripts are repeatedly resent after small tool-result appends. Despite high prompt-cache hit rates (94.1%), re-tokenizing full contexts can consume up to 64% of time-to-first-token (TTFT). The paper introduces a stateful tokenizer that guarantees output tokens are identical to full reference tokenization while reusing previous work via incremental repair and GPU-accelerated exact pre-tokenization.

Core Methodology§

Incremental Repair with Stable-Boundary Check§

For a session continuation with original text $x$ and appended text $\delta$, TokTier avoids full re-tokenization. It re-tokenizes a small window of length $w$ around the append point $p=|x|$, producing candidate tokens for $x[p-w:p+|\delta|]$. The result is spliced with the cached prefix tokens only if the first token in the window is stable — i.e., its start position matches the cached token boundary. This is a per-request check: if the boundary shifted, the window widens (e.g., doubles) and the check repeats. On repeated failure, it falls back to full tokenization. The key insight is that token-boundary shifts from appends are typically local, so small windows succeed in practice. The expected repair cost grows sublinearly with context length; for 100K to 3M characters, repair takes 0.5–1.1 ms (up to 437x faster than HuggingFace tokenizers).

GPU Exact Pre-tokenization§

When no reusable prefix exists (new session or failed repair), TokTier runs full tokenization on a GPU. GPT-family regex pre-tokenization is decomposed into run-local rules (character-class transitions) that can be evaluated in parallel over chunks. Each chunk independently computes its split points, followed by a boundary merge. BPE then runs on the set of pre-tokenized substrings, using a standard byte-pair merge algorithm efficiently parallelized across sequences. Full tokenization of a 1M-character request takes 0.87 ms, 491x faster than HF and 23.4x faster than the prior best CPU method.

Verifier§

A shadow verifier samples live traffic and compares TokTier output against the reference tokenizer. The paper reports zero divergence across 1.5×10^10 split checks, a 12.4 TB real-text corpus, and 93,000+ replayed agent steps.

Results with vLLM§

With vLLM as the LLM server, integrating TokTier reduces median TTFT by 16–34% and P99 by 23% under recorded agent bursts. For a 50 ms P99 objective, 4 repair cores + 1 GPU sustain 1,821 requests/s, while a 16-core stateless front end saturates at 40 requests/s—a 45x throughput improvement.

Key Equations§

The stable-boundary condition for a window at position $p$ is: $\text{start}(\text{token}_0) = p - w + \epsilon$, where $\epsilon$ accounts for boundary alignment. More formally, let $T(x)$ be the reference token sequence. For window $W = x[p-w : p+|\delta|]$, we require that $T(W)[0]$'s start offset matches the cached boundary. If not, update $w \leftarrow 2w$ and retry.

Implementation Sketch§

def incremental_tokenize(cached_prefix, prev_text, append_text, tokenizer):
    p = len(prev_text)
    delta = prev_text + append_text
    w = 128  # initial window size
    while True:
        window = delta[p-w:]
        # tokenize window independently
        window_tokens = tokenizer.encode(window)
        # check stable boundary: does the first token start exactly at p-w?
        if tokenizer.decode([window_tokens[0]]).startswith(delta[p-w]):
            # splice: cached_prefix + window_tokens with first token offset corrected
            return cached_prefix[:-1] + window_tokens  # merge overlapping token if needed
        if w >= len(delta):
            return tokenizer.encode(delta)  # full fallback
        w *= 2

This sketch (simplified) captures the widen-and-retry logic. The actual implementation uses fast character-class rule checks and GPU offload for large windows.

Conclusion§

TokTier demonstrates that exact, stateful tokenization is practical and delivers substantial gains for agentic workloads, where long contexts and small appends dominate. Its design is tokenizer-agnostic (evaluated on 17 tokenizer families) and complementary to KV caching, directly attacking a previously overlooked serving bottleneck.