Structured and Long-Context Inference

Two demands sit on top of a serving engine that the earlier chapters did not settle. One caller needs output that is valid JSON or that matches a grammar. Another brings a context far longer than the cache can comfortably hold. Both are handled at inference time, without retraining the model. Structured output masks logits against a finite-state machine (FSM), a finite-state machine that tracks which grammar state the partial output is in, then makes that mask cheap through a precomputed index and jump-forward over forced spans. Long-context serving decides which keys and values survive, from sliding windows, attention sink behavior where early tokens keep attracting attention, and heavy-hitter eviction to newer query-aware policies. In both cases, the serving engine bends a fixed model by constraining the decode loop.

Two Ways to Constrain a Fixed Model

The decoder of Chapter 33 emits one token at a time by sampling from a distribution over the whole vocabulary. Two callers stress that loop in opposite directions, and neither is willing to retrain the model.

The first caller wants structure. A program that calls a model to extract fields, choose a tool, or fill a form needs the output to parse: valid JSON against a schema, a value from a fixed enum, a SQL statement that a parser accepts. An unconstrained model produces text that is usually well-formed and occasionally not, and the occasional failure is the expensive one, because the program downstream cannot recover from a missing brace or an invented field name. Prompting and retrying narrows the failure rate but never closes it, and each retry pays a full generation. The problem is to make malformed output impossible rather than improbable, without retraining the model and without paying a large per-token tax.

The second caller wants length. A request may carry a long document, a multi-hour transcript, or an agent history that grows without bound, and the key-value cache of Chapter 32 grows linearly with that length. Past some point the cache no longer fits, or fits only by capping the batch size so low that throughput collapses. Worse, a model trained at one context length often degrades when asked to attend over a much longer one at inference time, even before memory runs out. The training-time fixes for that, extending the positional encoding through RoPE scaling and YaRN, live in Chapter 8. The inference-time question is different: given a fixed model and a context too long to keep whole, which keys and values do you keep, and how do you keep generation coherent when you drop the rest.

The two problems are not obviously related, yet both are answered by intervening in the decode loop rather than retraining: one masks the distribution before sampling, the other prunes the cache that attention reads. They share this chapter because they are the two ways a serving engine adapts a fixed model to a caller's constraint. Each track below is a sequence in which every step removes a cost the previous one paid.

Track one: constrained decoding, the grammar-checked decode loop

The mask, and why it is not a one-liner

The core idea for structure is small. At each decode step the model produces a logit, the raw pre-softmax score, for every token in the vocabulary. If you know which tokens could legally come next under the target format, you set the logits of all the others to negative infinity before the softmax, so they have zero probability and cannot be sampled. Generation then walks only the legal continuations, and the output is guaranteed to be a member of the formal language. Nothing about the model changes; the intervention is a mask applied between the logits and the sampler.

The work is in knowing the legal set at every step. Express the target format as a formal language: a regular expression for a phone number or an enum, a context-free grammar for JSON or for a programming language. Compile that into an automaton, a finite-state machine for a regular language or a pushdown automaton for a context-free one. The automaton has a current state; from that state, only some tokens keep the string within the language. The mask at each step is the set of vocabulary tokens whose first character, or whose whole spelling, the automaton accepts from its current state. After a token is sampled, advance the automaton and repeat.

Try changing allowed to a different set of legal tokens and watch the disallowed probabilities collapse to exactly zero while the legal ones renormalize.

import numpy as np
vocab = ['{', '}', '"', 'name', 'age', ':', ',', 'true', 'hello', '42']
logits = np.array([2.1, 0.3, 3.0, 1.2, 1.0, 0.5, 0.4, 0.8, 2.5, 1.1])
# FSM is just after '{' : the only legal next token is an opening quote.
allowed = {'"'}
mask = np.array([t in allowed for t in vocab])
masked = np.where(mask, logits, -np.inf)
def softmax(x):
    x = x - np.max(x[np.isfinite(x)])
    e = np.exp(np.where(np.isfinite(x), x, -np.inf))
    return e / e.sum()
p_free, p_masked = softmax(logits), softmax(masked)
for t, a, b in zip(vocab, p_free, p_masked):
    print(f'{t:>6}  unconstrained={a:.3f}  masked={b:.3f}')
print('masked mass on legal tokens:', round(p_masked[mask].sum(), 3))

The catch that makes this an engineering problem rather than a one-liner is the mismatch between the automaton, which is defined over characters, and the model, which emits tokens that are multi-character pieces of the byte stream from Chapter 7. A token may span several automaton transitions, and only some tokens are valid from a given state. Computing the allowed-token set naively means walking the automaton over the spelling of every one of tens of thousands of vocabulary entries, at every step, which would dominate the cost of decoding. So the first implementation of this idea was correct but slow, a per-step vocabulary scan against a hand-written automaton, and the history of the track is a chain of removing that cost.

Removing the per-step scan: a precomputed index

