Tokenization and incremental detokenization

Three bug reports, all from the same root cause.

These are not exotic. vLLM carries a dedicated recovery path for the first one, keyed off an error string that comes out of the Rust tokenizers crate:

# Only tokenizers >= 0.22.0 supports DecodeStream with native prefill
# (ids parameter) used for FastIncrementalDetokenizer.
USE_FAST_DETOKENIZER = version.parse(tokenizers.__version__) >= version.parse("0.22.0")

# Error string from https://github.com/huggingface/tokenizers/blob/909fdde2a4ffedd9295206f705eb612be2a91b12/tokenizers/src/tokenizer/mod.rs#L1042
INVALID_PREFIX_ERR_MSG = "Invalid prefix encountered"

The comment attached to the handler for that error is the whole chapter in one sentence: "Recover from edge case where tokenizer can produce non-monotonic, invalid UTF-8 output, which breaks the internal state of tokenizers' DecodeStream" (vllm/v1/engine/detokenizer.py:L235-L238, referencing vLLM issue #17448). Detokenisation is stateful, and its state can go wrong in ways that only manifest as text.

A BPE vocabulary maps integers to byte sequences, and nothing requires those bytes to be valid UTF-8 on their own. When the tokenizer meets a character whose bytes never earned a merge — most emoji, plenty of CJK, essentially all Burmese — it falls back to emitting raw bytes, one token per byte. vLLM's decoder names this: "utf-8 char at the end means it's a potential unfinished byte sequence from byte fallback tokenization" (vllm/tokenizers/detokenizer_utils.py:L260-L264). So the naive streaming algorithm — for id in new_ids: emit(tokenizer.decode([id])) — is wrong, and wrong only on the inputs your test suite lacks.

The URGENCY prefix is not decoration — it is lifted from vLLM's regression test, whose comment records the choice: # Using "URGENCY" since "CY" has token id 130282 (tests/tokenizers_/test_detokenize.py:L108), a Pixtral-12B id exercising the V3-Tekken edge case from PR #9625. The other fixture is Burmese, flagged as triggering "an edge-case where tokens may map to bytes with incomplete UTF-8 characters" (tests/tokenizers_/test_detokenize.py:L105-L107).

The correct algorithm is therefore: keep a window of recent tokens, decode the window, emit only the suffix that is now stable. Everything below is bookkeeping for that one idea.

Let $I = [i_1, \dots, i_n]$ be all token ids so far (prompt plus output) and $S(\cdot)$ the tokenizer's many-tokens-to-one-string decode. The quantity to emit at step $n$ is

where $p$ is the prefix offset, $r$ the read offset, $p \le r \le n$, and $\setminus_{\text{prefix}}$ means "strip the left-hand string as a prefix". Two nested windows, decoded independently; the delta is the difference.

Why two windows instead of one? Because $S$ is not a homomorphism. Decoding ["▁Hello"] and ["▁Hello", "▁world"] do not agree on whether a leading space survives — SentencePiece's decode() strips the dummy prefix, ByteLevel does not, BERT's post-processor inserts spaces around subwords. vLLM states the purpose flatly: the offsets exist "to defeat cleanup algorithms in the decode which decide to add a space or not depending on the surrounding ids" (vllm/tokenizers/detokenizer_utils.py:L195-L197). Decode both windows from the same left edge $p$ and whatever cleanup $S$ applies there cancels in the subtraction.

$r$ is the frontier of what has been emitted; $p$ trails it by a fixed number of tokens of context. That constant is five in both engines, and both call it arbitrary:

# 5 is an arbitrary value that should work for all
# tokenizers (bigger = more conservative).
INITIAL_INCREMENTAL_DETOKENIZATION_OFFSET = 5

SGLang's is INIT_INCREMENTAL_DETOKENIZATION_OFFSET = 5 at python/sglang/srt/managers/schedule_batch.py:L144, and the function using it credits the vLLM implementation it was ported from (python/sglang/srt/managers/schedule_batch.py:L1427). SGLang names its prefix offset surr_offset, for "surrounding"; same $p$.

Here is the core, worth reading twice:

    # The prefix text is necessary only to defeat cleanup algorithms in
    # the decode which decide to add a space or not depending on the
    # surrounding ids.
    if tokenizer.is_fast or not tokenizer.get_added_vocab():
        prefix_text = tokenizer.convert_tokens_to_string(
            output_tokens[prefix_offset:read_offset]
        )
        new_text = tokenizer.convert_tokens_to_string(output_tokens[prefix_offset:])
    else:
        # ...
    if len(new_text) <= len(prefix_text) or new_text.endswith("�"):
        # utf-8 char at the end means it's a potential unfinished byte sequence
        # from byte fallback tokenization.
        # If it's in the middle, it's probably a real invalid id generated
        # by the model
        return new_tokens, "", prefix_offset, read_offset

    new_text = new_text[len(prefix_text) :]
    return new_tokens, new_text, read_offset, len(output_tokens)

Read the two return statements as the two states of a latch. The hold return emits the empty string and returns prefix_offset, read_offset unchanged, so next step the same tokens are decoded again with one more token of context. The commit return emits the delta and slides the window one hop: the new $p$ is the old $r$, the new $r$ is the full length. Two conditions hold: the window got no longer, or it ends in U+FFFD.

Note what the hold costs: the window from $p$ grows while the latch is held. With one valid UTF-8 byte per token and no intervening empty or special tokens, an incomplete character needs at most three further bytes. This is not a universal bound in decode steps. A guard rejecting any replacement character anywhere could hold an invalid prefix indefinitely; the displayed guard is new_text.endswith and not "�" in new_text. A replacement character in the middle is treated as a real invalid id and emitted; only a trailing one is treated as incomplete. That distinction is the comment on lines 261–264, and it is load-bearing.

The initial offsets come from the prompt, and only its tail is converted — you do not stringify 8,000 prompt tokens to stream the 8,001st:

    # We do not need to convert the whole prompt to tokens.
    # Offset a little more in case we have special tokens.
    new_tokens = tokenizer.convert_ids_to_tokens(
        prompt_ids[-INITIAL_INCREMENTAL_DETOKENIZATION_OFFSET - 2 :],
        skip_special_tokens=skip_special_tokens,
    )
    read_offset = len(new_tokens)
    prefix_offset = max(read_offset - INITIAL_INCREMENTAL_DETOKENIZATION_OFFSET, 0)

Seven tokens of prompt tail, five of them prefix context. For Llama-3-8B with its 128,256-entry vocabulary that is seven convert_ids_to_tokens lookups per request at admission, not $n$.

A UTF-8 decoder handed F0 9F has two honest options. Replace: substitute U+FFFD and move on, which is what bytes.decode("utf-8", "replace") does and what every naive per-token decode does implicitly. Buffer: hold the incomplete bytes and wait, as Python's codecs.getincrementaldecoder("utf-8") does. For streaming only buffering is defensible, because replacement is lossy and irreversible — once U+FFFD is on the wire, the bytes that would have completed the character have nowhere to go. For one valid byte per token, completing a character needs at most three further bytes; empty, special, or invalid tokens invalidate a general three-step bound.

Both engines buffer by refusing to advance state. vLLM's is the endswith("�") latch above; SGLang adds a refinement, emitting the printable prefix of the held text rather than nothing:

            new_text = read_texts[i][len(surr_texts[i]) :]
            if recv_obj.finished_reasons[i] is None:
                # Streaming. Invariant: sent_offset >= decoded_text_len. The
                # gap (`pending`) is "printable but uncommitted" text emitted
                # in a prior "�" recovery step; we skip it from this step's
                # emission so we don't double-send.
                pending = s.sent_offset - s.decoded_text_len
                if new_text and not new_text.endswith("�"):
                    # Clean text: commit to decoded_text and advance offsets.
                    s.append_decoded_text(new_text)
                    s.surr_offset = s.read_offset
                    s.read_offset = len(s.decode_ids)
                    s.sent_offset = s.decoded_text_len
                    output_strs.append(new_text[pending:] if pending else new_text)
                else:
                    # Incomplete UTF-8: emit the printable prefix only; do not
                    # commit (token offsets stay so the next iteration retries
                    # with more tokens).
                    printable = find_printable_text(new_text)
                    s.sent_offset = s.decoded_text_len + len(printable)
                    output_strs.append(printable[pending:] if pending else printable)
                continue

new_text = read_texts[i][len(surr_texts[i]):] is exactly the $\setminus_{\text{prefix}}$ of the formula. The else branch is the interesting part. SGLang keeps three offsets where vLLM keeps two: the token-space pair (surr_offset, read_offset) plus a character-space sent_offset tracking what went out on the wire. When the latch holds, token offsets freeze but sent_offset may still move, so the next successful step must skip the pending characters it already sent. That asymmetry between "committed" and "sent" is the price of emitting anything during a hold.

What counts as printable is a heuristic borrowed from HuggingFace's TextStreamer:

def find_printable_text(text: str):
    """Returns the longest printable substring of text that contains only entire words."""
    # Borrowed from https://github.com/huggingface/transformers/blob/061580c82c2db1de9139528243e105953793f7a2/src/transformers/generation/streamers.py#L99

    # After the symbol for a new line, we flush the cache.
    if text.endswith("\n"):
        return text
    # If the last token is a CJK character, we print the characters.
    elif len(text) > 0 and _is_chinese_char(ord(text[-1])):
        return text
    # Otherwise if the penultimate token is a CJK character, we print the characters except for the last one.
    elif len(text) > 1 and _is_chinese_char(ord(text[-2])):
        return text[:-1]
    # Otherwise, prints until the last space char (simple heuristic to avoid printing incomplete words,
    # which may change with the subsequent token -- there are probably smarter ways to do this!)
    else:
        return text[: text.rfind(" ") + 1]

The last branch truncates at the final space, so a held chunk with no space emits nothing — the same behaviour as vLLM's latch. The CJK branches exist because Chinese has no spaces and would otherwise never flush. The comment admits this is a heuristic, and it is: a held chunk in a script with neither spaces nor CJK codepoints (Thai, Burmese, Lao) falls through to rfind(" ") and may emit nothing during the incomplete-text hold. Once clean text reaches the commit branch, whitespace is not required; do not infer a full-request no-space stall from this helper alone.

Neither engine detokenises on the GPU or inside the model-forward step. Both put it downstream of a process boundary — different boundaries, different consequences.

vLLM: in the frontend process, on the API server's event loop

OutputProcessor is constructed by AsyncLLM.__init__ at vllm/v1/engine/async_llm.py:L140-L145, in the same process as the FastAPI app; EngineCore is spawned separately on the next line. Detokenisation therefore overlaps GPU work by construction. What it does not overlap is HTTP serving, and vLLM has a knob for that:

                    # Split outputs into chunks of at most
                    # VLLM_V1_OUTPUT_PROC_CHUNK_SIZE, so that we don't block the
                    # event loop for too long.
                    engine_core_outputs = outputs.outputs
                    for start in range(0, num_outputs, chunk_size):
                        end = start + chunk_size
                        outputs_slice = engine_core_outputs[start:end]
                        # 2) Process EngineCoreOutputs.
                        processed_outputs = output_processor.process_outputs(
                            outputs_slice, outputs.timestamp, iteration_stats
                        )

VLLM_V1_OUTPUT_PROC_CHUNK_SIZE defaults to 128 (vllm/envs.py:L1430-L1432), and the loop does await asyncio.sleep(0) between chunks. Above batch 128 one engine step's detokenisation is deliberately split so the event loop can serve HTTP in between. The existence of that flag is the tell that the work shares an event loop.

vLLM has two detokeniser implementations, chosen at request admission:

        assert request.sampling_params is not None

        if tokenizer is None:
            # No tokenizer => skipping detokenization.
            return IncrementalDetokenizer()

        if USE_FAST_DETOKENIZER and isinstance(tokenizer, TokenizersBackend):
            # Fast tokenizer => use tokenizers library DecodeStream.
            return FastIncrementalDetokenizer(tokenizer, request)

        # Fall back to slow python-based incremental detokenization.
        return SlowIncrementalDetokenizer(tokenizer, request)

The fast path does not do the offset dance in Python at all — it hands the problem to the Rust tokenizers crate's DecodeStream, primed with the prompt so the first generated token has left context:

        # Use native prefill to prime the decode stream with prompt tokens.
        # Look up DecodeStream on the module so backend patches (e.g. the
        # fastokens shim that replaces ``tokenizers.decoders.DecodeStream``)
        # are honored regardless of import order.
        self.stream = tokenizers.decoders.DecodeStream(
            ids=request.prompt_token_ids,
            skip_special_tokens=self.skip_special_tokens,
        )

One call per token, all state in Rust. The cost: when that Rust state goes wrong you cannot repair it in place — you throw the stream away and rebuild it (vllm/v1/engine/detokenizer.py:L239-L247), losing the left context and any leading-space decision the discarded prefix would have made.

SGLang: a dedicated process, decoding the batch at once

SGLang runs detokenisation in its own OS process with its own ZMQ sockets, tokenizer instance, and watchdog (python/sglang/srt/managers/detokenizer_manager.py:L516-L533, setproctitle("sglang::detokenizer")). The payoff is visible in the shape of the work: because a whole batch arrives in one BatchTokenIDOutput, SGLang can push the per-row loop into Rust:

        if not getattr(self.tokenizer, "is_fast", False):
            decoded = [
                decode_without_hf_kwargs(self.tokenizer, ids, skip)
                for ids, skip in zip(ids_list, skip_list)
            ]
        else:
            # fast path: all rows share the same (skip, space) flags.
            first_skip, first_space = skip_list[0], space_list[0]
            if all(
                s == first_skip and sp == first_space
                for s, sp in zip(skip_list, space_list)
            ):
                decoded = self.tokenizer.batch_decode(
                    ids_list,
                    skip_special_tokens=first_skip,
                    spaces_between_special_tokens=first_space,
                )

Two batch_decode calls per step for the entire batch — one for the surr_ids windows, one for the read_ids windows (python/sglang/srt/managers/detokenizer_manager.py:L325-L335) — instead of $2B$ Python-level calls. Rows whose flags differ are grouped and decoded per group; rows with an empty span are filtered out and scattered back, because "under high-concurrency streaming this adds up" (python/sglang/srt/managers/detokenizer_manager.py:L238-L241). --disable-tokenizer-batch-decode turns it off to "prevent some detokenization edge cases (e.g., gpt-oss)" (python/sglang/srt/managers/detokenizer_manager.py:L336-L337).

That process is stateful, and its state is capacity-bounded — which produces one of SGLang's more memorable error messages:

            try:
                s = self.decode_status[rid]
            except KeyError:
                raise RuntimeError(
                    f"Decode status not found for request {rid}. "
                    "It may be due to the request being evicted from the decode status due to memory pressure. "
                    "Please increase the maximum number of requests by setting "
                    "the SGLANG_DETOKENIZER_MAX_STATES environment variable to a bigger value than the default value. "
                    f"The current value is {DETOKENIZER_MAX_STATES}. "
                    "For more details, see: https://github.com/sgl-project/sglang/issues/2812"
                )

DETOKENIZER_MAX_STATES defaults to 1 << 16 = 65,536 (python/sglang/srt/managers/detokenizer_manager.py:L57-L61), evicted LRU-style. vLLM has no equivalent: its detokeniser state hangs off the RequestState the frontend already owns.

A stop string is defined over characters and generation happens over tokens, so a stop string can begin inside one token and end inside another. Matching on token ids is therefore not merely inefficient, it is wrong: "</answer>" might be one token in one tokenizer and five in another, and might fuse with a preceding character to become a sixth. Both engines match on decoded text, and vLLM makes the dependency a hard validation error:

        if self.stop and not self.detokenize:
            raise VLLMValidationError(
                "stop strings are only supported when detokenize is True. "
                "Set detokenize=True to use stop."
            )

SGLang's equivalent fires when the tokenizer is absent: "stop={stop_strs!r} is unavailable when skip_tokenizer_init=True (requires tokenizer to decode tokens to text for matching)" (python/sglang/srt/sampling/sampling_params.py:L318-L322).

Matching is the easy half. The hard half is that you may have already streamed part of the stop string before you knew it was one. The fix is a hold-back buffer sized to the worst case:

        # Number of chars to hold back when stop strings are to be excluded
        # from streamed output.
        if self.stop and not self.include_stop_str_in_output:
            self.stop_buffer_length = max(len(s) for s in self.stop) - 1
        else:
            self.stop_buffer_length = 0
        self._last_output_text_offset: int = 0

Why $\max_s |s| - 1$ and not $\max_s |s|$? If the last $|s|$ characters were the stop string you would have detected it and truncated already. The dangerous case is a proper prefix at the tail, and the longest proper prefix has length $|s| - 1$. The hold is released the instant the request finishes:

    def get_next_output_text(self, finished: bool, delta: bool) -> str:
        """If delta is True, only new text since the last call to
        this method is returned"""

        # We return the full output text if the sequence is finished.
        buffer_length = 0 if finished else self.stop_buffer_length
        if not delta:
            if not buffer_length:
                return self.output_text
            return self.output_text[:-buffer_length]

        length = len(self.output_text) - buffer_length
        last_offset = self._last_output_text_offset
        if last_offset < length:
            self._last_output_text_offset = length
            return self.output_text[last_offset:length]
        return ""

Two consequences. stop=["</answer>"] costs eight characters of streaming latency on every chunk for the whole generation — a long stop string is a latency knob you did not know you were turning. And include_stop_str_in_output=True sets stop_buffer_length = 0, so it does not merely change the last chunk, it removes the hold-back entirely. If you were going to keep the stop string anyway, say so.

The matcher itself is careful about two things a naive find would get wrong:

    if not new_char_count or not stop:
        return None

    best_stop_str: str | None = None
    best_stop_index = 0
    best_end = sys.maxsize
    for stop_str in stop:
        stop_string_len = len(stop_str)
        # Avoid searching already-searched text.
        stop_index = output_text.find(stop_str, 1 - new_char_count - stop_string_len)
        if stop_index == -1:
            continue

        # Prefer the stop string that completes earliest in the text.
        end = stop_index + stop_string_len
        if end < best_end:
            best_stop_str = stop_str
            best_stop_index = stop_index
            best_end = end

The negative start index 1 - new_char_count - stop_string_len is the smallest window that can contain a match involving at least one new character: you must look back stop_string_len - 1 characters into already-searched text, because the match may have started there. The earliest-completing tie-break exists for speculative decoding, where several tokens land in one step — the docstring says the winner is chosen "so the result matches appending one token at a time" (vllm/v1/engine/detokenizer.py:L326-L329). Without it, stop-string semantics would depend on the draft model's acceptance rate.

SGLang splits the same job across two processes

SGLang does stop-string matching in the scheduler process, not the detokenizer, because the scheduler is what decides to stop generating. It decodes a token-space tail window per request per step:

    def tail_str(self, new_accepted_len: int = 1) -> str:
        # Check stop strings and stop regex patterns together
        if (
            len(self.sampling_params.stop_strs) == 0
            and len(self.sampling_params.stop_regex_strs) == 0
        ):
            return ""

        tail_len = self._stop_match_tail_len(new_accepted_len)
        return self.tokenizer.decode(self.output_ids[-tail_len:])

Note the unit difference. vLLM's buffer is in characters; SGLang's window is in tokens, sized from stop_str_max_len, which normalize() computes by encoding each stop string and taking the max token length (python/sglang/srt/sampling/sampling_params.py:L221-L228). Both bound the same quantity; the token-space one is looser.

The streaming hold-back is separate, and it is suppression rather than truncation. OutputStreamer.accept declines to emit a chunk whose tail could still become a stop string:

                if should_output:
                    # check_match_stop_str_prefix if  tail_str's suffix match stop_str prefix
                    should_output &= not req.check_match_stop_str_prefix()

And check_match_stop_str_prefix does the explicit proper-prefix scan that vLLM's fixed-length buffer implies: for i in range(1, min_len + 1): if tail_str[-i:] == stop_str[:i]: return True (python/sglang/srt/managers/schedule_batch.py:L1488-L1492). Precision costs a second tokenizer.decode per request per streaming step.

Final truncation happens in the detokenizer process, which knows the matched string but not its character offset:

        # Trim stop str.
        if isinstance(matched, str) and isinstance(output, str):
            pos = output.find(matched)
            if pos == -1:
                return output
            end = pos + len(matched)
            return output[:end] if no_stop_trim else output[:pos]

no_stop_trim is SGLang's include_stop_str_in_output, spelled inversely and defaulting to False (python/sglang/srt/sampling/sampling_params.py:L78). Note output.find(matched) — the first occurrence, not the one that triggered the stop. The comment three lines above is honest about the remaining gap: # TODO(lmzheng): handle the case where multiple stop strs are hit (python/sglang/srt/managers/detokenizer_manager.py:L187). If your stop string legitimately appears earlier in the output and you are not trimming, the two engines will disagree.

Everything above is Python and Rust on a CPU core. It is not free, and unlike the forward pass its cost is linear in batch size while the decode step's cost is nearly flat below the roofline ridge.

Let $B$ be the number of sequences detokenised per step, $c$ the wall cost of one Python-to-tokenizer round trip on a short window, and $T_{\text{step}}$ the decode step time. For Llama-3-8B in bf16 on an H100 SXM, $T_{\text{step}} = 4.48$ ms at batch 1 (weight-streaming bound, book constant), and because arithmetic intensity at batch 256 is still below the ridge $I^* = 295$, the step at batch 256 is still roughly weight-bound — call it 4.5–6 ms. Detokenisation cost is $N_{\text{calls}} \cdot c$ where:

Take $c = 10\ \mu\text{s}$ as a working assumption for a Python attribute lookup plus a PyO3 boundary crossing plus a short Rust decode. This is an assumption, not a measurement — measure it on your box before you act on it (the Hands-on section below tells you how). Under it:

Three readings. (1) A slow tokenizer at batch 256 costs more host time than the GPU step costs GPU time — hence SGLang's blunt "Using a slow tokenizer. This might cause a significant slowdown" (python/sglang/srt/utils/hf_transformers/tokenizer.py:L432-L435). (2) Neither engine detokenises inside the step loop, so below $B^*$ the work hides behind GPU time. The failure mode is not "the step got slower" but "detokenisation stopped keeping up and the output queue grew" — rising ITL against a flat GPU utilisation graph. (3) The one piece that is on the critical path is SGLang's scheduler-side tail_str: at $B = 256$ with stop strings and streaming, up to 512 decodes × 10 µs = 5.12 ms of scheduler Python per step, comparable to the step itself. Stop strings are not free in SGLang — though the no-stop-strings case is exactly zero.

The mitigation follows the arithmetic. vLLM's stream_interval (default 1, vllm/config/scheduler.py:L153-L157) and SGLang's identically-named server arg (default 1, python/sglang/srt/server_args.py:L1480-L1483) amortise per-chunk overhead across $k$ tokens: "a larger value (e.g., 10) reduces host overhead and may increase throughput by batching multiple tokens before sending". Raising it can amortise network emission over $k$ tokens, but does not necessarily eliminate internal per-step detokenization; observed ITL granularity changes with frame formation — see §1.2.

Encoding is easier than decoding but has sharper edges.

Fast vs slow. "Fast" is the Rust tokenizers backend; "slow" is a pure-Python PreTrainedTokenizer. SGLang exposes the choice as --tokenizer-mode and refuses the contradictory combination:

    if tokenizer_mode == "slow":
        if kwargs.get("use_fast", False):
            raise ValueError("Cannot use the fast tokenizer in slow tokenizer mode.")
        kwargs["use_fast"] = False
    elif tokenizer_mode == "auto":
        # Transformers v5 AutoTokenizer ignores use_fast (always fast), but
        # some code paths pass kwargs to non-AutoTokenizer loaders where
        # use_fast still matters. Set explicitly for those fallback paths.
        if "use_fast" not in kwargs:
            kwargs["use_fast"] = True

vLLM's choice is implicit: it loads via AutoTokenizer.from_pretrained and wraps the result in a caching proxy, because "transformers will recompute multiple tokenizer properties each time they are called, leading to a significant slowdown" (vllm/tokenizers/hf.py:L107-L111). The proxy memoises all_special_ids, all_special_tokens, get_vocab(), __len__ and is_fast — every property the detokeniser touches per token. Write your own wrapper and skip this, and you pay a vocabulary rebuild per decoded token.

add_special_tokens, and the double-BOS bug. vLLM's tokenize endpoints default it opposite ways, and say why:

    add_special_tokens: bool = Field(
        default=False,
        description=(
            "If true, special tokens (e.g. BOS) will be added to the prompt "
            "on top of what is added by the chat template. "
            "For most models, the chat template takes care of adding the "
            "special tokens so this should be set to false (as is the "
            "default)."
        ),
    )

For the completion endpoint the same field defaults to True (vllm/entrypoints/serve/tokenize/protocol.py:L28-L33). That is the whole double-tokenisation hazard in two defaults. A chat template renders <|begin_of_text|><|start_header_id|>user... as text; encoding that text with add_special_tokens=True prepends a second BOS id. The model sees two, and the output degrades in a way no error message describes. Tokenize once for the template and once for the engine, and exactly one of those must add specials.

The inverse trap is a tokenizer that ignores the flag: # tiktoken's encode adds no special tokens (add_special_tokens is ignored) (python/sglang/srt/tokenizer/tiktoken_tokenizer.py:L132). Passing False there is a no-op that happens to be correct; passing True is a no-op that is silently wrong.

The leading space. SentencePiece-family tokenizers encode a word boundary as a literal marker character (▁, U+2581) inside the vocabulary piece, and decode() strips the first one. vLLM undoes that when it needs per-token strings:

def _get_leading_space_marker(tokenizer: TokenizerLike) -> str | None:
    """Read the space marker from the tokenizer's pre_tokenizer config.

    Only Metaspace pre_tokenizers (used by SentencePiece-based models like
    Llama, Mistral, T5) have a replacement character whose leading instance
    gets stripped by decode(). ByteLevel (GPT-2), BertPreTokenizer (BERT),
    and others do not have this issue.

    Returns the marker character, or None if decode() is safe for single
    tokens.
    """

It reads the marker out of the serialised pre-tokenizer JSON, handling both a bare Metaspace and a Sequence containing one, and caches it on the tokenizer. This is the mechanism behind "why did my logprobs table show Hello where the text says  Hello": per-token strings and windowed decodes disagree about the space by construction, and only the windowed one is the truth.

Batching the encode side. Tokenising an 8k-token prompt is milliseconds of single-threaded Rust on the frontend's event loop. SGLang has an opt-in micro-batcher for it — a queue and a timeout, the same shape as continuous batching:

                # Check if there are more items immediately available in the queue
                # If queue is empty, process single item immediately without timeout
                if self._queue.empty():
                    # No other requests waiting, process immediately
                    pass
                else:
                    # There might be more requests, wait for dynamic batching opportunity
                    start_time = asyncio.get_running_loop().time()

                    # Collect more requests up to max_batch_size or batch_wait_timeout_s
                    while len(prompts) < self.max_batch_size:
                        elapsed = asyncio.get_running_loop().time() - start_time
                        if elapsed >= self.batch_wait_timeout_s:
                            break

                        remaining_time = self.batch_wait_timeout_s - elapsed
                        try:
                            prompt, kwargs, result_future = await asyncio.wait_for(
                                self._queue.get(), remaining_time
                            )

Three properties worth copying. It adds no latency when idle — the self._queue.empty() fast path skips the timeout, so a lone request pays nothing. It runs the blocking call on a single-thread ThreadPoolExecutor so the asyncio loop stays responsive (python/sglang/srt/managers/async_dynamic_batch_tokenizer.py:L43-L44). And it degrades loudly: requests with differing kwargs cannot share one tokenizer(prompts, **kwargs) call, so it logs "Dynamic batching disabled for batch of N requests due to differing kwargs" (python/sglang/srt/managers/async_dynamic_batch_tokenizer.py:L143-L147). Defaults: off, batch size 32, timeout 0.002 s (python/sglang/srt/server_args.py:L3466-L3480). Two milliseconds of TTFT is a real cost; buy it only when the tokenizer is the bottleneck.

A request with stop=["END"], include_stop_str_in_output=False, streaming, on a fast tokenizer. The engine has just sampled one token id.

1. EngineCore (separate process) puts the id into EngineCoreOutput.new_token_ids and ZMQs it to the frontend.
2. AsyncLLM.output_handler (vllm/v1/engine/async_llm.py:L685-L691) wakes on engine_core.get_output_async() and slices the batch into runs of 128.
3. OutputProcessor.process_outputs (vllm/v1/engine/output_processor.py:L603) loops the slice — its docstring warns this is "the only function that should loop over EngineCoreOutputs".
4. Step 2 of that loop detokenises and folds stop strings into the finish reason in one shot:
   vllm/v1/engine/output_processor.py:L676-L682 vLLM

                   # 2) Detokenize the token ids into text and perform stop checks.
                   stop_string = req_state.detokenizer.update(
                       new_token_ids, finish_reason == FinishReason.STOP
                   )
                   if stop_string:
                       finish_reason = FinishReason.STOP
                       stop_reason = stop_string

5. Inside BaseIncrementalDetokenizer.update (vllm/v1/engine/detokenizer.py:L96-L143): if the engine stopped on a stop token and we exclude it, that id is popped before detokenising and pushed back onto token_ids after — output_token_ids stays complete while output_text omits it. Then output_text += decode_next(id) per id, then check_stop_strings over the newly added characters only.
6. decode_next on the fast path is one DecodeStream.step (vllm/v1/engine/detokenizer.py:L211-L222), wrapped in _protected_step, which swallows OverflowError/TypeError for issue #21951 and rebuilds the stream on "Invalid prefix encountered" for issue #17448.
7. On a match, output_text = output_text[:truncate_to], where truncate_to is best_stop_index (exclude) or best_end (include).
8. _new_completion_output calls get_next_output_text(finished, delta) (vllm/v1/engine/output_processor.py:L407), applying the hold-back and advancing _last_output_text_offset.
9. The RequestOutput goes onto the per-request asyncio queue. If the detokeniser stopped a request the engine still thinks is running, its id joins reqs_to_abort and the handler sends abort_requests_async back over ZMQ (vllm/v1/engine/output_processor.py:L716-L722). Stop-string detection is a frontend decision propagated backwards into the engine.

SGLang's path has one more hop and one more tokenizer: Req.update_finish_state in the scheduler decodes a tail window and sets finished_reason = FINISH_MATCHED_STR(matched=stop_str) (python/sglang/srt/managers/schedule_batch.py:L1552-L1560); OutputStreamer.accept gathers init_incremental_detokenize() windows into a BatchTokenIDOutput (python/sglang/srt/managers/scheduler_components/output_streamer.py:L412-L423); the DetokenizerManager decodes and trims; the TokenizerManager formats SSE. No backwards abort — the scheduler decided.

The rule that resolves most of these: get the token ids. Use --skip-tokenizer-init (both engines support it, both then reject stop strings) or ask for logprobs, and diff against what your client tokenised. Text-level debugging cannot distinguish "the model produced the wrong tokens" from "the detokeniser rendered the right tokens wrongly", and those have different fixes.

First, measure the constant $c$ that the cost section assumed, on your own machine and tokenizer. No GPU needed — that is the point of the chapter.

python3 - <<'PY'
import time, tokenizers
from transformers import AutoTokenizer
tok = AutoTokenizer.from_pretrained("meta-llama/Meta-Llama-3-8B-Instruct")
ids = tok("The quick brown fox jumps over the lazy dog. " * 20).input_ids
stream = tokenizers.decoders.DecodeStream(ids=ids[:64], skip_special_tokens=True)
t0 = time.perf_counter()
for i in ids[64:]:
    stream.step(tok.backend_tokenizer, i)
dt = time.perf_counter() - t0
n = len(ids) - 64
print(f"{dt/n*1e6:.2f} us per DecodeStream.step over {n} tokens")
PY

Multiply by your batch size and compare against 4.48 ms. Then reproduce the split-character case end to end:

# vLLM: stream a prompt that forces multi-byte output and count empty deltas
vllm serve meta-llama/Meta-Llama-3-8B-Instruct --port 8000
curl -N localhost:8000/v1/completions -H 'Content-Type: application/json' -d '{
  "model":"meta-llama/Meta-Llama-3-8B-Instruct",
  "prompt":"Repeat exactly, nothing else: 我很感谢你的热情",
  "max_tokens":40,"stream":true}' | grep -c '"text":""'

