# ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 8 of its 20 references that are in the map.
- First posted on arXiv 25 Feb 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

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

- [ORLM: A Customizable Framework in Training Large Models for Automated Optimization Modeling](https://mlsanity.com/paper/2405.17743/) (2024)
- [OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Models](https://mlsanity.com/paper/2402.10172/) (2024)
- [LLMs for Mathematical Modeling: Towards Bridging the Gap between Natural and Mathematical Languages](https://mlsanity.com/paper/2405.13144/) (2024)
- [Solver-Informed RL: Grounding Large Language Models for Authentic Optimization Modeling](https://mlsanity.com/paper/2505.11792/) (2025)
- [OptiMUS-0.3: Using Large Language Models to Model and Solve Optimization Problems at Scale](https://mlsanity.com/paper/2407.19633/) (2024)
- [Self-Guiding Exploration for Combinatorial Problems](https://mlsanity.com/paper/2405.17950/) (2024)
- [OptiMind: Teaching LLMs to Think Like Optimization Experts](https://mlsanity.com/paper/2509.22979/) (2025)
- [Exploring Combinatorial Problem Solving with Large Language Models: A Case Study on the Travelling Salesman Problem Using GPT-3.5 Turbo](https://mlsanity.com/paper/2405.01997/) (2024)

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

- [Falsification-Based Verification of LLM-Generated Optimization Models: Sound Test Batteries and Their Detection Limits](https://mlsanity.com/paper/2607.16646/) (2026)
- [SCHEDBench: A Benchmark for Evaluating LLM Constraint Faithfulness in Natural-Language Combinatorial Scheduling](https://mlsanity.com/paper/2608.00991/) (2026)
- [SemVerBench: Benchmarking LLM Comprehension of Version-Constraint Resolution Semantics](https://mlsanity.com/paper/2609.11180/) (2026)
- [Blind-Spots-Bench: Evaluating Blind Spots in Multimodal Models](https://mlsanity.com/paper/2607.08317/) (2026)
- [Tasks over Application Manuals: Revealing Gaps in Long-Horizon Procedural Reasoning for Language Models](https://mlsanity.com/paper/2609.13005/) (2026)
- [Blackboard Intelligence Can Surpass Autoregressive on Globally Constrained Problems](https://mlsanity.com/paper/2609.38806/) (2026)
- [BANGLAPLAN: A Benchmark for Constraint-Based Planning and Decision-Making in Bangla](https://mlsanity.com/paper/2610.19704/) (2026)

## Abstract (arXiv)

Large language models are increasingly applied to operational decision-making where the underlying structure is constrained optimization. Existing benchmarks evaluate whether LLMs can formulate optimization problems as solver code, but leave open a complementary question. Can LLMs directly produce correct solutions to fully specified constrained optimization problems without access to a solver? We introduce ConstraintBench, a benchmark for evaluating LLMs on direct constrained optimization across 10 operations research domains, with all ground-truth solutions verified by the Gurobi solver. Each task presents a natural-language scenario with entities, constraints, and an optimization objective; the model must return a structured solution that a deterministic verifier checks against every constraint and the solver-proven optimum. We evaluate six frontier models on 200 tasks and find that feasibility, not optimality, is the primary bottleneck. The best model achieves only 65.0% feasibility, yet feasible solutions average 89 to 96% of the Gurobi-optimal objective. No model exceeds 30.5% on joint feasibility and optimality within 0.1% of the solver reference. Per-domain analysis shows large variation in difficulty, with average feasibility spanning from 85.0% in the facility location domain to 0.8% in the crew assignment domain. Further, systematic failure modes include duration constraint misunderstanding, entity hallucination, and a feasibility-optimality decoupling in facility location and vehicle routing where models achieve high feasibility but 0% optimality. ConstraintBench and all evaluation infrastructure will be publicly released.