CombiBench: Benchmarking LLM Capability for Combinatorial Mathematics
Junqi Liu, Xiaohan Lin, Jonas Bayer, Yael Dillies, Weijie Jiang, Xiaodan Liang, Roman Soletskyi, Haiming Wang, Yunzhou Xie, Beibei Xiong, Zhengfeng Yang, Jujian Zhang, Lihong Zhi, Jia Li, Zhengying Liu
cs.AI
May 6, 2025 · v1
TL;DR
CombiBench provides 100 combinatorics problems formalized in Lean 4 with a Fine-Eval framework to benchmark LLM provers.
Abstract
Neurosymbolic approaches integrating large language models with formal reasoning have recently achieved human-level performance on mathematics competition problems in algebra, geometry and number theory. In comparison, combinatorics remains a challenging domain, characterized by a lack of appropriate benchmarks and theorem libraries. To address this gap, we introduce CombiBench, a comprehensive benchmark comprising 100 combinatorial problems, each formalized in Lean~4 and paired with its corresponding informal statement. The problem set covers a wide spectrum of difficulty levels, ranging from middle school to IMO and university level, and span over ten combinatorial topics. CombiBench is suitable for testing IMO solving capabilities since it includes all IMO combinatorial problems since 2000 (except IMO 2004 P3 as its statement contain an images). Furthermore, we provide a comprehensive and standardized evaluation framework, dubbed Fine-Eval (for $\textbf{F}$ill-in-the-blank $\textbf{in}$ L$\textbf{e}$an Evaluation), for formal mathematics. It accommodates not only proof-based problems but also, for the first time, the evaluation of fill-in-the-blank questions. Using Fine-Eval as the evaluation method and Kimina Lean Server as the backend, we benchmark several LLMs on CombiBench and observe that their capabilities for formally solving combinatorial problems remain limited. Among all models tested (none of which has been trained for this particular task), Kimina-Prover attains the best results, solving 7 problems (out of 100) under both ``with solution'' and ``without solution'' scenarios. We open source the benchmark dataset alongside with the code of the proposed evaluation method at
https://github.com/MoonshotAI/CombiBench/.
Problem
Neurosymbolic approaches integrating LLMs with formal reasoning have achieved strong performance on algebra, geometry, and number theory competition problems, but combinatorics remains challenging due to a lack of appropriate benchmarks and theorem libraries.
Approach
The authors introduce CombiBench, a benchmark comprising 100 combinatorial problems formalized in Lean 4 and paired with informal statements. Problems range from high school to research level, covering topics from Brualdi's Introductory Combinatorics. Evaluation uses both whole-proof generation and a two-stage Fine-Eval pipeline. Multiple models are tested including reasoning models (o1, o3-mini, DeepSeek-R1, Gemini-2.5-pro) and dedicated theorem provers (Goedel-Prover, DeepSeek-Prover-V2).
Results
State-of-the-art models achieve very low success rates on CombiBench. At Pass@16, the best reasoning model (Gemini-2.5-pro-preview) solves 4 problems with solutions and 3 without. Dedicated theorem provers perform comparably poorly. CombiBench is the first benchmark with 100% Lean 4 friendly combinatorial problems, versus 0% for miniF2F and ProofNet.
| Model | With solution | Without solution |
|---|
| Gemini-2.5-pro | 4 | 3 |
| DeepSeek-R1 | 2 | 2 |
| Goedel-Prover | 2 | 2 |
| DeepSeek-Prover-V2 | 3 | 2 |
CombiBench evaluation results (Pass@16)