$\texttt{SEM-CTRL}$: Semantically Controlled Decoding
Authors: Mohammad Albinhassan
Pranava Madhyastha
Alessandra Russo
Venue: Accepted by TMLR ()

Abstract: Ensuring both syntactic and semantic correctness in Large Language Model (LLM) outputs remains a significant challenge, despite being critical for real-world deployment. In this paper, we introduce $\texttt{SEM-CTRL}$, a unified approach that allows for enforcing rich context-sensitive constraints, and task and instance specific semantics directly on the LLM decoder. Our approach integrates token-level MCTS which is guided by specific syntactic and semantic constraints. The constraints over desired outputs are expressed using Answer Set Grammars, which is a logic-based formalism that generalizes context sensitive grammars while incorporating background knowledge to represent task-specific semantics. We show that our approach helps guarantee valid completions for any off-the-shelf LLM without the need for fine-tuning. We evaluate $\texttt{SEM-CTRL}$ on a range of tasks, including synthetic grammar synthesis, combinatorial reasoning, JSON parsing, and planning. Our experimental results demonstrate that $\texttt{SEM-CTRL}$ allows even small pre-trained LLMs to efficiently outperform larger variants and state-of-the-art reasoning models (e.g., $\text{\textit{o4-mini}}$) while simultaneously guaranteeing semantic validity.

Published in Transactions on Machine Learning Research (03/2026)
SEM-CTRL: Semantically Controlled Decoding
Mohammad Albinhassan
mallhilkassem2222mpprirall.....
Department of Computing Imperial College London
Pranava Madhyastha
Deportment of Computer Science City, University of London
Alessandra Russo
a.russo @imperial.ac... ac.uu
Department of Computing Imperial College London
Reviewed on OpenReview: https: httpe:///penrreveeu openreview........ net/ per/formm? id= ICURKNOSSN
Abstract
Ensuring both syntactic and semantic correctness in Large Language Model (LLM) outputs remains a significant challenge, despite being critical for real-world deployment. In this paper, we introduce SEM-CTRL, unified approach that allows for enforcing rich context- sensitive constraints, and task and instance specific semantics directly the LLM decoder. Our approach integrates token-level MCTS which is guided by specific syntactic and mantic constraints. The constraints over desired outputs are expressed using Answer Set Grammars, which is logic-based formalism that generalizes context sensitive grammars while incorporating background knowledge to represent task-specific semantics. We show that our approach helps guarantee valid completions for any off-the-shelf LLM without the need for fine-tuning. We evaluate SEM-CTRL on range of tasks, including synthetic grammar syuthesis, combinatorial reasoning, JSON parsing, and planning. Our experimental results demonstrate that SEM-CTRL allows even small pro-trained LLMs to efficiently outperform larger variants and stale-of-the-ar reasoning models (e.g., 04-mini) while simultaneously guaranteeing semantic validity.
1 Introduction
Controlled generation aims at designing better decoding methodologies for Large Language Models (LLMs), which guarantecs output validity according formal specifications (Welleck et al. 2024 The challenge of controlled generation has far seen many appealing approaches that can be broadly categorized as: (i) syntactic control such as constraining based on regular or Context-Free Grammars (CFGs) (Geng et al. 2023 Beurer-Kellner et al. 2024 inter alia); (ii) control based on domain-specific semantic constraints (e.g..
Scholak et al. 2021 Pocsia et al. 2022); and (fii) search-guided reasoning improving control (c.g., Zhang
et al.
2023b
Hao et al. 2023
Nevertheless, the effectiveness of existing approaches remains limited. Syntactic control is insufficient for real-world tasks demanding context-sensitive correctness based token's relative position in sequence (Scholak et al. 2021). Domain-specifie solutions lack generalizability across tasks (Poesia et al. 2022 Roy
ct al.) (023). Critically, both focus exclusively on ensuring the LLM's generations conform to some specifica- tion ( (validity) without explicitly encoding the notion of solving the lask correctly (correctness). Search-based methods, while designed to capture correctness, suffer from inefficient exploration and premature pruning of valid solutions preciscly bocause they do not explicitly capture validity (c.g., ZZhang et al. 2023b Wan et al.) (2024). These empirical findings suggest fundamental limitations in current frameworks for handling both syntactic and semantic constraints simultaneously, as well for expressing correctness.

---

Published in Transactions on Machine Learning Research (03/2026)
We conjecture that the most plausible reason for these limitations is that existing approaches either focus solely on local constrainis or lack semantic guidance during search. In this paper, we introduce new approach, called Semantically Controlled Decoding (SEM-CTRL), that unifies semantic constraints with guided search to enable robust, controlled generation. SEM-CTRL exploits Answer Set Grammars (ASGs) to specify both syntactic structures and semantic rules within a single formalism, and combines this with token-level Monto-Carle Tree-Search (MCTS), guided by domain-specific rewards. SEM-CTRL distinguishes itself from prior work through: (1) directly encoding Context-Sensitivg Grammars (CSGs) to capture validity, versus simpler CFGs (e.g.. Geng et al.) 2023) ad-hoc constraint checks (e.g.. Scholak et al. 20210: (2) using ASGs to capture semantic meanings; and (3) employing MCTS for global correctness optimization.
S
Initial State
S + Seq Seq Act Seg end Act Pickup
pickup
stack
Act
Pickup pickup Block (handempty.)
Goal State
Block r end EOS
blue
red
<B08>
Pickup
# Background: end geal. ontable(red)
x
pickup
Block
<EOS>
<B0S>
b
r
(a) Planning Task
(b) Grammar & Rules
(c) Parse Tree
(d) MCTS Search
Figure Overview of SEM-CTRL showing: (a) Blocksworld planning task with initial and goal states. (b) ASG fragment showing syntax and semantic rules. Curly braces {--.) denote parse tree semantic constraints PR. with domain rules and state encoding V under "Background", (c) Partial parse tree of valid solution sequence. (d) MCTS scarch over the token space, with correct (green / V), suboptimal (orange / -2), and invalid paths (red x). States are simplified to show the generated token at each node instead of the entire sequence. Blue arrow shows MCTS MCTS-parse parse tree correspondence; each node maps to a valid parse tree as constraints are computed per step.
As an illustration, consider the Blocksworld planning task presented Figure 1 (a), where an agent must rearrange series of colored boxes into a target configuration. We distinguish between two critical dimensions: validity and correctness. Validity requires satisfying formal constraints. Traditional syntactic controls (c.g.. CFGs) fail here as they cannot express context-dependent rules sequence may be syntactically valid yet selects invalid actions given the current state. ASGs ensure validity by enforcing semantic preconditions (e.g.. one cannot pick up block if the hand is full). Correctness, however, requires solving the downstream task. A semantically valid sequence may be functionally inadequate, such as repeatedly manipulating blocks without progressing towards the goal state (e.g., pickup (A), putdown (A) is valid but not correct if the goal is stack A on B). Global correctness optimization refers to inference-time methods whose optimization objective is defined over entire sequences, evaluating decisions based on their contribution to the final task outcome (e.g., pickup (A), stack (). This contrasts with local optimization approaches, which optimize step-wise objectives such as next-token likelihood or locally constrained probabilitics (c.g., greedy or locally constrained decoding), without explicitly optimizing for task success over full sequences (Geng el al. 2023 Zhang el al. 2023b Welleck et al. 2024, inter alia). Unconstrained search methods attempt this optimization but must prune the token action-space due computational fcasibility, risking the climination of the solution and thereby losing reachability guarantees. SEM-CTRL unifies these by performing global correctness optimization strictly within the guaranteed semantically valid space defined by the ASG (Figure 1 (b) and (d)).
2

---

Published in Transactions on Machine Learning Research (03/2026)
Our empirical results show that SEM-CTRL successfully addresses these challenges through three key contribu- tions: 1) domain-independeen framework using ASGs to capture comprehensive hierarchy of token-aligned constraints; 2) an efficient token-level MCTS procedure that explores only semantically valid trajectories; and finally 3) using experiments across Synthetic Grammar Synthesis, Combinatorial Reasoning, JSON pars- ing, and Planning, we demonstrate that SEM-CTRL enables even smaller language models (such as with 1B parameters), to outperform larger state-of-the-art reasoning specific models (such as ol-preview, 04-mini, and DeepSeek-RI), while guaranteeing output correctness. The results underscore the importance of jointly capturing validity and correctness, which is underexplored in the current research landscape.
2 Background
In this section, we present the relevant background for SEM-CTRL, and introduce formal languages and ASGs.
Formal Languages and Grammars A formal language I. is a (possibly infinite) set of strings composed of a finite alphabet or vocabulary M, adhering to specific rules governing syntax and semantics. Each word in the language, w = Su," ... .S,, is a finite sequence of symbols 8 E E. The set of all possible strings (including the emply string E) over E forms the Kleene closure Σ,, with L Σ* Languages are generated by means of formal grammars G = (N,T, P,S), where N is a finite set of non-terminal symbols, T is the set of terminal symbols ( Σ), P is finite set of production rules of the form A + ar (where, the left hand side A E N and the right hand side a E (N UT)),, and S E N is the start symbol. A string w belongs to the language of a grammar G, denoted by w E I(G), if there exists a sequence of rule applications (derivation) from $ to w. A parse tree PT then represents this derivation hierarchically, with internal nodes labeled by N, leaves by T, and edges showing the application of production rules (Linz & Rodger 2022
The expressiveness of formal languages varies with grammar restrictions. CFGs restrict productions to A + a where A E N, thus suitable for nested structures like natural language syntax. Context-Sensitive Grammars (CSGs) allow more expressive productions of the form aA8 - ary3 where a, E (N (NUT) and E UT) -2 This enables CSGs to capture context-dependent patterns - e.g., while CFGs can generate 0}, only CSGs can generate L2 = fa"b"c" n 2 0} where counts are equal.
L = ca
k.j.k
A Answer Set Grammars ASG is a symbolic framework for expressing CSGs that extend CFG production rules with sentext- constraints (for a thorough introduction, we refer the reader to Law et al. 2019). An ASG is composed of a CFG, augumented with a set UP of context-sonsitive constraints annotating the CFG's productions rules, and domain knowledge VB capturing domain-specifie semantic information as general rules and instance-specific facts. Both context-sensitive constraints and domain knowledge are expressed using Answer Set Programming (ASP), a symbolic formalism for representing knowledge and performing reasoning using a specialized symbolic solver. In ASP, general rules are of the form h :- by. bn (read as "h true if all by are true") and constraints are of the form : b.. ,b, (ruling out solutions where all by 's are satisfied). A string w is said to belong to the language of given ASG (i.c., w E L(GAsG)) if there exists parse tree PT from S to w that satisfies all the constraints and domain knowledge specified in the given ASG. This is formally defined by Equation ( where str(PTT) returns the string generated by the parse tree PT, and sat (GPT))) defines the satisfiability (based on the ASP semantics (Lifschitz. 2019)
of the ASP program G[PT] that encodes the parse tree PT and v = PR U WB-
w E L(G + 3PT str((P)) A sat sat(G))TT)
(1)
In other words, the set of logical statements, rules, and constraints encoded in v must all be true simultane- ously in the parse tree of w. ASGs inherit the expressiveness of ASP, which is state-of-the-art. computational first-order logic paradigm capable of capturing first-order logic with default and preference reasoning, and of efficiently solving combinatorial search problems (Lifschitz] 2019 Erdem et al. 2016). While ASGs do not natively support certain logics such as fuzzy logic, alternative solvers could extend this capability, potentially extending into other NLP applications. For the class of grammars used in this paper, constraint checking
1 lzeer more elements from the set one or more elements from the set
3

---

