{"id":"2317412e-4410-40db-86cf-660cd2451e23","arxiv_id":"2505.08735","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Preference Optimization, a DPO-style training loss that ranks sampled solutions by their objective value, speeds up and improves RL-based neural solvers for combinatorial problems.","lead":"This paper replaces the usual reinforcement learning reward in neural routing solvers with a ranking signal that compares sampled solutions, and shows faster training and better routes on TSP, CVRP, and scheduling problems. A generalist would read it to see how RLHF-style preference training is moving into combinatorial optimization.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed equivalence between Eq 7 and the entropy-regularized objective Eq 3 is false: with deterministic reward-generated preferences, the classification loss has a degenerate optimum, not the Boltzmann policy π* ∝ exp(r/α).","rationale":"The reader's weakest_assumption correctly identified the missing proof of equivalence between Eq 7 and Eq 3. My stress-test sharpens this: the equivalence is not just unsupported, it is violated by the actual objective. Eq 7 is a Bradley-Terry classification loss over deterministic preference labels derived from the ground-truth reward. For a fixed instance, the supremum of this loss over the policy simplex is attained only as the policy concentrates on the argmax-reward trajectory; the Boltzmann policy of Eq 4 gives strictly negative loss and a nonzero gradient that continues to push probability toward the best trajectory. Thus the entropy-regularized interpretation in Section 3.3 does not hold for the implemented loss. The uniform-reference assumption that a DPO-style derivation would require is never stated and, even if it were, would not resolve the deterministic-label degeneracy: with noiseless preferences, the maximum likelihood solution of a BT model is a degenerate distribution rather than a finite-temperature Boltzmann policy. Because the central theoretical contribution of the paper is the reparameterized entropy-regularized objective and the claim that PO can seamlessly substitute policy gradient methods, this flaw undermines the paper's main argument. The empirical results may still indicate that PO works as a heuristic, but the paper as written would need substantial revision to remove the false equivalence claim and to reframe PO as an empirically motivated surrogate. For that reason, I recommend moving from CONDITIONAL to REJECT, while acknowledging that the empirical section could support a weaker, purely empirical claim after revision.","tokens_in":25657,"tokens_out":15231,"duration_ms":166226,"concrete_test":"Construct a single fixed instance with three trajectories and rewards r1 > r2 > r3, e.g., r = (3, 2, 1), and set α = 1. Parameterize πθ directly on the probability simplex and optimize Eq 7 (or the surrogate gradient Eq 8) with exact enumeration of all pairs, starting from the Boltzmann policy π* ∝ exp(r/α). If the iterate moves away from π* and the objective's supremum is approached only as πθ → (1, 0, 0), the claimed equivalence fails. This test is exact, requires only a few lines of code, and settles whether the classification objective recovers the entropy-regularized optimum.","verdict_should_be":"REJECT","load_bearing_attack":"The load-bearing step in the derivation is the assertion that maximizing Eq 7 solves the entropy-regularized RL problem Eq 3. This is not merely unproven; it is incorrect as stated. Eq 7 contains no entropy term and no reference-policy KL term. Substituting Eq 5 into the Bradley-Terry model yields a classification loss over deterministic labels y = 1(r(τ1) > r(τ2)). Optimizing this loss over the policy simplex drives the logit α[log πθ(τ1) − log πθ(τ2)] toward +∞ for every preferred pair, which is achievable only as πθ concentrates on the highest-reward trajectory. The entropy-regularized optimum π* ∝ exp(r/α) is not a fixed point: at π*, the logit equals the true reward difference r1 − r2, and the gradient of the classification loss is proportional to σ(−(r1 − r2)) > 0, still pushing probability mass toward the better trajectory. The supremum of Eq 7 is 0, approached only as the policy becomes degenerate, whereas Eq 3 has positive entropy at its optimum for finite α. Proposition 3.1 only shows that adding an instance-dependent constant to the reward does not change the optimal policy; it does not bridge the mismatch between deterministic indicator labels and the BT/Thurstone likelihood, nor does it supply the missing reference policy that a DPO-style derivation would require. The paper's claim that PO formulates an entropy-regularized objective therefore fails for the actual loss being optimized.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Preference Optimization (PO), a training objective for neural combinatorial optimization solvers that replaces scalar rewards with pairwise preference labels derived from the ground-truth objective (route length or makespan). The method reparameterizes the reward as alpha times the policy log-probability plus a per-instance constant, converts trajectory comparisons into a logistic (or other) preference loss (Eq. 7), and optionally fine-tunes with local search (Eq. 9). It is evaluated on TSP, CVRP, and FFSP across several RL4CO baselines (AM, POMO, Sym-NCO, Pointerformer, ELG, MatNet, DIMES), reporting faster convergence and lower optimality gaps than REINFORCE-based variants, plus a zero-shot generalization study.","tokens_in":25994,"tokens_out":8444,"duration_ms":86505,"significance":"PO is a conceptually appealing direction: it replaces the diminishing advantages of REINFORCE with a scale-invariant comparison signal, and the local-search fine-tuning procedure is a practical way to improve solution quality without extra inference cost. The empirical study is broad, the preference labels are anchored to the true objective, so the method is not circular, and the paper provides an implementation snippet and detailed hyperparameter tables. However, because the central equivalence claim (Eq. 7 versus Eq. 3) is not established and the empirical claims lack error bars or multiple seeds, the current form is not conclusive.","major_comments":[{"comment":"The load-bearing claim that maximizing Eq. (7) is equivalent to solving the entropy-regularized objective Eq. (3) is not established and is incorrect as stated. With deterministic labels y = 1(r(tau1) > r(tau2)), the Bradley-Terry loss in Eq. (7) is a binary classification loss with logit alpha[log pi_theta(tau1|x) - log pi_theta(tau2|x)]. Optimizing this loss over the policy simplex drives the logit to +infinity for every preferred pair, which is achievable only as pi_theta degenerates onto the highest-reward trajectory; the Boltzmann optimum pi* proportional to exp(r/alpha) of Eq. (4) is not even a stationary point, since at pi* the gradient for the preferred trajectory is proportional to sigma(-(r(tau1)-r(tau2))) > 0. Proposition 3.1 only shows that per-instance reward shifts do not change the optimal policy of Eq. (3); it does not supply the missing reference policy or bridge deterministic indicator labels to the BT/Thurstone likelihood. Please either prove the equivalence under explicit assumptions (stochastic preference labels, a reference policy, or an additional regularizer) or remove the claim that PO \"formulates an entropy-regularized objective\" from the abstract and Section 3.3.","section":"Section 3.3, Eq. (7) vs. Eq. (3)"},{"comment":"The empirical comparison lacks any measure of uncertainty. All gaps in Tables 1-3 and all convergence curves in Figures 2, 4, and 5 are single point estimates, and Figure 3 reports only point values; without multiple seeds and error bars (or at least bootstrap confidence intervals over test instances), the claim that PO \"significantly outperforms\" REINFORCE-based methods is not supported. Please report means and standard deviations over at least 3-5 independent training runs and state the number of seeds in every table and figure.","section":"Section 4, Tables 1-3, Figures 2-5"},{"comment":"The hyperparameters alpha and the preference model are tuned separately for each problem and solver (e.g., alpha = 0.05 for TSP and 0.03 for CVRP with POMO; BT for TSP and Exponential for CVRP). This tuning makes it difficult to attribute the observed gains to the PO objective rather than to per-task calibration. Please include a sensitivity analysis over alpha and over the preference model, or justify why the chosen values are comparable across methods.","section":"Appendix E.2, Tables 4-9"},{"comment":"The claim that PO \"naturally aligns with an imitation learning perspective\" and therefore handles the off-policy LS-refined solutions without importance sampling is asserted rather than demonstrated. Eq. (9) is a behavior-cloning term on LS outputs, and the paragraph does not analyze how this term interacts with the preference objective or why distribution shift is not a concern. Please provide a formal argument or an ablation that isolates the fine-tuning contribution.","section":"Section 3.4, Eq. (9)"}],"minor_comments":[{"comment":"Eq. (7) has a notational inconsistency: the expectation is over tau ~ pi_theta(·|x), but the integrand refers to tau1 and tau2; the objective should be written over pairs, and the normalization in Eq. (8) should match Algorithm 1.","section":"Section 3.3, Eq. (7)"},{"comment":"In Eq. (5), the symbol r is used where the surrounding text distinguishes the latent reward \\hat r; please use consistent notation.","section":"Section 3.3, Eq. (5)"},{"comment":"There are typos in the code snippet: \"preference_optimazation\" should be \"preference_optimization\" and \"Brandley-Terry\" should be \"Bradley-Terry\".","section":"Appendix E.1"},{"comment":"In Section 2, \"such ask-Opt\" should be \"such as k-Opt\".","section":"Section 2"},{"comment":"Table 2 reports CPLEX times in hours but uses \"x\" for FFSP50 and FFSP100; please clarify whether these are per-instance or total times and why entries are missing.","section":"Table 2"}],"recommendation":"major_revision","confidential_remarks":"The main theoretical result needs correction; if the authors are willing to reframe the contribution as a heuristic objective with strong empirical support, the paper could be publishable after the empirical rigor issues are addressed. I do not see evidence of circularity, as preferences are anchored to the true objective."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the paper has a useful empirical idea and a lot of experiments, but the theoretical justification in Section 3.3 doesn't hold up. The loss they actually optimize is not the entropy-regularized objective they claim.\n\nWhat's new: applying DPO-style preference optimization to neural COPs, using ground-truth rewards to generate pairwise preferences, and folding local search into fine-tuning. The experiments are broad: TSP, CVRP, FFSP across AM, POMO, Sym-NCO, Pointerformer, MatNet, DIMES, ELG, and they consistently show 1.5-2.5x faster convergence and small but consistent gap improvements. That's a solid empirical contribution—if the training recipe reproduces, it's genuinely useful for the RL4CO community.\n\nThe problem is the derivation. Eq 3 is the entropy-regularized objective, and Eq 4 is the Boltzmann policy. To rewrite the reward in terms of the policy, you need a reference policy—the term that makes DPO work. The authors drop it, leaving log pi_theta differences in Eq 6. Then Eq 7 maximizes the likelihood of deterministic preference labels. That objective has no entropy or KL term. With deterministic labels, its optimum is a degenerate policy that puts all mass on the best trajectory, not the Boltzmann distribution over rewards. Proposition 3.1 only shows reward-shift invariance, which is not the missing ingredient. So the central claim—that PO formulates an entropy-regularized RL objective—is false as stated.\n\nMinor issues: no error bars or seeds in the tables; alpha and the preference model (BT vs Exponential) are tuned per problem and architecture, which weakens the 'drop-in replacement' claim; code isn't released. These are fixable in a revision.\n\nWho's this for: people working on neural combinatorial optimization who want a practical training trick. The empirical story is worth engaging with, but I wouldn't cite it for the theory. If I were an editor, I'd send it to review with the request to either prove the equivalence properly (with a reference policy) or reframe PO as a heuristic ranking objective and drop the entropy-regularized language. As is, it's an honest but flawed paper.","headline":"Useful empirical recipe for DPO-style training in neural COPs, but the claimed entropy-regularized grounding is wrong.","tokens_in":26528,"tokens_out":4351,"would_cite":false,"duration_ms":44709,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that training combinatorial-optimization solvers on qualitative pairwise preferences between sampled solutions, instead of raw reward magnitudes, yields faster convergence and better solutions than REINFORCE-style…","keywords":["preference optimization","combinatorial optimization","reinforcement learning","neural solvers","entropy-regularized RL","direct preference optimization","traveling salesman problem","vehicle routing problem"],"falsifier":"Take a small combinatorial instance such as TSP with 8-10 cities, enumerate all tours to compute the exact entropy-regularized optimal policy $\\pi^*(\\tau|x) \\propto \\exp(r(x,\\tau)/\\alpha)$, train a policy with Eq. 7 from reward-generated labels, and compare the learned log-probability differences with the exact Gibbs differences; a systematic mismatch at high label accuracy would falsify the claimed equivalence.","tokens_in":25427,"feed_emoji":"🧩","tokens_out":9266,"duration_ms":77009,"temperature":0.7,"pith_summary":"The paper tries to establish that a preference-based training objective, which it calls Preference Optimization (PO), can replace the usual REINFORCE gradient in neural solvers for combinatorial optimization. Instead of scaling policy updates by a numerical advantage, the method labels each sampled solution as better or worse than another sampled solution and trains the policy to predict the winner. Because the reward is reparameterized in terms of the policy, the preference probability between two solutions becomes a function of their log-probability difference, and the intractable partition function cancels. The authors argue that this stabilizes training when rewards stop differentiating good from bad solutions, promotes exploration through an entropy-regularized objective, and lets local search be folded into fine-tuning rather than paid for at inference. A sympathetic reader would take the paper's claim to be that PO is a drop-in replacement for policy-gradient training that converges faster and finds shorter tours and schedules on TSP, CVRP, and FFSP benchmarks.","feed_headline":"Pairwise preference labels train neural solvers faster and better","feed_subtitle":"Qualitative comparisons replace numerical rewards, cutting training epochs and improving routes and schedules.","key_machinery":"The load-bearing object is the reward-to-policy reparameterization identity of Eq. 5, $\\hat{r}(x,\\tau) = \\alpha \\log \\pi(\\tau|x) + \\alpha \\log Z(x)$, obtained by inverting the analytical form of the entropy-regularized optimal policy. This identity turns a preference model into a policy-only objective: substituting it into the paired-comparison probability gives Eq. 6, $p(\\tau_1 \\succ \\tau_2 | x) = f(\\alpha [\\log \\pi(\\tau_1|x) - \\log \\pi(\\tau_2|x)])$, where $Z(x)$ cancels as an instance-dependent constant. The machinery then works by generating conflict-free preference labels from the grounding reward, maximizing the classification likelihood in Eq. 7, and, in the fine-tuning phase, treating local-search-improved solutions as preferred trajectories as in Eq. 9. The identity does the main work: it converts an intractable entropy-regularized RL problem into a tractable pairwise classification problem over sampled trajectories.","core_discovery":"The central claim, stated on the paper's own terms, is that the analytical relation $\\hat{r}(x,\\tau) = \\alpha \\log \\pi(\\tau|x) + \\alpha \\log Z(x)$ from the entropy-regularized optimal policy lets the probability that one trajectory is preferred over another be written as $p(\\tau_1 \\succ \\tau_2 | x) = f(\\alpha [\\log \\pi_{\\theta}(\\tau_1|x) - \\log \\pi_{\\theta}(\\tau_2|x)])$. Using the true objective to generate conflict-free preference labels, PO trains the policy by maximizing the likelihood of these preferences rather than by regressing on reward magnitudes. The resulting update in Eq. 8 replaces the advantage $r(x,\\tau) - b(x)$ in REINFORCE with a signed comparison term that is invariant to affine reward transformations, so it keeps separating good from bad solutions even when advantage values shrink. With the Bradley-Terry or exponential preference models, the paper reports that PO converges 1.5x-2.5x faster than the corresponding REINFORCE variants on POMO, Sym-NCO, and Pointerformer, improves solution quality on TSP, CVRP, and FFSP, and that fine-tuning with local search cuts the TSP-100 gap to 0.03% and CVRP-100 to 1.19% without extra inference time.","pith_inferences":["If the claimed equivalence between preference classification and the entropy-regularized objective holds only approximately, the method still works as an uphill heuristic: what matters is that the gradient increases probability mass on better solutions, not that the final policy is exactly the regularized optimum.","The ordinal-signal idea transfers to problems where a numeric reward is unreliable or multi-objective, since 'which solution is better' labels are easier to specify than a scalar reward; the paper gestures at multi-objective optimization but does not claim this extension.","Folding local search into fine-tuning turns the solver into an imitation learner of improved trajectories, so a testable extension is to tighten the off-policy story by comparing PO with an explicit DAgger-style correction when local search shifts the solution distribution."],"forward_implications":["Training time shrinks: PO reaches the performance REINFORCE achieves at epoch 200 in roughly 40%-60% of the epochs, with comparable gains on FFSP and large-scale TSP.","Final solution quality improves at no inference cost, because local search generates preference pairs during fine-tuning rather than running at test time.","PO is architecture-agnostic: swapping the update rule into POMO, Sym-NCO, Pointerformer, MatNet, ELG, DIMES, COMPASS, and Poppy improves or matches each baseline, placing the benefit in the training objective rather than the network design.","Preference labels are invariant to positive affine reward transformations, so the learned policy should be insensitive to reward shaping or to rescaling of route lengths and makespans."],"supporting_citations":[{"why":"Supplies the key trick of reparameterizing the reward in terms of the policy so that preference optimization can proceed without learning a reward function.","marker":"Rafailov et al. (2024)"},{"why":"Establishes the entropy-regularized RL objective and its analytical optimal policy, which PO inverts to obtain Eq. 5.","marker":"Haarnoja et al. (2017)"},{"why":"Provides the maximum-entropy derivation of the Gibbs-form optimal policy used for Eq. 4.","marker":"Ziebart et al. (2008)"},{"why":"Defines the attention-model REINFORCE baseline and the TSP/CVRP benchmark setup that PO's experiments build on and compare against.","marker":"Kool et al. (2019)"},{"why":"Defines POMO, the main solver architecture whose REINFORCE training PO replaces to demonstrate faster convergence and better gaps.","marker":"Kwon et al. (2020)"},{"why":"Supplies the preference-based RL framing and the paired-preference data model PO adapts to combinatorial optimization.","marker":"Wirth et al. (2017)"},{"why":"Provides the statistical paired-comparison model linking reward differences to preference probabilities, used in Eq. 2 and in the Plackett-Luce variant.","marker":"Plackett (1975)"}],"fun_headline_variants":["Preference labels replace reward signals for neural solvers","Pairwise comparisons train solvers faster and better than rewards","Preference optimization: qualitative signal for combinatorial problems","Local search fine-tuning improves preference-based neural solvers","From rewards to preferences: new RL method for TSP and CVRP"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole method rests on the unproved assumption that maximizing the likelihood of reward-generated pairwise preference labels drives the policy to the same optimum as the entropy-regularized RL objective; if that equivalence fails, the method is a heuristic whose guarantees evaporate.","fun_headline_variants_meta":{"raw":{"variants":["Preference labels replace reward signals for neural solvers","Pairwise comparisons train solvers faster and better than rewards","Preference optimization: qualitative signal for combinatorial problems","Local search fine-tuning improves preference-based neural solvers","From rewards to preferences: new RL method for TSP and CVRP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000296,"raw_usage":{"total_tokens":1755,"prompt_tokens":1019,"completion_tokens":736,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":635,"completion_tokens_details":{"reasoning_tokens":655}},"tokens_in":635,"tokens_out":736,"duration_ms":7206,"temperature":1.0,"reasoning_tokens":655,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:48:39.892370+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small combinatorial instance such as TSP with 8-10 cities, enumerate all tours to compute the exact entropy-regularized optimal policy $\\pi^*(\\tau|x) \\propto \\exp(r(x,\\tau)/\\alpha)$, train a policy with Eq. 7 from reward-generated labels, and compare the learned log-probability differences with the exact Gibbs differences; a systematic mismatch at high label accuracy would falsify the claimed equivalence.","supporting_citations":[{"cited_title":"Reinforcement learning with deep energy-based policies","cited_arxiv_id":null,"evidence_quote":"Establishes the entropy-regularized RL objective and its analytical optimal policy, which PO inverts to obtain Eq. 5."},{"cited_title":"D., Maas, A","cited_arxiv_id":null,"evidence_quote":"Provides the maximum-entropy derivation of the Gibbs-form optimal policy used for Eq. 4."},{"cited_title":"Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019","cited_arxiv_id":null,"evidence_quote":"Defines the attention-model REINFORCE baseline and the TSP/CVRP benchmark setup that PO's experiments build on and compare against."},{"cited_title":"Pomo: Policy optimization with multiple optima for reinforcement learning","cited_arxiv_id":null,"evidence_quote":"Defines POMO, the main solver architecture whose REINFORCE training PO replaces to demonstrate faster convergence and better gaps."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the statistical paired-comparison model linking reward differences to preference probabilities, used in Eq. 2 and in the Plackett-Luce variant."}],"review_version":1}