How LLM Agents Tackle Mathematical Theorem Proving: A Deep Dive into Verifiable Benchmarks

    This article explains how verifiable benchmarks evaluate large language model agents on mathematical theorem proving and combinatorial construction tasks. It covers the three task types, the scoring metrics, leaderboard results, two notable outcomes where agents produced new constructions and bounds, the modules agents use for automated proving, and the current limitations.

    1. Background: Why Verifiable Math Evaluation Matters

    In recent years, large language models have kept setting new records on tasks such as natural language reasoning and code generation. However, being able to talk about a topic does not mean being able to prove it. Mathematical theorem proving is naturally verifiable: a proof either holds or it does not. There is no “roughly correct” middle ground. For this reason, building a unified, verifiable evaluation system around formal mathematics and combinatorial construction problems has become an important way to measure the real reasoning ability of LLM agents.

    Recently, a research team consolidated mathematical proof tasks that were previously scattered across different research workflows into a benchmark that can be checked automatically (referred to here as a TCSExam-style benchmark). The core idea is to avoid manual grading. Instead, a program can independently verify every answer. Each answer is either a formal proof or a machine-checkable construction, such as a graph or a set of parameters. The benchmark covers classic problems in theoretical computer science, including extremal graph construction, tightening upper bounds for Ramsey numbers, and tasks related to probabilistically checkable proofs (PCP).

    2. Evaluation Design: Tasks, Metrics, and Workflow

    2.1 Task Types

    This kind of verifiable benchmark usually includes three task types:

    1. Automated theorem proving: Given a theorem statement, the agent must produce a complete proof. Alternatively, it must complete a step-by-step proof when intermediate lemmas are provided as hints.
    2. Constructive tasks: For example, “construct a graph that contains no triangles or quadrilaterals, with as many edges as possible.” The answer is not a text description but a concrete combinatorial object that a verifier can check directly.
    3. Upper bound tightening tasks: Given a known upper bound for a mathematical quantity, the agent must provide a tighter upper bound with a proof. The verifier checks the chain of deductions.

    2.2 Metric Design

    Evaluation usually covers two dimensions:

    • Full leaderboard score: The overall quality across all tasks, reflecting general capability.
    • Coverage and success rate: For example, if the system makes M attempts on N theorems, the benchmark counts the number of distinct theorems solved and the success rate of a single attempt. This distinction matters. One system may solve a few problems by retrying until it gets lucky, while another reliably solves more theorems. The two results carry very different weight.

    2.3 Why Verifiability Matters

    Traditional evaluation relies on answers that look plausible, which can be misled by hallucinations and pattern matching. Verifiable benchmarks require each answer to be an object, a parameter set, or a proof that can be checked independently:

    1. Input: theorem statement / construction task description
    2. Output: formal proof script, or combinatorial object (vertex set, edge set, parameter table)
    3. Verification: automated verifier checks each step of the derivation and each constraint
    4. Verdict: pass → scored; fail → recorded as a failure, no partial credit

    This “output as evidence” design raises evaluation from subjective grading to the same level of rigor as a compiler or a proof assistant.

    3. Current Capability Levels and Key Observations

    Public evaluation results show a clear gap between the leading agents, but the lead is uneven:

    1. Large score gaps: The top system scored about 71.9 on the Full leaderboard, and the second-place system scored about 57.4. Most other agents scored 11.7 or lower. This shows the task demands very deep reasoning, and ordinary models cannot close the gap through prompt engineering alone.
    2. Coverage is more informative than single-attempt success rate: With intermediate lemmas provided, the leading system completed most theorems. For example, it solved 14 of 20 theorems, a success rate of about 70%. On open tasks without hints, the system made many attempts, but it covered fewer problems and had a lower success rate per attempt. This suggests that task decomposition and supplying intermediate lemmas are among the most effective ways to raise proof success rates right now.
    3. No single system dominates everywhere: The second-place system outperformed the top system on some specialized tasks, such as verifying the reliability of PCP alphabets. The top system failed to solve that problem, while the second-place system completed it across multiple attempts. Systems differ in proof strategy, search pruning, and use of formal tools, so no single system is strong at everything.

    4. Notable Results: From Writing Answers to Producing New Knowledge

    Most notably, some agents produced results that exceed existing public records. This is a milestone in the history of evaluation:

    • Extremal graph construction: In the task of finding an extremal graph with girth 5, one system constructed a graph with 124 vertices and 630 edges that contains no triangles or quadrilaterals. This exceeds the 629-edge reference value used by the task. Because the verifier checks every edge for cycles of length 3 or 4, the result can be confirmed without manual review.
    • Upper bound tightening: Another system tightened the published upper bound of a combinatorial quantity from 84 to 82 and provided a complete derivation. Upper bound tightening is a typical “incremental but rigorous” contribution. Each reduction of 1 requires a tight chain of reasoning with no skipped steps.

    The common thread is that the answer itself is the evidence. An algorithm can check a graph directly, and an inequality can go through a formal verification process. This is the fundamental advantage of verifiable evaluation over traditional question-answering evaluation.

    5. Technical Approach: How Agents Complete Automated Proofs

    Based on public practice in these systems, automated proving agents typically include the following core modules:

    1. Problem formalization: Convert the natural language statement into a formal goal and remove ambiguity.
    2. Strategy library and experience accumulation: Maintain proven lemmas and common construction techniques, such as the probabilistic method, greedy construction, and local search. Retrieve and reuse them on new tasks.
    3. Search and backtracking: A proof is essentially a huge search space, so the system combines heuristic pruning with random restarts. This is why results like “23 successes in 60 attempts” are common. Repeated attempts are an inherent part of the current paradigm.
    4. Automated verification feedback loop: Each step goes to the verifier immediately, and failure information returns to the model for correction. This forms an iterative “generate, verify, repair” cycle.
    5. Specialized solvers for construction tasks: For tasks such as extremal graphs, systems often combine random search with local optimization. The model proposes construction hypotheses, while programs check constraints and suggest directions for improvement.

    6. Limitations and Outlook

    Despite the impressive results, current systems have clear weaknesses:

    • Dependence on prompt structure: Without intermediate lemmas, success rates drop sharply. This shows that models still lack enough ability to plan proof paths on their own.
    • Low overall success rates: Most agents succeed less than 20% of the time, which is still far from the stable level of human mathematicians.
    • Uncertain generalization: Uneven performance across specialized tasks suggests that a system may be strong only on certain proof patterns.

    Looking ahead, as verifier ecosystems mature and inference-time compute scales up, verifiable mathematical evaluation may become one of the gold standards for measuring the reasoning ability of LLM agents. For engineering teams, the “generate, verify, repair” loop also applies to code generation, data pipeline validation, and other scenarios that require hard correctness guarantees.

    Summary

    Verifiable benchmarks move the evaluation of LLM mathematical ability from “sounds convincing” to “can be proven.” Leading systems can already produce constructions and bounds that exceed public records, but coverage, autonomous planning, and stability remain the main challenges. For developers, the key lesson is that any task that can be verified automatically should drive agent iteration through a verification loop.