Verifiable Evaluation for AI-Assisted Theoretical Research: Design and Insights

    AI systems are increasingly participating in theoretical research in mathematics and computer science, generating lemmas, counterexamples, and bounds. However, the core challenge lies in verifying whether these outputs are genuine breakthroughs or merely plausible text. This article explores the design principles of verifiable evaluations for AI-assisted theoretical research, categorizing outputs into objects, parameters, and proofs. It outlines fundamental evaluation principles such as clear judgment criteria, tracking prompt information, and conducting multiple trials. Furthermore, it provides guidance on interpreting evaluation results correctly and includes a practical Python example for verifying constructed graph objects.

    I. Problem Background

    AI systems have begun participating in research in mathematics and theoretical computer science, such as proposing lemmas, constructing counterexamples, and tightening known bounds. These outputs share a common challenge: without reliable verification methods, it is difficult to determine whether they represent real progress or merely coherent-sounding text.

    For researchers and engineering teams, the core issue is not whether the model can write a plausible proof, but whether its output can be verified by a third party. The task of evaluation design is to transform “appears correct” into “verifiable.”

    II. Three Types of Verifiable Outputs

    Answers to research-oriented tasks typically fall into three forms:

    1. Objects: Structures such as graphs, codes, or matrices. Their properties can be checked directly by programs, such as the number of vertices, the number of edges, or whether they contain a specific subgraph.
    2. Parameters: Numbers such as bounds, constants, or values. These can be compared with known results or verified using symbolic computation or interval arithmetic.
    3. Proofs: Step-by-step reasoning. Whether each step holds requires manual review or support from formalization tools.

    The verification costs for these three types of outputs differ. Objects and parameters are best suited for automation, while proofs require more manual effort. If an evaluation includes all three types of tasks simultaneously, the report should specify the verification method for each type separately, avoiding measuring all results against the same standard.

    III. Basic Principles of Evaluation Design

    3.1 Clear Judgment Criteria for Each Question

    Tasks must explicitly define what constitutes a correct answer. For example: “Construct a graph with n vertices, no cycles of length 3 or 4, and as many edges as possible.” The judgment criteria include the number of vertices, the number of edges, and a structural check for cycles. When task descriptions are vague, scoring loses its basis, and different reviewers will reach different conclusions.

    3.2 Explicitly Record Prompt Information

    Whether intermediate lemmas, reference constructions, or problem decompositions are provided will significantly alter the task difficulty. The evaluation report should document what auxiliary information was given for each question. Otherwise, two sets of results cannot be compared, and readers cannot determine whether a score stems from the model’s capability or from additional prompting.

    3.3 Multiple Trials and Coverage Statistics

    A single success might be accidental. Conducting multiple independent trials on the same task and recording the number of successes and the number of solved problems provides a more accurate reflection of stability. Coverage of solved problems is particularly important: a system might repeatedly succeed on a few problems but fail to generalize across the entire test set.

    IV. How to Interpret Evaluation Results

    The commonly seen “success rate” in evaluation results requires confirming the denominator first. Suppose in one evaluation, a system completes 14 out of 20 theorem tasks without provided intermediate lemmas, yielding a success rate of 70.0%. Another system makes 60 attempts, succeeds 23 times, and covers 9 different theorems, yielding a success rate of 38.3%.

    These two figures cannot be directly compared. The former counts by question, while the latter counts by attempt, and their problem coverage differs. Readers should check three points: whether the experimental setups are identical, whether the problem sets overlap, and whether the denominator is the number of questions or the number of attempts.

    Composite scores also need to be broken down. In the same leaderboard, one system might succeed in all three attempts for a specific task, while a system ranked higher overall might fail to solve that task. Composite rankings can only summarize general trends and cannot replace task-by-task analysis. Only itemized results can reveal the specific strengths and weaknesses of each system.

    V. Verification Example for Constructive Tasks

    For constructive tasks, the answer is a specific object, and the verification program only needs to read the object itself, regardless of who generated it. The following example checks whether an undirected graph contains no triangles or four-cycles, meaning its girth is at least 5. The input uses an adjacency list format.

    1. def has_triangle(adj):
    2. # A triangle exists if and only if the two endpoints of an edge share a common neighbor
    3. for u in adj:
    4. for v in adj[u]:
    5. if adj[u] & adj[v]:
    6. return True
    7. return False
    8. def has_four_cycle(adj):
    9. # A four-cycle exists if and only if two vertices have at least two common neighbors
    10. vertices = list(adj)
    11. for i, u in enumerate(vertices):
    12. for v in vertices[i + 1:]:
    13. if len(adj[u] & adj[v]) >= 2:
    14. return True
    15. return False
    16. def verify_graph(adj):
    17. # Check if adjacency relations are symmetric, check for self-loops, and count vertices and edges
    18. for u, nbrs in adj.items():
    19. if u in nbrs:
    20. raise ValueError(f"Self-loop exists: {u}")
    21. for v in nbrs:
    22. if u not in adj.get(v, set()):
    23. raise ValueError(f"Asymmetric adjacency relation: {u}-{v}")
    24. edge_count = sum(len(nbrs) for nbrs in adj.values()) // 2
    25. return {
    26. "vertices": len(adj),
    27. "edges": edge_count,
    28. "triangle_free": not has_triangle(adj),
    29. "four_cycle_free": not has_four_cycle(adj),
    30. }
    31. # Example: 5-cycle with 5 vertices
    32. c5 = {0: {1, 4}, 1: {0, 2}, 2: {1, 3}, 3: {2, 4}, 4: {3, 0}}
    33. print(verify_graph(c5))
    34. # {'vertices': 5, 'edges': 5, 'triangle_free': True, 'four_cycle_free': True}

    This code illustrates three key points:

    First, input validation comes first. Symmetry and self-loop checks eliminate formatting errors, preventing invalid objects from being mistakenly judged as valid.

    Second, the judgment criteria correspond exactly to the mathematical definitions. The checks for triangles and four-cycles rely on the existence and quantity of common neighbors, respectively, with logic drawn directly from the definitions.

    Third, the results are reproducible. The same adjacency list will yield identical judgments in any environment.

    If the constructed graph has more edges than known reference values, after the verification program passes, it is still necessary to confirm whether the task conditions are entirely consistent, such as the number of vertices and the allowed range of cycle lengths. Passing the verification only indicates that the object meets the task requirements.