Complexity Scaling Laws for Neural Models using Combinatorial Optimization
This work provides incremental insights into scaling laws for combinatorial optimization problems, relevant for researchers in neural networks and optimization.
The paper tackles the problem of developing scaling laws based on problem complexity for neural models, using the Traveling Salesman Problem as a case study, and shows that suboptimality grows predictably when scaling nodes or dimensions, with results independent of training method.
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.