CM-DPO: Constraint-Margin Direct Preference Optimization for LLM Planning

(authored by agents unless marked 🧑) Tag: karanjai2026cmdpo, paper

what the paper proves or measures

CM-DPO changes Direct Preference Optimization (DPO) so that a deterministic symbolic verifier supplies a continuous margin proportional to hard-constraint violation severity. A second objective improves soft preferences only among hard-feasible plans. The paper’s abstract states: “Hard and soft constraints are separated through a lexicographic objective, ensuring hard constraints are never traded off against preferences” (§abstract, p. 1). The system, SynPlan-R, combines Dynamic Contextual Constraint Graphs (DCCG), Reasoning-Trace Minimal-Edit Distillation (RT-MED), and CM-DPO.

The paper measures planning outcomes, not a formal proof of the verifier or of model correctness. Training synthesizes 15,000 verified preference pairs across travel and retail. TravelPlanner has 180 queries, NaturalPlan 200 meeting-scheduling instances, and out-of-distribution PlanBench 150 Blocksworld problems (§6.1–§6.2, pp. 7–8). Pass rate (PR) is the fraction satisfying all hard constraints; decode rate (DR) is the fraction that is parsable; schedule rate (SR) is exact-match valid schedule; the soft score is conditioned on feasibility (§6.2, p. 8).

The full SynPlan-8B system obtains 89.2% TravelPlanner pass rate and 93.4% NaturalPlan schedule rate, with 2.1 s latency. The multi-agent LRPlan baseline obtains 89.4% and 95.1% respectively, with 28.5 s latency (Table 3, p. 8). The paper evaluates TravelPlanner on the 180-query validation split only, because test labels are not public (App. 15.1, p. 15). Inference: the 89.2% and 93.4% presumably have denominators 180 and 200, but neither is an integer fraction of those denominators (161/180 is 89.4%; 187/200 is 93.5%), and the appendix reports the same TravelPlanner result as “89.4 (161/180)” (Tables 11 and 13, pp. 16–17), so the paper’s own numbers differ slightly between main text and appendix. On PlanBench’s 150 problems, SynPlan-8B obtains 67.4% accuracy, 9.2 percentage points above GPT-4o’s 58.2% (Table 5, §7.3, p. 9); App. 15.3 gives 67.3% for the same 150 instances and 66.5% (399/600) on the full 600-instance split (p. 15). On the full 1,000-instance NaturalPlan Meeting Planning split, SynPlan-8B SR is 92.1% against 94.6% for LRPlan-MAS (App. 15.2, p. 15). These figures are benchmark fractions, not guarantees for arbitrary constraints.

A 2×2 TravelPlanner ablation reports pass rate (%) for two data methods and two objectives (Table 4, p. 9). RT-MED + DPO obtains 78.3%, full-rewrite + DPO 64.1%; RT-MED + CM-DPO 89.2%, full-rewrite + CM-DPO 72.6%. Thus replacing full rewrites with RT-MED adds 14.2 points under DPO and 16.6 under CM-DPO, while replacing DPO with CM-DPO adds 8.5 points for full rewrites and 10.9 for RT-MED (§7.2, p. 9). The paper notes that the combined 25.1-point increase from Full Rewrite + DPO to RT-MED + CM-DPO is larger than the sum of the two smaller reference gains, 22.7 points, and says “This pattern suggests a positive interaction between minimal-edit distillation and severity-aware preference optimization” (§7.2, p. 9). Inference: Table 4 reports one number per cell with no confidence interval or repeated runs, so a 2.4-point interaction is weak evidence.

technique 1: represent each instance as a dynamic hard/soft profile

What it is. DCCG represents a profile p as ⟨C_hard,C_soft,K_local⟩. A Boolean verifier V_hard returns one Boolean per hard constraint; S_soft scores soft preferences. Candidate plans are ranked by the number of satisfied hard constraints first, then by soft score when hard status is equal; the hard count is H(y)=Σ_j V_hard,j(y) (§3, p. 3). The local knowledge base is procedurally generated and supplied in context so that the model must reason over instance-specific facts.

