# Structured decoding and fairness · Inference engines

<!-- https://learn-kernels.com/chapters/inference-engines/structured-decoding-and-fairness -->

Callers increasingly want output that is not just plausible text but valid JSON, a function call, or a string in some grammar. **Constrained decoding** (Enforcing strict formal language constraints, such as a grammar or schema, during generation, typically by restricting which tokens the model is allowed to emit at each step.) methods enforce such formal language constraints during generation. Doing this naively is costly in two ways: Beurer-Kellner et al. show that many existing methods not only add performance overhead at generation time but also significantly impair task accuracy, because the constraint is defined over text while the model emits subword tokens, and misaligning the two distorts what the model is allowed to say. Their DOMINO algorithm enforces constraints in a fully subword-aligned fashion, and by leaning on pre-computation and speculative decoding it runs with virtually no overhead, in some cases almost 2 times faster than unconstrained decoding.

> Figure. Constrained decoding as a token mask. One decode step while generating JSON, with the output so far ending in a key and a colon. The constraint restricts which tokens the model is allowed to emit: candidates that would make the output invalid, here a bare word and a stray closing bracket, are masked out, and the next token is sampled only from the set the mask lets through.Illustrative numbers

The other trust problem an engine has to solve is between clients rather than within one request. First-come-first-serve with a per-client request rate limit is how most services protect themselves, but Sheng et al. call that notion of fairness rudimentary: it leaves capacity idle when a heavy client is throttled against an underutilized server, and a request cap treats a 2,000 token request the same as a 200 token one. Their fix is **fair queueing** (A scheduling discipline in which each of n clients sharing a resource is guaranteed at least a 1/n share of it, and any share a client does not use is redistributed to clients with more demand.) applied at the token level, and LLM serving breaks the classic algorithms in specific ways: a request’s output length is unknown when it is scheduled, input tokens cost less to process than output tokens, and the server’s effective capacity in tokens per second changes with the mix of sequence lengths in the batch. Their Virtual Token Counter tracks the service each client has received, counted in tokens as they are actually processed, and admits requests from the least-served client first on top of continuous batching. The scheduler is work-conserving, and they prove a tight upper bound of 2 times on the service difference between two backlogged clients.

Source

Subword misalignment and the DOMINO figures from [Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation](https://proceedings.mlr.press/v235/beurer-kellner24a.html) (Beurer-Kellner et al., 2024). Token-level fairness and the VTC bound from [Fairness in Serving Large Language Models](https://arxiv.org/html/2401.00588) (Sheng et al., 2024). More in [Structured decoding](https://learn-kernels.com/chapters/reading#structured-decoding) in the reading list.