Published in Transactions on Machine Learning Research (03/2026)
has exponential worst-case complexity; we refer readers to Law et al. (0199) for detailed complexity analysis and prools, and to Section 5.4 for empirical performance across our benchmark tasks.
ASG Grammar
Parse Tree for aabbcc
start + as bs cs {
start size (2 @1.2,3
:- size si)) @1, not size @2. size(X)@ @1, not size(X @3.
as size (2)
bs
size (2)
size (2)
as "a" as size(X+1) size(()(i) } (0)) }
as
bs
cs
bs + "b" "b" bs { size(X+1) = size } size(0).
"a"
size 1)
"b"
size (1)
"c"
size
1)
cs + "c" cs size(X+1) :- size(X)@2, } size(0).
bs (0z
size(0)
"c
size(()
Figure 2: ASG for cb (left) and corresponding parse tree for aabbcc with ASP annotations (right). The grammar uses ASP annotations to enforce equal sequence lengths, with nodes showing computed size.
Figure 2 illustrates the ASG for the above mentioned language L2 (a"b"c" 2 0} alongside its corresponding parse tree for the string aabbcc. The constraints in curly brackets {...) (shown in bold) represent the parse tree annotations PR expressed as ASP code. VB is, in this case, empty. The predicate size (X) tracks the length n each sequence, where @i indicates the i-th child position the production rule. The constraint :- size @1, not size @2. reads as: "if the first child has size X, but the second child does not have size X, then reject this parse". The production rules (except for the first one) contain two alternatives separated by "I': the first alternative outputs one terminal symbol (i.e., a) and increments the size counter by one, using the value propagated from the recursively generated second child (i.e., size (X) 02), via the rule size (X+1) :- size 62) The second branch initializes the base case counter with size (0). The parse tree demonstrates how these annotations are computed: each non-terminal node shows its computed size value, building up from size(0) (0) to size (2) at the sequence roots. The parse tree root node accepts the string aabbcc all three child sequences have equal length. This is verified by checking the satisfiability of the two constraints. Note that, in Figure 2 if all annotations the curly brackets were empty (i.c., V 0). the corresponding ASG would reduce to the CFG language L1 (abbe i, k 0).
Authoring new ASGs requires both domain knowledge of the underlying task and technical expertise in ASG construction. The latter consists of two parts: defining the CFG and specifying semantic constraints (sce Appendix D for additional details and ASG examples that provide concrele illustrations of this separation). CFGs are widely adopted in practice, with existing grammars and tooling available for many tasks (e.g., our JSON grammar in Section 5.5 was automatically generated from the Lark Python parsing library). Semantic constraints require expertise in ASP, though ASP has proven be effective across many application domains including knowledge representation, robotics, and bioinformatics (for comprehensive examples, see Erdem et al. 2016). While this expertise requirement may pose adoption barrier, recent work demonstrates that LLMs generate ASP code from natural language specifications ions (e.g., Alviano el al. 2025 Schrader et. al.
2025
Ishay et al. 2023), potentially lowering this barrier for practitioners in less formalized domains.
3
Our Approach: SEM-CTRL
We now present SEM-CTRL, which, at its core, uses ASGs to enable token-level constraint verification during gencration, guided by semantically controlled MCTS. This approach ensures both semantic validity and solution quality: the constraints guarantee validity (by construction), while tree search efficiently explores the semantically valid token space to find correct solutions.

---

Published in Transactions on Machine Learning Research (03/2026)
3.1 Controlled Decoding through Semantic Constraints
To achieve controlled and valid generation, require that every partial out of the language model remains extendable to complete sequence in a predetermined target language. Equivalently, at each generation step we restrict admissible tokens to preserve the possibility of producing a valid final string. We achieve this by defining a general constraint function that maps partial sequences to valid next tokens, then instantiate this framework with constraints of increasing expressivity.
Concretely, we now formalize semantic control in autoregressive generation. Let V be the vocabulary of the LLM defined by its tokenizer and V its Kleene closure. We aim to ensure that any generated sequence belongs to target formal language I. S y* We define a construint function C V - V that maps any prefix Veu = (V),-.. ..t-1) E V* to its valid next tokens:
C(yce) { {y 3 L (y<c o ye) prefix of
(2)
where o denotes token concatenation. Intuitively, the function C(y=t) returns the set of possible derivation steps from Vet (set of tokens) that may yield a valid string w E T..
Given a language L, Equation (2) defines how a set of valid tokens can be generated. Depending on L, C(yct) encodes different levels of control.
Definition 3.1 (Syntactic Control). Given a CFG G, and its associated language L(G), CCFG is the con- straint function that returns tokens governed by the CFG derivation steps.
Definition 3.2 (Context-Sensitive Control). Given CSG G, and its associated language L(G), Cesc is the constraint function that returns tokens governed by the CSG derivation steps, i.e, that satisfy the context-sensitive constraints in PR with 1 00
Definition 3.3 (Semantic Control). Given an ASG G with BB * 0, and its associated language L(G), CSEM is the constraint function that returns tokens governed by the ASG derivation steps, i.e., that satisfy the semantic constraints in Pr and B.
As an illustration, consider automated planning domains. CCFG ensures parscable action sequences. CosG enforces type consistency of action predicates. CSEM guarantoes that the action sequence in V<r maps to valid, executable operations in the target environment maintaining state consistency and avoiding invalid trajectories. We note that the semantic constraints capture domain knowledge about what makes action sequences meaningful in the real planning environment. This is because semantic constraints refer to domaan-specific knowledge, meaningful relationships, and rules that transcend typical local, positional nature of (CFG or CSG) grammar rules.
Controlled Autoregressive Sampling To incorporate these constraint functions at inference, we define constrained sampling mechanism. Let z denote the input and y<t the prefix of tokens generated up timestep t 1. The language model defines the autoregressive conditional distribution po(y x. Vet). To euforce constraints, the constrained distribution 40(1. xx, (e)) is given by:
qe x. (<e) & (o x, Myy E C(ys()),
(3)
where Ilye E C(yct)] when ye E C(ycr), and 0 otherwise.
3.2 Decoding with ASGs
We instantiate C using ASGs, which is expressive enough to capture CSEM- Standard ASG formulation allows specification of whether complete string w E L(G). To integrate ASG into decoding and enable semantic control, have extended ASGs to enable next-token valid completions. We expand on this here.
3.2.1 Semantically Valid Completions
When instantiating our constraint function with ASGs, valid next-token choices cannot be determined from the current. parse frontier alone, since semantic constraints may encode complex, non-local relationships
5

---

Published in Transactions on Machine Learning Research (03/2026)
and background facts. To address this, we track the complete set of partial parse trees consistent with the generated prefix and, for each candidate token, verify whether extending at least one of these trees still satisfies all ASP constraints. Thereby, admitting only tokens that preserve some valid partial parse, we can ensure every prefix remains on a guaranteod path to a fully derivable, hence semantically coherent output.
Formally, given a vocabulary Σ, a valid ASG the tuple GASG (Ger, V) where the terminals T E Σ align with LLM's vocabulary V (we discuss this in Section 3.2.2). For any prefix sequence Y<r E T", we define (( as the set of partial parse trees rooted at start symbol S with terminal frontier Ver- Each tree 8 E (ууar must satisfy all ASP constraints v (i.e., sat(G parse trees for given string, we maintain the complete set of partial trees, each representing a possible grammatical derivation of the prefix. We use ò @ a to denote extending a partial tree ó by token a E T, and Ayyc o a) to represent a collection of all partial parse trees consistent with the extended sequence y<r o a. Building on these definitions, we can specify the set of valid completions:
In order to handle multiple valid
CASa(Ue)) {ye E TTITLT 38 A(yc)), ó y E ((veo))))
(4)
The completion function (y essentially relurns precisely those tokens y for which at least one partial parse tree in (yga) can be correctly extended to yield Alyer o ye). This procedure guarantees that every selected token Yt E (U<) maintains Gss [PT) with respect to V as defined in Equation preserving a feasible path to a complete derivation in ((GsG)).
(PT]
The decoding procedure initiates with special start symbol S (corresponding to LLM's <BOS> token) and continues until either the only valid completion is end symbol (<EOS> token), or the LLM terminates generation when <EDS> appears among the valid completions.
Guaranteeing Semantic Validity We restrict each generation step only to tokens that preserve at least one valid partial parse, the goal here is to ensure that every prefix remains extendable to a complete derivation satisfying all constraints. This invariance guarantees that once decoding terminates, the complete output is in the (ASG's) language.
More precisely, the structure of ASGs guarantees, by construction, that any complete sequence y ~ [CAsc belongs to L(GAG)), where qe and CASG are defined in Equation (3) and Equation ( respectively. This guarantee follows from our token-level invariant: at each step 6, selecting yt (Css((<e ensures that at least one partial parse & E ((v+)) can be extended to some &, E A(Be(+1) while preserving all ASP constraints. The ASP solver enforces this invariant by examining all feasible extensions at every step. When generation terminates, the resulting parse tree satisfies sat(GAsc by construction, guaranteeing y E ASG)) This provides stronger somantic guarantces than approaches that rely on external solvers or prompl engineering (detailed in Section 6 through aligning constraints at the token-level.
3.2.2 Vocabulary Alignment
Our discussion thus far has assumed perfect alignment. between the ASG terminals T and the LLM vocabulary V. In practice, however, this alignment requires careful consideration as multiple LLM tokens might compose to single terminal, and vice versa (Beurer- Kellner al. 2024).
As such, we formalize this alignment through bidirectional mapping functions T* V* and -- V T T (1). For any sequence of terminals (a),..., an) E T"* r(a1,...,a,, produces a sequence of vocabulary tokens (V),... um) E V" that compose it, while --1 maps a sequence of tokens back to sequence of terminals if valid, returning 1 otherwise. These mappings must satisfy the following consistency property:
:sET" = (mapping consistency)
In practice, J automatically precomputes all possible expansions of sequences in T wrt. V. Since in our domains T is finite, enumerating valid expansions is tractable.
3 repreesenting an invalid or undefined mapping
6

---

Published in Transactions on Machine Learning Research (03/2026)
3.3 Decoding with Token- Aliinee Semantic Tree Search
we defined the constraint function CASG that guarantees semantic validity. While this guarantees that every generated sequence y is semantically valid, it does not guarantee that y is the correct solution to the problem. Consider the Blocksworld example in Figure I (a): a sequence of actions repeatedly picking up and putting down the same block would be semantically valid as it follows all the domain rules. However, it would not achieve the desired goal state.
In Section
3.1 we introduced constrained sampling, and in Section 3.2
One might consider encoding the goal-state as a requirement directly into the ASG's constraints V, forcing only sequences terminating in the goal to be valid. However, this approach would transform SEM-CTRL from being task-specific (applicable any instance of Blocksworld) to being instance-specifte (tied to one particular Blocksworld configuration and goal). Instead, we want V to express general rules and semantic knowledge about the domain, while using a separate mechanism to achieve instance goals. We exploit, a sementic MCTS procedure to enforce token-level control over the generation process such that it is capable of globally optimizing sequences using domain-specifi rewards to search for correct solutions. This allows for explicit exploration of multiple semantically valid trajectories through task-aware scoring of the trajectories and value backpropagation to guide future expansions.
We note that our approach fundamentally differs from traditional constrained decoding approaches, which only perform local pruning of invalid tokens at each step.
3.3.1 Token-level decoding as MDP
We formulate sequence generation as a Markov Decision Process (MDP), treating token selection as sequential
decision-making (Zhang et al. 2023b Wan et al. 2024). This formulation will allow us to apply principled
search while maintaining semantic control through our ASGs. The MDP is defined follows: 1) States & E 8 represents partial generation (ar, y<t) consisting of the input prompt and the tokens generated far y 2)
Actions E A correspond to selecting tokens from the LLM vocabulary V; and 3) Transitions T : x A that deterministically appends the selected token to the current sequence: (((I, a) = (z. (et
In this framework, the LLM serves as a policy To : S - A that maps each state to a distribution over actions: no (alss) = po(a|z, yer). Here, the goal thus to find a sequence y that maximizes the cumulative reward. Generation continues until a maxinum length is reached or EOS is generated.
Domain Specific Reward Design Unlike prior work that rely on LLM-bbsed approximate rewards (Hoo et al. 2023 Wan et al. 2024), we design explicit domsin-specific rewards R: S x A - R. This aligns with our overarching goal of guaranteed correctness. Our reward function combines two key elements: 1) semantic validity (enforced by ASG constraints); and 2) task-specific distance functions. Formally, we define:
if o E ((GAsG) Plyce oa)= =0 R(st, a) = -pless { o0) if yer a & T(GAsG) V plyer o +
{
(6)
Here, p(-) measures the "distance to goal" and imposes penalties for invalid generations. In empirical we highlight tasks where formal guarantees and exact correctness are achievable.
evaluations in Section
3.3.2 Semantically guided search
Building on our MDP formulation, we exploit MCTS to compute sequences that simultancously satisfy necessary semantic constraints L(GAsG) and optimize the final task-specific objective. Our semantic MCTS variant modifics the standard algorithm in three key ways:
1. Constrained Selection: We guide node selection using constrained token distribution @CxsO For each state we select the action a according to:
arg max Q(5e; a) + U(),
(7)
7

---

Published in Transactions on Machine Learning Research (03/2026)
where Q(s a) are average returns and ((s, a) is the PUCB term (iiver et al. 2017 Zhang et al.
2023b
VE, ((s,,))
Uss a) = B(s) 9Cssa (a st).
1 ((),,a)
where N-) tracks visit counts and ((s) balances exploration against exploitation.
2. Semantic Expansion: When expanding leaf nodes 8t, we exploit CASG to enumerate only valid next tokens. This semantic pruming yields small set of children (s)) = 1 15 in our experiments), greatly reducing the branching factor compared to unconstrained methods that consider thousands of tokens.
3. Controlled Rollouts: We simulate rollouts by gencrating a complete sequence y from state & according to y ~ II:50 (C 8t); where 4Caso guarantees semantic validity throughout the rollout. In practice, we use beam search with beam size=1 or greedy decoding for efficient and deterministic completions.
This semantic guidance distinguishes SEM-CTRL from previous moarch-guided (reasoning- related and other) approaches (detailed in Section 0 Our strategy of constraining exploration to valid trajectories and using domain-specific rewards helps ensure LLM's search process remains within the space of meaningful solutions, providing reliable control when coupled with ASGs.
3.4 Handling Computational Overheads
While our semantically constrained MCTS approach provides robust control over generation, it introducees additional computational costs. We address this through three complementary optimization strategies:
(1) Caching Partial ASG Derivations. We cache partial parse trees å to avoid recomputing CASC (V=c.)
(2 Semantic Tree Pruning Unlike methods that rely on arbitrary top-k sampling (Zhang et al. 2023b;
Wan et al. 2024 Hao et al.) 2023), our semantic constraints enable effective deep search by maintaining a small branching factor. As detailed in Section 3.3.2 CASG enables exploration at significant depths (e.g., 256 tokens) while preserving both domain feasibility and solution reachability-if a correct solution exists at depth d, it remains discoverable. This allows reliable traversal to high-reward solutions.
(3) Tree-Structure Caching Following Zhang et al. 2023b), exploit the hierarchical nature of MCTS by caching tree structures and sequences. For any prefx Ver that reappears across iterations, we reuse its stored top-k expansions and rollouts. Similarly, we cache partial or complete rollouts to avoid redundant sub-tree computations and duplicate model calls. This ensures we only pay for expansions once per node.
4 Experiments
We evaluate SEM-CTRL across four diverse classes of tasks to assess its effectiveness enforcing complex constraints while generating correct solutions. Our evaluation spans Synthetic Grammar Synthesis (SGS), Combinatorial Reasoning (CR), JSON parsing, and Planning tasks
4.1 Task Setup
We describe the details of each class of tasks below.
Synthetic Grammar Synthesis We evaluate SEM-CTRL on three canonical SGS tasks: L1 (a" 2 1), L2 = (am""" m., n 1,m * n), and Leopy { (ww
b), For each task, evaluate over 30 samples. For L1, we linearly increment n from 1 to 3 We define the distance function A n Rw where Nhw represents the count of n in the generated string y. For Lz, we increment m from 3 to 32 and use distance function P2 = (m + ( - (m + nww), where m and new are the respective counts in y. For Leopy: we divide the 30 samples into 10 cqual parts across three evaluation critcria: incrementing a from 1 to 10, incrementing from to 10, and maximizing their product. Here, P3 measures the distance to these largets.
See Appendix C for detailed task descriptions, constraints, and distance functions p(-).
Tn fact, our choice 30 is due in part Allen-Zha 2024 work.
8

---

Published in Transactions on Machine Learning Research (03/2026)
Each task involves prompting an LLM with exemplars E C1, et where 1 E 10,5], with the number of exemplars varying based on the complexity of the target string (e.g., fewer examples for simpler cases).
Combinatorial Reasoning The combinatorial reasoning related tasks include benchmarks from prior work Borazjanizadeh et al. 2024 Seely et al.) 2025), J, these include: (1) Sudoku 3x3 boards, (2) Sudoku
[ong 2023
4x4 boards, and (3) 3-Graph Coloring (NP-complete) (Law et al. 2019). For Sudoku, we use the dataset from Long 2023) with one-shot prompts, where we expect the solutions in a nested list format (as shown in Table in the Appendix). The MCTS employs sparse reward function where p(-) 0 for solved boards
and 1 otherwise. We further note that our ASG only encodes game rules.
For 3-Graph Coloring, we prompt the LLM to generate valid colorings for graphs with at most 5 nodes and between 3 and 10 edges, using pl-) = e - Ew as the distance function. Following the SGS setup, we use few-shot prompting and require solutions to be formatted as edge lists (i.j).
Planning Our benchmark comprises the Blocksworld domain using PlanBench's plan generation task (Valmeekam al.] 2024). The dataset contains 600 one-shot problems requiring the LLM to provide action sequences from initial state to the goal. In cases, we expect the LLM to return structured output: comma-scparated action sequences. Our ASG constraints (V) ensure action proconditions are satisfied, while Wg tracks state information and general rules (e.g., goal completion termination). The distance func- tion p(-) combines a heuristic function h(s,9) approximating goal distance (i.e., relaxed plan heuristic given by Pyperplan| Alkhazraji et al. (0200) with a plan length penalty a l-lennplan) discouraging repetitive actions.
Parsing Our final benchmark is a parsing task using the dataset from NousResearch (2024), where the LLM extracts information from natural language and formats it as JSON according to schema. While SEM-CTRL is designed for tasks with well-defined semantics and reward function capturing correctness, some structured generation and semantic parsing tasks lack these properties (Lei et al. 2025 Roy et al.
2023
Wang et al. 2023] inter alia). We include this task as representative example to demonstrate SEM-CTRL'S broader applicability. Here, we run SEM-CTRL without MCTS and use an ASG encoding a CFG, demonstrating semi-open-ended structural generation capability without semantic constraints.
4.2
Experimental Setup
Models and Baselines We evaluate SEM-CTRL using three variants of Llama 3: Llama 3.2 IB, Llama 3.1 8B, and Llama 3.1 70B, and three state-of-the-art reasoning models: o4-mini, DeepSeek-R1, and ol-preview. To disentangle the contributions of different components, systematically evaluate combinations of sampling algorithms with varying constraint types. We describe the key baselines below:
Base Unconstrained: Greedy sampling assess the base model's capability.
Base with CCFa: Locally constrained syntactic decoding. This approach is analogous to various
work in controlled decoding where the LLM's next tokens are masked according to CFG constraints
(Geng et al. 2023 Ugare et al. 2024
et al. 2024 inter alia), though we implement
This through an ASG encoding a CFG.
XGrammar (Dong et al.) 2024): While Base with CoFG is functionally equivalent to prior work in syntactic control, run an additional bascline for the parsing task for completeness and to empirically highlight this equivalence.
Base with Cosc: We mask LLM logits with terminals from an ASG encoding context-sonsitive and semantic constraints. This parallels work in semantic parsing, though prior methods typically use CFG with ad-hoc constraints (e.g., Scholak et al., 2021 Poesia et al. 2022 Roy et al.. 2023).
BoN Unconstrained: Best-of-N (BoNN serves a simple constraint satisfaction mechanism by sampling N generations and rejecting invalid samples according to C and ranking solutions by R(-) (Welleck et al., 2024). We set N to match SEM-CTRL's computational budget (maximum number of MCTS samples generated during search) for fair comparison. See Appendix for N values.
MCTS Unconstrained: MCTS applied at the token level, corresponding a range of search-
guided reasoning approaches (e.g., Zhang et al. 2023b Wan et al. 2024

---

Published in Transactions on Machine Learning Research (03/2026)
We note that several of our baselines are themselves either exact approximate global correctness optimiza- tion methods in the sense that they seek high-reward putputs at inference time (e.g., unconstrained MCTS via principled search (Zhang et al. 2023b Hao et al. 2023 Wan et al., 2024)). Throughout the main text, we compare against two primary baselines: (1) Base unconstrained; (2) Unconstrained BoN sampling. Section 5.3 we present a comprehensive ablation study on the Blocksworld benchmark with all algorithm- constraint combinations, and provide the full results for the other tasks in Appendix H The complete list
of all baseline methods is detailed in Appendix E
For BoN, use temperature-1 nucleus sampling with standard parameters (top-p 1.0, top- 50). For SEM-CTRL, we set top-k to the number of terminals in the grammar. For the reasoning models, we use Microsoft Azure's API. We average all results over 3 runs
Evaluation Metrics We assess performance using three primary evaluation metrics: (1) A: Measures task-
specific accuracy (correctness); (2) VerG: Mcasures CFG validity (y E L(Gera)); (3) VesG: Mcasures CSG validity (y E L(GcGG)); (4) VSEm: Measures semantic validity (y L(GSEM)).
5
Results
We present an empirical evaluation SEM-CTRL on the experimental set-up introduced in Section analysis structured answer several key research questions, which we address the following subscctions.
4 Our
5.1
Overall Results
We present our main findings in Table [ We observe that SEM-CTRL consistently matches or exceeds baseline performance across all tasks. We highlight the following key observations:
Table 1: Accuracy (A) results for the tasks: e" d"" Copy, Graph Coloring (Graph), Sudoku 3x3 (Sudoku-3), Sudoku 4x4 (Sudoku-4), and Planning (Blocks), using various sampling algorithms (Alg.), with different base LLMs (Model).
Synthetic Grammar Synthesis
Combinatorial Reasoning
Planning
Alg.
Model
a
Copy
Graph
Sudoku-3
Sudoku-4
Blocks
Llama 1B
3.3%
0.0%
10.0%
0.0%
0.0%
0.0%
0.0%
Base
Llama 70B
30.0%
0.0%
60.0%
37.5%
90.0%
30.0%
23.2%
Llama 1B
7.8%
1.1%
48.9%
0.0%
0.0%
0.0%
4.3%
BoN
Llama 70B
71.1%
22.2%
88.9%
100.0%
96.7%
80.0%
48.8%
ol-preview
83.3%
80.0%
96.7%
75.0%
100.0%
100.0%
94.5%
APT
DeepSeek-R1
83.3%
70.0%
96.7%
75.0%
100.0%
100.0%
96.5%
o4-mini
93.3%
93.3%
100.0%
75.0%
100.0%
100.0%
98.5%
Llama 1B
100.0%
100.0%
100.0%
100.0%
100.0%
100.0%
74.0%
SEM-CTRL
Llama 70B
100.0%
100.0%
100.0%
100.0%
100.0%
100.0%
96.8%
Parameter Efficiency SEM-CTRL with Llama 1B consistently outperforms both greedy and BoN Llama 70B variants across all tasks. Prominently, in the complex dd""""""d" task, SEM-CTRL with Llama 1B achieves 100% accuracy while Llama 70B fails completely (0% accuracy). This indicates that our semant rontrol framework effectively compensates for model size, enabling smaller models to solve complex reasoning tasks through guided exploration.
Comparison State-of-the-Ar Art SEM-CTRL achieves superior or competitive performance compared current stato-of-tho-art reasoning models, including o4-mini, DeepSeck-R1, and ol-preview, across SGS, Combinatorial Reasoning, and Planning domains. On SGS and Combinatorial Reasoning tasks, SEM-CTRL
Code will be released upon acceptance the paper once the review process concluded, order preserve anonymity. Texcept Blocksworld due computational cost and our inference budget constraints.
10

---

Published in Transactions on Machine Learning Research (03/2026)
consistently outperforms all reasoning models. For instance, in a"b"c", SEM-CTRL achieves 100% accuracy compared to ol-preview's 83.3% and o4-mini's 93.3%. The performance gap becomes more pronounced on the more complex a""b"c""d" task, where performance degrades for ol-preview (80.0%) and DeepSeek-RI (70.0%), while o4-mini maintains 93.3% and SEM-CTRL reaches perfect accuracy. The advantage is particu- larly notable in Graph Coloring, a complex NP-complete problem, where all reasoning models achieve only 75% accuracy while SEM-CTRL maintains 100% accuracy. This demonstrates that our semantic constraints and guided search provide reliable, systematic, and consistent reasoning capabilities for structured problems, ensuring semantic validity and strong empirical performance across these diverse domains.
Task Complexity The effectiveness of SEM-CTRL is particularly evident in Blocksworld planning, arguably our most complex task requiring long-horizon reasoning, precise state tracking, and satisfying action pre- and post-conditions across 600 samples. Even with the smaller Llama 1B model, SEM- achieves 74% ac- curacy, outperforming larger closed-source models including Claude 3.5 Sonnet (57.6%) and GPT-4o (28.3%) (Valmockam al. 2025). Statistical analysis using paired permutation tests (a = 0.05) reveals that perfor- mance dilferences between STM-CTRL with Llama 70B (96.8%) and 04-mini (98.5%) or DeepSeek-R1 (96.5%) are not statistically significant, though the improvement over ol-preview (94.5%) is.
Notably, SEM-CTRL achieves this superior or comparable performance to state-of-the-arr reasoning models despite the complexity of this task purely at inference time with off-the-shelf LLMs. This competitive performance comes with the added benefit of guaranteed semantic validity (100% constraint satisfaction), whereas reasoning models cannot ensure constraint adherence. This demonstrates SEM-CTRL's effectiveness in achieving reliable and consistent inference with semantic guarantees across complex reasoning tasks.
Specializing LLM models One general pattern that we observe in our experiments is that SEM-CTRL is capable of transforming general-purpose off-the-shelf LLMs into domain--peccialize models at inference time with guarantees on obtaining the correct and semantically valid solutions.
5.2
Can SEM-CTRL guarentee grammatical validity?
To evaluate how well SEM-CTRL and unconstrained LLMs capture control levels, we follow prior work (Schucher
Table 2: Accuracy (A), context-free (VCFg) and context-sensitive (Vesa) correctness results on
let a.. 2022 Drozdov et al.] 2023 Levy et al.) 2023 es- pecially) and present VCFG and VCSG scores on SGS in Table 2 The results reveal the unreliability of LLMs, where unconstrained models fail adhere to constraints consistently; SEM-CTRL addresses this by guaranteeing var lidity at inference time.
SGS
Alg.
Model
VerG
VesG
Llama 1B
4.4%
79.0%
23.0%
Base
Llama 70B
30.0%
99.0%
39.0%
Llama 1B
19.3%
63.0%
35.0%
BoN
Two key patterns emerge: First, all models struggle no- tably more with VesG than Verg- small models like Llama 1B achieve 79% VCFG but only 23% VesG, while large models like Llama 70B achieve 99% VCF vs. 39% VesG. This contrasts with prior work's focus on syntax alone and motivates more expressive controls. Second, while sampling algorithms like BoN improve performance (Llama 70B with BoN reaches 79% VCSG and 35% for IB), none guarantee perfect validity.
Llama 70B
60.7%
97.0%
79.0%
ol-preview
86.7%
100.0%
88
API
DeepSeek- R.I
83.3%
100.0%
87.0%
o4-mini
94.7%
99.0%
95.0%
SEM- CTRL
Llama 1B
100.0%
100.0%
100.0%
Llama 70B
100.0%
100.0%
100.0%
Even state-of-the-art reasoning models fall short: ol-preview and DeepSeek-RI achieve only 88% and 87% VesG respectively, while 04-mini reaches 95%. This reveals two failure modes for accuracy: inability capture constraints and failure to ensure solution correctness. These empirical observations suggest that while LLMs approximate constraints, they lack robustness. SEM-CTRL instead achieves perfect VerG and VesG across tasks and model sizes, demonst rat ing explicit semantic control is crucial for reliable generation.
11

---

Published in Transactions on Machine Learning Research (03/2026)
5.3 How does each disentangled dimension contribute to SEM-CTRL's abilities?
We now present the results an ablation study for SEM-CTRL on Blocksworld planning Table B to disentangle the contributions of each dimension (semantic control, semantic search, and parame- ter scale). Following Valmeekam et al. (2023). subsample 50 problems and systematically evaluate constraint types (unconstrained, CCFG, CSEM) across sampling algorithms (Base, BoN, and MCTS).
Table 3: Results from Blocksworld ablation study
Alg.
Model
C
A
VCFG
VsEm
Llama 18
0%
100%
0%
Llama 1B
Cora
0%
100%
0%
Llama 1B
CArM
6%
100%
100%
Base
Llama 70B
30%
100%
40%
Llama 70B
Cofa
30%
100%
40%
Llama 70B
40%
100%
100%
Key empirical findings emerge: First, incrementally moving from control to syntactic to semantic con- straints shows consistent improvements most pro- nounced with BoN where Llama 1B improves from 6% to 56%. Second, CCFG only benefits when com- bined with MCTS, yet still underperforms BoN with CSEM. Across all configurations, we find that CSEM provides the most substantial gains.
Llama 1B
6%
94%
6%
Llama 1B
COFG
6%
100%
6%
Llama 1B
CSEM
56%
100%
100%
BoN
Llama 70B
66%
100%
66%
Llama 70B
CoFG
66%
100%
66%
Llama 70B
CaEM
90%
100%
100%
Llama 1B
12%
100%
40%
MC-
Llama 1B
CoFG
38%
100%
66%
TS
Llama 70B
46%
96%
68%
Our SEM-CTRL strategy, (which essentially is CSEM + MCTS) achieves substantially better results than either component alone, enabling even the IJama 1B model to outperform baselines and the 70B model to match or exceed reasoning model performance. This highlights the importance of semantic control, which fundamentally provides crucial structure for MCTS effectively navigate the solution space, producing improvements exceeding the sum of their individual contributions. We present ablations on SGS and CR in Appendix H
Llama 70B
Cosa
62%
100%
92%
SEM-
Llama 1B
CabM
76%
100%
100%
CTRL
Llama 70B
CAEM 98%
100%
100%
where we observe similar trends.
5.4 How computationally efficient is SEM-CTRL compared to reasoning models?
We begin by formally decomposing SEM-CTRL's wall-clock time and computational cost into its constituent components follows:
Table 4: Average computational effi-
ciency per sample on SGS, CR, and Blocksworld Planning (Blocks) using
Llama 70B
Trotal RJ (Neokens x TLLM) + Tc + T Teearch ops
(9)
Class
Alg.
Ntokens
Te
where Ntokens is the total number of generated tokens, TILM is the hardware-dependent latency of a single forward pass, Te is the time spent evaluating ASG constraints, and T searrch_ope represents MCTS operations (e.g., incrementing visit counts). Notably, Tsearch ops consists of constant-time CPU operations, making its contribution negligible compared to Te or the dominant GPU costs of TLLM-
ol al-preview
1639.0
DeepSeek-R1
927.3
SGS.
04-mini
705.3
SEM-CTRL
250.2
123.24
ol-preview
3184.8
DeepSeek-RR
3016.5
CR.
o4-mini
1190.5
SEM-CTRL
123.3
15.90
We analyze computational and token costs compared to reason- ing models to evaluate SEM-CTRL's efficiency established via well- metrics that
ol-preview
2457.9
structured search, focusing on hardwarr-indeeendee enable fair comparisons. The class of reasoning models is under- stood to perform form of reasoning via reasoning tokens before outputting the final generation. Following recent work in token- level search (e.g,, Valmeekam et al.) 2025; Zhou el al.) (224)), we report Nokees and Tc as our primary metrics. Since our baselines are slorcd-source reasoning models running on unknown hardware and inference strategics, token counts provide hardware-independe comparison with reasoning models: just as reasoning models consume tokens during their reasoning process, SEM-CTRL consumes tokens during search.
Blocks
DeepSeck-R1
2345.8
04-mini
1544.5
SEM-CTRL
589.8
35.97
proxy for inference cost. This naturally enables
12

---

Published in Transactions on Machine Learning Research (03/2026)
While SEM-CTRL introduces constraint checking overhead (Tc), the results demonstrate significant reduction in total token generation. We observe that across all tasks, SEM-CTRL reduces token usage by an order of magnitude. For example, we see in CR tasks that SEM-CTRL is 25.8x, 24.5x, and 9.7x more efficient than ol-preview, DeepSeck-R1, and 04-mini, respectively, while achieving perfect accuracy. Te varies by task structure, with SGS showing higher overhead (123s) due to its synthetic nature requiring notably deeper parse trees (up to depth 64) compared to shallower structures in CR and Planning. We note that this computational time depends on the depth of the sequences' parse trees in the grammär, which, for this task, is stressed to be higher than prior work (e.g., Allen-Zhu & Li 2024
5.5 How well does SEM-CTRL work without semantics and rewards?
We turn to assessing SEM-CTRL's broader applicability when stripped of semantic structures and reward signals via the JSON parsing results in Table 5 Here, SEM-CTRL operates under Base sampling and achieves per- feet CFG validity (100%) across model sizes, matching XGrammar (Dong ett al. 2024), which we include as a representative baseline of existing CFG-constrained methods (see Sections 4.2 and 6 As anticipated, both approaches achieve identical results since they are functionally equivalent when only CFG constraints are present. Large models like Llama 70B (96.9%) and state-of-the-art reasoning models (98.4%) fail to guarantee perfect syntactic validity on this widely-used structured generation task. This confirms SEM-CTRL'S reliable constraint enforcement across the spec- trum, from complex semantic reasoning lasks to basic syntactic generation.
Table 5: VerG results on the JSON parsing task
Alg.
Model
VerG
Llama
75.0%
Base
Llama 70B
96.9%
Llama
100.0%
X Xgramiar
Llama 70B
100.0%
DeepSeek-RI
98.4%
API
o4-mini
98.4%
Llama 100.0%
SEX-CTRL
Llama 70H
100.0%
5.6
Does fine-tuning impact models' performance with SEM-CTRL?
While SEM-CTRL is designed as an inference-time algorithm enabling strong performance without the high training costs of fine-tuning, comparing the two approaches offers a valuable perspective on the trade-offs and potential complementarity between inference-tine time search and training-time adaptation. We conduct experiments on Blocksworld, fine-tuning LJama-1B models using varying fractions of the PlanBench training data (5%, 10%, 20%, 50%, and 100%). For each fine-tuned model, compare greedy decoding against SEM-CTRL. We evaluate on the Blocksworld ablation set introduced in Section and report (1) Accuracy (A): percentage of problems correctly solved, and (2) Sample Efficiency (Seq.): the average number of full sampled sequences explored by MCTS before finding a correct solution, with results summarized in Table 0
Table 6: Accuracy (A) and sam- ple efficiency (Seq.) results on the Blocksworld ablation set with vary- ing Fine-Tuning (FT) data splits on SEM-CTRL and greedy sampling.
Model
FT Data
A
Seq.
0.0%
12.0%
Llama 1B (Greedy)
10%
10.0%
20%
16.0%
50%
16.0%
100%
14.0%
0%
76.0%
71.14
Table 6 reveals three key findings. First, without fine-tuning, with Llama-1B substantially outperforms fine-tuned greedy baselines across all data regimes (76% vs. 16% maximum greedy accuracy), confirming that SEM-CTRL alone provides strong inference-time gains that fine-tuning does not reliably recover. Sec- ond, fine-tuning and SEM-CTRL are complementary: as the amount of fine-tuning data increases, accuracy improves further (up to 90%), while the number of sampled sequences required by MCTS drops by up to 5.4x (71.14 vs. 13.22 sequences with full data). This indicates that fine-tuning helps shape the model's distribution by learning to generate more valid trajectories that SEM-CTRL can efficiently explore via robust. semantic control to ensure correctness.
58.0%
53.80
Llama CTRL)
10%
76.0%
46.00
20%
90.0%
30.04
50%
88.0%
17.44
100%
88.0%
13.22
Llama 70B (SEM-CTRL)
0%
98.0%
19.12
Finally, regarding parameter efficiency, Llama 1B with SEM-CTRL and moderate fine-tuning (20-50% of FT data) rivals the performance of Llama 70B, despite being orders of magnitude smaller and 1.4x more sample efficient. (13.22 19.12 sequences). This demonstrates that SEM-CTRL significantly reduces the amount of
13

---

Published in Transactions on Machine Learning Research (03/2026)
fine-tuning required to reach target performance level. Ultimately, our results clarify that SEM- serves as a versatile inference-tmme mechanism rather than a strict alternative to fine-tuning: it ensures robust performance when training costs are prohibitive, yet yields synergistic gains when fine-tuning is feasible, simultancously improving both accuracy and search efficiency.
6 Related Work
Controlled Decoding Research in controlled decoding has evolved increasingly expressive forms of control. Early work focused on simple lexical constraints (Welleck et al.
2024
Hokamp & Liu 2017 Anderson
ct al. 2017 inter alia), subsequently formalized using predicate logic
Lu et al. 2022
Zhang et al. 2023a
and extended to higher abstraction levels (Lew et al. 2023 Yao et al.
2024a]. More sop cophisticated approaches
exploit CFGs to enforce syutactic validity (Beurer- -Beurer-Kellner et al. 2023 Koo et al. 2024
U Ugare et al. 2024
inter alia). Prior work refers to constrained decoding as control via hard constraints and controlled decoding
via preferences Vang Klein 2021 Meng al. 2024). We to both as control, formalized in Soction 3.1
Semantic Parsing with LLMs LLM-based semantic parsing has progressed from unconstrained methods via fine-tuning (inter alia Roy et al. 2023 Li et al., 2021 and prompting (Schucher et al.) 2022 Drozdov
ct al.
2023 to constrained gencration with domain-specific rules. Systems like PICARD (Scooakk et al.
2021
combine CFGs with domain-specific guards for SQL generation, with others exlending this to other
(2025) incorporates weal-world semantic signals instead of constraints alongside CFGs or assumes LLMs can approximate CFGs, We address these limitations through ASGs, which expresses a hierarchy of constraints, guaranteeing validity across domains. SEM-CTRL distinguishes itself by directly employing the CSG formalism (to our knowledge, first to do so) and focusing on tasks where correctness is observable at inference, unlike other semantic parsing work where semantic constraints, correctness observability, both are absent (i.e., JSON parsing).
domains (Ugare et al. 2025 Shin et al., 2021 Poesia et al., 2022). In contrast, Loula et al.
LLMs-Based Reasoning, Search, and Planning Work in augmenting reasoning capabilities of LLMs have extended Chain-of-Thought (Wei et al. 2022) to non-lincar reasoning through sequence-lovel tree search like Tree-of-Thought (Yao et al. 2024b) and MCTS (e.g.. mur.hyyrthy et al. 2024)) enabling betler exploration of solution paths. Token-level search methods (Zhang et al.] 2023b Wan et al.) 2024) offer more granular control. However, both limit tree width, risking the exclusion of valid solutions. Others augment LLMs with tools QQin et al. 2024) solvers (e.g., Yang et al., 2025 Xu et al. 2024), introducing potential translation errors FFng et al. 2024). In planning domains, reasoning models show impressive results (Valmeekam et al. 2025), yet cannot guarantee plan validity, leading to methods using search-guided reasoning (Hao et al, 2023). verifiers (Kambhampati et al. 2024), or LLMs as houristics (Wang et al. 2023). SEM-CTRL addresses this via token-aligned semantic constraints with MCTS, efficiently exploring the only valid solution spaces.
7 Conclusion
We presented SEM-CTRL, a unified framework enabling controlled generation from LLMs, combining seman- tie constraints expressed via ASGs with token-level MCTS. We show that combining expressive semantic constraints with guided search guarantees semantic correctness and augments the capabilities of off-the-shelf LLMs. Especially, we show that it enables small models to outperform state-of-the-ate LLMs (i.c., o4-mini). Our empirical results demonstrate that rich and expressive control mechanisms can transform general-purpose purpose LLMs into robust and reliable domain-spocialized models while greatly reducing token overhead.
Broader Impact Statement
SEM-CTRL enables smaller, more efficient models to achieve reliable performance with formal correctness guarantees, reducing computational costs and environmental impact while democratizing access to high- quality structured generation without fine-tuning.
However, several limitations warrant considcration. SEM-CTRL requires that the underlying language model's learned representations align with the target constraint vocabulary, i.c., domains where the model lacks suf- ficient exposure to relevant terminals may exhibit. degraded performance. Our approach currently operates
14