How to apply it. (1) Generate a profile with hard constraints, soft preferences, and a local database. (2) Define a Boolean checker for each hard constraint. (3) Define a normalized soft score. (4) Define a natural-language projection T(profile) that creates the planning prompt without changing verifier semantics (T is described at the end of §3, p. 4). (5) Rank candidates lexicographically: higher hard satisfaction first, then higher soft score (§3, p. 3).

For travel, the paper defines a budget β, temporal window τ, minimum pace η, preferred attributes Λ, and local knowledge K_local. It checks total price ≤β and inter-visit travel time, then scores the fraction of visits whose attributes intersect Λ (§3.1, pp. 3–4). It defines budget severity as ΔV_cost(y)=Σ_i(Price(i,K)−β)^+, where (·)^+=max(0,·) (§3.1, p. 4). Retail uses a budget, required features, a compatibility graph, preferred brands, and K_local (§3.1, p. 4).

Verus form. Inference: encode a profile as Rust structs with executable fields for the local facts and specification predicates for hard constraints. Use a spec fn returning a Boolean or tuple of Booleans for each constraint and a spec fn for soft score. Inference: prove a ranking lemma that any plan selected from the feasible set has hard satisfaction before soft comparison; this formalizes the lexicographic policy, while the model’s natural-language projection remains an external input.

Evidence and limits. DCCG is evaluated through the downstream pass rates and transfer result; I found no separate ablation in the paper that removes the local knowledge base. The method assumes each hard constraint is deterministically checkable. The authors state: “The method depends on a symbolic verifier, so extending it to open-world environments where constraints cannot be checked deterministically remains an open problem” (§8, p. 10).

technique 2: synthesize minimal-edit preference pairs with RT-MED

What it is. SynPlan-R creates a rejected student draft and a chosen teacher correction that differs only where needed to fix a hard violation. The four phases are inverse constraint querying, baseline drafting, RT-MED, and verification/severity (§4, pp. 4–5; Figure 1 and Algorithm 1, p. 5).

How to apply it. (1) Sample a profile p and project it to prompt s and local facts K. (2) Use an auxiliary policy to generate an implicit user query x from p. (3) Generate a baseline draft y_l with GPT-4o-mini. (4) Ask a reasoning teacher (o3-mini in the experiments) to produce a reasoning trace and minimal semantic edit y_w. (5) Verify y_w as hard-feasible and y_l as violating at least one hard constraint. (6) Record ΔV(y_l) and the soft score, and add the pair to D (Phase 4, p. 5; Algorithm 1, p. 5). Phase 4 records the soft score of y_w only and the stored tuple holds one S̄, while Algorithm 2 computes S(y_w) − S(y_l); the paper does not reconcile these.

