Finite State Machine (FSM)

An FSM tracks the exact position within a formal grammar during generation. Unlike probabilistic prompting, the FSM maintains a current state that represents what has been generated so far. This state determines the set of valid next tokens, physically preventing the model from producing syntactically invalid sequences. For example, after generating an opening bracket [, the FSM transitions to a state where only array elements or a closing bracket ] are permissible.

At each decoding step, the FSM computes a valid token mask by evaluating all possible tokens against the current state's transition rules. Tokens that would violate the schema have their logit probabilities set to negative infinity before the softmax operation. This is fundamentally different from post-hoc validation because it guarantees validity at the physical sampling layer, not just the application layer. The model's probability distribution is surgically altered to zero out invalid continuations.

FSM-guided generation provides a mathematical guarantee that the output will conform to a predefined schema or grammar. This eliminates entire categories of errors:

• Unclosed brackets or braces in JSON
• Invalid data types in required fields
• Missing required keys in structured objects
• Malformed string escapes in complex outputs The guarantee is absolute because the model is physically incapable of selecting tokens that would break the grammar.

Modern FSM implementations like the Outlines library use index-based generation rather than full grammar parsing at each step. The FSM pre-computes a compact index mapping each state to its valid token set. During generation, the current state index is used for an O(1) lookup of the valid token mask. This optimization reduces the computational overhead of guided generation to near-negligible levels, making it suitable for production latency budgets.

FSM-guided generation supports multiple grammar definition formats:

• GBNF Grammar: Used by llama.cpp for defining syntactical rules in a Backus-Naur Form variant
• JSON Schema: Automatically compiled into an FSM that enforces structural constraints
• Context-Free Grammars (CFG): Recursive production rules that define all valid strings in a formal language
• Regular Expressions: Compiled into deterministic finite automata for pattern-constrained generation The FSM compiler converts these declarative schemas into executable state machines.

FSM-guided generation introduces minimal latency overhead while providing absolute format guarantees:

• Token mask computation: Typically < 1ms per step with pre-compiled indexes
• Memory overhead: Compact state representations require minimal additional VRAM
• Throughput impact: Negligible compared to unconstrained generation when using optimized FSM compilers
• Batching compatibility: Valid token masks can be computed independently for each sequence in a batch The deterministic nature also enables caching of state transitions for repeated schema patterns.

FSMs are the core mechanism for guaranteeing syntactically valid JSON output. The FSM tracks the current parsing context (e.g., inside a string, expecting a comma, or closing an object) and masks any token that would violate the JSON specification.

• State Transitions: Moving from Key to Value to Comma states based on generated tokens.
• Contextual Awareness: The FSM knows if an array is open, preventing invalid primitive tokens.
• Library Integration: Frameworks like Outlines and llama.cpp compile JSON Schema directly into an FSM for guided decoding.

In function calling, the model must output a specific structure (e.g., {"name": "...", "arguments": {...}}). An FSM enforces this exact sequence, preventing malformed tool calls that would crash an agentic loop.

• Token-Level Control: The FSM forces the opening {, the "name" key, and the function name string.
• Argument Integrity: It ensures the arguments value is a valid JSON object, not a hallucinated string.
• Stop Sequence Enforcement: The FSM can mandate a specific closing } to signal the end of the tool call.

For domain-specific languages or formal grammars (e.g., GBNF), an FSM compiled from a Context-Free Grammar (CFG) restricts generation to only valid syntactical paths. This is critical for generating executable code or mathematical proofs.

• Lexer State Tracking: The FSM mirrors a lexer, ensuring keywords and identifiers are correctly formed.
• Recursive Rule Expansion: It manages the stack for recursive grammar rules, preventing infinite loops.
• AST Guarantee: The output is guaranteed to parse into a valid Abstract Syntax Tree.

The ReAct (Reasoning + Acting) paradigm requires a strict interleaving of Thought, Action, and Observation tokens. An FSM governs this sequential protocol, preventing the model from generating an Action before a Thought or skipping the Observation step.

• Phase Locking: The FSM transitions through a fixed cycle: Thought -> Action -> Observation.
• Token Forcing: It forces the generation of the next required keyword (e.g., "Action:") at the correct state.
• Loop Termination: The FSM defines valid terminal states (e.g., Final Answer) to end the agent's execution.

In task-oriented dialogue, an FSM tracks which slots in a semantic frame have been filled. It constrains the model's output to only ask for missing required information, ensuring a deterministic, efficient information-gathering flow.

• State as Frame: Each state represents the current fill-status of slots (e.g., date, time, location).
• Conditional Prompting: The FSM transitions to a prompt state that specifically asks for the next missing slot.
• Confirmation State: It enforces a final confirmation step before executing a transaction.

For systems generating interleaved text and structured actions (like image generation commands), an FSM coordinates the output sequence. It ensures a text description is completed before switching to a state that generates a structured API call for an image model.

• Mode Switching: States define whether the next token is free-form text or part of a structured command.
• Resource Integrity: The FSM validates that generated URLs or file paths conform to a required pattern.
• Sequence Guarantee: It enforces a strict order: Caption -> Image_Generation_Command -> Metadata_Block.