ComBench: A Benchmark for Rigorous Proof Reasoning and Constructive Realization in Olympiad-Level Combinatorics

Can AI Truly Build What It Claims to Prove?

Can an artificial intelligence not only argue that a mathematical object exists but also actually construct it? In the realm of Olympiad-level mathematics, the challenge is rarely just about finding a number. It is about describing complex, discrete structures like specific graph colorings or intricate tilings. While modern large language models (LLMs) have made significant strides in solving competitive math problems, a critical gap remains. They struggle to move from abstract reasoning to concrete realization.

A new study introduces ComBench, a specialized benchmark. It tests whether models can handle the dual demands of combinatorics: rigorous proof reasoning and constructive realization. The researchers report that current frontier models are surprisingly uneven. They often produce eloquent proofs that fail to yield a valid, machine-checkable mathematical object.

The gap between argument and artifact

The researchers investigated a specific deficiency in mathematical reasoning. They looked at the disconnect between proving a statement and realizing a witness. In combinatorics, a "witness" is a concrete mathematical object. This could be a specific arrangement of tiles or a particular set of connections in a graph. The witness serves as the physical proof that a claim is true.

The authors argue that existing benchmarks often fail to isolate this distinction. Many evaluations rely on simple answer-matching. This tells you if a model got the right number but says nothing about its logic. Others use rubric-based proof grading. This method judges the prose of a mathematical argument. However, the study finds that a model can write a convincing-sounding proof of existence while failing to actually produce the object it describes. This creates a risk where linguistic fluency masks a failure in structural planning.

Moving beyond prose-only evaluation

To address this, the authors developed a multi-stage pipeline to create ComBench. This benchmark contains 100 human-annotated Olympiad-level problems. The dataset splits problems into two types. Analysis-centric records focus on pure mathematical argumentation. Construction-centric records demand an explicit, machine-checkable witness.

As shown in, the creation of these construction-centric records involves a rigorous three-stage process.

First, experts define the "human intent." This specifies what kind of object the model must build. Second, the team generates deterministic Python verifiers. These are scripts that check the model's output automatically. Finally, they perform a semantic audit. This ensures the automated verifier actually enforces the intended mathematical constraints rather than just checking the format.

To ensure the scores reflected reality, the authors implemented a "verifier-gated" scoring rule .

In this protocol, high-scoring proofs are demoted if the model fails to produce a valid construction. If a model provides a high-scoring proof but fails the Python verifier, its score drops. This prevents a model from receiving full credit for a "proof" that lacks a functional blueprint.

Disentangling proof from realization

The experimental results reveal that proof-writing and object-building are distinct capabilities. The study evaluates ten frontier models, including GPT-5.5 and Kimi-K2.6. The researchers report that the strongest model, GPT-5.5, reaches a 65.4% overall average and a 75.3% Best@4 score. This indicates that even the best models still struggle with more than a third of the benchmark.

Crucially, the researchers found that success in one area does not guarantee success in the other. For example, the authors report that Kimi-K2.6 trails GPT-5.5 in analysis-centric proof grading. However, it actually surpasses GPT-5.5 in construction-centric Best@4 scores [Table 1]. This suggests that some models may possess superior "structural planning." This is the ability to organize discrete elements into a valid global pattern, even if their formal linguistic reasoning is less polished.

The difficulty varies significantly by mathematical category .

The authors find that "Existence and Construction" problems are consistently the hardest for all representative models. In contrast, "Counting" and "Graph Theory" problems yield higher scores. This is likely because they rely more on local structural constraints or enumerative patterns.

Identifying the mechanics of failure

When models do fail, the errors are rarely simple typos. An analysis of the unsuccessful attempts reveals that most failures are substantive mathematical errors .

The most frequent failure mode accounts for 41.2% of below-full-credit samples. This is a "Missing Core Mechanism." This occurs when a model provides local observations but fails to identify the central invariant (a property that remains unchanged during a process) required to finish the proof.

Other significant errors include "Wrong Mathematical Target," where the model optimizes the wrong quantity. "False Lemmas" also occur, where the argument relies on an unsupported claim. These findings suggest that improving mathematical AI requires more than just better language modeling. It requires a fundamental advancement in global proof planning and the ability to synthesize complex, multi-part discrete structures.

Implications for the future of mathematical AI

The dissociation between proof reasoning and constructive realization has profound implications. If these two capabilities are distinct, then current training objectives may be insufficient. Training focused solely on predicting the next token in a proof may not teach a model to build complex mathematical objects.

For researchers, this suggests a need for training regimes that explicitly reward the synthesis of discrete structures. This means teaching the model to "engineer" a solution rather than just "describe" one. For practitioners, the takeaway is a warning. High-quality natural language proofs are not a sufficient proxy for mathematical truth. Reliable systems will require integrated, executable verification. This ensures that a model's theoretical claims are backed by functional reality.