Grammar-Constrained Token Masking

MediumML Coding

Problem statement

When decoding from a language model under a grammar or finite-state machine (FSM), only a subset of tokens is valid at each step. Implement a single constrained decoding step as grammar_constrained_step(logits, allowed, transitions, current_state, sampled_token). You are given a raw logits vector, the set of allowed token indices for the current FSM state, an FSM transition table, the current state, and the token that was ultimately sampled.

Your function must produce a probability distribution over the vocabulary where every disallowed token has probability 0 and the allowed tokens carry a proper normalized distribution derived from their logits. It must also report the FSM state after consuming the sampled token. If the (state, token) pair has no defined transition, the FSM remains in the current state.

Inputs:

  • logits: list of floats, one per vocabulary token
  • allowed: list of allowed token indices for the current state (non-empty)
  • transitions: dict mapping (state, token) to the next state
  • current_state: the current FSM state
  • sampled_token: index of the token that was sampled

Return a tuple (probs, next_state) where probs is a Python list of floats.

Example

Input:

logits=[1.0, 2.0, 3.0], allowed=[0, 2], transitions={(0, 0): 1, (0, 2): 2}, current_state=0, sampled_token=2

Output:

([0.119203, 0.0, 0.880797], 2)

Reasoning: Token 1 is not allowed so its probability becomes 0. The remaining logits for tokens 0 and 2 are normalized into a valid distribution. The sampled token 2 drives the FSM from state 0 to state 2.

Show hint

How can you make a token's probability exactly zero while still using an ordinary softmax?

Relevant roles: LLM Engineer, AI Engineer, Agentic AI Engineer and Gen AI Engineer.

Related free problems