Complexity Scaling Laws for Neural Models using Combinatorial Optimization

• URL: http://arxiv.org/abs/2506.12932v1
• Date: Sun, 15 Jun 2025 18:20:35 GMT
• Title: Complexity Scaling Laws for Neural Models using Combinatorial Optimization
• Authors: Lowell Weissman, Michael Krumdick, A. Lynn Abbott,
• Abstract summary: We develop scaling laws based on problem complexity.<n>We analyze two fundamental complexity measures: solution space size and representation space size.<n>We show that optimization promotes smooth cost trends, and therefore meaningful scaling laws can be obtained even in the absence of an interpretable loss.
• Score: 3.4585775092874163
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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.

Related papers

• Unified Scaling Laws for Compressed Representations [69.72517034565467]
  We investigate whether a unified scaling framework can accurately predict model performance when training occurs over various compressed representations.<n>Our main finding is demonstrating both theoretically and empirically that there exists a simple "capacity" metric.<n>We extend our formulation to directly compare the accuracy potential of different compressed formats, and to derive better algorithms for training over sparse-quantized formats.
  arXiv  Detail & Related papers  (2025-06-02T16:52:51Z)
• Communication-Efficient Language Model Training Scales Reliably and Robustly: Scaling Laws for DiLoCo [22.7130140114906]
  We study the scaling law behavior of DiLoCo when training LLMs under a fixed compute budget.<n>We find that DiLoCo scales both predictably and robustly with model size.<n>When well-tuned, DiLoCo scales better than data-parallel training with model size, and can outperform data-parallel training even at small model sizes.
  arXiv  Detail & Related papers  (2025-03-12T20:04:38Z)
• Optimizing Sequential Recommendation Models with Scaling Laws and Approximate Entropy [104.48511402784763]
  Performance Law for SR models aims to theoretically investigate and model the relationship between model performance and data quality.<n>We propose Approximate Entropy (ApEn) to assess data quality, presenting a more nuanced approach compared to traditional data quantity metrics.
  arXiv  Detail & Related papers  (2024-11-30T10:56:30Z)
• Information-Theoretic Foundations for Neural Scaling Laws [20.617552198581024]
  We develop information-theoretic foundations for neural scaling laws. We observe that the optimal relation between data and model size is linear, up to logarithmic factors.
  arXiv  Detail & Related papers  (2024-06-28T02:20:54Z)
• Observational Scaling Laws and the Predictability of Language Model Performance [51.2336010244645]
  We propose an observational approach that bypasses model training and instead builds scaling laws from 100 publically available models. We show that several emergent phenomena follow a smooth, sigmoidal behavior and are predictable from small models. We show how to predict the impact of post-training interventions like Chain-of-Thought and Self-Consistency as language model capabilities continue to improve.
  arXiv  Detail & Related papers  (2024-05-17T17:49:44Z)
• More Compute Is What You Need [3.184416958830696]
  We propose a new scaling law that suggests model performance depends mostly on the amount of compute spent for transformer-based models. We predict that (a) for inference efficiency, training should prioritize smaller model sizes and larger training datasets, and (b) assuming the exhaustion of available web datasets, scaling the model size might be the only way to further improve model performance.
  arXiv  Detail & Related papers  (2024-04-30T12:05:48Z)
• A Dynamical Model of Neural Scaling Laws [79.59705237659547]
  We analyze a random feature model trained with gradient descent as a solvable model of network training and generalization. Our theory shows how the gap between training and test loss can gradually build up over time due to repeated reuse of data.
  arXiv  Detail & Related papers  (2024-02-02T01:41:38Z)
• An Information-Theoretic Analysis of Compute-Optimal Neural Scaling Laws [24.356906682593532]
  We study the compute-optimal trade-off between model and training data set sizes for large neural networks. Our result suggests a linear relation similar to that supported by the empirical analysis of chinchilla.
  arXiv  Detail & Related papers  (2022-12-02T18:46:41Z)
• Scaling up the self-optimization model by means of on-the-fly computation of weights [0.8057006406834467]
  This work introduces a novel implementation of the Self-Optimization (SO) model that scales as $mathcalOleft(N2right)$ with respect to the number of nodes $N$. Our on-the-fly computation paves the way for investigating substantially larger system sizes, allowing for more variety and complexity in future studies.
  arXiv  Detail & Related papers  (2022-11-03T10:51:25Z)
• A Solvable Model of Neural Scaling Laws [72.8349503901712]
  Large language models with a huge number of parameters, when trained on near internet-sized number of tokens, have been empirically shown to obey neural scaling laws. We propose a statistical model -- a joint generative data model and random feature model -- that captures this neural scaling phenomenology. Key findings are the manner in which the power laws that occur in the statistics of natural datasets are extended by nonlinear random feature maps.
  arXiv  Detail & Related papers  (2022-10-30T15:13:18Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  This work demonstrates a simple approach to reduce the computational and memory complexity of a large class of structured models. Experiments with neural parameterized structured models for language modeling, polyphonic music modeling, unsupervised grammar induction, and video modeling show that our approach matches the accuracy of standard models at large state spaces.
  arXiv  Detail & Related papers  (2022-01-08T00:47:50Z)
• Scaling Laws for Neural Language Models [14.472857826717613]
  We study scaling laws for language model performance on the cross-entropy loss. The loss scales as a power-law with model size, dataset size, and the amount of compute used for training.
  arXiv  Detail & Related papers  (2020-01-23T03:59:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.