Research map / Optimization / Optimizers
Complexity Scaling Laws for Neural Models using Combinatorial Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Develops complexity scaling laws for neural TSP solvers (RL via PPO and SFT) that predict suboptimality as TSP node count and spatial dimensionality scale with fixed model capacity, and compares against 2-opt local search.
Problem
Neural scaling laws describe performance vs. parameters, compute, and data, but not vs. problem complexity; the paper asks how fixed-size model suboptimality scales with solution-space size (TSP nodes) and representation-space size (spatial dimensions).
Approach
Uses Euclidean TSP to decouple solution space (node count) from representation space (dimensionality), fits power/exponential scaling laws to suboptimality for RL- and SFT-trained Pointer-Network Transformers, and reverse-engineers the trends with 2-opt local search on the cost landscape.
Key results
- RL and SFT suboptimality power-decays with parameters and compute; SFT appears more compute-efficient than RL at the tested scales (single seed per size).
- Node scaling suboptimality grows superlinearly with fitted exponent alpha ~1.86 for RL and ~1.69 for SFT.
- Spatial dimension scaling for RL saturates with exponential decay toward a bounded asymptote; 2-opt local search reproduces similar trends.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Scale model parameters | RL on 2D 20-node TSP · 2D 20-node TSP | suboptimality: α=0.582 | Helped |
| Scale model parameters | SFT on 2D 20-node TSP · 2D 20-node TSP | suboptimality: α=0.712 | Helped |
| Scale compute on the compute-efficient frontier | RL on 2D 20-node TSP · 2D 20-node TSP | suboptimality: α=0.439 | Helped |
| Scale compute on the compute-efficient frontier | SFT on 2D 20-node TSP · 2D 20-node TSP | suboptimality: α=0.555 | Helped |
| Increase node count with fixed model capacity | RL and SFT · 2D TSP node scaling | suboptimality: RL α=1.86; SFT α=1.69 | Hurt |
| Increase spatial dimensions with fixed model capacity | RL, 10-node TSP · 10-node TSP spatial dimension scaling | suboptimality: β=5.33 × 10^{-2} | Hurt |
| Increase spatial dimensions with fixed model capacity | RL, 20-node TSP · 20-node TSP spatial dimension scaling | suboptimality: β=0.209 | Hurt |
| Use SFT instead of RL | Fixed-size models on TSP · TSP compute scaling | compute efficiency: RL α=0.439; SFT α=0.555 | Helped |
| Use exponential decay rather than power decay to fit dimension scaling | RL complexity scaling · 10-node and 20-node TSP spatial dimension scaling | fit predictiveness: 10-node power-decay β_α ≈ 0.31; 20-node power-decay β_α ≈ 0.25; exponential-decay β values: 5.33 × 10^{-2}, 0.209 | Helped |
| Constrain 2-opt search depth | 2-opt local search · 2D TSP node scaling | suboptimality trend: M=25: α=2.09; M=20: α=1.82; M=15: α=1.67; M=10: α=1.49; M=5: α=1.27 | Helped |
| Extend 2-opt dimension scaling to 100 dimensions | 2-opt local search · TSP spatial dimension scaling | suboptimality trend: 10-node β=5.70 × 10^{-2}; 20-node β=0.254 | Helped |
Surprising findings
- Extrapolated node scaling fits imply model suboptimality would eventually exceed random-tour performance, a contradiction the authors attribute to eventual trend breakdown.
- SFT NLL loss decreases with node scale even as suboptimality grows.
Limitations
- Single seed per scale, so statistical significance of RL vs SFT differences cannot be determined.
- Study focuses on a single problem (Euclidean TSP), which is easier than most NP-hard problems.
- Infinite-compute performance can only be estimated; larger scales were not feasible with modest resources.
Experimental setup
Datasets: Concorde-solved 2D TSP instances (PyConcorde) local-search approximated higher-dimensional TSP solutions
Benchmarks: Concorde optimal TSP solutions (2D) local-search approximated higher-dimensional TSP
Metrics: suboptimality gap (mean model tour length minus mean optimal scaling law fit exponents
Baselines: 2-opt local search Concorde random tour
Builds on: Kaplan neural scaling laws Pointer Networks Proximal Policy Optimization Concorde TSP solver Hex scaling laws (Jones)
Closest papers by meaning
- 4+3 Phases of Compute-Optimal Neural Scaling Laws (NeurIPS 2024 · similarity 0.89)
- A Dynamical Model of Neural Scaling Laws (ICML 2024 · similarity 0.89)
- Probing Neural Combinatorial Optimization Models (NeurIPS 2025 · similarity 0.87)
- Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks (NeurIPS 2026 · similarity 0.87)
- Topological Generalization Bounds for Discrete-Time Stochastic Optimization Algorithms (NeurIPS 2024 · similarity 0.87)
- No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Paths (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.