Structured and Long-Context Inference

Two serving-time interventions change the decoder without changing model weights. Structured generation restricts which next tokens are admissible. Long-context policies restrict which previously computed key-value states attention retains or reads. They share the inference loop, but they provide different guarantees. A grammar can guarantee membership in an implemented formal language. Cache eviction and sparse reads approximate full attention and must be evaluated against the task.

This distinction matters in production. Parseable JSON can still contain the wrong value. A bounded cache can keep a stream fluent while forgetting a fact that appeared thousands of tokens earlier. Neither mechanism should be sold as a general correctness guarantee.

Constrained decoding changes the token distribution

Consider constrained decoding, the grammar-checked decode loop. Here $p(v\mid x_{<t})$ be the model probability of vocabulary token $v$ after prefix $x_{<t}$. Let $s_t$ be the current parser configuration and $A(s_t)$ the tokens that preserve the possibility of a valid completion. Grammar-constrained sampling uses

$$p_G(v\mid x_{<t},s_t)= \frac{p(v\mid x_{<t})\,\mathbf 1[v\in A(s_t)]} {\sum_{u\in A(s_t)}p(u\mid x_{<t})}.$$

Here $\mathbf 1[v\in A(s_t)]$ is one for an allowed token and zero otherwise. The denominator renormalizes the remaining probability mass. After sampling $v$, the parser consumes it and advances from $s_t$ to $s_{t+1}$. An end-of-sequence token is legal only when the parser is in an accepting configuration. If the allowed set is empty, the engine has reached a bug, unsupported constraint, or incompatible prefix; it must fail explicitly rather than sample from the original distribution.

The definition of $A(s_t)$ is stronger than "the next character is legal." A token belongs to that set only if it keeps at least one accepting completion reachable. Otherwise a locally valid token can lead to a dead end from which no complete document can be formed. On accepted termination, a correct implementation guarantees that the emitted byte string belongs to the implemented language. A maximum-token stop, cancellation, or engine failure can still leave an incomplete document.

The following runnable shows the renormalization itself. It deliberately uses a small allowed set rather than pretending to implement a full JSON parser.

from math import exp

def constrained_softmax(logits, allowed):
    if not allowed:
        raise ValueError("empty allowed set")
    peak = max(logits[i] for i in allowed)
    weights = [exp(logits[i] - peak) if i in allowed else 0.0
               for i in range(len(logits))]
    total = sum(weights)
    return [weight / total for weight in weights]

vocab = ["{", "}", '"', "name", "age", ":", ",", "true", "hello", "42"]
logits = [2.1, 0.3, 3.0, 1.2, 1.0, 0.5, 0.4, 0.8, 2.5, 1.1]
allowed = {2}  # Just after "{", this toy state accepts only an opening quote.
probabilities = constrained_softmax(logits, allowed)

for token, probability in zip(vocab, probabilities):
    print(f"{token:>6}  {probability:.3f}")
print("legal mass:", round(sum(probabilities[i] for i in allowed), 3))
print("illegal mass:", round(sum(probabilities[i] for i in range(len(vocab))
                                 if i not in allowed), 3))

The parser runs on token bytes, not token labels

A model emits tokenizer IDs, while a grammar is defined over an alphabet such as bytes or Unicode code points. The runtime must compose the two. For each candidate token, it obtains the bytes produced by the tokenizer and asks whether the parser can consume the token's complete byte string. One token may cross several grammar transitions. A byte sequence for one character may also be split across tokens. Special tokens require explicit rules because they may not decode to ordinary text at all.

Regular languages can be recognized by an finite-state machine (FSM), a machine that tracks which grammar state the partial output is in. A context-free grammar also needs a parser stack to represent nested structures. JSON-like objects, for example, need unbounded nesting in the general case. Calling every constraint an FSM hides that difference and leads to incorrect caching assumptions.

The generation loop therefore has five states that must agree:

What the guarantee includes

Syntactic validity is not value correctness. A grammar may ensure that output parses as JSON and that a field has an integer spelling. It cannot establish that the integer was copied from the source, that a tool call is authorized, or that a SQL statement is safe to execute. Those are semantic and policy checks.

JSON Schema adds another boundary. Engines commonly implement a supported subset of JSON Schema by translating it into a grammar or parser. Keywords for cross-field relationships, remote references, numeric ranges, or string semantics may be unsupported or enforced after generation. The advertised guarantee is therefore the intersection of the requested schema, the backend's grammar coverage, its tokenizer integration, and its termination behavior. Benchmarks of structured-generation engines find meaningful differences across schema coverage, compilation behavior, and output quality (Geng et al. 2025).

