PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2608.22149v1cs.ROcs.AI

TL;DR

LLM-generated robot plans often violate syntactic and semantic constraints, and existing approaches rarely provide both formal guarantees and high plan quality. Meta-Ctrl decouples syntax over tokens from semantics over action-level meta-tokens through exact factorization. It makes small open-weight LMs competitive across benchmarks and produces constraint-satisfying plans by construction, while remaining limited to DFA-expressible constraints and the encoded or believed state.

  • Problem

    Robot-planning LLMs frequently produce malformed or physically infeasible plans, while existing methods rarely combine formal guarantees with high plan quality.

  • Method

    Meta-Ctrl uses meta-tokens to enforce syntax at the token level and semantic preconditions, goals, and ordering at the action level through an exact factorization.

  • Results

    On VirtualHome action sequencing, Llama 3 8B with Meta-Ctrl surpasses every EAI leaderboard model, including larger open-weight and frontier closed models.

  • Takeaways & Limitations

    Across EAI, WAH-NL, and a real tabletop robot, Meta-Ctrl turns a small open-weight LM into a competitive planner with every encoded constraint satisfied by construction.

  • Takeaways & Limitations

    Meta-Ctrl is limited to DFA-expressible constraints, and its guarantees are relative to the encoded constraint and the robot’s perception-estimated symbolic state.

Abstract

from arXiv · show

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: https://meta-ctrlg.github.io/.

1 Introduction

Robot plans often fail syntactic and semantic constraints, while existing methods rarely combine formal guarantees with high plan quality. Meta-Ctrl decouples token-level syntax from action-level semantics using meta-tokens, enabling guaranteed constrained decoding and competitive planning performance.

  • Motivation: LLM-generated robot plans violate syntactic constraints such as malformed actions and semantic constraints such as failed preconditions or incorrect orderings.These failures occur frequently on long-horizon household tasks.
  • Limitations of Existing Methods: Soft guidance methods reshape outputs but can still generate infeasible plans, whereas grammar-constrained decoding can distort the LM toward valid but improbable completions.Grammar masks enforce local validity without reasoning over the full remaining sequence.
  • Motivation: 107 TB of memory is required by a monolithic token-level DFA combining syntax and semantics for a typical task.The product state space is wasteful because semantic validity depends on actions and their order, not token formatting.
  • Meta-Ctrl: Meta-Ctrl uses meta-tokens to enforce syntax over tokens and semantics over grounded actions through an exact two-level factorization.The framework applies formally guaranteed constrained decoding to robot planning.
  • Meta-Ctrl: 1,900× lower compute and 67,000× lower memory result from decoupling the token- and action-level constraint problems.The reductions are reported relative to the monolithic approach.
  • Evaluation: Llama 3 8B surpasses every model on the EAI VirtualHome action-sequencing leaderboard, including Llama 3 70B and frontier closed models.The evaluation covers EAI, LoTa-Bench, and a real tabletop robot.

2 Preliminaries: Ctrl-G

Ctrl-G treats constrained decoding as probabilistic reasoning over the probability that a full completion satisfies a constraint. It uses an HMM-DFA lookahead approximation to preserve guarantees while favoring fluent valid outputs.

  • Probabilistic Formulation: Ctrl-G decomposes constrained decoding into the LM’s next-token distribution and the probability that the full completion satisfies the constraint.The second factor conditions on the current prefix.
  • Probabilistic Formulation: Lookahead reweighting assigns zero probability to tokens with no valid completion and prefers valid tokens leading to natural, high-probability completions.This avoids treating all locally compatible tokens equally.
  • Tractable Lookahead: Ctrl-G substitutes an HMM approximation for the intractable exact probability of satisfying the constraint over all future sequences.The HMM approximates the LM’s sequence distribution.
  • Tractable Lookahead: The HMM-DFA product supports a backward dynamic program costing O(n · |D| · H2) for sequence length n, H hidden states, and DFA size |D|.The DFA reads tokens left to right and accepts in a final state.
  • Guarantee: The guarantee is preserved because the HMM lookahead is zero wherever no constraint-satisfying continuation exists.A more accurate HMM changes reweighting among valid tokens rather than validity itself.

3 Decoupling Syntax and Semantics for Constrained Decoding

