精读笔记

Problem Setting

这篇论文真正解决的不是 TSP/CVRP 的建模问题，而是 NCO 中 autoregressive policy 的训练信号组织问题。AM/POMO 这条路线长期依赖 policy-gradient + baseline：policy 负责产生解，baseline 负责给出可减方差的参照。困难点在于 routing 问题的 cost landscape 很稀疏、trajectory 很长、return 是 episode-level 的，梯度估计天然高方差；一旦 baseline 质量不足，advantage 不只是 noisy，而是可能系统性误导更新。

以前方法卡住的地方是 baseline 的外部性和滞后性。rollout baseline 看起来只是 variance reduction，但在 NCO 里它来自同一个策略家族的 greedy 解；当问题变难时，greedy baseline 本身会随策略退化而退化，形成闭环。POMO 通过多起点和 shared baseline 缓解这个问题，但仍然依赖多解对称性和 baseline 机制。论文的关键矛盾可以概括为：训练需要稳定参照，但在难实例上参照本身由不稳定策略生成。

Motivation

作者的动机不是“GRPO 在 LLM 里有效所以试一下”，而是指出 NCO 里的 baseline 依赖有结构性风险。TSP-50 上所有方法都能收敛，不足以暴露问题；TSP-100 中 REINFORCE warmup 后 collapse，提供了一个很直接的反例：baseline 不是无害组件，它可能决定训练是否进入坏反馈环。

关键缺口是 NCO 缺少 baseline-free 但仍能低方差训练的机制。critic 路线需要从图状态预测总 tour cost，随着规模变大也困难；rollout baseline 需要维护 frozen policy，并且依赖 greedy 解的参照质量。GRPO 的吸引力在于它把“参照”局部化到同一实例内的一组样本，不需要跨 epoch、跨策略版本或额外 value model。

Core Idea

核心思想是把 advantage 的定义从 external baseline 改成 intra-instance relative ranking。对于同一个 routing instance，采样多条 tour/route，把它们的 return 做组内标准化；一个 trajectory 是否得到正 advantage，不取决于它绝对有多好，也不取决于某个 frozen greedy policy，而取决于它在同一实例、同一采样分布下是否优于组均值。

这个变化引入的 inductive bias 很明确：NCO 训练不必学习全局 cost 尺度，也不必信任一个外部 baseline；只要同一实例下采样分布能产生足够多样性，局部相对比较就能提供方向性信号。它重新组织了信息流：从“policy vs baseline policy”的跨时间比较，变为“trajectory vs sibling trajectories”的同步比较。直觉上这更 scalable，因为 instance size 或 cost scale 变化时，z-score advantage 自动做尺度归一；但它的代价是需要多采样和足够 exploration。

Method

方法层面最关键的是三件事。

第一，GRPO 的 group-relative normalization 解决的是外部 baseline 不可靠的问题。每个实例采样 G 条轨迹，用组内均值和方差构造 advantage。核心变化不是公式本身，而是 baseline 从一个可能陈旧/退化的 greedy policy 变成了当前采样分布的局部统计量。这使训练信号对绝对 cost scale 不敏感。

第二，PPO clipping 和 inner-loop reuse 解决的是相对比较信号的利用率问题。采样 routing trajectory 成本不低，GRPO 存储一批 trajectory 后做多次更新，因此每个实例提取更多梯度信号。但这也是实验归因中最容易混淆的部分：它提升的是 per-instance sample efficiency，不一定提升 per-gradient efficiency。

第三，temperature annealing 是 group 方法能工作的前提，而不是可有可无的 trick。若策略过早接近 deterministic，同组 trajectory 可能相同或 cost 差异极小，advantage 退化。高温初期采样保证组内排序信号存在，后期降温则让训练分布接近 greedy evaluation。这里的探索设计很可能贡献了不少收益，文中没有充分隔离其影响。

P3O 可以看成 GRPO 的 pairwise 极简版本：只比较两条轨迹，用 reward difference 更新 log-prob ratio。它也 baseline-free，但 pairwise 信号方差更大，尤其在 CVRP 这种约束导致可行解结构更复杂的任务上更不稳。

Key Insight / Why It Works

最重要的 insight 是：在 NCO 中，baseline 的作用不只是减方差，它还定义了 credit assignment 的参照系；当参照系由一个不成熟 greedy policy 给出时，训练可能比无 baseline 更糟。GRPO 有效的根本原因是把参照系局部化和同步化，避免了 frozen rollout baseline 的跨时间耦合。

更具体地说，GRPO 的有效性来自四个机制叠加。第一，组内标准化消除了实例间 cost scale 差异，这对 TSP-50/100、CVRP-50/100 这种规模变化尤其重要。第二，相对排序比绝对 reward 更鲁棒：即使所有解都很差，也仍然能识别“相对不那么差”的解。第三，多轨迹采样提供了局部 exploration distribution，训练目标更像在当前 policy 的邻域内做 preference learning。第四，inner-loop reuse 把每批实例榨出更多更新，这提高了 sample efficiency，但不是纯算法优势。

我认为论文真正的贡献不是“GRPO 比 POMO 强”，因为 gradient-matched 后它没有超过 POMO；真正贡献是证明 baseline-free relative policy optimization 在 NCO 中可行，并且能绕开 rollout baseline 的特定 failure mode。POMO 仍然是更好的 per-update 方法，说明多起点对称性利用是很强的 inductive bias。GRPO 的优势更像 stability + instance efficiency，而不是 optimization efficiency。