The consumer validates the finished object again. It should reject extra bytes, unsupported schema features, incorrect field values, unsafe operations, and truncated output. Constrained decoding removes one class of failure; it does not replace the application validator or authorization layer.

Hard token masking also changes the model's sequence distribution. The local renormalization above does not, in general, sample from the original model conditioned on eventual grammar membership because it ignores how much valid probability mass lies beyond each prefix. Grammar-Aligned Decoding formalizes this distinction and reports cases where ordinary grammar-constrained decoding produces valid but lower-quality outputs (Park et al. 2024). The effect is workload- and model-dependent, so compare content accuracy as well as parse rate.

Making grammar execution affordable

The direct implementation tests every vocabulary token against the live parser at every step. That repeats tokenizer and parser work tens of thousands of times per generated token. Practical engines move as much of that work as possible out of the decode loop.

For a regular constraint, a runtime can precompute transitions from each automaton state through every vocabulary token. Willard and Louf describe a vocabulary index that makes the state-to-allowed-token lookup inexpensive (Willard and Louf 2023). The compile cache key must include the canonical grammar, tokenizer revision, special-token policy, byte encoding, and backend version. Reusing an index with a different tokenizer can admit the wrong token IDs.

Precomputation does not make the whole operation constant-cost. Mask application still touches the selected logits or a vocabulary-sized mask; device transfer, synchronization, heterogeneous grammars within a batch, and parser-stack updates can remain visible. XGrammar reduces context-free grammar overhead by prechecking context-independent tokens, checking a smaller context-dependent set against persistent parser stacks, and overlapping CPU grammar work with accelerator execution. Its near-zero end-to-end overhead is an empirical result for evaluated engines and workloads, not a universal bound (Dong et al. 2025).

Forced spans use an extend pass

A grammar often has deterministic spans such as punctuation and field names. SGLang compresses singular paths and jumps to the next branch (Zheng et al. 2024). This avoids one autoregressive decode iteration per forced token, but it does not make those tokens free. The forced span must still enter the model state so later tokens attend to it. The runtime retokenizes the combined suffix at the boundary, reconciles any changed tokenization, and processes the deterministic tokens together in a prefill-style pass that extends the KV cache.

This path needs the same reserve, commit, and rollback discipline as other cache updates. If boundary retokenization changes an already cached suffix, the runtime must invalidate and recompute the affected KV entries. A failed extend must not leave the parser ahead of model state. Jump-forward performance depends on deterministic-span length, retokenization cost, extend-kernel efficiency, and scheduler load.

Long context has four separate limits

"Supports 128K" does not answer every long-context question. A deployment must separate four limits:

1. The model's supported context length. Position encoding, training distribution, and architecture determine whether the model behaves sensibly at a given logical position. Evicting KV entries does not extend this learned capability.
2. KV capacity. Resident keys and values grow with retained tokens, layers, heads, batch, and element width. This can cap admitted concurrency.
3. Attention traffic. Even when the full cache fits, decode attention may read an increasingly large state for every new query. Chapter 34's IO model applies directly.
4. Information retention. A policy that drops or skips state may remove the evidence a later query needs. Stable perplexity or fluent generation is not proof of long-range recall.

Here $\kappa$ is the logical KV bytes per retained token from Chapter 34. Full attention retains approximately

$$M_{\mathrm{full}}(T)=T\kappa$$

bytes for a sequence of $T$ tokens, before allocator and metadata overhead. Here $T$ is the logical sequence length. A sink-plus-window policy with $s$ initial tokens and a recent window of $w$ tokens has budget $K=s+w$ and, after warm-up, retains at most

$$M_{\mathrm{window}}\lesssim K\kappa+M_{\mathrm{policy}}.$$

Here $M_{\mathrm{policy}}$ covers block tables, scores, page summaries, and padding. The formula describes resident decode state. A method that compresses only after processing a full prompt may still pay prompt-prefill peak memory and compute for all $T$ tokens.

Three policy families, three failure modes

Long-context methods are easier to compare by what they store and read than by publication date.

The first three reduce resident KV by deleting entries. Eviction is irreversible unless the system stores enough source state to recompute them. Query-aware page selection instead keeps the full cache and reduces attention traffic by reading a subset. Selected pages can change at the next query, so an unselected page remains recoverable even though the current attention result is still approximate.

Sinks and a recent window

