# Using Reasoning Models to Generate Search Heuristics that Solve Open Instances of Combinatorial Design Problems

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Mathematical reasoning, one of 17 directions in LLM reasoning.
- Builds on 19 of its 54 references that are in the map.
- First posted on arXiv 29 May 2025.

## Placed in

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

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

- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [OlympiadBench: A Challenging Benchmark for Promoting AGI with Olympiad-Level Bilingual Multimodal Scientific Problems](https://mlsanity.com/paper/2402.14008/) (2024)
- [A Survey on Large Language Models for Code Generation](https://mlsanity.com/paper/2406.00515/) (2024)
- [FrontierMath: A Benchmark for Evaluating Advanced Mathematical Reasoning in AI](https://mlsanity.com/paper/2411.04872/) (2024)
- [Proof or Bluff? Evaluating LLMs on 2025 USA Math Olympiad](https://mlsanity.com/paper/2503.21934/) (2025)
- [The Limits of Inference Scaling Through Resampling](https://mlsanity.com/paper/2411.17501/) (2024)
- [Constructions in combinatorics via neural networks](https://mlsanity.com/paper/2104.14516/) (2021)
- [PatternBoost: Constructions in Mathematics with a Little Help from AI](https://mlsanity.com/paper/2411.00566/) (2024)
- [CombiBench: Benchmarking LLM Capability for Combinatorial Mathematics](https://mlsanity.com/paper/2505.03171/) (2025)
- [CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization](https://mlsanity.com/paper/2504.04310/) (2025)
- [Generative Modeling for Mathematical Discovery](https://mlsanity.com/paper/2503.11061/) (2025)
- [Advancing Geometry with AI: Multi-agent Generation of Polytopes](https://mlsanity.com/paper/2502.05199/) (2025)
- [Generating Streamlining Constraints with Large Language Models](https://mlsanity.com/paper/2408.10268/) (2024)
- [Leveraging Large Language Models to Develop Heuristics for Emerging Optimization Problems](https://mlsanity.com/paper/2503.03350/) (2025)
- [QUBE: Enhancing Automatic Heuristic Design via Quality-Uncertainty Balanced Evolution](https://mlsanity.com/paper/2412.20694/) (2024)
- [Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematics](https://mlsanity.com/paper/2503.06366/) (2025)
- [Using Code Generation to Solve Open Instances of Combinatorial Design Problems](https://mlsanity.com/paper/2501.17725/) (2025)
- [LLM-Guided Search for Deletion-Correcting Codes](https://mlsanity.com/paper/2504.00613/) (2025)

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

- [Improved Upper Bounds for Slicing the Hypercube](https://mlsanity.com/paper/2602.16807/) (2026)
- [Improved lower bounds for the Shannon capacity of odd cycles](https://mlsanity.com/paper/2607.21517/) (2026)
- [Automated Discovery of Improved Constant Weight Binary Codes](https://mlsanity.com/paper/2603.00174/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) with reasoning are trained to iteratively generate and refine their answers before finalizing them, which can help with applications to mathematics and code generation. We apply code generation with reasoning LLMs to a specific task in the mathematical field of combinatorial design. This field studies diverse types of combinatorial designs, many of which have lists of open instances for which existence has not yet been determined. The Constructive Protocol CPro1 uses LLMs to generate search heuristics that have the potential to construct solutions to small open instances. Starting with a textual definition and a validity verifier for a particular type of design, CPro1 guides LLMs to select and implement strategies, while providing automated hyperparameter tuning and execution feedback. CPro1 with reasoning LLMs successfully solves long-standing open instances for 7 of 16 combinatorial design problems selected from the 2006 Handbook of Combinatorial Designs, including new solved instances for 3 of these (Bhaskar Rao Designs, Symmetric Weighing Matrices, Balanced Ternary Designs) that were unsolved by CPro1 with non-reasoning LLMs. It also solves open instances for several problems from recent (2025) literature, generating new Covering Sequences, Johnson Clique Covers, Deletion Codes, and a Uniform Nested Steiner Quadruple System.