Meta-Ctrl separates token-level syntax from action-level semantics using grounded meta-tokens and an exact factorization. This preserves valid formatting while enabling semantic state tracking with substantially lower computational cost.

  • Two-level constraint enforcement: Meta-Ctrl enforces syntactic validity with a token-level DFA and semantic validity with an action-level constraint over grounded action sequences.Syntax covers action names, argument structure, and JSON formatting; semantics covers goals, preconditions, and temporal ordering.
  • Token-level syntax: Every Level-1 output parses into a valid action sequence, eliminating malformed actions, invalid names, and ill-formed arguments.The constrained decoder prevents the raw LM's prose and malformed action outputs.
  • Action-level semantics: The parser τ maps each syntactically valid token sequence to grounded meta-tokens, while a DFA over those meta-tokens tracks preconditions and goal progress.The bijection assumption gives each action sequence a unique canonical token realization.
  • Exact factorization: The exact factorization communicates through p(a_l | x_≤t), leaving syntax at token level and semantics at action level without additional assumptions beyond τ's bijectivity.The resulting decoder uses separate constraint mechanisms at their natural granularities.
  • Computational tractability: Factoring replaces the monolithic product state space with additive computation and advances semantic dynamic programming over a small action vocabulary.Table 1 evaluates the resulting surrogate on a median VirtualHome task with H=128; sequence lengths are 42.7 raw tokens versus 7.6 grounded actions.

4 Experiments

Meta-Ctrl is evaluated across three planning benchmarks, four EAI task sets, and a real tabletop robot, with ablations separating semantic control and probabilistic lookahead. It substantially improves success and execution while preserving formal validity and transfers to new models without retraining.

  • Evaluation setup: Meta-Ctrl is evaluated on EAI, WAH-NL under LoTa-Bench, and a real XArm7 tabletop robot, reporting task, execution, and subgoal success rates.EAI covers VirtualHome and BEHAVIOR with Action Sequencing and Subgoal Decomposition; WAH-NL contains 100 tasks.
  • WAH-NL: 0.705 SSR exceeds LoTa-Bench’s strongest reported configuration, GPT-4, and STEP under the comparable SSR axis.On Llama-3.1-8B-Instruct, Meta-Ctrl reaches SR 0.470, SSR 0.705, and Exec 1.000.
  • Ablations: Semantic control accounts for nearly all WAH-NL gains, lifting execution from 0.010 to 1.000 while syntactic control alone adds only 1.5 SSR points.The base Llama-3.1-8B-Instruct solves none of the 100 tasks before full Meta-Ctrl.
  • Transfer: 90.7/97.7 task/execution SR transfers to Qwen3-8B without retraining, while both Qwen3 and Gemma-3-12B-it retain zero parsing and affordance errors.Porting rebuilds token-level constraints for each tokenizer while keeping the action-level representation unchanged.
  • Guarantees: 0% LM-fault replaces raw combined error rates of 24% on BEHAVIOR and 22.3% on VirtualHome by construction.The eliminated failures include hallucinated objects, malformed parameters, and other grammar errors.

5 Conclusion

Meta-Ctrl guarantees encoded syntactic and semantic constraints by separating token-level grammar enforcement from action-level semantic enforcement through meta-tokens. Its implementation uses benchmark-specific DFAs, a parser, and grounded action vocabularies to produce constraint-satisfying plans.

  • 5 Conclusion: Meta-Ctrl guarantees encoded syntactic and semantic constraints by decoupling enforcement across token and action granularities via meta-tokens.The framework applies syntax constraints over base-LM tokens and semantic constraints over grounded actions.
  • 5 Conclusion: Across EAI, WAH-NL, and a real tabletop robot, Meta-Ctrl turns a small open-weight LM into a competitive planner with every output constraint-satisfying by construction.The conclusion reports parity or superiority to models an order of magnitude larger within the evaluated settings.
  • Implementation: The decoding pipeline combines a syntactic DFA, semantic DFA, meta-token parser, and HMM-guided posterior to generate valid plans.Algorithm 1 returns token sequences satisfying the conjunction of syntactic and semantic constraints.
  • Meta-token representation: Meta-tokens represent grounded actions, allowing semantic state tracking over action sequences while the token DFA enforces output grammar.The parser emits a meta-step when an action block closes and remaps raw object identifiers to canonical forms.
  • Benchmark-specific construction: The framework specializes its output grammars and semantic state machines across VirtualHome, BEHAVIOR, and WAH-NL action or subgoal modules.These grammars encode module-specific JSON structures, action vocabularies, object instances, predicates, and precondition state.

D HMM Training

