Complexity Scaling Laws for Neural Models using Combinatorial Optimization
Authors: Lowell Weissman
Michael Krumdick
A. Lynn Abbott
Venue: NeurIPS 2025 poster ()
Keywords: scaling laws
problem complexity
traveling salesman problem
Primary area: deep_learning
TL;DR: Neural scaling laws fix the problem and scale the model/compute/data, we fix the model and scale the problem.

Abstract: Recent work on neural scaling laws demonstrates that model performance scales predictably with compute budget, model size, and dataset size. In this work, we develop scaling laws based on problem complexity. We analyze two fundamental complexity measures: solution space size and representation space size. Using the Traveling Salesman Problem (TSP) as a case study, we show that combinatorial optimization promotes smooth cost trends, and therefore meaningful scaling laws can be obtained even in the absence of an interpretable loss. We then show that suboptimality grows predictably for fixed-size models when scaling the number of TSP nodes or spatial dimensions, independent of whether the model was trained with reinforcement learning or supervised fine-tuning on a static dataset. We conclude with an analogy to problem complexity scaling in local search, showing that a much simpler gradient descent of the cost landscape produces similar trends.

Complexity Scaling Laws for Neural Models using Combinatorial Optimization
Lowell Weissman' Virginia Tech
Michael Krumdick
A. Lynn Abbott Virginia Tech
Kensho Technologies
Abstract
Recent work on neural scaling laws demonstrates that model performance scales predictably with compute budget, model size, and dataset size. In this work, we develop scaling laws based on problem complexity. We analyze two fundamental complexity measures: solution space size and representation space size. Using the Traveling Salesman Problem (TSP) as a case study, we show that combinatorial optimization promotes smooth cost trends, and therefore meaningful scaling laws can be obtained even in the absence of an interpretable loss. We then show that suboptimality grows predictably for fixed-size models when scaling the number of TSP nodes or spatial dimensions, independent of whether the model was trained with reinforcement learning or supervised fine-tuning on static dataset. We conclude with an analogy to problem complexity scaling in local search, showing that a much simpler gradient descent the cost landscape produces similar trends
Introduction
Neural network performance usually improves with more parameters, more training, and more data. While small increases in budget improve performance unpredictably, model performance becomes highly predictable scale, often with surprisingly simple trends [2 Such trends have been called neural scaling laws B 4) where performance smoothly improves when scaling model size, dataset size, compute budget. This principle is summarized elegantly [3] by analogy the ideal gas law, which describes the macroscopic behavior of a gas independent of its microscopic dynamics.
8 9. This observation implies the existence of general underlying order, one that persists across the diverse natures of various tasks. Neural scaling laws capture slices of this behavior, fixing variables of the problem so that their influence absorbed within the constants of a specific trend.
Neural scaling laws emerge over a wide variety of problems and problem scales 4 5
In this paper, we hypothesize that model performance is similarly predictable when scaling funda- mental measures of problem complexity. We directly isolate this relationship and scale problem complexity for parameter-consttee compute and data are unconstrained. We take an initial step toward predicting the limit performance as function of the deep learning algorithm, the capacity of the model, and the properties of the task.
fixed-size models while approximating the regime in which
If study measures of complexity that are task-specific, it will be difficult draw meaningful conclusions that are general in nature, even if smooth scaling laws emerge. For example, Jones [10] extends compute scaling laws also be function of Hex board size. Measures like game-tree complexity and state-space complexity are well-studied for Hex (IT) but have complicated rela- tionships with board size [12] and are primarily applicable sequential games. We approach this issue by distilling two fundamental measures of problem complexity inherent in any deep learning
Bradlcy Department of Electrical and Computer Engincering, Correspondence to: <lowel16 Nowell@@v.eedur Project code, along with new datasct of 128 million optimal TSP solutions, is provided at: https://github com wotp://oollll//ooooooooo cotplexipeeiiccccccccoocmmcl ty scal seaaiing-las laws
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Reinforcement learning (RL)
Supervised fine-tuning (SFT)
SFT
Suboptimality
10
Appogtimaan gap
5.38
Parameterrs (N)
10-1
127x10
2.41
2.68
Parameters
frontier
trend break
frontier
Parameters (N)
a (Cmin)
s (Cmin) (-.55)-055
6.88 101
1044
10-3
10-1
10-4
Compute (PF-days)
Compute (PF-days)
Language
SFT
Image 32x32
(Hennihhan et al.)
10-
AL Procgen (Hilton et al.)
Compute (PF-days)
Figure 1: Suboptimality gap, defined as the difference between mean model performance and mean optimal performance, smoothly power decays with respect model size and compute for both reinforcement learning (RL) and supervised fine-tuning (SFT) in TSP. Fits suggest that SFT is more compute-efiiee efficient than RL, and possibly more crrammter--fffcieee as we scale larger models, with faster decay toward optimal performance (larger a.). Top left: Suboptimality w.r.t. parameters (N) for models evaluated near convergence. Right: Suboptimality w.r.t compute (C) evaluated throughout training, where the compute-efficient frontier power decays. Note that the compute axis for SFT has been stretched for easier viewing. Bottom left: Optimal model size follows power growth w.r.t. compute budget. This relationship is strikingly consistent between domains 4 14
task: size of the solution space and size of the representation space. Isolating each measure to single variable is often not feasible in prevalent domains such as generative modeling and vision. We leverage combinatorial optimization toward this goal, using the Traveling Salesman Problem (TSP) to decouple the solution space and representation space, scaling TSP nodes or spatial dimensions independently. We then examine the limit of model performance when confronting the combinatorial growth of the solution space along with the curse of dimensionality.
Contributions: We obtain model size and compute budget scaling laws for TSP that predict model suboptimality, allowing us make direct comparisons between reinforcement learning (RL) and supervised fine-tuning (SFT) on the same task (Section 3 Figure IT. We then obtain smooth problem complexity scaling laws characterized by simple trends for parameter-constraiee (Section 4.. However, we show that these trends must break down at very large TSP node scales, reaffirming
models
3 that simple scaling behavior can become more nuanced beyond the scales studied. Informed by comparisons to local search, we provide potential explanations for our parameter- constrained complexity scaling laws (Section 5). Finally, we provide our newly created dataset of 128 million TSP solutions.
Experimental setup
2.1 Data design
All experiments were performed using the Symmetric Euclidean Traveling Salesman Problem. One problem instance consists of IRd coordinates uniformly sampled between [0, for each of the d dimensions (illustrated in Figure 2}. TSP's ((n!) combinatorial solution space is defined as all closed loops that visit each node exactly once. Such loops are called tours, and the objective is to find the minimum-length tour. In combinatorial optimization language, tour length is referred to as cost (or fitness when maximizing). and the cost surface w.r.t. the solution space referred to as the cost landscape.

---

1.0
0.2
0.0
1.0
6.8
0.2
0.4
0.0 0.4
0.0
0.6
6.0
0.2
X1 1.4
0.6
0.8
0.0
02
0.4
3.6
0.8
1.0
1.00.0
Node
Model tour
Optimal tour
Figure 2: TSP has two convenient ways to adjust problem complexity: node count and spatial dimensionality. Left: 2D TSP instance with nodes and trivial 12 solutions. The solution tour sampled from a trained RL model is the optimal, minimum-lengtt tour. Center: 2D TSP instance with 40 nodes and roughly 1046 solutions. The RL model tour is slightly suboptimal, 0.08 units longer than the optimal tour. Right: 3D TSP instance with 10 nodes, where brightness illustrates increased depth. Adding spatial dimensions does not modify the number of solutions but makes problem representation more complex. This RI model solution is 0.05 units suboptimal.
2.2 Optimal tour generation
We leverage optimal solutions for model evaluation and supervised model training. For two- dimensional TSP, we use PyConcorde [15]. Python wrapper for the Concorde TSP solver [16] 17]. We generate optimal solutions 128 million TSP problems, 12.8 million for each node scale we study, and share this dataset for academic use. We were unable to identify a pre-existing dataset of adequate size for supervised learning.
For our evaluations on higher-dimensionn TSP, we closely approximate optimality with local search. We discuss method and how validated the resulting datasets in Appendix E Although not exact, performance estimates derived from these datasets are statistically indistinguishable from their Concorde counterparts two dimensions. We produce 128,000 of these solutions for each 10-node dimension scale we study, and 64,000 solutions for each 20-node dimension scale.
2.3
Model training
We train models separately using both reinforcement learning (RL) and supervised fine-tuning (SFT). Our models output tour sequences autoregressively, producing policy distribution over each unvisited node Pointer Network head [18], adding an encoding of the sampled visitation its Transformer decoder memory [9] and repeating until all nodes are visited. Details our model architecture are provided in Appendix G along with a brief comparison alternative approaches. Hyperparameter
choices are detailed separately in Appendix H
Reinforcement learning:
We formalize the RL environment as a bandit problem where return the negative length of a solution tour. We use Proximal Policy Optimization (PPO) 20), training for one million gradient updates with hyperparameter optimization (HPO) informed learning rate decay.
Supervised fine-tuning: For SFT models, we minimize negative log- likelihood (NLL) loss between model edge selections and optimal edge selections with teacher forcing. We train for epoch over the optimal solution dataset generated for the corresponding problem scale One epoch translates to roughly 73,000 gradient updates with faster learning rate decay than that used for RL experiments.
2.4 Suboptimality estimation
We measure model performance in mean suboptimal tour length, 8 [Amodel Popt, where Pmmdee mean model tour length and Hopt mean optimal tour length. We refer to this regret-based metric as the suboptimality gap, or simply suboptimality. For neural scaling laws, raw tour length trends and
Multiple epochs of training is distinct scaling regime where data is also bottlenecked (Eq. 1.5 in B).

---

suboptimality trends both describe the same relationship since Hope remains constant. For problem complexity scaling Popt. varies, so measuring suboptimality extracts the underlying model behavior.
Parameter and node scaling evaluations use the first 1.28 million problems of their correspond- ing Concorde-solved datasets. Compute scaling evaluations, performed throughout training every 4000 updates, use the first 12,800 problems. Spatial dimension scaling evaluations use their full approximate dataset for each scale. We sample one model tour for each optimal tour.
2.5 Scaling experiments
For parameter and compute scaling laws, study two-dimensional 20-node TSP. We train at 12 model sizes, scaling model width to achieve geometric progression between roughly 60,000 and million parameters. Previous work suggests that neural scaling is relatively insensitive to Transformer width/depth aspect ratio over several orders of magnitude [3]. We would expect similar results if, for instance, the number of layers were scaled instead, provided models are still trained sufficiently near convergence. However, for some tasks such as neural machine translation, proportionality of encoder and decoder blocks must also be considered (2T).
Neural scaling:
Problem complexity scaling: For TSP node and spatial dimension scaling laws, we fix model width thereby fixing model capacity we scale problem complexity. For node scaling, we train one RL and one SFT model per node scale. We study ten scales, n E (5, 10,
50}- Sym-
metric TSP has 1/2 (n 1)! possible tours for n 3, these scales range from 12 solutions up to approximately x 1002_ and forgo SFT training given the scarcity of optimal data detailed in Section 2.2] We study d E 32, .... 12, 15, 20, 30, 40, 50, 100} over two node scales E {10, 20), which allows us to bet- ter interpret otherwise ambiguous trends.
1 For spatial dimension scaling, we train one RI. model per scale
Fitting scaling laws: Figures D and 3 show experiments that converge to trend. These results are the inputs for scaling law regression fits. We discuss experiments that failed to converge in Appendix B Critically, all trailing could not hypothesize that trend alignment is achievable with further training
experiments are more suboptimal than predicted. If any were
less suboptimal, and further model improvement. Note that RI. converges to trend at larger scales than SFT since the former is not constrained by the amount of available optimal data.
Compute requirements: Our 50-node RL experiment is the most computationally expensive. trained for 24 V100-days and consumed roughly 3 x 10 PF-days of compute. Including preliminary experiments and HPO, training required several months. Further details are provided in Appendix
3 Neural scaling laws for combinatorial optimization
Figure I shows that model suboptimality smoothly power decays w.r.t. parameters compute, for both RL and SFT with the chosen settings. At the scales tested, SFT more compute efficient than RL (at the expense of node-level supervision), but both exhibit similar parameter efficiency. Note that SFT's parameter-sculle scaling fit may slightly underestimate the true infinite- infinite-compute decay exponent. For the larger models shown in SFT's compute--fficient frontier, learning rate decay forces convergence before suboptimality visibly deviates from the frontier. Hence, further training may yield small improvements for these models, increasing SFT's parameter-scaling exponent and further differentiating it from RL's. This suggests SFT will surpass RL in parameter efficiency with larger models. However, with only one seed per model size, we cannot determine statistical significance.
Figure [ also shows that optimal model size can be expressed as function of compute budget by extracting each model's 's contribution to the compute-efficient frontier. This scaling law is very consistent between domains such as generative modeling B. [3] and reinforcement learning [ [4]. Growth rate exponents are usually around 0.5 to 0.75, and our TSP results closely align with these values. However, the degree of overlap between adjacent model sizes produces non- trivial imprecision, especially for SFT, extrapolation would be imprecise. We can infer that RL and SFT are compute efficient at similar model sizes for the tested range and TSP problem scale.
FFrom ne permutations, starting node insensitivity yields equivalent tours permutation and tour reversal insensitivity yields 2 equivalent tours per permutation (dividing by and 2, respectively).

---

RL
0.05
SFT
0.20
B pnn
5 a
y)2
Suboptimality gap
Suboptimality gap
RL (n 10)
0.15
RL (n 20)
0.03
$ x (d y)
0.10
B d
0.02
B 4
pv.n= 10
0.00
0.00
5
15
20
25
35
40
45
3
10 12
Nodes (n)
Spatial dimensions (d)
Figure 3: Suboptimality over problem scaling for models near convergence with a fixed number of non-embedding parameters. Left: Suboptimality follows superlinear power growth w.r.t. nodes, though we expect this trend eventually to break down before intersecting the near- random performance ceiling (Figure 4). Right: Suboptimality smoothly increases w.r.t. spatial dimensions, closely following negative exponential decay. Power growth (dashed), power decay (dash-dot), and exponential decay (solid) all predict the 10-node RI experiment (we show the latter). But power growth fails to find a convincing fit for its 20-node counterpart. Even random tour suboptimality is bounded d (Theorem (). so any netter-than-random monotonic trend must converge. But the power decay asymptote obtained for 10 nodes is larger than that for 20 nodes, which is nonsensical. Exponential decay is most predictive while maintaining sound By asymptote ordering, as shown.
broader implication of Figure Tis that TSP tour length a natural performance metric [4] For TSP, RL obtains smooth scaling laws directly for the return signal with high precision. For more complex environments with sequential dynamics, return-based RL scaling laws have considerable
variance and lose predictive power [9] 23 24)
Note that the RL compute-efficient frontier ignores the 168,000 parameter model, shown in lower opacity, which improves slightly faster than the trend otherwise predicts. We discuss this outlier in Appendix B We include scaling results for loss in Appendix Oppendix[aandd only summarize those findings here. First, loss variance can reveal a pattern of smooth power decay even when the corresponding mean has no trend. Second, PPO's mean critic loss predictably improves despite the absence of mean actor loss trend and the interdependence between the two learning objectives.
4 Complexity scaling laws at the infinite-compute limit
We now study problem complexity scaling for deep models with unbottlenecked compute and data, observing patterns in the limit performance under fixed model capacity. We find that predictable suboptimality trends emerge when scaling either the number of nodes the number of spatial dimensions, despite the stark contrast in how these measures influence the problem. Further, our node scaling result fosters useful critique of scaling law breakdown, and dimension scaling result characterizes the distinct nature of embedding parameters in complexity scaling laws. We again discuss corresponding loss trends in Appendix C Theorems introduced are proven in Appendix
4.1 Solution space scaling
The left plot in Figure shows suboptimality for RL and SFT models convergence scale the number of TSP nodes. Both experiments exhibit smooth power growth after including third fitted constant 7 node-scale offset E We find that growth rates for RL (a 1.86) and SFT
A sode-scale offset is required because zero-node TSP is ill-defined.

---

Mean tour length (cost)
25
random
ach. (n 10)
Suboptimality gap
random random SD
random 20)
achievable
random
20
optimal
15
random SD
15
10
10
5
20
35
50
2
35
50
12
50
100
Nodes (n)
Spatial dimensions (d)
Nodes (n)
Spatial dimensions (d)
Figure 4: Node and spatial dimension scaling have distinct effects on the achievable performance span, the suboptimality gap of random performance. Left: Mean optimal tour length closely follows sublinear power growth w.r.t. either problem scale. Mean random tour length grows linearly w.r.t.
nodes, and sublinearly w.r.t. dimensions rate similar to optimal tour length growth. Each sublinear trend approaches square root growth in the limit (a = 0.5; proof in Appendix II. Right: Suboptimality of random performance w.r.t. nodes is polynomial but approximately linear, being dominated by random tour length growth. Suboptimality of random performance w.r.t. dimensions produces a small, transient increase then decrease, but is provably constant in the limit (Theorem 6
(a x 1.69) are close for the tested model size, although their precise values are not necessarily meaningful. Power growth fits are sensitive to the suboptimalities obtained for the largest node scales, which require the most training to converge. If further training can produce small improvements at these scales, fit may overestimate the true infinite-compute a. Similar to parameter scaling fits in Figure M] SFT's node-scaling fit more likely to be pessimistic than RL's given the former's shortened training. However, extrapolating SFT's small advantage is less trustworthy here since SFT does not surpass RL by 30 nodes.
Even if we assume that a estimates are imprecise, the growth of suboptimality is clearly superlinear. This observation presents subtle contradiction. Figure44shove shows that the suboptimality of random tour length grows almost linearly with node scale. Indeed, this growth is provably O(n) as n + oc Thus, the obtained scaling laws imply model performance will eventually performance, and with enough scale, exceed even the maximum possible tour length (also (n))). Instead, we expect this superlinearity to break down before exceeding random performance, and we expect the obtained scaling laws to become pessimistic estimates at large node scales.
worse than random
Model suboptimality may be better expressed as a broken scaling law (26) given the strong fit quality over initial scaling and the subsequent need for an inflection point. However, this functional form would increase the number of fitted constants, and piecewise scaling is less useful unless we can also predict where trend breaks occur. Conveniently, extrapolating RL's more pessimistic fit, model suboptimality does not intersect random tour suboptimality until roughly 40,000 nodes, a scale with an unfathomably large solution space. Analogous contradictions with huge model sizes have been observed for neural scaling laws (e.g., Figure in (3), reinforcing the caveat that more intricate scaling behavior can appear simple over the scales studied.
4.2 Representation space scaling
The right plot in Figure shows suboptimality for RL models near convergence scale the number of TSP spatial dimensions. Both 10-node and 20-node experiments produce smooth bounded growth described by negative exponential decay toward fitted asymptote 3. We found that almost any regression model results a good fit the 10-node experiment since its growth is closer to being linear, but the 20-node experiment is more diseriminative. Unbounded power growth produces a markedly poor fit given the observed trend is visibly convergent. Power decay regression obtains smaller residuals but appears to converge slightly slower than the observed growth. Further, power decay fits produce a likely contradiction: the bound obtained for the 10-node experiment (3,, s 0.31) higher than that obtained for the more complex 20-node counterpart (3., 0.25). This implies that a lower suboptimality is achieved in the limit as + co by raising the baseline solution complexity,
'Lemma shows that expected random tour length grows linearly w.r.t while the Beardwood -oattoooo--Hoooo-- Halton- Hammersley Theorem 25 proves that optimal tour length is asymptotically proportional vn sc.

---

unless increased node scale fundamentally alters the form of scaling w.r.t. dimensions. In contrast, we find that exponential decay most predictive while maintaining sound asymptote ordering between 10- and 20-node experiments (the 3, values shown). Like a in node scaling fits, 3g.. is sensitive to the suboptimality values obtained at larger scales. Because higher-dimensional runs require more training to converge, &g estimates are likely imprecise, so the exact values shown may not be meaningful.
To explain the asymptotic nature of this scaling law, we again refer analysis. L*-norms such as Euclidean distance exhibit quite unintuitive behavior when scaling to higher dimensions [27] 28
29 30].
In expectation, both random tour length and optimal tour length diverge but at similar rates (Figure 4) so random tour suboptimality is roughly constant over the tested domain and is provably constant in the limit as d so (Theorem Several other properties of the cost landscape similarly converge as d + oo (Theorem [ and Appendix DD. For local search algorithms, these observations imply that TSP approaches a mostly (if not entirely) stationary problem complexity with one critical exception: the increasing computational complexity of evaluating scalar distances in higher dimensions. (However, the average number of distances that search evaluates converges.)
This increasing computational complexity is confined to the embedding layer for deep models. If we assume that arbitrarily large feature vectors can be embedded without producing learning bottleneck, then model performance converging to a better-than-randon
suboptimality becomes anticipated. This is a complementary view of pattern previously established in neural scaling: the separability of embedding parameters from model capacity [3] 14]. When embeddings are unbottlenecked
for a fixed problem, scaling non-embedding parameters studies the bottleneck of model capacity (parameter scaling laws). When scaling the problem, embeddings must also be scaled such that model capacity remains the only bottleneck (parameter-constraine complexity scaling laws).
5 Interpretable complexity scaling with local search
We now reverse engineer the complexity scaling laws introduced in Section 4 using local search, studying comparable trends produced with a white-box algorithm. These similarities do not directly imply that model inference and local search share underlying mechanisms. Instead, they provide potential topics to explore toward the development of formal theory for parameter-constrainee deep learning in future work. We evaluate local search using the same datasets discussed in Section 2.4 For each problem, we initialize search with random tour and then generate a locally optimum tour with the simple, well-studied 2-opt search move [11, performing gradient descent through the cost landscape. The landscape properties discussed at a high level below are detailed in Appendix() [D]
Figure Tigure shows the suboptimality of 2-opt solutions w.r.t. TSP node and spatial dimension scaling. For the latter, extending to 100 dimensions reveals a clearly convergent trend that aligns with the reasoning introduced in Section 4.2 If we only observe the lower-dimensional scales studied in Figure convergence is less obvious, as is for RL. We find that subexponential decay produces a better fit than pure exponential decay, though at the expense of another fitted constant ø. This form may also generalize better for deep models, although we observe no improvement when fitting subexponential decay to the RI. experiments in this paper.
Before trends converge, scaling spatial dimensions increases the density of local optima in the cost landscape. In expectation, search arrives at a local optimum faster, but one with increased suboptimality. This trend mirrors the result of parameter-constrrinedd models. 10-node experiments are especially similar, where 2-opt's 3 asymptote is nearly aligned with RL's at the tested model size. One potential explanation is that fixed model capacity limits model's ability to avoid poor local optima, matching the bottleneck observed with local search. For example, if models learn latent representation of a smoothed cost landscape (32), more model capacity may permit more advanced smoothing, making low cost optima casier to identify.
When scaling nodes, 2-opt's baseline behavior is less informative. We observe near-linear growth with an inflection point, an unclear relationship that deviates from the power growth observed for RL and SFT. One key distinction between dimension scaling and node scaling is the depth of search required to reach a local optimum. When scaling dimensions before trend convergence, the required search depth slightly decreases due to increased local optima density. In contrast, as n - co, the
"We also tested decays with the polys-polynomial form d' log d and the subexponential form w E (0, 1] but found extreme log base fits for the former and visual improvement from either form.
7

---

Z-opl 20-20
035
1.86)
200
0.0
2-opt (M
Zept (M
Seatc Seaach (M)
Suboptimality
0.20
525
5
15.0
20
0:15
2:0pt
n-
n 20
2-opt
trenend
0.29
0.35
10.0
15
7.5
2-opt Bn-10
0.19
0.05
2.5
0.00
0.00
10
20
30
40
50
100
5
20
15
20
35
50
Spatial dimensions (d)
Nodes (n)
Nodes (n)
Suboptimality gap
25
M
21.0/
8j--4
Max depth %
10
75
30
20
35
50
35
50
Nodes (n)
Nodes (n)
Nodes (n)
Nodes (n)
Nodes (n)
Figure 5: 2-opt local search suboptimality over problem complexity scaling. simpler gradient descent of the cost landscape can produce trends similar those of parameter-constrained deep models. Top left: 2-opt suboptimality w.r.t. spatial dimensions closely aligns with RI. trends. Pure exponential fit attempts decay slightly too fast, but obtain close fits with the subexponential generalization shown, where ø E (0, 1]. Top center: 2-opt suboptimality w.r.t. number of nodes. With unconstrained search depth, 2-opt produces an unclear trend with an inflection point. Top right: Contraining search depth (M) produces smooth superlinear growth. Bottom: Power growth emerges after saturating 100% early stopping. aligning with the scaling form of parameter-come constrrine- deep models (but these trends are not roughly equivalent, because proportionalities are quite different).
required search depth diverges to infinity. Attempting to align node scaling behavior, we constrain the maximum search depth (M). Doing causes suboptimality follow smooth superlinear power growth after search saturates at 100% early stopping (Figure ( top-right and bottom). Although Mcconstrained suboptimality much higher than model suboptimality, and expect breakdown of superlinearity (before exceeding random tour suboptimality) to occur more rapidly.
Despite these distinctions, the power growth form of M-constrained suboptimality may still help explain this form for
models. As the cost landscape grows, fixed-depth local search stops solutions that further from the attractor local optimum. inference similarly forced to approximate local optima under constrained model capacity? If so, what measure of solution proximity learned? We were able reproduce superlinear power growth with M-constrained 2-exchange search, which uses a different definition of solution adjacency (shown in Appendix D). Hence, this finding not overly sensitive the definition of solution proximity.
Related work
Neural scaling laws for loss: Neural scaling laws where cross-entropy loss smoothly improves with model size, dataset size, or compute budget were popularized by Kaplan et al.'s study of large language models (3), which also first demonstrated the separable nature of embedding parameters. Henighan et al. [4] generalize neural scaling laws to other autoregressive generative modeling domains, showing that optimal model size compute budget is remarkably consistent. Sorscher et al. 33 demonstrate that an exponential decay of test error w.r.t. data can be achieved using data pruning (instead of the typical power law scaling 3 5 ()). Analogously, Frantar al. [34] show that network sparsity influences scaling behavior. Supervised learning constitutes the majority of recent research neural scaling laws 3
36 37
Neural scaling laws for RL: Reward-based metrics for reinforcement learning models often do
not improve smoothly when scaling parameters, compute, or environment interactions [14. Notable exceptions include ground trouhd-truth reward in RL from human feedback (RLHF) 7 and Elo ratings in

---

two-player competitive zero-sum games such as Hex [T0] Connect Four and Pentago 8 (8). and to lesser extent in two-team competitive games like football [3] Hilton al. [4] address this challenge by introducing intrinsic performance, which maps the compute-efficient frontier to a linear relationship. Caballero al. [26] use broken neural scaling laws to predict more sophisticated return trends, like those observed in Procgen tasks [40]. We circumvent these challenges entirely because TSP natively exhibits smooth, pure power scaling of suboptimality w.r.t. parameters or compute.
Neural scaling law theory: Several theories have been proposed to explain the relationships between loss and parameters 41 between loss and data [42]
and for both in conjunction 43 44)
Most recently, Bordelon et al.' 's dynamical mean field theory 45 recovers phenomena from parameter,
data, and compute scaling. The Quantization Hypothesis 33
44 also explains emergent abilities [46]
by positing that there is an underlying discreteness to all abilities that deep models learn. However, Schaeffer et al. [47] show that emergent abilities often reflect the chosen performance metric rather than deep learning itself.
Problem complexity scaling laws: Jones 10
shows that the Elo score of a fixed-size Alp- haZero [88] model playing Hex can be predicted as a function of both compute budget and board size. The latter primarily grows the solution space similar to TSP node scaling, arguably making that work the closest to our own. However, our key contribution is studying the bottleneck of fixed model capacity, which Jones' method cannot address because achieves perfect play at each board size. More generally, when considering con-deep-learning algorithms applied to combinatorial optimization, the study of performance w.r.t. problem complexity goes back decades 49 Merz et al. [50) predict the performance of memetic algorithms on the Quadratic Assignment Problem (QAP) using cost landscape properties. (TSP is special case of QAP.) Ochoa et al. (51) predict local search performance on NK problems by introducing Local Optima Networks (LON) as a general model of cost landscapes. Tayarani et al. (52) broadly investigate local search trends for TSP, including several node scaling results for cost, some of which informed our methodology.
7 Discussion
Limitations:
Infinite-compun performance can only be estimated. With modest resources, we could not experiment on larger models and problem scales. This is especially important to consider when extrapolating node scaling trends, since they must eventually break down (possibly well before the contradiction detailed in Section 4.1. We are also limited in precision when comparing SFT and RI scaling law fits given that fewer SFT models converge to trend with one epoch of training, and we train only single seed per scale Nevertheless, the main limitation of this work is its focus single problem. Euclidean TSP is easier than most NP-hard problems, in part due to its cost metric satisfying the triangle incquality [49]. Euclidean TSP also admits polynomial-time approximation schemes (PTAS), allowing near-optimal tours to be computed in polynomial time with respect to the number of nodes [53]. These properties should be considered when hypothesizing how our findings generalize to other combinatorial optimization problems and beyond. Future work would need to demonstrate compelling generalization before complexity scaling laws can be substantiated general principle.
Beyond TSP scaling: Despite TSP's relative simplicity, there is some basis to be optimistic for parameter-constrainee complexity scaling laws in other tasks. The TSP cost landscape was once widely accepted to be approximately globally convex [54 (55. but more recent work has found this convexity to be increasingly coarse [56] 57 58). Even so, in expectation, smooth complexity scaling laws emerge. This macroscopic order despite microscopic disorder mirrors the nature of neural scaling laws and supports the hypothesis that complexity scaling laws can be obtained for less structured tasks. A natural next step would be studying ceeameter-constrainn complexity scaling with more elaborate Fuclidean combinatorial optimization problems where the solution space and the representation space remain independently scalable. Potential testheds include other routing problems like the Vehicle Routing Problem (VRP) [59]. the Orienteering Problem (OP) (60), and the Ring Star Problem (RSP) [61]. Given the similarity between the RL node scaling curve and its SFT counterpart (Figure leett, we especially encourage future study of algorithm insensitivity for parameter-coonstranne complexity scaling in other problems.
We provide leave-one-on fit statistics in Appendix A

---

Real-world domains: Identifying scalable yet precise measures of problem complexity is very challenging in domains like language modeling, vision, robotics, and so on. Solution complexity and representation complexity are often tightly coupled. For instance, in language modeling, vo- cabulary size affects both the number of token representations and the space of possible texts to generate. Discriminative NLP tasks like multiple choice question answering maintain separability of vocabulary size and number of classes, but at the expense of diminished relevance to generative modeling, Another challenge arises for real-world tasks where relevant performance metries do not smoothly improve, as often the case for sequential decision processes and tasks with discontinuous performance metrics. However, the latter has recently been addressed for language modeling with Token Edit Distance [47, an edit-space analogue to suboptimality.
Complexity scaling law theory: Without an underlying theory that explains parameter--onsttraned complexity scaling laws, we can only obtain a limited understanding of the conditions in which they apply and the types of problems they generalize to. Relating findings between domains will require significant speculation and extrapolations may be unreliable. Explaining each form of scaling is the most obvious gap. We are especially interested in whether model size predicts suboptimality growth rates like a and v), or 33 limits for spatial dimension scaling, and explaining the underlying nature if so. Extending Section 5] reverse engineer scaling laws with white-box machine learning model is one possible approach. Identifying and explaining counter-examples is another potentially useful approach. For example, if network sparsity were to influence parameter-constrr scaling laws (analogous to how sparsity influences neural scaling laws [34)), theory explaining this distinction may also address related open questions. Separately, another gap in our current understanding is what determines an embedding bottleneck. Widening the coordinate projection layer forever is probably insufficient to avoid an embedding bottleneck while dimension scaling. Extending the positional encoding sequence forever may be insufficient to avoid one while node scaling.
complexity
Practical implications: Deep methods that excel at solving TSP usually excel at solving sim- ilar routing problems like VRP and OP 62 63 64], both of which have well-studied practical variants [59 60 Practical use cases for parameter-constrane
complexity scaling laws are more challenging to identify given that training until convergence is usually inneftti-ieeficcient One use case would be predicting performance for applications mainly constrained by model size, such as edge applications requiring fast inference with limited hardware acceleration. Another potential use case is algorithm benchmarking, where we can estimate the limit of performance for several algorithms across range of problem complexities without training models on larger problem scales. Such benchmarks can also provide useful insights like sample efficiency tradeoffs with respect to problem complexity. Our single-seed node scaling results for RL and SFT demonstrate that SFT reaches intermediate suboptimality values faster at the scales evaluated (Figure X in Appendix B). Future work could use multiple-seed training to quantify this advantage with high statistical confidence.
Finite-compute complexity scaling: While this paper focuses on bottleneck from model capacity, could have instead chosen to limit compute budget or dataset size (with early stopping) and observe the patterns that emerge with increased problem complexity, if any. Compute-constraine and data-constrained complexity scaling laws would have many practical use cases. For example, Jones 10) shows that we can predict model performance as a bivariate function of train-time compute and test-time compute for a single Hex board size. If this neural scaling law can be generalized over problem scale, one could estimate for complex tasks the tradcoff between train-time and test-time compute using only cheap experiments.
Acknowledgments and Disclosure of Funding
We thank Charles Lovering for his feedback on delivery and clarity. We thank Joseph Weissman for reviewing portions of our proofs. This work was performed without third party support.
10

---

References
[1] Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically, arXiv preprint
2017.
[2] Jonathan $ Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. constructive prediction of the generalization error across scales. In International Conference on Learning Representations, 2020.
[3] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint urXiv:2001.08361 2020.
[4] Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun. Tom B Brown, Prafulla Dhariwal, Scott Gray, Chris Hallacy, Benjamin Mann, Alec Radford, Aditya Ramesh, Nick Ryder, Daniel M Ziegler, John Schulman, Dario Amodei, and Sam McCandlish. Scaling laws for autoregressive generative modeling. arXiv preprini arXiv:2010. 14701, 2020.
[5] Ibrahim M Alabdulmohsin, Behnam Neyshabur, and Xiaohua Zhai. Revisiting neural scaling laws in language and vision. Advances in Neural Information Processing Systems, 35:22300-
22312, 2022.
[6] Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transform- ers. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 22104-22115 2022.
[7] Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In International Conference on Machine Learning, pages 10835-10866. Proceedings of Machine Learning Research, 2023.
[8] Oren Neumann and Claudius Gros. Scaling laws for a multi aultii-geet reinforcement learning model. arXiv preprint arXiv:2200008849, 2022.
[9] Kuang-Huue Huei Lee, Ofir Nachum, Mengjiao Sherry Yang, Lisa Lee, Daniel Freeman, Sergio Guadarrama, Ian Fischer, Winnie Xu, Eric Jang, Henryk Michalewski, and Igor Mordatch. Multi-game decision transformers. Advances in Neural Information Processing Systems, 35: 27921-27936, 2022.
[10] Andy L Jones. Scaling scaling laws with board games, arXiv preprint arXiv:2104.03113 2021.
[11] H Jaap van den Herik, Jos WHM Uiterwijk, and Jack van Rijswijck. Games solved: Now and in the future. Artificial Intelligence, 134(1-2)277-311, 2002.
[12] Jack van Rijswijck. Computer Hex: Are bees better than fruitflies? MSc. thesis, U. Alberta, Edmonton, 2002.
[13] Jordan Hoffmann. Sebastian Borgcaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbi, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W Rae, Oriol Vinyals, and Laurent Sifre. Training compute-optimal large language models. Advances in Neural Information Processing Systems, 2022.
[14] Jacob Hilton, Jie Tang, and John Schulman. Scaling laws for single-agent reinforcement learning, arXiv preprint arXiv:2301.13444 2023.
[15] Joris Vankerschaver. PyConcorde. URL /ttpl//pppe/ggtabbb..oo//////rap
[16] David Applegate, Robert Bixby, William Cook, and Vasek Chvátal. On the solution of Traveling Salesman Problems. Documenta Mathematica, pages 645-656, 1998.
[17] William Cook. Concorde TSP solver.
URL. https: htte:://wwww //www//www////// math. www.uuatteoo..cataaaa...
html

---

[18] Oriol Vinyals. Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in Neural Information Processing Systems, 28, 2015.
[19] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
[20] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint /rXiv:/707.000 06347, 2017.
[21] Behrooz Ghorbani, Orhan Firat, Markus Freitag, Ankur Bapna, Maxim Krikun, Xavier Garcia, Ciprian Chelba, and Colin Cherry. Scaling laws for neural machine translation. International Conference on Leurning Representations, 2022.
[22] Jakob Bauer, Kate Baumli, Feryal Behbahani, Avishkar Bhoopchand, Nathalie Bradley-Schmieg Michael Chang, Natalie Clay, Adrian Collister. Vibhavari Dasagi, Lucy Gonzalez, Karol Gregor, Edward Hughes, Sheleem Kashem, Maria Loks- Toompsoooos,n, Hannah Openshaw, Jack Parker- Holder, Shreya Pathak, Nicolas Perez-Nieves, Nemanja Rakicevic, Tim Rocktäschel, Yannick Schroecker, Satinder Singh, Jakub Sygnowski, Karl Tuyls, Sarah York, Alexander Zacherl, and Lei M Zhang. Human-timescale adaptation in an open-ended task space. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 1887-1935, 23-29 Jul 2023.
[23] Sebastian Sartor and Neil Thompson. Neural scaling laws for embodied AI. arXiv preprint arXiv:2405. 14005, 2024.
[24] Jens Tuyls, Dhruv Madeka, Kari Torkkola, Dean Foster, Karthik Narasimhan, and Sham Kakade. Scaling laws for imitation learning in single-agent games. arXiv preprint arXiv:2307.09423 2023.
[25] Jillian Beardwood, John H Halton, and John Michael Hammersley. The shortest path through many points. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 55, pages 299-327. Cambridge University Press, 1959.
[26] Ethan Caballero, Kshitij Gupta, Irina Rish, and David Krueger. Broken neural scaling laws, In The Eleventh International Conference on Learning Representations. 2023.
[27] Charu C AAggarwal, Alexander Hinneburg, and Daniel A Keim. On the surprising behavior of distance metrics in high dimensional space. In International Conference on Database Theory, pages 420-434 Springer, 2001.
[28) Damien François, Vincent Wertz, and Michel Verleysen. The concentration of fractional distances. IEEE Transactions on Knowledge and Data Engineering, 19(7):873888, 2007.
[29] Gérard Biau and David M Mason. High- -igh-dimensional p-norms. Mathematical Statistics and Limit Theorems: Festschrift in Honour of Paul Deheuvels, pages 21-40, 2015.
[30] Evgeny M Mirkes, Jeza Allohibi, and Alexander Gorban. Fractional norms and quasinorms do not help to overcome the curse of dimensionality. Entropy, 22(10): 1105, 2020.
[31] Georges A Croes. A method for solving Saaveling-Saesmman Problems. Operations Research, 6 (6):791-812, 1958.
[32] Jun Gu and Xiaofei Huang. Efficient local search with search space smoothing: A case study of the Traveling Salesman Problem (TSP). IEEE Transactions on Systems, Man, and Cybernetics, 24(5):728-735, 1994.
[33] Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. Advances in Neural Information Processing Systems,
2022.
[34] Elias Frantar, Carlos Riquelme Ruiz, Neil Houlsby, Dan Alistarh, and Utku Evei. Scaling laws for sparsely-connecee foundation models. In International Conference on Learning Representations, 2024.
12

---

[35] Danny Hernandez, Jared Kaplan, Tom Henighan, and Sam McCandlish. Scaling laws for transfer. arXiv preprint arXiv:2102.01293, 2021.
[36] Danny Hernandez, Tom Brown, Tom Conerly, Nova DasSarma, Dawn Drain, Sheer El-Showk, Nelson Elhage, Zac Hatfield-Dodee Tom Henighan, Tristan Hume, Scott Johnston, Ben Mann, Chris Olah, Catherine Olsson, Dario Amodei, Nicholas Joseph, Jared Kaplan, and Sam Mc- Candlish. Scaling laws and interpretability of learning from repeated data. arXiv preprint arXiv:2205. /0487, 2022.
[37] Aidan Clark, Diego de Las Casas, Aurelia Guy, Arthur Mensch, Michela Paganini, Jordan Hoffmaann, Bogdan Damoc, Blake Hechtman, Trevor Cai, Sebastian Borgeaud, George van den Driessche, Eliza Rutherford, Tom Hennigan, Matthew Johnson, Katie Millican, Albin Cassirer, Chris Jones, Elena Buchatskaya, David Budden, Laurent Sifre, Simon Osindero, Oriol Vinyals, Jack Rae, Erich Elsen, Koray Kavukeuoglu, and Karen Simonyan. Unified scaling laws for routed language models. In International Conference on Machine Learning, pages 4057-4086. Proceedings of Machine Learning Research, 2022.
[38] Oren Neumann and Claudius Gros. AlphaZero neural scaling and Zipf"s law: tale of board games and power laws. arXiv preprint arXiv:2412. 11999, 2024.
[39] Siqi Liu, Guy Lever, Zhe Wang, Josh Merel, SM Ali Eslami, Daniel Hennes, Wojciech M Czarnecki, Yuval Tassa, Shayegan Omidshafiei, Abbas Abdolmaleki, Noah Y Siegel, Leonard Hasenclever, Luke Marris, Saran Tunyasuvunakool, H Francis Song, Markus Wulfmeier, Paul Muller, Tuomas Haarnoja, Brendan D Tracey, Karl Tuyls, Thore Graepel, and Nicolas Heess. From motor control to team play in simulated humanoid football. Science Robotics, 7(69): eabo0235, 2022.
[40] Karl Cobbe, Chris Hesse, Jacob Hilton, and John Schulman. Leveraging procedural generation benchmark reinforcement learning. In International Conference on Machine Learning, pages 2048 2056. Proceedings of Machine Learning Research, 2020.
[41] Utkarsh Sharma and Jared Kaplan. Scaling laws from the data manifold dimension. Journal of Machine Learning Research, 23(9):1334, 2022.
[42] Mareus Hutter. Learning curve theory. arXiv preprint arXiv:2102.04074, 2021.
[43] Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. Proceedings of the National Academy of Sciences, 22(27))e231187812) 2024.
[44] Eric Michaud, Ziming Liu, Uzay Girit, and Max Tegmark. The quantization model of neural scaling, Advances in Neural Information Processing Systems, 2-226299-2872,, 2023.
[45] Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. A dynamical model of neural scaling laws. In Proceedings of the 41st International Conference on Machine Learning, pages 4345-4382, 2024.
[46] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H Chi, Tatsunori Hashimoto, Oriol Vinyals, Perey Liang, Jeff Dean, and William Fedus. Emergent abilities of large language models. Transactions Machine Learning Research, 2022. ISSN 2835-8856.
[47] Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo. Are emergent abilities of large language models a mirage? Advances in Neural Information Processing Systems, 16:55565-55533 2023.
[48] David Silver, Thomas Hubert, Julian Schritwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arX.vv1112.000001
2017.
[49] Kate Smith-Miles and Leo Lopes. Measuring instance difficulty for combinatorial optimization problems. Computers & Operations Research, 39(5):875-889 2012.
13

---

[50] Peter Merz and Bernd Freisleben. Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Transactions on Evolutionary Computation, 4(4):337-352, 2000.
[51] Gabriela Ochoa, Sébastien Verel, Fabio Daolio, and Marco Tomassini. Local optima networks: A new model combinatorial fitness landscapes. Recent Advances in the Theory and Application of Fitness Landscapes, pages 233-262, 2014.
[52] Mohammad-H Tayarani-N and Adam Prügel--Bnnett. An analysis of the fitness landscape of Travelling Salesman Problem. Evolutionary Computation, 24(2)347-334, 2016.
[53] Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM (JACM), 45(5):553-782, 1998.
[54] Kenneth D Boese, Andrew Kahng. and Sudhakar Muddu. new adaptive multi-start technique for combinatorial global optimizations. Operations Research Letters, 16(2):101-113, 1994.
[55] Eric Angel and Vassilis Zissimopoulos. On the landscape ruggeeeee of the quadratic assignment problem. Theoretical Computer Science, 263(1-2):155-172)) 2001.
[56] Doug R Hains, L Darrell Whitley, and Adele E Howe. Revisiting the big valley search space structure in the TSP. Journal of the Operational Research Society, 62(2):305-312, 2011.
[57] Gabriela Ochoa, Nadarajen Veerapen, Darrell Whitley, and Edmund Burke. The multi- funnel structure of TSP fitness landscapes: a visual exploration. In Artificial Evolution: 12th International Conference, Evolution Artificielle, EA, pages 1-13. Springer, 2016.
[58] Gabriela Ochoa and Nadarajen Veerapen. Deconstructing the big valley search space hypothesis. In Evolutionary Computation in Combinatorial Optimization: 16th European Conference, EvoCOP, pages 58-73. Springer, 2016.
[59] Kris Braekers, Katrien Ramaekers, and Inneke Van Nieuwenhuyse. The Vehicle Routing Problem: State of the art classification and review. Computers & Industrial Engineering, 99: 300-313, 2016.
[60] Aldy Gunawan, Hoong Chuin Lau, and Pieter Vansteenwegen. Orienteering Problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research, (55(2):315-332) 2016.
[61] Martine Labbé, Gilbert Laporte, Inmaculada Rodríguez Martín, and Juan José Salazar González. The Ring Star Problem: Polyhedral analysis and exact algorithm. Networks: An International Journal, 1373):177-189, 2004.
[62] Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn solve routing problems! In International Conference on Learning Representations, 2019.
[63] Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep Policy Dynamic Programming for Vehicle Routing Problems. In International Conference on Integration of Constraint Programming. Artificial Intelligence, and Operations Research, pages 190-213. Springer, 2022.
[64] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. NeuroLKH: Combining deep learning model with Lin- Kenniennghhnn- Heeemighan-Hellggunn heuristic for solving the Traveling Salesman Problem. Advances in Neural Information Processing Systems, 34:7472-7483 2021.
[65] Eric Angel and Vassilis Zissimopoulos. On the classification of NP-complete problems in terms of their correlation coefficient. Discrete Applied Mathematics, 99(1-9):261 2000.
[66] Leticia Hernando, Jose A Pascual, Alexander Mendiburu, and Jose A Lozano. study on the complexity of TSP instances under the 2-exchange neighbor system. In IEEE Symposium on Foundations of Computational Intelligence (FOCI), pages 15-21, 2011.
[67] Shen Lin and Brian W Kernighan. An effective heuristic algorithm for the Traveling-Salesnne Problem. Operations Research, 21(2):498- -16, 1973.
14

