LLM Theorem-Proving Evaluation with Verifiable Artifacts: A New Paradigm for Research Capability Assessment

    Traditional evaluations of LLM mathematical research capabilities often rely on subjective open-ended answers, ambiguous objectives, and static single-turn scoring. This article presents a verifiable evaluation paradigm that treats proofs, constructions, parameters, and programs as independently checkable artifacts. It covers task selection across extremal graph theory, coding theory, and probabilistically checkable proofs (PCP); lemma-guided versus bare-problem modes; multi-attempt feedback loops; representative results such as a 124-vertex, 630-edge girth-5 graph and the bound $A(22,10) \le 82$; current capability boundaries; and practical implications for R&D teams. The central argument is that research capability should be measured by artifacts that can be independently verified, not by answers that merely appear plausible.

    1. Background: Why Verifiable Research Capability Evaluation Is Needed

    Over the past few years, large language models have made visible progress in mathematical reasoning and code generation. Yet a long-standing question remains unresolved: when a model appears “smart,” has it actually completed research, or is it merely restating conclusions from its training corpus?

    Traditional evaluation suffers from three defects:

    1. Not independently checkable: Open-ended question-answer evaluation can only be scored subjectively by humans, and a model may produce an answer that “looks reasonable but cannot be verified.”
    2. Ambiguous objectives: Real research problems rarely have a one-shot standard answer; they require diverse outputs such as constructions, optimizations, and proofs.
    3. Missing feedback: Research is an iterative process of attempt, failure, and correction. Static single-turn evaluation cannot show whether a model can use feedback.

    The field is therefore exploring a new paradigm: placing the outputs of theoretical research workflows—proofs, constructions, parameters, and programs—into one verifiable system. In this system, every model output is not an answer that “looks right,” but an object that can be independently reviewed. Proofs can be checked by formal verifiers, constructions can be tested by enumeration programs, and upper bounds can be confirmed by computation. This fundamentally avoids the “hallucination” problem because only mathematically valid objects can pass verification.

    This approach is closely related to “test-driven evaluation” in software development: rather than evaluating what a model says, evaluate what it delivers as a machine-checkable artifact.

    2. Evaluation Design: Lemma Guidance, Verifiable Feedback, and Multiple Attempts

    The core design of this evaluation system can be divided into three layers.

    2.1 Task Selection: Covering Multiple Branches of Theoretical Computer Science

    The evaluation deliberately selects representative directions in theoretical computer science, including:

    • Extremal graph theory: for example, constructing graphs that satisfy specific girth constraints, which tests combinatorial construction ability;
    • Coding theory: for example, improving upper bounds on code distance parameters, which tests analysis and proof ability;
    • Probabilistically checkable proofs (PCP): which tests understanding and computational ability related to deep structures in complexity theory.

    These directions share a common feature: short results, strict determination, and programmatic verifiability. For example, a graph construction can be confirmed simply by checking the number of vertices, the number of edges, and whether it contains no triangles or quadrilaterals—without any subjective judgment.

    2.2 Lemma Guidance: Scaffolding or Bare Problems?

    The evaluation distinguishes two modes:

    • Providing intermediate lemmas: the problem includes key lemmas as hints, reducing the search space;
    • Not providing intermediate lemmas: the model must discover lemmas and build the proof chain itself, which is closer to real research.

    This distinction is critical. Comparative data show that leading models drop noticeably in success rate under the “bare problem” mode, indicating that the bottleneck is not single-step reasoning but long-chain research planning—how to decompose a large goal into provable intermediate steps.

    2.3 Multiple Attempts and a Feedback Loop

    The evaluation allows models to make multiple attempts under a sufficient budget and to iterate based on verifiable feedback. The statistical approach is therefore more scientific: it examines not only “whether the model succeeded,” but also how many distinct theorems were successfully covered (diversity), success rate (stability), and the degree of improvement over reference values (novelty). For example, one model succeeded 23 times in 60 attempts and covered 9 distinct theorems, showing that its success was not accidental but reflected some generalization ability.

    3. Representative Results: Breakthroughs in Both Construction and Proof

    The most informative part of the evaluation is the independently confirmable progress models made on real mathematical problems. Two types of results are especially typical.

    3.1 Extremal Graph Construction: From “Close to Reference” to “Beyond Reference”

    In the classic Erdős extremal graph problem, the task requires constructing a graph with girth 5—that is, containing no triangles and no quadrilaterals—while maximizing the number of edges. The reference construction used in the evaluation has 629 edges. The model produced a graph with 124 vertices and 630 edges, programmatically verified to contain no triangles or quadrilaterals—exceeding the reference edge count.

    The significance of this result is as follows:

    • It is not an answer that was “memorized.” The space of extremal graph constructions is enormous, and the 629-edge reference construction is itself a carefully designed human-made object.
    • It demonstrates a closed-loop capability of combinatorial search + constraint verification + local improvement: first guess a structure, then use a program to check violations, and then repair them in a targeted way.
    • It provides a new candidate solution for the lower-bound record of this open problem. Although a one-edge improvement is mathematically small, it is a qualitative signal for an automated system.

    3.2 Coding Theory Upper Bound: From “Discovery” to “Proof”

    Another type of result is analytical: the model proved $A(22,10) \le 82$ in coding theory, tightening the published upper bound of 84 by 2. Unlike construction results, an upper-bound proof requires the model to:

    1. Correctly understand the mathematical definition of the problem and known tools, such as linear programming bounds and sphere-packing bounds;
    2. Choose an appropriate parameterization and relaxation;
    3. Produce a rigorous proof acceptable to a verifier.

    Such results show that the model is not only a “searcher.” When lemmas are complete, it can also act as a “proof engineer”—correctly assembling known techniques into a new conclusion.

    3.3 Capability Is Not Linearly Ordered: Task Structure Determines Success

    It is worth emphasizing that the evaluation results are not a simple case of “overall dominance.” On a PCP-related alphabet reliability task, the strongest-performing model failed to solve the problem, while another model completed all three attempts. This reveals a practical point: model capability is highly differentiated across task types. PCP-style tasks require understanding complex reliability-analysis structures, while graph construction requires search ability—these belong to different skill dimensions. For enterprise evaluation, a single score is far from enough; it is necessary to build a task matrix that covers multiple cognitive dimensions.

    4. Capability Boundaries: What Current Models Can and Cannot Do

    Taken together, the evaluation data can be summarized as a “terrain map” of current LLM research capabilities.

    4.1 Capabilities Already Present

    • Proof generation under well-defined problems: when the goal is clear, lemmas are provided, and feedback is verifiable, models can reliably produce partially correct proofs;
    • Construction and optimization improvements: on constraint-optimization tasks that are programmatically verifiable, models can exceed human reference values through iterative improvement;
    • Using feedback for error correction: the success rate of multiple attempts is significantly higher than that of a single attempt, indicating that models can effectively use verification signals.

    4.2 Capabilities Still Missing

    • Autonomous selection of research directions: models cannot judge “which problems are worth studying.” Topic selection and value judgment remain core human functions.
    • Autonomous lemma discovery: the sharp drop in success rate under the bare-problem mode shows that “research planning” ability—inferring intermediate lemmas from a goal—remains weak.
    • Tackling major open problems: current successes are concentrated on “moderately difficult, verifiable” tasks. There is still an order-of-magnitude gap from Clay Millennium Prize-level open problems.

    These boundaries have direct implications for enterprise applications: the most feasible deployment scenario is a human-machine collaborative research pipeline—humans propose problems and judge value, models conduct large-scale search, construction, and proof attempts in a verifiable environment, and verifiers gate correctness. This division of labor treats the model as a “tireless research assistant” rather than an “independent scientist.”

    5. Methodology Lessons for R&D Teams

    Whether or not a team directly uses a similar academic evaluation, the design principles of this system are worth borrowing:

    1. Shift the evaluation object from “text” to “artifact.” In internal evaluation, prioritize tasks with programmatic judges (unit tests, formal verification, numerical recomputation) and eliminate noise from subjective scoring.
    2. Design a gradient of lemmas and hints. Prepare multiple difficulty versions of the same task (bare problem, partial hints, complete lemmas) to distinguish “single-step capability” from “planning capability.”
    3. Use multiple statistical measures. Report success rate, coverage breadth, and improvement magnitude together to avoid being misled by a single hit.
    4. Build a feedback loop. Allow models to make multiple attempts and use verification signals. This is closer to real research and better reflects model upper bounds.
    5. Build a failure-case analysis library. The many unsuccessful attempts in the evaluation—for example, 37 failures out of 60 attempts by one model—are valuable data for understanding capability boundaries.

    6. Conclusion

    The most important contribution of this evaluation system is not a particular score or record, but a reusable evaluation philosophy: research capability must be measured through outputs that can be independently reviewed. From the 124-vertex, 630-edge extremal graph construction to the tightening of the $A(22,10)$ upper bound from 84 to 82, these results jointly show that, under conditions of clear problems, sufficient budget, and verifiable feedback, large models can already participate in real research workflows. How to choose problems worth studying and how to judge the value of results will remain irreplaceable core competencies of human researchers for the foreseeable future. For teams hoping to introduce AI into R&D workflows, building a “verifiable” evaluation foundation first—and then discussing capability iteration—is the more robust technical path.