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 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.

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 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.