---

[68] Alfonsas Misevicius and Andrius Blazinskas. Combining 2-opt, 3-opt and 4-opt with k-swap- kick perturbations for the Traveling Salesman Problem. 17th International Conference on Information and Software Technologies, 2011.
[69] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vitooo, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In Neural Information Processing Systems Workshop, 2017.
[70] Xavier Bresson and Thomas Laurent. The transformer network for the Traveling Salesman Problem. arXiv preprint arXiv:2103.03012 2021.
[71] Luke Metz, Julian Ibarz, Navdeep Jaitly, and James Davidson. Discrete sequential prediction of continuous actions for deep RL. arXiv preprint arXiv:1705.0506 2017.
[72] Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: Robust and efficient hyperparameter optimization at scale. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 1437-1446, 10-15 Jul 2018.
[73] Takuya Akiba, Shotaro Sano, Toshihiko Yanase. Takeru Ohta, and Masanori Koyama. Op- tuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery Data Mining, KDD '19, page 2623-2631, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450362016. doi: 10.1 011114//292500.333000
[74] Marius Lindauer, Katharina Eggensperger, Matthias Feurer, André Biedenkapp. Difan Deng, Carolin Benjamins, Tim Ruhkopf. René Sass, and Frank Hutter. SMAC3: A versatile Bayesian optimization package for hyperparameter optimization. Journal of Machine Learning Research, 23(54):1-9, 2022.
[75] James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. In Shawe-Taylor, Zemel, P Bartlett, Pereira, and KQ Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[76] Lisha Li, Kevin Jamicson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hy- perband: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, 18(1 ((185))1-522 2018.
[77] Shuhei Watanabe, Archit Bansal, and Frank Hutter. PED-ANOVA: Efficiently quantifying hyperparameter importance in arbitrary subspaces. In Edith Elkind, editor, Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, pages International Joint Conferences on Artificial Intelligence Organization, 2023. doi: 10. 04444666/jcaii.2022433
[78] Frank Hutter, Holger Hoos, and Kevin Leyton-Brown. An efficient approach for assessing hyperparameter importance. Eric Xing and Tony Jebara, editors, Proceedings of the 31st International Conference Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 754-762, Bejing, China, 22-24 Jun 2014.
15

---

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]
Justification:
The introduction mentions our key hypothesis and summarizes our contribu- tions in the last paragraph. We scope the problem studied (TSP) and the scaling regime we focus on (model capacity bottleneck from limited number of parameters).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 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 can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
First paragraph of the discussion, Section
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 are encouraged to create a 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiaatinn 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best 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 set of assumptions and complete (and correct) proof?
16

