Scaling Autoregressive Models for Neural Combinatorial Optimization

Autoregressive (AR) models have long served as a flexible and general paradigm for neural combinatorial optimization (NCO), naturally constructing feasible solutions through sequential decisions. However, scaling AR solvers to larger instances remains challenging, especially under Reinforcement Learning (RL), where long horizons, sparse rewards, and expensive decoding limit both efficiency and performance. We argue that this limitation is not inherent to autoregression, but arises because existing AR designs do not jointly support expressive decision modeling, efficient incremental decoding, and stable long-horizon training. We propose PrefixCO, a prefix-autoregressive paradigm for scaling AR models for routing-style NCO. PrefixCO encodes problem instance attributes into reusable prefix representations and causally generates solutions with cached key-value states, computing static instance information once while allowing each step to condition on the evolving partial solution. This preserves AR flexibility and reduces the average per-step decoding complexity to $O(N)$ from $O(N^2)$. PrefixCO further adopts a cache-compatible pointer decoder that matches prefix-derived candidate-node keys with a trajectory-conditioned query, producing a step-specific distribution over feasible next nodes while preserving incremental decoding efficiency. For training, PrefixCO introduces a scalable RL protocol that combines imitation warm-starting with non-negative improvement-based reward shaping. Experiments on TSP and CVRP show that PrefixCO establishes a strong quality-efficiency trade-off: under RL, it reduces the optimality gap on 1000-node TSP by 30$\times$ over prior AR baselines and achieves a 2$\times$ reduction on CVRP.