组合与约束世界中的推理：以自然语言组合优化对LLM进行基准评测

尽管大语言模型（LLM）在数学与逻辑推理上表现出色，其处理组合优化（CO）——在硬约束下搜索高维解空间——的能力仍鲜有研究。为弥合这一差距，我们提出NLCO这一自然语言组合优化（Natural Language Combinatorial Optimization）基准，评测LLM的端到端CO推理：给定以语言描述的决策场景，模型必须在编写代码或调用外部求解器的情况下输出离散解。NLCO涵盖43个CO问题，并按变量类型、约束族、全局模式与目标类别构成四层分类体系，支持细粒度评测。我们提供由求解器标注的解答，并从可行性、解的最优性与推理效率三方面对LLM进行全面评估。对众多现代LLM的实验显示，高性能模型在小规模实例上能达到较强的可行性与解质量，但随着实例规模增大两者都退化，即便使用更多token进行推理也是如此。我们还观察到跨分类体系的系统性效应：集合类任务相对容易，而图结构问题与瓶颈类目标更常导致失败。