Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

CODING CHALLENGE · N°56

Constrained Decoding (Logit Masking)

Easy AIStructured OutputDecoding

How do you force an LLM to emit only valid JSON, a legal move, or a token your grammar allows? You mask the logits: set every disallowed token to −∞ before picking, so the model can only choose from the permitted set. It’s the backbone of structured-output and grammar-constrained decoding. Solve it in Python or TypeScript, with hidden tests.

The problem

Given the model’s logits (one score per token id) and a list of allowed token ids (the tokens a grammar or schema permits at this step), pick the next token by masking: only the allowed tokens are eligible, and you choose the one with the highest logit. Break ties by the smaller token id. Implement constrained_argmax(logits, allowed): return the chosen token id.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? open the hints under the problem, or Reveal solution is one click away.

YOUR TASK

Implement constrained_argmax(logits, allowed): scan the allowed ids in increasing order, tracking the best one; update only on a strictly larger logit so ties keep the smaller id. Return the best id.

CPython · WebAssembly
Examples and constraints 3 examples
EXAMPLE 1
Input logits = [1.0, 5.0, 2.0, 4.0], allowed = [0, 2, 3]
Output 3
token 1 has the highest logit but is not allowed; among {0,2,3} token 3 (logit 4) wins
EXAMPLE 2
Input logits = [9, 1, 1], allowed = [2, 1]
Output 1
tokens 1 and 2 tie at logit 1 → pick the smaller id, 1
EXAMPLE 3
Input logits = [-1.0, 5.0, -3.0], allowed = [0, 2]
Output 0
edge case: every allowed logit is negative; −1.0 beats −3.0, so do not start the best score at 0
CONSTRAINTS
  • Only tokens in allowed may be chosen — this is equivalent to setting every other logit to −∞ before taking the argmax.
  • Among allowed tokens, choose the one with the maximum logit; on a tie, choose the smallest token id.
  • allowed is non-empty and its ids are valid indices into logits.
Hints 4 ideas
HINTS — 4 IDEAS
  1. You only ever consider tokens in allowed — the rest are effectively masked to −∞.
  2. Iterate the allowed ids in ascending order and keep the one with the highest logit so far.
  3. Update the best only when you find a strictly larger logit; that way an equal logit does not displace the smaller id already held.
  4. Return the surviving best id — the token constrained decoding would emit.
Approach, complexity & discussion — open after you solve

Start from brute force

The obvious approach follows the definition literally: copy logits, set every id not in allowed to −∞, then take the argmax over the whole vector, keeping the first maximum so ties go to the smaller id. It is correct because a −∞ logit loses every comparison. It costs O(V) time and O(V) space for the masked copy, where V is the vocabulary size, plus O(a) to build a set of the a allowed ids. The waste: every decoding step touches all V logits, often tens of thousands, even when the grammar allows only a handful of tokens, such as a digit or a closing brace.

The approach

Masking to −∞ and then taking the argmax is the same as taking the argmax over the allowed ids alone, so the mask never needs to exist. The reference walks sorted(allowed) in increasing id order and keeps best, replacing it only when logits[idx] > logits[best]. The strict comparison is the tie-break: an equal logit later in the scan always has a larger id, so it cannot displace the smaller id already held. Starting from best = None rather than a score of 0 matters too, because every allowed logit can be negative.

The invariant after each step: best is the smallest id carrying the maximum logit among the ids seen so far. The sort costs O(a log a); a single unsorted pass that also accepts an equal logit with a smaller id gives the same answer in O(a).

idlogit id 02.0 id 17.0 → −∞ id 23.5 id 33.5 id 46.0 → −∞ id 51.0 maskedchosentiemasked scan sorted(allowed) = [0, 2, 3, 5] 0: first, best 0 2: 3.5 > 2, best 2 3: 3.5 > 3.5? no 5: 1.0 > 3.5? no return 2 ids 1 and 4 (7.0, 6.0) are never read
The walkthrough input. The two tokens the model likes most are outside the allowed set, so they behave as −∞ without a mask ever being built: the scan reads only the four allowed ids, in ascending order, and the strict > in step 3 is what keeps the tie at the smaller id.

Walk through an example

With logits = [2.0, 7.0, 3.5, 3.5, 6.0, 1.0] and allowed = [5, 3, 2, 0], the reference scans sorted(allowed) = [0, 2, 3, 5], never looks at the two highest logits (ids 1 and 4), and resolves the 3.5 tie between ids 2 and 3 to 2.

