评测大模型在自然语言组合优化中的推理能力，发现规模增大时性能显著下降。
Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimization
- 构建自然语言组合优化基准NLCO，评估模型端到端求解离散问题的能力。
- 小规模问题下高分模型可行性和最优性良好，但规模扩大后性能明显下滑。
- 图结构任务和瓶颈目标更难，集合类问题相对容易，适合关注推理鲁棒性的研究者。
尽管大语言模型在数学与逻辑推理上表现优异，其在组合优化（CO）——即在高维解空间中满足硬约束地搜索最优解——方面的能力仍鲜有研究。为此，我们提出NLCO：一个自然语言组合优化基准，用于评估模型在给定语言描述的决策场景中输出离散解的能力，无需编写代码或调用外部求解器。NLCO涵盖43个组合优化问题，采用四层分类体系（变量类型、约束族、全局模式、目标类别），支持细粒度评估。我们提供带求解器标注的解，并从可行性、解的最优性与推理效率三方面全面评估现代大模型。实验显示，高性能模型在小规模实例上具备良好可行性和解质量，但随着实例规模增加，即使增加推理上下文长度，性能仍持续下降。此外，在分类体系中观察到系统性差异：集合类任务较易，而图结构问题和瓶颈型目标导致更高失败率。
原文摘要 · Abstract (English)
While large language models (LLMs) have shown strong performance in math and logic reasoning, their ability to handle combinatorial optimization (CO) -- searching high-dimensional solution spaces under hard constraints -- remains underexplored. To bridge the gap, we introduce NLCO, a \textbf{N}atural \textbf{L}anguage \textbf{C}ombinatorial \textbf{O}ptimization benchmark that evaluates LLMs on end-to-end CO reasoning: given a language-described decision-making scenario, the model must output a discrete solution without writing code or calling external solvers. NLCO covers 43 CO problems and is organized using a four-layer taxonomy of variable types, constraint families, global patterns, and objective classes, enabling fine-grained evaluation. We provide solver-annotated solutions and comprehensively evaluate LLMs by feasibility, solution optimality, and reasoning efficiency. Experiments across a wide range of modern LLMs show that high-performing models achieve strong feasibility and solution quality on small instances, but both degrade as instance size grows, even if more tokens are used for reasoning. We also observe systematic effects across the taxonomy: set-based tasks are relatively easy, whereas graph-structured problems and bottleneck objectives lead to more frequent failures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。