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

Rabimba Karanjai; Qun Gu; Hemanth Hegadehalli Madhavarao; Wenhuan Sun; Xiaojiao Yu; Suryabhan Singh Hada; Libin N. George; Uma Kona

cs.AIOct 6, 2026

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

Authors: Rabimba Karanjai, Qun Gu, Hemanth Hegadehalli Madhavarao, Wenhuan Sun, Xiaojiao Yu, Suryabhan Singh Hada, Libin N. George, Uma Kona, +3 more

Organizations: PayPal AI Lab

Abstract

Direct Preference Optimization (DPO) treats all constraint violations equally: a $1 budget overshoot and a$ 1,000 overshoot induce the same training signal. It is also susceptible to length and style bias when preference pairs come from different model families. We introduce Constraint-Margin DPO (CM-DPO), which replaces DPO's binary preference signal with a continuous margin derived from a deterministic symbolic verifier and scaled by violation severity. Hard and soft constraints are separated through a lexicographic objective, ensuring hard constraints are never traded off against preferences. To supply CM-DPO with bias-reduced training pairs, we generate preference data through procedurally generated constraint profiles (DCCG) and minimal-edit distillation from a reasoning teacher (RT-MED), within a framework we call SynPlan-R. On TravelPlanner, NaturalPlan, and out-of-distribution PlanBench, an 8B model fine-tuned with CM-DPO achieves 89.2% pass rate and 93.4% solve rate, matching multi-agent systems at 13x lower latency while outperforming GPT-4o on unseen Blocksworld by 9.2 points.

Figures & tables

Figure 1: The SynPlan-R architecture. Phase 1: DCCG decomposes each profile into hard constraints

\mathbf{C}_{hard}

(red), soft preferences

\mathbf{C}_{soft}

(blue), and a procedural knowledge

Panel of Figure 2 — Figure 2: RT-MED qualitative example The hard constraint is total cost $\leq 600$ , and the soft constraint is a preference for boutique hotels. Left: the student draft violates the budget constraint (hotel at $195/night, yielding a total cost of$ 650). Center: RT-MED swaps only the hotel ( $\sim 12$ tokens). Right: a full rewrite changes $\sim 245$ tokens and introduces style bias. Bottom: token-count and PR comparison.

Figure 3: CM-DPO vs. Standard DPO. Standard DPO assigns the same penalty regardless of violation severity. CM-DPO scales the margin

\gamma m_{c}

proportionally to the budget overshoot, producing stronger repulsion for larger violations.

Table 4

Method	TravelPlanner			NaturalPlan	Eff.
Method	PR $\uparrow$	DR $\uparrow$	$\bar{\mathcal{S}}$ $\uparrow$	SR $\uparrow$	Lat. $\downarrow$
External baselines
Zero-Shot (Llama-3-8B)	1.3	35.4	—	18.5	2.1s
Zero-Shot (GPT-4o)	39.8	88.3	0.61	68.4	5.4s
MAS (LRPlan w/ GPT-4o)	89.4	98.1	0.72	95.1	28.5s
SynPlan-R ablations (Llama-3-8B)

Table 3: Main results. SynPlan-8B reaches a TravelPlanner pass rate close to MAS performance (89.2% vs. 89.4%) while reducing latency from 28.5s to 2.1s. The soft-preference score

\bar{\mathcal{S}}

is computed only over feasible plans.

	Standard DPO		CM-DPO
	PR	Tok $\Delta$	PR	Tok $\Delta$
Full Rewrite	64.1	245	72.6	245
RT-MED	78.3	32	89.2	32

Table 4:

2\times 2

ablation on TravelPlanner pass rate (%).

Table 7

Domain	$\|V_{C}^{\text{hard}}\|$	$\|V_{C}^{\text{soft}}\|$	$\|V_{E}\|$	avg. $\|E_{\text{grounds}}\|$
Travel	3.4	1.8	41.2	14.7
Retail	3.2	2.0	28.4	11.9

Table 7: Constraint-profile graph statistics (averaged across instances).

Constraint	$\tau_{j}$	Unit
Travel: cost overflow	84	USD
Travel: time violation	38	minutes
Travel: pace deficit	1	cities
Retail: budget overflow	138	USD
Retail: feature missing	1	feature count
Retail: compat violation	1	edge count

Table 8: Severity normalization constants

\tau_{j}

(frozen).

Metric	Value
Hard-pass/fail agreement with manual labels	$98.7\%$ ( $296/300$ )
Wilson 95% CI	$[96.7\%,99.6\%]$
False-pass rate	$0.3\%$ ( $1/300$ )
False-fail rate	$1.0\%$ ( $3/300$ , all schema-ambiguity)
Schema-failure (decode failure) rate over synthesis stream	$1.7\%$