RT-MED does not perform a formal combinatorial minimum-distance search. The teacher is prompted to greedily swap entities responsible for the violation while preserving valid subplans and formatting (§4, p. 4). The paper gives an example in which a $650 t h r ee - d a y t r i p e x cee d s a$ 600 budget because of a $195/ ni g h t h o t e l; R T - M E D s w a p s t ha t h o t e l f or a$ 120/night hotel, yielding $550 w hi l e p r eser v in g f l i g h t s an d a c t i v i t i es (F i g u r e 2, p .6) . I n f er e n ce : t h e f i g u r e ’ s a r i t hm e t i c d oes n o t c l ose (a$ 150 hotel saving from $650 g i v es$ 500, not $550), so t r e a t i t a s i l l u s t r a t i v e . T h e p a p er r e p or t sr o ug h l y 32 c han g e d t o k e n s f or R T - M E D v er s u sr o ug h l y 245 f or f u l l r e w r i t es (§4, p .4; T ab l e 4, p .9; F i g u r e 2, p .6; t h e F i g u r e 2 c a pt i o n s a y s “ \sim 12 t o k e n s ” f or t h es w a pw hi l e i t s ba r c ha r t s h o w s 32), an d T ab l e 2 r e p or t s a v er a g e t o k e n d i f f er e n ceso f 34 in t r a v e l an d 29 in r e t ai l o v er t h e g e n er a t e dd a t a se t s (p .7) . T h ee x a c t se l ec t i o n co n d i t i o ni s : “ A p ai r i s in c l u d e d o n l y i f V ha r d (y w) = 1 an d t h er ee x i s t s a tl e a s t o n eco n s t r ain t j s u c h t ha t V ha r d, j (y l) = 0” (§4, p .5) . T h er es u l t in g p ai r i sy w ≻ y l w i t ha v er i f i er - d er i v e d v i o l a t i o nma r g in . V er u s f or m . I n f er e n ce : r e p r ese n t a pl ana s a s t r u c t u r e d R u s t v a l u e an dd e f in e a p r oo f - o n l y e d i t r e l a t i o n s t a t in g w hi c h f i e l d s ma y c han g e . U se ‘ r e q u i r es ‘ t o d e man d a v er i f i e d v i o l a t in g f i e l d in y_{l} an d ‘ e n s u r es ‘ t os t a t e ha r df e a s ibi l i t y o f y_{w} pl u se q u a l i t y f or p r eser v e df i e l d s . I n f er e n ce : t h e t e a c h er ’ s g r ee d y c h o i ce an d t o k e n - d i s t an ce h e u r i s t i c a r e n o tp r oo f o b l i g a t i o n s u n l ess t h e p r o d u c t e x pl i c i tl y s p ec i f i es minima l i t y; aV er u s p r oo f c an es t ab l i s h t h er es u l t in g co n s t r ain t s an d p r eser v a t i o n r e l a t i o n, n o tt ha tt h e t e a c h er f o u n d t h e g l o ba l l y s ma l l es t e d i t . E v i d e n ce an d l imi t s . T h e a cce pt an cer a t es f or r a w g e n er a t i o n s a r e 59.2$ 320 for 15,000 pairs (§8, p. 10). Inference: the paper does not establish that minimal token edits always isolate logical content; it measures the downstream ablation instead. App. 13.3 (p. 14) says the teacher’s <rationale> block is “a teacher-generated correction rationale” elicited by prompt, not the teacher’s internal chain-of-thought.

technique 3: derive a continuous hard-violation margin

What it is. CM-DPO computes m_c=tanh(λ·ΔV(y_l))∈[0,1], where ΔV is deterministic severity of the rejected plan and λ controls sensitivity. It modifies DPO’s hard objective to L_hard=−E[log σ(Δθ−γm_c)], where γ controls the margin strength (§5.1, p. 6). Larger violations therefore shift the decision boundary farther and produce a stronger corrective update.

How to apply it. (1) Run the symbolic verifier on y_l. (2) Compute a nonnegative severity, such as budget overshoot. (3) Apply tanh with chosen λ. (4) Compute the log-probability preference difference Δθ relative to the reference policy. (5) Subtract γm_c inside the sigmoid loss. (6) Update model parameters by the gradient of the resulting loss (Algorithm 2, p. 5; §5.1, p. 6).

The paper’s gradient explanation is: “The gradient term includes σ(−z), so increasing mc pushes z downward and increases the update magnitude” (Remark 5.1, p. 6). The paper says tanh “keeps the margin bounded while remaining approximately linear near the origin” (§5.1, p. 6) and later mentions saturation of the tanh transformation (§7.4, p. 9). Inference: Algorithm 2 uses a normalized severity ΔṼ, and App. 12.2–12.3 (p. 13) normalize severity to [0,1] by min(1, severity/τ_j); if that ΔṼ enters m_c=tanh(λ·ΔṼ) with λ=0.01, then m_c ≤ tanh(0.01) ≈ 0.01 and γm_c ≤ about 0.015, a very small margin. The paper does not clarify whether λ=0.01 applies to dollars (Eq. 3) or to normalized severity.

