Verifiable Evaluation: A Roadmap for Mapping AI Research Capability

    Large language models produce mathematical proofs, algorithm code, and technical reports that often read cleanly and use precise terminology. But the value of research does not depend on how fluent the narrative sounds; it depends on whether the conclusions hold up under scrutiny. A proposition is either true or false; a graph either satisfies every constraint or it does not; a bound either holds or it fails. This article explains how to design verifiable benchmarks that require models to hand over checkable artifacts, how to engineer the evaluation pipeline, how to interpret results correctly, and how teams can adapt the approach to their own domains. We cover theorem proving, combinatorial constructions, coding-theory bounds, and algorithm optimization, using publicly reported results only to illustrate that real capability gaps exist without any single system dominating every direction.

    Introduction: From “Answers” to “Evidence”

    Large language models generate mathematical proofs, algorithm code, and technical reports that often read cleanly and use accurate terminology. But the value of research does not depend on whether the narrative flows well; it depends on whether the conclusions can withstand review. A proposition either holds or it does not; a graph either satisfies every constraint or it does not; a bound either holds or it fails.

    A recent piece of publicly released research pushes this idea into evaluation. The researchers focused on theoretical computer science and designed a benchmark that requires models to submit “reviewable objects,” including standalone proofs, explicit constructions, and programs, then published the results. Among the systems evaluated, one model solved 14 of 20 theorem-proving problems, while another succeeded 23 times across 60 samples, covering 9 distinct theorems. The capability gap is real, but no single side dominates across the board.

    This article strips out specific models and institutions and discusses only the transferable methodology:

    • How to design “verifiable” research evaluations;
    • How to engineer the evaluation pipeline;
    • How to interpret results correctly;
    • How teams can implement similar approaches in their own domains.

    1. Why Traditional Evaluation Struggles to Measure Research Capability

    1.1 Text-based scoring cannot handle open-ended conclusions

    Automated grading usually relies on matching against a reference answer, or on having another model score the output against that reference. Such methods can check whether a solution path is close to the standard one, but they cannot judge whether an entirely new construction is valid or whether a novel proof holds. The more open the answer, the more subjective the score.

    1.2 The process cannot be verified, so “able to do it” and “happened to get it right” blur together

    A model might derive a plausible-looking conclusion from false assumptions, or it might retry repeatedly and “happen” to land on the correct answer. If only the final answer is recorded, there is no way to distinguish the two. Research cares precisely about a stable, reproducible reasoning process.

    1.3 Single-sample scoring hides search capability

    Succeeding on one generation is a different capability from solving a problem once multiple attempts are allowed. Real research is never a “one-shot” process: researchers try several lines of thought, fix intermediate mistakes, and iterate using feedback. Ignoring the number of attempts and the budget constraints systematically overstates how usable a model is for research.

    1.4 Results cannot be reviewed, so knowledge cannot accumulate

    A natural-language answer cannot be directly reused or verified by other programs or researchers. But a verified new upper bound, or a graph that passes every check, can be cited, improved, and refuted by later work. This is the fundamental difference between an “answer” and a “research output.”

    1.5 It aligns with formal-verification practice

    Formal methods are already applied in areas such as protocol verification, compiler correctness proofs, and mathematical specifications for critical systems. In such practice, proofs are checked by machines and conclusions can be verified automatically. Designing an evaluation around “machine verifiability” is consistent with the direction of engineering practice.

    2. Theoretical Computer Science: A Natural Testing Ground for Verifiability

    Theoretical computer science is well suited as the main arena for verifiable evaluation, for four reasons:

    • Objective conclusions: The truth of a mathematical proposition does not depend on subjective judgment.
    • Machine-checkable artifacts: Proofs can be verified step by step by a formal checker; combinatorial constructions can have their constraints checked one by one by a program; algorithms can be judged against test cases and specifications.
    • Anchorable difficulty: A large body of published results can serve as a baseline. Whether a model can surpass an existing conclusion is a direct yardstick for progress.
    • Transferable skills: Modeling abstraction, constructing counterexamples, combinatorial reasoning, and complexity analysis are core capabilities shared across algorithm design, cryptographic analysis, and system performance modeling.

    More importantly, theoretical computer science relies almost entirely on neither experimental equipment nor domain-specific data accumulation, so it can keep the evaluation focused on “reasoning and construction capability” itself, making it suitable for comparing different models head to head.

    3. Design Patterns for Three Classes of Verifiable Tasks

    3.1 Theorem proving: Removing the crutch of “intermediate lemmas”

    In theorem-proving tasks, the model must produce a complete, step-by-step valid derivation and hand it to a formal proof checker for verification. One key design choice is: whether to provide intermediate lemmas.

    • Providing lemmas: The model only needs to fill in the remaining steps, which tests its “gap-filling” ability.
    • Not providing lemmas: The model must find the proof path and the required auxiliary conclusions on its own, which is closer to real research.

    The publicly reported evaluation adopts the setting of not providing intermediate lemmas. The results showed that one model solved 14 of 20 problems, a success rate of 70.0%; another model succeeded 23 times across 60 attempts, covering 9 distinct theorems, a success rate of 38.3%; the remaining systems all had completion rates below 11.7%. What separated them was not speed on individual problems, but whether they could independently find a route to the proof.

    3.2 Combinatorial constructions: Counting as an “improvement” only when the reference baseline is beaten

    Extremal-combinatorics tasks are usually framed like this: under given constraints, construct an object as “large” as possible. Take the “extremal graph with girth 5” as an example. The goal is to maximize the number of edges for a fixed number of vertices, and the graph must contain neither triangles nor quadrilaterals.

    • Clear decision criteria: The checker traverses all vertex pairs and all paths of length 2 and 3 to confirm there are no cycles of length 3 or 4; counting the edges yields the target value.
    • Quantifiable improvement: In this task, one model constructed a graph with 124 vertices and 630 edges that satisfies the constraints, surpassing the 629-edge reference value used by the task.

    This type of task tests “construction ability,” that is, finding a clever structure under large-scale constraints, rather than merely proving a known result.

    3.3 Coding-theory parameter bounds: Tightening an upper or lower bound

    Coding theory studies the maximum number of codewords for a given code length and minimum distance. Let A(n,d) denote the maximum size of a binary code of length n with minimum distance d. This is usually hard to determine exactly, and can only be approached gradually through constructing lower bounds and proving upper bounds.

    In the evaluation mentioned above, one model proved that A(22,10) ≤ 82, tightening the published upper bound from 84 to 82. Such a result has two characteristics:

    • Clear decision: The proof is verified by a formal checker;
    • Direct significance: A tightened bound means the feasible region for related engineering designs narrows, or the infeasible range expands.

    3.4 Algorithm and program optimization: Correctness plus performance

    For algorithm problems, the evaluation target is not text but a program. The decision usually has two layers:

    1. Correctness: Whether the program satisfies a formal specification, or passes all hidden tests;
    2. Performance: Metrics such as runtime and memory usage on public benchmark inputs, along with a complexity analysis backed by proof.

    Once the specification is machine-checkable, “faster and still correct” becomes a measurable improvement rather than a subjective impression.

    3.5 Comparing the three task types

    Task type Core focus Evaluated artifact Decision method
    Theorem proving Independently finding a proof path Formal proof Step-by-step verification by a proof checker
    Combinatorial construction Structural design under large-scale constraints Explicit object Program verifies all constraints and compares against the baseline
    Bound tightening Reasoning and bound arguments Upper- or lower-bound proof Formal verification or mathematical review
    Algorithm optimization Balancing correctness and efficiency Program and complexity analysis Specification checks, hidden tests, performance benchmarks

    4. Engineering the Evaluation System

    4.1 The verifier: Decoupled from the solving model

    The verifier is the root of trust in the evaluation system and should follow these principles:

    1. Independent implementation: It does not depend on the solving model’s self-report or natural-language explanation;
    2. Deterministic: The same artifact and the same input must yield the same conclusion;
    3. Auditable: The decision process produces complete logs, including the specific constraints and locations where it failed;
    4. Restricted input: It accepts only structured artifacts, preventing malicious input from crashing the verifier or “gaming” it;
    5. Version-controlled alongside the problem set: When the artifact format or decision logic changes, historical results should be re-evaluable.

    4.2 Scoring: Binary decisions, partial credit, and difficulty tiers

    • Binary decision: Satisfying every constraint scores 1, otherwise 0, with the reason for failure attached.
    • Partial credit: Staged scores can be set, for example, awarding 0.5 for “satisfying most constraints but not beating the baseline,” making it easier to observe the capability gradient.
    • Difficulty tiers: Using known answers as anchors, problems are divided into easy, medium, and hard tiers; the harder the problem, the greater the score weight, which prevents easy problems from racking up high scores.
    • Resource constraints: Fixing the number of attempts, time, or compute budget makes results comparable across different models.

    4.3 A sketch of the runtime flow

    The pseudocode below shows the skeleton of an evaluation pipeline: the model produces structured results, the verifier independently re-checks them, and multiple sampling rounds are aggregated under a fixed budget.

    1. from dataclasses import dataclass
    2. @dataclass
    3. class Task:
    4. name: str
    5. spec: dict # task parameters, e.g., number of vertices, target edges, baseline value
    6. verifier: object # verifier, accepts only structured artifacts
    7. max_attempts: int = 3 # attempt budget
    8. difficulty: str = "hard" # difficulty tier, used for weighting
    9. def evaluate(task: Task, model) -> dict:
    10. passed = 0
    11. best_value = None
    12. for _ in range(task.max_attempts):
    13. artifact = model.solve(task.spec) # artifact: proof / construction / program
    14. verdict = task.verifier.check(artifact)
    15. # the verifier is independent of the model; conclusions come only from step-by-step checking of the artifact
    16. if verdict.valid:
    17. passed += 1
    18. if best_value is None or verdict.value > best_value:
    19. best_value = verdict.value # record the best verifiable result
    20. return {
    21. "task": task.name,
    22. "success_rate": passed / task.max_attempts,
    23. "best_verified_value": best_value,
    24. "difficulty": task.difficulty,
    25. }

    4.4 Infrastructure

    Evaluation often involves large amounts of repeated computation: formal checking, constraint verification for constructions, test-case execution, and so on. Engineering-wise, the following division of labor is a useful reference:

    • Use a container platform to batch-schedule verification tasks, isolating runtime environments for different tasks;
    • Use object storage to keep artifacts and decision logs, ensuring results are traceable and reproducible;
    • Use a logging service with monitoring and alerting to track verification failure rates and timeout rates, so anomalies in the verifier are caught promptly.

    4.5 Evaluation validity: Avoiding “score gaming”

    Verifiable does not mean immune to optimization. Common risks and countermeasures include:

    • Overfitting to the verifier: A model might discover implementation flaws in the checker and submit artifacts that “exploit loopholes.” The countermeasure is to implement the verifier ahead of the solver and run adversarial tests regularly.
    • Problem contamination: Public problems may be “memorized” by a model. The countermeasure is to keep a private problem set and to include variant problems during evaluation, such as changing scale parameters or constraints.
    • Inconsistent resources: Different systems differ widely in decoding strategy, tool access, and runtime. The countermeasure is to standardize the budget and record it faithfully.
    • A single metric: Looking only at the total score masks the structure of capability. The countermeasure is to report per-problem success rate, sampling success rate, average number of attempts, and the distribution of failure modes together.

    5. Interpreting Results: What One Evaluation Revealed

    5.1 Leading on the total score does not mean leading everywhere

    In the publicly reported evaluation mentioned earlier, the top-ranked system solved 14 theorem-proving problems but failed to solve the “alphabet reliability” problems; some system solved that problem successfully on all three of its attempts.

    This shows that “overall capability” and “capability in a specific direction” are two different things, possibly for three reasons:

    • Training data covers different branches of mathematics unevenly;
    • The skills required by different problems vary greatly;
    • The solving strategy does not match the structure of the problem.

    So when interpreting results, look at performance by dimension rather than just the ranking.

    5.2 Distinguishing “single-shot capability” from “search capability”

    The two models’ data form a sharp contrast:

    • The former solved 14 problems in one pass, showing that its single-shot reasoning is stable;
    • The latter succeeded 23 times in 60 attempts, showing that with ample sampling it can reach more problems.

    The former suits scenarios that demand high stability; the latter better fits research workflows that “allow iteration and are outcome-oriented.”

    5.3 Incremental improvements also carry research value

    • A verified new upper bound can directly shrink the search space for follow-up work;
    • An explicit construction that beats the baseline can serve as a starting point for further improvement.

    Together they show that as long as a conclusion is verifiable, even a gradual improvement has value worth entering academic discussion.

    6. Takeaways for R&D Teams: Building Verifiable Evaluation in Your Own Domain

    6.1 First define a “reviewable artifact”

    Ask yourself: in the tasks your team cares about most, what counts as “done”?

    • If your domain has objective decision criteria, like code, protocols, or data structures, prioritize designing machine-checkable artifacts;
    • If judgment relies on subjective review, first establish a process of two independent reviewers plus arbitration, then gradually introduce automated checks.

    6.2 The verifier comes before the problem set

    The decision logic should be implemented first, thoroughly tested, and version-controlled. Problems are consumables; the verifier is a long-term asset.

    6.3 Anchor difficulty using existing human results

    Collect published baseline values from your domain, such as optimal parameters, known upper bounds, and reference-implementation performance, and use them as “baselines” to judge whether there is “genuine progress.”

    6.4 Keep a private problem set

    Public problems are good for smoke tests; private problems reflect real generalization ability. The private problem set needs to be updated regularly.

    6.5 Make budgets and failure records explicit

    Record the number of attempts, elapsed time, and the distribution of failure reasons. This information is often more useful than the total score for guiding model selection and prompt design.

    6.6 Human-machine division of labor

    Verifiable tasks are well suited to having the model “search” candidate solutions at scale, while humans handle three things: posing problems worth studying, judging the significance of results, and dealing with the parts that cannot be formalized. This is the reasonable boundary of “AI as a research copilot.”

    7. Limitations and Future Directions

    • High formalization barrier: Formal proof languages have a steep learning curve, and the mathematical domains they cover are still limited.
    • Limited problem-set size: Public evaluations usually have a modest number of problems, so single-problem results are easily affected by randomness.
    • Difficulty covering open problems: Major open problems often cannot be judged automatically and still require human expert review.
    • High cost: Formal verification, construction verification, and multiple sampling rounds all consume considerable compute.
    • Future directions:
      • Automated formalization, converting natural-language propositions into machine-checkable form;
      • Learning-based verifiers to help filter out obviously wrong artifacts;
      • Human-machine collaboration paradigms deeply integrated with human research workflows.

    Conclusion

    The core lesson of this evaluation methodology can be summarized in one sentence: turn “looks reasonable” into “can be proven.”

    When a model can hand over verified constructions, tightened bounds, and reusable proofs, AI’s participation in research moves from “assisted writing” to “assisted output.” But it still needs humans to pose questions, set directions, and judge value. Once you understand the design logic of verifiable evaluation, your team can use the same method to map your own AI capability landscape within your domain.