NaDRO: Leveraging Dual-Reward Strategies for LLMs Training on Noisy Data
Authors: Haolong Qian
Xianliang Yang
Ling Zhang
Lei Song
Jiang Bian
Chun Yuan
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Models
Combinatorial Optimization
Preference Learning
Process Reward
Primary area: optimization
TL;DR: NaDRO employs unique preference and context-based rewards to effectively train LLMs on noisy data, enabling even smaller models to achieve superior performance in complex decision-making tasks.

Abstract: Group Relative Policy Optimization (GRPO) fine-tuning has demonstrated significant enhancements in reasoning tasks. However, it often relies on high quality labeled dataset, which is typically difficult to obtain. To address this challenge, we introduce \textbf{N}oise-\textbf{A}ware \textbf{D}ual-\textbf{R}eward \textbf{O}ptimization (\textbf{NaDRO}) to  effectively enhances the training of Large Language Models (LLMs) under noisy or ambiguous supervision. NaDRO operates through two key components: \textbf{(1) Preference-based Outcome Reward (POR)},which makes a principled bias-variance tradeoff, reducing training variance by learning from robust preference rankings instead of overfitting to single-best estimates; and \textbf{(2) Context Perception Reward (CPR) mechanism}, which ensures that LLMs conduct necessary qualitative assessment of the current problem state to foster deeper situational understanding prior to decision-making. To validate our approach in a realistic decision-making testbed, we model classic combinatorial optimization problems like the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) as Markov Decision Processes, generating training data via cost-limited exploration. Our results demonstrate that the fine-tuned Qwen 7B and Llama 3.1-8B models achieve statistically robust performance, significantly outperforming leading LLM baselines and standard fine-tuning methods on these complex benchmarks. Code is released at \url{https://github.com/microsoft/HeurAgenix/tree/NaDRO}.

NaDRO: Leveraging Dual-Reward Strategies for LLMs Training on Noisy Data
Haolong Qian' Xianliang Yang?, Ling Zhang?, Lei Song", Jiang Bian', Chun Yuan
TTinnhua Shenzhen International Graduate School, Tsinghua University Microsoff Research Asia, Microsoft gh123@mails llls. tsinghua. edu.
Abstract
Group Relative Policy Optimization (GRPO) fine-tuning has demonstrated signif- icant enhancements in reasoning tasks. However, it often relies on high quality labeled dataset, which is typically difficult to obtain. To address this challenge, we introduce Noise-Aware Duwl-Reward Optimization (NaDRO) effectively en- hances the training of Large Language Models (LLMs) under noisy ambiguous supervision. NaDRO operates through two key components: (1) Preference-based Outcome Reward (POR).which makes a principled bias-variance tradeoff, re- ducing training variance by learning from robust preference rankings instead overfitting single-best estimates; and (2) Context Perception Reward (CPR) mechanism, which ensures that LLMs conduct necessary qualitative assessment of the current problem state foster deeper situational understanding prior pacision-making To validate our approach a realistic decision-making testbed, model classic combinatorial optimization problems like the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) as Markov De- cision Processes, generating training data via cost-limited exploration. Our results demonstrate that the fine-tuned Qwen 7B and Llama 3. 3.B models achieve statis- tically robust performance, significantly outperforming leading L.MM baselines and standard fine-tuning methods on these complex benchmarks. Code is released at https: https:///ithuue www http://tt......oooooooooooooooo/ http:///ww/..ooooooo////////////
Mppa Reva(a,, Mgap Roar(a)) Mader Rator (9c)
State Space
Action Spece(A)
XN
GRPO Trainning
Training
Sincle repeoss
Reward System
CIPE roward
D-nd
Poliey
rowards
MCTS Search
AcurodAcctios
POR mward
Data Gencration
Figure 1: Training LLMs with NaDRO: Leveraging Noisy MCTS Data through Preference-based Outcome Reward (POR) (see Section 4.1 and Context Perception Reward (CPR) (see Section 4.2
'The work was conducted during Haolong's 's internship at Microsoft Research Asia. I Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Introduction
Large Language Models (LLMs) exhibit considerable promise in complex reasoning [44 but encounter notable challenges in long-horizon decision making tasks [5] 61. This challenge stems from fundamental ambiguity inherent (7) in such tasks: often, there is no single optimal action, and even if one exists, its true long-term value is nearly impossible to perfectly evaluate with finite computational resources. This reality creates a critical mismatch for existing fine-tuning techniques like Group Relative Policy Optimization (GRPO) g]. Applying such methods directly to these ambiguous, imperfect reward signals leads training instability and suboptimal performance (9).
To address this, we propose Noise-Aware Dual-Reward Optimization (NaDRO), a method enabling LLMs learn effectively from noisy data (TO), particularly within offline training paradigms such as GRPO 8 NaDRO is founded upon two core mechanisms:
Preference-based Outcome Reward (POR): This component makes principled bias- variance tradeoff. Instead of overfitting to a single, high-variance 'optimal action', it reduces training variance by learning from the more stable preference rankings of multiple candidate actions [
Context Perception Reward (CPR): a process reward, CPR incentivizes LLMs to accurately assess key qualitative features of the current problem state prior to reasoning and action selection. This provides a dense and immediate training signal [3 [4], counteracting the sparse, delayed rewards common in long-horizon tasks and mitigating the risk of "reward hacking".
To evaluate NaDRO's ability to handle noisy data in complex, hong-horizon tasks, we model classic combinatorial optimization problems, such as the Traveling Salesman Problem (TSP) and the Ca- pacitated Vehicle Routing Problem (CVRP), as Markov Decision Processes. In this setup, the LLM learns to act as a meta-controller, dynamically selecting heuristic algorithms. By generating training data via Monte Carlo Tree Search (MCTS), we effectively simulate the noisy and imperfect data conditions prevalent in specialized real-world domains. Our extensive experiments robustly show that small-sized models like Qwen 7B [15] and Llama 3.B-BB [16), when fine-tuned with NaDRO, significantly surpass the performance of leading LLMs, including GPT-4o and DeepSeek RI, on these demanding decision-make makinn tasks.
Our primary contributions are:
1. A Novel Paradigm for Noise-Robust LLM Training: NaDRO offers a new methodology for LLMs to effectively utilize large-scale, noisy exploration data in complex decision- making task, reducing reliance on perfectly labeled data.
2. Synergistic Noise Reduction via Dual Rewards:
NaDRO, through POR and CPR, synergis- tically optimizes learning signals from both outcome preference and intermediate reasoning process, enhancing learning efficiency and decision reliability in noisy environments.
3. Superior Empirical Performance: We demonstrate that moderately sideed LLMs like Qwen 7B and Llama 3.1-8B, when trained with NaDRO, can outperform leading LLMs challenging TSP and CVRP tasks.
4. Broad Generalization Potential: This research offers significant insights for applying and training LLMs in other complex decision-making domains characterized by difficult data acquisition,, high labeling costs, or inherent data noise.
2 Related Work
2.1 LLM Fine- Fine-Tuning for Reasoning and Decision-Making
Fine-tuning strategies are crucial for adapting LLMs to specialized reasoning tasks. Methods such as Reinforcement Learning from Human Feedback (RLHF) [12 II [7] and Direct Preference Optimization (DPO)
[88 have advanced model alignment. Concurrently, Group Relative Policy Optimization (GRPO) g leverages comparisons among multiple responses for logical reasoning
tasks. This paradigm increasingly applied to learning heuristic meta-policies [5] for sequential docision-making [19] where LLMs now act meta-controllers. A persistent challenge across these

---

approaches is their reliance on high-quality reward signals, performance degrades on the noisy data common long-horize tasks. Parallel fine-tuning, alternative post-training approaches (20 also aim to enhance LLM capabilities.
2.2 Test-Time Scaling Method
Complementary to training-time improvements, Test-Time Scaling (TTS) 23 is an inference-time strategy that enhances performance by exploring multiple candidate solutions 24 25]. While NaDRO focuses on improving the underlying policy quality during training, TTS can be applied during inference to further refine the final output by leveraging additional computation.
3
Preliminaries
MDP Formulation We model the task of dynamic heuristic selection as a Markov Decision Process (MDP). Within this framework, an LLM acts meta-controller policy, л (a, 8t). that maps the current problem state to heuristic action from predefined discrete set A. Applying the action transitions the environment to new state 8t+1. The objective is to learn a policy that optimizes quality of the final solution after sequence of H decisions.
Data Generation and Inherent Noise To train the LLM policy, we require state-action value pairs supervisory signals. We employ Monte Carlo Tree Search (MCTS) to explore the decision space from any given state 8, and generate an estimated value, (s o,). for each candidate action a, However, due to computational constraints and the eredit assignment problem inherent in long- horizon tasks, these Q-values are fundamentally noisy and imperfect approximations of an action's 's true long-term utility. A critical observation, empirically validated in Figure [ is that while the absolute scores from MCTS are unreliable, their relative rankings preserve a much more robust signal. The results show that policy constrained select actions from the top 30% of MCTS evaluated scores significantly outperforms random policy and achieves near optimal performance. This finding strongly suggests that an effective learning paradigm should focus on leveraging these robust preference signals rather than attempting to directly regress the noisy, absolute action values.
Optimal Gap%
optimal rendom sumple top randim sample from all actions
Figure 2: Preference learning effectiveness noisy data in rd100 task. The y-axis represents the optimality gap of the final solution. The optimal action policy always selects the action with the highest MCTS score, while the other policies sample from either the top 30% of actions all actions at each step.
4 Methodology
The GRPO algorithm, which is Reinforcement Learning with Verifiable Rewards (RLVR) paradigm, fundamentally challenged when applied to complex decision-making tasks. Unlike domains with clear, ground-truth answers such mathematics, these tasks often lack single correct action,

---

[rodiens prodec
Pribi repurs
joate proke portilly visted
Strasoning
=miniiing*
Ielasilan probee explaration
roward
<ipesstting"
Decnl
Carswer
Samowrr
the cXrmen Rith sentesed modes rensering.... cratt!
Prote nequese
Octput
Slanawors
epppp thr coreal
from Inseiical dadium dats rmunice beare te conabanslly
Civer du ou camone staa, with unrk Slndd modes reextizng....
We wlll hone 63 ansisted mudes insophaatton ulg.niiin RocoOna
Neay Stote
Jangarge
Gi Pital clts rundiningg.....
Lasetio
Lewaad
-]
+1
Predict
Figure Schematic of Reward Components for LLM Training with NaDRO, detailing Format Reward [8) Language Consistency Reward [26], and the operational mechanisms of the novel POR and CPR.
and any feasible evaluation of action quality is inherently noisy. Directly applying the standard GRPO approach to reward the highest value is therefore prone to training instability. To address this mismatch, we introduce NaDRO framework to enhance the learning process through its core contributions: redesigning the outcome reward to learn from robust preference rankings (POR) and supplementing with process reward for ambiguous outcomes (CPR). This dual-reward mechanism is complemented by standard auxiliary signals, such as format rewards g and language consistency rewards 26
4.1 Preference-based Outcome Reward (POR): Learning from Ordered Noisy Signals
To stabilize learning from noisy MCTS values, introduce the POR method to partition the ranked action space using a hyperparameter & E (0, 1) into a positive set A4 (top k%) and a negative set A.. An action's 's reward is then linearly scaled based its rank i within action space A:
RRp (1-
i-1 T--Nal Rn :- K.NA NA
if E A+ af A
Rpon(si, a.)
This design grounded in the learning target (a sharp Dirac delta function, 8(a a²) )) that, while unbiased in expectation, jumps erratically between batches and destabilizes training. POR replaces this with a softer target over the positive set, (a].4)) which significantly reduces training variance. This is achieved by introducing a minor bias, as the positive set A4 serves as robust proxy for the true optimal actions a". This principled tradeoff prioritizes learning stability over unbiasedness, necessary adaptation when dealing with inherently ambiguous or noisy evaluations.
tradeoff. A standard Top-1 approach uses high-variance
Furthermore, the selection of the hyperparameter l is also itself principled. We derive its optimal value by maximizing value separability term, defined as the expected value gap between the positive and negative action sets. We formalize this objective as:
J(k) E NA_ AEA-(()
Σ Q(a) Σ Q(a) NA (k) AkA+(K)
(2)
By modeling the relative action values based on MCTS, we can compute an estimate for [(k) for any given partition. The theoretically optimal partition is therefore found by solving for k. arg max (k). As demonstrated Section 5.3 this theoretical optimum aligns remarkably well with &
empirical findings, reinforcing the principled design of our framework.

---

4.2 Context Perception Reward (CPR): Unearthing Richer Process Rewards
Dependence exclusively on outcome rewards encounters significant challenges. Especially in complex long-horizon decision tasks, a valid reasoning process or accurate qualitative perception of the problem's 's present state typically underpins effective decision-making To address this, we introduce the CPR mechanism, designed to guide and evaluate the LLMs' pre-decision cognitive process and process-level rewards. Crucially, CPR provides a dense, immediate, and outcome independent learning signal, which helps mitigate the severe credit assignment problem and prevents the model from "reward hacking" by focusing on the reasoning process.
Specifically, the CPR mechanism requires the model, prior its standard reasoning, first conduct qualitative evaluations of key contextual dimensions, including problem type, problem state, current cost and other relevant features. The model must clearly output its assessment of these dimensions.
Without CPR Mechanism
With CPR Mechanism
Given the state space and sution space A, place select action accurlindy..
Gäves the stzee space 8 and action space A. plaase relect action accendingly
Ielgerilian
i encal cspaad canosi patk
From the Nokeaal Eackoon teuction bourbii hore consinanty card ... ingrantig that
Give locdback
coill cradial is cqued cunza
tinoncal dectove drs, tauatin becrutt
bisker racios in lasill in decunnel
Revg
comieratty said augonting
We addl lave 60 cavisited andes exploratiin alguritii it ancoenty pontann coisito cociisoicn of <ooinn
butict anci anvnt on cxnccal bot We stil lane 53 saniaked andes in cupheniiin algoriia incoaayy ancoiiiiii comontction of ile cooeiniing
Rove c
borieds aeareed Jesertiion
Figure 4: Impact of the CPR mechanism in rectifying qualitative judgment errors during LLM inference. The illustration shows how CPR guides the LLM towards accurate contextual assessments, mitigating errors that might otherwise go uncorrected.
As illustrated in Figure 4 even if the final decision happens to be correct or good, the model should not receive the full reward if it failed to establish correct understanding of the state. To quantify the quality the cognitive process, we define a CPR reward function for each state s;:
12
(stR(st):
Σ
[( v5.) 1(De. + vi.)) rj
Here, j corresponds the context perception dimensions, Dr.j denotes the model's response for the j-th contextual dimension at state 8t, and yī,; is the ground-truth label, which can be easily annotated due to its qualitative nature. We employed rule-based method for annotation, details can be found in Appendix B Reward weights assigned to correct and incorrect answers are denoted by r and rj. respectively.
Through the CPR mechanism, the LLMs are incentivized to learn how to accurately perceive and interpret the current state features of the problem. RETR provides learning signal that is independent of the final outcome, more immediate, and more stable.
5 Experiments
The NaDRO framework developed enhance LLM fine-tuning for a wide array of long-horizon drcision-makingg tasks. To empirically evaluate its effectiveness and demonstrate its capabilities, this study primarily focuses on heuristic algorithm selection in the context of TSP. Furthermore, to illustrate the generalizability of our method, we also present experiments conducted on CVRP, details can be found in Appendix A The core objectives of these evaluations are to rigorously assess NaDRO's s ability to leverage MCTS data for robust policy learning and to benchmark its performance.
5

---

5.1 Experimental Settings
5.1.1 Tasks and Datasets
The primary task for LLMs is a meta-controller, dynamically selecting the most appropriate heuristic algorithm at each decision step to progressively construct or improve solutions for TSP and CVRP instances.
We randomly selected a diverse set of 10 instances from the well-known TSPLIB benchmark library evaluate our method. These instances were chosen to cover range of sizes and complexities, ensuring that the evaluation captures both scalability and robustness to diverse structural patterns.
TSP:
We selected instances through 10 from the Golden dataset for CVRP. These instances are particularly challenging, characterized by large number of customers (n) ranging from 200 to 480 and vehicle fleet sizes (K) varying between 5 and 16. Detailed results can be found in Appendix
CVRP:
For each instance, a decision sequence consists of H steps, equal to N/nrun where N is number of nodes, frun is the running times of the heuristics selected each step. At each step f, LLMs observe the current state & and selects an action aj from a predefined action space (the full state space and action space are described in Appendix E F).
5.1.2 Models and Baselines
We employed the Qwenn.5-7B-Instructt-ee 15 and Llama-3.1-8B-Intruue [6 as base LLMs for fine-tuning with NaDRO method. To demonstrate its efficacy, compared the performance of MaDRO-Qwen 7B and NaDRO-Llama 1-8B against several baselines, including GPT-4o [27].
GPT-o3, Deepseek-R1 [26] Mainstream heuristic and meta-heuristic methods like OR-Tools, LKH EoH 31.
28
GLS 29
ACO 30
ReEvo 32 are also compared.
5.1.3 Training Data Generation
Training data in the form of (st; {a., Q(+,, a.) 1 pairs were generated using MCTS. For each state encountered during training instance generation process, MCTS was run for 1000 iterations to evaluate the set of NA candidate heuristic actions. The default policy for MCTS rollouts was random heuristic selection. This process inherently produces noisy values due to the limited search budget, as discussed in Section
5.1.4 Fine-tuning and Implementation Details
All models were fine-tuned using the GRPO algorithm. For NaDRO-Qwen 7B, NaDRO-Llama 3BB and the GRPO baseline, fine-tuning was performed with number generations set to 12. Details of the fine-tuning experiments
provided in Appendix [D] Experiments were performed on
a cluster with NVIDIA A100 and NVIDIA A6000 GPUs, leveraging the Unsloth framework (33] for optimized training efficiency. typical fine-tuning for our primary models took approximately 32 hours. Comprehensive fine-tuning procedures are further detailed Appendices C [ndd
5.2 Main Empirical Results on TSP
To evaluate the efficacy of our proposed NaDRO method, we conducted extensive experiments on Traveling Salesman Problem. The comparative results, presented in Table demonstrate the clear superiority and statistical robustness of the NaDRO framework.

---

Table 1: Comparative optimality gap (%) on TSP instances, sorted by problem size. Results for NaDRO-Qwen 7B and NaDRO-Llama 3-1-8B generated using our proposed NaDRO mechanism. For baselines, the performance of ReEvo 332 mentations.
and EoH [31] is based on their original code imple-
Method
p276
g296
xd100
ch130
pz162
u169
begiee
gx202
tcp226
a280
Traditional Soforrs
LKIL
0.00 1 0.0
0.0 1 0.0
0.00 1. 0.
0:00 0.0
0.0
0.01 1. 0.0
001
OR-Tools
7.4
GLSS
2.03
+.06
ACO
9:26
12:58 1.26
17.12
8,39
4.70 1.6
9:28 1.
3,43
10.43 2.7
9.71 2.1
17.28 1.3
Rebivo + GLS
1,56 +.0.6
2:57
6.70 + 2.1
5:04 1.9
2.88 1.6
3:99 + 1.5
4.11
5.80 0.7
4.73 1.6
3.92 +.05
Relivo + ACO
7.71 1.0.1
6,66 1.4
9.12 1: 0.9
5.85 1: 1.4
7.87
0.5
5.52 1: 0.1
3.91 2.3
8.29
1.4
6.99 1: 2.9
1591 2:2.1
22M L.Ad-dured Apprnachiss
GPT-4o
0.99 0:07
1.55 4:
2.18 0:0.7
3.19 0:03
2 +: 0.7
4,70 0.6
4.23 1.2
5.78 8: 0.6
7.11
GPT
0.44 0.5
2886
5:11
Despseek
1.18 1
2.27 1 0.8
1,3 0.5
2.94 0.5
0.5
6,47 1 0.9
14.10 1 0.7
7B
4.45
Qwen
1.14::00
733
3.5
Lllmna
0.5
0.8
301 0.7
2.00
7.33
LaDRo-LlamaiOurs)
0.31
0.28 0.L
0.70 0.02
2.19 1.
0.37 0.L
0.94 1. 022
2.17 0.3
2.41 0.5
4,89 1. 0.8
6.22.00.
TaDRO-Queen(hurs)
0.63 0.2
0.16 + 0.2
0.11 + 0.1
1 0.2
0.22 + 01
1.38
+ 0.3
0 + 0.1
2.29 0L3
3.76 + ILS
5:31 +31
The results in Table I demonstrate the clear superiority of our NaDRO framework. Our NaDRO- tuned models consistently and significantly outperform other LLM-based approaches, including larger models like GPT-4o, and are highly competitive with established metaheuristics. The most critical insight comes from the direct comparison against standard GRPO fine-tuning on identical base models (Qwen 7B and Llama 3.1 1-B). This comparison reveals decisive performance gains (for instance on the gr202, the optimality gap is reduced from 14.68% % with standard GRPO to just 2.29% with NaDRO) that are directly attributable to our novel reward architecture, not merely the act of fine-tuning, Furthermore, the low standard deviations across multiple runs confirm that these improvements are statistically robust. While a specialized solver like LKH defines the performance ceiling, NaDRO's ability to guide general-purpose LLM to surpass many strong metaheuristics highlights its practical efficacy for tackling complex combinatorial optimization problems.
5.3 Correctness Reward Dynamics and Robustness
To validate the robustness and practical applicability of the NaDRO framework, we analyzed the training dynamics of the answer correctness reward across different configurations. This analysis dissects the framework's 's sensitivity to the POR cutoff parameter k and its resilience under extreme data corruption.
Smoothed Correctness Reward( 10-2)
GRPO(Baseline)
GRPO+POR
NaDRO(k=0.1)
55
NaDRO(k=0.3)
NaDRO(k=0.5)
-10
NaDRO(k=0.7)
NaDRO(Randomized)
500
1000
1500
2000
2500
3000
Training Steps
Figure 5: Correctness reward dynamies during training on the pr152 instance. The y-axis represents the smoothed correctness reward for the CPR mechanism which is scaled by factor of 10 10-2.
7

---

The training dynamics presented in Figure offer critical insights into the NaDRO framework. Compared to the GRPO baseline, the introduction of POR (GRPO+POR) yields modest improve- ment; however, being fundamentally outcome-oriented its learning dynamic remains limited. The introduction of the CPR mechanism yields significant performance improvement, as seen in all NaDRO configurations, which rapidly achieve and maintain high level of correctness, forming distinct and vastly superior performance cluster.
Additionally, within the top cluster, the performance curves for a wide range of POR cutoff values (k sensitive this hyperparameter. from 0.1 0.7) are tightly grouped, confirming that NaDRO (ando(Randomized) curve, which And the framework's 's resilience is powerfully demonstrated by the simulates 10% chance of catastrophic data corruption at each step. Even under this severe noise condition, the model's 's ability remains almost unimpaired. This underscores NaDRO's 's exceptional resilience and suitability for training on the highly imperfect data found real-world scenarios.
The empirical observation that performance peaks around 0.7 not coincidental but is direct consequence the task's inherent value structure, which can analyze theoretically. This data- driven insight allows us to make a principled bias-variance tradeoff.. As discussed in Section 4.1 choosing larger & intentionally introduces bias towards broader set of positive actions. This specific bias, guided by the training data, stabilizes the learning process by reducing variance.
To formalize this, analyze the value distribution across action ranks. For TSP task (Na 15), we define the value decrease for a given state s as the difference between the action value at rank i + and rank i: (C:(s) E., (()+)((()) Qi(s)]. The Contribution Ratio for each rank transition, visualized in Figure 6 is then the expectation the voftmax-normalizae cost increases over the entire dataset D:
(xp(ACi(s)) Σ ソ= exp(AC,
p: E ESND
This value, P., represents the average relative magnitude of the performance drop occurring between rank and i + 1, normalized across all transitions. Figure 6 visualizes these average ratios.
35
Contribution to Total Cost Gap 1%)
80
25
20
15
10
5-
3.54
6:57
8:59
11:512
Transition between Action Ranks
Figure 6: Average Contribution Ratios Across Rank Transitions (TSP Task), Each bar represents the average percentage of the total value gap attributable to the drop between adjacent ranks.
Figure 6 reveals highly non-uniform value distribution specific to our TSP task dataset: the performance drop-off between the worst-ranked actions far more significant than the differences among the top-ranked ones. For instance, the transition from rank 14 to 15 alone accounts for over 33% of the total gap. This particular distribution suggests that, this task, prioritizing the avoidance of the worst actions is critical. By applying this relative value model to our Value Separability function J (k)), we can calculate the expected separability for every possible cutoff, as shown Table
2

---

Table Optimal Cutoff Determination via Value Separability Analysis
9
11
13
WNA (%)
6.7
13.3
20.0
26.7
33.3
40.0
46.7
53.3
60.0
66.7
73.3
80.0
86.7
93.3
((k)
0.3486
D.3809
0.3957
0.4071
04173
0,4280
0.4798
0,4550
0.4847
0.5106
0.5284
0,5262
0.4901
0.3953
The utility function [kk reaches its maximum at k = 11, corresponding to an optimal positive set ratio of 11/15 73.3%. This theoretical result provides strong justification for our empirical finding that performance peaks around h = 0.7.
5.4 Training Stability: Loss and Variance Analysis
Beyond final task performance, critical indicator of robust training framework is the stability of its optimization process. To provide empirical support for the theoretical motivations presented in Section we analyzed the training dynamics of our framework, focusing on two key metries: reward variance and training loss. These analyses reveal how NaDRO's dual-reward mechanism fosters more stable and effective learning process compared to baseline methods.
GAPOlBas2lin)
NaERO) GRRO
(uinnO/urst GRPD-POR
1063
5000 Traniig Stops
Taining Steos
(a) Reward variance dynamics
(b) Training loss dynamics
Figure 7: Training stability analysis. (a) The variance of the total reward signal over training steps. The NaDRO framework demonstrates significantly lower and more stable reward variance compared to the volatile baseline GRPO. (b) Training loss dynamics. The baseline GRPO's s loss rapidly collapses to near-zero value, indicative of "reward hacking," while NaDRO maintains a healthier, actively fluctuating loss. The y-axis values are scaled by factor of 10-4
Our analysis these dynamics, presented in Figure 7 First, Figure 7 shows that the NaDRO framework significantly reduces reward variance compared to the standard GRPO baseline. This result provides direct empirical validation for the core theoretical principle behind POR (discussed in Section D. by rewarding preference subset our method generates a more stable learning signal, which is fundamental for effective learning in noisy environments.
Furthermore, the training loss curves in Figure ()) offer a critical insight into the quality of the learning process. The standard GRPO model's loss quickly drops near-zero value and stagnates, classic symptom of "reward hacking" where the model exploits the reward function without learning robust strategy. In stark contrast, the NaDRO model maintains healthier, actively fluctuating loss. This dynamic, paired with its high final reward, proves that the model remains meaningfully engaged in learning rather than collapsing into trivial solution. Together, these findings demonstrate that NaDRO not only achieves superior results but does so via more stable and principled optimization process.
5.5 Ablation Studies
To dissect the individual contributions of NaDRO's key components and to evaluate the interaction with TTS, we conducted series of ablation studies. In our experiments, TTS refers to strategy where the model performs additional inference time computations to explore multiple candidate solutions before committing to final output. The "TTS Level" reported in Table quantifies the extent of this search effort.

---

Table Ablation Study: Impact of NaDRO Components and Search on the pr152 TSP
instance (Optimality Gap %)
TTS Level
Qwen 7B (Base)
GRPO Baseline
GRPO POR
NaDRO (Full, Ours)
18.33 + 1.2
11.57 1.4
6.74 1.1
3.17 + 1.1
5.83 = 0.9
4.66 + 1.8
3.54 + 0.8
1.74 + 0.7
3.62 = 0.3
3.86 0.5
2.64
1.77 + 0.2
4
1.69 = 0.3
2.14 0.3
1.79 0.2
1.48 + 0.2
10
1.31 = 0.2
1.04 0.1
0.87 0.2
0.22 + 0.1
20
0.88 0.1
0.87 + 0.2
0.63 0.1
0.16 + 0.1
30
0.32 = 0.1
0.41 + 0.1
0.14 0.1
0.04 + 0.1
The ablation results Table 3 validate NaDRO's component-win benefits and reveal a powerful synergy with test-time search (TTS). The TTS=0 results, which reflect pure policy quality, are particularly revealing: adding POR nearly halves the optimality gap of the GRPO baseline (from 11.57% to 6. 6.74%), and the full NaDRO framework halves it again to 3.17%, underscoring the critical impact of CPR. This superior base policy then creates a powerful synergy with TTS. While all configurations benefit from increased search, NaDRO's advantage widens as the TTS level increases, achieving near optimal gap of just 0.04% TTS=30.
Conclusion
To address the challenge of training LLMs for complex long- long-horizon decision-making with noisy data, this paper introduces NaDRO. By bridging preference-basee and process-based based rewards, NaDRO contributes to the broader goal of building LLM agents that are both robust imperfect supervision and aligned with human-like reasoning processes. Extensive experiments demonstrate that NaDRO enables moderately-sizee LLMs (Qwen 7B and Llama 8B), trained MCTSS-eeneaan noisy data, to significantly outperform LLMs. These findings underscore NaDRO's strong empirical performance and its efficacy in fostering robust learning from imperfect data, offering promising pathway towards more capable and data-efficient LLM agents for complex real-world decision-making
Limitation and Broader Impact
Limitations NaDRO's 's Context Perception Reward (CPR) currently relies on manually defined qualitative features and aale-based annotations. This dependency may limit its direct applicability to new domains requiring significant feature engineering and domain expertise. Future work should explore methods for automatically discovering or learning these crucial contextual features to enhance the framework's generality.
By enabling LLMs to learn more effectively from imperfect data, NaDRO can make advanced AI eeciisionmmaiing tools more practical for real- world applications (e.g., logisties, operations research) where perfectly clean data is scarce. This could improve efficiency and resource allocation.
Broader Impact
Acknowledgments
This work is supported by the National Key R&D Program of China (002XYBB470114004471444)) SSTIC Grant (KJZDD223092211151000 KJZD2002009231499 14916032, GJHZ2022422181116400088 and the National Natural Science Foundation of China (62502317).
References
[1] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoe Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models, 2023. URL httttp:://axxv.orrte htapg/abb/22200 11903
10

---

[2] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners, 2023. URL httpss//aaaxi org/ /b2//205 11916
[3] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of thoughts: Solving claborate problems with large language models. Pro- ceedings of the AAAI Conference Artificial Intelligence, 38(16)17682- 17690, March 2024. URL http: doi org 1609/
ISSN 2159-5399. doi: 10.1609/aaai, v3..69 www..vi.i11...... aaai v
[4] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models, 2023.
URL https::/axxii wrg. abs/ 2305. 10601
[5] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models, 2023. URL https
03629
[6] Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning, 2023. URL
https://arxisn org/ abs 2303. 11366
[7] Dillon Bowen, Brendan Murphy, Will Cai, David Khachaturov, Adam Gleave, and Kellin Pelrine. Data poisoning in Ilms: Jailbreak-tuning and scaling laws, 2024. URL. https
7 7/arxiv. org/abs/ absaabas2222 200.. 02946
[8] Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song. Xiao Bi, Haowei Zhang. Mingchuan Zhang, Y. K. Li, Y. Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathematical reasoning in open language models, 2024. URL //ttps://axxi... / abs/
0330003300
[9] Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline reinforcement learning, 2020. URL htt./tppp//axxxx..rrr///////////
[10] Wei Shen, Xiaoying Zhang, Yuanshun Yao. Rui Zheng, Hongyi Guo, and Yang Liu. Robust RLHF with noisy rewards, 2024. URL /ttp:h/gge//pppprreeeeerer/////a
[11] Nisan Stiennon, Long Ouyang. Jeff Wu, Daniel M. Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. Learning to summarize from human feedback, URL https::///axxii org/ /bss/2/0000032.
2022.
[12] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida. Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Gray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors. Advances Neural Information Processing Systems, 2022. URL httts:://ppenreeee TaoTm//I--GKKKEEO0
net/
[13] Andrew Y. Ng, Daishi Harada, and Stuart J. Russell. Policy invariance under reward transforma- tions:
Theory and application reward shaping. In Proceedings of the Sixteenth International Conference on Machine Learning, ICML '99, page 278-287, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. ISBN 1558606122.
[14] Vivek Veeriah, Matteo Hessel, Zhongwen Xu, Richard Lewis, Janarthanan Rajendran, Junhyuk Oh, Hado van Hasselt, David Silver, and Satinder Singh. Discovery of useful questions as auxiliary tasks, 2019, URL htthhttps:: //axiiv wwtrxxivvoggg//// 1909. 046007 04607
[15] Yang and Bowen Yu et Qwen2.5-1mm technical report, 2025. URL https : / //axxi/xvvvv//// org/ at//a/b////0111333 15383

---

[16] Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ah- mad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten. Alex Vaughan, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aurelien Rodriguez, Austen Gregerson, Ava Spataru, Baptiste Roziere, Bethany Biron, Binh Tang, Bobbie Chern, Charlotte Caucheteux, Chaya Nayak, Chloe Bi, Chris Marra, Chris McConnell, Christian Keller, Christophe Touret, Chunyang Wu, Corinne Wong, Cristian Canton Ferrer, Cyrus Nikolaidis, Damien Allonsius, Daniel Song. Danielle Pintz, Danny Livshits, Danny Wyatt, David Esiobu, Dhruv Choudhary, Dhruv Mahajan, Diego Garcia- Diego Perino, Dieuwke Hupkes, Egor Lakomkin, Ehab AlBadawy, Elina Lobanova, Emily Dinan, Eric Michael Smith, Filip Radenovic, Francisco Guzmán, Frank Zhang. Gabriel Synnaeve, Gabrielle Lec, Georgia Lewis Anderson, Govind Thattai, Graeme Nail, Gregoire Mialon, Guan Pang. Guillem Cucurell, Hailey Nguyen, Hannah Korevaar, Hu Xu, Hugo Touvron, Iliyan Zarov, Imanol Arrieta Ibarra, Isabel Kloumann, Ishan Misra, Ivan Evtimov, Jack Zhang, Jade Copet, Jaewon Lee, Jan Geffert, Jana Vranes, Jason Park, Jay Mahadeokar, Jeet Shah, Jelmer van der Linde, Jennifer Billock, Jenny Hong. Jenya Lee, Jeremy Fu, Jianfeng Chi, Jianyu Huang, Jiawen Liu, Jie Wang. Jiecao Yu, Joanna Bitton, Joe Spisak, Jongsoo Park, Joseph Rocca, Joshua Johnstun, Joshua Saxe, Junteng Jia, Kalyan Va- suden Alwala, Karthik Prasad, Kartikeya Upasani, Kate Plawiak. Ke Li, Kenneth Heafield, Kevin Stone, Khalid El-Arini, Krithika Iyer, Kshitiz Malik, Kuenley Chiu, Kumal Bhalla, Kushal Lakhotia, Lauren Rantala- Rantala-Yeary, Laurens van der Maaten, Lawrence Chen, Liang Tan, Liz Jenkins, Louis Martin, Lovish Madaan, Lubo Malo, Lukas Blecher, Lukas Landzaat, Luke de Oliveira, Madeline Muzzi, Mahesh Pasupuleti, Mannat Singh, Manohar Paluri, Marcin Kardas, Maria Tsimpoukelli, Mathew Oldham, Mathieu Rita, Maya Pavlova, Melanie Kam- badur, Mike Lewis, Min Si, Mitesh Kumar Singh, Mona Hassan, Naman Goyal, Narjes Torabi, Nikolay Bashlykov, Nikolay Bogoychev, Niladri Chatterji, Ning Zhang, Olivier Duchenne, Onur Çelebi. Patrick Alrassy, Pengchuan Zhang, Pengwei Li, Petar Vasic, Peter Weng. Prajiwal Bhargava, Pratik Dubal, Praveen Krishnan, Punit Singh Koura, Puxin Xu, Qing He, Qingxiao Dong, Ragavan Srinivasan, Raj Ganapathy, Ramon Calderer, Ricardo Silveira Cabral, Robert Stojnic, Roberta Raileanu, Rohan Maheswari, Rohit Girdhar, Rohit Patel, Romain Sauvestre, Ronnie Polidoro, Roshan Sumbaly, Ross Taylor, Ruan Silva, Rui Hou, Rui Wang. Saghar Hos- seini, Sahana Chennabasappa, Samjay Singh, Sean Bell, Seohyun Somia Kim, Sergey Edunov, Shaoliang Nie, Sharan Narang, Sharath Raparthy, Sheng Shen, Shengye Wan, Shruti Bhosale, Shun Zhang, Simon Vandenhende, Soumya Batra, Spencer Whitman, Sten Sootla, Stephane Collot, Suchin Gururangan, Sydney Borodinsky, Tamar Herman, Tara Fowler, Tarek Sheasha, Thomas Georgiou, Thomas Scialom, Tobias Speckbacher, Todor Mihaylov, Tong Xiao, Ujjwal Karn, Vedanuj Goswami, Vibhor Gupta, Vignesh Ramanathan, Viktor Kerkez, Vincent Gonguet, Virginie Do Vish Vogeti, Vítor Albiero, Vladan Petrovic, Weiwei Chu, Wenhan Xiong. Wenyin Fu, Whitney Meers, Xavier Martinet, Xiaodong Wang, Xiaofang Wang, Xiaoqing Ellen Tan, Xide Xia, Xinfeng Xie, Xuchao Jia. Xuewei Wang. Yaelle Goldschlag, Yashesh Gaur, Yasmine Babaci, Yi Wen, Yiwen Song. Yuchen Zhang, Yue Li, Yuning Mao, Zacharie Delpierre Coudert, Zheng Yan. Zhengxing Chen, Zoe Papakipos, Aaditya Singh. Aayushi Srivastava, Abha Jain, Adam Kelsey, Adam Shajnfeld, Adithya Gangidi, Adolfo Victoria, Ahuva Goldstand, Ajay Menon, Ajay Sharma, Alex Boesenberg, Alexei Baevski, Allie Feinstein, Amanda Kallet, Amit Sangani, Amos Teo, Anam Yunus, Andrei Lupu, Andres Alvarado, Andrew Caples, Andrew Gu, Andrew Ho, Andrew Poulton, Andrew Ryan, Ankit Ramchandani, Annie Dong, Annie Franco, Anuj Goyal, Aparajita Saraf, Arkabandhu Chowdhury, Ashley Gabriel, Ashwin Bharambe, Assaf Eisenman, Azadeh Yazdan, Beau James, Ben Maurer, Benjamin Leonhardi, Bernie Huang. Beth Loyd, Beto De Paola, Bhargavi Paranjape, Bing Liu, Bo Wu, Boyu Ni, Braden Hancock, Bram Wasti, Brandon Spence, Brani Stojkovic, Brian Gamido, Britt Montalvo, Carl Parker, Carly Burton, Catalina Mejia, Ce Liu, Changhan Wang, Changkyu Kim, Chao Zhou, Chester Hu, Ching-Hsiang Chu, Chris Cai, Chris Tindal, Christoph Feichtenhofer, Cynthia Gao. Damon Civin, Dana Beaty, Daniel Kreymer, Daniel Li, David Adkins, David Xu, Davide Testuggine, Delia David, Devi Parikh, Diana Liskovich, Didem Foss, Dingkang Wang, Duc Le, Dustin Holland, Edward Dowling, Eissa Jamil, Elaine Montgomery, Eleonora Presani, Emily Hahn, Emily Wood, Eric-Tuan Le, Erik Brinkman, Esteban Arcaute, Evan Dunbar, Evan Smothers, Fei Sun, Felix Kreuk, Feng Tian, Filippos Kokkinos, Firat Ozgenel. Francesco Caggioni, Frank Kanayet, Frank Seide, Gabriela Medina Florez, Gabriella Schwarz, Gada Badeer, Georgia Swee, Gil Halpern, Grant Herman, Grigory Sizov, Guangyi, Zhang, Guna Lakshminarayanan, Hakan Inan, Hamid Shojanazeri, Han Zou, Hannah Wang, Hanwen Zha, Haroun Habeeb, Harrison
12

---

Rudolph. Helen Suk, Henry Aspegren, Hunter Goldman, Hongyuan Zhan, Ibrahim Damlaj, Igor Molybog, Igor Tufanov, Ilias Leontiadis, Irina-Elena Veliche, Itai Gat, Jake Weissman, James Geboski, James Kohli, Janice Lam, Japhet Asher, Jean-Baptiste Gaya, Jeff Marcus, Jeff Tang, Jennifer Chan, Jenny Zhen, Jeremy Reizenstein, Jeremy Teboul, Jessica Zhong, Jian Jin, Jingyi Yang, Joe Cummings, Jon Carvill, Jon Shepard, Jonathan McPhie, Jonathan Torres, Josh Ginsburg. Junjie Wang, Kai Wu, Kam Hou U, Karan Saxena, Kartikay Khandelwal, Katayoun Zand, Kathy Matosich, Kaushik Veeraraghavan, Kelly Michelena, Keqian Li, Kiran Jagadeesh, Kun Huang. Kunal Chawla, Kyle Huang, Lailin Chen, Lakshya Garg, Lavender A, Leandro Silva, Lee Bell, Lei Zhang. Liangpeng Guo, Licheng Yu, Liron Moshkovich, Luca Wehrstedt, Madian Khabsa, Manav Avalani, Manish Bhatt, Martynas Mankus, Matan Hasson, Matthew Lennie, Matthias Reso, Maxim Groshev, Maxim Naumov, Maya Lathi, Meghan Keneally, Miao Liu, Michael I.. Seltzer, Michal Valko, Michelle Restrepo, Mihir Patel, Mik Vyatskov, Mikayel Samvelyan, Mike Clark, Mike Macey, Mike Wang. Miquel Jubert Hermoso, Mo Metanat, Mohammad Rastegari, Munish Bansal, Nandhini Santhanam, Natascha Parks, Natasha White, Navyata Bawa, Nayan Singhal, Nick Egebo, Nicolas Usunier, Nikhil Mehta, Nikolay Pavlovich Laptev, Ning Dong, Norman Cheng, Oleg Chernoguz, Olivia Hart, Omkar Salpekar, Ozlem Kalinli, Parkin Kent, Parth Parekh, Paul Saab, Pavan Balaji, Pedro Rittner, Philip Bontrager, Pierre Roux, Piotr Dollar, Polina Zvyagina, Prashant Ratanchandani, Pritish Yuvraj, Qian Liang, Rachad Alao, Rachel Rodriguez, Rafi Ayub. Raghotham Murthy, Raghu Nayani, Rahul Mitra, Rangaprabhu Parthasarathy, Raymond Li. Rebekkah Hogan, Robin Battey, Rocky Wang. Russ Howes, Ruty Rinott, Sachin Mehta, Sachin Siby, Sai Jayesh Bondu, Samyak Datta, Sara Chugh, Sara Hunt, Sargun Dhillon, Sasha Sidorov, Satadru Pan, Saurabh Mahajan, Saurabh Verma, Seiji Yamamoto, Sharadh Ramaswamy, Shaun Lindsay, Shaun Lindsay, Sheng Feng. Shenghao Lin, Shengxin Cindy Zha, Shishir Patil, Shiva Shankar, Shugiang Zhang, Shuqiang Zhang, Sinong Wang. Sneha Agarwal, Soji Sajuyigbe, Soumith Chintala, Stephanie Max, Stephen Chen, Steve Kehoe, Steve Satterfield. Sudarshan Govindaprasad. Sumit Gupta, Summer Deng, Sungmin Cho, Sunny Virk, Suraj Subramanian, Sy Choudhury, Sydney Goldman, Tal Remez, Tamar Glaser, Tamara Best, Thilo Koehler, Thomas Robinson, Tianhe Li, Tianjun Zhang, Tim Matthews, Timothy Chou, Tzook Shaked, Varun Vontimitta, Victoria Ajayi, Victoria Montanez, Vijai Mohan, Vinay Satish Kumar, Vishal Mangla, Vlad Ioneseu, Vlad Poenaru, Vlad Tiberiu Mihailescu, Vladimir Ivanov, Wei Li, Wenehen Wang, Wenwen Jiang, Wes Bouaziz, Will Con- stable, Xiaocheng Tang, Xiaojian Wu, Xiaolan Wang, Xilun Wu, Xinbo Gao, Yaniv Kleinman, Yanjun Chen, Ye Hu, Ye Jia, Ye Qi, Yenda Li, Yilin Zhang, Ying Zhang, Yossi Adi, Youngjin Nam, Yu, Wang, Yu Zhao, Yuchen Hao, Yundi Qian, Yunlu Li, Yuzi He, Zach Rait, Zachary Vito, Zef Rosnbrick, Zhaoduo Wen, Zhenyu Yang, Zhiwei Zhao, and Zhiyu Ma. The llama herd of models, 2024. URL pictts://arxivee org/ wtwg//bs/// /407 21783
[17] Paul Christiano. Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences, 2023. WtRLhhtps://aare org/ /bs/ 1706. 00741
[18) Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. 2024. WtRpshtts:///rxxt.
org/ 2305/
[19] Sherry Yang, Ofir Nachum, Yilun Du Jason Wei, Pieter Abbeel, and Dale Schuurmans. Foundation models for decision making: Problems, methods, and opportunities, 2023. URL
https://arxiv. http//aaxvvvv....a//// /bbb//300 04129
[20] Yongxian Wei, Anke Tang. Li Shen, Zixuan Hu, Chun Yuan, and Xiaochun Cao. Modeling multi-task model merging as adaptive projective gradient descent. In secood International Conference on Machine Learning, 2025.
[21] Yongxian Wei, Zixuan Hu, Li Shen, Zhenyi Wang, Chun Yuan, and Dacheng Tao. Open- vocabulary customization from clip via data-free knowledge distillation. In The Thirteenth International Conference on Learning Representations, 2025.
[22] Yongxian Wei, Runxi Cheng, Weike Jin, Enneng Yang. Li Shen, Lu Hou, Sinan Du, Chun Yuan, Xiaochun Cao, and Dacheng Tao. Unifying multimodal large language model capabilities and modalities via model merging, arXiv preprint a50iv:2505. 19892, 2025.
13

---

[23] Qiyuan Zhang, Fuyuan Lyu. Zexu Sun, Lei Wang, Weixu Zhang, Wenyue Hua, Haolun Wu, Zhihan Guo, Yufei Wang, Niklas Muennighoff, Irwin King, Xue Liu, and Chen Ma. A survey on test-time scaling in large language models: What, how, where, and how well?, 2025. URL httpp://arxiiv. org/ abs/ 24235
[24] Charlie Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters, 2024. URL https://arxiv org/abs/2408. 03314
[25] Xiaosong Ma, Jie ZHANG, Song Guo, and Wenchao Xu. Swapprompt: Test-time prompt adaptation for vision-language models. In Thirly-seventh Conference Neural Information Processing Systems, 2023.
[26] DeepSeek-AI. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning, 2025. URL wttp://axxxvvxv/aaaaa/
[27] OpenAl. Gpt-4o system card, 2024. URL Utt/tttp::/arriivoorr///aa
21276
[28] Keld Helsgaun. An extension of the lin- kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems, 12 2017.
[29] Florian Arnold and Kenneth Sörensen. Knowledge-guider local search for the vehicle routing problem. Computers Operations Research, 105:32-46, 2019. ISSN 0305-0548. doi: https: (dtoi..rg/00.10161.co..000199999 002. URL httph:tttswat sciencedirectt. com/science.
arricle/pp11/0000564441900000
[30] Marco Dorigo and Luca M. Gambardella. Ant colony system: A cooperative learning approach the traveling salesman problem. In IEEE Transactions on Evolutionary Computation. IEEE, 1996.
[31] Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution heuristics: Towards efficient automatic algorithm design using large language model, 2024. URL https://::///t
org/ abs /2002241.00 02051
[32] Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. Reevo: Large language models as hyper-heuristics with reflective evolution, 2024.
bttttpp://axxiv.orr/bbb..s
01145
[33] Michael Han Daniel Han and Unsloth team. Unsloth, 2023. URL http://github. unslothai/umsloth
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction accurately state the paper's main contributions, including the proposed NaDRO framework with its dual-reward (POR and CPR) strategy for robust L.LM training on noisy data, and its demonstrated empirical superiority on complex TSP and CVRP tasks. These claims are substantiated by the methodology detailed in Section 4 and the comprehensive experimental results, including ablations, presented in Section 5 (e.g., Tables and 3).
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper discusses limitations of the current work within the Limitation and Broader Impact part, refer Section 7 These include the primary focus on MCTS- generated noise characteristics and the manual definition of qualitative features for the Context Perception Reward (CPR) mechanism, suggesting areas for future refinement.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
15

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The paper provides theoretical justification for the Preference-basee Outcome Reward (POR) mechanism. Section 4.1 introduces the concept of maximizing a "Value Separability" objective function J(k) (Equation to determine the optimal cutoff based on a principled bias-variance tradeoff. Section 5.3 and Table 2 further develop this by modeling the relative action value distribution (Equation 4), theoretically deriving an optimal k-value that aligns with empirical results. All assumptions (e.g., MCTS value modeling) and derivations are presented within the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The paper provides extensive details to support reproducibility. This includes: (I) A full description of the NaDRO methodology (Section 4, Algorithm in Appendix
Justification:
C). (2) The MCTS-based data generation process (Section 3, Section 5.1.3). (3) Sources for all public datasets (TSPLIB, Golden in Section 5.1.1). (4) Comprehensive details on state/action spaces (Appendix E, F), CPR annotation rules (Appendix B), and all training hyperparameters (Appendix D). (5) The release of the code, as stated in the abstract.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
16

---

While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The paper provides a GitHub link to the code in the abstract. The repository includes scripts to implement the NaDRO framework and reproduce the main experiments (as shown in Tables 1, 3, and 4). The datasets used are from public benchmarks (TSPLIB, Golden), and instructions for generating the training data are provided in the paper (Section 5.1.3) and the code repository.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
Sublic/guides httpg//e///ooeeeuiiieeeeeeeeeeee
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips.cc/publl httpsssccpbbllccuuiiiiiie wttpi///guuieee//Coooeee
ssi ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper provides comprehensive details on the experimental setup. Section 5.1 describes the tasks (TSP, CVRP), datasets (TSPLIB, Golden), and base models (Qwen, Llama). Section 1.3 and 5.1.4 detail the MCTS-based data generation and fine-tuning
17

---

process. Crucially, Appendix D (Table 5) specifies all necessary hyperparameters (e.g.. learning rate, optimizer, LORA rank, sequence length), while Appendices and define the exact state and action spaces. Appendix B details the rules for CPR annotation, ensuring all components are specified for reproducibility. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The paper reports statistical variance (standard deviation) across multiple experimental runs for all main results, as presented in Table 1, Table 3, and Table 4. This findings.
information allows for the assessment of statistical significance and robustness of the
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The paper provides sufficient information on compute resources. Section 5.1.4 specifies the hardware used (a cluster with NVIDIA A100 and NVIDIA A6000 GPUs) and the typical execution time (approximately 32 hours for fine-tuning run). Further details on the training procedure and hyperparameters are available in Appendix (Training Pipeline) and Appendix D (Parameter Setting).
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
18

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics atttps:/nneurppn
Answer: [Yes]
Justification: The research presented in this paper has been conducted in full conformity with the NeurIPS Code of Ethics. We have prioritized transparency in methods and findings, and aimed to ensure the reproducibility of our work through detailed documentation, clear experimental procedures, and the provision of code.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In Section 7, we discuss the broader impacts of NaDRO. We highlight positive contributions, such as enhancing efficiency and resource saving in logistics and operations re- search. We also acknowledge potential negative impacts, including the risks associated with over-reliance on automated decision-making critical infrastructure and the environmental considerations (e.g., energy consumption) inherent in training large-scale models.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
19

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This work introduces NaDRO, training methodology. and applies it to fine- tune existing pre-trained language models (Qwen2.5-7B-Instteeee
1--aa--.1--B-Instmuue for the specific task of heuristic selection combinatorial optimization. The code and any derived models are specialized for this narrow, non-generative application and do not inherently possess a high risk for misuse in the sense of generating harmful content or disinformation, unlike general-purpee purpose language image generators. The base pre-trained models are governed by the release policies and safeguards of their original creators. Our released artifacts (code and MCTS -ennerreed training data for CO) do not include scraped PII or sensitive user data.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All existing assets utilized in this paper, including base large language models (e.g., Qwen2255-7B-Instruuc Llama-3. 1-8-- Instuunst benchmark datasets (TSPLIB, Golden dataset), and baseline algorithms or software (e.g., LKH, OR-Tools, specific metaheuristic implementations like ReEvo, EoH), properly credited via citations throughout the manuscript, particularly in Section 5.1 and the captions of experimental tables. We have endeavored respect all applicable licenses and terms of use, and further details regarding significant third-party assets are provided in our supplementary material and code repository documentation.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, papppsaipttteeeecc twwose..tehcce...m. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
20

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
The primary new assets introduced are the code implementation the NaDRO framework and the released via a Github repository. This repository includes scripts for data generation and experiment reproduction. The paper itself provides extensive documentation for these assets, including the training algorithm (Appendix C), detailed hyperparameters (Appendix D), the state/action space definitions (Appendix E, F), and data annotation rules (Appendix B). This documentation is provided alongside the assets to ensure reproducibility.
Justification:
training data. As stated in the abstract, the code is
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details the dataset/code/mmodl as part their submissions via structured templates, This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The research presented in this paper does not involve crowdsourcing or any direct research with human subjects. All training data is generated through Monte Carlo Tree Search (MCTS) simulations on established benchmarks, and evaluations are based on automated performance metrics.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information tion of the paper involves human subjects, then much detail as possible should be included the main paper.
supplemental material is fine, but if the main contribu-
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This research does not involve human subjects or crowdsourcing. The training data is generated via Monte Carlo Tree Search (MCTS) simulations established com- binatorial optimization benchmarks (TSPLIB and Golden datasets), and the experimental evaluation relies automated performance metrics on these problem instances.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
21

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [Yes]
The use of Large Language Models (LLMs) is fundamental and core com- ponent of this research, the paper introduces NaDRO, novel framework specifically designed for training L..Ms. The paper extensively describes which LLMs are used (e.g.. Owen2.55-7BIIntruuct, -lamma-3.---B--nsnnnee
Justification:
how they are fine-tuned with the NaDRO methodology to act as heuristic selectors, and how their performance is evaluated. This is detailed throughout the manuscript, particularly in the Methodology (Section 4), Experi- ments (Section 5), and various appendices covering model parameters, state/action spaces, and the training pipeline.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
22

---

A Generalization Results on CVRP
To further assess the generalizability and robustness our NaDRO framework, we extended our evaluation to the Capacitated Vehicle Routing Problem (CVRP). We utilized instances 1 through 10 from the challenging Golden dataset, which are characterized by large numbers of customers (200 to 480) and varying fleet sizes. These instances are particularly suitable for testing performance in large-scale, intricate decision makinn scenarios. Performance is evaluated based on the optimality gap, where lower values indicate better results.
Table Comparative Optimality Gap %) on Capacitated Vehicle Routing Problem instances from the Golden dataset. Results for NaDRO-Qwen 7B are generated using NaDRO. Methodologies for baseline models are analogous to those the TSP evaluation.
Method
Golden_1
2
3
4
6
7
8
10
Truditional Solvers
OR-Tools
2.94
1.77
8.73
12.17
3.0
10.56
7.19
7.99
2.47
0.49
Metaheuristics
ACO
14.19
27.23
22.68
28.96
21.0
15,99
28.96
22.38
87.04
98.05
ReEvo ACO
7.57
15.45
19.68
23.09
13.84
17.24
17.46
16.71
N/A*
N/A*
LLM-based Approaches
GPT-4o
19.53
12.65
23.29
31.46
28.89
19.3
30.88
34,42
28.50
29.31
GPT-o3
20.49
15.17
18.19
22.67
25.42
16.67
29.62
27.82
22.11
33.39
Deepseek-R1
20.44
21.33
18.4
25.16
25.55
18.2
32.32
30.36
23.31
31.25
Qwen 7B
33.31
30.66
42.12
46.65
26.29
49.6
53.66
51.65
36.79
GRPO on Qwen 7B
27.18
27.08
33.35
43.77
23.29
42.51
48.94
30.64
29.83
36.20
NaDRO-Qwen 7B(Ours)
7.49
9.71
16.61
23.00
18.36
18.21
20.64
16.13
18.85
24.82
For simplicity, the prefix "Golden_"" " is omiiteed from task names, all tasks are from the Golden dataset. *N/A indicates that the method was unable to complete the run within the limited resources.
In the more complex CVRP domain (results in Table 4. NaDRO- -wen 7B demonstrated strong performance and excellent adaptability, further validating the generalizability and effectiveness of the NaDRO framework. Compared to other large language models, NaDRO- NaDRO-Qwen 7B held a significant advantage. Its dual-reward mechanism proved particularly effective within CVRP's intricate decision spaces, leading to performance gains over its own baselines (Qwen 7B and GRPO-tuned Qwen 7B) that even surpassed those observed in TSP. Furthermore, when facing traditional metaheuristics, NaDRO-Qwen 7B not only exhibited competitive or even superior performance but, particularly noteworthy, it successfully obtained high-quality solutions on some very large-scale instances where certain specialized meta-heuristics failed due to resource limitations, highlighting the practical value of NaDRO-enhanced LLMs in tackling such challenging problems.
B
CPR Annotation
The Context Perception Reward (CPR) mechanism, introduced in Section 4.2
incentivizes the LLM
to accurately assess key qualitative features of the current problem state before making decision. Ground-truth labels (yt,,) )) for these features are generally straightforward annotate using rule-based methods. In our work, the annotated qualitative features include: problem type, state type, algorithm type, and cost type.
This appendix details the rule-based annotation scheme for one specific feature: the assessment the current solution's 's cost situation. This label helps the LLM understand if the current partial solution's cost is relatively low, high, or normal compared to a baseline. The process is as follows:
1. Calculate Reference Cost (Cost.reedy)) For each problem instance, we first compute reference cost by constructing full solution using a simple greedy heuristic, The total cost of this greedy solution serves as baseline.
2. Calculate Current State Cost (Coslcarrent): At each decision step I, we calculate the average path cost of the partial solution constructed so far in state 8t.
3. Assign Label based on Thresholds: We compare Costourrent to Coslgreedy to assign one of three labels:
23

---

(1) "High Cost": if Costcurrent 2 1.15 x Costgreedy-
(2) "Low Cost": Costcurrent Σ 0.80 x Costgreedy-
"Normal Cost": otherwise (0.80 Costgreedy Costcurrent 1.15 Costgreedy).
4. Apply Conditional Activation: This cost assessment is only performed after the solution construction has progressed beyond an initial phase (specifically, when more than 10% of the path is constructed in implementation). Evaluating costs early be misleading. Before this threshold, the label might be considered "not applicable."
This rule-based method provides an objective and easily computable signal for the CPR. Similar transparent methodologies are used for annotating the other qualitative dimensions, ensuring the practical applicability of the CPR mechanism.
C Training Pipeline
This section details the offline training pipeline used to fine-tune the Large Language Model (LLM) with our proposed Noise-Award Aware Deal-Reward Optimization (NaDRO) framework, leveraging Group Relative Policy Optimization (GRPO). The core training loop, shown in Algorithm | fine-tunes the initial LLM parameters 8g over Mepochs.
Algorithm 1 NaDRO Offline Training Algorithm
Require: Offline dataset flife = {(kk Q(sk,)) vr.) )) Initial LLM parameters 0o: GRPO hyperparameters( NNG, Mepochs: Bsize); Reward coefficients (WPOR, WCPR; W Auz).
Ensure: Optimized LLM parameters 0.
1: Initialize LLM policy network my with parameters 0g-
2: for epoch e = 1, 1..... Mepochs do
3: Sample a batch of indices Kbatch corresponding to data points in Dof fline-
4: Initialize preference data set for this batch Pbatch + 0.
5: for each index it E Kbatch do
6: Retrieve state .CTS evaluations QACCTS(SK, :), and CPR labels yi. from Dof fline-
7:
Initialize response group Groups +- 0. for response index j 1,.... NG do (o6") a (-(s
8:
9:
10:
RPOR= - CalculatePOR(a QMCTs(Sk:)) RCP CalculateCPR vk.)
11:
Auz CalculateAuxRewardds ((()) a0
(1)
12:
R(1)
total.k + WronRRoO + WCrn CPR + w Ann R()
R()
13:
Aux
Add ((i)) ax ), Rlddar.) to Groups.
(5)
14:
15:
Pk FormGGROOPrefeencces (rrooef
Poatch +- Phatch U Pt-
+- PpplatePolicyyitGGRPP@... Poatch)
18:
return B.
D Detailed Parameter Setting
This section outlines the key hyperparameters and configuration settings employed during the fine- tuning of the Dwen2.5-7B-Insttren model using NaDRO framework with the Group Relative Policy Optimization (GRPO) method. These settings were largely managed via the 'GRPOConfig' class from the TRL (Transformer Reinforcement Learning) library, leveraging Unsloth for efficient training.
The primary parameters are detailed in Table

---

Table 5: Key Hyperparameters and Configuration Settings for NaDRO Training.
Category
Parameter
Value
Model Config.
Max. Sequence Length
3584
LoRA Rank (a)
32
Optimization
Optimizer
Paged AdamW (8-bit)
Learning Rate
10-6
Adam 81
0.9
Adam 82
0.99
Weight Decay
0.1
LR Scheduler
Cosine
Warmup Ratio
0.1
Max. Gradient Norm
0.1
Training Setup
Mixed Precision
BF16/ FP16
Epochs
Max. Steps
Disabled
GRPO Config.
Inference Backend Generations (NG)
vLLM
12
Max. Prompt Length
2048 tokens
Logging & Saving
Checkpoint Save Steps
250
Logging Steps
5
E
State Space
E.1
State Space for TSP
Task Definition, Operational Guidelines, and Output Format
Problem Description: A clear definition the primary task and its core objectives.
General Interaction Rules: Instructions on LLM interaction, such as the naming convention for invoking heuristic algorithms.
Termination Strategy: An outline the general conditions for concluding the solution process.
Decision Output Format: Precise structured format for the LLM's s responses, detailing how to present its reasoning (<reasoning>... //sisminn...<//rrsoonnnn>>>) and chosen action (<answe>...<answwer> including differentiation between selecting a heuristic and signaling termination.
2. Global Problem Instance Characteristics (Static Data)
Node Count:
Total number of cities/nodes the problem.
Average Distance: Average distance between all pairs of cities.
Minimum Distance: The shortest distance between any pair of cities.
Maximum Distance: The longest distance between any pair of cities.
Distance Standard Deviation: Standard deviation of all pairwise distances.
Node Density: measure related to the spatial distribution of nodes.
Centroid: Identifier coordinates of central node or point.
2. Dynamic Solution State (Current Progress Metrics)
Visited Nodes: Number of nodes currently included in the tour.
25

---

Unvisited Nodes: Number of nodes not yet included in the tour.
Current Total Cost: The total length of the current partial or complete tour.
Last Edge Cost: The cost of the most recently added edge or incurred by the last operation.
Current Path Length: Number of edges or segments the current tour.
Remaining Nodes: Equivalent to "Unvisited Nodes," indicating nodes yet to incorporated.
Average Edge Cost: Average cost of edges in the eurrent partial tour.
Edge Cost Standard Deviation: Standard deviation of edge costs in the current partial tour.
Solution Validity: A flag indicating whether the current partial solution adheres to problem constraints (e.g., for valid).
Minimum Remaining Edge Cost: An estimated minimum cost related connecting remaining nodes.
Maximum Remaining Edge Cost: An estimated maximum cost related to connecting remaining nodes.
Historical Context (Recent Decision Trajectory)
To provide the LLM with a short-term memory of its recent actions and their consequences, the prompt includes summary of the immediately preceding decision rounds. For each round in this history, the following information is typically provided:
Heuristic: The name of the heuristic algorithm selected in that round.
Parameters: Any hyperparameters used for the selected heuristic.
Delta of Visited Node: The change in the number of visited nodes resulting from that round's
action.
Delta of Current Cost: The change in the total solution cost due that round's action.
E.2
State Space for CVRP
Task Definition, Operational Guidelines, and Output Format
Problem Description: Defines the task and its objective.
Decision Output Format: Specifies the precise structured format for the LLM's response, includ- ing the qualitative cards, the reasoning section <rrasoning>..<<rrasoniig
and the answer block (<answer>..<<asswerr> The answer block can contain up to three ranked heuristic choices or ***Stop*** command if no further improvement is deemed possible under specific conditions.
Global Problem Instance Characteristics (Static Data)
node_mee __mm Total number of nodes.
vehicle_num: Number of available vehicles in the fleet.
capacity: Capacity of each vehicle.
depot: Identifier of the depot node.
average_dentn Average demand across all eustomer nodes.
demand_varte variance Variance of customer demands.
average distance; Average travel distance between nodes.
26

---

max mxx_distance: Maximum distance between any two nodes.
ain_distance Minimum distance between any two nodes.
distance_ Variance of inter-node distances.
cahiicle_caacciityutiiiia. An aggregate measure of how vehicle capacities are typically utilized.
node to_ toeeetttt_eiieeeeaeeeeee Ratio of customer nodes to vehicles.
3. Dynamic Solution State (Current Progress Metrics)
visited_muu Total number of unique customer nodes visited/serviced.
unvisited Number of customer nodes not yet serviced.
total_current_cost:: Sum of costs of all current vehicle routes.
average_.ruute_lengthh Average number of customers per active route.
nax_routte_eentth Maximum number of customers any single route.
min_routt_leentth:: Minimum number of customers in any single route.
std_dev__route_lennthh Standard deviation of route lengths.
average_routte_cost: Average per route.
total_demand_servedd Sum of demands of all visited customers.
average.vehicle_lood.. Average load carried by active vehicles.
Aveagg_.eeaaniiigg..eehhllle.eee Average unused capacity across active vehicles.
avarage.urriiiited_nddddddddd Average demand of nodes not yet serviced.
Lotal_remaining__emandd Total demand of all unvisited nodes.
solution_validia Boolean flag indicating if the current solution adheres to all constraints.
4. Historical Context (Recent Decision Trajectory)
Heuristic:
The name of the heuristic algorithm selected.
Delta of Visited Node Num: Change in the number of newly serviced customer nodes.
Delta of Current Cost: Change in the total routing cost.
Delta of Fulfilled Demands: Change in the total demand satisfied.
Action Space
The action space available the LLM for the TSP and CVRP.
F.1 Action Space for TSP
2opt() ()
Description: Swaps two non-adjacent edges to untangle the tour.
Advantages: Simple; effectively reduces cost.
Disad Prone to local optima; slower for large-scale problems.
27

---

Parameters: N/A
random( ()
Description: Randomly appends unvisited node the current solution.
Advantages: Fast and straightforward for constructing an initial solution.
Disadvantages: Unpredictable; often produces suboptimal results.
Parameters: N/A
greedy_algorithm((
Description: Extends the tour by always choosing the shortest available edge.
Advantages: Quickly generates a low-cost initial solution.
Disadvantages: Greedy choices may lead to local minima.
Parameters: N/A
nearest.neighborr ()
Description: Selects the nearest unvisited node from the current node.
Advantages: Low computational cost and simplicity.
Disadvantages: Sensitive to the starting point; may yield inconsistent global results.
Parameters: N/A
3opt ()
Description: Reconnects three segments for deeper local optimization.
Advantages: More powerful than 2-opt for further improvements.
Disadvantages: Higher computational cost; diminishing returns if overused.
Parameters: N/A
farthest_inseerionll
Description: Inserts the farthest unvisited node with minimal cost increase.
Advantages: Helps construct balanced initial tour.
Disadvantages: May result in suboptimal local insertions; sensitive to node distribution.
Parameters: N/A
nearest_insertion/
Description: Inserts the closest unvisited node the optimal position.
Advantages: Controls cost during expansion.
28

---

Disadvantages: Local decisions might limit global optimality.
Parameters: N/A
s ammllatedaannealll
Description: Randomly swaps nodes and accepts changes based on a temperature criterion.
Advantages: Escapes local optima; ideal for fine-tuning.
Disadvantages: Requires careful parameter tuning; can slow and computationally heavy,
Parameters: N/A
Description: Inserts two randomly selected unvisited nodes with minimal cost increase.
Advantages: Increases solution diversity and helps overcome local optima.
Disadvantages: Inconsistent performance; optimality guaranteed.
Parameters: N/A
Description: Chooses the best among the k nearest unvisited nodes for insertion. int (default: 1) Number of nearest neighbors to consider.
Parameter: k:
Advantages: Balances exploration and exploitation.
Disadvantages: The choice of is critical; poor selection can lead to suboptimal results.
Description: Randomly inserts an unvisited node the position with minimal cost increase.
Advantages: Merges randomness with cost efficiency; versatile for multiple stages.
Disadvantages: Results can vary significantly between runs.
Parameters: N/A
irrapest_insertion/
Description: Inserts the unvisited node that causes the smallest cost increase at its best position.
Advantages: Minimizes incremental cost; ideal for cost-sensitive scenarios.
Disadvantages: Greedy approach may get trapped in local minima; computationally intensive for large instances.
Parameters: N/A
29

---

inpertioonheeristicss (insertion_strategy
str = 'cheapest')
Description: A flexible insertion heuristic that supports 'cheapest', 'farthest', and "nearest" inser- tion strategies.
Parameter: insertion_stxategy" str (default: "cheapest") Defines the insertion logic.
Advantages: Flexible and adaptable different phases of the solution process.
Effectiveness depends heavily on the chosen strategy; poor selection can hurt overall solution quality.
Disadvantages:
(alpha: float 0.3)
Description:
Combines greedy randomized construction with local search. A restricted candidate list (RCL) is formed based on parameter alpha, from which an element is randomly selected.
Parameter: alpha: float (default: 0.3) Controls the greediness/randonnes of the construc- tion phase.
Advantages: Enhances solution diversity and can lead to better global optimality, especially in large-scale problems.
Disadvantages: Sensitive to the alpha parameter; can be computationally intensive.
colony ()
Description: Uses pheromone levels and heuristic desirability to probabilistically select the next node, updating pheromones via evaporation and deposit.
Advantages: Dynamically balances exploration and exploitation.
Disadvantages: Requires complex parameter tuning; risk of premature convergence and high computational cost.
Parameters: N/A
F.2
Action Space for CVRP
sade_shift__bee wtw.sshftt.beteeerrttteeeee
Description:
Attempts to move a node from its current position in one route to a different position another route the move reduces the total distance and respects capacity constraints.
Advantages: Can improve existing solutions by exploring inter-route moves; helps escape some local optima.
Higher computational cost due to checking many potential moves; it's a local search operator and may not find the global optimum.
Disadvantages:
Parameters: N/A
three_opt()
Operates within single route removing three edges and reconnecting the resulting six endpoints in one of several possible ways to decrease the route's 's length.
Description:
Advantages: More powerful than 2-opt, capable of untangling more complex route crossings.
Disadvantages: Significantly higher computational complexity than 2-opt; operates only intra- route, cannot exchange nodes between routes.
30

---

Parameters: N/A
two_opt()
Operates within a single route by selecting two non-adjacent edges, removing them, and reconnecting the endpoints to reverse the segment between them, if this reduces the route length.
Description:
Advantages:
Simple and effective local search for improving individual quality; reduces tour length by eliminating edge crossings.
Disadvantages: Prone to local optima; only performs intra-route improvements.
Parameters: N/A
Parthest_inseetionn]
Description:
Starts with the unvisited node farthest from the depot and inserts it into the position an existing route that causes minimum cost increase, respecting capacity constraints.
Advantages: Often produces better initial solutions than nearest neighbor or random insertion; considers global positioning some extent.
Slightly higher computational cost than simpler insertions; the farthest node isn't tt always the best starting point.
Disadvantages:
Parameters: N/A
greedy
Description: Iteratively adds the closest unvisited node to the end the current vehicle's 's route.
Advantages: Simple to implement; fast for generating an initial solution.
Disadvantages: Prone to local optima due to myopic choices; often results in poor solution quality.
Parameters: N/A
min www.oooosiiniiionnncc
Iteratively selects an unvisited node and inserts it into the position that minimizes the increase in total route cost, respecting capacity.
Description:
Advantages: Balances construction speed and solution quality; generally better than simple greedy or random methods.
Disadvantages: Computationally more intensive as it evaluates many insertion points per node.
Parameters: N/A
nearest_neighhet
For each vehicle, starting from the depot the last visited node, adds the nearest unvisited node that satisfies capacity constraints, until no more nodes can be added or all nodes are visited.
Description:
Advantages:
Simple, intuitive, and fast.
31

---

Disadvantages: Very susceptible to local optima; solution quality highly dependent on the starting point and node distribution.
Parameters: N/A
petal_ a
Deseription:
Sorts nodes based on their polar angle relative to the depot, attempts to form feasible single-node "petal" routes, and assigns these petals to vehicles if capacity allows.
Advantages: Considers geographic clustering; sometimes produce intuitive route structures. Relatively complex; angle-based sorting isn't always optimal; effectiveness depends on node distribution.
Disadvantages:
Parameters: N/A
random(
Randomly selects an unvisited node and appends to the end of a randomly chosen vehicle's 's route, provided capacity constraints are met.
Description:
Advantages: Extremely simple and fast; useful for generating diverse starting points for other algorithms.
Disadvantages: Solution quality is highly variable and generally poor; doesn't 't perform any cost optimization.
Parameters: N/A
saving_algorithm()
Calculates the cost savings achieved by merging pairs of routes. It iteratively merges the pair with the highest savings, subject to capacity constraints.
Description:
Advantages: Classic and often effective construction hcuristic; usually fast and provides good quality initial solutions.
Disadvantages: Greedy nature can lead to suboptimal final solutions; sensitive to distance matrix accuracy.
Parameters: N/A
variable_nette hewgoie_niggtboroo__seeeeee
Description: Intended as a Variable Neighborhood Search (VNS) metaheuristic, which systemati- cally explores different neighborhood structures escape local optima. However, the provided code implements a simple best-insertion heuristic: finds the best position to insert any unvisited node into any existing route based minimizing insertion cost.
Advantages: Identifies the single most cost-effective node insertion available.
Disadvantages:
Very limited scope, essentially single step of Min-Cost Insertion heuristie; does not implement the broader VNS strategy of changing neighborhoods.
Parameters: N/A
32


Reviews:
[{"review_id": "HWWXmIAWzR", "reviewer": "Reviewer_5e7B", "summary": "The paper proposes NaDRO, a framework for fine-tuning LLMs to perform well on long-horizon decision-making tasks using noisy, imperfect supervision—particularly from sources like MCTS (Monte Carlo Tree Search). This is fundamentally a challenge, since it is hard to estimate the long-term value of actions: scores are inherently noisy, being estimated from a tiny fraction of the action space. The commonly used methods (e.g., GRPO) require high-quality labeled data. NaDRO addresses this by introducing a dual-reward formulation: it constructs more robust training signals by splitting rewards into a Preference-based Outcome Reward (POR) and a Context Perception Reward (CPR). Rather than relying on absolute action scores, NaDRO leverages pairwise preference rankings to construct POR and combines it with CPR in an alternating optimization scheme, enabling the model to generalize better in the face of sparse, noisy, or inconsistent reward signals.", "questions": "# Questions\n\n1. How does CPR contribute specifically to solving long-horizon credit assignment, beyond acting as an auxiliary classification loss?\n    While CPR improves performance, it’s unclear whether its benefits stem from better credit assignment over multi-step trajectories, or simply from regularizing the model with intermediate supervision. Could one isolate its impact by measuring reward variance or learning dynamics with/without CPR over varying trajectory lengths?\n2. How sensitive is POR to the rank cutoff parameters and MCTS quality?\n    Since POR transforms noisy Q-values into ordinal rankings and selects top-k actions for positive supervision, could a poorly chosen cutoff degrade performance by discarding near-optimal actions that fall just below the threshold?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "# Strengths\n\n* Reward Decomposition Strategy: The paper proposes a technically sound reward decomposition—splitting noisy feedback into a Preference-based Outcome Reward (POR) and a Context Perception Reward (CPR)—which improves gradient stability and enables more robust training from noisy, partial supervision.\n* Rank-Based POR Mechanism: Instead of relying on unstable top-1 MCTS scores, POR converts noisy Q-values into ordinal rankings and applies position-sensitive scaling, preserving learning signal while mitigating variance—this feels like a principled alternative to argmax-based distillation.\n* State-Level Supervision via CPR: CPR provides intermediate, context-sensitive reward signals during trajectory generation, helping to stabilize training and improve credit assignment in long-horizon reasoning tasks where final rewards are sparse or noisy.\n* Comprehensive Evaluation: The experiments benchmark NaDRO across TSP and CVRP using multiple LLM backbones, including DeepSeek variants, and show improvements over strong baselines like GRPO and RLAIF. Ablation studies further isolate the roles of POR and CPR, confirming that both components contribute to final performance\n\n# Weaknesses\n\n* Heuristic CPR Labels May Limit Generality: The CPR supervision relies on handcrafted heuristics (e.g., binning cost/tour length into categories), which introduces labeling bias and may not generalize to domains where such features are unavailable or noisy.\n* No Explicit Credit Assignment Analysis: While CPR may help credit assignment, the paper lacks analysis showing whether it improves learning dynamics or sample efficiency, particularly in longer-horizon settings.\n* No Sensitivity Analysis of POR: The paper does not evaluate how sensitive POR is to the choice of rank cutoffs (e.g., top-k) or to the quality of the MCTS rankings. It is unclear how robust POR remains if ranking noise causes mislabeling near the decision threshold.", "was_revised": true, "final_justification": "After carefully reviewing both the paper and the rebuttal, I find this to be a strong submission for NeurIPS. The additional experiments provided by the authors directly address my earlier questions and points of potential weaknesses convincingly. I will keep my original score.", "rebuttal": "We thank the reviewer for their positive evaluation and constructive comments. We have performed the requested supplementary analyses and will incorporate them into the final version.\n\n> **Q1: How does CPR contribute specifically to solving long-horizon credit assignment, beyond acting as an auxiliary classification loss? While CPR improves performance, it’s unclear whether its benefits stem from better credit assignment over multi-step trajectories, or simply from regularizing the model with intermediate supervision. Could one isolate its impact by measuring reward variance or learning dynamics with/without CPR over varying trajectory lengths?**\n\nThank you for this insightful question. `CPR`'s primary contribution is providing a dense, immediate, and outcome-independent reward for correct qualitative state assessment. This stabilizes the learning signal, building a reliable cognitive foundation for the policy, which is crucial for long-horizon tasks where final rewards are sparse and noisy. We demonstrate this with two key pieces of evidence.\n\n1.  **Learning Dynamics**: `CPR` successfully guides the model to learn correct state perception. As shown in **Table 1**, baseline methods (`raw_GRPO`, `GRPO+por`) fail to achieve this, registering low or negative \"Correctness Rewards.\" In contrast, our full method (`ours`) shows a sustained and significant increase in this reward, confirming that `CPR` provides a meaningful, process-based learning signal that was previously absent.\n\n    **Table 1: Correctness Reward Dynamics during Training**\n    | **Method** | **5** | **105** | **205** | **305** | **405** | **505** | **605** | **705** | **805** | **905** | **1005** | **1105** | **1205** | **1305** | **1405** | **1505** | **1605** | **1705** | **1805** | **1905** | **2005** | **2105** | **2205** | **2305** | **2405** | **2505** | **2605** | **2705** | **2805** | **2905** |\n    |:---|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n    | `GRPO` | -0.0861 | -0.0703 | -0.0572 | -0.0571 | -0.0530 | -0.0328 | -0.0179 | -0.0266 | -0.0420 | -0.0672 | -0.0605 | -0.0350 | 0.0067 | 0.0028 | 0.0087 | 0.0099 | 0.0293 | 0.0132 | 0.0237 | 0.0485 | 0.0443 | 0.0352 | 0.0281 | 0.0152 | 0.0297 | 0.0510 | 0.0833 | 0.0791 | 0.0724 | 0.0462 |\n    | `GRPO+POR` | -0.0762 | -0.0245 | -0.0180 | -0.0207 | -0.0133 | -0.0063 | -0.0063 | -0.0052 | -0.0132 | -0.0446 | -0.0389 | -0.0043 | 0.0291 | 0.0241 | 0.0309 | 0.0360 | 0.0383 | 0.0354 | 0.0472 | 0.0548 | 0.0455 | 0.0397 | 0.0426 | 0.0395 | 0.0555 | 0.0768 | 0.1088 | 0.1126 | 0.0941 | 0.0833 |\n    | `NaDRO(ours)` | -0.0286 | 0.0751 | 0.0593 | 0.0744 | 0.0939 | 0.1155 | 0.0991 | 0.0847 | 0.0988 | 0.1085 | 0.1065 | 0.1128 | 0.1385 | 0.1232 | 0.1128 | 0.1166 | 0.1342 | 0.1428 | 0.1543 | 0.1318 | 0.1205 | 0.1206 | 0.1485 | 0.1597 | 0.1382 | 0.1465 | 0.1475 | 0.1642 | 0.1509 | 0.1309 |\n\n2.  **Ablation Study**: Our ablation study (**Table 2**) quantifies `CPR`'s critical impact on final task performance. When evaluating pure policy performance (TTS Level=0), adding `CPR` to the `GRPO` + `POR` model causes the optimality gap to drop from 6.74% to 3.17%. This demonstrates that `CPR` is a decisive component driving the final SOTA performance.\n\n**Table 2: Ablation Study on NaDRO Components (Optimality Gap % on pr152)**\n\n| TTS Level | Qwen 7B (Base) | GRPO Baseline | GRPO + POR | NaDRO (Full, Ours) |\n|:---:|:---:|:---:|:---:|:---:|\n| tts = 0 | 18.33 ± 1.2 | 11.57 ± 1.4 | 6.74 ± 1.1 | 3.17 ± 1.1 |\n| tts = 1 | 5.83 ± 0.9 | 4.66 ± 1.8 | 3.54 ± 0.8 | 1.74 ± 0.7 |\n| tts = 2 | 3.62 ± 0.3 | 3.86 ± 0.5 | 2.64 ± 0.3 | 1.77 ± 0.2 |\n| tts = 4 | 1.69 ± 0.3 | 2.14 ± 0.3 | 1.79 ± 0.2 | 1.48 ± 0.2 |\n| tts = 10 | 1.31 ± 0.2 | 1.04 ± 0.1 | 0.87 ± 0.2 | 0.22 ± 0.1 |\n| tts = 20 | 0.88 ± 0.1 | 0.87 ± 0.2 | 0.63 ± 0.1 | 0.16 ± 0.1 |\n| tts = 30 | 0.32 ± 0.1 | 0.41 ± 0.1 | 0.14 ± 0.1 | 0.04 ± 0.1 |\n\n> **Q2:  How sensitive is POR to the rank cutoff parameters and MCTS quality? Since POR transforms noisy Q-values into ordinal rankings and selects top-k actions for positive supervision, could a poorly chosen cutoff degrade performance by discarding near-optimal actions that fall just below the threshold?**\n\nWe sincerely appreciate the reviewer's insightful question. To thoroughly investigate the robustness of our Preference-based Outcome Reward (POR) framework, we have conducted a new series of experiments. The results are presented below. **Please note that due to submission constraints not allowing for image files, this table presents sampled data points from performance curves. The complete graphs will be included in the final camera-ready version.**\n\nWe tested various cutoff thresholds (*k*). It is important to clarify the settings: `ours_k0.5` uses a standard 50% cutoff. The **`ours_random`** setting also uses a 50% cutoff but introduces severe noise: there is a **10% probability at each step of the entire preference list being completely shuffled**.\n\n**Table 3: Empirical Performance with Varying $k$ and Injected Noise (Correctness Reward)**\n| **Method** | **5** | **105** | **205** | **305** | **405** | **505** | **605** | **705** | **805** | **905** | **1005** | **1105** | **1205** | **1305** | **1405** | **1505** | **1605** | **1705** | **1805** | **1905** | **2005** | **2105** | **2205** | **2305** | **2405** | **2505** | **2605** | **2705** | **2805** | **2905** |\n|:---|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| `ours_k0.1` | -0.0286 | 0.0765 | 0.0678 | 0.0864 | 0.0996 | 0.1166 | 0.0967 | 0.0829 | 0.1058 | 0.1225 | 0.1185 | 0.1064 | 0.1279 | 0.1223 | 0.1161 | 0.1128 | 0.1371 | 0.1439 | 0.1518 | 0.1301 | 0.1107 | 0.1117 | 0.1383 | 0.1591 | 0.1260 | 0.1406 | 0.1461 | 0.1579 | 0.1432 | 0.1215 |\n| `ours_k0.3` | -0.0286 | 0.0704 | 0.0614 | 0.0824 | 0.1002 | 0.1134 | 0.1014 | 0.0778 | 0.0934 | 0.1096 | 0.1150 | 0.1132 | 0.1306 | 0.1195 | 0.1067 | 0.1166 | 0.1383 | 0.1468 | 0.1385 | 0.1249 | 0.1055 | 0.1072 | 0.1282 | 0.1467 | 0.1181 | 0.1392 | 0.1543 | 0.1760 | 0.1477 | 0.1334 |\n| `ours_k0.5` | -0.0286 | 0.0751 | 0.0593 | 0.0744 | 0.0939 | 0.1155 | 0.0991 | 0.0847 | 0.0988 | 0.1085 | 0.1065 | 0.1128 | 0.1385 | 0.1232 | 0.1128 | 0.1166 | 0.1342 | 0.1428 | 0.1543 | 0.1318 | 0.1205 | 0.1206 | 0.1485 | 0.1597 | 0.1382 | 0.1465 | 0.1475 | 0.1642 | 0.1509 | 0.1309 |\n| `ours_k0.7` | -0.0187 | 0.0816 | 0.0704 | 0.0929 | 0.1075 | 0.1177 | 0.1162 | 0.0991 | 0.1078 | 0.1175 | 0.1145 | 0.1185 | 0.1488 | 0.1511 | 0.1228 | 0.1140 | 0.1430 | 0.1484 | 0.1533 | 0.1292 | 0.1090 | 0.1050 | 0.1507 | 0.1718 | 0.1547 | 0.1790 | 0.1823 | 0.1922 | 0.1561 | 0.1459 |\n| `ours_random` | -0.0094 | 0.0579 | 0.0583 | 0.0843 | 0.0999 | 0.1126 | 0.1019 | 0.0808 | 0.1051 | 0.1090 | 0.0959 | 0.0939 | 0.1222 | 0.1258 | 0.1188 | 0.1149 | 0.1342 | 0.1534 | 0.1578 | 0.1401 | 0.1182 | 0.1149 | 0.1372 | 0.1572 | 0.1340 | 0.1500 | 0.1549 | 0.1784 | 0.1552 | 0.1273 |\n\n**Key Findings:**\n\n1.  **High Robustness across *k* Values**: The framework demonstrates strong robustness, as all *k* settings yield competitive performance without any catastrophic failure. Notably, the **`k=0.7` setting shows slightly superior performance across many stages**.\n\n2.  **Exceptional Resilience to Severe Ranking Noise**: The `ours_random` result is a powerful testament to POR's resilience. Even when faced with a 10% chance of the ranking signal becoming **completely random**, the model's performance **does not collapse and remains on par with other stable settings**. This directly proves that the framework can withstand not just minor misrankings but also occasional catastrophic failures in the preference signal, strongly validating its suitability for learning from highly noisy data.\n\nThese findings confirm that POR is not overly sensitive to its parameters and is exceptionally robust to noise. We will incorporate this analysis into the final manuscript."}, {"review_id": "EaAgGRV3dF", "reviewer": "Reviewer_4Ria", "summary": "This paper proposes a framework called NaDRO, which combines two mechanisms—Preference-based Outcome Reward (POR) and Context Perception Reward (CPR)—to train large language models (LLMs) using noisy Monte Carlo Tree Search (MCTS) data, addressing decision-making noise in combinatorial optimization problems. The experimental section validates NaDRO's effectiveness by comparing multiple baseline models (e.g., Qwen 7B, Llama 3-8B) and demonstrates performance advantages in tasks such as TSP and CVRP. The paper is well-structured, the framework design is practical, and the code and data are open-sourced.", "questions": "--Theoretical Clarifications:\nProvide error bounds for POR under noisy distributions or prove CPR’s impact on policy gradient optimization.\n--Enhanced Experimental Rigor:\nReport standard deviations for multi-run experiments.\nTest robustness in additional noise scenarios (e.g., artificially injected noise).\nInclude comparisons with SOTA noise-robust methods.\n--Extended TTS Analysis:\nSupplement experimental results for TTS level > 10 to clarify performance trends.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n--Practical Problem Setting: The paper focuses on the challenge of training LLMs on noisy data, particularly for long-sequence decision-making tasks in combinatorial optimization (e.g., TSP/CVRP), which is highly relevant to real-world applications.\n--Reproducible Methodology: The method is thoroughly designed and reproducible. Appendices provide complete implementation details (state/action space definitions, CPR annotation rules, hyperparameter configurations), and the code is open-sourced (Appendices A-F cover data generation, training pipeline, and parameter settings).\n--Comprehensive Experimental Validation:\nEvaluated on two classical problems (TSP and CVRP).\nExtensive baseline comparisons with significant results.\n\nWeaknesses:\n--Lack of Theoretical Analysis:\nNo convergence proof for POR/CPR in policy optimization or theoretical bounds on noise robustness (only heuristic experiments in Figure 3).\n--Potential Bias in CPR Labeling:\nCPR labels in Appendix C are based on greedy solution thresholds (±15%–20%), but the universality of this rule for decision quality is not validated, possibly introducing bias.\n--Limitations in Experimental Validation:\nNo Statistical Significance: Results (e.g., Tables 1–3) lack standard deviations/confidence intervals, making it unclear whether performance differences are significant (authors acknowledge limited computational resources for multiple runs, see Page 27 Q7).\nNarrow Noise Scope: Only MCTS-simulated noise is tested (Section 3.2), without real-world noise (e.g., crowdsourced or expert disagreement noise), weakening generalization claims.\nInsufficient Baseline Comparisons: Missing comparisons with state-of-the-art noise-robust methods (e.g., Robust RLHF by Shen et al. 2024), limiting the evaluation to basic GRPO.\n--Ablation Study Ambiguity:\nIn ablation experiments (Table 3), the performance gap between POR and GRPO narrows as TTS level increases. Would this gap further diminish with TTS level > 10?", "was_revised": true, "final_justification": "The author's response has addressed my concerns, so I will raise my score to Borderline Accept.", "rebuttal": "We thank the reviewer for their positive evaluation and constructive comments. We have performed the requested supplementary analyses and will incorporate them into the final version.\n\n> **Q1: Theoretical Clarifications: Provide error bounds for POR under noisy distributions or prove CPR’s impact on policy gradient optimization.**\n\nDue to space constraints, the impact of **CPR** on policy gradient optimization has been detailed in our response to Reviewer **5e7B**. Here, we will focus on the theoretical analysis of how **POR** provides robustness and reduces gradient variance under noisy distributions, directly addressing the core of your question.\n\n**Theoretical Analysis of POR's Lower Gradient Variance under Noise**\n\nWe provide a theoretical analysis demonstrating that **Preference-based Outcome Reward (POR)** inherently reduces policy gradient variance compared to a standard Top-1 reward scheme, ensuring a more robust optimization process under noisy distributions.\n\n* **Mathematical Setup**: Let's simplify POR to a binary model: actions in the top-*k* (as ranked by noisy MCTS) receive a reward of 1, and others receive 0. We compare this to a Top-1 scheme where only the single best action gets a reward. The core randomness stems from MCTS noise (`ϵ`), which makes the rank of any action a random variable. The variance of a Bernoulli reward (taking values in {0, 1}) is given by `Var(R) = p(1-p)`, where `p` is the probability of receiving the reward.\n\n* **Key Derivation**: For any high-quality action `a*`, the probability of it ranking in the top-*k* (`p_k = P(rank(a*, ϵ) ≤ k)`) is fundamentally greater than or equal to the probability of it being exactly rank 1 (`p_1 = P(rank(a*, ϵ) = 1)`). Due to noise and competition, `p_1` may be significantly less than 1 (e.g., 0.6), whereas `p_k` remains very high (e.g., >0.95).\n    Since the variance function `f(p) = p(1-p)` is monotonically decreasing on the interval `[0.5, 1]`, and we have `0.5 ≤ p_1 < p_k ≈ 1`, it directly follows that:\n    $$Var(R_{POR}) < Var(R_{Top-1})$$\n\n> **Q2: Enhanced Experimental Rigor: Report standard deviations for multi-run experiments. Test robustness in additional noise scenarios.**\n\nWe thank the reviewer for these constructive suggestions to enhance the paper's experimental rigor. We have addressed each point as detailed below.\n\n**1. Reporting Standard Deviations for Multi-Run Experiments**\n\nTo improve statistical rigor, we have conducted multiple runs for all experiments and updated our main results table to include both the **mean and standard deviation**. The revised table is presented below. The results confirm that **NaDRO's superior performance is statistically robust**. Our method not only achieves a lower optimality gap on average but also exhibits relatively low variance, indicating consistent and reliable performance across runs.\n\n**Table 4: Comparative optimality gap (%) on TSP instances, updated with Mean ± Standard Deviation**\n| **Method** | `a280` | `bier127` | `brg180` | `ch130` | `gr202` | `gr96` | `pr124` | `pr152` | `pr76` | `rd100` | `tsp225` | `u159` |\n|:---|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| ***Traditional Solvers*** |\n| LKH | 0.01 ± 0.0 | 0.00 ± 0.0 | 0.00 ± 0.0 | 0.00 ± 0.0 | 0.00 ± 0.0 | 0.00 ± 0.0 | 0.00 ± 0.0 | 0.00 ± 0.0 | 0.00 ± 0.0 | 0.00 ± 0.0 | 0.01 ± 0.0 | 0.00 ± 0.0 |\n| OR-Tools | 6.32 ± 0.0 | 2.91 ± 0.0 | 0.51 ± 0.0 | 0.51 ± 0.0 | 5.12 ± 0.0 | 3.11 ± 0.0 | 2.34 ± 0.0 | 2.92 ± 0.0 | 2.58 ± 0.0 | 3.93 ± 0.0 | 5.13 ± 0.0 | 3.14 ± 0.0 |\n| ***Metaheuristics*** |\n| GLS | 2.83 ± 1.7 | 1.73 ± 0.1 | 3.58 ± 2.5 | 5.32 ± 2.1 | 5.44 ± 0.3 | 1.65 ± 0.8 | 1.47 ± 0.9 | 2.82 ± 0.9 | 1.05 ± 0.4 | 7.48 ± 2.3 | 3.74 ± 1.2 | 4.22 ± 1.4 |\n| EoH + GLS | 4.04 ± 0.6 | 1.25 ± 0.5 | 4.35 ± 2.3 | 5.64 ± 2.4 | 3.31 ± 1.1 | 1.34 ± 0.4 | 1.92 ± 0.4 | 2.73 ± 0.7 | 1.31 ± 0.3 | 3.85 ± 1.2 | 2.56 ± 0.1 | 4.07 ± 0.6 |\n| ACO | 17.78 ± 1.3 | 5.71 ± 0.4 | 3.43 ± 2.4 | 8.89 ± 1.4 | 10.43 ± 2.7 | 12.58 ± 2.6 | 3.78 ± 0.7 | 4.70 ± 1.6 | 9.26 ± 1.1 | 17.12 ± 2.9 | 9.71 ± 2.1 | 9.28 ± 1.5 |\n| ReEvo + GLS | 3.92 ± 0.5 | 2.31 ± 0.5 | 4.11 ± 2.3 | 5.04 ± 1.9 | 5.80 ± 0.7 | 2.37 ± 1.2 | 2.37 ± 0.1 | 2.88 ± 1.6 | 1.86 ± 0.6 | 6.70 ± 2.1 | 4.73 ± 1.6 | 3.99 ± 1.5 |\n| ReEvo + ACO | 15.91 ± 2.1 | 4.86 ± 1.5 | 3.91 ± 2.3 | 5.85 ± 1.4 | 8.29 ± 1.4 | 6.66 ± 1.4 | 4.12 ± 1.9 | 7.87 ± 0.5 | 7.71 ± 0.1 | 9.12 ± 0.9 | 6.99 ± 2.9 | 5.52 ± 0.1 |\n| ***LLM-based Approaches*** |\n| GPT-4o | 7.11 ± 1.1 | 1.72 ± 0.4 | 4.70 ± 0.6 | 3.19 ± 0.3 | 4.23 ± 1.2 | 1.55 ± 0.3 | 0.87 ± 0.5 | 1.29 ± 0.6 | 0.99 ± 0.7 | 2.18 ± 0.7 | 5.78 ± 0.6 | 2.48 ± 0.7 |\n| GPTo3 | **3.71 ± 0.4** | 1.48 ± 0.4 | 2.67 ± 0.3 | 2.86 ± 0.2 | 3.79 ± 0.5 | 0.53 ± 0.4 | 0.21 ± 0.2 | 0.28 ± 0.2 | 0.37 ± 0.3 | 0.44 ± 0.5 | 5.11 ± 0.6 | **0.68 ± 0.3** |\n| Deepseek-R1 | 14.10 ± 0.7 | 2.31 ± 0.5 | 2.94 ± 0.5 | 2.27 ± 0.8 | 3.88 ± 0.5 | 1.04 ± 0.2 | 0.17 ± 0.2 | 0.86 ± 0.2 | 0.69 ± 0.3 | 1.18 ± 0.4 | 6.47 ± 0.9 | 1.83 ± 0.5 |\n| Qwen 7B | 8.83 ± 1.4 | 5.31 ± 1.7 | 5.86 ± 1.9 | 4.45 ± 0.3 | 15.38 ± 3.3 | 3.89 ± 0.4 | 1.22 ± 0.3 | 1.31 ± 0.2 | 2.33 ± 0.4 | 3.98 ± 1.1 | 10.42 ± 1.9 | 3.29 ± 0.5 |\n| GRPO on Qwen 7B | 7.33 ± 0.4 | 1.39 ± 0.2 | 5.42 ± 0.3 | 2.29 ± 0.3 | 14.68 ± 0.4 | 1.97 ± 0.2 | 0.13 ± 0.2 | 1.04 ± 0.1 | 1.23 ± 0.2 | 2.43 ± 0.2 | 11.14 ± 0.3 | 2.57 ± 0.4 |\n| Llama 8B | 9.21 ± 1.2 | 4.85 ± 0.7 | 7.39 ± 0.8 | 4.86 ± 0.5 | 13.43 ± 1.1 | 4.47 ± 0.8 | 1.65 ± 0.3 | 2.07 ± 0.4 | 1.79 ± 0.2 | 3.84 ± 0.5 | 9.92 ± 1.3 | 3.51 ± 0.4 |\n| GRPO on Llama 8B | 8.10 ± 0.6 | 3.09 ± 0.3 | 5.22 ± 0.5 | 3.91 ± 0.7 | 11.33 ± 0.7 | 2.39 ± 0.5 | 0.82 ± 0.2 | 0.89 ± 0.2 | 0.67 ± 0.1 | 2.12 ± 0.8 | 7.33 ± 1.1 | 2.08 ± 0.5 |\n| **NaDRO-Llama(Ours)** | 6.22 ± 0.4 | 1.35 ± 0.2 | 2.17 ± 0.3 | 2.19 ± 0.3 | 2.41 ± 0.5 | 0.28 ± 0.1 | 0.13 ± 0.1 | 0.37 ± 0.1 | **0.31 ± 0.1** | 0.70 ± 0.2 | 4.89 ± 0.8 | 0.94 ± 0.2 |\n| **NaDRO-Qwen(Ours)** | 5.31 ± 0.7 | **0.63 ± 0.1** | **0.08 ± 0.1** | **1.80 ± 0.2** | **2.29 ± 0.3** | **0.16 ± 0.2** | **0.00 ± 0.0** | **0.22 ± 0.1** | 0.63 ± 0.2 | **0.11 ± 0.1** | **3.76 ± 0.5** | 1.38 ± 0.3 |\n\n**2. Robustness in Additional Noise Scenarios**\n\nTo further validate robustness, we conducted a stress test with **artificially injected noise**. In this experiment, we introduced a 10% probability at each decision step of **completely randomizing the MCTS preference list**. This simulates a catastrophic failure in the ranking signal.\n\nOur findings show that even under this severe noise condition, **NaDRO's performance does not collapse** and remains competitive and stable. This powerful result demonstrates the framework's exceptional resilience to extreme data corruption, going beyond the inherent noise of MCTS.\n\n> **Q3: Extended TTS Analysis: Supplement experimental results for TTS level > 10 to clarify performance trends.**\n\nThank you for the insightful questions regarding the performance trends at higher Test-Time Search (TTS) levels and the dynamics of the performance gaps in our ablation study. To clarify these points, we have extended our analysis up to a TTS level of 30. The supplemented results are presented in the table 5 below.\n\n**Table 5: Extended Ablation Study on NaDRO Components and TTS Level (Optimality Gap % on pr152)**\n| TTS Level | Qwen 7B (Base) | GRPO Baseline | GRPO + POR | NaDRO (Full, Ours) |\n|:---:|:---:|:---:|:---:|:---:|\n| tts = 0 | 18.33 ± 1.2 | 11.57 ± 1.4 | 6.74 ± 1.1 | **3.17 ± 1.1** |\n| tts = 1 | 5.83 ± 0.9 | 4.66 ± 1.8 | 3.54 ± 0.8 | **1.74 ± 0.7** |\n| tts = 2 | 3.62 ± 0.3 | 3.86 ± 0.5 | 2.64 ± 0.3 | **1.77 ± 0.2** |\n| tts = 4 | 1.69 ± 0.3 | 2.14 ± 0.3 | 1.79 ± 0.2 | **1.48 ± 0.2** |\n| tts = 10 | 1.31 ± 0.2 | 1.04 ± 0.1 | 0.87 ± 0.2 | **0.22 ± 0.1** |\n| tts = 20 | 0.88 ± 0.1 | 0.87 ± 0.2 | 0.63 ± 0.1 | **0.16 ± 0.1** |\n| tts = 30 | 0.32 ± 0.1 | 0.41 ± 0.1 | 0.14 ± 0.1 | **0.04 ± 0.1** |\n\n**Clarification on Performance Trends and Gaps:**\n\n1.  **General Trend**: As expected, increasing the TTS budget improves performance across all models. This confirms that a larger search space at inference time is beneficial.\n\n2.  **Addressing the Narrowing Gap**: You correctly observed that the performance gap between `GRPO + POR` and the `GRPO Baseline` narrows at some levels. Our extended results clarify this trend. While extensive search can help weaker models compensate for their policy deficits, the **`GRPO + POR` model consistently outperforms the `GRPO Baseline`** at every TTS level, confirming the value of the POR component.\n\n3.  **NaDRO's Superior Scalability with TTS**: Most importantly, the extended analysis reveals that our full **`NaDRO` model benefits most from an increased TTS budget**. The performance gap between `NaDRO` and all other baselines remains significant and even widens in terms of relative improvement at higher search levels. At TTS=30, NaDRO achieves a near-optimal gap of just **0.04%**, demonstrating a powerful synergy between a robust, well-trained policy and test-time computation. A better policy makes the search process far more effective.\n\n> **Q3: Insufficient Baseline Comparisons: Missing comparisons with state-of-the-art noise-robust methods (e.g., Robust RLHF by Shen et al. 2024), limiting the evaluation to basic GRPO.**\n\nThank you for your valuable feedback. We have carefully analyzed the work by Shen et al. (2024) and believe our NaDRO framework differs fundamentally in its problem setting, noise source, and core methodology. \"Robust RLHF\" addresses an inaccurate Reward Model (RM) in general LLM alignment, which stems from errors in human preference labeling. In contrast, NaDRO focuses on specialized sequential decision-making tasks, dealing with noise inherent in the training data itself, caused by inaccurate MCTS estimations.\n\nCrucially, a direct experimental comparison is not feasible. The \"Robust RLHF\" paper states that the code will only be released \"upon acceptance.\" Given its status as a withdrawn paper from ICLR 2025, an official public implementation is unavailable."}, {"review_id": "mDFibdEkCp", "reviewer": "Reviewer_pkT3", "summary": "The paper proposes NaDRO (Noise-Aware Dual-Reward Optimization), a framework for fine-tuning LLMs in noisy training environments. It introduces two reward mechanisms:\n\n1. Preference-based Outcome Reward (POR): Guides learning using relative rankings of actions instead of relying on potentially noisy absolute scores from sources like Monte Carlo Tree Search (MCTS).\n\n2. Context Perception Reward (CPR): Provides intermediate supervision by encouraging the model to qualitatively assess the problem state before making decisions.\n\nThe framework is tested on combinatorial optimization tasks (TSP and CVRP), and shows improved performance over strong baselines, including GPT-4o, GRPO-finetuned models, and traditional metaheuristics.", "questions": "See weakness.", "limitations": "I didn't find the discussion of limitation.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The paper addresses the practical problem that finetuning LLM for combinatorial optimization problem. The problem is important and challenge.\n2. The use of relative preferences (POR) is well justified as a noise-robust alternative to direct score regression. CPR encourages process-level reasoning, which adds interpretability and structure.\n3. NaDRO-fine-tuned models show substantial gains on TSP and CVRP benchmarks, even outperforming larger LLMs in some cases.\n\nWeaknesses:\n\n1. The primary weakness of the paper is that the proposed approach is highly heuristic. The main contribution lies in the design of the reward signals (POR and CPR), but these are introduced without accompanying theoretical analysis or systematic empirical justification beyond the benchmark results. There is no ablation on the design of the rewards, nor any attempt to analyze their properties or limitations.\n\n2. Most baseline comparisons are made against publicly available LLMs (e.g., GPT-4o, DeepSeek) without task-specific fine-tuning on TSP or CVRP. Throughout the experimental section, only one model—GRPO-Qwen—is fine-tuned on the dataset. Given that the authors provide results for NaDRO-Llama-8B, it is unclear why corresponding results for Llama-8B (zero-shot) and GRPO-Llama-8B (fine-tuned using existing methods) are omitted. These comparisons are important: the former would clarify the benefit of any fine-tuning, while the latter would isolate the effect of the new reward design relative to established methods.\n\n3. Most critically, the paper lacks a proper ablation study isolating the effects of the two proposed reward components. Without such analysis, it is difficult to assess whether the POR and CPR signals meaningfully contribute to the observed improvements. Since the paper is largely empirical in nature, the absence of such foundational validation weakens the contribution. As it stands, the work does not meet the scientific rigor expected of a NeurIPS paper.\n\n4. Throughout the paper, the citation format is inaccurate. The authors should use \\citep{} when the citation is not a part of the sentence.", "was_revised": true, "final_justification": "I thank the authors for the detailed response. I really appreciate the additional experiments provided. My questions 2-4 is addressed. As for my question 1, it is mentioned that \"from a policy gradient perspective, as detailed elsewhere in our rebuttal, POR is designed to produce a low-bias, low-variance gradient estimator\". The bias and variance is justified using the binary model, with variance p(1-p). This analysis below my expectations. Nevertheless, I will increase my score.", "rebuttal": "We thank the reviewer for their positive evaluation and constructive comments. We have performed the requested supplementary analyses and will incorporate them into the final version.\n\n> **Q1:  The primary weakness of the paper is that the proposed approach is highly heuristic.**\n\nThank you for the insightful feedback regarding the need for deeper justification for the proposed reward design. This is a crucial point, and this response will address the core of the issue. More detailed analyses of each component are provided in other sections of our rebuttal.\n\n**1. On the Principled Design of POR**\n\nIn response to the reviewer's point about the method's contribution, it is important to clarify that **POR is not a heuristic but a principled approach** to ensure stable training in noisy environments.\n\nFrom a policy gradient perspective, as detailed elsewhere in our rebuttal, POR is designed to produce a **low-bias, low-variance gradient estimator**. This is achieved by rewarding a stable *region* of top actions (\"ensembling\") rather than a volatile single best action. This structure mathematically guarantees a more reliable convergence process compared to naive reward schemes.\n\n**2. Analysis of Reward Design, Properties, and Limitations**\n\nRegarding the request for a more explicit analysis of the rewards' design, properties, and limitations, we offer the following:\n\n* **Ablation on Reward Design**: Ablation studies on key design parameters have been performed. For instance, testing POR's cutoff threshold *k* (from 10% to 70%) revealed the performance to be highly robust. Furthermore, a stress test was conducted by **injecting severe artificial noise** (completely randomizing the preference list 10% of the time), which showed that **performance did not collapse**. This empirically validates the robustness of the chosen design.\n\n* **Analysis of Properties and Limitations**:\n    * **POR**: A key property of POR is its ability to filter noise and reduce gradient variance. Its **limitation**, however, is that its effectiveness relies on the MCTS rankings being meaningful, even if noisy. In scenarios with an extremely poor MCTS rollout policy, the quality of the relative rankings themselves could degrade, limiting POR's efficacy.\n    * **CPR**: A core property of CPR is providing a dense, process-based reward that stabilizes learning, a point elaborated upon in our other responses. Its primary **limitation** is that the qualitative features are currently **hand-engineered** and require rule-based annotation. This reliance on manual design restricts its out-of-the-box applicability to entirely new problem domains and points to a clear direction for future work in automatic feature discovery.\n\n\n> **Q2:Most baseline comparisons are made against publicly available LLMs (e.g., GPT-4o, DeepSeek) without task-specific fine-tuning on TSP or CVRP. \"**\n  \nThank you for this critical feedback. You are correct that a full comparison including the Llama-8B baselines is essential for a rigorous evaluation and to properly isolate the contributions of our method. We apologize for this omission in the initial submission.\n\nTo address this, we have now run these experiments and included the results for **Llama-8B (Base)** and **GRPO on Llama 8B** in our main results table. You can see our response to Reviewer **4Ria**. This new data allows us to draw two clear conclusions, directly addressing your points:\n\n1.  **Benefit of Standard Fine-Tuning**: Comparing `GRPO on Llama 8B` to the `Llama 8B (Base)` model shows that applying an established fine-tuning method (GRPO) does provide a noticeable, though often modest, performance improvement. For instance, on instance `gr202`, the optimality gap improves from 13.43% to 11.33%. This confirms the benefit of task-specific fine-tuning.\n\n2.  **Isolating the Effect of NaDRO**: The most critical comparison is between `NaDRO-Llama` and `GRPO on Llama 8B`. Here, the results are stark. On `gr202`, our method reduces the gap from 11.33% down to just **2.41%**. Similarly, on `pr152`, the gap is more than halved from 0.89% to **0.37%**. This demonstrates unequivocally that **the vast majority of the performance gain is attributable to our novel NaDRO reward design**, not just the fine-tuning process itself.\n\n> **Q3: Most critically, the paper lacks a proper ablation study isolating the effects of the two proposed reward components.** \n\nThank you for this critical feedback. We agree that a rigorous ablation study isolating the effects of POR and CPR is fundamental to our contribution, and we would like to respectfully clarify that this analysis was indeed a core part of our original submission.\n\n**1. Existing Ablation Study in the Original Manuscript**\n\nIn **Section 5.3, Table 3** of our original paper, we presented an ablation study that explicitly decomposes the contribution of each component to the final task performance. \n\nFor example, at a TTS level of 0, the optimality gap improves from 11.57% (GRPO) to 6.74% (GRPO+POR), and finally to 3.17% (NaDRO), quantifying the meaningful and distinct contribution of each component.\n\n**2. Deeper Analysis of Learning Dynamics: Reward Variance and Reward Hacking**\n\nTo further deepen this analysis, we have conducted a new investigation into the *training process itself*, focusing on reward variance and loss curves. This reveals *how* our components lead to superior performance by ensuring a more stable and meaningful learning process.\n\n**Table 6: Analysis of Training Loss Curves**\n\n| **Method** | **2000** | **2135** | **2270** | **2405** | **2540** | **2675** | **2810** | **2945** | **3080** | **3215** | **3350** | **3485** | **3620** | **3755** | **3890** | **4025** | **4160** | **4295** | **4430** | **4565** | **4700** | **4835** | **4970** | **5105** | **5240** | **5375** | **5510** | **5645** | **5780** | **5915** |\n|:---|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| **GRPO** | 0.000100 | 0.000193 | 0.000212 | 0.000376 | 0.000638 | 0.000814 | 0.000854 | 0.000826 | 0.000842 | 0.000878 | 0.000832 | 0.000744 | 0.000760 | 0.000798 | 0.000756 | 0.000704 | 0.000682 | 0.000644 | 0.000654 | 0.000674 | 0.000708 | 0.000712 | 0.000688 | 0.000678 | 0.000660 | 0.000666 | 0.000688 | 0.000680 | | |\n| **NaDRO(ours)*** | 0.000200 | 0.000236 | 0.000246 | 0.000290 | 0.000380 | 0.000510 | 0.000680 | 0.000798 | 0.000818 | 0.000900 | 0.000980 | 0.001020 | 0.001046 | 0.001034 | 0.001048 | 0.001138 | 0.001152 | 0.001254 | 0.001306 | 0.001270 | 0.001274 | 0.001314 | 0.001300 | 0.001324 | 0.001408 | 0.001508 | 0.001510 | 0.001456 | 0.001398 | 0.001496 |\n| **GRPO+POR** | 0.000200 | 0.000157 | 0.000174 | 0.000202 | 0.000250 | 0.000346 | 0.000514 | 0.000700 | 0.000764 | 0.000806 | 0.000864 | 0.000834 | 0.000788 | 0.000794 | 0.000782 | 0.000814 | 0.000784 | 0.000710 | 0.000772 | 0.000820 | 0.000782 | 0.000788 | 0.000784 | 0.000796 | 0.000766 | 0.000704 | 0.000750 | 0.000810 | 0.000784 | 0.000776 |\n\n\n\n**Table 7: Reward Variance During Training**\n\n| **Method** | **5** | **170** | **335** | **500** | **665** | **830** | **995** | **1160** | **1325** | **1490** | **1655** | **1820** | **1985** | **2150** | **2315** | **2480** | **2645** | **2810** | **2975** | **3140** | **3305** | **3470** | **3635** | **3800** | **3965** | **4130** | **4295** | **4460** | **4625** | **4790** | **4955** |\n|:---|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| **GRPO** | 0.8711 | 1.0822 | 1.0805 | 1.0634 | 1.0254 | 1.0806 | 1.0501 | 0.9969 | 0.9412 | 0.9205 | 0.8526 | 0.8033 | 0.7651 | 0.6765 | 0.6611 | 0.6594 | 0.6184 | 0.5531 | 0.5674 | 0.5557 | 0.5652 | 0.5577 | 0.5542 | 0.5703 | 0.5850 | 0.5791 | 0.5546 | 0.5096 | 0.5441 | 0.5031 | 0.5309 |\n| **NaDRO(ours)** | 0.7555 | 0.9128 | 0.8888 | 0.8794 | 0.8833 | 0.8599 | 0.8100 | 0.7757 | 0.7269 | 0.6593 | 0.5857 | 0.5404 | 0.5356 | 0.4981 | 0.4738 | 0.4685 | 0.4765 | 0.4534 | 0.4584 | 0.4615 | 0.4368 | 0.4639 | 0.4741 | 0.4558 | 0.4331 | 0.3947 | 0.3897 | 0.4189 | 0.4032 | 0.4047 | 0.3954 |\n| **GRPO+POR** | 0.9577 | 1.1380 | 1.1484 | 1.1298 | 1.1265 | 1.1180 | 1.1067 | 1.0528 | 0.9942 | 0.9323 | 0.8282 | 0.7748 | 0.7018 | 0.6345 | 0.5852 | 0.5910 | 0.5711 | 0.5450 | 0.5280 | 0.5255 | 0.5002 | 0.4850 | 0.4753 | 0.4787 | 0.4830 | 0.5040 | 0.5244 | 0.4992 | 0.4796 | 0.4537 | 0.4427 |\n\n\n**Key Findings from Training Dynamics:**\n\n* **NaDRO Reduces Reward Variance**: The data confirms that both POR and the full NaDRO framework significantly **reduce reward variance** compared to the GRPO baseline. This creates a more stable learning signal and a more reliable policy gradient, which is crucial for effective convergence.\n\n* **NaDRO Prevents Reward Hacking**: The loss curves offer a critical insight. The standard `GRPO` model's loss quickly drops to a near-zero value. While seemingly positive, this, combined with its poor final performance, indicates a classic case of **reward hacking**. The model has found a \"lazy\" loophole to minimize loss without actually learning a robust policy. In contrast, the **`NaDRO` model maintains a healthier, actively fluctuating loss**, which, paired with its high final reward, proves it remains **meaningfully engaged in the learning process**, avoiding deceptive, low-effort solutions.\n\n> **Q4: Throughout the paper, the citation format is inaccurate. The authors should use \\citep{} when the citation is not a part of the sentence.** \n\nThank you for pointing out the inconsistency in our citation format. We will carefully review the entire manuscript and correct all citations to ensure they fully comply with the NeurIPS style guidelines in the camera-ready version."}, {"review_id": "ZXNXlj8zTZ", "reviewer": "Reviewer_tJhr", "summary": "This paper proposes a novel approach to help LLM learn effectively from noisy or incomplete data. The proposed algorithm, NaDRO, which is built on dual rewards: preference-based outcome reward and context perception reward, synergistically optimizes learning signals from both outcome preference and intermediate reasoning process. The authors validate the empirical performance on two specific problems: travelling salesman problem and capacitated vehicle routing problem.", "questions": "Questions: \n1. While the NaDRO outperforms other LLM-based methods on MCTS-generated data, the conclusion in claiming offering a promising pathway towards real-world noisy data handling is not fully justified by current experiments. I would suggest adding a brief discussion on what types of real-world noise might be relevant and how NaDRO could be adapted or expected to handle them.\n2. The paper adopts fixed thresholds (1.15 and 0.8) for labeling high and low cost in CPR annotation, but it’s unclear how these specific values were determined.\n3. The empirical evaluation does not demonstrate a clear advantage over classical baselines such as LKH in TSP, which raises concerns about the practical relevance of using LLMs for these tasks. What is the advantage of LLM-based methods in such tasks and when would such method be preferable to strong classical solvers?", "limitations": "See Weaknesses and Questions.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths: \nThe paper is well-written, with a clear and logical flow that makes it easy to follow. The methodology is explained in detail, providing a solid understanding of the approach. The ablation study shows the importance of each component clearly.\n\nWeaknesses: \n1. The ablation studies clearly demonstrate that the dual-reward strategy improves performance. However, it is better for the authors to more explicitly articulate the intuition or theoretical basis for combining these specific rewards.\n2. Given that the paper does not provide a theoretical analysis for NaDRO, the empirical results become only evidence supporting the effectiveness of the method. Therefore, it is better to add even a minimal variance analysis across different random seeds to demonstrate that the observed performance improvements are robust.\n3. In the experiments, the comparison methods are appropriately cited. However, it would be helpful to add a brief explanation of the algorithms, for instance, clarifying that LKH stands for ‘Lin-Kernighan-Helsgaun’ and is a widely used heuristic for solving the TSP.", "was_revised": true, "final_justification": "Thank you to the authors for the thorough and thoughtful rebuttal. As the main concerns I raised have now been addressed, I am updating my overall score to 4.", "rebuttal": "We thank the reviewer for their positive evaluation and constructive comments. We have performed the requested supplementary analyses and will incorporate them into the final version.\n\n> **Q1:  The ablation studies clearly demonstrate that the dual-reward strategy improves performance. However, it is better for the authors to more explicitly articulate the intuition or theoretical basis for combining these specific rewards.**\n\nThank you for this excellent question. You are right that a more explicit articulation of the synergy between POR and CPR is crucial. The decision to combine these two rewards is not arbitrary; they are designed to solve two distinct, fundamental challenges in training LLMs for complex decision-making, and their combination creates a powerful synergistic effect.\n\nWe have discussed the individual theoretical and empirical justifications for each component with other reviewers, but we will summarize the core intuition here.\n\n1.  **POR Addresses Noisy *Outcome* Signals**: As detailed in our theoretical analysis (discussed with Reviewer 5e7B  and 4Ria), **POR's primary role is to stabilize the learning signal related to the final *outcome* of an action**. It tackles the noisy credit assignment problem by creating a low-bias, low-variance policy gradient. In essence, POR teaches the model **WHAT** a good action looks like relative to its peers, even when the absolute scores are unreliable.\n\n2.  **CPR Addresses Sparse *Process* Signals**: In long-horizon tasks, rewards are often sparse and delayed. **CPR's role is to provide a dense, stable, and immediate reward for the reasoning *process* itself**. It incentivizes the model to first achieve a correct qualitative understanding of the current state. In essence, CPR teaches the model **WHY** a certain context calls for a specific type of action, independent of the final outcome.\n\n**NaDRO combines these to create a more robust and intelligent agent.** By rewarding both the final action preference (POR) and the preceding cognitive process (CPR), we ensure the model learns a policy that is not only effective in its choices but is also grounded in a correct and verifiable understanding of the problem context. This synergy moves the approach from a \"heuristic\" combination to a principled framework for fostering robust, reason-based decision-making.\n\n> **Q2:  Given that the paper does not provide a theoretical analysis for NaDRO, the empirical results become only evidence supporting the effectiveness of the method. Therefore, it is better to add even a minimal variance analysis across different random seeds to demonstrate that the observed performance improvements are robust.**\n\nThank you for this essential feedback. We completely agree that for an empirically-driven study like ours, demonstrating the statistical robustness of the results across different random seeds is critical to validate our claims.\n\nTo address this, we have conducted multiple runs for all our experiments and have updated our main results table to include both the mean and standard deviation for all reported performance metrics. The detailed table, which we have provided in our response to Reviewer 4Ria, confirms our findings.\n\nAs the updated results demonstrate, our NaDRO-trained models consistently outperform the baselines. More importantly, the low standard deviations associated with our results indicate that these performance improvements are not an artifact of a specific random seed but are indeed robust and statistically significant. This variance analysis provides the necessary empirical evidence to confirm that our method's effectiveness is reliable and reproducible.\n\n> **Q3:  In the experiments, the comparison methods are appropriately cited. However, it would be helpful to add a brief explanation of the algorithms, for instance, clarifying that LKH stands for ‘Lin-Kernighan-Helsgaun’ and is a widely used heuristic for solving the TSP.**\n\nThank you for the positive feedback and this very helpful suggestion. We agree that providing brief descriptions of the baseline algorithms will enhance the clarity of our experimental section.\n\nIn the camera-ready version, we will add concise explanations for key methods like LKH (Lin-Kernighan-Helsgaun), GLS, and others, following the excellent example you provided. This will help readers better understand the context of our results.\n\n> **Q4:  While the NaDRO outperforms other LLM-based methods on MCTS-generated data, the conclusion in claiming offering a promising pathway towards real-world noisy data handling is not fully justified by current experiments. I would suggest adding a brief discussion on what types of real-world noise might be relevant and how NaDRO could be adapted or expected to handle them.**\n\nThank you for this insightful question about justifying the generalization of our method to real-world noise.\n\nWe address this by highlighting a key stress-test experiment, which we also discussed with Reviewer 5e7B. To simulate severe real-world scenarios beyond simple MCTS estimation noise, we injected artificial noise by completely randomizing the MCTS preference list with a 10% probability at each decision step. This setup mimics catastrophic data corruption or severe label noise found in real-world datasets.\n\nThe crucial finding was that NaDRO's performance did not collapse under this extreme condition, remaining stable and competitive. This provides strong empirical evidence that our framework's robustness extends beyond well-behaved estimation noise.\n\nThis resilience stems from NaDRO's core principles. CPR learns a robust state representation by focusing on key qualitative features, making the policy less susceptible to noisy inputs. POR’s 'ensembling' approach trusts the consensus of top-ranked actions, inherently filtering out outlier noise, including the severe ranking errors we introduced. The synergy between these two components is what allows NaDRO to handle such a challenging noise profile, justifying its promise as a pathway for real-world applications.\n\n> **Q5:  The paper adopts fixed thresholds (1.15 and 0.8) for labeling high and low cost in CPR annotation, but it’s unclear how these specific values were determined.**\n\nThank you for this excellent question regarding the specific values used in our CPR annotation. We agree that the choice of any fixed threshold warrants justification. Our response is twofold: first, we will explain the design philosophy behind these thresholds, and second, we will provide empirical evidence of their robustness.\n\n**1. Design Philosophy: Correcting Uncalibrated LLM Perception**\n\nThe core goal of CPR is to instill human-like **qualitative judgment** into the model. A challenge with any qualitative label (e.g., \"large\" vs. \"small\") is that its boundaries are inherently fuzzy. For example, we can definitively say a 10-node TSP is \"small\" and a 10,000-node TSP is \"large,\" but the exact dividing line is ambiguous.\n\nCritically, we observed that LLMs often have a skewed or **uncalibrated perception** of scale, sometimes viewing a 50-node problem as an immense task. The CPR thresholds are not intended to represent a universal \"truth,\" but rather to provide a clear, corrective signal to anchor the model's flawed intuition. By defining clear zones for \"High Cost\" (>1.15x greedy) and \"Low Cost\" (<0.8x greedy), we create an unambiguous \"Normal\" zone in between. This three-zone approach helps the model build a more reasonable, human-aligned understanding of its performance state.\n\n**2. Empirical Robustness of Thresholds**\n\nTo ensure our method is not sensitive to these specific values, we conducted experiments with different threshold pairs as (2.0, 0.8) and (1.15, 0.5). Our key finding was that there was **no significant difference in the final performance or the training dynamics** when using these alternative thresholds. This demonstrates that the model is **robust to the specific choice of these values** within a reasonable range. The crucial factor for the model's learning is the existence of these distinct qualitative regions, not the precise numerical boundaries, which validates our design choice.\n\n> **Q6:  What is the advantage of LLM-based methods in such tasks and when would such method be preferable to strong classical solvers?**\n\nThank you for this crucial question. You are correct that our method does not outperform a highly specialized solver like LKH. However, we would like to clarify that the primary goal of our research is not to create a new state-of-the-art solver for a mature and well-defined problem like TSP.\n\nInstead, we use TSP as a representative benchmark to explore a much broader, forward-looking question: **how can Large Language Models be leveraged as general-purpose agents for a wide array of complex sequential decision-making tasks?** We believe this is an inevitable and important future direction for AI.\n\nThe key distinction and practical relevance lie in the underlying paradigms:\n* **Classical Solvers (e.g., LKH):** These are highly optimized, specialized algorithms designed for a single domain. They are powerful but inflexible and cannot be easily adapted to other problems.\n* **Our LLM-based Framework:** We propose a general framework that can be **easily adapted to various decision-making tasks**. The LLM learns a high-level, adaptive strategy. As demonstrated in our paper, the same NaDRO framework excels on **both TSP and the more complex CVRP**, showcasing its versatility. \n\nOur work should be viewed not as an attempt to beat a specific classical solver on its home turf, but as a crucial step towards a new paradigm of **general, adaptable AI decision-makers** capable of tackling a diverse portfolio of complex challenges."}]

Author rebuttal:

Meta-review: This paper introduces Noise-Aware Dual-Reward Optimization (NaDRO) to train LLMs with noisy training data. The core technique involves decomposing the reward signal into a Preference-based Outcome Reward (POR) and a Context Perception Reward (CPR). Experiments show that models like Qwen-7B and Llama 3-8B, when trained with NaDRO, can outperform significantly larger models on complex tasks such as the TSP and vehicle routing problems.

Reviewers found the dual-reward concept to be reasonable and intuitive, although the initial submission lacked sufficient motivation. The authors addressed most concerns during the rebuttal by providing additional experiments that verified the impact of CPR, analyzed hyperparameter sensitivity, and included a comparison using Llama 3-8B, which satisfied the reviewers.

A single minor concern remains regarding the paper's explanation of how NaDRO reduces variance, which currently relies on a very simplistic example. The paper would be further strengthened if the authors could expand on this point. Overall, the consensus is positive, and the work is recommended for acceptance.
Decision: Accept (poster)