Complexity Scaling Laws for Neural Models using Combinatorial Optimization

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.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Engineering

Department dc:contributor.department

Electrical and Computer Engineering

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2025

Author dc:creator

• Weissman, Lowell Meyer

Chair dc:contributor.committeechair

• Abbott, Amos L.

Committee members dc:contributor.committeemember

• Jia, Ruoxi
• Jin, Ming

• Scaling Laws
• Problem Complexity
• Traveling Salesman Problem

Statement dc:rights

• Creative Commons Attribution-NonCommercial 4.0 International

Licence dc:rights.uri

• http://creativecommons.org/licenses/by-nc/4.0/

Language dc:language.iso

en

Dc Identifier Other

vt_gsexam:44338

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/136879