$\texttt{SEM-CTRL}$: Semantically Controlled Decoding

Researchers introduce SEM-CTRL, a new approach that ensures Large Language Models produce syntactically and semantically correct outputs without requiring fine-tuning. The system uses token-level Monte Carlo Tree Search guided by Answer Set Grammars to enforce context-sensitive constraints, allowing smaller pre-trained LLMs to outperform larger models on tasks like reasoning and planning.

• →SEM-CTRL enables any off-the-shelf LLM to guarantee valid outputs without fine-tuning by using constrained decoding.
• →The approach integrates token-level Monte Carlo Tree Search with Answer Set Grammars to enforce syntactic and semantic constraints.
• →Small pre-trained LLMs with SEM-CTRL can outperform larger models and state-of-the-art reasoning systems like o4-mini.
• →The system was tested on diverse tasks including grammar synthesis, combinatorial reasoning, JSON parsing, and planning.
• →Answer Set Grammars allow incorporation of background knowledge to represent task-specific semantics beyond basic grammar rules.