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

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 107 TB to under 2 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 strong results across the Embodied Agent Interface (VirtualHome and BEHAVIOR). We further demonstrate it on a real tabletop robot, where every generated plan satisfies its preconditions and goals by construction.

Contributions

An exact two-level factorization. Meta-tokens decouple token-level syntax from action-level semantics, replacing a multiplicative constraint-state space with an additive one: ~350M DFA states shrink to ~57K, dynamic-programming memory drops from 107 TB to 1.6 GB (~67,000× less), and decoding runs ~1,900× faster.

Guarantees without giving up plan quality. Every output satisfies the encoded syntactic and semantic constraints by construction—no hallucinated actions, no precondition or ordering violations—while full-sequence probabilistic lookahead keeps the base LM's plans fluent and goal-directed.

Small open models pass frontier models. On VirtualHome action sequencing, Llama-3-8B rises from 21.3 to 88.7 task success rate—above every entry on the Embodied Agent Interface leaderboard, including Llama-3-70B, GPT-4o, and o1-preview.

Method

Plans must satisfy two kinds of constraints. Enforcing them jointly in a single token-level automaton blows up to ~350M states; Meta-Ctrl factors the problem across granularities so each level stays tractable—exactly.

Level 1 — syntactic constraint γ, enforced over tokens. Valid action names, argument structure and formatting, enforced at the token level with a DFA. Following Ctrl-G, each token is weighted by a tractable estimate of whether the full completion can still satisfy γ—keeping the hard guarantee while reasoning about the whole remaining sequence, not just the next token.

Level 2 — semantic constraint β, enforced over meta-tokens. Preconditions, goal achievement and ordering over the evolving world state, enforced at the action level over meta-tokens—a compact alphabet {ACT, ID0…IDk, EOS} of grounded actions, ~132 symbols instead of a 128K-token vocabulary.

~1,900× faster · ~67,000× less memory · ~16.7× better fit.

Formulation

A plan must satisfy a token-level syntactic constraint γ and an action-level semantic constraint β. Four steps take Meta-Ctrl from probabilistic reweighting to an exact two-level factorization.

1. Constrained decoding as probabilistic reasoning (Ctrl-G). $$ p_{\mathrm{LM}}(x_t \mid x_{\lt t}, \alpha)\;\propto\;p_{\mathrm{LM}}(x_t \mid x_{\lt t})\;\cdot\;p_{\mathrm{LM}}(\alpha \mid x_{\le t}) $$ The second factor is the probability that the full sequence will satisfy the constraint α given the current prefix. It assigns zero mass to tokens with no valid completion—so satisfaction is guaranteed—and among valid tokens prefers those leading to fluent, high-probability completions.

2. Tractable lookahead via an HMM and a DFA. $$ p_{\mathrm{ctrl}}(x_t \mid x_{\lt t}, \alpha)\;\propto\;p_{\mathrm{LM}}(x_t \mid x_{\lt t})\;\cdot\;p_{\mathrm{HMM}}(\alpha \mid x_{\le t}) $$ The exact lookahead is intractable, so α is compiled to a DFA \(\mathcal{D}_\alpha\) and approximated by a trained HMM. Their product is finite-state, admitting a backward dynamic program that returns the lookahead for every prefix at cost \(O(n\cdot|\mathcal{D}|\cdot H^2)\). Composing constraints multiplies DFA sizes (\(|\mathcal{D}_1|\cdot|\mathcal{D}_2|\))—the bottleneck Meta-Ctrl removes.

3. Two levels via meta-tokens. $$ x \models \alpha \;\iff\; (x \models \gamma)\;\wedge\;(\tau(x) \models \beta) $$ A parser \(\tau\) maps each syntactically valid token sequence to its sequence of grounded actions (meta-tokens, e.g. Open(dishwasher)); β is a DFA over meta-tokens tracking preconditions, ordering, and goal progress. On the γ-valid support, \(\tau\) is a bijection (one canonical tokenization per action sequence).

4. Exact factorization. $$ p(\alpha \mid x_{\le t}) = \sum_{a_l} \underbrace{p(a_l \mid x_{\le t})}_{\text{bridging}}\;\cdot\;\underbrace{p(\gamma \mid x_{\le t}, a_l)}_{\text{syntax (tokens)}}\;\cdot\;\underbrace{p_{\mathrm{meta}}(\beta \mid a_{\le l})}_{\text{semantics (actions)}} $$ Bijectivity of \(\tau\) makes the semantics term depend only on the completed-action prefix \(a_{\le l}\), so syntax (token level) and semantics (action level) decouple exactly, communicating only through the bridging term \(p(a_l \mid x_{\le t})\). Each level becomes an independent backward DP—an additive state space instead of a multiplicative one, the source of the ~1,900× compute and ~67,000× memory savings.

Results

On the Embodied Agent Interface, Meta-Ctrl lifts open-weight LMs to match or exceed frontier closed models; on WAH-NL it turns an unusable LM into a deployable planner.

On Llama-3-8B, Meta-Ctrl raises VH Action-Sequencing task SR from 21.3 to 88.7 and Subgoal-Decomposition from 48.8 to 88.2; on gpt-oss-20B it raises VH AS from 74.4 to 86.6. Both exceed every model on the EAI leaderboard, including o1-preview, Claude-3.5 Sonnet, and Mistral Large. The lift is smaller on BEHAVIOR, where prompts encode fewer of the task's preconditions (24% vs 82% on VH), so less of the constraint can be written into the DFA.

The guarantee is necessary but not sufficient. Hard masking achieves the same syntactic validity yet collapses task success—greedy decoding steers to the shortest constraint-satisfying continuation (high Exec, near-zero Task). Full-sequence probabilistic lookahead recovers task success by +87 to +88 points on VirtualHome.

On the SSR axis comparable across protocols, Meta-Ctrl (0.705) exceeds LoTa-Bench's strongest reported configuration (LLaMA-1-65B 0.433; GPT-4 0.342) and the closed-loop STEP baseline (0.620), with every plan executable by construction.

Real-robot deployment

Meta-Ctrl deployed on a physical xArm 7 with a calibrated RealSense RGB-D camera, composing its plans with a Code-as-Policies executor (Molmo + SAM2 grounding, GraspGen grasps).

Meta-Ctrl achieves 100% plan validity by construction on all tasks, including the multi-step precondition sequences for articulated containers. Its remaining failures occur downstream of a valid plan (perception or grasp), which isolates cleanly from planning. Example—put donut into canister: planning 20/20, perception 17/20, execution 13/17; the unconstrained baseline fails at planning (1/20).