---

Published in Transactions on Machine Learning Research (03/2026)
exclusively on text, though hypothesize extensibility to multimodal scenarios; validation requires addi- tional research, experinentation, and benchmarks for multimodal constraint enforcement. Furthermore, our constraint framework operates under a binary validity paradigm, precluding applications required for NLP tasks such as text summarization.
Finally, systematic constraint enforcement may amplify distributional biases present constraint formu- lations, necessitating careful specification design to mitigate potential discriminatory outcomes. However, while SEM-CTRR CEM- does not inherently prevent such bias, and recognizing that formal correctness does not imply ethical social appropriateness, our framework mitigates these risks through transparency. Since SEM-CTRL relies on symbolic constraint specifications, these rules are inherently interpretable and provide natural mechanism to verify or audit for potential malware or malicious intent. This stands in contrast to knowledge distilled in opaque model parameters. Although such checks require ASP expertise, LLMs can be utilized to generate these constraints, thereby facilitating the democratization of auditable, controlled generation (e.g.- Alviano et al., 2025; Schrader et al.] 2025 Ishay et al., 2023). These limitations, while crucial, remain out of the scope of this paper, necessitating additional research in the field of controlled decoding.
Acknowledgments
We thank Anthony Cohn and Microsoft Research's Accelerating Foundation Models Research program for the provision of Azure resources run some of the LLMs used in the experiments in this paper. This work supported in part by the Alan Turing Institute under Fundamental Rescarch (Project No. PP00029) and projects 3928 and EP HPP/Y03741/1 funded by the UKRI.
References
Yusra Alkhazraji, Matthias Frorath, Markus Grützner, Malte Helmert, Thomas Licbetraut, Robert Mattmüller, Manuela Ortlieb, Jendrik Seipp, Tobias Springenberg, Philip Stahl, and Jan Wülfing. Pyper- plan. https://doi.
2020. URL https: /tap::///oo.orr/10... 1tt/10.5521//2endd... 5281/zenodo..
3700819
Zeyuan Allen-Zhu and Yuanzhi Li. Physics of language models: Part 1, learning hierarchical language structures, 2024. URL httpp:://arxiv.or//aaaas
13673
Mario Alviano, Lorenzo Grillo, Fabrizio Lo Scudo, and Luis Angel Rodriguez Reiners. Integrating answer set programming and large language models for enhanced structured representation of complex knowledge natural language. In James Kwok (ed.), Proceedings of the Thirty- Fourth International Joint Conference on Arlificial Intelligence, IJCAI-25, pp. 4330 4338. International Joint Conferences on Artificial Intelligence Organization, 8 2025. doi: 20.24963/ijcai..o 2025/482 URL httpp:://o// 10.g//0..oo 20133/2j6aiaaai 2025/482) Main Track.
Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. Guided open vocabulary image captioning with constrained beam search. In Martha Palmer, Rebecca Hwa, and Sebastian Riedel (eds.), Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 936-945, Copenhagen, Demmark, September 2017. Association for Computational Linguistics. doi: 10.18653/v1/ 117-1098. URL. httts://acclanthol/ wtw.:attwhhoootoo///11/110000000 org////11//9///////
Luca Beurer-Kellner, Mare Fischer, and Martin Vechev. Prompting is programming: A query language for large language models. Proceedings of the ACM on Programming Languages, 7(PLDI):1946 1969, June 2023. ISSN 2475-1421.
doi: 10.1145/3591300. URL http://x...01.or//1.111111.1 1111///11111511111000
Luca Beurer-Kellner, Marc Fischer, and Martin Vechev. Guiding LLMs the right way: Fast, non-invasive constrained generation. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (ods.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 3658-30 3673. PMLR, 21-27 Jul 2024. URL httpp:://rooeeedings mlr
15

---

Published in Transactions on Machine Learning Research (03/2026)
Nasim Borazjanizadeh, Roci Herzig, Trevor Darrell, Rogerio Feris, and Leonid Karlinsky. Navigating the labyrinth: Exaluating and enhancing llss' ability to reason about search problems, 2024. URL https:
//arxiv. flarxiv.org/ble org/abs//406..o..///gg/ 2t
Yixin Dong, Charlie F Ruan, Yaxing Cai, Ruihang Lai, Ziyi Xu, Yilong Zhao, and Tianqi Chen. Xgram- mar: Flexible and efficient structured generation engine for large language models. ar preprinl
arXiv:2411.15100 2024.
Andrew Drozdov, Nathanael Schärli, Ekin Akyürek, Nathan Scales, Xinying Song, Xinyun Chen, Olivier Bousquet, and Denny Zhou. Compositional semantic parsing with large language models. In The Bleventh International Conference on Learning Representations, 2023. URL https://openreviiet wtwp:rrwwwwwinneefooreeeeeee
g @J8hSSBBss8
Esra Erdem, Michael Gelfond, and Nicola Leone. Applications of answer set programming. AT Magazine, 37 (3):53-68 68, Oct. 2016. doi: 00.1609/aimag, 2678. URL httpp:://ossssaatt aaai www. arg/alnngaaznee/ndee php/ http///mmgzzzee/aattttt/////////
Jiazhan Feng, Ruochen Xu, Junheng Hao, Hiteshi Sharma, Yelong Shen, Dongyan Zhao, and Weizhu Chen. Language models can be deductive solvers. In Kevin Duh, Helena. Gomez, and Steven Bethard (eds.); Findings of the Association for Computational Linguistics: NAACL 2024, pp. 4026 4042, Mexico City, Mexico, June 2024. Association for Computational Linguistics. doi: 2011653/v11222444 findings- naacl. 254. URL htttps::/aclattthloloo wtwppog..rr//o/........ findings-naacl 254/
Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West. Craamar-coostrainee decoding for struc- tured NLP tasks without finetuning. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 10932 10952, Singapore, December 2023. Association for Computational Linguistics. doi: 10.18653/v1/2022 200653//1/2023emmmppp emnlp-main.61 main.674. URL https://aclanthhllo. .wr.agg...rgg/u0g org//o23 emnlp monnlp-min.... main. 674/
Shibo Hao, Yi Gu, Haodi Ma, Joshua Hong, Zhen Wang, Daisy Wang, and Zhiting Hu. Reasoning with language model is planning with world model. In Houda Bouamor, Juan Pino, and Kalika. Bali (eds.), Proceedings of the 2023 Conference on Empirical Melhods in Natural Language Processing, pp- 8154- 8173, Singapore, December 2023. Association for Computational Linguistics. doi: 10.18653/v120023 mmnlp-main.507. URL
wrwp:/ggy..gg/222..r..g smnnp-mmin.550 507/
Chris Hokamp and Qun Liu. Lexically constrained decoding for sequence generation using grid beam search. In Regina Barzilay and Min-Yen Kan (eds.), Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pp. 1535 1546, Vancouver, Canada, July 2017. Association for Computational Linguisties. doi: 10.18653/v1/P17-1144 URL https://aclanthoologyy org/P17-1141/
Adam Ishay, Zhun Yang, and Joohyung Lee. Leveraging large language models to generate answer set programs. In Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, KR '23, 2023. ISBN 978-1-956792-00-7. doi: 2224966/kr.2223/// URL https://doi. org/19 10. 24963/kr. 2023/37
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil B Murthy. Position: LLMs can't plan, but can help planning in LLM- modulo frameworks. In Forty-first International Conference Machine Learning, 2024. URL https: //openreview.oo wwwpanrevieew.et/ffrrooeeee wwt.:nettfooooeee (errummidiThhe d=Th8JPPEM44z
Terry Koo, Frederick Liu, and Luheng He. Automata- constraints for language model decoding. In First Conference on Language Modeling, 2024. URL https:://peenrevier. htt.://www....emmmooooooddddddaa
Mark Law, Alessandra Russo, Elisa Bertino, Krysia Broda, and Jorge Lobo. Representing and lcarning grammars in answer set programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp.
2019.
16

---

Published in Transactions on Machine Learning Research (03/2026)
Fangyu Lei, Jixuan Chen, Yuxiao Ye, Ruisheng Cao, Dongchan Shin, Hongjin SU, ZHAOQING SUO, Hongcheng Gao, Wenjing Hu, Pengcheng Yin, Victor Zhong, Caiming Xiong, Ruoxi Sun, Qian Liu, Sida Wang, and Tao Yu. Spider 2.0: Evaluating language models on real-world enterprise text-to- SQL workflows. In The Thirteenth International Conference on Learning Representations, 2025. URL
Itay Levy, Ben Bogin, and Jonathan Berant. Diverse demonstrations improve in-context compositional generalization. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1401- 1422, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023 acl-long.78. 78. URL https:: https///taaaaatto.a.oooomm org/ 2023 acl-long. 78/
Alexander K. Lew, Tan duan, Gabriel Grand, and Vikash Mansinghka, Sequential monte carlo steering of large language models using probabilistic programs. In ICML 2023 Workshop: Sampling and Optimization in Discrete Space, 2023. URL
Haoran Li, Abhinav Arora, Shuohui Chen, Anchit Gupta, Sonal Gupta, and Yashar Mehdad. MTOP: A comprehensive multilingual task-oriented semantic parsing benchmark. In Paola Merlo, Jorg Tiedemann, and Reut Tsarfaty (eds.): Proceedings of the 16th Conference of the European Chapler of the Association for Computational Linguistics: Main Volume, pp. 2950-2962, Online, April 2021. Association for Com- putational Linguistics. doi: 20.18653/v1/2221..er waal-mmiin2257 URL attpp://aalaanhhooggy herpllogy.orgg/0000 org/2021. macl-main.2777
Vladimir Lifschitz. Answer set programming, volume 3. Springer Heidelberg, 2019.
Peter Linz and Susan H Rodger. An introduction to formal languages and aulomala. Jones & Bartlett Learning, 2022.
Jieyi Long. Large language model guided troughf-thought, 2023. URL hatpps://axxw..org///aa wttp///g/aa///a/aaa////// 08291
João Loula, Benjamin LeBrun, Li Du, Ben Lipkin, Clemente Pasti, Gabriel Grand, Tianyu Liu, Yahya Emara, Marjorie Freedman, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Alexander K. Lew, Tim Vieira, and Timothy J. O'Donnell. Syntactic and semantic control of large language models via sequential monte carlo. In The Thirteenth International Conference on Learning Representations, 2025. URL https: Plopenreviev.net/// ttee:/forummiixxxx62222222 =xx00
Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, Noah A. Smith, and Yejin Choi. NeuroLogic a a*esque decoding: Con- strained text generation with lookahead hcuristics. In Marine Carpuat, Marie-Catherine de Marneffe, and Ivan Vladimir Meza Ruiz (eds.), Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 780-799 299,799, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10.18653/ v1 /2022 www.:2222mammmmmmma....m.. URL https://aclanthology) org/ 2022 naacl 57/
Tao Meng, Ninareh Mehrabi, Palash Goyal, Anil Ramakrishna, Aram Galstyan, Richard Zemel, Kai- Wei Chang, Rahul Gupta, and Charith Peris. Attribute controlled fine-tuning for large language models: A case study on detoxification. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Findings of the Association for Computational Linguisties: EMNLP 2024, pp. 13329 13341, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: 10. 00.18653/v1/240 http:////20...ndnnn--emm/p/pp findings-ennlp.779 wttp://o////2...oiin.........
URL
Rithesh Murthy, Shelby Heinecke, Juan Carlos Niebles, Zhiwei Liu, Le Xue, Weiran Yao, Yihao Feng, Zeyuan Chen, Akash Gokul, Devansh Arpit, Ran Xu, Phil L Mui, Huan Wang, Caiming Xiong, and Silvio Savarese. REX: Rapid exploration and exploitation for Al agents. In ICLR 2024 Workshop Large Language Model (LLM) Agents, 2024. URL https://openreviier http:///www.....oooooooodd/ds/ds
NousResearch.
NousResearch/ssn--ooeee
https://uuginngaae. http://nnngaacccocttttttttt///// co//attssstts//ooseeeeeeaaall
j -son-mode-en eval February 2024. Accessed: March 28, 2025.
17

---

Published in Transactions on Machine Learning Research (03/2026)
Kanghee Park, Jiayu Wang, Taylor Kong-Kirkpatrick, Nadia Polikarpova, and Loris D'Antoni. Grammar- aligned decoding. In The Thirly-eighth Annual Conference on Neural Information Processing Systems. 2024. URL
Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meck, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models. In International Conference on Learning Representations, 2022. URL
Yujia Qin, Shengding Hu, Yankai Lin, Weize Chen, Ning Ding, Ganqu Cui, Zheni Zeng, Xuanhe Zhou, Yufei Huang, Chaojun Xiao, et al. Tool learning with foundation models. ACM Compuling Surveys, 57(4): 40, 2024.
Subhro Roy, Sam Thomson, Tongfei Chen, Richard Shin, Adam Pauls, Jason Eisner, and Benjamin Van Durme. BenchCLAMP: A benchmark for evaluating language models on syutactic and semantic parsing, In Thirky-seventh Conference on Neural Information Processing Systems Dalasels and Benchmarks Track, 2023. https://openrevver httt::///ppaarrveeeeeee/rrrrrrra /ttp://oooror...../////......
Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. PICARD: Parsing incrementally for con- Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 9895 9901, Online and Punta Cana, Dominican Republic, Novem- ber 2021. Association for Computational Linguistics. doi: 10.18653 10.18653/v1/202/ http:///////.../mmmmaiiiii mainp-main.779. URL emnlp-manie main. 779/
strained auto-regressive decoding from language models. In
https::/aclantiooooy..or..
Timo Pierre Schrader, Lukas Lange, Tobias Kaminski, Simon Razniewski, and Annemaric Friedrich. A solver-in-the-loop framework for improving Ilms on answer set programmning for logic puzzle solving, arXiv preprint arXiv:2512. 17093, 2025.
Nathan Schucher, Siva Reddy, and Harm de Vries. The power of prompt tuning for low-resource semantic parsing. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meeling of the Associalion for Computational Linguistics (Volume Short Pupers), pp. 148-156, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10. /11188//1/2222222c-////// URL https://aallanthooogg.//
www.oogg........................ www.oogg./......eeoo acl-short......r.... 17/
Jeffrey Seely, Yuki Imajuku, Tianyu Zhao, Edoardo Cetin, and Llion Jones. Sadoku-Bende 2025.
https://
Richard Shin, Christopher Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. Constrained language models yield Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference on Empérical Methods in Natural Language Processing, pp. 7699-7715, Online and Punta Cana, Dominican Republic, November 2021. Association for Compu- tational Linguistics. doi: (0.18633vv1/20 http:/11222211111111111 Lemnlp-main.666 6088. URI. htttp:://cclattholooo org.//21......11.... Sanlp-main.. aoo-mai..600 608/
few-shot semantic parsers. In
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. Mastering chess and shogi by self-play with a general reinforcement learning algorithm, 2017. URL htttp:::/aaxiv.og//bbb///////
01815
Shubhan Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. Syncode: Llm generation with grammar augmentation, 2024. CRL http::://aaxv...gg//////////////
Shubham Ugare, Rohan Gumaste, Tarun Suresh, Gagandoep Singh, and Sasa Misailovic. Itergen: Iterative semantic-aware structured LLM generation with backtracking. In The Thirteenth International Conference on Learning Representations, 2025. URL htttas///paaaaiiiaaeeeeee/rrrrrr
18

---

Published in Transactions on Machine Learning Research (03/2026)
Karthik Valmeckam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilities of large language models-a critical investigation. Advances in Neural Information Processing Systems, 36:75993 76005, 2023.
Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Planbench: An extensible benchmark for evaluating large language models planning and reasoning about change. Advances in Newral Informalion Processing Systems, 36, 2024.
Karthik Valmeckam, Kaya Stechly, Atharva Gundawar, and Subbarao Kambhampati. A systematic evalua- tion of the planning and scheduling abilities of the reasoning model ol. Transactions on Machine Learning Research, 2025. ISSN 2835-8856. URL
Ziyu Wan, Xidong Feng, Muning Wen, Stephen Marcus Mcaleer, Ying Wen, Weinan Zhang, and Jun Wang. AlphaZero-like treo-search can guide large language model decoding and training. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 49890 49920. PMLR, 21 27 Jul 2024. URL https::/ppocceeding
mlr. press/v236 3/2235/aan24c... wan24c. html
Ballin Wang, Zi Wang. Xuczhi Wang, Yuan Cao, Rif A. Saurous, and Yoon Kim. Grammar prompting for domain-specific language generation with large language models. In Thirly-seventh Conference on Newral Information Processing Systems, 2023. URL httaps://openrevien net/Hoorum?dddBtttkeeel
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thought prompting clicits reasoning large language models. Advances in neural information processing systems, 35:24824 24837, 2022.
Scan Welleck, Amanda Bertsch, Matthew Finlayson, Hailey Schoelkopf, Alex Xic, Graham Neubig, Ilia Kulikov, and Zaid Harchaoui. From decoding to meta-generation: Inference-time algorithms for large language models. arXiv preprint ar 2rx::22406. 16838, 2024.
Fangzhi Xu, Zhiyong WU, Qiushi Sun, Siyu Ren, Fei Yuan, Shuai Yuan, Qika Lin, Yu Qiao, and Jun Liu. Symbol-LLM: Towards foundational symbol-centric interface for large language models. In Lun- Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Compulational Linguisties (Volume 1: Long Pupers), pp. 13091-13116 Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10.18653/v1 1/22444/// lon.loo..777. URL https: //aclanthology. wrg/2024..0.......o ac1.24..111ooo..70 707/
Kevin Yang and Dan Kloin. FUDGE: Controlled text gencration with future discriminators. In Kristina Toutanova, Anna Rumshisky, Luke Zeutlemoer, Dilek Hakkani-Tur, Iz Beltagy, Sleven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (eds.), Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technolo- gies, pp. 3511-3535, Online, June 2021. Association for Computational Linguisties. doi: 10.18653/v1/ 2021 naw.l- mainllmmin..211 276. URL ctttps//aaclantholloe wrwpchhollogy.oo//222222. maacl-main 276/
Sen Yang. Xin Li, Leyang Cui, Lidong Bing, and Wai Lam. Neuro-symbolic integration brings causal and re- liable reasoning proofs. In Luis Chiruzzo, Alan Ritter, and Lu Wang (eds.). Findings of the Association for Computational Linguistics: NAACL 2025, pp. 5732-5744, Albuquerque, New Mexico, April 2025. Associ- alion for Computational Linguistics. ISBN 179-8-89176--955- doi: 10. (0.18653/v1/2025..1 www.://5..innnn-mmm. 337. wtw. www.iing-nnaacl.3111111
URL
Shunyu Yao, Howard Chen, Austin W. Hanjie, Runzhe Yang, and Karthik R Narasimhan. COLLIE: Sys- tematic construction of constrained text generation tasks. In The Twelfth International Conference Learning Representations, 2024a. URL httpt:://opeerevieeeeeee httpi/iwww.nnetteeeeeeeeee net//forumiddxxxllyyiUU
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024b.
19

---

Published in Transactions on Machine Learning Research (03/2026)
Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. Tractable control for autoregressive language generation. In International Conference Machine Learning, pp.
PMT.R, 2023a.
Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua Tenenbaum, and Chuang Gan. Planning with large language models for code generation. In The Fleventh International Conference Learning Representations, 2023b. URL htBLLtttps//ppprrveveeeeee//// htt.://www....eeoooooooooeeeee/0
Andy Zhou, Kai Yan, Michal Chlapentook--oohhmant Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifics reasoning, acting, and planning in language models. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Searlett, and Felix Berkenkamp (eds.). Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proccedings of Machine Learning Research, pp. 62138 62160. PMLR, 21 27 Jul 2024. URL httt:://prooeedingg..ii hasss/v236/zhou243 html
20

---

Published in Transactions on Machine Learning Research (03/2026)
A Prompt Examples
System Message:
You an expert reasoning, solving puzzles, and formal languages, specifically, Context- and Context- Sensitive Grammars. Given puzzle or reasoning problem, you can easily solve it, even those requiring combinatorial reasoning. Furthermore, you can read understand grammars, and given a grammna spec- ification, you can generate words that consistently conform to the grammar, its language, and rules without single mistake. Specifically, you are an expert solving Sudoku puzzles. The generalised rules of an n n Sudoku board are as follows:
grid with numbers through 2. Each row must contain numbers 1-n without repeating.
1. Fill an
3. Each column must contain numbers 1-n without repeating.
4. Each yn x y box must contain numbers I-n without repeating (only applicable in the case where is perfect square).
Pre-filled numbers camnot be changed.
For each message, you will be presented with a Sudoku board, and you must return a solution to the puzzle conforming its grammar. The grammar for Sudoku is follows: srow_1.....Ior nl, where each row i is a list numbers separated by a comma without any spaces representing a row in the Sudoku board, ie., [j.....n]] .n]. Furthermore, separate each by comma without any spaces. Simply put, this grammar is matrix (nested list. format) representation
the Sudokn board. Missing numbers in the partial boards You must leave the pre-filled numbers unchanged. Your goal is solve the Sudoku board and only return a valid solution to the puzzle according to the grammar; do not generate any additional text beyond the solution.
presented are represented
Example Interaction:
User: Generate valid solution to the Sudoku board [,,,]],,,,,,,3, [3, [3]+,2]] where represents cell to be filled in. Please return your solution according to the grammar for Sudoku.
Assistant: [[2,3, 1], [1, 21,,,3], [3,1,2]
[4,2, where represents a cell to be filled in. Please return your solution according to the grammar for Sudoku.
User: Generate valid solution to the Sudoku board [1,,,, [4,1, [4,,,,
Assistant: [[1,3,2], 12,1,3), [3]2,1]]
Figure 3: Prompt template for the 3x3 Sudoku lask, showing the system message that defines the task and grammar, followed by example interactions.
Figure 3 showcases an example prompt from our (asks, specifically, the Sudoku-3x3 prompt. It adopts standard prompting strategy. We find that combination of textual description of the task, syntax, and constraints, and a simplified grammar format provides better results opposed to simply providing the entire grammar itself (i.e., in ASG or Extended Backus Naur Form). This is in contrast with prior work (Wang et al. 2023), which found providing the complete grammar to the LLM to be helpful the case of GPT-4. This was not the case with our experiments. We empirically choose these prompts according the basclines' accuracies (i.c., Greedy or BoN), as we find SEM-CTRL be robust to slight variations in the prompt. SGS and Combinatorial Reasoning follow similar prompting strategy. Hence, we omit them.
We further provide the prompts used for our plan generation PlanBench task in Figure g given we slightly modify the task from the original dataset Valmeekam et al. (0024). Our slight changes were made by empirically examining the model's performance when required to return the action sequences as a list. of actions as opposed to free-form text.
21

---

Published in Transactions on Machine Learning Research (03/2026)
System Message:
You expert planner, where given a domatin and an instance of problem, you must provide sequence of actions taking the agent the environment from the initial state the goal state in the most optimal manner. You do not select invalid actions, you do not generate sub-optimal plans, and you must conform to the domain's specifications provided to you. In your response, you must only provide sequence of actions separated by commas achieving the goal state without providing any other information. You must only use the actions and enviromment objects available to you and nothing else. Specifically, you planner in the Blocksworld domain, where given a set of blocks arranged in an initial configuration, you must provide sequence of actions achieving the goal of arranging the blocks in desired configuration. You very good at this task.
expert PDDL
Initial and goal states are defined by a series of predicates, described below:
1. BLOCK N BLOCK NAME The block BLOCK NAME is top of block BLOCK NAME 2
2. ontable BLOCK_NAMK The block BLOCK BLOCK_NAME on the table
3. clear BLOCK BLOCK_NAME: The block BLOCK being held
BLOCK_NAMP. NAME is clear, i.e. no other blocks are on top of it and it
4. handempty: The robotic hand holding any blocks and is free
The restrictions of the actions are as follows:
1. You can only pickup or unstack one block at time
2. You can only pickup or unstack a block if the robotic hand is empty
3. You can only pickup block if the block is the table and the block is clear
4. You can only unstack block from top of another block if the block you are unstacking really
on top of other block
5. You can only unstack a block from on top another block if the block you are unstacking is clear
6. Once you pickup or unstack a block, the robotic hand holding the block
7. You can only putdown a block that the robotic hand is holding
8. You can only stack block top of another block if the robotic hand is holding the block being stacked
9. You can only stack block top another block if the latter block is clear
10. Once you putdown or stack block, the robotic hand becomes empty
11. Once you stack a block on top second block, the second block is no longer clear
12. You can only terminate the plan when the goal state is reached or your plan is complete
Block are defined colors, will be shown in the specific instances of the problem. To provide sequence of actions, you must separate them by comma.
Example Interaction:
User: Given instance of the Blocksworld domain follows:
Block Objects: red, blue, orange, yellow
Initial State: clear red, clear blue, clear yellow, handempty, on blue orange, ontable red, ontable orange, ontable yellow
Goal State: orange blue
Generate a plan, l.c., a sequence of actions separated by commas, taking the agent in the environment from the initial state to the goal state.
Assistant: unstack blue orange, putdown blue, pickup orange, stack orange blue, end User: Given an instance of the Blocksworld domain as follows:
Block Objects: red, blue, orange, yellow
Initial State: clear red, clear yellow, handempty, on red blue, on yellow orange, outable blue, ontable orange
Goal State: orange red
Generate a plan, iee, a sequence of actions separated by commas, taking the agent in the environment from the initial state to the goal state.
Assistant: unstack yellow orange, putdown yellow, pickup orange, stack orange red, end
Figure 4: Prompt template for the Blocksworld planning task, showing the system message that defines predicates and action restrictions, followed by example interactions.
22

---

Published in Transactions on Machine Learning Research (03/2026)
B Answer Set Programming
Answer Set Programming ( (ASP) is declarative paradigm for knowledge representation and reasoning, where problems are specified logically, and solutions (answer sets) are computed via specialized solvers. An ASP program consists of rules: normal rules of the form t- b,, (which is read as "h is true all b, are true"), choice rules I(/i;-.. Amm + b,. bn (specifying that between [ and u atoms from hy.... hm must be true when the body holds), hard constraints of the form <- by. b, (ruling out answer sets where the body is satisfied); and weak constraints ",,,,,, bn-[wr@]] (assigning weight. at level to penalize solutions that satisfy the body of the constraints).
Given an ASP program P, its semantics is defined through its Herbrand Base HBp (the set of all possible ground atoms) and Herbrand Interpretations (subsets of H Bp). ASP solvers compute answer sets AS(P), i.c., interpretations that satisfy all rules in P. We refer the reader to Lifschitz 2019) for more thorough details.
C
Task Breakdown
Table 7: Overview of tasks and their characteristics
Class
Task
Example
Constraint
p(-)
a"
3: aaabbbocc
Equal count of
Pla
Syuthetic
0, b,
Grammar
d" m 2, 3: aabbbcodddd
Paired counts
(m + n) (m. + Rw))
Synthesis
m #
w//w
10 ab: abob
Exact string replication
Distance to target counts
Sudokn-3x3
[1,",3) (,),,,,,,1
Row, column constraints
if solved, otherwise
Combinatorial
Sudoku-4x4
[1,,3,4] 2, 1,,,,,,,,,
Row, column, box constraints
0 if solved, otherwise
Reasoning
3-Graph
()., (0 2):
Valid 3-color assignment
Coloring
Edges: [0, 1,2]
Parsing
JSON
("item": "book",
JSON schema (CFG)
"price": 15}
(no reward)
Blocks
Plan
pickup rod, stack rod blue, end
State validity
M(sg)+ a allem(plan)
Planning
Gen.
preconditions
Table provides comprehensive overview of all tasks evaluated in our experiments. Each row details a specific task, showing example inpuls/outputs, constraints that must. be satisfied, and distance functions used to evaluate solution quality/ccrrreeness /correctness. The tasks span four categories: Synthetic Grammar Syn- thesis (testing formal language generation with increasing complexity), Combinatorial Reasoning (assess- ing structured problem-solving requiring combinatorial reasoning). Parsing (demonstrating semi-open-ended structural generation capabilities where semantic constraints and correctness rewards are not applicable). and Blocks Planning (evaluating semantic constraints and sequential decision-male makiinn with state-dependent constraints).
23

---

Published in Transactions on Machine Learning Research (03/2026)
D Answer Set Grammar Examples
start board { % This is ezample of purely contert-free production rule
board + "[" row, row, row row "]"
% This is conteat-sensitive production rule with the following semantic constraints:
% Assign each cell's value to corvesponding (X, Y) coortinate cell valle((1,)))
col(1,V1)@2. @2.
cell valvvalle (2) :- col(2,V2)
cell @all_value(44,4),___ :- col(4,V4)
Sudoku constranns:: Some row, column, and block
:- same C2), cell value value(C1,V) (C1,V), cell value (C2, V).
same (C1,C_) cell cell_value value(C1,V) cell cell_value(C) value(C2, (22,V) same (lo.k(C11CC) cell (allueCC1V)) cell value C2, C2,V).
row - "[" cell, cell, cell, cell "]" col(1,V1) :- cell val_eelllee
col(4,V4) :- cell_ value value(V4)@8.. V4)
}
cell - digit { cell cell_value(X :- di) }
digit "1" { (1git(1). "2" (iiiit()). "3" digit(3). } "4" { digit(4).
# #background
% Cell coordinates
cell((1,1)). cell((1,2)). ... cell((4,4)).
Cell values
cell_ cell_valuo 1), 1).
% Block definitions
((x))( :- X<3, Y<3.
block ((,,))br) :- X>2, Y>2.
% Structural relations
same row (X1,Y), Y)) X1 != X2.
same (o_e___olXXXX,))X,,,,.,_) :- Y1 != Y2.
same (ec__blocckCCCCCCC :- block(C1,B), block) C1 != C2.
Figure Example ASG for 4x4 Sudoku puzzle. The context-free portion of the ASG is given by the grammar productions, while semantic constraints expressed as bold ASP annotations within curly braces; omitting these annotations yields standard CFG. For instance, the start production rule is context-free, it carries no ASP annotations specifying semantic constraints. Answer Set Programming (ASP) annotations define grid structure, map parsed digits to grid coordinates, and enforce Sudoku constraints over rows, columns, and blocks.
24