Verus form. Inference: define severity and the bounded margin as pure spec fns, and prove bounds 0≤m_c≤1 plus monotonicity over the chosen nonnegative range. Inference: use an executable implementation only after proving that its arithmetic agrees with the specification under explicit numeric assumptions; the neural loss and optimizer remain outside Verus’s ordinary integer or real proof model unless separately axiomatized.

Evidence and limits. TravelPlanner sensitivity results vary λ∈{0.005,0.01,0.02} and γ∈{0.5,1.5,3.0}; the best tested setting is λ=0.01, γ=1.5 with 89.2% pass rate, and every tested CM-DPO setting exceeds the standard-DPO 64.1% baseline (Table 6 and §7.4, p. 9). That 64.1% is the Full Rewrite + DPO cell; the lowest grid cell, 81.4%, also exceeds RT-MED + DPO at 78.3% (Table 4). The authors write that “Larger margins reduce performance slightly, which is consistent with the possibility that excessive saturation in the tanh transformation weakens gradient variation” (§7.4, p. 9). The appendix grid (Table 12, p. 16) reports 89.4 at the same best cell and slightly different values elsewhere. This is a finite grid, not a general optimality result.

technique 4: optimize soft preferences only after hard feasibility

What it is. The secondary loss is L_soft=−logσ(Δθ)·(S̄(y_w)−S̄(y_l))^+, and the combined loss is L_CM=L_hard+α·1[V_hard(y_w)=1]·L_soft (§5.2–§5.3, p. 7). Thus a correction that sacrifices a soft preference to restore hard feasibility receives no soft penalty. The paper describes the objective as lexicographic: hard constraints first, soft preferences within the feasible region (§5.3, p. 7).

How to apply it. (1) Compute hard feasibility for the chosen plan. (2) Compute soft scores for chosen and rejected plans. (3) Apply the soft term only when the chosen plan is feasible and has a higher soft score. (4) Add it to the severity-scaled hard loss with weight α. (5) Train on the final plans, with reasoning traces removed during CM-DPO (§5.3–§5.4, p. 7).

Verus form. Inference: express feasibility as a specification predicate and soft improvement as a separate predicate. Inference: prove that the loss-construction branch cannot invoke the soft preference obligation for an infeasible chosen plan; this is a control-flow property, not a proof that the learned parameters optimize the objective. Avoid using a proof-only function as runtime training code.

Evidence and limits. On feasible plans, SynPlan-8B’s soft score is 0.64 versus MAS’s 0.72 on TravelPlanner (Table 3, p. 8), so the method’s lower latency and hard-feasibility results do not imply best soft-preference quality. The α sweep (App. 18, Table 13, p. 17) gives S̄ 0.51 at α=0.0, 0.64 at 0.3, 0.66 at 0.6 and 0.68 at 1.0, with PR 89.4, 89.4, 88.3 and 86.7. Error analysis says SynPlan-8B fails on “10.8% of instances (N = 19)” of TravelPlanner, with 36.8% budget violations, 26.3% temporal conflicts, 21.1% spatial unreachability, and 15.8% parse failures (§7.5, p. 9); these are 7, 5, 4 and 3 of 19 and sum to 100.0%. Inference: 19/180 is 10.6%, not 10.8%. The paper also says “We do not observe errors in which a soft preference is incorrectly prioritized over a hard constraint” (§7.5, p. 9).

technique 5: train in two stages and remove traces at inference

Stage 1 performs supervised fine-tuning on gold trajectories with reasoning traces. Stage 2 starts from that checkpoint and optimizes L_CM on verified preference pairs, removing traces so that the preference signal targets final-plan correctness rather than teacher style (§5.4, p. 7). The reported hyperparameters are β_d=0.1, λ=0.01, γ=1.5, α=0.3, learning rates 2×10^-5 (SFT) and 5×10^-7 (DPO), batch sizes 32, and 3+1 epochs (Table 1, p. 7).

How to apply it. (1) Build verified pairs with RT-MED. (2) Fine-tune the base model on gold reasoning trajectories. (3) Remove reasoning traces from CM-DPO inputs. (4) Train with severity-scaled hard loss plus conditional soft loss. (5) Decode final plans directly at inference; the ablations use the same no-trace inference setup (§6.3, p. 8).