Table 9: Verifier audit on 300 manually labelled pairs.

Benchmark	Max 8-gram overlap
TravelPlanner reference plans	0.0%
TravelPlanner queries	0.0%
NaturalPlan gold schedules	0.0%
PlanBench action sequences	0.0%

Table 10: Contamination audit (max 8-gram overlap with benchmarks).

Margin source $m_{c}$	PR % (count)	$\bar{S}$
Random $\sim\mathrm{Unif}[0,1]$	65.6 (118/180)	0.53
Length-difference (R-DPO style)	67.8 (122/180)	0.54
Reward-model gap	73.3 (132/180)	0.56
Raw severity (un-normalized)	84.4 (152/180)	0.61
Verifier-derived normalized severity (ours)	89.4 (161/180)	0.64

Table 11: Margin-source ablation, TravelPlanner-val. All variants use the same

\mathcal{D}

and the same SFT initialization.

	$\gamma\!=\!0.5$	$\gamma\!=\!1.5$	$\gamma\!=\!3.0$
$\lambda\!=\!0.005$	81.7	84.4	83.3
$\lambda\!=\!0.01$	84.4	89.4	87.8
$\lambda\!=\!0.02$	83.3	87.2	82.2

Table 12: Sensitivity of TravelPlanner-val PR (%) to

\lambda

and

\gamma

$\alpha$	PR % (count)	$\bar{S}$
$0.0$	89.4 (161/180)	0.51
$0.3$ (default)	89.4 (161/180)	0.64
$0.6$	88.3 (159/180)	0.66
$1.0$	86.7 (156/180)	0.68

Table 13: Effect of

\alpha

on TravelPlanner-val.

Pairs synthesized	API cost	Marginal pass-rate gain
$5{,}000$	$110	$+18.4$ pt over SFT
$10{,}000$	$215	$+24.3$ pt
$15{,}000$ (reported)	$320	$+25.0$ pt
$25{,}000$	$535	$+25.6$ pt

Table 15

Explore similar work

Programming over Thinking: Efficient and Robust Multi-Constraint Planning
Jan 14, 2026Derrick Goh Xin Deik, Quanyu Long, Zhengyuan Liu +2Large Language Model Planning Classical Planning
Nanyang Technological University, Singapore · Agency for Science, Technology and Research (A*STAR), Singapore
Continuous-Utility Direct Preference Optimization
Jan 31, 2026Muhammad Ahmed Mohsin, Muhammad Umer, Emily Fox
Stanford University, Stanford, California, USA
Boosting Direct Preference Optimization with Penalization
Jun 10, 2026Pengwei SunBacktranslation Augmented Direct Preference Optimization Penalties
Stanford University.

Jan 14, 2026, cs.AIJ/K move · Enter open · S save

Programming over Thinking: Efficient and Robust Multi-Constraint Planning

Derrick Goh Xin Deik, Quanyu Long, Zhengyuan Liu, Nancy F. Chen+1

Nanyang Technological University, Singapore · Agency for Science, Technology and Research (A*STAR), Singapore

Large Language Model Planning Classical Planning LLM Reasoning Strategies Planning

Open paper AskPDF arXiv

Multi-constraint planning involves identifying, evaluating, and refining candidate plans while satisfying multiple, potentially conflicting constraints. Existing large language model (LLM) approaches face fundamental limitations in this domain. Pure reasoning paradigms, which rely on long natural language chains, are prone to inconsistency, error accumulation, and prohibitive cost as constraints compound. Conversely, LLMs combined with coding- or solver-based strategies lack flexibility: they often generate problem-specific code from scratch or depend on fixed solvers, failing to capture generalizable logic across diverse problems. To address these challenges, we introduce the Scalable COde Planning Engine (SCOPE), a framework that disentangles query-specific reasoning from generic code execution. By separating reasoning from execution, SCOPE produces solver functions that are consistent, deterministic, and reusable across queries while requiring only minimal changes to input parameters. SCOPE achieves state-of-the-art performance while lowering cost and latency. For example, with GPT-4o, it reaches 93.1% success on TravelPlanner, a 61.6% gain over the best baseline (CoT) while cutting inference cost by 1.4x and time by ~4.67x. Code is available at https://github.com/DerrickGXD/SCOPE.

Abstract

Explore similar work

Programming over Thinking: Efficient and Robust Multi-Constraint Planning

Continuous-Utility Direct Preference Optimization

Boosting Direct Preference Optimization with Penalization