stepidxlogits[idx]comparisonbest
102.0best is None, so take it0
223.53.5 > 2.02
333.53.5 > 3.5 is false, so the tie keeps 22
451.01.0 > 3.5 is false2

Complexity

The reference costs O(a log a) time for the sort and O(a) space for the sorted copy, where a = len(allowed); a one-pass tie-break makes the time O(a). Masking the whole vocabulary costs O(V) time and O(V) space at every decoding step, however few tokens are allowed, because it builds and scans a full-size copy.

Edge cases to test

  • Every allowed logit is negative: constrained_argmax([-1.0, 5.0, -3.0], [0, 2]) returns 0. A solution that seeds the best score with 0 never updates and returns its sentinel.
  • A tie: constrained_argmax([9, 1, 1], [2, 1]) returns 1. Scanning allowed in the given order with > returns 2, and so does a sorted scan with >=.
  • One allowed id: constrained_argmax([5, 9, 2], [0]) returns 0, even though token 1 holds the top logit. The grammar has already decided.
  • Duplicate ids in allowed are harmless: constrained_argmax([1, 2, 3], [2, 2, 0]) returns 2.
  • A NaN logit compares false against everything, so it is never picked over a number but never displaced once held: constrained_argmax([float("nan"), 1.0], [0, 1]) returns 0. Reject NaN logits before decoding.

Common mistakes

  • Taking the argmax over all logits and only then checking whether it is allowed. In the first example the top token, 1, is not allowed, and there is no second choice to fall back to.
  • Scanning allowed in the order given instead of ascending id order, so a tie goes to whichever id is listed first.
  • Using >= instead of >, which hands every tie to the larger id.
  • Seeding the best score with 0 instead of the first allowed logit, which breaks when every allowed logit is negative.

Follow-ups an interviewer asks next

How does this extend to generating a whole JSON object?
Call it once per decoding step with a fresh allowed set. A grammar or regex compiled to a finite-state machine tracks the position in the structure; after each emitted token the state advances and yields the next step’s allowed ids. This function is the masking step. The hard part is computing those sets quickly when tokens span several characters.
What changes if you sample instead of taking the argmax?
Set disallowed logits to −∞, apply softmax (with temperature) to the rest, and sample. Since exp(−∞) = 0, masked tokens get probability exactly 0 and the allowed ones renormalize among themselves: for the first example, about 0.844 for token 3, 0.114 for token 2 and 0.042 for token 0. Top-k or top-p then filters the masked distribution.
What if the grammar leaves no allowed token?
That is a dead end: the constraint and the text so far are inconsistent, often because the grammar has a bug or a token boundary split a required string. This function assumes allowed is non-empty; given an empty list the reference returns None (TypeScript: -1). A production decoder should detect the empty set and fail loudly or backtrack.

Where this shows up

Constrained decoding is how you guarantee structured output — valid JSON, a value from an enum, a well-formed SQL query — instead of hoping the model complies. It underpins grammar-constrained generation and the reliable, schema-valid arguments that make tool-calling trustworthy.

The hard engineering is not this function but producing allowed fast enough to call it on every token. A grammar is written over characters, while the vocabulary holds multi-character tokens, so a token is allowed only if every character in it keeps the grammar in a valid state. Checking that by trying all V tokens at every step is far too slow. The approach described by Willard and Louf in 2023, and used by the Outlines library, compiles a regex or JSON schema to a finite-state machine and precomputes, for each state, the set of tokens that are legal there, so a decoding step becomes a table lookup followed by this masking step. llama.cpp offers the same capability through its GBNF grammar format.

Masking guarantees the syntax, not the quality. In the walkthrough, the model put most of its probability on the two masked tokens: under a plain softmax of the six logits, the four allowed ids together hold only about 4.8% of the mass. The mask forces a choice from that small remainder, and when that happens at many steps the output is valid but can drift away from what the model would naturally say. Two practical consequences follow. Log how much probability the mask removed at each step, because a consistently large number means the prompt and the schema disagree. And give the model room in the schema, such as a free-text reasoning field before the constrained answer field, instead of forcing every token from the first one.

The same masking shows up outside structured output: blocking banned tokens, restricting a classifier-style prompt to a fixed set of label tokens, and enforcing legal moves when a model plays a game all reduce to “argmax or sample over an allowed subset”.

