Horizonless Lookahead for Language Model Control under Nested Constraints

Constrained generation asks a language model to produce text that follows a rule, such as a JSON schema. At every step it needs the lookahead, the probability that the string can still be completed inside the rule, which is intractable for the language model itself. Current methods approximate the language model by a hidden Markov model and the rule by a finite automaton, and store the lookahead in a table indexed by the remaining length. But the model decides for itself when to end, and rules such as JSON need a stack, which a finite automaton tracks only with exponentially many states. We compute the horizonless lookahead, summed over every length, under a constraint with a stack. In verification this is the probability that a probabilistic pushdown system ends in acceptance, in general hard to compute. A language model, which can end the string at every step, makes it cheap. One summary per level of brackets adds up every way to complete it, at every length, and depends only on the symbol that opened the level. Once the summaries are computed, each token costs about $10\%$ more than unconstrained decoding, independent of the string length. The method covers every deterministic context-free language and, under a length cap, gives a mask that guarantees the output ends. It matches the exact conditional on a nested Dyck language. On JSON and RNA tasks it guarantees the constraint and raises content scores, putting an 8B model ahead of every published model on DeepJSONEval Format.