Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimization

📄 arXiv: 2602.02188v1 📥 PDF

作者: Xia Jiang, Jing Chen, Cong Zhang, Jie Gao, Chengpeng Hu, Chenhao Zhang, Yaoxin Wu, Yingqian Zhang

分类: cs.AI

发布日期: 2026-02-02

💡 一句话要点

提出NLCO基准，评估LLM在自然语言组合优化问题中的推理能力

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 组合优化 自然语言推理 基准数据集 约束求解

📋 核心要点

  1. 现有方法难以评估LLM在复杂约束下的组合优化推理能力，缺乏专门的评测基准。
  2. NLCO基准通过自然语言描述的组合优化问题，直接评估LLM生成离散解的能力，无需代码或外部工具。
  3. 实验表明，LLM在小规模问题上表现良好，但随着问题规模增大，可行性和解的质量显著下降。

📝 摘要（中文）

大型语言模型（LLM）在数学和逻辑推理方面表现出强大的能力，但它们处理组合优化（CO）问题的能力——即在硬约束下搜索高维解空间——仍未得到充分探索。为了弥补这一差距，我们引入了NLCO，一个自然语言组合优化基准，用于评估LLM在端到端CO推理方面的能力：给定一个语言描述的决策场景，模型必须输出一个离散解，而无需编写代码或调用外部求解器。NLCO涵盖了43个CO问题，并使用变量类型、约束族、全局模式和目标类的四层分类法进行组织，从而实现细粒度的评估。我们提供了求解器注释的解决方案，并通过可行性、解的最优性和推理效率全面评估LLM。对各种现代LLM的实验表明，高性能模型在小型实例上实现了强大的可行性和解的质量，但随着实例规模的增长，两者都会下降，即使使用更多的tokens进行推理也是如此。我们还观察到跨分类法的系统性影响：基于集合的任务相对容易，而图结构问题和瓶颈目标会导致更频繁的失败。

🔬 方法详解

问题定义：论文旨在评估大型语言模型（LLM）在解决自然语言描述的组合优化（CO）问题时的推理能力。现有的LLM评估方法通常侧重于数学或逻辑推理，缺乏对复杂约束下高维解空间搜索能力的考察。此外，现有方法通常需要LLM生成代码或调用外部求解器，无法直接评估其端到端的推理能力。

核心思路：论文的核心思路是构建一个名为NLCO的基准数据集，该数据集包含一系列自然语言描述的CO问题，要求LLM直接输出离散解，而无需编写代码或调用外部求解器。通过评估LLM在NLCO上的表现，可以更全面地了解其在复杂约束下的组合优化推理能力。

技术框架：NLCO基准数据集包含43个CO问题，并采用四层分类法进行组织：变量类型（例如，集合、序列、图），约束族（例如，容量约束、分配约束），全局模式（例如，覆盖、划分），以及目标类（例如，最小化成本、最大化利润）。每个问题都提供求解器注释的解决方案，用于评估LLM生成解的可行性和最优性。评估过程包括可行性评估、解的最优性评估和推理效率评估。

关键创新：NLCO基准的主要创新在于其自然语言描述的CO问题，以及端到端的评估方式。与传统的CO问题求解方法不同，NLCO直接评估LLM的推理能力，而无需依赖外部工具。此外，NLCO的四层分类法可以实现细粒度的评估，从而更深入地了解LLM在不同类型的CO问题上的表现。

关键设计：NLCO数据集中的每个问题都包含一个自然语言描述的场景，以及相应的约束条件和目标函数。问题的规模可以调整，以评估LLM在不同规模问题上的表现。评估指标包括可行性（生成的解是否满足所有约束条件）、解的最优性（生成的解与最优解的差距）和推理效率（生成解所需的时间）。论文还研究了不同类型的LLM（例如，不同大小的模型、不同架构的模型）在NLCO上的表现。

📊 实验亮点

实验结果表明，高性能LLM在小规模NLCO问题上表现出较强的可行性和解的质量，但随着问题规模的增长，性能显著下降。例如，即使增加推理tokens的数量，性能提升也有限。此外，实验还发现，LLM在处理基于集合的任务时相对容易，而在处理图结构问题和瓶颈目标时更容易失败。

🎯 应用场景

该研究成果可应用于评估和改进LLM在现实世界决策问题中的应用，例如资源分配、调度优化、供应链管理等。通过NLCO基准，可以更好地了解LLM在复杂约束下的推理能力，并指导LLM的设计和训练，使其能够更好地解决实际问题。

📄 摘要（原文）

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.