Grammar-Constrained Token Masking
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 tokenallowed: list of allowed token indices for the current state (non-empty)transitions: dict mapping(state, token)to the next statecurrent_state: the current FSM statesampled_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
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium