Suppose there’s a model you’re serving, and this model has a tendency to overuse a specific phrase, one that you don’t particularly like. With specific tokens, you may penalize or ban it outright, but with whole phrases, it can get extremely difficult, as you can’t really penalize the whole token sequence or the starting token, since the blast radius* would end up too large. Wouldn’t it be better if you could make the serving engine enforce a list of full phrases it must not emit?
That’s not too difficult to do in offline serving, but streaming responses makes it quite the interesting challenge. By the time the engine recognizes a complete phrase, some of its tokens may already be on the user’s screen. The model has also consumed those tokens and updated its cache, so removing the text from the response doesn’t remove it from the model’s history. The best way to do it is to hold back output that could still complete a banned string. If a match occurs, rewind that request and sample a different continuation.
Phrase backtracking already exists in some form in ExLlamaV3, KoboldCpp, and AntiSlop Sampler. However, implementing this mechanism in an asynchronous scheduler, including workers that may already be processing a later step, is a bit of a challenge. This exercise and implementation was done in Sonar (previously Aphrodite Engine). Let’s take a look below.
* Yes, I know Claude loves that word.
A phrase is not a token
Consider a schematic tokenization of testament:
test | am | ent
These boundaries aren’t representative of any real tokenizer and used for illustrative purposes only. A real tokenizer might represent the whole word with one token, split it differently, or maybe include a preceding space. Globally banning test would remove otherwise useful continutations such as testimony. Banning only the sequence returned by tokenizing the phrase once would miss other token sequences that decode to the same text. The matcher therefore consumes the text produced by incremental detokenization.
Sonar uses literal substring matching. By default, both phrase list and decode text are case-folded before conversion to UTF-8. There’s also an option for case-sensitive matching, but this doesn’t add word boundaries, or an understanding of paraphrases as an inevitable limitation. A ban on test also matches the beginning of testament.
What reaches the client?
When the model generates test, the engine can’t yet know whether it’ll become testament or testimony. If the next token contributes am, the suffix still needs to be held. If ent follows, the engine has a complete match and can discard the private suffix without retracting anything from the client.
Token boundaries and the replacement continuation are schematic. The matcher was exercised with these chunks and the red shows the match before it’s discarded.
The guard maintains a small output journal containing token IDs and their decoded byte boundaries, and a native C++ (for the purposes of performance) automaton scans new bytes and reports matches, together with the suffix that remains a prefix of a banned phrase. The implementation we opted for uses a trie with failure links, following the Aho-Corasick approach. The journal then releases complete tokens before that suffix, so it doesn’t need to delay every request by the length of the longest configured phrase. Text with no relevant suffix can also leave immediately after the guard checks it.
Token boundaries will still matter when releasing the output. For example, if one token contains both safe text and the beginning of a banned phrase, the whole token stays private. Splitting its visible text while retaining its token ID would make rollback and token-level metadata diverge.
There’s also another boundary inside UTF-8. Some tokenizers produce byte-fallback tokens that don’t immediately decode to a complete character. The journal retrains those zero-width contributions until the decoder resolves them, so rollback includes every token that contributed to the matched character. Overlapping phrases need to be handled as carefully, as the guard keeps enough pending history for a match that started earlier, even when another phrase has just completed. ITs saved automaton state also lets whole-token rollback restore a partial match that crosses the retained boundary.
Choosing another continuation
Once testament completes, the guard identifies the token boundary to rewind to. In the example, that’s the position before test. It removes the rejected suffix from the request’s token history and records test as a blocked token at that position. The retry uses the retained context with that token’s logit set to -INF (negative infinity). The ban belongs to this request at this position, and it must NEVER apply to another request, or globally to every occurrence of the same token (this may go without saying you might say, but I’ve unfortunately had the displeasure of dealing with samplers that accidentally affected other sequences in a batch, perhaps due to implementation oversights because of how far-reaching their effects are).
If another attempted continuation completes a forbidden phrase at the same checkpoint, its starting token joins the blocked alternatives. Moving to a different retry position resets that set. The implementation also caps the total number of retries, so we don’t end up with an impossible set of constraints keeping the request running indefinitely. This little policy changes sampling a bit. After test leads to a failed continuation, blocking it at the retry position also excludes allowed alternatives beginning with that token. Unfortunately, we won’t be exhaustively searching every possible suffix under test.
Consequently, this isn’t an exact sampler from the model’s distribution condition on the absence of banned strings, and more so a bounded backtracking policy. For this reason, you should probably be careful if you plan to use the outputs or probabilities generated by this method for training or evals.
The GPU may already be ahead
In a synchronous loop, the CPU can inspect a token before scheduling the next step. An asynchronous serving engine overlaps scheduling and GPU execution, so when the scheduler sees the match, later work for that request may already be in flight. Sonar’s approach to handling this is through request preemption. It marks output from the abandoned history as stale and removes the request from ordinary execution until its old work drains. The saved replacement history reaches the workers when the request is scheduled again.
Horizontal axis shows the event order. Ordinary scheduling doesn’t guarantee a token for every request in every engine step.
There are two separate requirements we have to meet here, 1) old output must not be appended to the replacement histroy, and 2) memory that old GPU work can still write must not be handed to a different request. The phrase scheduler enables deferred block freeing in the base scheduler. Blocks remain retained until the corresponding execution work is done. Without that, a block could potentially return to the pool, be allocated to request $B$, and then receive a late write from $A$’s abandoned execution. Only $A$ is held for its rewind, so $B$ and $C$ keep their state and remain eligible for scheduling. This is still just a logical isolation, so we can’t guarantee that their latency stays the same. $A$’s replay consumes GPU work, and temporarily retained blocks consume memory from the same pool.
Recovering the cache
Changing the token history is only the CPU-side part of rollback. The next forward pass needs to use model state corresponding to that retained history. Sonar resumes the request through the existing prefix-cache lookup and prefill machinery. We truncate hashes for the discarded suffix and ruses compatible cached state where available. The retained portion after the usable cache boundary is replayed as needed.
The usable recovery boundary depends on the cache layout and surviving cache entries. Position $g$ is generated frontier before rollback. Positions above are only illustrative.
For full attention, earlier KV entries describe earlier tokens, but a recurrent layer has a different state representation. Its running state has absorbed the tokens that are now being removed, so assigning an earlier position to that state doesn’t undo their effect. Hybrid models need to recover a compatible checkpoint and process the retained gap, or recompute from an earlier boundary when needed. The phrase guard delegates this recovery to the cache manager instead of inventing an inverse operation for each recurrent layer. Because of this, prefix caching is required to be enabled for this phrase banning mechanism, and only admits specific cache layouts. We won’t promise that every rewind will hit a nearby checkpoint, as eviction or cache-layout contraints can make replay longer and potentially extend back through the prompt.
Speculative decoding produces more than one answer per step
A speculative verification step can return several accepted tokens for one request, and our guard processes them in order. Suppose the packet contains:
test | am | ent | to | their | resilience
When ent completes the match, the rest of that packet belongs to a history that’s about to be discarded. The scheduler stops consuming it and removes draft tokens based on the old history before retrying. The retry mask also needs to respect the runner’s indexing, for example, a request can occupy several logits rows in a speculative batch. Masking “row A” is therefore not enough. The V2 model runner (same as vLLM’s) maps each logits row back to its request slot and checks its position against the retry checkpoint. A small Triton kernel applies the mask to the matching row. Rows for other requests and other positions aren’t touched by principle. If the batch has no active retry state, that mask kernel isn’t launched at all. The V1 model runner uses a dedicated logits processor for the same position-local restriction.
Pipeline parallelism adds more in-flight work to drain, but doesn’t change the ownership rule. The request must not resume with its shortened history while workers can still deliver output from the old one.
Logprobs and termination belong in the journal too
Streaming token metadata can’t run ahead of streaming text. If a pending token is discarded, its logprob row must be discarded with it. For requests that ask for logprobs, the guard journals those rows and releases them alongside the corresponding token IDs. Prompt logprobs are handled separately so replay doesn’t publish the original prompt’s probabilities a second time.
These are the engine’s token-level logprobs for the retained generation path, so they don’t include a correction for the full history of failed retries, and shouldn’t be interpreted as the normalized likelihood of the final phrase-constrained response.
Termination will also need a proper polciy. For example, a partial prefix such as testam can be released when generation eneds because the complete banned string never appeared. An omitted EOS or stop token contributes no client-visible text. If an included stop token complete a forbidden phrase, the request needs to fail instead of overriding the stop condition.
In our implementation, we currently have a limit of 2,048 phrases, 256 characters per phrase, and a 256 KiB phrase-byte budget. There’s also a limit of pending tokens, and allows at most 128 rewinds per request. Exhausting sampling alternatives or these runtime limits can end the request with an error.
Where the cost comes from
Most tokens need incremental detokenization, a native scan, and journal bookkeeping. Compiled phrase sets can be reused through a bounded cache, so there’s no loop that searches the full generated response separately for every phrase on every token.
HOWEVER, this doesn’t make the path entirely free. Python still manages the journal and scheduling decisions. A failed continuation has already consumed GPU work, and retrained tokens may still need replaying before the engine can sample again.
There’s also the user-visible cost that a tolens-per-second figure will hide. When a suffix remains ambiguous, the client receives no new text even though the engine is generating tokens. A phrase list full of common prefixes can therefore make streaming arrive in bursts (like when you have a spotty internet connection).
Current scope
Our implementation requires the fast Hugging Face incremental detokenizer and async scheduling. Cache connectors are excluded for now, including configurations that move KV state between engines. Other exclusions include text stop strings, structured output grammars, resumable input, encoder inputs, and prompt embeddings. Literal phrase suppression also doesn’t guarantee good writing. Phrase banning only controls substrings in the generated text inspected by the guard, this means that, well, meanings aren’t banned, input prompt isn’t sanitized, and it doesn’t prevent a different spelling from conveying the same thing. If a model is really stubborn about a specific turn of phrase or concept, it WILL try and output it one way or another.
You can find the implementation at dphnAI/sonar#1778.