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.

Highlights

An exact factorization that makes guaranteed semantic constraints tractable.

67,000×

Less memory

Two-level factorization replaces a multiplicative state space (107 TB) with an additive one (<2 GB), and runs ~1,900× faster.

Guaranteed

Valid by construction

Every output satisfies the encoded syntactic and semantic constraints—no hallucinated actions, no precondition or ordering violations.

8B > GPT-4o

Small model, big results

On VirtualHome action sequencing, Llama-3-8B goes from 21.3 to 88.7 task SR—past every EAI leaderboard entry, including Llama-3-70B and frontier closed models.

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 · Tokens

Syntactic constraint γ

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 · Meta-tokens

Semantic constraint β

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.

Why two levels: factoring the joint constraint is both cheaper and a better surrogate (median VirtualHome task, hidden size H=128).
Quantity	Monolithic	Two-level (ours)
DFA states	Sγ × Sβ ≈ 350 M	Sγ + Sβ ≈ 57 K
Compute	1,720 T	922 G
DP memory	107 TB	1.6 GB
Surrogate fit (−log p / action)	33.54 (token HMM)	2.01 (action HMM)

~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 β. The four steps below 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.

Embodied Agent Interface — VirtualHome (VH; n=342 AS, 338 SD) and BEHAVIOR (BEH; n=100 AS, 100 SD). Task SR / Execution SR (%). Leaderboard baselines from Li et al.; each base LM is grouped with its full Meta-Ctrl (γ+β) result. Best per column in green.
Model	Action Sequencing				Subgoal Decomposition
	Task SR		Exec SR		Task SR		Exec SR
	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)	88.7	34.0	95.7	64.0	88.2	36.0	92.0	53.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

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.

Probabilistic lookahead vs. hard masking on Llama 3 8B (Task SR / Exec SR, %). Hard masking applies the syntactic DFA as a local mask each step (standard grammar-constrained decoding); Meta-Ctrl adds HMM backward-DP lookahead. Both enforce the same syntactic guarantee.
Method (Llama 3 8B)	VH AS	VH SD	BEH AS	BEH SD
Hard masking (γ DFA)	1.4 / 97.3	0.0 / 96.0	12.0 / 20.0	19.0 / 31.0
Meta-Ctrl (γ+β, ours)	88.7 / 95.7	88.2 / 92.0	34.0 / 64.0	36.0 / 53.0
Δ Task SR	+87.3	+88.2	+22.0	+17.0

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.

Watch-And-Help (WAH-NL), single-agent, n=100, under the LoTa-Bench protocol. SR: full-task success; SSR: subgoal success; Exec: executable-plan rate. External references use different LMs / executors (ballpark context). Same-LM rows 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=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 (ours)	Llama 3.1 8B	0.470	0.705	1.000

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 Demonstrations

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

Real-robot tabletop tasks executed with Meta-Ctrl plans. — Real robot setup with an 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). Eight BEHAVIOR-derived long-horizon tasks are demonstrated; three pick-and-place tasks are evaluated end-to-end over 20 rollouts each.

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).