---

Published in Transactions on Machine Learning Research (03/2026)
start action_seg seq ( % This is example of purely conterl-free production rule
action_seg seq
+ actions action_seq { end O 0
actions + stack 0 unstack 0 | pickup 0 putdown 0
pickup + "pickup" block {
% This is a contert-sensitioe production rule with the following semantic constraints: block(X)@@) not handempty.
block(X (X)
@2, not clear(X)
block block(X)@2) not ontable(X)@2.
goal.
}
putdown "putdown" block { block(X) not holding @2.
@X)
:- goal.
}
stack > "stack" block block {
:- block(X)or) @2, block Y @3, X Y.
block(X @2, not holding(X)ee)
block (X) @3, not clear(X) @3.
goal.
}
unstack "unstack" block block
block(X)@2, block(Y) @3, X = Y.
block(X) @2, block(Y) @3, not on(X, Y).
:- block(X) @2, not clear(X).
block(X) @2, alock(Y)@33, not handempty.
goal.
}
end + "end" { :- not goal.
comma + "," 0
block + "red" { block("red"), } "blue" { block("blue"). } "green" {
block(" (oock("geee").... }
# #background {
% Initial state ontable("red") on("blue", "red"). ontable(" ("green""" clear ("blue". alear("greent handempty.
}
Figure 6: Example ASG for the Blocksworld domain. Grammar productions define context-free backbone in standard Extended Backus-Naur form, while ASP annotations in bold and within curly braces specify semantic constraints; removing these annotations yields CFG. Answer Set Programming (ASP) annotations enforce action preconditions, state consistency, and goal satisfaction over generated action sequences.
25

---

Published in Transactions on Machine Learning Research (03/2026)
start + as bs ca {
This is a contexl-sensitive production rule with the following semantic constraints: size @1, not size @2.
size X @1, not size @3.
}
as - "a" as { size(X+1)) :- size(X) @2. } { size }
bs "b" bs { sizc(X+1) size (2e(X } { size(()). }
cs > "c" cs { size(X+1) size(X)@z @2. } { {size(0). }
Figure 7: Example ASG for the language a'b" where conlext-sensilive equal-length raintraints are intro- duced via ASP annotations in bold and enclosed in curly braces. If these annotations are removed (i.e., all curly braces are empty), the language defined by the grammar productions reduces to a a'bic
This ASG encodes a pure CFG without any ASP semantic constraints over production rules in carly braces
start + "{" fields "}" 0
fields firstName lastName age {
firstName "firstName" ":" string 0
lastName + "lastNiame ":" string {
age + "age" ":" number {
Figure 8: Example ASG for simplified fragment of JSON, where all semantic annotation blocks are empty, and the formalism reduces to pure CFG written in standard Extended Backus -aur form.
26

---

Published in Transactions on Machine Learning Research (03/2026)
E Complete Baseline Methods
We systematically evaluate all combinations of sampling algorithms (Base, BoN, MCTS) with constraint types (unconstrained, CorG, CCsG) to provide comprehensive ablation analysis. The complete list of bascline methods is as follows:
1. Base Unconstrained: Greedy sampling to assess the base model's capability.
2. Base with CCFG: Locally constrained syntactic decoding. This approach is analogous to various work in controlled decoding where the LLM's next tokens are masked according to CFG constraints (Geng et al. 2023; Ugare et al.) 2024 Kellner et al. 2024 interalia), though we implement this through an ASG encoding CFG.
3. XGrammar (Dong et al., 2024): While Base with Cora functionally equivalent to prior work in syntactic control, we run an additional baseline for the parsing task for completeness and to empirically highlight this equivalence.
4. Base with Ccsc: We mask LLM logits with terminals from an ASG encoding context-sensitive and semantic constraints. This parallels work in semantic parsing, though prior methods typically
use CFG with ad-hoc constraints (e.g., Scholak et al., 2021 Poesia et al. 2022 Roy et al. 2023)
BoN Unconstrained:: Best-of-N (BoN) serves a simple constraint satisfaction mechanism by sampling N generations and rejecting invalid samples according to C and ranking solutions by R(-) Welleck et al. (2024). We set N to match SEM-CTRL's ' computational budget (maximum number of MCTS samples generated during search) for fair comparison. See Appendix for N values.
6. BoN with Corg: We apply rejection sampling with local syntactic constraints.
BoN with Cesg: This serves as an additional ablation against SEM-CTRL to ascertain whether SEM-CTRL's 's search-guided reasoning capability and token-level incorporation of solution quality in- duces improvements. This is the first baseline that incorporates both notions of semantic validity and solution correctness.
8. MCTS Unconstrained: MCTS applied at the token level, corresponding to a range of search- guided reasoning approaches (e.g., Zhang et al. 2023b Wan et al.) 2024
MCTS with CCFG: Here, we run MCTS with an ASG only encoding syntactic constraints assess if the model benefits from additional semantic guidance and pruning achieved by SEM-CTRL.
10. SEM-CTRL: Our complete approach combining semantic constraints (Cosc) with MCTS for semanti- cally guided search.
F Further LLM Sampling Parameters
Table 8: Maximum sample times (N) for BoN and MCTS/SEM-CTRA CTML
Task
Sample Times (N)
SGS
50
Graph Coloring
35
Sudoku 3x3
Sudoku 4x4 Blocks
265
We have already provided most of the LLM sampling parameter details in Section 4.2 Here, define the max sample times for BoN and SEM-CTRL/MC (N) for both BoN and SEM-CTRL/MCTS based on lask complexity, as shown in Table In BoN, an LLM samples generations, then the reward function R(yx) selects the best output according to the highest reward. In MCTS, we conduct the four MCTS steps (discussod in Section 3.3.2) until we sample N full generations. Note: for the JSON parsing task, we only sample one generation for all methods (operate under Base sampling), given the lack of reward function.
We empirically select the maximum sample times
27

---

Published in Transactions on Machine Learning Research (03/2026)
For computational feasibility, make exception for Llama 70B BoN in Blocks tasks: use 15 samples (matching SEM-CTRL's average) for main experiments and 50 samples (31 more than SEM-CTRL's average) for ablation studies, rather than the full 200 samples, as generating this many sequences from a 70B model across 600 problems would be prohibitively expensive.
G Compute Cluster Specifications
Our experiments were conducted using two GPU clusters. The first cluster used nodes with 2x Intel Xeon Platinum 8358 CPUs (2.60GHz, 32 cores each) and NVIDIA L40S GPUs (48GB GDDR6), where we utilized up 4 GPUs with 1TB RAM per node. The second cluster used nodes with 2x Intel Xcon Platinum 8360Y CPUs (2.40GHz, 36 cores each) and NVIDIA A100 GPUs (80GB), where utilized up 2 GPUs with 1TB RAM per node.
H Further Results
This section provides additional experimental results, including those referenced in the main text and further analyses that support findings.
H.1
Context- Feetext-Free and Context-Sensitive Correctness Results on Combinatorial Reasoning and Planning
In Section 5 discussed the abilities of L.MSs to conform to CFG and CSG constraints without enforcing any form of control across various sampling strategies, contrasting such results with SEM-CTRL and its impact on accuracy. The discussion specifically presented results on Synthetic Grammar Synthesis in Table 2 Here, we present the same tables on the tasks Combinatorial Reasoning and Planning in Table g and Table T0 respectively. As detailed in Section 5 similar conclusions can be drawn according to such results. Hence, any further discussions are omitted.
Table 9: Accuracy (A), context-free (Verg) and context-sensitive (Vesg) correctness results on Combina- torial Reasoning
Alg.
Model
VCFG
VesG
Llama 1B
0.0%
11.0%
4.0%
Base
Llama 8B
25.0%
79.0%
32.0%
Llama 70B
57.4%
96.0%
66.0%
Llama 1B
0.0%
18.0%
10.0%
BoN
Llama 8B
65.5%
87.0%
73.0%
Llama 70B
89.7%
99.0%
91.0%
ol-preview
92.9%
100.0%
99.0%
API
DeepSeek- R1
92.9%
100.0%
96.0%
o4-mini
92.9%
100.0%
100.0%
Llana 1B
100.0%
100.0%
100.0%
SEM-CTRL
Llama 8B
100.0%
100.0%
100.0%
Llama 70B
100.0%
100.0%
100.0%
28

---

Published in Transactions on Machine Learning Research (03/2026)
Table 10: Accuracy (A), context-free (Vera) and context-sensitive (Vesa) correctness results on Planning (Blocks)
Alg.
Model
A
VCFG
Vesc
Llama 1B
0.0%
100.0%
0.0%
Base
Llama 8B
2.0%
100.0%
2.8%
Llama 70B
23.2%
100.0%
28.7%
Llama 1B
4.3%
86.2%
5.2%
BoN
Llama
27.3%
99.2%
27.8%
Llama 70B
48.8%
98.8%
54.7%
ol-preview
94.5%
99.8%
94.7%
API
DeepSeek-rl
96.5%
99.5%
97.2%
04-mini
98.5%
99.0%
98.5%
Llama
74.0%
100.0%
100.0%
SEM-CTRL
Llama 8B
90.3%
100.0%
100.0%
Llama 70B
96.8%
100.0%
100.0%
H.2 Extended Results with Llama 3.1 8B
The results presented in Section showcased model performance on Llama 3.2 1B and Llama 3.1 70B. Here, present the full results with Llama 3.1 8B, which was omitted from the original tables due to space requirements. While similar findings can be drawn, we chose to present models at opposite ends of the parameter scale (IB and 70B) in the main text. Table II corresponds to Table [ and Table 12 corresponds to Table 2 the main text. Similarly, Table 9 and Table I0 showcase the 8B results on Combinatorial Reasoning and Planning, respectively.
Table 11: Accuracy (A) results for all lasks: cb a"" Copy, Graph Coloring (Graph), Sudoku 3x3 (Sudoku-3), Sudoku 4x4 (Sudoku-4), and Blocksworld Planning (Blocks), using various sampling algorithms (Alg.), or API in the case of ol-preview, DeepSeck-R1, and 04-mini, with different base LLMs (Modcl). Here, we include Llama 3.1 8B.
Synthetic Grammar Synthesis
Combinatorial Reasoning
Planning
Alg.
Model
a
ad
Copy
Graph
Sudoku-3
Sudoku-4
Blocks
Llama 1B
3.3%
0.0%
10.0%
0.0%
0.0%
0.0%
0.0%
Base
Llama 8B
3.3%
0.0%
13.3%
25.0%
40.0%
10.0%
2.0%
Llama 70B
30.0%
0.0%
60.0%
37.5%
90.0%
30.0%
23.2%
Llama 1B
7.8%
1.1%
48.9%
0.0%
0.0%
0.0%
4.3%
BoN
Llama 8B
26.7%
13.3%
98.9%
41.7%
70.0%
80.0%
27.3%
Llama 70B
71.1%
22.2%
88.9%
100.0%
96.7%
80.0%
48.8%
ol-preview
83.3%
80.0%
96.7%
75.0%
100.0%
100.0%
94.5%
APT
DeepSeek-RR R1
83.3%
70.0%
96.7%
75.0%
100.0%
100.0%
96.5%
o4-mini
93.3%
93.3%
100.0%
75.0%
100.0%
100.0%
98.5%
Llama 1B
100.0%
100.0%
100.0%
100.0%
100.0%
100.0%
74.0%
SEM-CTRL
Llama 8B
100.0%
100.0%
100.0%
100.0%
100.0%
100.0%
90.3%
Ilama 70B
100.0%
100.0%
100.0%
100.0%
100.0%
100.0%
96.8%
29

---

Published in Transactions on Machine Learning Research (03/2026)
Table 12: Synthetic Grammar Synthesis tasks results (with Llama 8B)
Alg.
Model
A
VCFG
VesG
Llama 1B
4.4%
79.0%
23.0%
Base
Llama 8B
5.6%
94.0%
24.0%
Llama 70B
30.0%
99.0%
39.0%
Llama 1B
19.3%
65.0%
35.0%
BoN
Llama 8B
46.3%
91.0%
59.0%
Llama 70B
60.7%
97.0%
79.0%
ol-preview
86.7%
100.0%
88.0%
API
DeepSeck-RI
83.3%
100.0%
87.0%
o4-mini
94.7%
99.0%
95.0%
Llama 1B
100.0%
100.0%
100.0%
SEM-CTRL
Llama 8B
100.0%
100.0%
100.0%
Llama 70B
100.0%
100.0%
100.0%
H.3 Soft Accuracies
In Table 1 we demonstrate the performance of all models and basclines according to binary accuracy (1 if solved, otherwise). Here, we also introduce a complementary metric, Soft Accuracy, which uses the raw values from the reward function defined in Equation 6 Unlike binary accuracy, soft accuracy shows a continuous progression of results, where partial solutions receive credit proportional to their proximity to the correct solution, as determined by p(-). Table to model comparisons.
presents these results, which provide additional nuance
Table 13: Soft Accuracy (%) results for all tasks
Synthetic Grammar Synthesis
Combinatorial Reasoning
Alg.
Model
a"b"c" a dd
Copy
Graph
Sudoku-3
Sudoku-4
Llama IB
6.1+-20.5%
1.1+11.3%
10.5+-40.5%
10.4428.198 1%
0.0+00.0%
0.0+0.0%
Base
Llama 8B
7.7+24.1%
0.0+0.0%
42.5++42.4%
25.0 .2%
40.0:44.889
10.0+30.5%
Llama 70B
30.0.146.1% 3.1.1
77.4.137.2%
37.5.51.8%
90.0.130.5%
30.0.146.6%
Llama 1B
16.01133.0%
5.4.120.89
67.1141.11
24.3.1:6.099
0.0.0.0%
0.0.0.0%%
BoN
Llama 8B
39.3+47.6% 33.7++44.0%
98.9+10.5%
52.4+49.5%%
70.0+46.6%
80.0+40.77%
Llama 70B
78.3140..8% 59.61145.3%
91.11:26.6%
100.0=0.0%
96.7+18.3%
80.01:40.7%
ol-preview
33.5137.55%
80.6
98.6+10.7%%
92.0121.3%
100.0=1.00%
100 000.0:0.00%
API
DeepSeek-R1
87.64-31.6%
70.0+-4.669
99.6+-2.3%
85.0+135.0%
100.0++0.0%
10..0+00.0%
o4-mini
93.3+25.199 93.3+25..%%
100.0
96.1=7.6%
100.0
100.0=0.0%
Llama 1B
100.0+0.0%
100.0+0.0%
100.0
100.0+0.0%
100.0=0.0%
100.0%0.0%
SEM-
Llama 8B
100.0.0..05
100.0.1..9%
100.011.00%
100.0.10.0%
100.010.0%
100.0....0%
CTRL
Llama 70B
100.0+0.0%
100.0+t0.0%
100.0+0.0%
100.0+0.0%
100.0+0.0%
100.0+0.0%
From these soft accuracy results, we make several key observations:
The high variance in base models and BoN (shown by large standard deviations) suggests inconsis- tent performance even when measuring partial correctness, highlighting the inherent unrcliability of unconstrained approaches.
30

---

Published in Transactions on Machine Learning Research (03/2026)
2. The progression from Llama 1B to 70B shows more gradual improvement under soft accuracy pared to binary accuracy, indicating that larger models not only solve more problems but also get 'closer' to correct solutions when they fail.
3. Tasks like Copy and Sudoku-3x3 show higher soft accuracy than binary accuracy across all baselines, suggesting these tasks may be casier to partially solve but challenging to get exactly right. In contrast, a=""""""""""""""""""""""""""""""
e d shows similar scores in both metries, indicating an 'all-or-nothing" task structure.
SEM-CTRL maintains perfect scores with zero variance across all models and tasks under both metrics, further validating its reliability regardless of the evaluation criteria.
H.4 More Ablation Studies
In Section we conduct an ablation study on the PlanBench benchmark Valmeekam et al. (2024), comparing
our approach against prior work's sampling algorithms like BoN and Greedy with CCFG. Here, we extend this analysis to Synthetic Grammar Synthesis and Combinatorial Reasoning, with results shown Tables [4 and 15 While our findings largely mirror those from the Blocksworld domain, we observe an interesting phenomenon with Llama 8B: BoN with CCFG performs worse than its unconstrained version. This aligns with prior work (e.g., Park et al., 2024 showing that local decoding misalign the LLM's generative distribution by naively redistributing probability mass from invalid tokens, inflating the likelihood of rare soquenees. SEM-CTRL avoids this issuc through its combination of semantic control and principled scarch guided by domain-specifie rewards.
Table 14: Synthetic Grammar Synthesis ablation tasks results
Alg.
Model
C
A
VCrG
V VCsG
Llama 1B
4.4%
79.0%
23.0%
Llama 1B
CCFG
4.4%
100.0%
23.0%
Llama 1B
CaEM
11.1%
100.0%
100.0%
Llama 8B
5.6%
94.0%
24.0%
Base
Llama 8B
Cofa
8.9%
100.0%
34.0%
Llama 8B
CSEM
21.1%
100.0%
100.0%
Llama 70B
30.0%
99.0%
39.0%
Llama 1B
19.3%
65.0%
35.0%
Llama 1B
Cera
26.7%
100.0%
50.0%
Llama 1B
CsEM
71.5%
100.0%
100.0%
BoN
Llama 8B
46.3%
91.0%
59.0%
Llama 8B
CerG
39.6%
100.0%
60.0%
Llama 8B
CAEM
85.9%
100.0%
100.0%
Llama 70B
60.7%
97.0%
79.0%
Llama 1B
20.0%
80.0%
33.0%
Llama 1B
CerG
27.8%
100.0%
70.0%
MCTS
Llama 8B
36.7%
97.0%
47 47.0%
Llama 8B
Cora
36.7%
100.0%
78.0%
ol-preview
86.7%
100.0%
88. 98.0%
API
DeepSeek-RI R1
83.3%
100.0%
87.0%
04-mini
94.7%
99.0%
95.0%
Llama 1B
CAEM
100.0%
100.0%
100.0%
SEM-CTRL
Llama 8B
CsEM
100.0%
100.0%
100.0%
Llama 70B
CSEM
100.0%
100.0%
100.0%
31

---

Published in Transactions on Machine Learning Research (03/2026)
Table 15: Combinatorial Reasoning ablation tasks results
Alg.
Model
C
A
VCFG
VCsG
Llama 1B
0.0%
11.0%
4.0%
Llama 1B
CCFG
3.6%
100.0%
25.0%
Llama 1B
CseM
14.3%
100.0%
100.0%
Llama 8B
25.0%
79.0%
32.0%
Base
Llama 8B
Cera
21.1%
100.0%
32.0%
Llama 8B
CaEM
28.6%
100.0%
100.0%
Llama 70B
57.4%
96.0%
66.0%
Llama 1B
0.0%
18.0%
10.0%
Llama 1B
CCra
19.1%
100.0%
39.0%
Llama 1B
CSEM
76.2%
100.0%
100.0%
BoN
Llama
65.5%
87.0%
73.0%
Llama 8B
CCFG
77.4%
100.0%
81.0%
Llama
CsEM
94.0%
100.0%
100.0%
Llama 70B
89.7%
99.0%
91.0%
Llama 1B
0.0%
18.0%
14.0%
Llama 1B
CerG
32.1%
100.0%
61.0%
MCTS
LJama 8B
82.1%
93.0%
82.0%
Llama 8B
CerG
85.7%
100.0%
93.0%
ol-preview DeepSeek-R1
92.9%
100.0%
99.0%
API
92.9%
100.0%
96.0%
o4-mini
92.9%
100.0%
100.0%
Llama 1B
CSEM
100.0%
100.0%
100.0%
SEM-CTRL
Llama 8B
CsEM
100.0%
100.0%
100.0%
Llama 70B
CSEM
100.0%
100.0%
100.0%
32


Reviews:
[{"review_id": "Jtt9Mccjp4", "reviewer": "Reviewer_3cgA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "SEM-CTRL is a decoding framework that guarantees both syntactic and semantic validity of LLM outputs by combining Answer Set Grammars and token-level MCTS. The key insight is that semantic constraints dramatically prune the search space, enabling efficient exploration while guaranteeing validity by construction.\n\n## Key Strengths\n\n- A 1B-parameter model with SEM-CTRL achieves 100% accuracy on tasks where even o4-mini and o1-preview score 75–95%, demonstrating that explicit constraint enforcement outperforms implicit reasoning.\n- Unlike prompting or fine-tuning, outputs are provably valid with respect to the specified grammar, so no post-hoc verification needed.\n- Uses an order of magnitude fewer tokens than reasoning models while achieving equal or better performance.\n\n## Key Weaknesses\n\n- Authoring ASGs requires a lot of expertise in both the domain and Answer Set Programming, which is a significant adoption barrier.\n- This method only works for tasks with well-defined semantics and computable correctness signals; unsuitable for open-ended generation (e.g., summarization).\n- ASP constraint checking adds non-trivial latency (up to ~120 seconds on some tasks).\n- Benchmarks are pretty narrow and structured; generalization to messier real-world domains is unclear.", "claims_and_evidence_yn": "Yes", "claims_explanation": "I think the claims made in this papre are mostly supported by evidence.\n\nThe key claims include:\n- semantic constraints (CSEM) contribute more than syntactic constraints (CCFG), and that combining constraints with MCTS yields synergistic gains. (this is supported by ablation studies)\n- The 100% validity guarantee (it follows from the construction).\n- Token efficiency (the comparisons are pretty straightforward and convincing).", "audience_yn": "Yes", "audience_explanation": "I believe researchers building pipelines requiring guaranteed valid outputs (APIs, code generation, agentic workflows) will be interested in this submission.", "requested_changes": "Overall, I think this paper is in good shape.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1XqGfxEz8I", "reviewer": "Reviewer_g2Ju", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "SEM-CRTL is a method for constrained decoding to enforce semantic and syntactic rules on language model generation. The method uses Answer Set Grammars to define semantically valid trajectories that respect the rules of the task, in combination with token-level Monte Carlo Tree Search to search and explore semantically valid trajectories that reach the goal terminating state. \n\nTo address concerns of computation efficiency, the implementation relies on caching partial ASG derivations, pruning invalid tokens to reduce the branching factor, and caching partial rollouts of the tree structure.\n\nThe authors present a comprehensive set of experiments across a suite of tasks, comparing the performance of off the shelf language models of varying sizes with/without SEM-CTRL to other API accessible models.\n\nStrengths:\n* Well-written paper, easy to follow.\n* Nice background that makes the paper approachable to a reader outside this domain.\n* SEM-CTRL enforces global, context-sensitive constraints.\n* Strong empirical performance of SEM-CTRL across various tasks that improves parameter efficiency. SEM-CTRL on a 1b model can achieve higher accuracy than a 70b model.\n* SEM-CTRL offers token efficiency compared to reasoning models by constraining the generation.\n* Experiments are conducted over a wide range of tasks, validating that SEM-CTRL can be applied broadly.\n\nWeaknesses:\n* Introduces computational overhead to check constraints.\n* Requires domain knowledge of the user to define the rules and grammar.\n* Requires that constraints are binary, which could be limiting in some softer cases.\n* Depends somewhat on the alignment of LLM vocab and task vocab.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors include substantial empirical evidence that backs the claims they make.", "audience_yn": "Yes", "audience_explanation": "Yes, the findings presented in the paper would be of interest to researchers working on applying LLMs to solve tasks with logic-based constraints.", "requested_changes": "Minor fixes:\n* Page 1: define CSGs before using acronym", "broader_impact_concerns": "No concerns. The authors present the limitations of the paper in a Broader Impact Statement, and there are no ethical implications of the work that need to be addressed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WD56OOmYHo", "reviewer": "Reviewer_TZXh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces SEM-CTRL, a controlled decoding method that combines ASG-based semantic validity checking with MCTS-based search for solution correctness. Unlike methods that rely only on syntactic constraints or unconstrained MCTS, SEM-CTRL jointly enforces syntactic validity, semantic validity, and answer correctness. ASGs filter next-token candidates to those that can still form a semantically valid completion, while MCTS searches globally for high-reward (i.e., correct) solutions; all explored rollouts are semantically valid by construction.\n\nSEM-CTRL is evaluated on synthetic formal languages, combinatorial reasoning tasks (Sudoku, graph coloring), JSON parsing, and Blocksworld planning. Across these benchmarks, SEM-CTRL achieves high accuracy (Table 1) and perfect grammatical and semantic validity (Tables 2 and 4). Notably, it also improves parameter efficiency: even Llama 1B matches or surpasses state-of-the-art reasoning models (o1-preview, o4-mini, DeepSeek-R1).\n\n**Strengths**\n- A novel integration of symbolic validity checking (via ASGs) with reward-guided search (via MCTS).\n- Strong empirical results demonstrating high accuracy across diverse benchmarks.\n- Provides semantic validity guarantees that even state-of-the-art reasoning-oriented LLMs cannot offer.\n- Covers a broad range of tasks, including synthetic grammars, combinatorial puzzles, JSON parsing, and planning.\n- Offers a rich set of experiments that go beyond accuracy, including grammatical validity analyses, ablation studies, and computational efficiency measurements.\n- Includes (albeit brief) discussion of methods to reduce computational overhead (Section 3.4).\n\n**Weaknesses**\n- Authoring ASGs may require substantial expert knowledge and may not be feasible for more open-ended or poorly formalized domains. Relatedly, all evaluated tasks are synthetic or highly structured, leaving open the question of whether SEM-CTRL can be applied in more unconstrained, real-world settings.\n- Semantic constraint checking can incur significant computational overhead (e.g., >100 seconds in SGS tasks). The absence of wall-clock execution times in Section 5.4 makes it difficult to fully understand or contextualize this overhead relative to end-to-end performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claims made in the submission are supported by convincing evidence.\n\nClaim 1: (Performance enhancement) SEM-CTRL improves task performance.\n → This is supported by the near-perfect accuracy of SEM-CTRL–enabled models shown in Table 1.\n\nClaim 2: (Parameter efficiency) SEM-CTRL enables small models to match or exceed the performance of much larger reasoning-oriented models.\n → This is demonstrated by comparing Llama 1B + SEM-CTRL against 70B unconstrained models and state-of-the-art reasoning models in Table 1.\n\nClaim 3: (Validity guarantees) SEM-CTRL enforces grammatical and semantic correctness of outputs.\n → This is substantiated by the V_CFG, V_CSG, and V_SEM results reported in Tables 2 and 3.\nWhile the computational overhead of semantic constraint checking is somewhat under-discussed, this does not undermine the core claims. Overall, the empirical evidence is strong and clearly presented.", "audience_yn": "Yes", "audience_explanation": "The paper is highly relevant to researchers working on controllable generation, structured prediction, logical reasoning with LLMs, and safe or verifiable model outputs. SEM-CTRL is likely to appeal to the TMLR audience because it offers a unique approach that simultaneously addresses controllable generation (semantic validity) and logical reasoning (task accuracy). The work is particularly notable in showing that a principled decoding method can outperform much larger reasoning-focused models, making it both timely and impactful.", "requested_changes": "**Critical changes (important for acceptance):**\n1. **Discuss scalability limitations more transparently.**\n The ASG constraint-checking overhead is substantial in some benchmarks. A deeper analysis of computational complexity, memory usage, and scalability to longer sequences or larger grammars would strengthen the practical claims.\n2. **Provide a more complete computational cost analysis.**\n Include wall-clock time comparisons (not just token counts) for SEM-CTRL versus baselines on the same hardware. Break down time spent on LLM inference, constraint checking, and search. This information is essential for practitioners to assess feasibility.\n3. **Clarify the challenges and limitations of authoring ASGs for real-world domains.**\n The method assumes access to well-specified semantic rules. Discussion or concrete examples of how practitioners might construct ASGs in new or less formalized domains would help evaluate applicability and usability. Moreover, it would be helpful if the paper clarified whether ASGs can express all types of logic or are limited to particular families of logics, and where they can or cannot be applied. Explaining these limitations would make the scope of the method clearer.\n\n**Non-critical suggestions (would improve the work but are not required):**\n1. **Explore generalization beyond highly formal tasks.**\n Although the paper acknowledges limitations with open-ended tasks, consider adding an experiment demonstrating partial applicability to semi-structured generation (beyond JSON parsing), such as constrained story generation or semantic parsing with softer constraints.", "broader_impact_concerns": "The paper includes a Broader Impact Statement, which largely addresses environmental benefits and risks of bias encoded in constraints. \n\nAdditionally, below concerns could be addressed to enrich the Broader Impact Statement:\n1. The statement could more explicitly discuss potential misuse cases. While guaranteed correctness is beneficial, it could also be used to generate formally valid but malicious content (e.g., syntactically correct exploits, valid but misleading formal arguments).\n2. The democratization benefit of enabling smaller models is mentioned, but the requirement for ASG specification expertise may actually create new barriers to access. This tension could be acknowledged.\n3. The paper should briefly mention that perfect syntactic/semantic validity doesn't guarantee truthfulness or ethical appropriateness of generated content.\n\nThese are relatively minor concerns, and the existing Broader Impact Statement demonstrates appropriate consideration of ethical implications. The suggested additions would strengthen it but are not critical omissions.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BKhj1WrqUL", "reviewer": "Reviewer_aSC2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose SEM-CTRL, a framework which uses MCTS methods on constrained LLM outputs to improve performance on reasoning tasks. The core idea is this: once an LLM's output is correctly constrained to a grammar (in this case, an \"answer set grammar\", which defines \"task-specific semantics\"), it becomes possible to model and analyze sequences of decisions/outputs to better inform the decoding of the generated answer. The authors show that this principle, combined with their MCTS approach, improves the performance of off-the-shelf language models on a variety of benchmarks, allowing for small LLMs to achieve performance that normally requires more expensive models to achieve with previous methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors took care to benchmark their approach on a variety of datasets and across different popular LLM models, and the results are consistent with their claims that SEM-CTRL boosts performance, even with small models (such as llama-1b). The effect of the SEM-CTRL approach is studied explicitly via ablation, which shows improvement over a more simplistic MCTS approach that does not use the grammar-based approach, and constrained sampling approaches that do not use MCTS. The discussion at the end about broader impact and limitations of the work is appreciated.", "audience_yn": "Yes", "audience_explanation": "This work seems obviously relevant for audiences interested in ML/AI, since it focuses on popular language models and their applications.", "requested_changes": "The work discusses how the proposed approach is related to \"global correctness optimization\". As someone mostly unfamiliar with this field, it would be nice to see more explanation of other approaches, and possibly comparison. \n\nOne of the advertised benefits is the ability to achieve strong performance while avoiding fine tuning. But the work focuses on SEM-CTRL's inference-time performance. The high cost of fine tuning happens at training time: once a model is deployed for inference there is no difference (assuming same model size). Thus, if one is interested in just inference performance, it makes sense to compare any claims against results with fine tuning. Is it worth using a non-fine-tuned model of the same size equipped with SEM-CTRL? What benefits are there to using SEM-CTRL together with fine tuning? Or, if aiming for a certain level of performance at a certain model size (above what is possible with previous decoding approaches on a non-fine-tuned model), does using SEM-CTRL reduce the amount of fine tuning needed to reach the target? I would be curious to see further analysis of this.", "broader_impact_concerns": "I have no broader impact concerns that were not addressed in the provided statement in the paper already.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)