Evaluating LLM Research Capabilities: Automated Theorem Proving and Constructive Optimization

    This article explores a newly proposed evaluation framework designed to assess the research-level reasoning capabilities of large language models (LLMs) in theoretical computer science. By focusing on verifiable outputs such as automated theorem proving, program optimization, and constructive improvements, the framework shifts the evaluation metric from semantic plausibility to algorithmic certainty. The article reviews the framework's design, analyzes the tiered performance results of participating AI systems, highlights the critical role of verifiable feedback, and outlines the current boundaries and practical engineering strategies for integrating AI as a research accelerator rather than a replacement.

    1. Why Verifiable AI Research Evaluation is Needed

    In recent years, large language models have matured in areas like code generation and intelligent question-answering, but “research-level reasoning” remains an unconquered frontier. The reason is that scientific research problems come with explicit constraints and verification methods: the correctness of a mathematical theorem can be formally checked; whether a construct satisfies constraints can be verified algorithmically; and whether a parameter upper bound is improved can be compared against published results. This differs entirely from the scoring logic of traditional Q&A tasks—if evaluation only checks whether “the answer is close to human expectations,” it cannot measure whether the model genuinely participated in the research process.

    Recently, an AI startup founder, in collaboration with an academic team led by a Turing Award laureate, proposed the first unified evaluation framework for theoretical computer science. The core concept of this framework is to place the outputs of research workflows—such as theorem proving, program optimization, and constructive improvement—into a single verifiable system. For developers, this means advancing the evaluation standard from “can the model generate a sentence” to “can the model generate an independently verifiable piece of evidence.”

    2. Evaluation Framework Design: Goals, Budget, and Verifiable Feedback

    This evaluation framework functions less like a traditional “question bank” and more like an automated scientific research experiment system. Its basic loop can be abstracted as follows:

    1. Problem Definition -> Model Generates Candidate Results -> Automated Verifier Checks -> Record Success/Failure -> Calculate Task Coverage

    Three key design constraints determine its rigor:

    1. Clear Goals: Every task is a decidable problem. For instance, “construct a graph that contains no triangles or quadrilaterals,” rather than “discuss graph theory.”
    2. Sufficient Budget: Models are allowed multiple attempts. Different tasks may have different attempt limits; for example, a specific theorem might be given 60 chances. This tests the model’s exploratory ability through continuous iteration, rather than the luck of a single hit.
    3. Verifiable Feedback: The model cannot output a “seemingly plausible answer.” It must produce an independently reviewable object—such as a formal proof script, a graph data structure, or a code parameter upper bound.

    This design raises the bar for the model: it must not only “know how to reason” but also “know how to self-verify.” The verifier acts as an external reviewer, using deterministic algorithms to evaluate candidate results. Taking the extremal graph construction task as an example, the verifier can be implemented as follows:

    1. def verify_extremal_graph(vertices, edges, min_edges):
    2. # Build graph
    3. adj = build_adjacency(vertices, edges)
    4. # Constraint 1: Edge count must exceed the known reference value
    5. if len(edges) <= min_edges:
    6. return False, "edge count not improved"
    7. # Constraint 2: Must not contain a triangle (3-cycle)
    8. if has_cycle_length(adj, 3):
    9. return False, "contains triangle"
    10. # Constraint 3: Must not contain a quadrilateral (4-cycle)
    11. if has_cycle_length(adj, 4):
    12. return False, "contains quadrilateral"
    13. return True, "valid"

    Such verifiers are not new in theoretical computer science; what is novel is orchestrating “verification capability” and “model reasoning capability” into a closed loop, and then observing the actual performance of different systems within that loop.

    3. Evaluation Results: Capability Stratification and Task Differences

    Looking at the overall results, there was a massive score gap among the participating AI agents, forming several distinct tiers:

    • The top-ranked system scored 71.9, completing 14 out of 20 theorems (a 70.0% success rate), achieved without being provided with intermediate lemmas;
    • The second-ranked system scored 57.4, succeeding 23 times out of 60 attempts, covering 9 different theorems (a 38.3% success rate);
    • The remaining six systems had success rates of no more than 11.7%.

    This indicates that leading systems already possess stable output capabilities in “end-to-end theorem proving,” while mid-to-lower-tier systems tend to linger in the “candidate generation” phase, failing to pass the verifier.

    However, a high overall score does not mean leading in every sub-task. A notable counterexample occurred in the PCP (Probabilistically Checkable Proof) alphabet soundness task: the second-ranked system succeeded in all three attempts, while the highest-scoring system failed to solve it. This reminds us that different models’ capabilities across different formal methods and reasoning types are not perfectly correlated, and a single ranking can mask these differences.

    Let’s look at two more intuitive “constructive improvement” achievements:

    • In the extremal graph construction task with a girth of 5, the second-ranked system constructed a graph with 124 vertices and 630 edges, containing no triangles or quadrilaterals, surpassing the task’s 629-edge reference value;
    • Meanwhile, the highest-scoring system proved that the upper bound of a specific coding parameter does not exceed 82, tightening the published upper bound from 84 to 82.

    The value of these two results lies in the fact that the models did not reiterate existing knowledge; they generated new, verifiable objects that outperformed existing reference results. Whether it is an extra edge or a two-unit decrease in the upper bound, it demonstrates that the models’ capabilities in combinatorial search and parameter optimization can be translated into concrete scientific output.

    4. Why Verifiable Feedback is the Core Variable

    The most important insight this evaluation framework offers the technical community is treating “verifiable feedback” as the foundational infrastructure for assessing model capabilities. In traditional training and evaluation, reward signals often come from human annotation or semantic similarity; in this framework, the verifier provides a hard true/false signal. This hard signal offers two major advantages.

    First, it eliminates the space for hallucination. The model cannot get away with vague expressions. If a provided proof lacks a critical step, or if a construct fails to meet constraints, the verifier immediately judges it as a failure. This forces the model to generate more rigorous output.

    Second, it supports iterative search. The model can repeatedly “propose candidates—verify—correct,” converting computational budget into search depth. Giving a theorem 60 attempts essentially simulates the trial-and-error loop of the scientific research process. This also explains why “number of attempts” became a critical variable in the evaluation.

    From an engineering perspective, this is similar to introducing a deterministic reward function in reinforcement learning. However, this evaluation framework is stricter than general RLHF: the reward is not based on semantic similarity, but on the true value of the objective function. This requires verifiers to be reliable and cost-effective to run. Therefore, task designers must make trade-offs between expressiveness and decidability: problems that are too complex may not be automatically verifiable, while problems that are too simple may not differentiate model capabilities.

    5. Current Boundaries and Engineering Insights

    While the overall rankings and specific achievements are impressive, we cannot yet conclude that “AI can replace researchers.” Even the best-performing systems exhibited three types of limitations:

    1. Insufficient Autonomous Topic Selection: Models can solve explicitly given problems, but they cannot actively pose “open questions worth studying.” The starting point of research still relies on human intuition and domain vision.
    2. Reliance on Humans for Value Judgments: Models can construct objects that exceed reference values, but they cannot determine whether this improvement has theoretical significance, whether it can be generalized to broader cases, or whether it is worth publishing.
    3. Major Open Problems Still Require Human-in-the-Loop: There remains a difficult gap between proving a lemma and conquering a long-standing open problem. This is not merely a matter of computational volume, but of direction selection and research strategy.

    For developers and enterprise technical teams, these boundaries can be translated into pragmatic engineering strategies:

    • Position AI research assistants as accelerators rather than replacements, focusing on verification, search, and candidate generation rather than research direction decision-making;
    • Prioritize automating research tasks that have clear goals, low verification costs, and enumerable search spaces;
    • Prioritize building verifiers within the toolchain, as they are the components that most enhance automation reliability;
    • At the compute level, teams can leverage cloud platforms such as Baidu AI Cloud for container services, object storage, and log monitoring to orchestrate large-scale verification tasks into observable and replayable workflows.

    6. Conclusion: A Topographic Map, Not a Finish Line

    Overall, this research acts more like a topographic map of AI research capabilities. It clearly marks that, under conditions of explicit problems, sufficient budgets, and verifiable feedback, models are already capable of completing certain theorem proofs, program optimizations, and constructive improvements. At the same time, it marks that autonomously selecting research directions, judging the value of results, and solving major open problems still heavily rely on human leadership.

    For developers, this map provides a sober, practical reference: combine compute, verifiers, and human judgment, and let the model function where it has already proven its capabilities, rather than blindly expecting it to entirely replace scientific exploration itself. The next step in AI-assisted research may not be a one-shot generation “from model to conclusion,” but rather a continuous loop of “human defines the problem—model generates candidates—verifier provides feedback—human makes value judgments.”