Paper deep dive

Meta-Ctrl: Guaranteed Plan Generation by Decoupling Syntactic and Semantic Constraints

Gwen Yidou-Weng, Edward Sun, Tianyi Ma, Metin Alp Dogan, Benjie Wang, Allen Peng, Guy Van den Broeck, Yuchen Cui

Year: 2026Venue: arXiv preprintArea: cs.ROType: PreprintEmbeddings: 90

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%

Last extracted: 8/25/2026, 8:22:59 AM

Summary

The paper introduces Meta-Ctrl, a constrained-decoding framework for Large Language Models (LLMs) that generates robot action plans with formal guarantees. It decouples syntactic constraints (enforced at the token level) from semantic constraints (enforced at the action level) using 'meta-tokens'. This factorization reduces memory requirements from over 107TB to under 2GB and allows small open-weight models (like Llama 3 8B) to outperform larger frontier models (like GPT-4) on benchmarks such as WAH-NL and the Embodied Agent Interface (EAI).

Entities (11)

Meta-Ctrl · method · 100%GPT-4 · model · 95%Llama-3-8B · model · 95%meta-tokens · concept · 95%BEHAVIOR · dataset · 90%Ctrl-G · method · 90%Embodied Agent Interface · benchmark · 90%LoTa-Bench · benchmark · 90%VirtualHome · dataset · 90%WAH-NL · dataset · 90%XArm7 · robot · 90%

Relation Signals (7)

Meta-Ctrl → evaluatedon → WAH-NL

confidence 95% · We validate Meta-Ctrl on the EAI benchmark... LoTa-Bench [2] (WAH-NL)

Meta-Ctrl → evaluatedon → Embodied Agent Interface

confidence 95% · We validate Meta-Ctrl on the EAI benchmark [9] (VirtualHome and BEHAVIOR)

Meta-Ctrl → improves → Llama-3-8B

confidence 95% · With it, a small open-weight LM becomes competitive... an open-weight LM (Llama 3 8B) surpasses every model on the EAI leaderboard

Meta-Ctrl → uses → meta-tokens

confidence 95% · Meta-Ctrl introduces meta-tokens—a compact vocabulary of grounded actions—enforcing syntax at the token level and semantics... at the action level

Meta-Ctrl → outperforms → GPT-4

confidence 90% · on WAH-NL under the LoTa-Bench protocol it reaches the highest reported subgoal success rate, exceeding GPT-4’s

Meta-Ctrl → reducesmemoryusageof → constrained_decoding

confidence 90% · an exact factorization that cuts the memory of constrained decoding from over 107TB to under 2GB.

Ctrl-G → isbasefor → Meta-Ctrl

confidence 85% · We bring formally guaranteed constrained decoding to robot planning via Ctrl-G... We present Meta-Ctrl, a two-level constrained-decoding framework

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:LLMs generate fluent plans for robots but routinely violate the syntactic and se8mantic constraints they must satisfy to execute, and existing remedies trade formal guarantees against plan quality: soft methods (affordance scoring, grounded decoding) give no guarantee, while symbolic planners (LLM+P) discard the LM's commonsense. We propose \textbf{Meta-Ctrl}, a constrained-decoding framework that guarantees the encoded constraints while preserving the base LM's plan quality. Meta-Ctrl introduces \emph{meta-tokens}---a compact vocabulary of grounded actions---enforcing syntax at the token level and semantics (preconditions, goals, ordering) at the action level, an exact factorization that cuts the memory of constrained decoding from over 107TB to under 2GB. With it, a small open-weight LM becomes competitive where it otherwise sits at the bottom of the leaderboard: on WAH-NL under the LoTa-Bench protocol it reaches the highest reported subgoal success rate, exceeding GPT-4's, with consistent gains across the Embodied Agent Interface. We further demonstrate it on a real tabletop robot, where every generated plan satisfies its preconditions and goals by construction. Project website: this https URL.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

86,483 characters extracted from source content.

Expand or collapse full text