The HMM training procedure builds token- and meta-token surrogates from unconstrained generations, sharing action-level models across related modules. Trained and uniform surrogates preserve the same guarantee but differ in how they rank valid continuations, while decoding remains greedy under a finite horizon.

  • Training data construction: Training data consists of unconstrained base-LM generations from benchmark-format prompts with evaluation task instances held out.Prompts are constructed by category-preserving substitution of objects and predicate arguments.
  • Corpus diversity: At temperature 0.1, generated corpora are highly redundant, whereas temperature 1.0 produces substantially more diverse continuations.BEH AS has 58 distinct meta-token sequences from 95,665 low-temperature samples, while 34.8% of high-temperature meta-token sequences are distinct.
  • HMM configuration: EAI uses shared 132-symbol action-sequencing and 123-symbol subgoal-decomposition meta-token HMMs, while each base LM receives its own token-level HMM.All HMMs use hidden dimension H=128, with token-level vocabularies determined by the tokenizer.
  • Meta-token representation: A meta-token is a grounded action emitted as its name followed by one object-ID symbol per argument, with hand assignment folded into the action name.Nullary, unary, and binary actions therefore emit one, two, and three symbols respectively.
  • Trained versus uniform: Trained and uniform meta-HMMs enforce the same constraint guarantee but differ only in ranking constraint-satisfying actions.The trained surrogate models corpus typicality, whereas the uniform surrogate contributes no learned preference beyond reachability and acceptance.
  • Decoding procedure: Greedy decoding selects the argmax token under the factored posterior, without temperature sampling, top-p, or beam search, using a 40-action semantic horizon.The horizon covers nearly all evaluated plans; one 54-step VirtualHome action-sequencing task exceeds it.

F Qualitative Examples: DFA-only Degeneration vs. Meta-Ctrl

Local grammar validity can produce semantically empty plans: DFA-only decoding stops after a predicate that is true initially but does not achieve the goal. Meta-Ctrl’s semantic lookahead prevents premature termination by requiring goal-completing continuations, while BEHAVIOR affordance information comes from benchmark specifications and a public taxonomy.

  • DFA-only degeneration: DFA-only decoding achieves 96.0% execution rate but 0.0% task success on VirtualHome subgoal decomposition.Its locally valid output is accepted without changing the relevant scene state.
  • Meta-Ctrl correction: Meta-Ctrl’s semantic lookahead assigns zero mass to bracket closures that cannot lead to the required goals, forcing goal-relevant predicates.This distinguishes locally valid continuations from completions that satisfy the full semantic constraint.
  • BEHAVIOR affordance prior: BEHAVIOR affordance information is recovered from the benchmark’s public BDDL taxonomy because its prompts do not expose per-object affordances.The taxonomy provides ability annotations such as openable, toggleable, soakable, and cleaning-tool properties.
  • Prior construction: The prior adds one task-evidence-based admissibility rule and five generic physical-world rules on top of the taxonomy.These additions govern which open actions enter the action universe and encode affordances such as open-top vessels and passive water sources.
  • Semantic constraints: The semantic DFA encodes preconditions and goal progress over evolving object, hand, and relational states rather than token surface forms alone.Examples include open-container requirements, hand availability, and ordered predicate goals.
  • Prior limitation: The fixed affordance prior renders 17 of 100 BEHAVIOR gold plans infeasible, causing Meta-Ctrl to fall back to syntax-only decoding on those tasks.These rejected plans cap achievable BEHAVIOR task success independently of the base LM.

H Format and Hallucination Errors: Per-Module Breakdown

Meta-Ctrl eliminates LM-fault parsing, hallucination, and parameter errors by construction, while residual evaluator failures arise from benchmark-side vocabulary, parser, or naming mismatches. The per-module breakdown separates these external discrepancies from genuine model output errors.

  • Aggregate breakdown: The LM-fault error rate is uniformly zero for Meta-Ctrl across all four EAI modules and all tested error classes.The syntactic DFA encodes the parsing and vocabulary constraints evaluated by these categories.
  • Benchmark-side residuals: Meta-Ctrl’s non-zero Total error rates reflect evaluator quirks rather than LM output errors.The benchmark-side component includes plans admissible under the prompt specification but rejected by the evaluator.
  • VH AS: In VH AS, 1.3% hallucination errors result from PLUGIN being listed in the prompt vocabulary but excluded from the evaluator’s accepted action set.This is a vocabulary desynchronization between the prompt template and evaluator parser.
  • VH SD: In VH SD, 2.1% parsing errors occur when the evaluator rejects the POUR predicate despite its inclusion in the supplied predicate vocabulary.The passage identifies this as an upstream evaluator predicate-dispatcher issue.
  • BEH SD: In BEH SD, 1.0% hallucination reflects a canonical object-name mismatch that causes the evaluator to reject shirt.1.Meta-Ctrl emits the canonicalized identifier, but the evaluator reports that identifier as absent from the scene.

I Why BEHAVIOR Gains Less from Constrained Decoding than VirtualHome

