用组合优化问题研究模型复杂度与性能的关系，发现性能可预测。
Complexity Scaling Laws for Neural Models using Combinatorial Optimization
- 以旅行商问题为例，基于解空间和表示空间大小构建复杂度缩放定律。
- 固定模型规模下，节点数或空间维度增加时，次优性增长规律明确。
- 不依赖可解释损失函数，适用于强化学习与监督微调等多种训练方式。
近期神经网络缩放定律研究表明，模型性能可随计算资源、模型规模和数据集规模进行可预测的提升。本文基于问题复杂度构建新的缩放定律，分析了两个基本复杂度度量：解空间大小与表示空间大小。以旅行商问题（TSP）为案例，我们发现组合优化带来平滑的成本变化趋势，因此即便在缺乏可解释损失函数的情况下，仍能获得有意义的缩放规律。进一步表明，对于固定规模的模型，当扩展TSP节点数量或空间维度时，次优性增长具有可预测性，且不受训练方式（强化学习或静态数据上的监督微调）影响。最后通过类比局部搜索中的问题复杂度缩放，说明对成本景观进行简单的梯度下降也能产生类似趋势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。