# MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Mathematical reasoning, one of 17 directions in LLM reasoning.
- Builds on 21 of its 66 references that are in the map.
- First posted on arXiv 8 May 2026.

## Placed in

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

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

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [gpt-oss-120b & gpt-oss-20b Model Card](https://mlsanity.com/paper/2508.10925/) (2025)
- [Kimi K2: Open Agentic Intelligence](https://mlsanity.com/paper/2507.20534/) (2025)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [MiniF2F: a cross-system benchmark for formal Olympiad-level mathematics](https://mlsanity.com/paper/2109.00110/) (2021)
- [MathArena: Evaluating LLMs on Uncontaminated Math Competitions](https://mlsanity.com/paper/2505.23281/) (2025)
- [LiveBench: A Challenging, Contamination-Limited LLM Benchmark](https://mlsanity.com/paper/2406.19314/) (2024)
- [ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning](https://mlsanity.com/paper/2502.01100/) (2025)
- [ARC-AGI-2: A New Challenge for Frontier AI Reasoning Systems](https://mlsanity.com/paper/2505.11831/) (2025)
- [ARC Prize 2024: Technical Report](https://mlsanity.com/paper/2412.04604/) (2024)
- [Enigmata: Scaling Logical Reasoning in Large Language Models with Synthetic Verifiable Puzzles](https://mlsanity.com/paper/2505.19914/) (2025)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [FrontierCS: Evolving Challenges for Evolving Intelligence](https://mlsanity.com/paper/2512.15699/) (2025)
- [MathConstruct: Challenging LLM Reasoning with Constructive Proofs](https://mlsanity.com/paper/2502.10197/) (2025)
- [NP-Engine: Empowering Optimization Reasoning in Large Language Models with Verifiable Synthetic NP Problems](https://mlsanity.com/paper/2510.16476/) (2025)
- [PyCSP3: Modeling Combinatorial Constrained Problems in Python](https://mlsanity.com/paper/2009.00326/) (2020)
- [Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimization](https://mlsanity.com/paper/2602.02188/) (2026)
- [Nondeterministic Polynomial-time Problem Challenge: An Ever-Scaling Reasoning Benchmark for LLMs](https://mlsanity.com/paper/2504.11239/) (2025)
- [HardcoreLogic: Challenging Large Reasoning Models with Long-tail Logic Puzzle Games](https://mlsanity.com/paper/2510.12563/) (2025)
- [MathDuels: A Self-Play Benchmark That Grows](https://mlsanity.com/paper/2604.21916/) (2026)

## Abstract (arXiv)

We introduce MathConstraint, a hard, adaptive benchmark for evaluating the combinatorial reasoning capabilities of LLMs. We combine constraint satisfaction problems with rigorous solver-based verification and design an adaptive generator to create instances that remain challenging as the LLMs improve in their reasoning capabilities. Unlike existing benchmarks that quickly saturate on fixed datasets or use LLM-as-a-judge for checking solutions,MathConstraint uses parameterized problem types that enable scalable generation of arbitrarily difficult and automatically verifiable instances. We release MathConstraint-Easy (266 instances), on which frontier models achieve between 72.6% (gemini-3.1-flash-lite) and 87.6% (gpt-5.5) accuracy, and MathConstraint (329 instances) on which the same models drop to between 18.5% (claude-4.6-sonnet) and 66.9% (gpt-5.5) accuracy, demonstrating the resilience of our benchmark generator against rapid progress in LLM reasoning capabilities. We evaluate 12 frontier and open-weight models with and without access to a sandboxed Python environment that includes generic SAT/SMT solvers. Tool access roughly doubles frontier accuracy on MathConstraint (mean +28pp; up to +52pp for claude-4.6-sonnet). Further, halving the tool-call budget from 8 to 4 rounds erases up to 37 points -- a sensitivity that most single-budget benchmarks miss. We release the generator, dataset, and evaluation harness as a robust environment for studying combinatorial reasoning and tool-use behavior under adversarially-tunable difficulty.