---

Answer: [Yes]
Justification: Proof of relations and limits referenced in Section are provided in the supplementary materials.
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 to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Details our model architecture and hyperparameters for experiments (along with their motivation) are then provided in the supplementary materials.
Justification: Our method outlined in Section 2
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
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 it possible for others to replicate the model with the same dataset, or provide access 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 replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a 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 describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
17

---

5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Code for all experiments and figure generation will be provided with the paper when released, but not provided with this submission. Most experiments take the order of weeks (if not months) to reproduce assuming access to mid-range GPU cluster. The optimal solution dataset we used and plan to contribute is much larger than the 100MB limit for supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not 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 NeurlPS code and data submission guidelines (https
7 //nips //nips.ccpput hcc/pbblic/ggideeeeeeeceeppeeeee httpa///giiioe//oeeeuubbiiieeee TrodeSubmissionPolll..
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as 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: Key training and test settings are discussed Section Hyperparameters and our HPO method are provided in the supplementary materials.
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: [No]
Justification: TSP data distribution means are estimated with large enough datasets to produce very tight confidence intervals. Intervals are similarly tight for seed-specific algorithm performance. However, due to resource constraints, we train only one seed per scale deep learning experiments. We cannot determine statistical significance for specific fit constants, which we mention where relevant in the paper. Otherwise, we do include statistical significance information where feasible and appropriate, such as with approximations of
TSP optimality in the supplementary materials.
18

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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 be given (e.g.. Normally distributed errors).
should be clear whether the eπror bar is the standard deviation or the standard error of the mean.
It is OK to report I-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 not show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
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
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Provided in Section 2.5 and the supplementary materials. Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We adhere to every requirement.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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 socictal impacts and negative societal impacts of the work performed?
Answer: [No]
19

---

Justification: This paper is foundational research. We discuss potential applicability to domains beyond TSP and combinatorial optimization in Section 7 However, until this is better characterized in future work, any discussion of broader societal impact would be purely speculative.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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.. deploymentt 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 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 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 ML).
11. Safeguards
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: We do not release any pretrained models and our dataset only contains solved TSP problems, which pose no such risks.
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 to 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 is 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: For optimal tour generation we use PyConcorde
15 which
wraps Concorde. Concorde available for all academic research use [17] Our repository follows PyConcorde's BSD-3-Clause requirements, and cite all creators in Section 2
20

---

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 or dataset.
The authors should state which version of the asset used and, 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 (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com camdsatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that 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
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification: As discussed in Question 5, we plan release our project code and TSP solution dataset, but do not include them in this submission. However, dataset details are documented in Section
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cood/mmodll as part of 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 an anonymized zip file.
14. Crowdsourcing 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 details about compensation (if any)?
Answer: [NA]
Justification:
Our research did not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code Ethics, workers involved in data collection, curation, 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?
21

---

Answer: [NA]
Justification:
Our research did not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
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 NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it 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.
Answer: [NA]
Justification:
We occasionally used LLMs for word or phrase choice.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy htteep///oarrrssecc///oofeeeeeep for what should or should not be described.
22

---

Contents
Introduction
2
Experimental setup
2.1
Data design
2.2
Optimal tour generation
2.3
Model training
2.4
Suboptimality estimation
2.5
Scaling experiments
3
Neural scaling laws for combinatorial optimization
Complexity scaling laws the infnite-compute limit
4.1
Solution space scaling).
4.2
Representation space scaling
Interpretable complexity scaling with local search
6
Related work
Discussion
References
11
Scaling law fit constants
25
Trend breakdown and assessment of learning convergence
26
I Training details
27
B Neural scaling assessment
27
B.3 Complexity scaling assessment
27
Loss behavior
29
Relevant experiment details
29
Neural scaling loss behaviors
29
Complexity scaling loss behaviors
30
D Local search supplement
32
D.I Properties of the 2-opt cost landscape
32
D.I.I Evaluation method
32
D.1.2 Property convergence as d 00
32
D.1.3 Property divergence n
34
D.2 2 2-exchange search results
34
Optimal solution approximation in higher dimensions
35
23

---

E.
Approximation method
35
2 Dataset validation
35
Compute requirements
37
Model archifecture
37
Policy network
37
Critic network
38
G.3
PPO using compositional value baseline
38
Hy Hyperparameter seftings
40
HPO method
40
H.2 ВOHB results
41
Proof of scaling relations and limits
44
Lemma
44
Lemma
44
Lemma
45
heorem
46
Theorem
47
Theorem
24

---