哪些可能只是 engineering / scaling：epoch-matched 表中的 GRPO 最优基本不能算核心证据，因为更新次数多很多；temperature annealing 也可能贡献了早期探索收益；FP16、batch、fresh instance generation、checkpoint selection 等都不是核心。增益来源不清的部分是：到底多少来自 baseline-free，多少来自高温多采样，多少来自 8x update reuse，文中没有做足够消融。

这不是 retrieval，也不是 test-time compute；更接近 better inductive bias + memory/sample reuse。所谓“更 generalizable”目前证据不足，它只是对 reward scale 和 baseline failure 更鲁棒，并未证明跨分布泛化。

Relation To Prior Work

最接近的 prior 是 AM 的 rollout-baseline REINFORCE、POMO 的多起点 baseline、PPO/critic 路线，以及 LLM alignment 中的 GRPO/P3O。论文的实质不是发明新优化器，而是把 alignment 中的相对偏好/组内归一化训练范式迁移到 NCO，并把它解释为 baseline-free advantage estimation。

和 AM 的本质差异：AM 依赖 frozen greedy rollout 作为外部参照，GRPO 用当前组内样本的统计量作为内部参照。和 POMO 的差异：POMO 利用 routing 问题的 multiple optima / start symmetry，仍是 baseline-dependent；GRPO 不需要这种对称结构，但需要采样多样性。和 PPO-critic 的差异：GRPO 不学 value function，避免了“从初始图预测整条 route cost”的 critic 难题。

看似新的地方其实是已有思想重组：relative reward、z-score normalization、PPO clipping、多次 epoch reuse 都不是新组件。实质创新在于问题定位：把 rollout baseline 的脆弱性明确作为 NCO scaling bottleneck，并给出 alignment-style relative optimization 作为替代训练参照系。

Dataset / Evaluation

评估覆盖了标准 synthetic TSP/CVRP，规模到 100 节点，使用统一 AM 架构和 RL4CO，实现上比较干净。它足以支持一个有限 claim：在这些标准 routing benchmark 和该训练配置下，GRPO 是一个可行的 baseline-free 替代，并能避免 TSP-100 上 REINFORCE 的 collapse。

但 evaluation 不能支持更强 claim。首先任务范围很窄，没有 TSP-200+、更复杂 VRP 变体、时间窗、pickup-delivery、非均匀分布或真实物流数据。其次只有两个 seed，collapse 现象虽然明显，但统计说服力有限。第三，所有 inference 都是 greedy decoding；如果加入 sampling/beam/search，算法排序可能变化。第四，GRPO/P3O 使用温度退火而 REINFORCE/POMO 不使用，这是明显 confound，虽然不一定解释 REINFORCE collapse。

gradient-update matched 是论文里最有价值的评估设计，因为它揭穿了 epoch-matched 的表面优势：GRPO 并非每步更强，只是每 epoch 更新更多。另一方面，sample-efficiency 的比较也不完全公平，因为 POMO 800 epoch 看到更多 unique instances，而 GRPO 通过 inner-loop reuse 看到更少实例但更多更新。论文比较了两种轴，但仍未彻底拆解 compute、data、sampling diversity 三者贡献。

Limitation

方法成立依赖一个强前提：同一实例下的 G 条采样 trajectory 必须有足够 diversity，且 return 方差能反映有意义的局部优劣。如果策略过于确定、问题过于容易、或采样温度不足，组内标准差接近零，GRPO 的 advantage 会退化。反过来，如果温度过高，组内比较可能主要比较随机噪声，而非可学习结构。

scalability 上限也不清楚。随着节点数增大，随机采样 trajectory 的质量分布可能整体变差，组内相对最优并不一定指向全局有用方向；G=4 在 TSP-100 可用，不代表 TSP-500 或强约束 VRP 可用。若要增加 G，则计算和显存成本上升，baseline-free 的代价变成 sampling-heavy。

泛化没有被真正验证。训练和测试都是同分布 synthetic uniform instances，不能排除方法主要受益于标准 benchmark 的平滑分布和大量 on-the-fly 数据覆盖。这里没有 hidden supervision 或 benchmark leakage 的明显证据，但也没有证明真实 deployment 下的 robustness。

REINFORCE failure 的归因还不够严谨。作者把它解释为 rollout baseline 的结构性缺陷，但文中未充分说明是否尝试了更长 warmup、更慢 baseline update、不同 learning rate、temperature sampling、baseline reset 或 stronger rollout policy。这个 failure mode 很有价值，但目前更像“RL4CO 默认配置下的结构性脆弱性”，不应直接外推为所有 rollout baseline 都会在 TSP-100 崩溃。

最后，GRPO 可能只是把 baseline 问题转移成 exploration/diversity 问题。它不需要外部 baseline，但需要 group 内部有可比较的多样本；这个条件在训练后期和更大规模问题上未必自然成立。

Takeaway

• 1. NCO 中 baseline 不是中性工程细节，而是训练参照系；当参照系由弱 greedy policy 产生时，可能成为 scaling bottleneck。
• 2. Group-relative advantage 是一个值得迁移的机制：对同一实例采样多个候选，用局部相对质量训练 policy。
• 这种思想可用于更广泛的 CO、程序生成、规划任务，尤其是绝对 reward 尺度不稳定或 critic 难学的场景。
• 3. GRPO 的定位应是 baseline-free stability method，而不是 POMO replacement。

一句话总结

这篇论文把 LLM alignment 的组内相对优化引入 NCO，核心贡献不是刷新 routing 性能，而是指出并绕开 rollout-baseline 训练在难实例上的脆弱参照系，属于从 baseline-dependent policy gradient 向 relative, baseline-free optimization 演化的一步。