# same request with a long stop string; watch the deltas start late
curl -N localhost:8000/v1/completions -H 'Content-Type: application/json' -d '{
  "model":"meta-llama/Meta-Llama-3-8B-Instruct","prompt":"Count to twenty.",
  "max_tokens":60,"stream":true,"stop":["\n\nHuman:"]}'

# SGLang: same shape, then flip the batch-decode path off and diff the output
python -m sglang.launch_server --model-path meta-llama/Meta-Llama-3-8B-Instruct \
  --port 30000 --disable-tokenizer-batch-decode

The empty-delta count in the first command is the hold latch. It can be nonzero when tokens split multibyte characters; complete-character tokens need no hold. Exclude empty role, terminal, and usage frames before interpreting empty content deltas.

• vLLM PR #9625 — the V3-Tekken incomplete-UTF-8 fix. Its two fixtures (Burmese, and URGENCY plus a chilli emoji) are still the regression tests at tests/tokenizers_/test_detokenize.py:L104-L110.
• vLLM issue #17448 — non-monotonic invalid UTF-8 corrupting DecodeStream state; the reason _protected_step exists. Issue #21951 is the still-undiagnosed OverflowError in the same function.
• vLLM PR #22014 — min_tokens interacting with stop-string checking; cited inline at vllm/v1/engine/detokenizer.py:L121. It is why stop_check_offset is recomputed inside the per-token loop.
• SGLang issue #2812 — the detokeniser state table filling up, and where SGLANG_DETOKENIZER_MAX_STATES came from.
• huggingface/tokenizers — DecodeStream in tokenizers/src/tokenizer/mod.rs. vLLM pins the exact commit and line of the error string it matches on, which is the correct way to depend on someone else's message.
• HuggingFace TextStreamer in transformers/generation/streamers.py — the origin of find_printable_text, and worth reading for how much simpler the single-sequence case is.
• §9.1 for chat templates and the API surface that produces the ids; §9.3 for the SSE plumbing that carries the deltas; §6.5 for the token-level grammar mask and the retokenisation hazard in jump-forward.