Meta-Ctrl: Guaranteed Plan Generation by Decoupling Syntactic and Semantic Constraints Gwen Yidou-Weng Edward Sun Tianyi Ma Affiliation: Michigan State Universitygwenweng,edwardsun12895@ucla.eduguyvdb,yuchencui@cs.ucla.edu Metin Alp Dogan Benjie Wang Allen Peng Guy Van den Broeck Yuchen Cui [4pt] University of California Los Angeles [2pt] Equal contribution Abstract LLMs generate fluent plans for robots but routinely violate the syntactic and semantic constraints they must satisfy to execute, and existing remedies trade formal guarantees against plan quality: soft methods (affordance scoring, grounded decoding) give no guarantee, while symbolic planners (LLM+P) discard the LM’s commonsense. We propose Meta-Ctrl, a constrained-decoding framework that guarantees the encoded constraints while preserving the base LM’s plan quality. Meta-Ctrl introduces meta-tokens—a compact vocabulary of grounded actions—enforcing syntax at the token level and semantics (preconditions, goals, ordering) at the action level, an exact factorization that cuts the memory of constrained decoding from over 107107 TB to under 22 GB. With it, a small open-weight LM becomes competitive where it otherwise sits at the bottom of the leaderboard: on WAH-NL under the LoTa-Bench protocol it reaches the highest reported subgoal success rate, exceeding GPT-4’s, with consistent gains across the Embodied Agent Interface. We further demonstrate it on a real tabletop robot, where every generated plan satisfies its preconditions and goals by construction. Project website: https://meta-ctrlg.github.io/ Keywords: Constrained Decoding, Formal Guarantees, Task and Motion Planning 1 Introduction Large language models (LLMs) are increasingly used to generate action plans for robots, mapping natural-language instructions to sequences of grounded actions [1, 10, 20, 8, 6, 7]. On long-horizon household tasks in environments such as VirtualHome [17] and BEHAVIOR [21], these plans violate constraints at high rates: hallucinated objects, precondition failures, missing steps, and incorrect orderings [9, 22]. The failures are of two kinds: syntactic (malformed output: invalid actions, wrong argument structure, ill-formed formatting) and semantic (well-formed but physically infeasible or goal-violating, such as placing an ungrasped object or skipping a required precondition). Existing methods mitigate these failures but rarely provide both formal guarantees and high plan quality. Affordance scoring [1] and grounded decoding [7] reshape the LM’s output distribution with feasibility scores or environment models, but the guidance is soft. Infeasible outputs can still be generated. Replanning with execution feedback [8, 23] retries after failures, with no termination guarantee and compounding cost. Active knowledge acquisition [12] learns missing task information by interaction; it is complementary to enforcing constraints already known, and could supply the learned constraint extractors our limitations call for. LLM+P [11] hands planning to a PDDL solver, trading the LM’s commonsense for a full domain specification. A separate line of work guarantees validity by construction. Grammar-constrained decoding (GCD) [16, 4, 24], the closest to ours, masks at each decoding step any token that would violate the grammar. But the mask is local and admits any token compatible with some valid completion, regardless of whether the remaining sequence is likely or satisfies longer-range constraints, which can sharply distort the LM’s distribution [15], yielding valid but improbable outputs, exactly when LM likelihood tracks plan plausibility. Avoiding this requires reasoning about the full remaining sequence, not just the next token. Ctrl-G [25] does so while keeping the guarantee: it weights each token by a tractable estimate of the probability that the full completion will satisfy the constraint, recovering the LM’s distribution conditioned on satisfaction. Applied to syntax, it yields guaranteed well-formed plans directly. Figure 1: Meta-Ctrl enforces preconditions that the base LM violates. Task: put dishes in dishwasher; PUTIN requires holding an object and an open container. The base LM (top) attempts PUTIN while the dishwasher is closed. Meta-Ctrl (bottom) enforces the action-level precondition, inserting OPEN(dishwasher). Enforcing semantic constraints on top of syntax is substantially harder: semantic validity depends on the evolving world state (e.g. whether an object has been grasped before it is placed), not just each action’s surface form. The naïve fix (compiling syntax and semantics into a single token-level DFA) has a state space that scales as the product of the two, exceeding 350350M states and requiring 107107 TB of memory for a typical task. This is wasteful: semantics depends only on which actions occur and in what order, not on token-level formatting. It motivates factoring constraint enforcement across granularities: syntax at the token level, semantics at the action level. We introduce Meta-Ctrl, a two-level constrained-decoding framework built around meta-tokens: a compact action-level representation that lets syntax be enforced over tokens and semantics over actions (Fig. 1). Because the two levels can be aligned exactly, the joint constraint decouples into two independent subproblems, yielding a 1,900×1,900× reduction in compute and a 67,000×67,000× reduction in memory over the monolithic approach. Empirically, this turns a small open-weight LM into a competitive planner that matches or exceeds models an order of magnitude larger (Section 4). Our contributions are: • We bring formally guaranteed constrained decoding to robot planning via Ctrl-G, enforcing syntactic constraints with provable validity. • We present Meta-Ctrl, a two-level constrained-decoding framework that decouples token-level syntax from action-level semantics via meta-tokens, an exact factorization of the joint constraint. • We validate Meta-Ctrl on the EAI benchmark [9] (VirtualHome and BEHAVIOR), LoTa-Bench [2] (WAH-NL), and a real tabletop robot: on VirtualHome action sequencing, an open-weight LM (Llama 3 8B) surpasses every model on the EAI leaderboard, including the 8×8× larger Llama 3 70B and frontier closed models such as GPT-4o, Claude 3.5 Sonnet, and o1-preview. 2 Preliminaries: Ctrl-G Constrained decoding as probabilistic reasoning. Ctrl-G [25] formulates constrained decoding as probabilistic reasoning over logical constraints. Given an LM and a constraint α (e.g. valid JSON, or containing a keyphrase), we sample from pLM(x1:n∣α)p_LM(x_1:n α); decomposing autoregressively, pLM(xt∣x<t,α)∝pLM(xt∣x<t)⋅pLM(α∣x≤t).p_LM(x_t x_<t,α)\; \;p_LM(x_t x_<t)\;·\;p_LM(α x_≤ t). (1) The first factor is the LM’s next-token distribution; the second, pLM(α∣x≤t)p_LM(α x_≤ t), is the probability that the full sequence will satisfy α given the current prefix. Rather than a hard mask that treats all locally compatible tokens equally—and so can commit to a token from which every completion is a dead end—this term reweights each token by the probability that it leads to a constraint-satisfying completion. The reweighting (i) assigns zero probability to tokens with no valid completion, so constraint satisfaction is guaranteed, and (i) among valid tokens, prefers those leading to natural, high-probability completions under the LM, preserving fluency. Tractable lookahead via HMM and DFA. Computing pLM(α∣x≤t)p_LM(α x_≤ t) exactly is intractable, as it marginalizes over all future sequences that satisfy α. Ctrl-G trains a Hidden Markov Model pHMM(x1:n)≈pLM(x1:n)p_HMM(x_1:n)≈ p_LM(x_1:n) and substitutes pHMM(α∣x≤t)p_HMM(α x_≤ t): pctrl(xt∣x<t,α)∝pLM(xt∣x<t)⋅pHMM(α∣x≤t).p_ctrl(x_t x_<t,α)\; \;p_LM(x_t x_<t)\;·\;p_HMM(α x_≤ t). (2) The guarantee is preserved—pHMM(α∣x≤t)=0p_HMM(α x_≤ t)=0 wherever no continuation satisfies α—so the HMM affects only the reweighting among valid tokens, and a more accurate HMM yields generations that are both constraint-satisfying and natural. To evaluate the lookahead, α is represented as a deterministic finite automaton (DFA) αD_α that reads tokens left to right and accepts in a final state: a natural match for autoregressive decoding, composable by intersection and union, with size |||D| measured in edges. The HMM and DFA are both finite-state, so their product is a finite-state model over (hidden state, DFA state) pairs, admitting a backward dynamic program (DP) that returns pHMM(α∣x≤t)p_HMM(α x_≤ t) for every prefix; for length n, H hidden states, and DFA size |||D|, it costs O⁡(n⋅||⋅H2)O(n·|D|· H^2). Ctrl-G was demonstrated on constraints with small DFAs (keywords, length, infilling); for compositional constraints the standard product of DFAs has edge count |1|⋅|2||D_1|·|D_2|, so the DP cost scales multiplicatively—the bottleneck we address next. 3 Decoupling Syntax and Semantics for Constrained Decoding Embodied plans must satisfy two kinds of constraints at different granularities: a token-level syntactic constraint γ (valid action names, argument structure, well-formed JSON) and an action-level semantic constraint β (goal achievement, preconditions, temporal ordering among grounded actions). We enforce each at its natural level, applying Ctrl-G first to syntax (Section 3.1), then extending to semantics through a meta-token projection (Section 3.2), and finally showing why factoring across the two levels is both necessary and beneficial (Section 3.3). 3.1 Level 1: Token-Level Syntax The syntactic constraint is naturally a token-level DFA γD_γ that accepts well-formed action blocks: valid action names, correct argument arity and types, and proper JSON structure. Applying Ctrl-G with γD_γ steers generation toward syntactically valid output: p⁡(xt∣x<t,γ)∝pLM(xt∣x<t)⋅pHMM(γ∣x≤t).p(x_t x_<t,γ)\; \;p_LM(x_t x_<t)\;·\;p_HMM(γ x_≤ t). (3) This eliminates malformed output entirely: the raw LM frequently emits prose (e.g. ‘To solve this, the action is TYPE…’), invalid action names, or ill-formed arguments, whereas every Level-1 output parses into a valid action sequence (e.g. "WALK":["computer"],"GRAB":["mouse"]). Syntax is not enough. A syntactically valid plan can still be semantically wrong: it may attempt to place an object before grasping it, open a container that is already open, or terminate before achieving the goal. These errors naturally live at the action level, not the token level. We therefore need a second constraint that reasons about the action sequence as a whole. 3.2 Level 2: Action-Level Semantics via Meta-Tokens To enforce semantics, we lift generation to the action level. We introduce a vocabulary W of meta-tokens, each a grounded action (e.g., Open(dishwasher)), and a parser τ:suppγ→∗τ:supp_γ ^* that maps each syntactically valid token sequence to its action sequence, much as a tokenizer maps characters to tokens (Figure 2). The semantic constraint β is then a DFA over meta-tokens that tracks task-relevant state (which actions have occurred, whether preconditions hold, whether the goal is reached). We assume τ is a bijection on suppγsupp_γ, so every action sequence has a unique token realization τ−1(w)τ^-1(w).11 1 For each action sequence to have exactly one token sequence, we fix a deterministic canonical tokenizer (typically shipped with the LM) and let γ admit only canonically-tokenized sequences. Then τ is one-to-one. The joint constraint is x⊧α⇔(x⊧γ)∧(τ⁡(x)⊧β).x α\; \;(x γ)\; \;(τ(x) β). (4) tokens["GRAB":plate,…project via τ , dish.β DFAclosedopengoalOpenClosePut plate in Figure 2: Level 2: action-level semantics. The parser τ projects each action block of tokens (e.g. "GRAB":"plate") to one meta-token (Grab(plate)). A DFA βD_β over meta-tokens enforces preconditions and goal progress (e.g. Put requires the container open). Operating on a small action vocabulary, rather than raw tokens, is what makes the factored computation below tractable. Factored posterior. At decoding step t, let a<l=τinc(x≤t)a_<l= _inc(x_≤ t) be the completed action history, where τinc _inc returns the actions parsed so far. Marginalizing the joint posterior over the identity of the current action, p⁡(α∣x≤t)=∑alp⁡(al∣x≤t)⏟bridging⋅p⁡(γ∣x≤t,al)⏟syntax⋅p⁡(β∣x≤t,al,γ)⏟semantics.p(α x_≤ t)= _a_l p(a_l x_≤ t)_bridging· p(γ x_≤ t,a_l)_syntax· p(β x_≤ t,a_l,γ)_semantics. (5) The semantics term still couples both granularities. We decouple it using the bijectivity of τ on suppγsupp_γ. Define the induced meta-token distribution pmeta(w):=pLM(τ−1(w)|γ),p_meta(w)\;:=\;p_LM\! (τ^-1(w)\, |\,γ ), (6) which is well-defined because τ−1(w)τ^-1(w) is a unique token sequence in suppγsupp_γ for each w∈∗w ^*. Conditional on the completed actions a<la_<l, the candidate next action ala_l, and the syntactic constraint γ, the token-level prefix x≤tx_≤ t carries no further information about the meta-token sequence: a<la_<l together with ala_l fixes the prefix of meta-tokens, which by bijectivity fixes the prefix of tokens up to the canonical tokenization that γ enforces. Hence p⁡(β|x≤t,al,γ)=pmeta(β|a≤l),p\! (β\, |\,x_≤ t,a_l,γ )\;=\;p_meta\! (β\, |\,a_≤ l ), (7) and substituting into Eq. 5 yields the fully factored posterior p⁡(α∣x≤t)=∑alp⁡(al∣x≤t)⏟bridging⋅p⁡(γ∣x≤t,al)⏟syntax(token-level)⋅pmeta(β∣a≤l)⏟semantics(action-level).p(α x_≤ t)= _a_l p(a_l x_≤ t)_bridging· p(γ x_≤ t,a_l)_ subarraycsyntax\\ (token-level) subarray· p_meta(β a_≤ l)_ subarraycsemantics\\ (action-level) subarray. (8) Syntax is enforced purely at the token level and semantics purely at the action level, communicating through the bridging term p⁡(al∣x≤t)p(a_l x_≤ t), which maps the current partial token sequence to a distribution over the action it commits to. The decoupling is exact and requires no assumption on the LM beyond bijectivity of τ. Algorithm 1 (Appendix B) summarizes the resulting two-level decoder. 3.3 Why Two Levels? Enforcing β and γ jointly in a single DFA would require lifting β to the token level and intersecting with γ, producing a joint DFA whose state space is the product of the two (Appendix A). Factoring keeps the levels separate: it replaces that multiplicative state space with an additive one, advances the semantic DP at the action rather than token granularity, and lets the meta-token HMM concentrate on a small action vocabulary instead of the syntactic variation γ already handles. The result is both cheaper and a better surrogate (Table 1). This yields a lower per-action NLL surrogate, and a more accurate surrogate produces higher-quality plans among the constraint-satisfying set (Section 2). The factorization also separates the pipeline’s cheap and expensive parts: each task’s constraints live in DFAs that compile in seconds and swap freely, while the costly trained HMMs are few and shared, one meta-token HMM per module type and one token-level HMM per base LM (Appendix D). Table 1: Why two levels: factoring the joint constraint is both cheaper and produces a better surrogate. Numbers are for a median VirtualHome task (H=128H=128); see Section 4 for the quality ablation. Both −log⁡p- p columns are per grounded action; sequence length is raw tokens (42.7) for the token HMM and grounded actions (7.6) for the meta-token HMM. Efficiency Monolithic Two-level States Sγ×SβS_γ×S_β Sγ+SβS_γ+S_β 350 M 57 K Compute 1,720 T 922 G DP memory 107 TB 1.6 GB ∼1,900× 1,900× faster, ∼67,000× 67,000× less memory Quality Token HMM Meta-token HMM Vocab 128 K 132 Emission 16.4 M 16.9 K Seq. length 42.7 7.6 −log⁡p- p/act. 33.54 2.01 ∼16.7× 16.7× better fit 4 Experiments We evaluate Meta-Ctrl on three planning benchmarks and on a real XArm7 tabletop robot (Section 4.4). A lookahead ablation isolates probabilistic reweighting as the source of the gains, and an analysis (Appendix I) explains where Meta-Ctrl helps most. 4.1 Setup Benchmarks. We evaluate on three benchmarks. Embodied Agent Interface (EAI) [9] covers VirtualHome (VH) and BEHAVIOR (BEH) over two plan-generation modules, Action Sequencing (AS) and Subgoal Decomposition (SD), yielding four (simulator, module) sets of 342342, 338338, 100100, and 100100 tasks.22 2 The other two EAI modules (Goal Interpretation, Transition Modeling) are structured-prediction tasks whose failure modes are missing or misinterpreted predicates, which constraint enforcement cannot supply. Watch-And-Help (WAH-NL) [18], under the LoTa-Bench protocol [2], provides 100100 single-agent tasks across five families with a stricter symbolic executor than EAI. Each task provides an instruction and a structured scene description and is scored by the official evaluator on goal satisfaction and executability. We also deploy on a real XArm7 tabletop with open-vocabulary perception and downstream execution modules (Section 4.4). Base LMs and baselines. On EAI, we evaluate Meta-Ctrl on two open-weight base models, Llama-3-8B-Instruct [5] and gpt-oss-20B [14]; on WAH-NL, we use Llama-3.1-8B-Instruct [5]. We compare against all 14 EAI leaderboard models [9] and, on WAH-NL, published numbers for SayCan [1], ProgPrompt [20], LoTa-Bench [2], and STEP [26]. For internal comparison we also report each base LM unconstrained and under a hard-masking variant of the syntactic DFA. Metrics. We report Task SR (fraction of plans achieving the goal) and Exec SR (fraction executing to completion in the simulator); WAH-NL additionally reports SSR, the fraction of subgoals satisfied. Real-robot metrics are defined in Section 4.4. Meta-Ctrl configuration. We build a syntactic DγD_γ and a semantic DβD_β per (benchmark, module) pair and induce τ from DγD_γ. The trained HMMs are shared across pairs rather than built per task; Appendix D gives the sharing structure and training details. All train on unconstrained base-LM generations matching the benchmark format but containing no evaluation instance. Decoding is greedy under Eq. 8 with a 40-action horizon for the semantic DP; provably infeasible tasks fall back to γ-only. 4.2 Watch-And-Help via LoTa-Bench Table 2: WAH-NL (single-agent, n=100n=100) under the LoTa-Bench protocol. External references use different LMs and executors; we report them as ballpark context, not strict baselines. Empty entries are not reported. Same-LM rows (Llama 3.1 8B) are direct comparisons. †STEP is closed-loop; ours is open-loop. Method Base LM SR SSR Exec External references (different LM / executor) SayCan — 0.010 0.021 — ProgPrompt — 0.030 0.187 — LoTa-Bench GPT-4 — 0.342 — LoTa-Bench LLaMA-1 65B — 0.433 — STEP† (larger) 0.400 0.620 — Same LM (Llama 3.1 8B), same evaluator, n=100n=100 Raw LM (unconstrained) Llama 3.1 8B 0.000 0.022 0.010 + syntax Llama 3.1 8B 0.000 0.037 0.010 Meta-Ctrl Llama 3.1 8B 0.470 0.705 1.000 Constrained decoding turns an unusable LM into a deployable one, and semantic control drives the gain. Llama-3.1-8B alone solves none of the 100100 tasks (SR 0.0000.000, Exec 0.0100.010); its raw outputs are already mostly well-formed at the token level, so syntactic control alone (+γ+γ) raises SSR by just 1.51.5 points and leaves Exec at 0.0100.010. Adding semantic control (full Meta-Ctrl) lifts SSR a further 66.866.8 points and Exec by 9999, reaching SR 0.4700.470, SSR 0.7050.705, Exec 1.0001.000. On the same LM and evaluator, task success goes from 00 to 0.470.47, and semantic control accounts for nearly all of it. On the SSR axis comparable across protocols, Meta-Ctrl (0.7050.705) exceeds LoTa-Bench’s strongest reported configuration (LLaMA-1-65B, 0.4330.433; GPT-4, 0.3420.342) and the closed-loop STEP baseline (0.6200.620).33 3 Prior WAH-NL evaluations use natural-language instruction inputs and a Unity simulator; the LoTa-Bench protocol [2] uses oracle-goal inputs and a strict symbolic executor. SSR-to-SSR is the comparable axis across protocols. The constraint enforces the invariants that prompting baselines violate. Examining where the ProgPrompt baseline’s plans fail under the same executor: 6060 of 100100 fail at Grab, 2121 at PutIn, 1010 at PutBack. The failures are precondition violations (hands already full, target not co-located, container closed), not formatting or hallucination. Meta-Ctrl’s β DFA tracks these invariants at every decoding step, and enforcing them during generation, instead of checking them after the plan is produced, is what yields the 0→1.0000→ 1.000 execution rate. 4.3 Embodied Agent Interface Table 3: Embodied Agent Interface results on VirtualHome (V; n=342n=342 AS, 338338 SD) and BEHAVIOR (B; n=100n=100 AS, 100100 SD). Task SR and Execution SR (%). Leaderboard baselines from [9]; Each base LM is grouped with its full Meta-Ctrl (γ+βγ+β) result. Bold: best per column; underline: second-best. ‡The gpt-oss rows use a keyword-based BEHAVIOR affordance prior; the Llama rows use the taxonomy-derived specification of Appendix G. Our VirtualHome cells are means over six evaluator seeds (Appendix K). Action Sequencing Subgoal Decomposition Task SR Exec SR Task SR Exec SR Model VH BEH VH BEH VH BEH VH BEH Representative baselines GPT-4o 71.5 47.0 81.3 53.0 87.6 49.0 91.1 55.0 Claude-3.5 Sonnet 76.1 60.0 81.3 69.0 89.1 39.0 92.0 44.0 o1-preview 65.2 81.0 72.5 91.0 89.4 60.0 93.2 62.0 Mistral Large 78.4 33.0 84.6 50.0 84.3 31.0 92.0 38.0 Llama 3 70B Instruct 59.0 34.0 66.6 42.0 78.4 21.0 87.3 30.0 Llama 3 8B Instruct (base) 21.3 10.0 23.6 16.0 48.8 22.0 58.0 29.0 + Meta-Ctrl (ours) 90.4 34.0 97.7 89.0 89.9 36.0 93.5 66.0 gpt-oss-20B (base) 74.4 40.0 80.3 51.0 72.5 27.0 82.2 36.0 + Meta-Ctrl (ours)‡ 86.6 40.0 94.1 90.0 82.3 41.0 86.4 66.0 Meta-Ctrl lifts open-weight LMs to match frontier closed-weight models on VirtualHome. On Llama-3-8B-Instruct, Meta-Ctrl raises task SR from 21.321.3 to 90.490.4 on VH Action Sequencing and from 48.848.8 to 89.989.9 on Subgoal Decomposition (Table 3); on gpt-oss-20B, it raises VH AS from 74.474.4 to 86.686.6. Both lifted numbers exceed every model on the EAI leaderboard, including o1-preview (65.265.2 on VH AS), Claude 3.5 Sonnet (76.176.1), and Mistral Large (78.478.4). On BEHAVIOR the task-SR lift is positive but smaller (Llama-3-8B: 10→3410→ 34 on AS, 22→3622→ 36 on SD; gpt-oss: 40→4040→ 40 on AS, 27→4127→ 41 on SD), while the execution-SR lift stays large (16→8916→ 89 on AS, 29→6629→ 66 on SD): enforcing the constraints removes the failures that stop a plan from running, but achieving a BEHAVIOR goal also needs world knowledge the prompt withholds (Appendix I). Constrained decoding closes the gap between an 88B open-weight LM and the strongest proprietary models on VirtualHome and brings a 2020B open-weight LM above all of them. Meta-Ctrl works best when the prompt specifies the task’s constraints. The gap between VirtualHome and BEHAVIOR shows when Meta-Ctrl helps most. VirtualHome prompts describe each object’s properties and states directly, so the DFA can encode 82%82\% of the task’s preconditions from the prompt alone; BEHAVIOR prompts do not, and the DFA can encode only 24%24\% from the prompt (Appendix I). For BEHAVIOR the remainder comes from the benchmark’s public BDDL object taxonomy, looked up by the synsets the prompt already names, plus five documented generic rules (Appendix G); this is still strictly less than the complete transition model the benchmark hands its own planner baselines. The method recovers the most when a task’s constraints can be made explicit and written into the DFA. Table 4: Porting Meta-Ctrl to newer base LMs, VH AS (n=342n=342), task / execution SR (%). Each port rebuilds γ over the new tokenizer automatically and uses a uniform token-level HMM over the new vocabulary; the meta level is unchanged (uniform meta-surrogate rows for all three bases). No training of any kind. VH-AS means over six evaluator seeds. Base LM unconstrained + Meta-Ctrl changed lines Llama 3 8B Instruct 21.3 / 23.6 90.7 / 97.7 — Qwen3-8B 50.8 / 58.4 90.7 / 97.7 ∼40 40 Gemma-3-12B-it 47.5 / 50.5 89.4 / 96.1 ∼35 35 The construction transfers to new base LMs without training. The token-level HMM turns out to be nearly inert once β is present: replacing the trained one with a uniform HMM over the same vocabulary leaves 273273 of 342342 VH AS programs byte-identical, and the 6969 that differ swap tie-broken synonym verbs (4141 of them Find↔ ), moving task SR by −0.7-0.7. Since γ is compiled from the prompt over whatever tokenizer the base model uses, and the meta level is defined over grounded actions rather than tokens, porting to a new base LM needs no retraining at either level. We ported to two 2025 open-weight models spanning two tokenizer families, Qwen3-8B (byte-level BPE, 152152K) and Gemma-3-12B-it (SentencePiece, 262262K), in well under 100100 changed lines each, and both reproduce the pattern: both task and execution SR transfer exactly on Qwen3 (90.790.7/97.797.7, tying the Llama pipeline), and the guarantee transfers with zero parsing and zero affordance errors on both (Table 4). Table 5: What each component contributes, task / execution SR (%) on Llama 3 8B. Rows 3–6 share the same constraint construction (meta-tokens, γ and β compiled from the prompt and the public object taxonomy) and the same guarantee; they differ only in the guidance signal. Search, no LLM is breadth-first search over the meta-level automaton with the LM removed. Masking keeps only the support of the lookahead term, a reachability yes/no. Uniform and trained instantiate the lookahead measure itself. Classical planner is Fast Downward given the benchmark’s own PDDL domain, i.e. a complete transition model, strictly more information than our automata encode; SD asks for goal states rather than actions, so planners do not apply. Method (Llama 3 8B) VH AS VH SD BEH AS BEH SD LLM only (unconstrained) 21.3 / 23.6 48.8 / 58.0 10 / 16 22 / 29 LLM + syntax-only GCD (γ mask) 1.4 / 97.3 0.0 / 96.0 12 / 20 19 / 31 Classical planner, full domain 47.2 / 84.6 n/a 13 / 37 n/a with our meta-level automata: Search, no LLM 83.8 / 93.1 72.5 / 79.0 31 / 77 52 / 64 LLM + masking (reachability only) 81.7 / 87.5 88.7 / 92.6 33 / 85 38 / 51 LLM + uniform lookahead 90.7 / 97.7 88.4 / 93.2 36 / 89 41 / 59 LLM + trained lookahead (Meta-Ctrl) 90.4 / 97.7 89.9 / 93.5 34 / 89 36 / 66 Guarantees. Format and hallucination errors that account for 24%24\% of raw Llama-3-8B outputs on BEH AS (15%15\% hallucinated objects, 9%9\% malformed parameters) drop to 0%0\% under Meta-Ctrl by construction; the same pattern holds on VH AS, where the LM’s 22.3%22.3\% combined error rate becomes 0%0\% LM-fault under Meta-Ctrl (Appendix H reports the per-module breakdown). The guarantee eliminates the failure modes that account for the majority of grammar errors at this scale. Semantic constraints and probabilistic lookahead each carry part of the gain. Table 5 separates them. Syntax-only masking, the standard grammar-constrained setup, collapses task success while inflating execution (1.41.4 task at 97.397.3 execution on VH AS): the greedy LM steers toward the shortest well-formed continuation, which executes cleanly and achieves nothing. The decoding target is p⁡(a∣constraint satisfiable)∝pLM(a)⋅P⁡(satisfiable future∣a)p(a satisfiable) p_LM(a)· P(satisfiable future a), and the second factor is a probability; masking, uniform, and trained lookaheads are successive approximations of it. Masking keeps only its support, a reachability yes/no that tells the LM nothing about the future: under identical γ+βγ+β automata it reaches 81.781.7 on VH AS, no better than searching the automaton with no LM at all. The uniform lookahead scores each step by the accepting future it preserves and reaches 90.790.7, cutting hallucination 6.2%→1.6%6.2\%→ 1.6\% and missing steps 3.3%→0.7%3.3\%→ 0.7\% and raising execution to 97.797.7. On VH SD, where the automaton already pins the answer down, the measure adds nothing, exactly as this decomposition predicts. Representative masking outputs appear in Appendix F. The LM and the automaton are both load-bearing. Search over the compiled automaton with no LM is already strong (83.883.8 on VH AS), an honest measure of how much structure the constraints carry; the LM contributes grounding and ordering common sense worth +6.9+6.9 on VH AS and +16+16 on VH SD, and the failures it removes are groundings no person would pick. In the other direction, a classical planner given the benchmark’s own full PDDL domain, strictly more information than our automata encode, solves nearly every problem it is posed yet scores 1313/3737 on BEH AS and 47.247.2/84.684.6 on VH AS: wherever its model or goal language falls short of the evaluated environment it returns confidently wrong plans, while encoding constraints rather than a world model degrades gracefully when knowledge is incomplete. The trained surrogate is the full model the derivation calls for; uniform is its zero-training approximation. The trained HMM approximates the LM’s own distribution over futures, and it delivers the best execution SR on three of the four modules. On task success the uniform surrogate matches or slightly exceeds it, and the reason is a measurable bias rather than an equivalence: this benchmark’s mandatory but rare actions almost never appear in the LM’s unconstrained outputs (Sleep and PlugIn occur zero times in ∼108 10^8 sampled tokens), so a faithful surrogate assigns them near-zero mass and fines exactly the steps the constraints exist to enforce; the uniform surrogate is immune by construction. Training thus pays where the automaton leaves many admissible futures and the corpus covers them, and costs little where it does not; Appendix D quantifies both directions. 4.4 Real Robot Demonstrations Figure 3: Real robot setup with xArm 7 and deployed tabletop manipulation tasks. Top-row tasks require only pick-and-place; bottom-row tasks require specialized motion primitives (e.g. open door). We deploy Meta-Ctrl on a tabletop XArm7 with a calibrated Realsense RGB-D camera, composing Meta-Ctrl plans with a Code-as-Policies executor [10] that grounds objects via Molmo [3] and SAM2 [19] and synthesizes grasps via GraspGen [13]. We demonstrate 8 BEHAVIOR-derived long-horizon manipulation tasks (Fig. 3) and quantitatively evaluate 3 pick-and-place tasks over 20 rollouts each. Table 6: Real robot evaluations on an XArm7, 2020 repetitions per task. Meta-Ctrl columns are a cascade: plan success holds by construction; perception and execution are conditional on preceding stages. Baseline perception is scored per-module, independent of plan validity; its execution is end-to-end and bounded by planning failures. Baseline downstream columns are thus not directly comparable to Meta-Ctrl’s. Meta-Ctrl (ours) Baseline (Llama 3 8B) Task Planning Perception Execution Planning Perception Execution Put donut in canister 20/20 17/20 16/20 2/20 18/20 1/20 Pick up green block (under blocker) 20/20 19/20 18/20 1/20 19/20 1/20 Stack dishes by size 20/20 20/20 17/20 0/20 19/20 0/20 Meta-Ctrl achieves 100%100\% plan validity by construction, including the multi-step precondition sequences needed for articulated containers. The unconstrained baseline routinely skips these preconditions—Place into a closed container, Grasp on an occluded object, or Grasp while holding another object—so its failures concentrate at planning. Meta-Ctrl’s remaining failures occur downstream, at perception or grasp execution, isolating cleanly from planning errors. Representative rollouts and baseline precondition violations appear in Appendix J. 5 Conclusion We presented Meta-Ctrl, a constrained-decoding framework that guarantees LLM-generated plans satisfy their encoded syntactic and semantic constraints by decoupling enforcement across granularities via meta-tokens. Across EAI, WAH-NL, and a real tabletop robot, Meta-Ctrl turns a small open-weight LM into a competitive planner that matches or exceeds models an order of magnitude larger, with every output constraint-satisfying by construction. Limitations. Meta-Ctrl assumes both constraints are DFA-expressible: syntax over tokens, semantics over meta-tokens. Constraints requiring unbounded memory (e.g., arbitrary arithmetic over continuous quantities) fall outside this class. The semantic DFA is built per task family from a structured specification; our experiments use the simulator’s predicates and, on BEHAVIOR, the benchmark’s published object taxonomy (Appendix G). Domains without such a published specification will need learned constraint extractors or more permissive constraints, and the guarantee then holds relative to whatever the extractor recovers. On a real system the automaton is initialised from the perception-estimated symbolic state, so the guarantee is relative to the robot’s believed state rather than the true one; carrying a belief over automaton states, rather than a single state, is the natural extension. The guarantee is likewise relative to the encoded constraint, and an incomplete specification can over-constrain: on BEHAVIOR our fixed affordance prior rejects 17%17\% of gold plans (Appendix G), with infeasible tasks falling back to γ-only decoding. Real-robot goal success is bounded by perception and grasping, not the planner; closing that gap is orthogonal to plan generation. Finally, HMM surrogates are shared across simulators (Appendix D) but trained per module type; a single surrogate spanning module types and base models remains future work. References [1] M. Ahn, A. Brohan, N. Brown, Y. Chebotar, O. Cortes, B. David, C. Finn, C. Fu, K. Gopalakrishnan, K. Hausman, A. Herzog, D. Ho, J. Hsu, J. Ibarz, B. Ichter, A. Irpan, E. Jang, R. J. Ruano, K. Jeffrey, S. Jesmonth, N. Joshi, R. Julian, D. Kalashnikov, Y. Kuang, K. Lee, S. Levine, Y. Lu, L. Luu, C. Parada, P. Pastor, J. Quiambao, K. Rao, J. Rettinghouse, D. Reyes, P. Sermanet, N. Sievers, C. Tan, A. Toshev, V. Vanhoucke, F. Xia, T. Xiao, P. Xu, S. Xu, M. Yan, and A. Zeng (2022) Do as i can and not as i say: grounding language in robotic affordances. In arXiv preprint arXiv:2204.01691, Cited by: §1, §1, §4.1. [2] J. Choi, Y. Yoon, H. Ong, J. Kim, and M. Jang LoTa-bench: benchmarking language-oriented task planners for embodied agents. In The Twelfth International Conference on Learning Representations, Cited by: 3rd item, §4.1, §4.1, footnote 3. [3] M. Deitke, C. Clark, S. Lee, R. Tripathi, Y. Yang, J. S. Park, M. Salehi, N. Muennighoff, K. Lo, L. Soldaini, et al. (2025) Molmo and pixmo: open weights and open data for state-of-the-art vision-language models. In Proceedings of the Computer Vision and Pattern Recognition Conference, p. 91–104. Cited by: §4.4. [4] Y. Dong, C. F. Ruan, Y. Cai, Z. Xu, Y. Zhao, R. Lai, and T. Chen (2025) Xgrammar: flexible and efficient structured generation engine for large language models. Proceedings of Machine Learning and Systems 7. Cited by: §1. [5] A. Grattafiori, A. Dubey, A. Jauhri, A. Pandey, A. Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Vaughan, et al. (2024) The llama 3 herd of models. arXiv preprint arXiv:2407.21783. Cited by: §4.1. [6] W. Huang, P. Abbeel, D. Pathak, and I. Mordatch (2022) Language models as zero-shot planners: extracting actionable knowledge for embodied agents. In International conference on machine learning, p. 9118–9147. Cited by: §1. [7] W. Huang, F. Xia, D. Shah, D. Driess, A. Zeng, Y. Lu, P. Florence, I. Mordatch, S. Levine, K. Hausman, et al. (2023) Grounded decoding: guiding text generation with grounded models for embodied agents. Advances in Neural Information Processing Systems 36, p. 59636–59661. Cited by: §1, §1. [8] W. Huang, F. Xia, T. Xiao, H. Chan, J. Liang, P. Florence, A. Zeng, J. Tompson, I. Mordatch, Y. Chebotar, et al. (2022) Inner monologue: embodied reasoning through planning with language models. arXiv preprint arXiv:2207.05608. Cited by: §1, §1. [9] M. Li, S. Zhao, Q. Wang, K. Wang, Y. Zhou, S. Srivastava, C. Gokmen, T. Lee, E. L. Li, R. Zhang, et al. (2024) Embodied agent interface: benchmarking llms for embodied decision making. Advances in Neural Information Processing Systems 37, p. 100428–100534. Cited by: Appendix K, Appendix K, 3rd item, §1, §4.1, §4.1, Table 3. [10] J. Liang, W. Huang, F. Xia, P. Xu, K. Hausman, B. Ichter, P. Florence, and A. Zeng (2023) Code as policies: language model programs for embodied control. In 2023 IEEE International conference on robotics and automation (ICRA), p. 9493–9500. Cited by: §1, §4.4. [11] B. Liu, Y. Jiang, X. Zhang, Q. Liu, S. Zhang, J. Biswas, and P. Stone (2023) Llm+ p: empowering large language models with optimal planning proficiency. arXiv preprint arXiv:2304.11477. Cited by: §1. [12] X. Liu, A. Pesaranghader, J. Kim, T. Sadhu, H. Jeon, and S. Sanner (2026) ActiveVOO: value of observation guided active knowledge acquisition for open-world embodied lifted regression planning. Advances in Neural Information Processing Systems 38, p. 106621–106647. Cited by: §1. [13] A. Murali, B. Sundaralingam, Y. Chao, W. Yuan, J. Yamada, M. Carlson, F. Ramos, S. Birchfield, D. Fox, and C. Eppner (2025) Graspgen: a diffusion-based framework for 6-dof grasping with on-generator training. arXiv preprint arXiv:2507.13097. Cited by: §4.4. [14] OpenAI, :, S. Agarwal, L. Ahmad, J. Ai, S. Altman, A. Applebaum, E. Arbus, R. K. Arora, Y. Bai, B. Baker, H. Bao, B. Barak, A. Bennett, T. Bertao, N. Brett, E. Brevdo, G. Brockman, S. Bubeck, C. Chang, K. Chen, M. Chen, E. Cheung, A. Clark, D. Cook, M. Dukhan, C. Dvorak, K. Fives, V. Fomenko, T. Garipov, K. Georgiev, M. Glaese, T. Gogineni, A. Goucher, L. Gross, K. G. Guzman, J. Hallman, J. Hehir, J. Heidecke, A. Helyar, H. Hu, R. Huet, J. Huh, S. Jain, Z. Johnson, C. Koch, I. Kofman, D. Kundel, J. Kwon, V. Kyrylov, E. Y. Le, G. Leclerc, J. P. Lennon, S. Lessans, M. Lezcano-Casado, Y. Li, Z. Li, J. Lin, J. Liss, Lily, Liu, J. Liu, K. Lu, C. Lu, Z. Martinovic, L. McCallum, J. McGrath, S. McKinney, A. McLaughlin, S. Mei, S. Mostovoy, T. Mu, G. Myles, A. Neitz, A. Nichol, J. Pachocki, A. Paino, D. Palmie, A. Pantuliano, G. Parascandolo, J. Park, L. Pathak, C. Paz, L. Peran, D. Pimenov, M. Pokrass, E. Proehl, H. Qiu, G. Raila, F. Raso, H. Ren, K. Richardson, D. Robinson, B. Rotsted, H. Salman, S. Sanjeev, M. Schwarzer, D. Sculley, H. Sikchi, K. Simon, K. Singhal, Y. Song, D. Stuckey, Z. Sun, P. Tillet, S. Toizer, F. Tsimpourlas, N. Vyas, E. Wallace, X. Wang, M. Wang, O. Watkins, K. Weil, A. Wendling, K. Whinnery, C. Whitney, H. Wong, L. Yang, Y. Yang, M. Yasunaga, K. Ying, W. Zaremba, W. Zhan, C. Zhang, B. Zhang, E. Zhang, and S. Zhao (2025) Gpt-oss-120b and gpt-oss-20b model card. External Links: 2508.10925, Link Cited by: §4.1. [15] K. Park, J. Wang, T. Berg-Kirkpatrick, N. Polikarpova, and L. D’Antoni (2024) Grammar-aligned decoding. Advances in Neural Information Processing Systems 37, p. 24547–24568. Cited by: §1. [16] G. Poesia, O. Polozov, V. Le, A. Tiwari, G. Soares, C. Meek, and S. Gulwani (2022) Synchromesh: reliable code generation from pre-trained language models. arXiv preprint arXiv:2201.11227. Cited by: §1. [17] X. Puig, K. Ra, M. Boben, J. Li, T. Wang, S. Fidler, and A. Torralba (2018) Virtualhome: simulating household activities via programs. In Proceedings of the IEEE conference on computer vision and pattern recognition, p. 8494–8502. Cited by: §1. [18] X. Puig, T. Shu, S. Li, Z. Wang, Y. Liao, J. B. Tenenbaum, S. Fidler, and A. Torralba Watch-and-help: a challenge for social perception and human-ai collaboration. In International Conference on Learning Representations, Cited by: §4.1. [19] N. Ravi, V. Gabeur, Y. Hu, R. Hu, C. Ryali, T. Ma, H. Khedr, R. Rädle, C. Rolland, L. Gustafson, et al. (2025) Sam 2: segment anything in images and videos. In International Conference on Learning Representations, Vol. 2025, p. 28085–28128. Cited by: §4.4. [20] I. Singh, V. Blukis, A. Mousavian, A. Goyal, D. Xu, J. Tremblay, D. Fox, J. Thomason, and A. Garg (2022) Progprompt: generating situated robot task plans using large language models. arXiv preprint arXiv:2209.11302. Cited by: §1, §4.1. [21] S. Srivastava, C. Li, M. Lingelbach, R. Martín-Martín, F. Xia, K. E. Vainio, Z. Lian, C. Gokmen, S. Buch, K. Liu, S. Savarese, H. Gweon, J. Wu, and L. Fei-Fei (2021) BEHAVIOR: benchmark for everyday household activities in virtual, interactive, and ecological environments. In 5th Annual Conference on Robot Learning, External Links: Link Cited by: Appendix G, §1. [22] K. Valmeekam, M. Marquez, A. Olmo, S. Sreedharan, and S. Kambhampati (2023) Planbench: an extensible benchmark for evaluating large language models on planning and reasoning about change. Advances in Neural Information Processing Systems 36, p. 38975–38987. Cited by: §1. [23] G. Wang, Y. Xie, Y. Jiang, A. Mandlekar, C. Xiao, Y. Zhu, L. Fan, and A. Anandkumar (2023) Voyager: an open-ended embodied agent with large language models. arXiv preprint arXiv:2305.16291. Cited by: §1. [24] B. T. Willard and R. Louf (2023) Efficient guided generation for large language models. arXiv preprint arXiv:2307.09702. Cited by: §1. [25] H. Zhang, M. Dang, N. Peng, and G. Van den Broeck (2023) Tractable control for autoregressive language generation. In International Conference on Machine Learning, p. 40932–40945. Cited by: §1, §2. [26] T. Zhou, Z. Wang, H. Ao, G. Chen, B. Xing, J. Cheng, Y. Yang, and Y. Yue (2025) STEP planner: constructing cross-hierarchical subgoal tree as an embodied long-horizon task planner. In 2025 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 16731–16738. Cited by: §4.1. Appendix A Construction of the Joint DFA αD_α We give the explicit construction of a token-level DFA αD_α that accepts the joint constraint α⁡(x)=γ⁡(x)∧β⁡(τ⁡(x))α(x)=γ(x) β(τ(x)) from Eq. 4, and bound its size by |γ|⋅|β||D_γ|·|D_β|. This construction is the baseline that our factored approach (Section 3) avoids. Setup. Let γ=(Sγ,V,δγ,sγ0,Fγ)D_γ=(S_γ,V, _γ,s_γ^0,F_γ) be the token-level syntax DFA over the LLM vocabulary V, with states SγS_γ, transition function δγ _γ, initial state sγ0s_γ^0, and accepting states FγF_γ. Let β=(Sβ,,δβ,sβ0,Fβ)D_β=(S_β,W, _β,s_β^0,F_β) be the meta-token-level semantic DFA over W, with the analogous components. The parser τ:suppγ→∗τ:supp_γ ^* maps each completed action block in suppγsupp_γ to a single meta-token in W. Let γ⊆SγC_γ S_γ denote the subset of γD_γ states at which an action block has just been completed (i.e., states reached by the token that closes the block). Construction. We construct αD_α as follows: • States: Sα=Sγ×SβS_α=S_γ× S_β. • Initial state: (sγ0,sβ0)(s_γ^0,s_β^0). • Transition function. For each (qγ,qβ)∈Sα(q_γ,q_β)∈ S_α and each token v∈Vv∈ V, let qγ′=δγ(qγ,v)q_γ = _γ(q_γ,v). If qγ′q_γ is undefined (the token violates syntax), the transition is undefined. Otherwise, – If qγ′∈γq_γ _γ (token v closed an action block), let a∈a be the meta-token produced by τ from the block tokens; advance the semantic state: δα((qγ,qβ),v)=(qγ′,δβ(qβ,a)). _α ((q_γ,q_β),v )= (q_γ , _β(q_β,a) ). – If qγ′∉γq_γ _γ (token v did not close a block), hold the semantic state fixed: δα((qγ,qβ),v)=(qγ′,qβ). _α ((q_γ,q_β),v )= (q_γ ,q_β ). • Accepting states: Fα=Fγ×FβF_α=F_γ× F_β. Correctness. By induction on |x||x|, for any x∈V∗x∈ V^*, αD_α reaches state (qγ,qβ)(q_γ,q_β) if and only if γD_γ reaches qγq_γ on x and βD_β reaches qβq_β on τinc(x) _inc(x). Hence x∈L⁡(α)x∈ L(D_α) iff x⊧γx γ (reaches FγF_γ) and τ⁡(x)⊧βτ(x) β (reaches FβF_β), matching Eq. 4. Size bound. The state space satisfies |Sα|≤|Sγ|⋅|Sβ||S_α|≤|S_γ|·|S_β|, and each state has at most |V||V| outgoing transitions, giving |α|≤|Sγ|⋅|Sβ|⋅|V|≤|γ|⋅|β||D_α|\;≤\;|S_γ|·|S_β|·|V|\;≤\;|D_γ|·|D_β| when DFA size is measured in edges and |V||V| is absorbed into the per-state branching. Reachability and minimization can reduce this constant, but the multiplicative scaling persists in the worst case because each state in γC_γ must branch into |Sβ||S_β| distinct successors, one per reachable semantic configuration. This is the bottleneck our factored approach avoids: we never construct αD_α, only γD_γ and βD_β separately. Appendix B Two-Level Decoding Algorithm Input: Prompt xpromptx_prompt; LM pLMp_LM; syntax HMM and DFA γD_γ; meta-token HMM and DFA βD_β; parser τ (incremental form τinc _inc). Output: Token sequence satisfying α=γ∧(β∘τ)α=γ (β τ). Bγ←B_γ← backward DP over HMMtoken×γHMM_token×D_γ ; // token-level lookahead Bβ←B_β← backward DP over HMMmeta×βHMM_meta×D_β ; // action-level lookahead x←xpromptx← x_prompt; l←1l← 1; repeat a<l←τinc(x)a_<l← _inc(x) ; // completed actions so far for each token v∈Vv∈ V admissible at the current DγD_γ state do q⁡(v)←pLM(v∣x)⋅p⁡(α∣x⋅v)q(v)← p_LM(v x)· p(α x·v) ; // constraint-conditioned posterior, Eq. 8 end for xt←arg⁡maxv⁡q⁡(v)x_t← _vq(v); x←x⋅xtx← x· x_t; if xtx_t closes an action block then l←l+1l← l+1 end if until xt=<EOS>x_t= <EOS>; return x Algorithm 1 Two-Level Constrained Decoding Appendix C Per-Module DFA and Parser Construction We build a separate syntactic DFA γD_γ, semantic DFA βD_β, and meta-token parser τ for each (benchmark, module) pair. All four core modules share the same three-part skeleton: γD_γ is a deterministic state machine over the base-LM token alphabet that admits exactly the grounded action//predicate plus type-compatible object-instance pairs derivable from the prompt; βD_β is a state machine over the meta-token alphabet that rejects on a precondition violation and accepts when every (non-dropped) task goal is satisfied; τ consumes the same token stream as γD_γ and emits one meta-step per completed action//atom boundary, remapping the prompt’s raw object ids to contiguous 00-based canonical ids. C.1 VirtualHome Action Sequencing (VH-AS) Output grammar (γD_γ). Plans are emitted as a single JSON object whose keys are action names and whose values are flat argument arrays [name, id] (or [name0, id0, name1, id1] for two-argument actions): "WALK": ["soap", "1002"] , "GRAB": ["soap", "1002"] , "PUTON": ["clothes_jacket", "1003"] γD_γ threads three per-scene tries (action-name, object-name, and per-name id) compiled once from the prompt’s object listing. After a complete action block, the DFA returns to its block-start state; an arbitrary-length action list is emitted until the close brace followed by the end-of-turn token. Actions are offered only when all of their argument roles have at least one type-compatible object in the scene. Action vocabulary (W). The VH-AS action set has |VH-AS|=36|W_VH-AS|=36 types: one nullary (StandUp); three binary (Pour, PutBack, PutIn); and 3232 unary actions including Walk, Find, Grab, Open, SwitchOn, PlugIn, Sit, Drink, Cut, Read, Type, Wash, Scrub, Wipe. The set is a subset of the official evaluator’s valid actions, omitting those that are non-executable or never goal-bearing. Semantic constraints (βD_β). βD_β tracks a state tuple consisting of: agent location, both hand-occupancy slots, posture, facing direction, and per-object bitmasks for openable, switchable, and plugged-in state, plus relational bits for graph edges and ordered action goals. Static preconditions are derived from prompt-stated object properties: Grab requires GRABBABLE; Open//Close require CAN_OPEN; SwitchOn//SwitchOff require HAS_SWITCH; PlugIn//PlugOut require HAS_PLUG; Sit//Lie require SITTABLE//LIEABLE; container//surface arguments of PutIn//PutBack require CONTAINERS// SURFACES. Dynamic preconditions are checked against the live state: a free hand and proximity for Grab; plugged-in and not-open for SwitchOn; not-on for Open; held object plus open destination for Put*; posture for locomotion. Goals are partitioned into node, edge, character-state, and ordered action goals; a state is accepting iff all (non-dropped) goals hold. Parser (τ). τ advances in lock-step with γD_γ and emits one meta-step at each block-boundary closure (the ] closing an action’s argument array), reading the action name and raw ids from trie leaves and remapping each raw id to canonical form. C.2 VirtualHome Subgoal Decomposition (VH-SD) Output grammar (γD_γ). Plans are a JSON object with a single "output" key whose value is a list of predicate atoms in temporal order: "output": ["PLUGGED_IN(washing_machine.1001)", "output": ["CLOSED(washing_machine.1001)", "output": ["ON(washing_machine.1001)"] Each atom is PRED(name.id) or PRED(name0.id0, name1.id1) with arguments written in dotted form. Cross-argument predicates carry forward the chosen arg0 so that arg1’s admissible set is filtered by arg0’s identity. Subgoal vocabulary (W). |VH-SD|=36|W_VH-SD|=36 predicates: 99 state (Closed, Open, On, Off, Plugged_In, Plugged_Out, Dirty, Sitting, Lying); 66 relation (Inside, OnTop, Next_To, Facing, Holds_LH, Holds_RH); and 2121 action-named intermediate-subgoal predicates (Grab, Clean, Cut, etc.). Semantic constraints (βD_β). βD_β carries per-object state bitmasks plus goal-progress bits. Executor ordering is enforced as predicate preconditions: On requires Plugged_In and not-Open; Open requires not-On; Inside//OnTop require the destination container Open; HoldsLH/RH require a free hand and a grabbable target. State and placement goals are evaluated from the live state at accept time (re-emitting Open after Closed correctly leaves the object open), and repeated placements use latest-wins semantics mirroring the evaluator. A state is accepting iff every (non-dropped) goal is currently satisfied. Parser (τ). τ emits one meta-step per completed atom, reading the predicate name and dotted name.id arguments from trie leaves and remapping ids. Structural tokens emit nothing. C.3 BEHAVIOR Action Sequencing (BEH-AS) Output grammar (γD_γ). Plans are a JSON array of one-action dictionaries "action": NAME, "object": INSTANCE: ["action": "LEFT_GRASP", "object": "plywood_0", ["action": "SLICE", "object": "strawberry_0", ["action": "LEFT_PLACE_INSIDE", "object": "jar_0"] BEHAVIOR object instances are written as base_name_index. γD_γ recognizes the action via a vocabulary trie and the instance via a per-scene instance trie built from the prompt, closing the list with ] and EOS. As in VH-AS, the grammar is cyclic across action blocks and applies viable-action and affordance pruning (Appendix G). Action vocabulary (W). |BEH-AS|=30|W_BEH-AS|=30 action types, all hand-explicit where the simulator is bimanual: left//right Grasp, Release, Place_OnTop, Place_Inside, Place_NextTo, Place_Under, Place_NextTo_OnTop (binary), and Transfer_Contents_Inside//OnTop; plus the hand-agnostic state actions Open, Close, Toggle_On, Toggle_Off, and the attribute actions Clean, Slice, Soak, Dry, Cook, Freeze, Unfreeze. Navigation is implicit and is not emitted. Semantic constraints (βD_β). βD_β carries goal bits, two hand-occupancy slots, a per-object location hash, and per-object boolean state bits. It encodes both task-specific preconditions parsed from the prompt’s initial-state block and the task-independent affordance prior of Appendix G: Grasp requires a free target hand, a graspable target, and no closed container in the target’s containment ancestry; Place_Inside requires the destination to be open; Toggle_On is forbidden on an open appliance; Soak requires the target inside a toggled-on water source; Clean of a stained target requires holding a soaked cleaner. A state accepts iff all (non-dropped) goal bits are set. Parser (τ). τ emits one meta-step when each per-action dictionary closes, mapping captured base_name_index strings to canonical ids. C.4 BEHAVIOR Subgoal Decomposition (BEH-SD) Output grammar (γD_γ). Plans are a JSON object "output": [ … ] whose elements are temporally ordered subgoal steps; within a step, atoms are joined by " and " (a conjunctive set): "output": ["holds_rh(carton.66) and inside(hardback.64, carton.66) "output": [ and inside(hardback.65, carton.66)", …] Each atom is [not ]pred(name.id[, name.id]) with lowercase predicate names. The grammar uses " and " within a step and ", " between steps. Subgoal vocabulary (W). 1616 positive predicates plus their NOT_ negations (3232 atoms total): 88 state (open, toggledon, cooked, frozen, sliced, soaked, stained, dusty); 88 relation (inside, ontop, under, onfloor, nextto, touching, holds_lh, holds_rh). Anti-goals are first-class. Semantic constraints (βD_β). βD_β carries goal bits, container-open bits, and a clean//soak chain bitmask. It accepts every γ-valid atom, setting the matching goal bit on positive match. Two precondition mechanisms are retained. Gate: an object the prompt’s initial state places inside a closeable container requires that container’s open bit before any non-open predicate may target it. Clean//soak chain: soaked or not stained goals are creditable only after the place–toggle–soak prerequisite chain. Goals are obtained by expanding the prompt’s quantified goal AST; anchored relations whose anchor is itself repositioned impose the ordering that the anchor’s placement goal must be set first. Parser (τ). τ emits one meta-step per atom, mapping instance labels to canonical ids. C.5 WAH-NL via LoTa-Bench The WAH-NL setting reuses the VirtualHome machinery with Llama-3.1-8B-Instruct as the base LM. γD_γ is the VH-AS DFA restricted to the WAH-relevant action subset (navigation, manipulation, object interaction, posture; WakeUp, Sleep, and PutObjBack are trimmed). βD_β is the VirtualHome state machine of Appendix C.1 applied to WAH goals: Grab requires a free hand and co-location; PutIn requires holding the object and the destination container not closed; Open//Close require co-location; SwitchOn requires the appliance plugged-in. These are the invariants whose violation accounts for the 6060 / 2121 / 1010 failure distribution of the ProgPrompt baseline in Section 4.2: any action whose precondition fails is never offered to the LM. τ is the VirtualHome parser of Appendix C.1 applied to the WAH action subset. C.6 Shared construction notes Canonical tokenization. All DFAs operate over the base LM’s token alphabet using a single canonical tokenization per atom. Token sets are computed once per tokenizer; structural substrings with more than one tokenization are treated as equivalence classes and marginalized over by logsumexp, so no tokenization variant collapses the candidate set mid-stream. EOS handling. End-of-sequence is treated as a meta-token gated by β: EOS is admitted only at an action//atom boundary, and only when the β state is accept-reachable. Appendix D HMM Training Training data construction. For each (benchmark, module) pair we construct a training set of unconstrained base-LM generations whose prompts share the benchmark format but contain no evaluation task instances. Specifically, we hold out the official evaluation tasks and construct training prompts by category-preserving substitution: object names and predicate arguments in the EAI/WAH-NL prompt template are resampled from the corresponding vocabularies (objects, properties, locations) so the surface format and predicate distribution match evaluation but the actual instances do not. We sample up to 1,000,0001,000,000 generations per (benchmark, module) pair at temperature 0.10.1, top-p 0.950.95, length cap 20482048 tokens (seed 4242); the BEHAVIOR halves comprise 492,352492,352 (AS) and 703,360703,360 (SD) raw generations. Generations that fail to parse are discarded (γ-acceptance for AS outputs, closed-output for SD), and the two simulators’ surviving halves are subsampled to a balanced 1:11:1 mixture before training. The retained sequences are used for both the token-level HMM (raw token sequence) and the meta-token HMM (the τ-projection of the same sequence). Corpus diversity. Continuations are sampled with a distinct seed per generation call. At temperature 0.10.1 the corpora are highly redundant: BEH AS yields 5858 distinct meta-token sequences from 95,66595,665 samples over 7070 prompts, and scaling VH AS by 5.3×5.3× adds 1414; held-out NLL agrees (99–10×10× more data buys 0.070.07–0.080.08 nats, and the last 1.6×1.6× buys 0.0050.005). The temperature-1.01.0 corpus is far more diverse (294294 of 512512 raw continuations distinct per prompt; 34.8%34.8\% of meta-token sequences distinct on BEH AS). Diversity does not, however, recover mandatory-but-rare actions, which are absent from the base LM’s output distribution at any temperature. HMMs. For EAI we train two meta-token HMMs: a 132-symbol Action Sequencing HMM shared by VH-AS and BEH-AS, trained on the union of the two simulators’ AS augmented generations, and a 123-symbol Subgoal Decomposition HMM shared by VH-SD and BEH-SD, trained on the union of their SD generations. WAH-NL uses a third meta-token HMM. Each uses hidden dimension H=128H=128. We train one token-level HMM per base LM over that model’s tokenizer vocabulary (Llama 3: 128K, gpt-oss: 200K) and reuse it unchanged across all of that base LM’s modules and simulators. The meta-token alphabet decomposes into grounded-action (or predicate) names, one object-ID symbol per argument slot, Unk, and Eos:44 4 A meta-token is one grounded action, the symbol over which DβD_β is defined (e.g. Grab(plate)). The HMM emits each grounded action as its name followed by one object-ID symbol per argument: a nullary action is one symbol, a unary action two ([action, ID]), a binary action three ([action, ID, ID]). Hand assignment is folded into the action name (e.g. Left_Grasp), so it carries no separate symbol. The vocabulary sizes count these emission symbols, not distinct grounded actions. for Action Sequencing the 132 symbols are 81 action names, 49 object-ID symbols (ID0 through ID48), Unk, and Eos; Subgoal Decomposition’s 123 decompose analogously. The main configuration uses the trained meta-HMM; the uniform variant below is an ablation. Table 7: HMM parameter counts. Token-level HMM size is dominated by the emission matrix H×|V|H×|V|; meta-token HMM is dominated by the H×H× H transition matrix at this scale. H=128H=128 throughout; token-level |V||V| shown for the Llama-3 tokenizer (gpt-oss uses |V|≈201|V|≈201K ⇒ ∼25.7 25.7M). Vocab Token-level HMM Meta-token HMM VH-AS 132 actions / 128128K tokens ∼16.4 16.4M ∼33 33K VH-SD 123 predicates / 128128K ∼16.4 16.4M ∼32 32K BEH-AS 132 actions / 128128K ∼16.4 16.4M ∼33 33K BEH-SD 123 predicates / 128128K ∼16.4 16.4M ∼32 32K WAH-NL 7 actions + 128 ids / 128128K ∼16.4 16.4M ∼34 34K Trained vs. uniform meta-HMM. We compare the trained meta-token HMM against a uniform variant in which the emission and transition parameters are uniform (i.e., no learned action-level prior; the meta-HMM contributes no preference beyond which actions are constraint-reachable and how far they are from acceptance). The main-table configuration uses the trained meta-HMM. Both surrogates enforce the same constraint and carry the same guarantee; they differ only in how they rank the constraint-satisfying set. Table 8: Trained vs. uniform meta-token HMM on Llama 3 8B, task / execution SR (%). All trained rows use the single recipe of Appendix D: parse-filtered corpus, balanced 1:1 simulator mixture, App. D hyperparameters, no decode-time scaling. The last row retrains the same recipe on a temperature-1.01.0 corpus. VH-AS cells are means over six evaluator seeds (Appendix K). Meta-HMM VH AS VH SD BEH AS BEH SD Uniform 90.7 / 97.7 88.4 / 93.2 36 / 89 41 / 59 Trained (T=0.1T=0.1 corpus) 90.4 / 97.7 89.9 / 93.5 34 / 89 36 / 66 Trained (T=1.0T=1.0 corpus) 90.1 / 98.0 87.5 / 92.3 32 / 95 44 / 65 The two configurations trade places by a few points per module. The trained surrogate wins where the automaton leaves many admissible continuations and the corpus covers them: with the more diverse temperature-1.01.0 corpus it overtakes uniform on BEH SD (4242 vs 4141) and takes the best execution SR on the action-sequencing modules; the uniform surrogate is slightly ahead elsewhere. Where the trained surrogate loses, the mechanism is a bias toward corpus typicality: this benchmark’s mandatory but rare actions almost never appear in the LM’s unconstrained outputs (Sleep and PlugIn never occur in ∼108 10^8 sampled tokens), so a faithful surrogate assigns them near-zero mass and fines exactly the steps the constraints exist to enforce; the uniform surrogate is immune by construction. A fuller treatment of surrogate calibration for constrained decoding is left to future work. Appendix E Decoding Details Greedy decoding under the factored posterior. At each decoding step we evaluate the factored posterior of Eq. 8 and select the argmax token. We do not use temperature sampling, top-p, or beam search; the constraint-aware reweighting is the only departure from greedy. Horizon budget. The semantic backward DP requires a finite horizon over meta-tokens. We set this budget to 4040 actions for all EAI and WAH-NL evaluations. This bound is generous: across the four EAI modules, gold plans have a median length of 44 meta-tokens and a 9595th-percentile length of 1919, well within budget. Only a single VH AS task (5454-step plan) exceeds the cap; remaining 879 remaining evaluation tasks fit. The budget cap is not the primary source of fallback. Appendix F Qualitative Examples: DFA-only Degeneration vs. Meta-Ctrl Section 4.3 reports that hard masking on the same γ DFA collapses task success while inflating execution rate. DFA-only collapses to a single trivially-true predicate after the LM’s first sample, because no token in the local mask is preferred over closing the bracket. Meta-Ctrl emits a concise, goal-completing plan because the β backward DP assigns zero mass to any continuation that closes the bracket before the goal predicates are reached. Table 9: Representative outputs from DFA-only (γ hard mask) and Meta-Ctrl (γ+βγ+β) on VirtualHome Subgoal Decomposition. DFA-only emits a single locally-true predicate and stops; Meta-Ctrl produces the predicates required to reach the goal. Task Prompt id DFA-only (γ mask) Meta-Ctrl (γ+βγ+β) Turn on light scene_1_125_2 NEXT_TO(character.65, light.411) PLUGGED_IN(light.411), ON(light.411) The DFA-only output is locally valid: NEXT_TO(character, light) is a syntactically correct subgoal predicate and is true in the initial scene, so the executor accepts it and reports the plan as executed (96.0%96.0\% execution rate on VH SD). It does not change the light’s state, so it does not satisfy the task goal (0.0%0.0\% task SR on VH SD). Meta-Ctrl’s lookahead, scoring each token by the probability that the remaining sequence satisfies β, rules out the early bracket close and forces the LM to emit the predicates the goal requires. Appendix G BEHAVIOR Affordance Prior The BEHAVIOR system prompt specifies the action grammar, object instances, initial-state relations, and goal predicates, but does not expose per-object affordances (which objects are openable, toggleable, graspable, valid containers, or valid cleaning agents). VirtualHome prompts carry this information directly via property tags; the BEHAVIOR prompt format does not. To match VirtualHome’s setup, we recover the missing affordance information from the benchmark’s own public object taxonomy. Affordances come from the BDDL taxonomy, not from an author list. Each BEHAVIOR prompt names its object instances by WordNet synset (e.g. bucket.n.01), and the BEHAVIOR Domain Definition Language (BDDL) [21] ships a taxonomy over those synsets: an ISA tree of 1,8221,822 nodes together with per-synset ability annotations (openable, toggleable, soakable, cleaningTool, and so on). BDDL is the language in which the benchmark’s own activity definitions are written and is distributed in the public bddl package; our copy is semantically identical to the released one (1,8221,822 nodes, zero ability differences). Affordance membership for an instance is therefore a lookup: the prompt supplies the synset, the taxonomy supplies the abilities and the ISA class, and DβD_β reads them off. No substring matching over instance names and no author-curated keyword list is involved. Two additions on top of the taxonomy. The taxonomy is not quite sufficient, and we state exactly where we go beyond it. First, an admissibility rule used at DFA-construction time: Open and Close (and the corresponding open atoms in Subgoal Decomposition) enter the action universe for an object only if the prompt’s initial or goal state mentions that object’s open state, or the object is an open-gated container in container role for this task, i.e. the target of an inside goal or the holder of an initial inside relation. This is a statement about which actions the task gives evidence for, not a generation-time heuristic, and it is load-bearing: removing it flips seven tasks from success to failure and none in the other direction, worth +3+3 task points on both BEHAVIOR modules. Second, five generic rules, each justified by a statement about the physical world that stands without reference to the evaluator: open-top vessels (bucket, basket, bin ISA subtrees) have no lid and are not open-gated; bathtubs are tap-equipped water fixtures, hence toggleable water sources; kettles, teapots and pools dispense or hold water without a switch, hence passive water sources; an object a goal asks to be repositioned is graspable, whatever its ISA class; and soaking or drying applies to cleaning implements unless the prompt states otherwise. The first of these knowingly disagrees with the benchmark’s gold plans, which do emit open on buckets and baskets; we keep the physical statement and absorb the resulting over-constraint. General precondition rules. The β state machine enforces a small number of task-independent precondition rules, each a domain-general property of the simulator: a grasp is rejected if the target hand is already holding an object; interacting with or placing into a closeable container requires it to be open; an object cannot be placed inside itself or anything (transitively) contained in it; and a position anchor must be established before relations referencing it. Scope of the prior. The prior encodes the kinds of object-affordance facts that VirtualHome’s prompt format exposes directly. The taxonomy lookup, the one admissibility rule, the five generic rules and the ≈4≈4 precondition families apply to every task in the module; none of them depends on a task’s goal, gold plan, or intermediate state. The information available to DβD_β is thus the prompt plus a published object taxonomy, strictly less than the planner baselines of Table 5 receive, since the benchmark itself distributes a full BEHAVIOR PDDL domain with 3030 action schemas carrying preconditions and effects, whereas DβD_β encodes no effects. Over-constraint on gold plans. Because the prior is fixed and task-independent, it can be stricter than a given task requires. Applied to the BEHAVIOR gold plans with no LM in the loop, it renders 17 of 100 infeasible, each containing one action the gold plan performs but a precondition rule rejects. Meta-Ctrl falls back to γ-only decoding on these, so they cap achievable BEHAVIOR task SR independently of the base LM. That the prior rejects this many gold plans is itself evidence it is generic rather than fit to the gold set. Appendix H Format and Hallucination Errors: Per-Module Breakdown Table 10 reports the rate of parsing, hallucination, and parameter errors for the raw Llama 3 8B baseline and for Meta-Ctrl across all four EAI (simulator, module) pairs. Total is the fraction of plans containing the corresponding error type. We then decompose this total into a benchmark-side component (errors caused by quirks of the evaluator’s input handling, where the LM’s output is in fact admissible under the prompt’s stated grammar and vocabulary) and an LM-fault component (residual errors that would constitute genuine constraint violations Meta-Ctrl was responsible for preventing). The LM-fault column is uniformly zero by construction: every Meta-Ctrl output satisfies its syntactic DFA γD_γ, which encodes exactly the parsing and vocabulary constraints these error categories test. Table 10: Format and hallucination error rates for raw Llama 3 8B and Meta-Ctrl. Parsing: output fails the evaluator’s parser. Hallucination: output references objects or predicates not present in the evaluator’s per-task vocabulary. Parameter: argument arity, type, or formatting mismatch. The Meta-Ctrl benchmark-side column counts plans rejected by the evaluator even though they comply with the prompt’s stated grammar and vocabulary (footnotes identify each case). The LM-fault column is the residual after removing benchmark-side rejections, and is zero across every module and error class. Module Error class Raw Llama 3 8B Meta-Ctrl Total Benchmark-side LM-fault BEH AS Parsing 0.0% 0.0% 0.0% 0.0% Hallucination 15.0% 0.0% 0.0% 0.0% Parameter 9.0% 0.0% 0.0% 0.0% Sum format/hallucination 24.0% 0.0% 0.0% 0.0% VH AS Parsing 14.4% 1.3% 1.3%a 0.0% Hallucination 6.9% 1.3% 1.3%b 0.0% Parameter 1.0% 0.0% 0.0% 0.0% Sum format/hallucination 22.3% 2.7% 2.7% 0.0% VH SD Parsing 0.6% 2.1% 2.1%c 0.0% Hallucination 3.3% 0.0% 0.0% 0.0% Parameter 0.6% 0.0% 0.0% 0.0% Sum format/hallucination 4.5% 2.1% 2.1% 0.0% BEH SD Parsing 0.0% 0.0% 0.0% 0.0% Hallucination 21.0% 1.0% 1.0%d 0.0% Parameter 0.0% 0.0% 0.0% 0.0% Sum format/hallucination 21.0% 1.0% 1.0% 0.0% Notes on benchmark-side residuals. The non-zero Meta-Ctrl rates in the Total column reflect quirks of the EAI evaluator rather than LM output errors: a VH AS, 1.3%1.3\% parsing: four prompts (339_1, 627_1, 84_1, 93_1) have empty goal blocks in the benchmark specification; the LM correctly emits , which the evaluator’s parser then rejects as malformed. b VH AS, 1.3%1.3\% hallucination: four prompts (125_2, 715_2, 173_1, 134_1) emit the PLUGIN action, which is listed in the prompt’s action vocabulary (PLUGIN: (1, [[‘HAS_PLUG’]])) and admitted by γD_γ, but is not in the evaluator’s accept set for the action-sequencing module—a vocabulary desynchronization between the prompt template and the evaluator’s parser. c VH SD, 2.1%2.1\% parsing: seven prompts emit the POUR subgoal predicate; the evaluator’s grammar reports Unknown primitive: POUR even though POUR appears in the predicate vocabulary supplied with the benchmark. This is a known upstream issue in the EAI evaluator’s predicate dispatcher. d BEH SD, 1.0%1.0\% hallucination: one prompt (packing_boxes_for_household_move_or_trip_0_Ihlen_1_int) has two scene objects of category shirt_n_01: shirt.0 and t-shirt.1. Meta-Ctrl’s canonical object encoder normalizes the second to shirt.1 and emits the (canonically valid) shirt.1, which the evaluator then reports as “Object shirt.1 is not in scene.” A naming-pipeline mismatch, not an LM-emitted hallucination. The LM-fault column separates these benchmark-side discrepancies from genuine LM output errors. Across all four modules and all error classes, Meta-Ctrl produces zero LM-fault errors, consistent with the syntactic guarantee of γD_γ. Appendix I Why BEHAVIOR Gains Less from Constrained Decoding than VirtualHome Meta-Ctrl’s gain on a benchmark depends on how completely the prompt specifies the task’s constraints, because the DFA can only enforce what the prompt makes available. VirtualHome and BEHAVIOR sit at opposite ends of this axis, and the gap in observed task SR lift tracks the gap in prompt content. VirtualHome prompts expose object affordances; BEHAVIOR prompts do not. Every VirtualHome prompt lists, for each object, the properties that determine which actions are applicable to it (e.g. HAS_PLUG, GRABBABLE, CAN_OPEN). On average each prompt carries about 1111 such property tags. BEHAVIOR prompts list object instances, an initial-state block, and goal predicates, but do not expose per-object affordances at all; this is a property of the benchmark’s prompt format, not of the tasks themselves. Most VirtualHome preconditions are derivable from the prompt; most BEHAVIOR preconditions are not. For each action in each gold plan, we look up its declared preconditions, taken from the benchmark’s own action definitions, the VirtualHome evaluator’s action schemas, and the BDDL/BEHAVIOR PDDL domain, and ask whether the predicate and its bound object can be read off the prompt directly: Prompt-derivable preconditions Affordance tags per prompt VirtualHome 82%82\% ∼11 11 BEHAVIOR 24%24\% 00 On VirtualHome the DFA can encode 82%82\% of declared preconditions from prompt-stated facts alone. On BEHAVIOR it can encode 24%24\%; the rest must come either from a task-independent affordance prior (Appendix G) or from the LM’s own world knowledge. The remaining BEHAVIOR gap cannot be closed by enlarging the prior. BEHAVIOR’s gold plans reference 148148 unique object base-names; the task-independent prior assigns an actionable affordance class to 4343 of them, and the uncovered tail is dominated by everyday items that the taxonomy places under classes carrying no relevant ability (book, candle, apple, plywood, strawberry, shoe, soap, jar, …). What is missing is not taxonomy coverage (every instance resolves to a synset) but the per-task state information VirtualHome prompts list directly; the gap is one of benchmark prompt content, not of constraint enforcement. This is also why the prior remains generic rather than fitted: its memberships are read from a published taxonomy that was authored for the benchmark’s activity definitions, not by us, and it rejects 17%17\% of the gold plans it is scored against. The effect. On BEHAVIOR Action Sequencing, Meta-Ctrl lifts Llama 3 8B from 10%10\% to 34%34\% task SR; on VirtualHome AS, from 21%21\% to 89%89\%. The absolute gain is large on BEHAVIOR because the baseline is low, but the achieved score is bounded by what the prompt makes encodable. The same DFA construction yields a larger gain on VirtualHome because the prompt supplies more of the constraints the DFA could enforce in the first place. Appendix J Real Robot Demonstrations We list the generated plans for five of the eight real-robot demonstrations in Fig. 3, contrasting the unconstrained Llama 3 8B baseline with Meta-Ctrl (ours). Each line is one meta-token (grounded action); instance IDs are dropped for readability. Actions that Meta-Ctrl inserts or substitutes to satisfy a precondition or goal the baseline violates are shown in green; baseline actions that violate a precondition or leave the goal unsatisfied are marked with ✗. Videos of each rollout are on the project website: https://meta-ctrlg.github.io/. J.1 Clean dishes with detergent Goal: clean the plate and bowl. Clean with a rag requires the rag to be soaked, and proper dish-cleaning requires detergent to be applied first. Baseline (Llama 3 8B) 1. Grab(orange rag) 2. Clean(plate) ✗ rag not soaked 3. Clean(bowl) ✗ rag not soaked 4. PutOn(orange rag, stool) Meta-Ctrl (ours) 1. Grab(spray bottle) 2. Spray(plate) 3. Spray(bowl) 4. PutOn(spray bottle, stool) 5. Grab(orange rag) 6. Soak(cup of water) 7. Clean(plate) 8. Clean(bowl) 9. PutOn(orange rag, stool) What Meta-Ctrl adds: detergent application before cleaning and an explicit Soak step so the rag satisfies the Clean precondition. J.2 Put dishes in dishwasher Goal: place blue mug, white cup, and gray pot inside the dishwasher. PutIn requires the target container to be open. Baseline (Llama 3 8B) 1. Grab(blue mug) 2. PutIn(blue mug, dishwasher) ✗ dishwasher closed 3. Grab(white cup) 4. PutIn(white cup, dishwasher) ✗ 5. Grab(gray pot) 6. PutIn(gray pot, dishwasher) ✗ Meta-Ctrl (ours) 1. Open(dishwasher) 2. Grab(blue mug) 3. PutIn(blue mug, dishwasher) 4. Grab(white cup) 5. PutIn(white cup, dishwasher) 6. Grab(gray pot) 7. PutIn(gray pot, dishwasher) What Meta-Ctrl adds: a single Open(dishwasher) prefix that unlocks every subsequent PutIn. J.3 Fetch egg from fridge Goal: place fridge-stored ingredients into a pot and heat it on the stove. Grab on items inside a closed container is infeasible. Baseline (Llama 3 8B) 1. Grab(orange) ✗ fridge closed 2. PutIn(orange, pot) 3. Grab(syrup) ✗ fridge closed 4. PutIn(syrup, pot) 5. Grab(pot) 6. PutOn(pot, stove) 7. ToggleOn(stove) Meta-Ctrl (ours) 1. Open(fridge) 2. Grab(orange) 3. PutIn(orange, pot) 4. Grab(syrup) 5. PutIn(syrup, pot) 6. Grab(pot) 7. PutOn(pot, stove) 8. ToggleOn(stove) What Meta-Ctrl adds: an Open(fridge) precondition for the enclosed ingredients. J.4 Set up breakfast table Goal: arrange a bowl, bread, oat-milk carton, and tuna can on the stool. The gripper is single-handed: Grab requires the hand to be empty. Baseline (Llama 3 8B) 1. Grab(bowl) 2. PutOn(bowl, stool) 3. Grab(bread) 4. Grab(oat-milk carton) ✗ holding bread 5. Grab(blue tuna can) ✗ holding oat-milk 6. PutOn(blue tuna can, stool) ✗ bread, milk lost Meta-Ctrl (ours) 1. Grab(bowl) 2. PutOn(bowl, stool) 3. Grab(bread) 4. PutIn(bread, bowl) 5. Grab(oat-milk carton) 6. PutOn(oat-milk carton, stool) 7. Grab(blue tuna can) 8. PutOn(blue tuna can, stool) What Meta-Ctrl adds: a release step (PutIn/PutOn) between every consecutive Grab, respecting the single-gripper invariant and ensuring all four items reach the goal surface. J.5 Place boxed objects in drawer Goal: move the tools inside the boxes (pliers, screwdriver) into their respective shelves. The baseline misreads the goal as relocating the boxes themselves. Baseline (Llama 3 8B) 1. Open(box 1) 2. Open(shelf 1) 3. Grab(box 1) ✗ wrong object 4. PutIn(box 1, shelf 1) ✗ goal not met 5. Close(shelf 1) 6. Open(box 2) 7. Open(shelf 2) 8. Grab(box 2) ✗ 9. PutIn(box 2, shelf 2) ✗ 10. Close(shelf 2) Meta-Ctrl (ours) 1. Open(box 1) 2. Open(shelf 1) 3. Grab(pliers) 4. PutIn(pliers, shelf 1) 5. Close(shelf 1) 6. Open(box 2) 7. Open(shelf 2) 8. Grab(screwdriver) 9. PutIn(screwdriver, shelf 2) 10. Close(shelf 2) What Meta-Ctrl adds: goal-aware object selection. The semantic DFA encodes the goal predicate Inside(pliers,shelf 1)∧Inside(screwdriver,shelf 2) Inside(pliers,shelf 1) Inside(screwdriver,shelf 2), so the only Grab that drives the β DFA toward acceptance is on the tools, not the boxes that contain them. Summary. The five demos cover the three precondition families Meta-Ctrl is designed to repair: container access (dishwasher, fridge), tool-use chains (detergent→ → ), and single-gripper / object-identity goals (breakfast table, boxed tools). In every case the baseline produces a syntactically clean plan that nonetheless fails at the planning stage; Meta-Ctrl’s β-DFA inserts the missing precondition or substitutes the goal-relevant object without changing any otherwise-valid step. Appendix K Extended Evaluation on Recent Models The EAI leaderboard [9] was published in 2024 and predates several frontier and open-weight model releases. To contextualize Meta-Ctrl against the current state of the art, we evaluated nine recent models on EAI under its official protocol (Table 11): four Claude variants (Opus 4.6, 4.7, 4.8; Sonnet 4.6), three GPT-5 variants (5.4, 5.4 mini, 5.5), and two open-weight models (Gemma 4 31B and gpt-oss-20B, the latter also serving as a Meta-Ctrl base model). Evaluation protocol. We used the official EAI evaluation pipeline [9] with prompts and scoring identical to the leaderboard configuration. For each model, we generated plans under default sampling parameters and scored them with EAI’s official symbolic evaluator on the full VirtualHome (n=342n=342 AS, 338338 SD) and BEHAVIOR (n=100n=100 AS, 100100 SD) test sets. Open-weight models were run locally on 8×NVIDIA H200 GPUs. We report both Task SR and Execution SR. Evaluation protocol. The official VirtualHome evaluator matches a task’s gold action goals in a hash-dependent order, so VH-AS task SR on identical plans can vary by up to ±1.4± 1.4 points across runs (thirteen of the 342342 tasks carry more than one action goal). All our VirtualHome numbers are therefore means over six fixed evaluator seeds. Where Meta-Ctrl stands. Meta-Ctrl with Llama 3 8B tops the VH-AS Task SR column (90.4, mean over six evaluator seeds), above Claude Opus 4.8 (87.9), despite the base LM being roughly an order of magnitude smaller and open-weight; the two Meta-Ctrl models also take the top two slots on VH-AS execution (97.7 and 94.1). On VH-SD, recent frontier models (Claude Opus 4.6, GPT-5.4) reach 92.9 Task SR, surpassing Meta-Ctrl (89.9 with Llama 3 8B), and they keep the lead on execution as well (95.6 vs. 93.5). On BEHAVIOR, recent frontier models lead Task SR in both modules, but the picture splits on execution: Meta-Ctrl with gpt-oss-20B tops BEH-AS execution (90.0), just ahead of Claude Sonnet 4.6 (89.0), while frontier models retain the lead on BEH-SD execution. This pattern is consistent with our hypothesis that constraint enforcement most benefits weaker base models on objectives where plan validity is the dominant failure mode—hence Meta-Ctrl’s strength on the execution-SR columns—while stronger base models recover their advantage on Task SR, which demands richer world knowledge and goal interpretation, most visibly on BEHAVIOR. The Subgoal Decomposition results on VirtualHome are particularly telling: every recent frontier model clusters within 90.8–92.9 Task SR (and 93.5–95.6 execution), suggesting SD has become a near-saturated benchmark where constraint enforcement contributes less marginal value. Table 11: Extended Embodied Agent Interface results on recent models, evaluated by us under the official EAI protocol. Task SR (T) and Execution SR (E) on VirtualHome (VH; n=342n=342 AS, 338338 SD) and BEHAVIOR (BEH; n=100n=100 AS, 100100 SD). Meta-Ctrl rows from Table 3 included for reference. Bold: best per column; underline: second-best. Action Sequencing Subgoal Decomposition VH BEH VH BEH Model T E T E T E T E Avg Recent frontier models Claude Opus 4.8 87.9 86.2 74.0 81.0 90.8 93.8 61.0 65.0 78.4 Claude Opus 4.7 77.7 76.1 73.0 82.0 91.1 93.8 64.0 71.0 76.5 Claude Opus 4.6 74.4 74.8 78.0 87.0 92.9 95.6 78.0 82.0 80.8 Claude Sonnet 4.6 73.1 75.7 84.0 89.0 91.7 93.5 73.0 79.0 80.5 GPT-5.5 73.4 78.0 72.0 75.0 92.3 95.0 69.0 76.0 76.7 GPT-5.4 70.8 74.8 57.0 59.0 92.9 95.3 66.0 76.0 71.7 GPT-5.4 mini 71.5 76.7 70.0 79.0 91.1 94.7 63.0 76.0 73.9 Recent open-weight models Gemma 4 31B 20.7 22.6 51.0 58.0 83.7 93.5 37.0 42.0 48.1 gpt-oss-20B 74.4 80.3 40.0 51.0 72.5 82.2 27.0 36.0 53.5 Meta-Ctrl Llama 3 8B + Meta-Ctrl 90.4 97.7 34.0 89.0 89.9 93.5 36.0 66.0 62.6 gpt-oss-20B + Meta-Ctrl 86.6 94.1 40.0 90.0 82.3 86.4 41.0 66.0 62.5 T = Task SR, E = Execution SR. Avg = mean of the four Task SR columns.

Instant research discovery