BEHAVIOR gains less because its prompts expose far fewer task-specific preconditions than VirtualHome, limiting what Meta-Ctrl’s DFA can encode. This prompt-content gap bounds the achievable lift despite constrained decoding.

  • Prompt content: BEHAVIOR prompts omit per-object affordances, whereas VirtualHome prompts provide about 11 affordance tags per object on average.VirtualHome lists properties such as HAS PLUG, GRABBABLE, and CAN OPEN; BEHAVIOR provides instances, initial state, and goals instead.
  • Constraint coverage: 82% of declared preconditions are prompt-encodable on VirtualHome, compared with 24% on BEHAVIOR.The remainder on BEHAVIOR must come from a task-independent affordance prior or the LM’s world knowledge.
  • Constraint coverage: BEHAVIOR’s remaining gap reflects missing per-task state information rather than insufficient taxonomy coverage.Its gold plans reference 148 object base-names, while the prior assigns actionable affordance classes to 43; every instance still resolves to a synset.
  • Observed effect: Meta-Ctrl lifts Llama 3 8B task SR from 10% to 34% on BEHAVIOR Action Sequencing and from 21% to 89% on VirtualHome AS.The larger VirtualHome gain tracks its richer prompt-specified constraint information, while BEHAVIOR’s achieved score remains bounded by prompt encodability.

J.2 Put dishes in dishwasher

For dishwasher placement, the baseline repeatedly attempts PUTIN while the dishwasher is closed. Meta-Ctrl inserts OPEN(dishwasher), making the subsequent placements satisfy the container precondition.

  • Baseline: PUTIN requires the target dishwasher to be open, but the baseline attempts placement immediately after each GRAB.All three baseline PUTIN actions violate the closed-container precondition.
  • Meta-Ctrl: Meta-Ctrl adds OPEN(dishwasher) before grabbing and placing the three target items.The resulting sequence places the blue mug, white cup, and gray pot inside the dishwasher without the baseline’s precondition violations.

J.4 Set up breakfast table

The breakfast-table example combines a single-gripper constraint with object-specific goals. Meta-Ctrl inserts release actions and selects goal-relevant objects, producing a plan that satisfies all four placement goals.

  • Set up breakfast table: Because the gripper is singlehanded, consecutive GRAB actions fail when the hand still holds the previous object.The baseline loses track of bread and oat milk after attempting unsupported consecutive grasps.
  • Set up breakfast table: Meta-Ctrl inserts PUTIN or PUTON between every consecutive GRAB to respect the single-gripper invariant.The revised sequence places the bowl, bread, oat-milk carton, and tuna can on the stool or in the bowl.
  • Set up breakfast table: The semantic DFA uses the goal predicates to select the tools rather than the boxes containing them.This addresses the baseline’s misinterpretation of the goal as relocating the boxes themselves.
  • Set up breakfast table: Across the five demonstrations, Meta-Ctrl repairs container access, tool-use chains, single-gripper constraints, and object-identity goals without changing otherwise-valid steps.Each baseline plan is syntactically clean but fails during planning; the β-DFA inserts missing preconditions or substitutes the goal-relevant object.

K Extended Evaluation on Recent Models

An extended evaluation under the official EAI protocol compares Meta-Ctrl with recent frontier and open-weight models on VirtualHome and BEHAVIOR. Meta-Ctrl remains strongest on selected action-sequencing and execution metrics, while frontier models lead several task-success settings.

  • Evaluation setup: Nine recent models were evaluated under the official EAI protocol on the full VirtualHome and BEHAVIOR test sets.The comparison includes Claude variants, GPT-5 variants, Gemma 4 31B, and gpt-oss-20B.
  • VirtualHome: Meta-Ctrl with Llama 3 8B reaches 90.4 VH-AS Task SR, above Claude Opus 4.8 at 87.9.The Llama 3 8B Meta-Ctrl model also tops VH-AS execution with 97.7, while the second Meta-Ctrl model reaches 94.1.
  • VirtualHome: On VH-SD, Claude Opus 4.6 and GPT-5.4 reach 92.9 Task SR, exceeding Meta-Ctrl’s 89.9 with Llama 3 8B.Frontier models also lead execution, at 95.6 versus 93.5.
  • BEHAVIOR: Meta-Ctrl with gpt-oss-20B tops BEH-AS execution at 90.0, just ahead of Claude Sonnet 4.6 at 89.0.Frontier models retain the lead on BEH-SD execution and on BEHAVIOR Task SR.
  • Interpretation: Frontier models cluster within 90.8–92.9 Task SR and 93.5–95.6 execution on SD, suggesting a near-saturated benchmark.Task SR denotes Task SR and execution denotes Execution SR; Avg is the mean of four Task SR columns.
Loading 2608.22149v1…