When a prompt ends with http:, the model concludes that :// cannot follow — because the tokenizer split : into a standalone token (ID 27). With that ID at the end of the context, the token for :// (ID 1358) cannot appear at the next position; that's what the model learned during training. This is a validated example from the Microsoft guidance library documentation.
In serving with prefix caching enabled, the same phenomenon corrupts cache keys. Both problems share the same root cause, and Token Healing fixes both in a single operation.
How Prefix Caches Break
vLLM's Automatic Prefix Caching (APC) and SGLang's RadixAttention use token ID sequences as cache keys. Each request's input is split into blocks (typically 16–32 tokens), and any block whose KV has already been computed is reused. This relies on one assumption: the same natural-language prefix always produces the same token ID sequence. BPE tokenizers break that assumption at boundaries.
Consider the typical RAG pattern:
[fixed system prompt] + [dynamic retrieved chunk] + [user query]
Many implementations pre-compute and cache the KV for the system prompt portion. The cache key is the token ID sequence produced by tokenizing the system prompt in isolation.
SentencePiece-based tokenizers (Llama 2/3, Mistral, Gemma, etc.) process the entire string at once and apply greedy merging. The token IDs at the boundary can differ between tokenizing the system prompt alone versus tokenizing the full "system prompt + chunk" string. Because SentencePiece prepends a space to the following word (the ▁-prefix scheme), which characters come next affects how the space at the current position is segmented.
Take the case where the system prompt ends with "Context:\n":
# tokenize the system prompt alone
tokenizer.encode("Context:\n")
# → [..., ▁Context, :, ▁] ← space as a separate token
# tokenize the full string with the retrieved chunk appended
tokenizer.encode("Context:\n The answer is...")
# → [..., ▁Context, :, ▁The, ...] ← space merged with "The"
The last token ID of the preceding block changed, so it no longer matches the cached block — a cache miss. Even though the natural-language prefix is identical, a different suffix is enough to invalidate the prefix's cache key.
tiktoken (cl100k_base) uses regex pre-tokenization to split on word boundaries first, so this problem is comparatively rare. That's why it surfaces less often when using OpenAI-family models via API. It occurs more frequently with the Llama/Mistral/Gemma families — which happen to be every major model family used in self-hosted serving today.
How Token Boundary Bias Corrupts Output
A cache miss is a performance problem. Token boundary bias is an output quality problem. The cause is the same.
Returning to the http: example: when the model generates tokens after :, the vocabulary probability distribution is distorted. During training, :// frequently followed the : token, but at inference time, if : is already in the input, the model must generate // — and // appearing alone at the start of a sequence is rare in the training distribution. The result is the model generating malformed URLs like http: //www.google.com with an extraneous space, instead of a valid URL like http://youtube.com.
How widespread is this bias? According to the guidance team's analysis, roughly 70% of the top 10,000 tokens in StableLM can be extended into longer tokens. That means when a prompt is cut at an arbitrary position, 7 times out of 10 the last token is acting as an incomplete prefix.
This is especially pronounced in code generation. If a prompt ends with def calculate_, and _ is a token that should have merged with the next word, the model fails to continue the function name pattern correctly. The same distortion appears in LaTeX expressions (cutting off mid-command, e.g., \frac{) and at multilingual boundaries where CJK characters and Latin text alternate. These just look like strange outputs, and tracing the cause back to a tokenizer boundary is not straightforward.
How Token Healing Works and What It Costs
The mechanism is simple. Drop the last one (sometimes two) tokens from the prompt, then constrain the first generated token to those that begin with the bytes of the dropped token.
For the http: case:
- Remove
:(ID 27) - Restrict the first generated token to those starting with the byte
:→:(27),://(1358),:/, etc. - The model selects
://(1358) → correct URL generated
From a prefix caching perspective, the prefix with the last token stripped becomes the cache key. No matter what the suffix is, the token IDs in blocks before the boundary remain stable — the last-token mutation caused by the suffix disappears.
The cost is additional prefill computation.
healing_cost = N_rollback × C_prefill_per_token + C_logit_mask
cache_benefit = N_cache_prefix × C_prefill_per_token (savings on cache hit)
Healing is worth it when:
(cache hit rate improvement × N_cache_prefix) > N_rollback + logit_mask_overhead
N_rollback is typically 1–2 tokens. N_cache_prefix for a system prompt plus document context can be hundreds to thousands of tokens. At a ratio of 1:hundreds, the healing cost is negligible.
This changes at larger batch sizes. In a continuous batching environment, if each request in a batch has a different rollback token, logit masking must be applied per request independently. The current vLLM batch processing implementation has no efficient code path for this. At batch sizes of 32 or more, healing can noticeably reduce prefill throughput, and at that point it needs to be compared directly against the cache hit rate gain.
Decision Criteria by Serving Pattern
| Serving Pattern | Prefix Reuse Rate | Token Healing | Rationale |
|---|---|---|---|
| Chatbot (fixed system prompt) | High | Enable | Improves both cache hit rate and generation quality |
| RAG (fixed SP + dynamic chunk) | Fixed for SP only | Enable | Stabilizes SP boundary caching |
| Code completion (arbitrary prefix) | Low | Enable | Generation quality degradation is the primary issue |
| Multilingual mixed prompts | Medium | Enable | Strong bias at CJK/Latin boundaries |
| Fully dynamic prompts | None | Disable | No cache benefit; pure overhead |
| Batch size 32+, high throughput | Irrelevant | Measure first | Must compare throughput loss vs. cache gain |
Code completion is a special case. Prefix reuse is low, so there is almost no cache benefit, but healing should still be enabled because the model repeatedly branches in the wrong direction at incomplete token boundaries. In this pattern, the justification for healing is generation quality, not caching.
In RAG, healing is effective at stably caching the "prefix up to the system prompt." However, boundary issues inside the retrieved chunk itself are out of healing's reach. Since healing only rolls back the last 1–2 tokens of the prefix, boundary distortions in the middle of a chunk require a separate remedy.
For fully dynamic prompts — where every request is entirely new text — healing has no opportunity to improve cache hit rate at all. Only the additional prefill cost remains, making it a net loss.
Framework Status
guidance: Currently the most complete implementation. Natively supported on LlamaCpp and Transformers backends; this is also the library that established the principles behind token healing. Its nature as a structured generation library makes it impractical to use as a standalone serving engine.
llama.cpp: A feature request was opened in February 2024 as a "good first issue" (issue #5765), with a related PR #24247, but it has not been merged yet.
vLLM: No official token healing API. Prefix caching is enabled with the following flag:
vllm serve meta-llama/Llama-3.1-8B-Instruct \
--enable-prefix-caching \
--max-model-len 32768
Boundary stability is achieved through prompt-template-level workarounds: end the point where a suffix will be appended with a delimiter like \n---\n, and verify in advance that the delimiter always produces the same terminal token ID sequence. Not a complete solution, but it improves boundary stability without additional compute.
SGLang: RadixAttention is enabled by default; there is no separate healing mechanism, and prefix alignment is recommended at the request routing level.
TGI: Prefix caching support is limited, and there is no implementation discussion around token healing.
None of the three serving frameworks has a structural solution for token boundaries. guidance is the furthest along but is not a serving engine. llama.cpp is working toward it, while vLLM and SGLang expect operators to work around the issue through prompt design. The most reliable option available to operators today — rather than waiting for framework support — is to pre-validate that the end of the system prompt terminates at a stable token boundary.