Appendix
A Scaling law fit constants
We provide the fit constants for scaling laws discussed in the main paper. Remaining fits can be found in the project repository lhttps://gite example, our repository provides fits of the scaling laws for loss discussed in Appendix
commloweewww/come httpllexxtyyyccllinnee laws, For
RL and SFT scaling laws may have non-trivial imprecision due training with single seed per scale. This should be considered when extrapolating, or when comparing values between RL and SFT such as in node scaling and optimal model size fits. To mitigate this concern, performed jackknife (leave-one-out) resampling of RI. and SFT fits and provide growth rate statistics in Table 4 We provide individual leave-one-out (LOO) fits in the project repository. While LOO distributions distinct from those obtained using multiple seeds, they quantify sensitivity to individual training runs.
Optimal model size fits are relatively sensitive due to the frontier overlap between adjacent model sizes. observe higher variance and the largest SFT LOO a exceeds the smallest RL LOO a (despite the full-data RL being larger than the full-data SFT a:). Node-scaling fits relatively sensitive to the suboptimalities obtained at the largest node scales. For RL, we obtain a values as large as 1.95 when fixing the y offset at its full-data value and 2.22 when fitting y Demonstrated by the large positive skewness, these larger a fits occur at larger LOO node scales. However, fitting shift the offset more than 3 nodes and we know near optimality is achieved 5 nodes, fixed-y LOO variance is likely closer to multi-seed variance. Remaining LOO fits are quite stable, and we found that B asymptote fits for dimension scaling experiments nearly constant (roughly 1..001.
Table I: Neural scaling law fits.
Scaling law
Form
Algorithm
k
RL
0.582
4.42 x 10
Parameters (N)
(1)
SFT
0.712
1.38
1
RL
0.439
6.62 x 10-9
Compute (Cnin)
Cwin
SFT
0.555
6.78
10-9
RL
0.816
1.75 x 10 10-12 12
Optimal model size
N= = =x(
SFT
0.658
1.98 10-14
Table 2: TSP node (n) scaling law fits.
Form
Algorithm
M
?
k:
RL
1.86
4.99
1.91
10a
SFT
1.69
4.99
2.24 x 102
2-opt
25
2.09
22.3
18.6
(7=2)
2-opt
20
1.82
21.0
14.2
2-opt
15
1.67
18.1
11.1
2-opt
10
1.49
14.8
8.05
2-opt
5
1.27
10.8
4.94
Table 3: TSP spatial dimension (d) scaling law fits. RL fits use pure exponential decay (ø 1).
Form
Algorithm
n
/
+b
k
RL
10
5.33 x 10-
1.18
1.00
7.24
10-2
RL.
0.209
1.66
1.00
0.557
2-opt
10
5.70
10
66.8
0.215
5.22
2-opt
20
0.254
98.6
0.251
38.0
25

---

Table -ua (LOO) statistics for RL and SFT fits of exponent a and base 4s.
LOO indices (idx) are in ascending scale order.
Scaling law
Algorithm
Fit
Skew
Min (idx)
Max (idx)
Parameters (N)
RL
Qt
0.579
0.013
-1.9
0.545 (0)
0.593 (4)
SFT
a 0.718
0.015
0.87
0.701 (2)
0.745 (0)
RL
at 0.440
0.011
0.83
0.423 (5)
0.463 (0)
Compute mini
SFT
0.554
0.011
-0.28
0.536 (2)
0.570 (0)
RL
0.811
0.064
00.47
0.690 (7)
0.903
Optimal model size
SFT
Ct
0.655
0.071
- -0.22
0.556 (4)
0.734 (2)
RL
1.87
0.032
1.4
1.83 (6)
1.95 (8)
Nodes (n) fix 7
SFT
ax 1.71
0.059
1.4
1.65 (3)
1.83 (5)
RL
ax 1.90
0.116
2.2
1.81 (0)
2.22 (8)
Nodes (ni y
SFT
a 1.69
0.134
0.46
1.48 (0)
1.94
10n n n0
RL
1/ 1.18
0.007
-1.0
1.16
1.19 (5)
Dimensions (d)
RL
4/ 1.68
0.023
-0.46
1.62 (2)
1.71 (0)
Table 5: Performance bounds obtained for TSP node and spatial dimension scaling. Random tour length w.r.t nodes is derived (Lemma[]) T. Otherwise, these fits should not be extrapolated. Scaling variable
Form
Algorithm n
a
Y
Optimal
0.433
0.215
0.906
Nodes (n)
Hoost
1
Random
1.000
0.000
1.918
Optimal
10
0.593
0.981
0.175
Dimensions (d)
Peost
d=
Random
Optimal
20
10
0.656
0.501
0.368
1.24
6.04 x 10
0.102
Random
20
0.500
0.369
1.50 x 10
In Table for random tour length and optimal tour length, we provide the scaling trends that we obtain for the tested TSP node and spatial dimension domains. Random tour length w.r.t. number of nodes is derived (Lemma] I Other constants listed are empirical fits that may be useful for interpolation. For example, mean optimal tour length w.r.t. nodes produces errors less than 5 x 10-3 within the tested domain of 5 to 50 nodes. However, these fits should not be extrapolated to much larger scales because several
these fits provably break down. For mean optimal tour length, (25), where our empirical fit is 0.433. For mean random tour length w.r.t.
- 0.5 spatial dimensions, a fits are close to the true limiting behavior a = 0.5 (Theorem but error eventually accumulates due to inexact proportionality constant fits.
B Trend breakdown and assessment of learning convergence
This section details larger-scale experiments that did not converge to trend. We also elaborate on relevant details of our training method. We show models which visibly failed to converge using this method and we identify boundary cases where convergence is more difficult to assess. These scaling law predictions, evaluating to larger suboptimality values. If any
models underperform model were to outperform our scaling law predictions, trend breakdown could not be attributed to insufficient training.
significant portion of neural scaling laws research is performed by organizations with access to abundant computational resources. Experiments that initially fail to converge (if any) can be rapidly iterated. Researchers with more computational constraints often do include results for trend-breaking experiments. However, these results are sometimes mentioned in passing without evaluating model convergence. Besides promoting transparency, we provide this appendix to document the behavior of scaling law breakdown under compute budget constraints.
26

---

SFT
RL O trend broak S
SFT
-- bend break san-ay
15-1
Par (W)
Suboptmailty
222X30
127
D-DD
forter
berdbrok
Trontirr
Parameters (N)
Parameters (M)
Compute (PF-days)
Compute (PF-days)
Figure 6: Suboptimality w.r.t. parameter and compute scaling, including experiments which did not converge to trend. Left pair: Parameter scaling experiments evaluated at the end of training. Unfilled markers indicate models not shown in Figure I that are excluded from power law fits. Right pair: Suboptimality evaluated throughout training w.r.t. compute. Models excluded from parameter scaling fits fail to reach the compute-efficien frontier with our training settings.
B.1 Training details
Without data constraints, RL models trained for one million gradient updates with a three-stage learning rate schedule: brief linear warm-up, then cosine decay over early convergence, then slow linear decay to zero. Cosine decay terminates at a learning rate of 10-5 at update number 170,000. This termination update was informed by hyperparameter optimization results that we detail in Appendix H For the remainder of our training budget, 830,000 updates, was a design choice to use slow linear learning rate decay. For models which nearly converge within the cosine decay window, this approach reliably extracts remaining marginal improvements. However, late-stage training consumes most of the training budget. Models which insufficiently converge within the cosine decay window make less progress than they would if the learning rate was instead reduced more gradually. We opted for this trade-off to prioritize ensuring convergence for experiments smaller scales, providing more precise results for the scaling laws we present in the main paper.
For SFT models, data constraints restricted training duration given we stop after one epoch to avoid potential performance bottlenecks from dataset size. For these experiments, after warm-up, the learning rate cosine decays to zero over the remainder of the epoch, which yields 73,143 updates with our dataset and batch size settings. Despite this abbreviation training, SFT's strong supervised learning signal results in sufficient convergence for several smaller model scales and problem scales.
B.2 Neural scaling assessment
Figure/Jshows slowwws the complete set of parameter and compute scaling experiments evaluated. This includes the fitted results shown in Figure 1 along with results from larger models that failed to converge. Parameter scaling evaluations drift right of trend and level off. Temporal compute scaling trends demonstrate that these models failed to converge with our training settings. Learning curves for larger SFT models maintain steep descents throughout training. Curves for larger RL models level off only slightly, which is attributable to the very small learning rates used in late-stage training.
168,000 parameter outlier: We also exclude the roughly 168,000 parameter model (shown in lower opacity) when fitting the RL compute-efficient frontier. This outlier is unrelated convergence. However, fitting with this model separates the frontier from several other models that also converge. Scaling laws predict the expectation of model performance over random seed variables like parameter initializations and training batch sampling, and this outlier's random seed appears to perform unusually well. Averaging evaluations over several seeds would likely address this discrepancy.
B.3 Complexity scaling assessment
Figure 7 shows the full set of TSP node and spatial dimension scaling experiments we evaluated. For node scaling results, excluded SFT experiments only slightly break trend, whereas the excluded 50-node RI. experiment sharply breaks trend. F explains this behavior with suboptimality evaluations throughout training. Learning curves for excluded SFT experiments are more divergent
27

---

Suboptimalii gap
0.10
RL
trend breat s
trend breat 6n
0.08
ALow Ia
inea teat
0.4
0.15
- R.
0.3
2-
0.04
-0- mes teat
-on tred brck
0.30
2- -
0.02
0.00
0.1
0.00
0.0
50
10
20
29
30
40
100
Nodes (n)
Spatial dimensions (d)
Spatial dimensions (d)
Figure 7: Suboptimality w.r.t. TSP node and spatial dimension scaling, including experiments which did not converge to trend. Unfilled markers indicate models not shown in Figure that are excluded from scaling law fits. Left: Node scaling experiments evaluated at the end of training. SFT's power growth fit is shown in different color only for clarity. Right pair: Spatial dimension scaling experiments evaluated at the end of training. We show early trend breakdown (center) along with the full domain up 100 dimensions (right).
n-SFT
n-RL
d-RL (n = 10)
d-RL (n = 20)
0.5
1.0
excluded
excluded fitted
excluded fitted
excluded
fitted
fitted
10
7 10
10
Suboptimality gap
0.3
0.6
0.4
0.0
Model updates
Model updates
Model updates
Model updates
Figure 8: Suboptimality w.r.t. TSP node (n) and spatial dimension (d) scaling evaluated throughout training. For RL experiments, the end cosine decay is marked with a green vertical line. Subsequent updates use learning rates below 10-5, which impedes the convergence of models training larger problem scales. Note that we use smaller 12,800 sample datasets evaluate each learning curve. Each dataset is distinct since scale the problem, small differences between adjacent scales may not be statistically significant. The reduced sample size also (falsely) produces negative suboptimality values for 2D TSP with 5-node and 10-node scales where model performance becomes near-optimal
and maintain steeper descents until learning rate decay impedes progress. And the excluded 50- node RI. experiment performs particularly poorly in early training during the cosine decay period. Subsequent training makes significant progress, so this model may have initially approached a poor local optimum in loss landscape.
For spatial dimension scaling results, excluded experiments at scales beyond 20 dimensions fail to sufficiently converge in early training and maintain steeper descents in later training (right pair of Figure 8). However, excluded experiments between 11 and 15 dimensions are not as distinguishable from their fitted counterparts, especially with non-trivial imprecision from using smaller evaluation datasets that vary for each scale. These experiments correspond to the lowest black curve for 10-node plot (15 dimensions) and the lowest three black curves for the 20-node plot (11, 12, and 15 dimensions). For these boundary cases, we solely rely on evidence from adjacent scales to surmise that further training produce trend alignment.
28

---

C Loss behavior
For generative modeling, the majority of research neural scaling laws studies cross-entropy loss [3 [3] However, in general, we do not expect loss to trend for RL algorithms [14]. Further, the scaling behavior of RL loss is often irrelevant to task performance, whereas cross-entropy loss in language modeling, for example, is directly relevant to task performance. This detachment from performance makes scaling laws for RL loss less interpretable.
Even so, we observe several loss behaviors worth documenting. We detail these behaviors below and summarize them here. First, separate loss components can concurrently trend and not trend even when these components have interdependent learning objectives. Second, variance of loss can reveal underlying trend when mean loss does not trend. Third, when scaling problem complexity, token-level cross-entropy loss may not correlate with task performance.
C.1 Relevant experiment details
SFT models were trained to predict optimal tour length with a critic head alongside the primary objective of minimizing negative log- likelihooddd (NLL) of optimal next-node prediction. This setup maintains identical architectures (and equal parameter counts) between SFT and RL experiments, isolating differences the policy learning objective.
Loss evaluations use same datasets as corresponding suboptimality evaluations. We evaluate the same scales used for the main paper as we found that loss trend breakdown closely aligns with subop- timality trend breakdown when using our training method (with limited compute). Suboptimality trend breakdown is discussed in Appendix B
C.2 Neural scaling loss behaviors
Figure shows model test loss w.r.t. parameter and compute scaling. Supervised NLL loss power decays as expected from previous neural scaling laws work. PPO's s clipped surrogate objective [20] (actor loss) has obvious trend other than being zero-centered, also expected. However, PPO's critic loss does smoothly power decay. The existence of this scaling law is more surprising given the value target distribution is non-stationary (following on-policy tour length) and the mean actor loss does not trend.
RL
SFT
RL
SFT
10-
10-
5.004
1.69
L*
L
2.12
critic
5,002
10-2
5.38% 101
Parameters (N)
20a
10/
10a
10"
10
15
10
10
127 X100
Parameterss (N)
Parameters (M)
Compute (PF-days]
Compute (PF-days)
Mean Sctorr TO2E 10S2
N=
0.0033
0.28
0.02
0.8093
0.26
0.01
0.3090
0.24
0.00
3.00
-0.0003
0.22
0.25
Trantier
(C
0.3093
T[ 11
0.03
T17
Parameters (V)
Parameters
(N)
Compute (PF-days)
Compute (PF-days)
Figure 9: Loss w.r.t. parameter and compute scaling. Note that SFT's compute axes (right column) have been stretched for easier viewing. and the loss axes for those subplots do not share scale with the RI. compute scaling subplots to their left (unlike Figure Top: Self-supervised critie loss smoothly power decays when predicting on-policy tour length (RL.) or predicting optimal tour length (SFT). Bottom: Supervised NLL, actor loss smoothly power decays but PPO actor loss has no mean trend other than being zero-centered w.r.t. the non-stationary critic baseline.
29

---

5D cntic test loss
10-1
0.304
602x10
fronter
frontier
535
Parameters (N)
10a1
10
10
0.001
30a
10F
10a
10a
10-4
10
10
10-1
327%
Parameters (N)
Parameters (N)
Compute (PF-days)
Compute (PP da-sd
5D octor test loss
LWN
L=N
0.76
074
0.74
x.0
0.03
0.72
0.03
break
037
XXCual
0.02
0.70
0.02
0.79
6.18x10'
201
10P
10a
20*
10th
10
10
10th
Parameters (N)
Parameterss
Compute (PF-days)
Compute (PF-days)
Figure 10: Standard deviation (SD) of loss w.r.t parameter and compute scaling. Subplot layout matches that used for Figure The variance each loss component exhibits smooth power decay, even for the PPO actor loss which does not produce scaling laws for mean loss.
The behavior PPO actor loss variance may partially explain why scaling laws emerge for mean PPO critic loss. Figure shows that variance of loss also predictable when scaling parameters or compute. This observation is perhaps intuitive for loss components where the mean trends. However, we obtain similarly precise scaling laws for the variance of PPO actor loss, revealing that an underlying predictable nature persists despite the absence of predictable mean. The existence of scaling laws for mean critic loss may depend on this predictable actor loss behavior, and vice versa, given the strong interdependence between the learning objectives.
Lastly, subtle additional finding from these results is that scaling laws for loss appear more robust against outliers when compared to their suboptimality counterparts. For suboptimality trends in Figure including the (roughly) 168,000 parameter model the RL compute-efficient frontier fit noticeably skews the result. In contrast, while this outlier is still visible in the RL compute- -fficieet frontier for critic loss (Figure top. third column), excluding hardly alters the obtained fit.
C.3 Complexity scaling loss behaviors
Figure 11 shows model test loss w.r.t. TSP node and spatial dimension scaling. Aligning with observations for parameter and compute scaling, self-supervised critic loss components mirror the scaling law forms of their suboptimality counterparts, and PPO actor loss is zero-centered. However, supervised NLL loss w.r.t. node scale deviates from the power growth trend that SFT suboptimality and optimal tour length prediction adhere to. Instead, NLL loss exponentially decays with increased node scale over the tested domain Hence, as suboptimality accumulates with increasing solution space complexity, next-node prediction improves.
One potential explanation is that next-node prediction benefits from the increasing negative su- pervision: each label for next-node selection provides one positive example and (n 1) negative examples. If we were to assume this trend extrapolates, then next-node prediction NLL converges as suboptimality diverges. If so, the joint NLL of full-tour prediction may still diverge given the number node predictions per tour increases, although we did not evaluate this metrie. Alternatively, the trend observed for node-level NLL loss may break down shortly after the tested scales. In any case, node-level cross-entropy loss does not correlate with task performance. This complication avoided when scaling laws are obtained for metrics that correlate with task performance by definition (for example, suboptimality).
We find that standard deviation (SD) of critic loss follows the corresponding scaling law form of suboptimality and mean critic loss, as shown Figure 12
However, scaling behaviors are not as
'ee also tested power decay but this form converges too slowly and fits negative & asymptote (NLL is strictly nogatega)..).
30

---

SFT
RL
RL (n 10)
RL (n = 20)
3.0
3.0
Mean cnbic test 1085
Lx(n-ph*
1.0
8
2.5
0.8
2.0
2.0
2.0
1.5
1.5
1.5
1.0
1.0
0.5
0.5
0.0
0.0
0.0
0.0
15
25
10
(m)
Nodes
Spatial dimensions (d)
Spatial dimensions
1.0
1.0
1.0
Mean actor test loss
0.3
0.5
0.0
0.2
-0.5
0.1
15
25
35
15
25
36
45
10
12
10
Nodes (n)
Nodes
Spatial dimensions (d)
Spatial dimensions
Figure 11: Loss w.r.t. TSP node and spatial dimension scaling. Top: Sclf-supervised critic loss adheres to the corresponding scaling law form observed for suboptimality (Figure Bottom: PPO actor loss only follows a zero-centered trend, as does for neural scaling experiments (Figure 9 Supervised NLL loss adheres to exponential decay when scaling nodes, deviating from the power growth pattern observed for suboptimality and critic loss. This trend implies that next-node prediction improves with node scale for SFT models, at least smaller scales. However, this trend does imply that full-tour prediction improves because the number of nodes predicted per tour increases.
SFT
RL
10)
RL 20)
1e-3
L
Le(n y
critic test loss
1.5
4
0.03
0.02
2
1
0.01
L 8
0.0
15
25
35
45
5
15
25
45
10
12
10
12
Nodes (n)
Nodes (n)
Spatial dimensions (d)
Spatial dimensions
0.8
SD actor test loss
1--------
0.05
La(nn 9
0.08
0.15
8
0.04
0.06
0.10
0.4
0.2
0.05
0.02
L 8
L-
8
15
25
35
45
5
15
25
35
45
10
12
Nodes
(n)
Nodes (n)
Spatial dimensions (d)
Spatial dimensions (d)
Figure 12: Standard deviation (SD) of loss w.r.t. TSP node and spatial dimension scaling. Subplot layout matches that used for Figure II Top: Standard deviation of critic loss adheres to the corresponding scaling law form of mean critic loss (and suboptimality). Bottom: Standard deviation of PPO actor loss roughly aligns with the corresponding suboptimality and critic loss trends, but fit quality is markedly worse (illustrated in red). Standard deviation of supervised NILL loss w.r.t. node scale does not follow a consistent trend (bottom left).
31

---

predictable for SD of PPO actor loss or supervised NLL. For the latter, node scale has no obvious correlation with SD. For the PPO actor loss. SD trends resemble their critic loss and suboptimality counterparts but fits are clearly inferior. We observe contiguous residuals of the same sign, and for spatial dimension scaling experiments exponential decay converges too fast, fitting 3 values below the SD values obtained at the largest scales. Compared to neural scaling results in Figure [0] predicting SD of loss appears to be more nuanced when scaling complexity. However, note that SD and variance would not share the dimension scaling law form due to the additive 3 term, Actor loss variance may produce a closer fit, but we did not evaluate these trends.
D Local search supplement
Section D.I details the 2-opt cost landscape properties referenced in Sections 4.2 and 5 provides complexity scaling results for 2-exchange search, which uses different definition of solution adjacency than 2-opt search.
Section D.2
D.1 Properties of the 2-opt cost landscape
For each complexity scaling scaling experiment, we measure three fundamental properties of the 2-opt cost landscape in expectation: the number of local optima, the size of local optimum's 's basin of attraction, and the relative size of the global optimum's 's basin of attraction. Results in Figure [3] suggest that these properties converge when scaling TSP spatial dimensions. In contrast, these properties diverge when scaling the number of TSP nodes.
D.1.1 Evaluation method
To measure these properties, we perform numerous search descents (k) for each TSP problem evaluated. Each descent starts at a random tour and terminates when arriving at a locally optimal tour (w.r.. one additional 2-opt move). We then count the number of unique local optima found, count the number of search moves required to reach them (basin of attraction size), and evaluate the fraction of descents that arrived at the best-found local optima (relative size of the global optimum' 's basin of attraction).
Estimating the number of local optima requires adequate coverage of the landscape, does estimating the visitation rate of the global optimum given we approximate the global optimum using the best- found local optima (BLO). For these estimations, we perform 100,000 descents per problem (large-k) while sampling small batches for each scale: 2048 problems for 10-node dimension scaling, 512 problems for 20-node dimension scaling, and 32 problems for node scaling.
Evaluating mean search moves does not require adequate coverage of the landscape, so we use fewer descents per problem and sample larger problem batches (small-k, large-batch). For dimension scaling, we reuse the approximately optimal datasets detailed in Appendix[E] For node scaling, we use 100 descents per problem and sample 64,000 problems. We also show evaluations for local optima count and BLO visitation rate using these datasets for comparison (blue triangles in Figure [3]
D.1.2 Property convergence as d
Figure 13 shows that expected search depth and BLO visitation rate both power decay when increasing spatial dimensions. The former implies that basin of attraction size converges in expectation. Because each 2-opt search move evaluates O(n²) adjacent solutions, and TSP node scale remains constant, convergent search depth implies convergence of the number of solutions evaluated per descent. Alongside the convergence of the BLO visitation rate, these observations suggest that, with many- descent local search, finding the optimal solution approaches a stationary computational complexity apart from the (d) complexity of evaluating each visited solution's cost.
Unlike search depth and BLO visitation rate, the number of local optima has no predictable convergent trend and instead grows non-monotonically. This is not an artifact of sample size as we observe the same behavior for small-k; large-batch evaluations (with a significant underestimation bias). Growth visibly slows by 100 dimensions, and growth is upper bounded by the fixed solution space size, so convergence is plausible but not directly implied by these results.
32

---

Mean local optima count
20
Mean BFLO visitation %
80
Mean search moves
5.6
70
10
60
5
8
100
10a
207
10²
107
10'
Spatial dimensions (d)
Spatial dimensions (d)
Spatial dimensions (d)
Mean local optima count
Mean BFLO visitation %
5000
Mean search moves
14.8
4000
20
14.4
1000
13.6
Spatial dimensions (d)
Spatial dimensions (d)
Spatial dimensions (d)
Mean local optima count
10a
100
Mean BFLO visitation
Mean search moves
40
10a
30
107
20
10:
20
35
50
20
50
35
Nodes (n)
Nodes (n)
Nodes (n)
Spatial dimenslon scaling (n= 10)
Small-k large-batch
y (d -
Spatial dimension scaling (n= 20)
Node scaling
y x 1
Figure 13: 2-opt cost landscape properties w.r.t. TSP node and spatial dimension scaling. From top to bottom: 10-node spatial dimension scaling, 20-node spatial dimension scaling, and 2-dimensional node scaling. From left to right: mean local optima count,
frequency that search arrives the best-found local optimum (BIO), and mean search depth before arriving at a local optimum. Dimension scaling: The number of local optima exhibits non-monotonic growth that is upper bounded by the fixed size of the solution space. BLO visitation rate and search depth adhere to power decay. We found that including y scale offset improves fit quality, but excluding still produces reasonable fits. From left to right axis scalings are: [semi-log-x, log-log, log-log]. Node scaling: Due to the expanding solution space, the number of local optima diverges as does the search depth required to reach one. BLO visitation rate decays roughly exponentially. Note that local optima count is underestimated by 100,000 descents per problem [52]. From left right scalings are: (semi-log-y semi-log-y, linear].
33

---

Lastly, these properties are closely related to landscape ruggedness measures like autocorrelation [55] 651. Because the expected range of cost values also converges (Theorem 6). the previous findings may imply autocorrelation converges as d + co. However, we did not directly evaluate this measure.
D.1.3 Property divergence as n
Node scaling produces none of the convergent complexity behaviors discussed above. Cost landscape analysis over solution space scaling is a well-studied topic in TSP and combinatorial optimization [22] (Section 1.1 in the cited work provides a useful overview). Our result provided for convenience.
When scaling nodes, the number of local optima rapidly exceeds what we can accurately estimate with 100,000 descents per problem. For 3-opt search moves, Tayarani et al. [22] show that this growth appears to be ( (ne))n(n) 2-opt's search depth grows almost linearly and 2-opt's BLO visitation rate decays roughly exponentially. Both observations align with 3-opt findings (52). Note that BLO visitation rate converging toward does not reflect steady state property of the cost landscape: we are measuring the relative size of the global optimum's 's basin of attraction as the absolute size of the landscape diverges.
D.2 2-exchange search results
In this paper, we define "2-exchange" as the naive search move that swaps two nodes in the tour sequence. We are not the first to use this definition [66]; however, the term is sometimes used refer to 2-opt in informal sources. 2-opt is the distinct search move that inverts a subtour (31.
Figure 14 shows that 2-exchange reproduces 2-opt's alignment with the complexity scaling law forms models (Figure P However, both moves modify only a few edges and
of parameter-constrainge both adjacency sets scale ( this result demonstrates limited generalization. Analyzing the conditions in which this alignment generalizes for k-opt moves (67] is one potential direction for future work.
3.0
20
capaddd 44h
2 exc (N
20
Suboptimality
2,0
0.6
trand 2veoc
0.4
2oect
1.0
2.645
R
10
0.2
35
Suboptimality gap
Spatial dimensions
Nodes (n)
Nodes (n)
M-
M
655
-3.1
9.7
75
Max depth
20
Nodes Im)
Nodes (m)
Nodes (m)
Nodes (m)
Nodes (n)
Figure 14: 2-exchange local search suboptimality over problem complexity scaling, When scaling nodes and constraining search depth, suboptimality follows superlinear power growth after saturating 100% max depth (top right and bottom). aligning with 2-opt behavior and the scaling form of parameter-constraimg subexponential constant ó when scaling spatial dimensions. However, 2-exchange dimension scaling fits are slightly inferior to their 2-opt counterparts, which may be attributable to 1--xchange exhibiting several the random-subope sutioommttoootiaaltyyy behaviors shown in Figure We observe slight decrease near convergence when scaling dimensions for the 20-node experiment, and unconstrained 2- 2-exchange search produces linear suboptimality growth when scaling nodes (beyond 10 nodes).
models. Like RL fits, 2-exchange fits do not benefit from fitting the
34

---

E
Optimal solution approximation in higher dimensions
For node scaling evaluations we leverage the Concorde-generated optimal solutions introduced in Section 2.2 But evaluating suboptimality higher dimensions requires different approach since the PyConcorde software stack expects 2D TSP. To the best of our knowledge, applying Concorde to higher-dimensional TSP has not been explored. This appears to only an implementation constraint, though, and not limitation of the Concorde algorithm itself since it uses the cutting-plane method [6 and additional spatial dimensions only modify the edge cost calculation. Regardless, we opted to closely approximate optimality for convenience.
E.1 Approximation method
Near-optimal solution tours are generated via mass repetition of local search. For a single TSP instance, k random starting tours are sampled, and for each starting tour distinct descent of local search is performed. Among the generated locally optimal tours, the tour with lowest cost is selected surrogate for the globally optimal tour. This full process is repeated B times using large batch of sampled TSP instances to acquire near-optimal datasets at a desired problem scale.
We use 2-opt moves when generating all surrogate optimal datasets. There are more sophisticated local search algorithms that usually find lower cost solutions for TSP (67 68), though often with increased search time or compute. But we find 2-opt surrogate optimality to be sufficiently accurate at the needed problem scales despite its simplicity.
E.2 Dataset validation
Near-optimal suboptimality scaling laws are sensitive the precision of optimality estimates, so here we investigate approximation quality. For clarity, we refer to surrogate optimal solutions as "surrogate" and reserve "optimal" for strictly optimal solutions.
First, we compare surrogate and optimal solution distributions in 2D TSP where we have datasets for the latter via Concorde [17]. Figure [5] shows that surrogate solution tour length closely approximates the distribution of optimal solution tour length at both 10 and 20 nodes using best-of- 100 and best- of- 10-0 2-opt descents, respectively. Being normally distributed, we perform two sample t-tests on the means Table (6, For each node scale, the mean surrogate tour length is slightly below the mean optimal tour length, which is possible since surrogate and optimal datasets sample distinct
Probabilty density
Probability density
0.8
0.6
0.4
0.4
0.
2.89
32206
3.881
2.916
3.21
3.526
3.831
Tour length
Tour length
Surrogate optimal
Optimal
Optimal's normal pdf fit
Figure 15: Histograms of surrogate tour lengths overlaying optimal tour lengths for 10-node and 20-node dataset pairs. Both are clearly normally distributed, justifying the t-test performed in Table G and the two distributions are visually similar with the optimal histogram's 's probability density function (pdf) fit aligning closely with the surrogate histogram. X-ticks are arranged in standard deviations of the optimality pdf fit.
35

---

Table 6: Two sample t-test comparing mean tour lengths of surrogate solutions and optimal solutions for 2D Euclidean TSP. P-values are obtained for both 10-node and 20-node dataset pairs. We fail to refute the null hypothesis that surrogate solutions come from the same distribution as optimal solutions.
10 nodes
20 nodes
Surrogate
Optimal
Surrogate
Optimal
Samples
128,000
1,280,000
64,000
1,280,000
Mcan
2.86839
2.86870
3,82970
3,83082
Standard deviation
0.33727
0.33753
0.30534
0.30478
t-value
-0.314
-0.906
P(t < t-value)
0.377
0.183
P(t > t-value)
0.623
0.817
problems. Thus, along with the surrogate algorithm itself, we are testing whether the smaller size of the surrogate datasets can sufficiently approximate 1.28 million samples from the optimal distribution.
At both node scales, we are unable to reject the null hypothesis that mean surrogate tour length is equivalent to mean optimal tour length. Because these surrogate datasets underestimate optimality, from these results we clearly cannot suggest the surrogate mean is larger than the optimal mean. But we also do not find spurious evidence that the surrogate distribution underestimates the optimal distribution average, with lower one-sided p-values of 0.377 and 0.183 at 10 and 20 nodes, respectively. With our chosen surrogate dataset settings, for 2D TSP with no more than 20 nodes, surrogate solutions appear statistically indistinguishable from optimal solutions (as desired).
One problem would arise if the best-found local optimum (BLO) visitation frequency were overesti- mated by fewer descents in surrogate solution generation. This overestimation would imply surrogate solutions require more descents to find the true global optima located relatively small basins of attraction. Instead, we find the BLO visitation rate of surrogate solution generation is almost identical to that observed in the small batch 100,000 descents-per perss---ppppppp problem experiment in Figure [3 (center and top center). The error magnitudes do not exceed 1.5% and 0.7% for 10-node and 20-node dimension scaling arrays, respectively. Alongside the high BLO visitation rates themselves, this suggests global optima are often found with only few 2-opt descents, a finding consistent with existing analysis of 3-opt [52) (Figure 15 in cited work).
Another problem would arise if surrogate solution generation were to visit only tiny fraction of local optima. Even with a high BLO visitation rate, eventually the number of missed global optima may accumulate. Figure plott the mean local optima discovery fraction of surrogate solution generation, where we estimate the true mean (divisor) using the 100,000 10-node surrogate solutions uphold greater than 60% discovery rate by 100 dimensions, increasing confidence in global optima discovery considering the BLO visitation rate maintains values greater than 50%. In contrast, 20-node surrogate solutions' local optima discovery decreases to around 10% by 100 dimensions. This discovery rate may still be sufficient to find the global optima in the overwhelming majority of problems. But given the 20-node BLO visitation rate sinks roughly 6% (Figure [3 center), we are of course less confident.
pereentt-per-pooblen experiments. The
There are three smaller caveats for 16 worth noting. First, the confidence intervals assume that the number of local optima at each problem scale are normally distributed. We did not verify as we only saved summary statistics for these experiments. If the local optima count was (for instance) long-tailed toward larger values, this could add uncertainty to our estimates. The second caveat is that we ignore uncertainty in the surrogate solutions' local optima discovery rate, which is relatively small since the surrogate datasets are orders of magnitude larger than those used to estimate the true discovery rate (2048 and 512 samples for 10 and 20 nodes, respectively). Lastly, 100,000 descents- per- per-problem may still miss elusive local optima with small basins of attraction. Even so, these local optima are quite unlikely to be global optima if 3-ppt trends generalize to higher- dinees-dimmniionall 2-opt solutions [52 (Figure 14 in cited work).
36

---

1.0
Fraction local optima discovered
1-
-
0.8
0.6
0.0
Spatial dimensions (d)
Figure 16: Surrogate solution generation's 's estimated mean local optima discovery fraction. Fills show 99% confidence intervals assuming local optima count normally distributed. True mean local optima count is estimated with small batches of 2-opt local search performing 100,000 descents- per-problem. 10-node surrogate generation never falls below 60% discovery, increasing confidence that best-found local optima are usually the true global optima. 20-node generation falls below 10% discovery by spatial dimensions, suggesting that best-found local optima at these scales may be suboptimal more often.
F
Compute requirements
Each model was trained on HPC node using one Nvidia Tesla V100 (I6GB), 24 Intel Xeon Gold 6136 cores, and 384GB of memory. GPU usage was the bottleneck, so fewer CPU cores and less memory would be sufficient. As mentioned in Section 2.5] the 50-node RL run trained for 24 days and consumed roughly 10-3 PF-days of compute. The longest spatial dimension scaling runs and parameter scaling runs trained for about half that time and consumed around an order of magnitude less compute.
Optimal solution generation only used CPU compute and was performed on the same HPC nodes. Using Concorde [17] via PyConcorde [5), generating 1.28 million optimal solutions 50-node 2D TSP required roughly 10 days. We provide 10 of these chunks for each TSP node scale we experimented on: 12.8 million solutions per scale and 128 million solutions in total. Generating and approximately optimal datasets for higher-dimensional TSP (Section 2.22ionnn22ammn and Appendix E) required around hours per 10-node scale and 60 hours per 20-node scale. Note that we used a Cython implementation of 2-opt, which we found to be several times faster than pure Python implementation.
G Model architecture
Our model design prioritizes simplicity where possible. Besides making experiments easier to implement, this choice was intended to improve the reproducibility of our results and promote their generalization to other deep architectures. All core model components are implemented using Py- Torch [69] Transformer modules. Model code, algorithm code, and training scripts are provided in the project repository at hhtpss: / //t/tttttbb com com/ comm/owelwww/ httpl//lwwwomlleee/epeeeemmm eexxitysscaainge.. llws Specific hyperparameter choices are discussed separately in Appendix
G.1 Policy network
Our policy network is most similar to that introduced by Kool et al. [62 with two key simplifications. First, our encoder does not produce full graph embedding, and so does not attend over a context node embedding during the subsequent forward passes of the autoregressive decoder. Second, unlike Kool et al. and Bresson et [70), our decoder does not include final single-head attention layer. Instead, our decoder performs multi-head attention over all node encodings for each decoding step
37

---

while building positionally-ena -ncoode partial tour in the decoder memory. No masking occurs until directly before logits are softmaxed and sampled, where probabilities are set to zero for previously selected nodes.
We moved forward with these simplifications after obtaining near-optimal performance without them at our experimented problem scales. But Kool et al.'s design has compelling motivation, especially concerning efficiency. Their graph embedding allows each decoder step to attend over the reduced subset of selectable nodes while still referencing representation of the full problem. This linear ramp down of attention length still incurs O(n") complexity to decode a full tour, as does our approach which maintains constant attention length 9 But pruning previously selected nodes requires only third the compute, all else being equal. Given that autoregressive decoding most of the forward pass, we suggest reconsidering this design choice when experimenting with large node scales.
G.2 Critic network
Our architecture learns values for the policy gradient baseline. Kool et al. instead use deterministic greedy rollouts from a baseline policy network, referencing the difficulty of multi-objectiin actor-critic learning. But we found the contrary to be true in experiments. Our greedy rollout implementation often diverges early in training (Figure 17 pink), which may stem from one of several distinctions. First, we use PPO actor loss rather than REINFORCE. Second, we synchronize the baseline policy every 625 gradient updates, matching Kool et al.'s period, but they only synchronize if a paired t-test determines statistically significant improvement. Lastly, we do not regenerate the evaluation dataset after synchronizing (to avoid overfitting), though we do use a larger samples size of 100,000. Where possible we also use hyperparameters from Appendix H which are optimized for compositional value learning (discussed below), creating a less fair comparison.
Regardless, learning value function was useful for studying critic loss trends (Appendix C). To learn problem-level state values, we use a second Transformer decoder which receives node encodings from the (now shared) policy encoder. But encodings encoding) and a zero-fill start token is input for the target. The output is projected into a scalar value estimate which train to predict on-policy tour cost for PPO, and optimal tour cost for SFT. Requiring just one forward pass, this is a relatively lightweight addition. We found this simple approach converges well in experiments (Figure 17 blue).
input as decoder memory (without positional
However, problem-level value estimates provide an increasingly stale baseline the longer decoding iterates. For example, just two nodes remain unvisited in a partial tour of 50, the range of possible cost outcomes dramatically reduces. From the perspective of the 49th decoding, all previous node selections can be considered as components of the current node-level state. Note that our framework of problem-level states is merely the outcome of our choice to formalize the TSP environment as bandit problem. We could have instead chosen to formalize the environment as an MDP with node-level decisions, and if we set a discount factor ? = 1, this MDP generates identical returns to bandit problem framing. (Because no rewards occur before the terminal step.)
Attempting to learn more granular credit assignment, we implemented node-level value estimation. We refer to this alternative as compositional value learning, and refer to problem-level value learning as state value learning. We compute compositional values through a straightforward modification to our state-value critic architecture: concatenating the positionalll--nnooe encoded node selection sequence to the start token for target input. This produces n + 1 compositional values, each attending over incremental partial tours in one forward pass via a causal mask. The first output remains the problem- level state-value, attending only over the start token and node encodings. The final output is the Q-value, attending over all node selections. We explain how compositional values influence learning objectives in the following subsection.
G.3 PPO using a compositional value baseline
This section describes how we set up the PPO actor-critic loss to learn and leverage node-level compositional value estimates. We use this style of PPO for all RL experiments in the main paper.
Self-attention has O(n²) complexity w.r.t to the node scale and attention length n 19 which we iterate
times.
38

---

0.30
greedy rollout
state values
Normalizen lized test cost
0.00
compositional values
0.00
0.04
0.42
1.75
Gradient updates
1e5
Figure 17: PPO baseline alternatives training 2D 30-node TSP, evaluated on held out set of 100,000 problems. We normalize suboptimality between optimal performance and random performance in the range [0, 1]. We summarize 5 random seeds for each baseline, where lines showing the means and fills showing the min/max values. Performance converges well when learning problem-level (state) values node-level (compositional) values with critic network, with no meaningful difference between approaches. But using greedy rollouts via a separate policy (updated sparsely like target Q-network) usually produces temporary divergence. We truncate this curve because two runs timed out due to external load on our HPC cluster. Of the three runs that reached 200,000 updates, surpassed learned value function performance.
omit these details for simplicity and because we observe no evidence of performance differences between node- and problem-level baselines (Figure 17 green and blue).
To leverage compositional values the actor loss, the PPO clipped surrogate objective (20] for each node selection we substitute the problem-level value for the node-specific value of the preceding partial tour. Formally, we minimize:
CLIP (0) E., [max (O), (e)
A,, Cr (0)
for on-policy tour t and node selection index i, where instead take the maximum term since minimizing cost c.. The ratio function rt,; is unchanged besides specifying the policy's 's node selection index. Note that do not add an entropy bonus since optimal edge selection is deterministic, and doing so may incentivize suboptimal infinite-cmppute performance, entangling the entropy objective with the model limitations we intend observe.
Modifying the critic loss to learn compositional values less straightforward since cost is defined only for complete solution. Transitioning from problem- node-level credit assignment resembles the transformation from top MDP to bottom MDP illustrated by Metz et al. [71 Because the return is shared between node selections within particular tour, the corresponding compositional value targets are identical as well. Our critic loss is then:
C (0) Ey, (c.))
theory, this loss still allows compositional value targets to diversify expectation. If rollouts from given partial tour usually result in low-cost solutions, the expected compositional value target is small, and the inverse also true. In preliminary experiments, compositional value learning appeared slightly more sample efficient compared to strictly learning problem-leve state values, motivating our selection of the former.
10Teei related work section provides useful introduction to other deep learning algorithms which address large discrete action spaces.
39

---

However, this distinction disappears when carefully controlling for other variables and averaging over several seeds, least for 30-node TSP. After initial transient effects, performance distributions are indistinguishable (Figure [7}. and we noticed that compositional value estimates vary little within a given tour. These findings are not surprising given the critic attempts learn granular values with coarse reward signal, an analogue to value estimation in sparsely rewarded MDP. Further, given tours are sampled on-policy for problems generated online, the critic sees each partial tour exactly once.
H Hyperparameter settings
Here we provide the hyperparameter (HP) settings used for model training (Table 7). along with how we determined them through hyperparameter optimization (HPO). We optimize HP selection for PPO experiments, but we also use the obtained settings for SFT experiments where applicable.
Critically, previous work suggests scaling law fits relatively insensitive model and algorithm HPs like Transformer model shape and learning rate decay [3. Within reasonable bounds, we do expect different HP settings severely alter the trends found in this paper long as training sufficiently converges.
Setting HPs effectively by hand would be tedious and rely heavily intuition. Reinforcement learning often involves more HPs than supervised learning, and setting model HPs for our custom architecture lacks the grounding of existing results. Algorithmic HPO has the added benefit of reducing wall-clock time that is required to reach sufficient convergence. With finite resources, unbottlenecked compute only be approximated in the scaling laws that require it. Some of our antuitioniinforme preliminary experiments required several million gradient updates (and multiple learning rate restarts) to sufficiently converge, dramatically slowing research flow. Our HPO- informed experiments converged well in less than half the gradient updates.
Table Hyperparameters used for RL mode-scaling experiments. Other experiments, including SFT training runs, default to these settings where applicable unless otherwise specified. After learning rate cosine decay finishes, RL runs switch to slow linear decay for the remainder of training.
Category
Name
Value
HPO-informed
Minibatch size
175
No
Minibatches
4
Yes
PPO
Ratio clip
0.17
Yes
Critic loss coefficient
0.52
Yes
Algorithm
Adam
No
Optimizer
Gradient norm clip
0.24
Yes
Max learning rate
9.37 x 10-5
Yes
Linear warm-up updates
3,000
No
Scheduler
Cosine decay finish update
170,000
Yes
Cosine decay floor
10.
No
Encoder layers
3
Yes
Policy decoder layers
2
Yes
Critic decoder layers
2
Yes
Model
Transformer width
184
Yes
Transformer feedforward
736
No
Transformer attention heads
No
Transformer dropout
0
No
H.1 HPO method
We use BOHB 72 implemented with Optuna 73 to optimize update efficiency for 50-node TSP. We truly wish to optimize serial-compute efficiency, so more strictly limit model depth, especially for the autoregressive policy decoder. We chose our maximum scale of nodes to optimize the slowest run, and because expect perf-perg HPs for harder TSP scales to generalize well
40

---

to smaller, easier scales. But HPs optimized for small scales may fail to converge on larger scales within the same update budget.
We chose BOHB for its balance of anytime and final performance 72 BOHB is no longer state- of-the-art in final performance but has comparable anytime performance 74 and is relatively easy to implement. We implemented BOHB using Optuna 3.5's multivariate Tree-structured Parzen Estimator (TPE) 775 for HP sampling (the Bayesian optimization "BO" in BOHB) paired with their Hyberband [76] pruning algorithm (the "HB" in BOHB). Table 8 details the HPs we used for the BOHB algorithm itself along with our evaluation setup. We found BOHB especially sensitive to the minimum gradient updates budgeted per trial. Setting this value too low results in pruning based on noise before initial convergence. Setting too high wastes a significant amount of time and compute.
Several HPs in Table 7 were fixed for various reasons. PPO minibatch size was maximized under GPU memory constraints for search space. The learning rate linear warm-up schedule was fixed to avoid incentivizing rapid ascents that are more likely to diverge. Cosine learning rate decay was selected because we observed other schedules like exponential decaying too quickly to sufficiently converge; this issue was also noted in related work [3. We fixed the learning rate decay floor to allow for subsequent linear decay to zero over the remainder of training. This design choice couples fast, HPO-informed early convergence with meticulous late-stage convergence that appears to better approximate the commite--cmpute performance limit.
Table MaleeGettene details our BOHB search space. We set relaxed bounds in preliminary attempts then trimmed unpromising regions. Runs often diverged when surpassing the reported upper bounds for max learning rate, gradient norm clip, and PPO ratio clip. GPU memory constraints limited model width's 's upper bound and our results suggest wider networks would perform better (Figure (Figure[[@top-leffeee top-left..
Lastly, we found that forcing a warm-start, human-intuition HP configuration for trial 0 allows BOHB to find high-performing regions of the search space considerably faster than when using only random startup trials.
H.2 BOHB results
summarizes the BOHB search results that were used to inform our HP selection. Using larger model widths, a tight range near 10-4 for max learning rate, and a small gradient norm clip less than 1 are most important for achieving high performance with fewer model updates. Convergence was particularly sensitive to gradient norm clip values greater than 1. In preliminary attempts without gradient clipping, pruning simply selected trials which most recently diverged.
Figure 18
PED-ANOVA importance ranking [77 was chosen over the more common f-ANOVA 78 algorithm as we found the latter to be overly sensitive to poor performing regions of HP space (attributing majority importance to gradient norm clip). PED-ANOVA importance quantifies HP's degree of influence in attaining a top quantile of performance [77], which we found produces a more balanced ranking that also roughly aligns with concentration of nigh-performing clusters. We used a top-0.22 quantile which computed the local HP importance of the top 7 of 32 complete trials.
Optuna tracks objective scores by the final value achieved at the maximum update budget, not the best value achieved over the trial, which poses a question of statistical significance in near-optimal improvements. For example, trial 300 had the best outcome with a suboptimality gap of 0.169 completion. But its minimum validation score over training was slightly below this at O. 166, though this happens to be the minimum score reported over all validations for all trials, which is encouraging. We evaluated the impact of our validation dataset size relative to these small performance deltas. This evaluation was performed retrospectively using the 50-node model from our main experiments since no checkpoints were saved during HPO. We rescored with 100 randomly sampled datasets of 10,000 problems each, obtaining a standard deviation of less than 0.003 suboptimality. The difference in suboptimality between the top two trials is over four standard deviations. Even comparing the final validation score of the top trial with the minimum score of the second-place trial returns a difference of over two standard deviations, demonstrating that our sample size is statistically meaningful assuming validation scores are normally distributed.
41

---

Table 8: BOHB algorithm and data settings. Remaining configurations use the defaults in Optuna 3.5.0. PPO minibatch size is fixed 144 due to GPU memory constraints, and Transformer feedforward dimensions are set at 4 modelt- Otherwise, non-HIPOiinformed settings match Table 7
Category
Name
Value
Trials
400
TSP nodes
50
Evaluation setup
Validation dataset size
10,000
Validation period (gradient updates)
100
Reduction factor
Hyperband pruner
Min gradient updates
1,000
Max gradient updates
100,000
Startup trials
10
TPE sampler
Multivariate KDE
True
Table 9: Experiment variables and corresponding search spaces for BOHB HPO. Continuous intervals
log- treetrrnsfor Transformer width's interval the minimum value for attention heads.
Category
Name
Min
Max
Interval
Minibatches
12
PPO
Ratio clip
0.05
0.2
0.01
Critic loss coefficient
0.1
2.0
0.01
Optimizer
Gradient norm clip
0.1
10
Continuous
Max learning rate
5 x 10
5 x 10
Continuous
Scheduler
Cosine decay finish update
100,000
500,000
1,000
Encoder layers
4
Policy decoder layers
2
Model
Critic decoder layers
12
Transformer width
96
192
42

---

Model width (ej 0.30)
Max learning rate (ej 0.16)
5x30"
144
30
0.375
06
Gradient norm clip fe@ 0.111
Policy decoder layers 0.11)
10'
0.325
Critic decoder layers (x2 0.11)
Critic coefficient (e]
0.08)
12
Suboptimality gap
0.275
PPO ratio clip [o] 0.05)
PPO minibatches (o] 0.04)
12
9.35
0225
9.15
Cosine decay finish update (u] = 0.03)
Encoder layers (s) 0.02)
60K
300k
200:
0.155
100k
0.164
200
200
Count
Search results BOHB HPO on 50-node TSP for each HP in the search space. Y-axis labels are placed above subplots for clarity. The bar plots show HP search frequency over either discrete (bar gaps) or binned (no bar gaps) ranges, referencing all 400 trials. The scatter plots illustrate the performance of these HP ranges through the final scores of non-outlier completed trials, similarly to the plot generated by Optuna's iisualization.plo. ploo_slicee( function. Random Y-jitter is added to the policy decoder layers and encoder layers scatter plots reduce point overlap. The best performing trial 300 is marked by diamond (the wholeness of this number is just coincidence and irrelevant to the HP sampling procedure). HPs are ranked by PED-ANOVA importance fi [77] descending order left to right, top to bottom. Note the distinctive clusters of nigh-performing (warmer) regions found over time for importaim HPs.
Figure 18:
43

---

I Proof of scaling relations and limits
Here we prove the node and spatial dimension scaling relations asserted in Section 4 mostly through extensions of existing analysis. We exclusively the term "tour length" rather than "cost" for these demonstrations to maintain precise language.
For node scaling in 2D TSP, simply show linear growth for both the expectation and variance of Haaeooodd--atto-aaaaaae
random tour length. The optimal tour length grows proportionally to / as oo.
Theorem 25 already shows that expected
For spatial dimension scaling with a fixed number nodes, we show that expected random tour length is strictly upper bounded by growth proportional to vd. We then show that expected random tour length itself grows proportionally vd as d 2o while random tour length variance and random tour suboptimality both approach constant value.
Lemma 1. Expected random tour length grows linearly w.r.t. n.
Proof. Assume node coordinates sampled within unit square such that each coordinate dimension is i.i.d. randomly sampled v; E [o. Vi:Vi (1,2). Let X; (P:4) [-111] 1] be the random variable describing the difference between nodes p and q along the 7th axis:
(p-9) x;
x (0)
Xi
The Euclidean norm between nodes p and q is then
X -
(v-9)
-
/ (x(x-2)
)= + (x2 (x(r-))
and deseribe the full length of a random tour through each sampled point as
|
X (p).
s.t. pk 9k-1, P1 Jn
| (p....) variable shares sampled coordinates with their adjacent edges in the sum, meaning || not sum independent variables. But these random edge norms are still identically distributed given that the choice of starting node pı is arbitrary. Thus,
Note that each |
E [
E
(p). nE [
MIXIIII
where 1ix is the expected Euclidean distance between arbitrary nodes p and q.
For the uniform coordinate sampling used in this paper, evaluating Раx analytically involves cumbersome quadruple integral for which several informal solutions can found online. The exact solution is
2 + V + 5mn(2++
Px
0.521
15
which our empirical approximates with trivial error.
Lemma 2. Variance of random tour length grows linearly w.r.f. n.
Proof. Because || is not a sum of independent random variables,
Var
|
+
Var
||X
(pu.st
Jom
44

---

This slightly complicates the proof. However, we can make use of the fact that dependencies are limited adjacent edge variables. We start with the following equation:
Var [| Var Σ | (m)
Cov (IIXI)
|X (1)
which is true for any sum of random variables
Since 1 only depends on | (Pt 1.f6
and | (p% 1.9k (1) (with circular indexing for edges {1, n)), all non-adjacent edge combinations
have zero covariance. Thus, the previous expression simplifies to
Cov (1IxI)/2000 (p..0.))
11 1.0h 11)
k=1
+ Cov [|XI] ( | (Pa.ew)
+ Cov
[| (mnmm))
||x||| (pk (
Given that covariances between adjacent edge lengths are identically distributed, we obtain
Var [ [13]
Σ
Var
Cov ( me)
|| b (0+
k=1
n Var (1xx1((r00) 2 Cov ( |
where (p.g, 8) denotes an arbitrary 3-node sequence in the tour with edges (p. q) and (g. s), and (g(n.).0)) is defined as the summation term obtained above.
Hence, the standard deviation of random tour length grows proportionally to vn, which our empirical results closely approximate (Figure Soauuee00ooppp top left, == 0.497).
We could not find existing solutions for ş g(maa.)) and make no attempt to evaluate ourselves. But our empirical fit suggests g(p.a.s) x 0.276 for uniform coordinate sampling.
Lemma 3. Expected random tour length w.r.t d upper bounded by a function proportional vd.
Proof. In a unit hypercube of d spatial dimensions consider fixed number of n nodes i.i.d. randomly sampled as previously described. First, we obtain the expected value of the square of the high- dimensional Euclidean norm between two random nodes:
E [
E
Σ
Xe
(p.9) x
d dE - ((x((e)))) = d =d
where n.* 10, 1] is the expected squared difference between p and q along an arbitrary spatial dimension axis. From the concave form of Jensen's 's Inequality, it follows that
E3 [ = = (IXIIS(00)
S sV [1
) dd
Thus,
E
X (P.0)
S Vdp
Note that Vd is the hypercube's maximal Euclidean norm, measuring from one corner to its farthest opposing corner. Hence the expected Euclidean distance between two randomly sampled nodes
Derived from the equality Var [Σ x.] = (E x.)² [Σ x.]
45

---

is bounded below that maximal length scaled by vHz2. Since Equation dimensions, extending this result to full tour length is simple:
generalizes to higher
EB [ E | ny dd
So.
[| S /n/u
If we wish to specify this bound for the uniform coordinate sampling used in this paper, it is straightforward to obtain naa directly from the continuous definition of expectation. Let f be (p) random variable's probability density function and p and w the integrand variables for x and x respectively. Then,
S.
Ma = E -
f(w)f())( - w)² dp du
Since f() and (w) are uniform between and 1, this simplifies to
222 L. I. (0 d L/¹ (wP-w- w + 1
du 6
Thus, for any TSP problem distribution in this paper,
d
B ||
m 6
We plot the difference between this upper bound and empirical ceceessoo-scaaling results in Interestingly, this gap also forms a smooth power law.
Figure
Bound for mean random tour length
n 10
n= 20
trend 0.53
10:1
10
10?
Spatial dimensions (d)
Figure 19: Upper bound for expected random tour length subtracted by observed means for both the 10-node and 20-node spatial dimension scaling experiments. Means evaluate 128,000 and 64,000 samples, respectively. This gap below the upper bound asymptotically decays toward zero (provably). Between node scales, decay rates are both close to square root power (a s 0.53) so increasing the number of nodes simply increases the proportionality constant from roughly 0.82 1.62. This notably close to the proportionality of node increase (doubling).
Theorem 4. Expected random tour length is proportional vd as d oc.
Proof. Extending existing analysis, it is simple to show that the previous upper bound becomes arbitrarily tight in the limit d co. Specifying the Euclidean norm case for the proof of Lemma 1 in François et al. 28 (Section 5.1.1), it directly follows that
X (p.4)
lim
P
Vd
12, = 2 the cited work. Our usage of p the norm starting node unrelated.
46

---

Borrowing Equation | once again, for the full tour length we obtain
X
E
E
|
(Pw))
E
[ (0.9]
lim 7000
lim d+000
72
lim d000c
n
Vd
vd
vd
or
2
lim
n
vd
For this paper's uniform coordinate sampling distribution, this becomes
|
12
lim
d0000
vd
V6
implying that the upper bound gaps observed Figure 19 inddedd converge toward zero.
Theorem 5. Variance of random tour length approaches constant value as d oc.
Proof. For this limit we extend Lemma 2 in François et al. (proved in Section 5.1.2 of their paper). For the Euclidean norm case, their Lemma shows
(a,=)
lim Var || X ( d-+00
where ar the standard deviation of (x)) 2 for an arbitrary spatial dimension. Since Equation 2 holds for higher dimensions,
Var [|]]
Var (1x11((000 Cov (1X11 (0-)) ||Ix1(()0))
[|]]]]]] lim Var (1XI1(11) d
lim Cov [|III|p10) .|Ix ( d0000
lim Var
d000
(1 ||x]((_)))
lim Cov d-vo0
(4)
4 4,,
now follow reasoning analogous to François et al.'s initial steps proving Lemma of their work, but for covariance instead of variance. By definition,
Cov (1X11( || 11
E [IXI]] E [IxI)()))
(Ix (1..>) E (1111(1000)
Thus, using the Fatou Lebeu-Le theorem move the limit inside expectation,
(11 (11x116600, (P.)) |X ((..))
lim d
Cov
[|XX] - [III1((00]
(IIII
E | (9.5)
E lim
(5)
We may rewrite the first product term
| (p.4)]
(Ii1I(b1)) 2 EE
|| [mve)
E
X (p.0)
E [
(
Vi
(6)
(p:4)
EE
X
(p.9)
|X (Pvz)
x (2.0)
va
Referencing Equation 3 along with François et al.'s intermediate step result from their Lemma proof, we know the limit of the denominator almost surely approaches constant:
(p.9)
R
|| (P
(
X
(p.a)
E
| (p:9)
lim d=
lim
lim
Vd
Vd
François al. at first describe 0,2 variance, but later in their proof show it be standard deviation.
47

---

and
||
(p-9)
P
lim
v122 =1
d-000
vd
SO
||
X 1
(P-0)
P lim
V V 2/
=
vd
vd
Meanwhile, the limit of the numerator of Equation that
is simplified using Equation again. First, note
(1x1(
||
Σ
(n-9))
| |
(p.g) 2
-B
Xk
k=
|| (p-2))
d
and since
||
(p-2)]
E | 11 (p.9)
E
|| 11
(p-2)]
2
lim d-000
lim d-+00
lim d0000
222
d
vd
vd
taking the limit and substituting yields
11 (n-1))
E
lim d0000
2 EE
||x
[2:0)]
lim
(x(rr))
d=000
d
k=1
(n-9)) X
lim d=
Mx2
k=1
Returning to Equation 5] notice that all analysis from Equation dlp until this point produces analogous results for the second product term [|XX][<>>
(g.0)
-
E
||
(g.*)
since ||_||[ (9.9) and ||
(g.s)
are
identically distributed. Thus,
((1X)15
TE || (p-r))
(111) (0.5)
| ((..))
lim d+00
(0000))) 2 ||x (
(111)())))
-_ ||
lim
V
V
d-+00
|
E.
|
| |||
E
Vd
Vi
Vd
Vid
(1X1I
- (
-
lim
d=
E ||X E (o
|X [
Vd
Vd
Va
and with probability
( " -=(1
lim
d=
[X ([
[X]](0.0)
E [|i])i
lim
lim d+ooo
vd +
d=+00
Vd
Vi
vdd
Σlm (xx(010))²
-p,3
Σj=n
(x ((/2)) -H,²
lim
d-+00
4 11.2
48

---

Here, the numerator differs slightly from that in the proof from François et al. given we are proving for covariance rather than variance. But we can still apply reasoning analogous to their remaining
1 (xx (xxx-1) M₂21 0.
steps. By the definition of covariance, and since E
Cov Σ
((121))) 1xx)
Σ
(x) (x)o)1)) Hx²
j=1
d
1121) ))
EE
X
(p.0)) 2 ) mx21
Σ
(x ) Hx2
|=1
[xx²) )
d
(x (p-9)
Σ
E
[x
-1a²
1=1
j=1
Σ
d
Xxx
)
(2-4)) 2
- m2²) ))
Σ
(x
(q:0)
- 11.2 ))
Thus,
E
d
( - m.2)
2 -M1e) ))
Σ
d
(xx
(x)) - Hxx)
(0.2)) 2
k=
j=l
Σ (xx))10) - 1x22
(x) (1)))) 2
= Cov
Σ
- -122
h=
5=1
d
(( - 1x2 -mx2)
(x)a 12,3)
Cov
k= 1=1
and since coordinates are independently sampled between dimensions,
((1 (xxx )2000)) 2 - 1x2) ((x. 2 - 1x22
ECon Cov
A=1
With the observation E (xxeerr) M2² covariance, we obtain
= 0 alongside another recursion through the definition of
2 - ((x( 12221
Σ Cov
(2200) 2 -1,22) ( (xxx (()))) )
2 - 11,21
E
2 - Mrz E (q.5)) 2 - Mx22 1)
E
(xlexe)
(xxm00)) - -m²) ((x ((xi (xx(ee0)2 2 - kx2z) -1²) -00
E
k=1
= d (p)
since the product inside the expected value is identically distributed for each summation term over d. We define this summation term as (vo(219.)))² 2 Condensing, we arrive at
d
M₂²) ))
Σ (1 (9:33) Mxx3 -1,2) ))] =d <(potann)))
E
Σ k=1
(p..))
(8)
49

---

Returning to Equation
5 we can now see that with probability 1,
lim
Cov [|X112
(x
E
lim
(11x))6 - TE [1x (x01( (117)/00) -
|
d=000
Σi= ((x(ar0))= - )
lim d=+00
E
via Eq. 7
4 22
Eiー (xxxx))) -1
( (xxa-1))-
lim
d-200
via Fatou Lebesge theorem
1622
d(plo-n1e))2
lim
d=+20
via Eq.
4 (spl1.8.8)) ?
4 12y2
Thus,
(plD)),ee) 27
P lim Cov (11II1611) (1
1
4 p2y
Referencing step 2 in François et al.'s proof of their Lemma the same reasoning shows
(so(p.9.01) 2
lim Cov (1I1) ||x]((1)))
d0o00
4 422
Finally, returning to Equation 4 obtains the desired result:
(0,2) +2 lim Cov (11 || /1x1)(00)) dooo0
lim do
Var |
= n
4 p,,
(o,²)
n
+ 2
4 4pp
4
(o,2)²
+ 2 (1p(p121s) 2
4 pb.²
We then evaluate (o and (fo(-99.)) for the uniform coordinate sampling used in this paper, like we did for paa after proving Lemma
(0 = S( Jo FW))(()( - w/ - dp = -1-- 1/' (10- ((--)}-1) ))²² dp dw 180
(ollanns)) So St I (())(W)NI w) mx2)((w - -)² - Mx 2x2) du dr
S/ (') (' (w- -/ ( (w-r)}²
7)² - ) dp dr
180
50

---

Plugging in values yields:
3
lim Var |||
d000
40
Evaluating for 10 and 20 nodes, respectively, we obtain variance limits of 3 and 2, translating to standard deviation limits of approximately 0.87 and 1.22. Our empirical results for standard deviation of random tour length Figure 20 very closely align.
18
D0 cost
5D best cost
866
1.0
85
n 10
Nodes (r)
Spatial dimensions
12.
(est Cost
50 test coot
1.
Nodes (n)
Spatial dimensions (d)
Random
2-exchange
Optimal
2.opt
RL
RL trend break
Figure 20: Standard deviation (SD) of cost over TSP node and spatial dimension scaling, shown for random, optimal, and algorithm distributions. Behavior of random tour length variance aligns with our analysis Lemma 2 and Theorem 5 Top left: Tour length SD for random performance and mediocre algorithms like 2-exchange diverge w.r.t. number of nodes. Bottom left: Tour length SD for sufficiently near-optimal distributions decreases w.r.t. nodes, implying optimal tours become more similar in length with increasing node density in the representation space (at least for 2D TSP). Right: Like random tour suboptimality, random tour variance w.r.t. spatial dimensions is roughly constant over the tested domain and provably constant in the limit (Theorem 5). All other distributions produce an increasing convergent trend.
The difference between expected random tour length and expected optimal tour length (random tour suboptimality) approaches a constant value as d + oc.
Theorem 6.
Proof. Here we leverage an existing derivation that bounds the limit of expected absolute contrast for fixed number of nodes. Taking the norm from an arbitrary query point to each node coordinate, absolute contrast defined as maximum difference between norms. Specifying the Fuclidean case for Corollary 2 in Aggarwal et al. 27 the bound can be formally described as follows:
A < lim d
max uEQ
X (p.a)
min ((.0)) .EQ
S (n 2))
where node p is our chosen query point is the of remaining nodes such that p & Q, and is non-negative constant. This bound applies to any node coordinate distribution satisfying i.i.d. sampling for each dimension.
Aggarwa et al. consistently use the origin as their query point but without loss of generality. Our upper bound term scaled (n account for removing node from the end point set Q.
51

---

Let || be defined as the length of the optimal tour between the sampled nodes, that which incurs minimum Euclidean distance:
|
X (Pa.st) S.t. Ph 9x- P1 4n
where node th forms the optimal subsequent edge from node Pk- Random tour suboptimality can the expected difference between random and optimal tour
then be expressed as IE X || length.
First, we extend Aggarwal al.'s Corollary upper bound the limit of random tour suboptimality, Let E Q be randomly selected node and let qº' Q form (p, q"), an optimal edge 13 It follows
that
| 2 (p:9)
||
I max ueQ
X
min X vEQ
|
(p.v)
lim E
X (v.4)
||
S lim E
max uEQ
X XX|
(p.w)
min X 11 (p.0)
(n
2
via Rel.
9
Repeating this reasoning with each node taking the perspective as the query point p then summing all inequalities yields:
lim
E
|
(pw-2e) - |
I n(n - 2)
Nmm
Because we know each limit inside the sum does not diverge sum:
we can bring the limit outside the
| (pu..e)) - ||x 1 (
Jim
S n2(n- 22)
| (PI-93)]
lim
E
E
S n(n - 2)A
Like each random edge, each optimal edge variable || choice of starting node Pı is arbitrary. Therefore, the above relation is equivalent to
(P5-95) (x is identically distributed given the
lim
||X|
- E [ - n 2)
lim
E
|
|
S
showing the desired upper bound. From here it is straightforward show a non-negative lower bound. By the definition of optimality,
|
X
S |
0 < X
0 < lim
E
| ||
Thus.
0 < lim E |X
||
S n(n 2)
d=+00
''Ecch node p has two alternatives for 9". but this choice does not affect the analysis. 'We can easily show each limit is lower bounded using the mirroring relation: || (( (x)")) 2 min X|| X|| (p.0) m ( (p.u)
52

---

In words, in the limit as d - 30, random tour suboptimality approaches a non non-negative constant value. The upper bound dependent on the number of nodes and, through X, dependent on the coordinate sampling distribution.
one can show E stricter bound
0 for arbitrary spatial dimensions, we could obtain the
c
lim E d+000
| - |
n(n 2)
for some 0 < S nn 2) where may be a function of n. For uniform coordinate sampling, this seems almost certainly true. Using Markov's inequality, would be sufficient show that for arbitrary spatial dimensions
P [1XXI -IXI 2 > 0
While intuitive, we forgo attempting a proof.
53


Reviews:
[{"review_id": "g3JDRZLEvm", "reviewer": "Reviewer_3C61", "summary": "The paper introduces complexity scaling laws: empirical laws that predict a fixed-capacity model’s sub-optimality as the problem (not the compute budget) grows. Using the Euclidean Traveling-Salesman Problem, the authors separate two axes of complexity—solution-space size (number of nodes) and representation-space size (embedding dimension). They show (i) classical neural scaling laws in this domain, and (ii) smooth, super-linear or bounded trends in sub-optimality as problem complexity increases, holding parameters constant. Comparable trends emerge from simple 2-opt local search, suggesting an interpretable link between learned inference and cost-landscape properties.", "questions": "How can you guarantee extrapolation of your conclusions beyond TSP?", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "strengths:\n1- Using TSP to evaluate scaling laws is interesting and, to me at least, a novel approach to investigate deep learning scaling. This can also enable better interpretability.\n2- Somewhat thorough evaluation.\n3- Open-dataset and code. \n\nweaknesses: My main skepticism is whether the conclusions truly transferable to more complex problems? TSP is a nice testbed but I am often skeptical of the utility of such theoretical investigations to real-world more complex cases.\n\nOverall though, I enjoyed reading the paper and find that it can be valuable in better understanding scaling - an important (if not the most important) aspect of modern DNNs.", "was_revised": true, "final_justification": "I found this paper to be interesting and novel and I maintain my positive review post-rebuttal.", "rebuttal": "Thank you for the review and for your thoughtful feedback. To the best of our knowledge, we are indeed first to investigate scaling laws using combinatorial optimization problems, which we hope will provide a useful testbed for exploring scaling law theory (both neural scaling and complexity scaling). Sharing our dataset and code is intended to assist in that pursuit.\n\n> My main skepticism is whether the conclusions are truly transferable to more complex problems? TSP is a nice testbed but I am often skeptical of the utility of such theoretical investigations to real-world more complex cases.\n\nWe agree that the applicability and utility of complexity scaling laws for real-world tasks is currently speculative. Beyond TSP, our results simply suggest that the complexity scaling laws hypothesis should be further explored. Complexity scaling laws can be argued as a general principle only *after* demonstrating they broadly apply to a diverse set of tasks, including those where solution space complexity and representation space complexity are not independently scalable.\n\n**We plan to make two revisions for the camera-ready version of the paper which further emphasize the importance of addressing this question in future work.**\n- Include specific examples of relevant future work at the end of the *Beyond TSP scaling* paragraph in Section 7.\n- Elaborating on “interpreting and relating findings between domains will be more difficult” in the beginning of the *Complexity scaling law theory* paragraph to more precisely specify those gaps (along with how future work can address them).\n\n> How can you guarantee extrapolation of your conclusions beyond TSP?\n\n**Guaranteeing generalization requires explaining the underlying behavior.** Extending the future work mentioned above, one potentially useful avenue would be identifying problems where smooth parameter-constrained complexity scaling laws emerge but with *different* scaling forms. For example, suppose that scaling nodes and spatial dimensions in the Convex Hull problem resulted in divergent linear growth and convergent power growth of suboptimality, respectively. A theory explaining these distinctions from TSP complexity scaling may explain some (or all) of the distinctions between TSP and next-token prediction."}, {"review_id": "dFdZxsiaer", "reviewer": "Reviewer_r11d", "summary": "This paper provides a neural-scaling analysis to task complexity by quantifying how solution quality degrades as (i) the TSP instance size grows and (ii) the embedding dimension increases.   Across extensive supervised and RL experiments on Euclidean TSP, error follows a power-law with node count and converges exponentially with dimensionality. Futhermore, this paper analyze with the classic 2-opt heuristic to mirror these trends.", "questions": "Listed above", "limitations": "Limitations are discussed in Section 7.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Pros:\n1. It is interesting to explore the scaling law in the context of COPs.\n2. The dataset of 128 million optimal TSP solutions will be helpful for future research.\n\nCons:\n1. The paper is relatively hard to understand.\n2. While the findings offer useful guidance for model capacity, they rest on a single benchmark ( Euclidean  TSP) and sparsely seeded runs, so the proposed \"complexity-scaling laws\" remain provisional for richer combinatorial tasks. \n3. Although this paper provides some insights, I feel like the empirical evidence is too limited and the comparisons too uneven to substantiate the strong, general claims made.\n- To make the 2-opt curves resemble those of the neural models, the authors cap the number of swaps. However, removing this cap will change the error trajectory entirely, so the observed similarity is an artifact of the experimental setup, which may not evidence that both methods share the same optimization landscape.  \n- The paper repeatedly infers that similar error curves imply shared underlying mechanisms and hence general laws.  It would be helpful to provide some theorectical justifications and  controlled counter-examples.\n4. Any justification for the relation between the TSP problem size and complexity?\n5. It would be better to conduct the significance tests and provide variance across seeds.", "was_revised": true, "final_justification": "The topic is novel, and it is indeed interesting to explore the scaling law in combinatorial optimization.\n\nOne limitation of this paper lies in the generality of the proposed scaling law, as also pointed out by Reviewer 3C61. As a researcher in combinatorial optimization, particularly on complex routing problems, I often encounter situations where conclusions that hold well for the very simple TSP break down completely when even a single constraint is added. I believe this is a fundamental concern that the current manuscript cannot fully address.\n\nIn addition, there are some concerns regarding the writing of the paper, although the authors promise substantial rewriting.\n\nFor these reasons, I lean toward a borderline rejection of this paper.", "rebuttal": "Thank you for the detailed review, this is useful feedback. We agree that exploring scaling laws using combinatorial optimization is interesting and we are excited for future work that can build on top of our dataset.\n\n> The paper is relatively hard to understand.\n\nClarity was a major consideration for the authors. Given that we rely on a combination of empirical evidence and analysis for several claims, there was a tension between readability and conciseness that was difficult to balance in the main paper. **Would you be willing to elaborate with example passages or claims that were unclear?** Further addressing these concerns and improving the readability of our paper would be a priority for us during camera-ready revisions. \n\n> While the findings offer useful guidance for model capacity, they rest on a single benchmark (Euclidean TSP) and sparsely seeded runs, so the proposed \"complexity-scaling laws\" remain provisional for richer combinatorial tasks.\n\nWe agree that the proposed “complexity scaling laws” remain provisional for richer combinatorial tasks, and we can further emphasize this point during revisions. **Focusing on Euclidean TSP as a case study allowed us to provide in-depth supporting analysis and reduced the compute required for model training.** We intended to answer whether the complexity scaling laws hypothesis should be further explored at all (to which we argue the answer is yes). Future work must demonstrate smooth suboptimality with respect to fundamental measures of complexity in other problems before complexity scaling laws can be argued as a general principle.\n\n**We propose two discussion revisions to further emphasize the limitations of using Euclidean TSP as a case study.**\n- Include specific examples of relevant future work at the end of the *Beyond TSP scaling* paragraph in Section 7.\n- Elaborating on “interpreting and relating findings between domains will be more difficult” in the beginning of the *Complexity scaling law theory* paragraph to more precisely specify those gaps (along with how future work can address them).\n\n> To make the 2-opt curves resemble those of the neural models, the authors cap the number of swaps. However, removing this cap will change the error trajectory entirely, so the observed similarity is an artifact of the experimental setup, which may not evidence that both methods share the same optimization landscape.\n\nWe intentionally sought a local search algorithm that reproduced the scaling forms of parameter-constrained models, arriving at depth-constrained 2-opt. The similarity is indeed dependent on the search depth constraint. **We argue that this approach is beneficial for informing future work on scaling law interpretability**, given that the depth constraint is critical for alignment when scaling nodes (and the relationship between performance and that depth constraint is interpretable).\n\n**It is also important to clarify that we are not claiming that Figure 5 provides evidence of a shared optimization landscape.** In the opening paragraph of Section 5: “These similarities do *not* directly imply that model inference and local search share underlying mechanisms. Instead, they provide potential topics to explore in future work, which we identify throughout this section.” We introduce Section 5 this way since the connections drawn are informal conjectures, and we attempt to appropriately scope related claims. By providing an interpretable reference algorithm with aligned complexity scaling behavior, these results and conjectures may help develop a formal theory for parameter-constrained deep learning in future work. **We will further clarify this purpose of the 2-opt experiments for the camera-ready version.**\n\n> The paper repeatedly infers that similar error curves imply shared underlying mechanisms and hence general laws. It would be helpful to provide some theoretical justifications and controlled counter-examples.\n\nIf this comment is referencing the local search analogy **in Section 5, we state that similar suboptimality curves do *not* directly imply shared underlying mechanisms** (see previous paragraph).\n\nRegarding Figure 3, when comparing RL and SFT, **we agree the term “law” can be misleading** (especially for those who are less familiar with neural scaling laws research) given 1) we do not understand the conditions that lead to that scaling form and 2) we do not understand the degree to which the model-capacity bottleneck is algorithm insensitive (our results suggest some degree of insensitivity, but compare only two algorithms with single-seeded runs, hence why we avoid claiming that is strong evidence for a general case).\n\n**We argue that this is a broader terminology concern** since both points above apply to neural scaling laws as well until the community arrives at consensus on theory explaining them. For a concrete example, Sorscher et al. [1] show that for data-constrained training an exponential decay of test error w.r.t. data can be achieved using data pruning. Thus, power law scaling w.r.t. data is not truly a “law” over arbitrary data distributions. We adopt the term for complexity scaling laws to make the connection to neural scaling laws immediately recognizable: simple macroscopic relationships that appear relatively insensitive to model and algorithm details.\n\nIt is also worth noting that several neural scaling law theories partially explain algorithm insensitivity (among gradient descent algorithms) for parameter-constrained convergence: resolution-limited underparameterized parameter scaling [2, 3] and model quanta capacity [4]. **Since our proposed complexity scaling laws are similarly underparameterized, it seems reasonable to hypothesize that RL and SFT node-scaling behavior share an underlying mechanism.**\n\nTheory and controlled counter-examples are important next steps for establishing stronger claims. Using data pruning as a reference counter-example for neural scaling laws, **we propose extending the *Complexity scaling law theory* paragraph (in Section 7) to suggest investigating counter-examples in problem complexity scaling as future work** (along with providing theory explaining the distinction in scaling regimes).\n\n> Any justification for the relation between the TSP problem size and complexity?\n\n**Would you be willing to clarify this question?** For example, do you mean the relationship between TSP node scale and solution space complexity? Or the relationship between solution space complexity and instance difficulty in TSP?\n\n> It would be better to conduct the significance tests and provide variance across seeds.\n\nWe agree that training on multiple seeds per run would be ideal, however, **this is a common shortcoming of neural scaling laws research.** Fitting a single seed per scale is typical due to both parallel compute requirements (many runs) and serial compute requirements (expensive runs). We detail compute requirements for this work in Appendix F. We are releasing our code in part to facilitate the reproduction and extension of our experiments using several seeds.\n\n**We have also performed jackknife (leave-one-out) resampling for node scaling, spatial dimension scaling, and parameter scaling regression fits. We plan to include relevant statistics in Appendix A of the camera-ready version.** Leave-one-out distributions are distinct from those obtained using multiple seeds. However, this addition documents each fit’s sensitivity to individual training runs. Node-scaling $\\alpha$ exponent fits are relatively sensitive to the suboptimalities obtained at the largest node scales (as expected). Otherwise, fitted constants have low variance. \n\nWe provide numerical results at the end of our rebuttal for Reviewer SbNi, if you would like to read the details. For the camera-ready version we also plan to report leave-one-out statistics for compute scaling and optimal model size regression fits.\n\n---\nReferences:\n1. Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond\nNeural Scaling Laws: Beating Power Law Scaling via Data Pruning. In *Advances in Neural Information Processing Systems*, 35:19523–19536, 2022.\n2. Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining\nNeural Scaling Laws. In *Proceedings of the National Academy of Sciences*, 121(27):e2311878121, 2024.\n3. Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. A Dynamical Model of Neural\nScaling Laws. In *Proceedings of the 41st International Conference on Machine Learning*, pages\n4345–4382, 2024.\n4. Eric Michaud, Ziming Liu, Uzay Girit, and Max Tegmark. The Quantization Model of Neural\nScaling. In *Advances in Neural Information Processing Systems*, 36:28699–28722, 2023."}, {"review_id": "La6qLkRJNR", "reviewer": "Reviewer_SbNi", "summary": "This work proposes scaling laws in terms of tasks and solutions in contrast to the common use of training settting details such as FLOPs or parameters. They demonstrate their process on a common graph based problem at multiple operating points. This analysis can serve as an alternative and complementary process in the development of agent-esque decision frameworks.", "questions": "Results appear to use a single seed per model size.  How stable are the fitted exponents across seeds?\nThe authors note the super-linear node law must “break” before ~40k cities. Can any empirical evidence beyond the small plotted frontier show where deviation begins?\nFigure 3 suggests SFT achieves the same gap with 3 times less compute. have the authors performed statistical tests or quantified intervals  to confirm this advantage is statistically reliable", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Principled and novel perspective on a salient problem in broader optimisation, particularly given recent concerns regarding the efficacy of PPO etc.\n- Method is thoroughly investigated with several operating points\n- Findings are well formed and explored deeply\n\nWeaknesses\n- I have some concerns about quantifying the solution space for real world problems akin to set shattering. Could the authors further qualify this point as a constraint to the work with respect to real world application.\n- Domain is narrow, though deep, broader insights are hindered, potentially if parameter size is fixed another synthetic investigation could be conducted", "was_revised": true, "final_justification": "I had already given a positive score, and outstanding points primarily serve to probe the broader application of the approach. As such, I maintain my score as I see little concern to change my current judgement.", "rebuttal": "Thank you for the review and your thoughtful connections and questions. We appreciate your recognition of the novelty and salience of our work, the rigor of our evaluations, and the depth to which we investigated this topic.\n\n> I have some concerns about quantifying the solution space for real world problems akin to set shattering. Could the authors further qualify this point as a constraint to the work with respect to real world application.\n\n**Would you be willing to elaborate on this request?** We are very interested in discussing how our work connects to approaches for quantifying solution spaces in real world problems.\n\n> Domain is narrow, though deep, broader insights are hindered, potentially if parameter size is fixed another synthetic investigation could be conducted.\n\nWe agree broader insights are hindered by focusing on Euclidean TSP. An important next step for future work is demonstrating that complexity scaling laws are more broadly applicable across domains. Evaluating similar combinatorial optimization problems is straightforward, but there is further value in determining how to evaluate real-world problems where solution space complexity and representation space complexity are not independently scalable.\n\n**We plan to make two revisions for the camera-ready version which further emphasize the importance of this future work.**\n- Include specific examples of relevant future work at the end of the *Beyond TSP scaling* paragraph in Section 7.\n- Elaborating on “interpreting and relating findings between domains will be more difficult” in the beginning of the *Complexity scaling law theory* paragraph to more precisely specify those gaps (along with how future work can address them).\n\n> The authors note the super-linear node law must “break” before ~40k cities. Can any empirical evidence beyond the small plotted frontier show where deviation begins?\n\n**We observe no sign of deviation at the evaluated node scales**, so we expect that scaling law to not break immediately after 50 nodes. We also do not expect the break to occur suddenly at ~40k nodes. So, to limit compute requirements, future work could empirically estimate where breakdown occurs using a binary search of that node space, perhaps in log-space to provide more resolution to smaller node scales which require less training. We can add a brief mention of this to the final paper.\n\n> Figure 3 suggests SFT achieves the same gap with 3 times less compute. have the authors performed statistical tests or quantified intervals to confirm this advantage is statistically reliable\n\n**Providing confidence intervals is difficult here given our single-seed compute limitations.** Figure 8 in Appendix B quantifies what this sample efficiency advantage looks like temporally (note that SFT’s plot has different x-axis scaling), demonstrating that the advantage is consistent over training. We believe this is an important piece of future work. After obtaining multi-seed results, one could measure the updates or compute required to reach successive target suboptimality scores, then provide confidence intervals for when those target scores are achieved, comparing between RL and SFT. We can add a summary of this future work proposal during revisions.\n\n> Results appear to use a single seed per model size. How stable are the fitted exponents across seeds?\n\nTraining on multiple seeds per run would be preferred, though this is a common shortcoming of neural scaling laws research due to computational constraints. To address this question, **we performed jackknife (leave-one-out) resampling for node scaling, spatial dimension scaling, and parameter scaling regression fits. We plan to include relevant statistics in Appendix A of the camera-ready version.** Leave-one-out distributions are distinct from those obtained using multiple seeds. However, this addition documents each fit’s sensitivity to individual training runs. Node-scaling $\\alpha$ exponent fits are relatively sensitive to the suboptimalities obtained at the largest node scales (as expected). Otherwise, fitted constants have low variance. **Numerical details are provided below.** For the camera-ready version we will also report leave-one-out statistics for compute scaling and optimal model size regression fits.\n\n---\nFor node scaling, when fixing the $\\gamma$ offset, we obtain RL $\\alpha$ exponents of $[1.86, 1.86, 1.86, 1.87, 1.85, 1.89, 1.83, 1.85, 1.95]$ compared to the full-data $\\alpha=1.86$ when holding out node scales of $[5, 10, …, 45]$, respectively. We obtain SFT $\\alpha$ exponents of $[1.69, 1.67, 1.69, 1.65, 1.72, 1.83]$ compared to the full-data $\\alpha=1.69$ when holding out node scales of $[5, 10, …, 30]$. Thus, $\\alpha$ is sensitive to values obtained at the largest node scales. Fitting the $\\gamma$ offset yields comparable results for both $\\alpha$ and $\\gamma$ over intermediate node scales but yields larger differences when holding out the edges; for example, $\\alpha=1.49$ for 5-node SFT and $\\alpha=2.22$ for 45-node RL. *However*, these fits shift the $\\gamma$ offset by 2-3 nodes and we *know* near optimality is achieved at 5 nodes (roughly $5 \\times 10^{-5}$ suboptimality for both RL and SFT).\n\nLeave-one-out fits for spatial dimension scaling and parameter scaling are quite stable. $\\beta$ asymptotes in the former are nearly constant (roughly ±0.001). Base $\\psi$ and exponent $\\alpha$ fits have the following mean and standard deviation of absolute difference (w.r.t. the full-data fit after ‘=’):\n- RL 10-node dimension scaling: $\\psi$=1.18 ± 0.005 (0.006 SD)\n- RL 20-node dimension scaling: $\\psi$=1.66 ± 0.016 (0.017 SD)\n- RL parameter scaling: $\\alpha$=0.582 ± 0.008 (0.011 SD)\n- SFT parameter scaling: $\\alpha$=0.712 ± 0.012 (0.011 SD)"}, {"review_id": "vU7J07kc2c", "reviewer": "Reviewer_8w55", "summary": "Using the TSP as a target problem, this study extends existing work on data, parameter, and compute scaling laws to scaling laws based on problem complexity. The problem complexity is varied along both solution space size and input space size. For both SFT and RL trained models, the suboptimality gap smoothly decays approximately according to a power law with more model parameters or more compute. The authors find superlinear suboptimality growth with problem size, but plateauing suboptimality growth with spatial dimensions.", "questions": "Does your work point to any data / compute / problem size regimes where deep learning approaches to solving TSP would be practically useful in some sense?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. When comparing the neural laws with local search laws, there are interpretable findings and interesting hypotheses (e.g. similarity of cost landscapes when neural models have constrained capacity).\n2. Rigorous and reasonable experimental setup.\n3. Release of the TSP solution datasets would be a good contribution.\n4. Good discussion of results in the context of other neural scalings laws. It is quite interesting that SFT and RL here both scale according to power laws, and that for RL the scaling is with respect to the used reward metric.\n5. Very interesting discussion that is grounded in theory of how superlinearity of suboptimality gap in number of nodes must end at some point, meaning that fit scaling laws would be pessimistic at large problem sizes. In general, nice theoretical results that are relevant to the empirical analysis.\n\nWeaknesses:\n1. The studied model and problem (TSP) is not that relevant to the rest of the deep learning literature. Even when considering prior works on deep learning for TSP, there are a few changes to e.g. the Kool et al. model that make it difficult to compare with prior work there.", "was_revised": true, "final_justification": "Great work overall, and my questions are generally answered. accept!", "rebuttal": "Thank you for the detailed review and your thorough decomposition. We appreciate your recognition of the interest and interpretability of our findings, the rigor of our evaluations, and the value of our dataset for future work.\n\n> Good discussion of results in the context of other neural scaling laws. It is quite interesting that SFT and RL here both scale according to power laws, and that for RL the scaling is with respect to the used reward metric.\n\nWe are also interested in the similarity of the RL/SFT curves and would be excited about future work further evaluating algorithm insensitivity under model capacity bottleneck.\n\nTasks often don’t support scaling laws for RL directly w.r.t. return, making TSP (and speculatively, combinatorial optimization at large) a great testbed for researchers who want to study return as a natural performance metric.\n\n> The studied model and problem (TSP) is not that relevant to the rest of the deep learning literature. Even when considering prior works on deep learning for TSP, there are a few changes to e.g. the Kool et al. model that make it difficult to compare with prior work there.\n\nWe agree that the model architecture presents such challenges. We explain the motivation and discuss design details in Appendix G (due to space limitations in the main paper). We also provide hyperparameter optimization results in Appendix H and are open sourcing the code to help mitigate these concerns.\n\n> Does your work point to any data / compute / problem size regimes where deep learning approaches to solving TSP would be practically useful in some sense?\n\n**We plan to add a short *Practical implications* paragraph to the discussion in the camera-ready version to address this important question.**\n\nAlgorithms that excel at solving TSP usually excel at other *routing problems* like the Vehicle Routing Problem (VRP) and Orienteering Problem (OP) [1], where the Kool et al. paper briefly introduces the relevance of routing problems to real-world problems. More recent work integrating the advantages of classical Operations Research (OR) algorithms with deep learning also emphasizes practical application [2].\n\nRegarding parameter-constrained complexity scaling laws, we foresee some practical use cases, although they take more consideration to identify given that training until convergence is usually compute-inefficient. One use case would be predicting the limit of performance when primarily constrained by model size, e.g. edge applications requiring very fast inference.\n\n---\nReferences:\n1. Wouter Kool, Herke van Hoof, and Max Welling. Attention, Learn to Solve Routing Problems! In\n*International Conference on Learning Representations*, 2019.\n2. Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep Policy Dynamic Programming for Vehicle Routing Problems. In *International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research*, 2022."}]

Author rebuttal:

Meta-review: This paper proposes the study of complexity scaling laws in deep learning for combinatorial optimization, using the Euclidean traveling salesperson problem (TSP) as a testbed. More specifically, the authors separate solution-space and representation-space complexity, showing empirical suboptimality trends under parameter constraints. Finally, the paper also provides an analysis of parameter-constrained scaling laws through an interesting examination of local search.

This is an interesting and novel paper. Reviewers specifically noted the excellent presentation and the very extensive and rigorous experiments to assess their scaling laws, which I strongly commend the authors for. The reviewers and authors also had a productive discussion, clarifying minor points on the numerical analysis or instance generation. The main limitation identified, however, was the restricted scope of experiments, with concerns that conclusions may not generalize beyond the relatively simple Euclidean TSP.  Thus, although most reviewers leaned positively, the paper was still sitting on a borderline score.

After carefully considering the review reports and re-reading the paper, I agree with the positive comments and believe this is an exceptionally well-executed study and a good fit for NeurIPS. In particular, rarely scaling laws have been studied in such a depth, and the TSP presents a nice case study with well-known (but complex) structure that allows for a first study of this form. The extensive numerical reports and reproducibility in sharing code are also a plus here.

I do, however, share the concern with reviewer r11d that the reliance on the Euclidean TSP as the sole testbed represents a limitation; it would be important if authors could include this in their discussion, and I do encourage the authors to extend their framework to more complex problem classes in the future.
Decision: Accept (poster)