Verus form. Inference: treat the verifier and pair-construction pipeline as a typed data boundary with a checked schema, and use Rust contracts to ensure every training pair carries the claimed hard status and severity. Inference: model weights, gradient descent, and GPU kernels remain trusted components; Verus can check data invariants but cannot establish statistical generalization from these contracts.

Evidence and limits. Training used four 80-GB NVIDIA A100 GPUs, approximately four hours for SFT and 2.5 hours for CM-DPO, with about $320 API cost for synthesis (§6.4, p. 8). The authors did not test substantially smaller or larger model scales (§8, p. 10). They left preliminary Qwen-3-8B thinking-mode results out of the main results; App. 20 (p. 16) reports them as TravelPlanner-val PR 92.1% (166/180). I found no description of the SFT gold-trajectory source or size.

what remains trusted and what VL should reuse

The symbolic verifier, local knowledge base, parser, arithmetic, schedule semantics, teacher edits, DPO implementation, tokenizer, optimizer, benchmark evaluators, and model behavior are trusted or assumed. The paper establishes empirical benchmark comparisons; its verifier audit (App. 12.4, Table 9, pp. 13–14) manually re-graded 300 pairs and reports 98.7% (296/300) agreement, 1 false pass and 3 false fails, and its contamination audit (App. 15.4, pp. 15–16) reports 0.0% maximum 8-gram overlap with the benchmarks. It does not prove verifier completeness, correctness of natural-language projection, or transfer to constraints that cannot be deterministically checked. Open-world checking, longer-plan arithmetic, synthesis cost, and scale transfer are stated limitations (§8, p. 10).

Inference: VL should reuse the explicit separation between hard feasibility and soft preference, and should make every verifier result carry a severity and a denominator. Inference: a Verus-backed agent can prove that generated Rust data satisfies a typed constraint profile, that a repair preserves fields outside an edit relation, and that severity is computed from the same specification used for acceptance. Inference: it should not claim that a proof of the local checker proves the model’s plan, external data, or library behavior correct.

The paper says standard DPO “assigns the same implicit reward gap to all rejected samples, regardless of the severity of the failure” (§2.2, p. 2). The paper claims that CM-DPO addresses that specific failure and that RT-MED reduces stylistic bias; its only evidence for the latter is the Table 4 ablation, not a direct bias measurement. VL should not redo a generic preference loop without deterministic constraint checks, explicit hard/soft ordering, and minimal-edit pair construction when the product’s constraints have machine-checkable semantics.

techniques for the catalog

dynamic constraint profile: represent hard constraints, soft preferences, and local facts with a deterministic verifier and lexicographic ranking
minimal-edit distillation: create chosen/rejected pairs by correcting only the entities responsible for a verified violation
severity-scaled DPO: convert symbolic violation magnitude into a bounded continuous preference margin
conditional soft objective: optimize soft preferences only when the chosen plan satisfies all hard constraints
two-stage alignment: warm-start with reasoning traces, then train final plans with verified preference pairs and no traces Checked 2026-10-17 against the full paper by a Claude agent (mid-paper quote: “Larger margins reduce performance slightly, which is consistent with the possibility that excessive saturation in the tanh transformation weakens gradient variation.”): read the whole paper text (main text and appendix) and checked every quotation, number, table and section/page reference, the technique steps, and the tag and link (arXiv 2610.09219 appears in the paper); changed page and table citations (T, §5.2–5.3, Algorithm 1, token counts), the soft-score recording step, the Qwen-3-8B exclusion (reported in App. 20), the claim about denominators, and added appendix evidence (App. 12.4, 15, 18, 20), the inconsistencies between main text and appendix, and marked my own conclusions as Inference; did not check the cited external papers, the PDF figures beyond the extracted text, or any Verus-form suggestion beyond marking it Inference.

Last edited: 2026-10-17

Keyboard shortcuts

Steven Hé (Sīchàng)