Check yourself

What does constrained_argmax([0.5, 3.0, 3.0, -2.0, 3.0], [4, 2, 3]) return?

2. Among the allowed ids, 2 and 4 tie at 3.0 and id 3 holds −2.0; the scan visits [2, 3, 4], takes 2 first, and the strict comparison stops 4 from replacing it. Id 1 also holds 3.0 but is not allowed.

A variant scans allowed in the order given, without sorting. What does it return on the same input, and why?

4. It visits 4 first, and the tied 2 cannot displace it under >, so the tie goes to whichever id happens to be listed first. The tie rule only works when the scan order is ascending id order.

You sample instead of taking the argmax on the walkthrough input at T = 1. What probability do ids 1, 2 and 3 get?

Id 1 gets exactly 0, because its logit is masked to −∞. Ids 2 and 3 each get about 0.434: the softmax renormalizes over the allowed logits 2.0, 3.5, 3.5 and 1.0, giving about 0.097, 0.434, 0.434 and 0.036.

The scan is O(a) instead of O(V). Does that make each decoding step meaningfully faster?

Only the selection step. The model’s output layer has already produced all V logits, which costs far more than scanning them once, so the forward pass dominates either way. The real savings in constrained decoding come from computing the allowed set quickly, not from the argmax.

Reference solution

Reference solution — Python
def constrained_argmax(logits, allowed):
    best = None
    for idx in sorted(allowed):              # ascending -> ties keep smaller id
        if best is None or logits[idx] > logits[best]:
            best = idx                        # strictly larger logit wins
    return best


print(constrained_argmax([1.0, 5.0, 2.0, 4.0], [0, 2, 3]))   # -> 3
print(constrained_argmax([9, 1, 1], [2, 1]))                 # -> 1
Reference solution — TypeScript
function constrainedArgmax(logits: number[], allowed: number[]): number {
  let best = -1;
  for (const idx of [...allowed].sort((a, b) => a - b)) {  // ascending -> ties smaller id
    if (best === -1 || logits[idx] > logits[best]) best = idx;  // strictly larger wins
  }
  return best;
}

console.log(constrainedArgmax([1.0, 5.0, 2.0, 4.0], [0, 2, 3]));  // -> 3
console.log(constrainedArgmax([9, 1, 1], [2, 1]));               // -> 1

Questions about Constrained Decoding (Logit Masking)

Why set disallowed logits to negative infinity instead of zero?

Logits are unnormalized log-probabilities, and zero is an ordinary value, not a minimum. A disallowed token with logit 0 would still beat every allowed token with a negative logit, and after softmax it would keep a real share of the probability. Negative infinity works for both decoding styles: it loses every comparison in an argmax, and exp of negative infinity is exactly 0, so after softmax the token has probability 0 and the allowed tokens renormalize among themselves. Zeroing probabilities after softmax and renormalizing gives the same distribution; masking the logits does it in one step.

How does constrained decoding guarantee valid JSON?

At every step it computes which tokens keep the text valid from the current position in a grammar or schema, masks every other token, and then picks or samples from what is left. Because an invalid token can never be chosen, the finished output cannot break the grammar, as long as generation runs to completion. This challenge implements the single-step pick. A full system adds the state machine that produces each allowed set, which is the hard part, because grammars are written over characters while models emit tokens that often span several characters.

Why break ties toward the smaller token id?

A tie needs some rule. Without one, the result depends on the order the allowed ids happen to arrive in, which makes runs hard to reproduce and tests flaky. Smaller id is simple and deterministic. Exact ties between float logits are uncommon in real models, but they occur with low-precision logits and in tests that use round numbers. The reference implements the rule by scanning ids in ascending order and replacing the best only on a strictly larger logit, so an equal logit found later can never displace the smaller id.

Does constrained decoding slow generation down?

The masking itself is cheap: one pass over the logits, small next to the model forward pass that produced them. The real cost is working out the allowed set at each step, because a grammar is defined over characters while the model emits multi-character tokens, so the decoder must know which tokens keep the text on a valid path. Implementations precompile the grammar against the vocabulary so this lookup is fast at generation time. The other cost is quality: forcing a token the model ranked low conditions everything after it, so prompting for the format still helps.

Finished this one? 0 / 76 Challenges done
NextBeam Search Decoder Next on the “Inference & decoding” ladder · rung 3 of 5

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Challenges