Some evaluated transformer families exhibit attention sink behavior where early tokens keep attracting attention even when they are not semantically important. StreamingLLM reports that preserving a few initial KV entries along with a recent window avoids the sharp degradation observed when a naive window drops the prefix. In its evaluated Llama-2, MPT, Falcon, and Pythia settings, the policy supported stable streaming language-model evaluation for very long sequences without fine-tuning (Xiao et al. 2024).

The paper proposes softmax normalization as part of the explanation: when a head has no strongly relevant token, initial positions can absorb attention mass. This is an observed model behavior, not a theorem that every head follows. Sink count and window size are model- and workload-specific. The policy also does not remember evicted content. It supports continuing generation, not unlimited recall.

Attention-history eviction and prompt compression

H2O retains recent tokens and tokens with large accumulated attention scores in the models and tasks it evaluates (Zhang et al. 2023). The score is historical. A token with little attention so far may still become essential to a later query, so the heavy-hitter budget must be tested against future-use patterns rather than only average language-model loss.

SnapKV is a different operation. It observes attention near the end of the prompt, selects important prompt positions separately by head, and compresses prompt KV before generation (Li et al. 2024). This is prompt compression, not a continually updated heavy-hitter cache. It can reduce decode-state memory and reads, but it may not reduce prefill peak cost because the observation is made after the prompt has been processed.

Query-aware page selection

Quest keeps the full cache and stores per-channel key extrema for each page. For a new query, those summaries provide an upper-bound score used to choose the top-$k$ pages to load for attention (Tang et al. 2024). Storage remains close to full KV plus summaries, while device-memory traffic and attention work can fall. This changes the failure from permanent deletion to query-specific omission, but it does not guarantee that every relevant page is selected.

Native sparse-attention architectures make token selection part of training. They are an important alternative, but they do not belong to the fixed-model inference policies above. Retrofitting an eviction or selection rule onto a dense-attention checkpoint and training a model to use sparse attention are different interventions.

Cache state must remain internally consistent

A keep or read policy operates on more than key and value arrays. Each retained entry needs its logical position, layer and head identity, numeric format, and ownership state. Position metadata must remain consistent with the model's rotary or other positional encoding. Renumbering retained tokens as if gaps had never existed changes attention geometry unless the method explicitly requires and validates that transformation.

Paged allocation helps when a policy keeps or evicts whole blocks. It does not make arbitrary per-token or per-head eviction free. A physical block may contain both retained and discarded slots, may be shared by prefix-cached requests, and may have outstanding readers. Fine-grained policies need block-aligned choices, gather indirection, compaction, or specialized sparse kernels. Reference counts, reserve/commit/rollback, cancellation, and prefix-cache identity from Chapter 32 still apply.

The policy metadata also consumes memory and bandwidth. H2O-style scores, SnapKV per-head indices, and Quest page summaries should be included in peak and resident measurements. A policy that stores less KV but launches slow gather kernels can lose latency even while capacity improves.

Verify the complete service path

Structured generation and long-context policies need different correctness tests, followed by one shared load test.

For structured generation:

1. Run the official parser or schema validator over adversarial and real schemas. Include nested objects, Unicode, token pieces that span several transitions, special tokens, empty allowed set, and maximum-length stops.
2. Report schema-valid rate, grammar coverage, field-level correctness, and downstream rejection separately. A valid object with wrong fields is not a successful extraction or tool call.
3. Measure grammar compilation latency, compiled-cache hit rate and memory, mask preparation and application time, allowed-set size, and time per output token. Test mixed grammars in one batch.
4. Compare jump-forward output and KV state with ordinary token-by-token extension across tokenizer boundaries, cancellation, and allocation failure.

For long-context inference:

1. Compare with a full-KV baseline inside the model's supported context length. Sweep prompt length, generation length, cache budget, and page-selection budget.
2. Report retrieval accuracy by evidence position, multi-hop answer quality, long-generation quality, and adversarial cases where a low-attention fact is needed later. Perplexity alone is insufficient. Comparative studies find that cache-compression rankings vary across tasks and models (Yuan et al. 2024).
3. Measure prompt peak memory, resident and peak KV memory, metadata, KV bytes read per step, time to first token, time per output token, throughput, goodput, and latency tails at matched load.
4. Exercise shared prefixes, block reference counts, cancellation, position boundaries, quantized KV, unsupported kernels, and rollback after failed compaction or selection.

Payoff and boundary

Constrained decoding can make malformed syntax unreachable when grammar, tokenizer, and termination agree. It cannot make the values true. Long-context policies can bound resident state or reduce attention reads. They cannot make discarded evidence available. Production readiness means stating that boundary, then measuring the guarantee, task quality, and service result together.

Further reading