{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/136879"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/136879","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Complexity Scaling Laws for Neural Models using Combinatorial Optimization","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Weissman, Lowell Meyer"],"institution":"Virginia Tech","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Computer Engineering","degree_department":"Electrical and Computer Engineering","school":null,"contributors":[],"advisors":[],"committee_chairs":["Abbott, Amos L."],"committee_members":["Jia, Ruoxi","Jin, Ming"],"year":2025,"date_issued":"2025-07-22","date_published":"2025-07-22","updated_at":"2026-07-22T22:19:56Z","subjects":["Scaling Laws","Problem Complexity","Traveling Salesman Problem"],"languages":["en"],"rights":["Creative Commons Attribution-NonCommercial 4.0 International"],"rights_urls":["http://creativecommons.org/licenses/by-nc/4.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:44338"],"render_values":[{"text":"vt_gsexam:44338","href":null,"code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/10919/136879","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeechair","label":"Committee Chair","values":["Abbott, Amos L."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Jia, Ruoxi","Jin, Ming"]},{"key":"dc:contributor.department","label":"Department","values":["Electrical and Computer Engineering"]},{"key":"dc:creator","label":"Author","values":["Weissman, Lowell Meyer"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-07-23T08:00:48Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-07-23T08:00:48Z"]},{"key":"dc:date.issued","label":"Date","values":["2025-07-22"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Scaling Laws","Problem Complexity","Traveling Salesman Problem"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Creative Commons Attribution-NonCommercial 4.0 International"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://creativecommons.org/licenses/by-nc/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:44338"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10919/136879"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.abstractgeneral","label":"General Abstract","values":["In recent years, artificial intelligence (AI) has rapidly become more powerful and generalized. Much of this progress arises simply from scale. For example, ChatGPT's digital brain has hundreds of billions or even trillions of learnable parameters, orders of magnitude more than state-of-the-art AI models a few years earlier. ChatGPT also learned from hundreds of gigabytes of training examples using a multi-million dollar supercomputer setup. Despite the intricacies of this learning process, scaling its inputs usually improves AI model performance predictably, often with surprisingly simple trends. These trends have been called neural scaling laws. Neural scaling laws predict AI performance on a specific task while scaling the AI learning process. In this thesis, we predict AI performance while scaling the difficulty of the task. We call these trends complexity scaling laws. Using the Traveling Salesman Problem (TSP) as a case study, we show that complexity scaling laws emerge for two fundamental measures of task difficulty: the number of possible solutions a task presents, and the intricacy of the task representation. This work is an initial step toward predicting AI performance as a function of both the inputs to the learning process and the difficulty of the task."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science"]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["ETD"]},{"key":"dc:title","label":"Title","values":["Complexity Scaling Laws for Neural Models using Combinatorial Optimization"]}]}],"canonical_facts":{"dc:contributor.committeechair":["Abbott, Amos L."],"dc:contributor.committeemember":["Jia, Ruoxi","Jin, Ming"],"dc:contributor.department":["Electrical and Computer Engineering"],"dc:creator":["Weissman, Lowell Meyer"],"dc:date.accessioned":["2025-07-23T08:00:48Z"],"dc:date.available":["2025-07-23T08:00:48Z"],"dc:date.issued":["2025-07-22"],"dc:description.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."],"dc:description.abstractgeneral":["In recent years, artificial intelligence (AI) has rapidly become more powerful and generalized. Much of this progress arises simply from scale. For example, ChatGPT's digital brain has hundreds of billions or even trillions of learnable parameters, orders of magnitude more than state-of-the-art AI models a few years earlier. ChatGPT also learned from hundreds of gigabytes of training examples using a multi-million dollar supercomputer setup. Despite the intricacies of this learning process, scaling its inputs usually improves AI model performance predictably, often with surprisingly simple trends. These trends have been called neural scaling laws. Neural scaling laws predict AI performance on a specific task while scaling the AI learning process. In this thesis, we predict AI performance while scaling the difficulty of the task. We call these trends complexity scaling laws. Using the Traveling Salesman Problem (TSP) as a case study, we show that complexity scaling laws emerge for two fundamental measures of task difficulty: the number of possible solutions a task presents, and the intricacy of the task representation. This work is an initial step toward predicting AI performance as a function of both the inputs to the learning process and the difficulty of the task."],"dc:description.degree":["Master of Science"],"dc:format.medium":["ETD"],"dc:identifier.other":["vt_gsexam:44338"],"dc:identifier.uri":["https://hdl.handle.net/10919/136879"],"dc:language.iso":["en"],"dc:publisher":["Virginia Tech"],"dc:rights":["Creative Commons Attribution-NonCommercial 4.0 International"],"dc:rights.uri":["http://creativecommons.org/licenses/by-nc/4.0/"],"dc:subject":["Scaling Laws","Problem Complexity","Traveling Salesman Problem"],"dc:title":["Complexity Scaling Laws for Neural Models using Combinatorial Optimization"],"dc:type":["Thesis"],"thesis:degree_discipline":["Computer Engineering"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:56Z"}