The design that makes constrained decoding practical is to precompute the relationship between automaton states and allowed tokens once, before generation, rather than at every step. Willard and Louf's formulation, the basis of the Outlines library, builds an index over the vocabulary keyed by automaton state: for each state of the finite-state machine, the set of tokens that are legal from it, and the state each of those tokens leads to (Willard and Louf 2023). With that index in hand, the per-step work is a dictionary lookup by current state, not a scan over the vocabulary, which turns the per-token overhead from proportional to vocabulary size into roughly constant. The index is built from the regular expression and the tokenizer once and reused for every request that shares the format. This 2023 leap is what made guided generation cheap enough to use by default.

Removing the forced tokens: jump-forward over a compressed machine

Even with a constant-time mask, a second cost remains, because large stretches of a constrained output are forced. Inside {"name": ", the next several characters are not a choice, they are the only continuation the grammar allows until the value begins. A token-by-token loop still runs a full forward pass for each of those forced characters, paying decode cost to generate text that was never in doubt. The compressed finite-state machine, introduced in SGLang, collapses runs of single-transition edges in the automaton into one edge, so the runtime can recognize a forced span and emit it directly (Yin et al. 2024). This is jump-forward decoding: when the machine has only one path forward, write those tokens into the sequence without a model call, then resume sampling where the format branches. The model is consulted only where the output is genuinely undetermined.

Figure 35.3 contrasts the two regimes. The forced span between two branch points is one edge in the compressed machine, written in a single step, while the model runs only at the points where the grammar leaves a real choice.

Removing the grammar overhead: hiding behind the forward pass

The precomputed index and jump-forward both target regular languages. The remaining step generalizes the mask from regular to context-free languages while keeping the per-step cost near zero. A context-free grammar needs a stack, not just a state, so the allowed-token set depends on the current stack, which seems to defeat precomputation. XGrammar's insight is to split the vocabulary into tokens whose legality does not depend on the stack, which can be checked once and cached, and the smaller set of context-dependent tokens that must be checked against the live stack at runtime (Dong et al. 2024). With a persistent stack structure and by overlapping the grammar computation with the model's forward pass on the accelerator, the engine drives a full grammar constraint at close to the speed of unconstrained decoding. The arc of this track, taken whole, pushes the constraint from a per-step vocabulary scan down to a precomputed table, then to skipped tokens, then to a grammar engine that hides behind the forward pass.

Track two: pruning the cache

Attention is concentrated, so most keys are dead weight

The long-context half rests on a different observation. Attention does not weight all past tokens equally. For most heads, the probability mass concentrates on a small subset of positions: the most recent tokens, plus a few specific earlier ones. If most keys and values receive almost no attention, keeping all of them is paying full memory for tokens that barely contribute. The design move is to keep only the keys and values that matter and let attention run over that reduced set, trading a controlled approximation for a cache that no longer grows without bound. The first cut at this rule is blunt, and each step that follows files down a little more of that bluntness.

The blunt rule and the dropped-prefix failure

The simplest keep rule is a sliding window: retain only the last $w$ tokens and drop everything older. This bounds the cache to a constant size and matches how local-attention models already behave. But a plain sliding window fails in a specific and revealing way. When the earliest tokens fall out of the window, perplexity, a measure of how well the model predicts held-out text where lower is better, spikes and generation degrades sharply, far more than dropping unimportant tokens should cost.

The explanation is the attention sink, the central finding of StreamingLLM (Xiao et al. 2024). The softmax that turns attention scores into weights forces those weights to sum to one, so a head always spends a full unit of attention across the tokens it can see, even when none of them is worth attending to. When a head has no informative place to attend, it dumps that unavoidable surplus onto the first few tokens of the sequence, which therefore receive large scores regardless of their content. These initial tokens act as a sink. Drop them, as a naive sliding window does, and every head loses the place it was parking its spare attention, and the distribution destabilizes. The fix is to keep a handful of initial tokens permanently, the sinks, alongside the sliding window of recent tokens. With four sink tokens plus a recent window, a model trained at a fixed length can stream over millions of tokens with stable perplexity, no fine-tuning required (Xiao et al. 2024).

Letting content decide: eviction by attention history

Sinks plus a window is a fixed rule that ignores content; the middle of a long document may hold the one fact the answer needs. Content-aware compression keeps the cache small while letting which tokens survive depend on the input. H2O reframed the cache as an eviction problem and keeps the heavy hitters, the tokens that have accumulated the most attention so far, retained alongside the most recent tokens, with the rest evicted (Zhang et al. 2023). SnapKV makes a sharper observation for the prompt: each head consistently attends to particular prompt positions, and those positions can be identified from the attention in a small observation window at the end of the prompt, then the rest of the prompt's cache compressed away before generation even starts (Li et al. 2024). Both keep a budget-sized cache whose contents are chosen by the model's own attention rather than by position alone.

The two arcs are dated steps that line up step for step: window attention and recompute baselines bounded memory but broke on the dropped prefix; H2O in 2023 kept heavy hitters by accumulated attention (Zhang et al. 2023); StreamingLLM, also in 2023, explained why naive windows fail and fixed it with the attention sink (Xiao et al. 2024); SnapKV in 2024 pushed compression into the prompt itself using the end-of-prompt observation window (Li et al. 2024). The frontier continues toward query-aware and learned eviction, deciding what to keep based on what the current generation is actually attending to. The sharpest version of that move stops evicting altogether: Quest keeps the full cache, summarizes each page of keys by its per-channel extremes, and fetches only the top-$k$ pages relevant to the current query (Tang et al. 2024). Selection changes the failure mode, because which tokens matter shifts with every query in multi-turn use: an evicted token is gone, while an unselected one is merely cold and can be fetched next step, or parked in the tiered cache of Chapter 32 until a query wants it. A connected development is designing the sink in at training time: models can be trained with a dedicated sink token so the attention parking is explicit rather than emergent, which makes the inference-time keep rule cleaner. The same is happening to sparsity itself: natively trainable sparse attention, the NSA line that DeepSeek shipped in V3.2 with a matching cut in long-context API prices, trains the model to attend over a selected subset, which turns this chapter's approximation into an architecture guarantee (Yuan et al. 2025). That training-time choice belongs to Chapter 8; this chapter inherits its consequence.

The two lineages, side by side

Figure 35.6 sets the two tracks beside each other, and both obey the same logic: every step pays off a cost the one before it left behind. On the structured side the path runs from a per-step vocabulary scan to a precomputed table, on to skipped forced tokens, and finally to a grammar engine that hides behind the forward pass. The long-context side begins with a position-only window that breaks on the dropped prefix, adds a few permanent sinks, and ends by letting attention decide what to keep.

Where the two tracks converge

The two tracks meet at the same place: each bends a fixed model by accepting an approximation, and the open question is what the approximation costs. For the structured track the cost is mostly bounded and known; for the long-context track it is genuinely unsettled.

What each move costs

Each technique buys its benefit at a stated cost.

• Constraint versus fluency. Masking guarantees the output parses, but it can force the model down a path its own distribution disfavors, lowering quality on the content inside the structure. A constraint that is too tight, an over-specified schema, can push the model into locally legal but globally awkward text, because the mask removes the token the model wanted without removing the reason it wanted it. The constraint should be as loose as correctness allows.
• Index build versus reuse. The precomputed index pays an up-front cost to compile the regular expression or grammar against the tokenizer (Willard and Louf 2023). For a format used across many requests this amortizes to nothing, but for a one-off schema generated per request the build can rival the generation it saves. Engines cache compiled grammars by format for exactly this reason.
• Jump-forward correctness. Emitting forced tokens without a model call is only safe where the automaton truly has a single continuation, and tokenizer boundaries complicate that: the jumped text must re-tokenize the same way the model would have produced it, or the cache and the output diverge (Yin et al. 2024). The speedup is real but the boundary handling is where the bugs live.
• Compression budget versus recall. A smaller cache budget saves more memory and fits more concurrent requests, but raises the chance that an evicted token was the one the answer needed. The budget is the dial between throughput and the recall of long-range facts, and the safe setting is workload-specific.

• Sink count and window size. Too few sink tokens and the parking insight fails; too large a window and the memory saving shrinks. The small published defaults, a handful of sinks and a window in the thousands, are starting points, not constants (Xiao et al. 2024).

Putting it in the engine

A constrained decoder is a mask hooked into the sampler. The engine compiles the format into an automaton and its index once, then at each step looks up the allowed-token set for the current state, sets every other logit to negative infinity, samples, and advances the automaton. In vLLM this is a logits processor invoked inside the sampling path, backed by a structured-output backend such as XGrammar or Outlines that owns the grammar and the index. With jump-forward enabled, the runtime checks the compressed machine before each model call: if the current state has a single forced continuation, it appends those tokens directly and only invokes the model when the format branches. The grammar engine runs alongside the forward pass so the mask is ready when the logits are (Dong et al. 2024).

A compressing long-context engine is the memory manager of Chapter 32 with a keep policy on top. For sink-plus-window streaming, the engine pins the first few token blocks as sinks, keeps a rolling window of recent blocks, and frees the rest, so the cache stays at constant size as generation continues. For attention-based eviction, the engine tracks an attention score per cached token, accumulated for heavy hitters or measured in the end-of-prompt observation window for prompt compression, and evicts the lowest-scoring tokens down to the budget, freeing their blocks back to the pool. The keep policy is a small layer; paging is what makes it cheap, because evicting a token is freeing a block, not compacting a buffer.

Two operational realities are worth naming. First, a constraint is only as correct as its grammar: a schema that permits a value the parser downstream rejects moves the failure rather than removing it, so the grammar and the consumer must agree on the exact format. Second, compression quality is workload-shaped in a way aggregate metrics hide, so the real test is the downstream task, retrieval accuracy or answer correctness at the chosen budget, not perplexity, which can stay flat while the specific evicted fact is exactly the one a query needed.

These two mechanisms split the chapter between efficiency and trust. Constrained decoding buys trust, a guarantee the output parses, at a small efficiency cost that the index and jump-forward nearly erase. Long-context compression buys efficiency, a bounded cache, at a trust cost: the risk of evicting the fact a later query needed, which query-aware policies try to bound.

Further reading