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

arXiv: https://arxiv.org/abs/2602.02188 · HTML: https://mlsanity.com/paper/2602.02188/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Mathematical reasoning, one of 17 directions in LLM reasoning.
- Builds on 14 of its 108 references that are in the map.
- First posted on arXiv 2 Feb 2026.

## Placed in

- LLM reasoning / [Mathematical reasoning](https://mlsanity.com/lr/mathematical-reasoning/)

## Builds on (most cited first, 14 of 14)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [DeepSeek-V3.2: Pushing the Frontier of Open Large Language Models](https://mlsanity.com/paper/2512.02556/) (2025)
- [LogiQA: A Challenge Dataset for Machine Reading Comprehension with Logical Reasoning](https://mlsanity.com/paper/2007.08124/) (2020)
- [A Survey on Large Language Model Benchmarks](https://mlsanity.com/paper/2508.15361/) (2025)
- [AutoLogi: Automated Generation of Logic Puzzles for Evaluating Reasoning Abilities of Large Language Models](https://mlsanity.com/paper/2502.16906/) (2025)
- [CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization](https://mlsanity.com/paper/2504.04310/) (2025)
- [Large Language Models for Combinatorial Optimization: A Systematic Review](https://mlsanity.com/paper/2507.03637/) (2025)
- [ProBench: Benchmarking Large Language Models in Competitive Programming](https://mlsanity.com/paper/2502.20868/) (2025)
- [Starjob: Dataset for LLM-Driven Job Shop Scheduling](https://mlsanity.com/paper/2503.01877/) (2025)
- [FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2505.16952/) (2025)
- [GraphThought: Graph Combinatorial Optimization with Thought Generation](https://mlsanity.com/paper/2502.11607/) (2025)
- [XCSP3: An Integrated Format for Benchmarking Combinatorial Constrained Problems](https://mlsanity.com/paper/1611.03398/) (2016)

## Built on by (most cited first, 9 of 9)

- [FrontierOR: Benchmarking LLMs' Capacity for Efficient Algorithm Design in Large-Scale Optimization](https://mlsanity.com/paper/2605.25246/) (2026)
- [Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers](https://mlsanity.com/paper/2605.12421/) (2026)
- [OptSkills: Learning Generalizable Optimization Skills from Problem Archetypes via Cluster-Based Distillation](https://mlsanity.com/paper/2605.29829/) (2026)
- [Beyond Objective Equivalence: Constraint Injection for LLM-Based Optimization Modeling on Vehicle Routing Problems](https://mlsanity.com/paper/2606.04816/) (2026)
- [ORAgentBench: Can LLM Agents Solve Challenging Operations Research Tasks End to End?](https://mlsanity.com/paper/2606.19787/) (2026)
- [SCHEDBench: A Benchmark for Evaluating LLM Constraint Faithfulness in Natural-Language Combinatorial Scheduling](https://mlsanity.com/paper/2608.00991/) (2026)
- [MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMs](https://mlsanity.com/paper/2605.08498/) (2026)
- [Improving Natural-Language Combinatorial-Optimization Accuracy in Resource-Constrained Language Models via Formal Abstractions](https://mlsanity.com/paper/2608.18409/) (2026)
- [Blackboard Intelligence Can Surpass Autoregressive on Globally Constrained Problems](https://mlsanity.com/paper/2609.38806/) (2026)

## Abstract (arXiv)

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 Natural Language Combinatorial Optimization 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.