Why Verifiable Output Matters: A Top AI Agent's Peak Shows in One Query, Products Decide the Rest
TCSExam, a verifiable evaluation framework co-developed by a Chinese large-model company's founder-CEO and Turing Award laureate Andrew Yao, reframes AI agent evaluation around theoretical computer science research tasks. This article explains why verifiable, machine-checkable artifacts matter more than answers that merely look correct, and walks through the leaderboard's core metrics—difficulty weighting, the no-hint full-proof rate, and multi-attempt pass rates. It also provides an engineering blueprint for building comparable systems, covering a five-layer architecture, sample evaluation code, safeguards against data contamination, and three common misreadings of leaderboard scores, before outlining the framework's limitations.
1. From Answering Questions to Doing Research: Why Evaluation Needs a Paradigm Shift
The founder and CEO of a Chinese large-model company has, for the first time, co-authored a research paper with Andrew Yao, a chief professor from Tsinghua University’s Institute for Interdisciplinary Information Sciences (“Yao’s Class”) and a Turing Award laureate. Together they propose TCSExam, a theory-oriented evaluation system spanning branches of Theoretical Computer Science (TCS) such as combinatorial mathematics, coding theory, probabilistically checkable proofs, and computational complexity. The paper’s core idea fits in one sentence: put the objects, parameters, and proofs produced during the research process into a single, verifiable evaluation system.
Two points stand out in this system:
- Multi-track, unified evaluation: Different research stages—“produce a new construction,” “find optimal parameters,” “complete a full proof”—are organized under one framework.
- Machine-checkable: What the tested agent produces is no longer an answer that merely “looks reasonable,” but an artifact that can be independently verified.
This approach matters because existing benchmarks struggle to capture “research capability.” Common evaluations fall into three categories, each with clear weaknesses:
| Evaluation type | Typical form | Main limitation |
|---|---|---|
| Knowledge and reasoning | Multiple-choice, short-answer | Real reasoning can be bypassed via retrieval or memorization, and scoring depends on reference answers |
| Code | Programming problems, unit tests | Focuses on engineering implementation; hard to assess constructive proofs and optimality judgments |
| Competition math | Problem solving, proof writing | Proof grading relies on human or model judges, making consistency hard to guarantee |
The idea behind TCSExam is to make the artifacts of research work themselves the object of evaluation. No matter which workflow produces the result, it must satisfy objective, verifiable acceptance criteria to count as a “solved problem.”
2. Verifiability: The Foundation of an Evaluation System
2.1 Artifact Types: Four Machine-Checkable Research Objects
By nature, evaluation objects fall into four categories:
- Constructions: such as graph structures in graph theory, combinatorial designs, and coding schemes. Evaluation directly checks whether the object satisfies its constraints—for example, girth requirements or minimum-distance requirements—then compares quality metrics.
- Parameters: such as extremal function values, upper or lower bounds on coding parameters, and complexity lower bounds. Evaluation compares the produced value against the current best-known value to determine whether substantial progress was made.
- Proofs: such as a complete derivation of a proposition or a new theorem proved from known results. Evaluation focuses on whether each reasoning step holds.
- Refutations: such as finding a counterexample that overturns a conjecture, or proving that no solution exists under certain conditions. Evaluation checks the completeness and correctness of the counterexample.
Whatever the category, the shared requirement is “verifiable results.” Typical cases from the paper illustrate this directly:
- Extremal graph theory construction: The agent must construct a simple graph with as many edges as possible that contains neither triangles nor quadrilaterals. It produces a concrete graph with 124 vertices and 630 edges, exceeding the task’s 629-edge reference value.
- Tightening a coding bound: On a task to solve the parameters of the binary error-correcting code A(22,10), a leading model proves A(22,10) ≤ 82, tightening the published upper bound from 84 to 82.
Neither depends on subjective judgment; both hinge on machine-checking results: whether the object satisfies the constraints, whether the derivation holds, and whether the result surpasses the baseline.
2.2 Why “Verifiable” Matters More Than “Looks Correct”
Large language models are already quite mature at generating fluent text. So producing a well-formatted “proof” with complete terminology is not hard—what is hard is making every step stand up to scrutiny. The value of verifiable evaluation shows up in three main ways:
- Strong discrimination: Correctness is decided by machines, not by a grader’s subjective impression.
- Resistant to memorization and guessing: Constructed objects and parameter results cannot be guessed by reciting templates; each output must be an independent, checkable mathematical object.
- Traceable: Artifacts are archived together with the solving process, supporting both verification and error analysis.
It is worth emphasizing that “verifiable” does not mean “simple.” As long as the checker is well designed, genuinely hard tasks can still be judged automatically. Take the “triangle-free and quadrilateral-free” graph: verification only needs to rule out triangles and quadrilaterals (a simple graph has no self-loops or multi-edges, so its girth is at least 3). Triangle detection can be done in O(n^ω) time, where ω is the matrix multiplication exponent (the best current upper bound is about 2.3714); quadrilateral detection can be done in O(m^{3/2}) time, where m is the number of edges. For graphs on the order of a hundred vertices, verification completes in milliseconds.
By contrast, having a model independently prove A(22,10) ≤ 82 demands computational complexity far beyond this. So “automatically checkable” only means that scoring is cheap and reliable—not that the task itself is simple.
2.3 Design Principles for Verifiable Artifacts
To design a verifiable evaluation system, the first step is to define what the agent’s “deliverable” is. The following principles are recommended:
- The deliverable must be an object, not a narrative: Use acceptance criteria like “produce a graph,” “produce a coding construction,” “produce a complete proof,” rather than “explain the idea.”
- Build the checker before the problem set: Each problem needs independently written verification logic, decoupled from the problem-generation process, so the checker and the generator do not make the same mistake.
- Separate “pass/fail” from “better/worse”: The former determines whether a problem is solved; the latter measures quality, such as how many edges a graph has or how much an upper bound was tightened. The two can be defined separately and combined into a score.
- Preserve the full process: Archive artifacts along with intermediate steps to localize the point of failure—an enumeration error, a construction error, or a gap in the proof.
3. Leaderboard Structure: Measuring Different Capability Dimensions
3.1 The Full Leaderboard and “Difficulty Weighting”
TCSExam’s Full leaderboard ranks overall solving performance. According to the paper’s published data, the leading Model A takes first place with 71.9 points, and Model B ranks second with 57.4 points.
Because problem difficulty varies widely, directly counting “how many problems were solved” tends to let the hardest, highest-scoring problems dominate the result. A more reasonable approach is difficulty weighting, which can be expressed with the following illustrative formula:
TotalScore = 100 × Σ(w_i · s_i) / Σ w_i
Here w_i is the weight of problem i, reflecting its difficulty or research value; s_i is the score rate in the range 0–1, which can be split by completion level—for example, a base score for producing a compliant object and an incremental score for quality beyond the baseline.
3.2 No-Hint Solve Rate: Testing Whether Capability Is Genuine
Beyond rankings, the paper also reports how models perform on theorem-proving tasks without intermediate lemmas:
| Model | Full proofs completed | Success rate |
|---|---|---|
| Model A | 14 / 20 | 70.0% |
| Model B | 0 / 20 | 0% |
| The other six agents | — | All no more than 11.7% |
“Without intermediate lemmas” is the key to this statistic. In real research, researchers usually do not know at the outset which lemmas need to be proved; the ability to independently decompose a problem and find the key intermediate steps is precisely at the core of research capability.
Hints change task difficulty significantly:
- With lemmas provided: Solving degrades into “completing a proof along a known path,” mainly testing execution.
- Without lemmas: The model must decide on its own which auxiliary results are needed and prove them, testing planning and exploration.
Therefore, when comparing different agents, the prompting conditions must be unified; otherwise the data are not comparable.
3.3 Multi-Attempt Pass Rate: Characterizing Exploration Ability
The paper also reports pass rates under multiple sampling. Take second-place Model B as an example: across 60 attempts it succeeded 23 times, covering 9 different theorems, for a success rate of 38.3%. Two easily confused concepts need to be clarified:
- Number of attempts k: the total number of independent attempts allowed per problem.
- Number of theorems covered: the number of problems solved at least once.
The two mean different things: 38.3% reflects “the probability of success on an average attempt,” while 9 theorems reflect “how many problems can ultimately be solved reliably.”
This definition can also be understood from a sampling perspective. If a task gets k independent attempts with success probability p each, the problem pass rate (at least one success) is:
Problem pass rate = 1 − (1 − p)^k
When p = 0.383 and k = 60, the per-problem pass rate is about 1 − 0.617^60 ≈ 0.99999996, nearly 1. From this it can be estimated that the 9 covered theorems are likely close to this model’s “coverage ceiling” at the given attempt count. In other words, even if the number of problems were increased to 10, the model would most likely still solve only 9 reliably.
This exposes a common misreading: a high per-problem pass rate does not equal high solving capability. The reason is that task difficulty varies enormously:
- Easy problems: the single-attempt success rate is close to 1, so more attempts are pointless.
- Hard problems: the single-attempt success rate is extremely low, and even more sampling rarely translates into stable output.
Therefore, the single-attempt success rate and the multi-attempt pass rate need to be read together: the former reflects “everyday performance,” while the latter characterizes the “capability ceiling.”
3.4 One Leaderboard Is Not Enough: A Capability Profile Matters More Than a Total Score
Total scores and overall pass rates reflect average strength, but the source indicates that the results were not a one-sided, across-the-board lead. For example, on the alphabet reliability task for Probabilistically Checkable Proofs (PCP), Model B completed all three attempts, while Model A failed to solve it.
This shows that different models have different capability structures:
- Some models excel at “building from scratch,” completing multi-step proofs without hints.
- Others excel at “strictly executing along an existing path,” performing stably on specific reasoning tasks within a bounded scope.
So a ranking can only reflect average overall strength; model selection calls for a capability profile:
| Dimension | Corresponding metric | Applicable scenario |
|---|---|---|
| Full solving ability | No-hint full-proof rate | Open-ended research tasks that need independent problem decomposition |
| Average success rate | Multi-attempt pass rate | Batch tasks, automated pipelines |
| Exploration ceiling | Number of problems covered | Retry-friendly settings aiming for the best result |
| Specific capability | Per-domain, per-task-type scores | Specialized vertical scenarios |
4. Engineering Implementation: Building a Comparable Verifiable Evaluation System
4.1 Overall Architecture
A verifiable evaluation system is typically divided into five layers, each with clear responsibilities:
- Problem-set layer: stores problems, difficulty labels, hint tiers, and reference answers.
- Execution layer: assigns an independent sandbox to each attempt to isolate interference between tasks.
- Verification layer: invokes the appropriate checker based on artifact type and returns structured results.
- Scoring layer: computes scores by rules such as difficulty weighting and partial credit, and aggregates the statistics.
- Analysis layer: accumulates error cases and failure patterns to form capability-profile reports.
4.2 Evaluation Framework Skeleton (Illustrative Code)
The following is product-agnostic illustrative code that demonstrates the basic structure of verifiable evaluation:
import heapqfrom dataclasses import dataclassfrom itertools import combinationsfrom typing import Any, Optional, Protocol@dataclass(frozen=True)class Task:task_id: strtrack: str # Branch: ExtremalGraph / Coding / PCP / Complexity ...difficulty: int # Difficulty weight, used for Full leaderboard weightingprompt: str # Problem statementhints: tuple[str, ...] = () # Tiered hints: whether to release intermediate lemmas in the first round@dataclass(frozen=True)class Cost:tokens_in: int = 0tokens_out: int = 0tool_calls: int = 0elapsed_ms: int = 0@dataclass(frozen=True)class Verdict:passed: boolmetrics: dict # Objective metrics: edge count, code distance, bound tightening, etc.reason: str = ""class Agent(Protocol):"""Unified interface for the agent under test, hiding differences in the underlying model and toolchain"""def solve(self, task: Task, use_hints: bool = False) -> tuple[Any, Cost]:...class GraphAgent(Agent):"""Illustrative implementation: construct a simple graph with no triangles or quadrilaterals"""def solve(self, task: Task, use_hints: bool = False):n = task.n_vertices # Number of vertices given by the problemedges = [(i, (i + 1) % n) for i in range(n)] # Start with a ring as the base constructionreturn {"n": n, "edges": edges}, Cost()def local_search(self, graph, steps: int):"""Perform local search within the feasible region to increase the edge count, illustratively"""return graphclass Verifier(Protocol):"""Checker interface: takes an output object and returns whether it passes + structured metrics"""def verify(self, task: Task, output: Any) -> Verdict:...class GirthVerifier(Verifier):"""Verify that the graph has no triangles or quadrilaterals; more edges means a better metric"""def verify(self, task: Task, output: Any) -> Verdict:g = outputn = g["n"]edges = list({tuple(sorted(e)) for e in g["edges"]})# 1) Structural validity: vertex indices in range, no self-loops, no multi-edgesif n != task.n_vertices or any(not (0 <= u < n and 0 <= v < n) or u == v for u, v in edges):return Verdict(False, {}, "Vertex count mismatch or illegal edge present")if len(edges) != len(g["edges"]):return Verdict(False, {}, "Multi-edges present")# 2) Constraint check: no triangles or quadrilaterals <=> any two vertices share at most one common neighboradj = [set() for _ in range(n)]for u, v in edges:adj[u].add(v)adj[v].add(u)for u, v in combinations(range(n), 2):if len(adj[u] & adj[v]) > 1:return Verdict(False, {}, f"({u}, {v}) has two common neighbors")# 3) Quality metric: whether the edge count exceeds the problem's baselinem = len(edges)return Verdict(passed=True,metrics={"vertices": n, "edges": m, "excess": m - task.baseline_edges},)def evaluate(task: Task, agent: Agent, verifier: Verifier,k: int = 1, use_hints: bool = False) -> dict:"""Single-problem evaluation: run k independent attempts, recording pass count, best metrics, and cost"""best: Optional[Any] = Nonebest_metrics: dict = {}passed = 0total = Cost()for _ in range(k):output, cost = agent.solve(task, use_hints=use_hints)total = Cost(tokens_in=total.tokens_in + cost.tokens_in,tokens_out=total.tokens_out + cost.tokens_out,tool_calls=total.tool_calls + cost.tool_calls,elapsed_ms=total.elapsed_ms + cost.elapsed_ms,)verdict = verifier.verify(task, output)if verdict.passed:passed += 1# Use edge count as the comparison basis; keep the current best constructionif best is None or verdict.metrics["edges"] > best_metrics.get("edges", -1):best, best_metrics = output, verdict.metricsreturn {"task_id": task.task_id,"attempts": k,"passed": passed,"single_pass_rate": passed / k, # Single-attempt success rate"task_passed": passed > 0, # Whether this problem was solved at least once"best_metrics": best_metrics, # Best artifact metrics"best_output": best,"cost": total,}def build_leaderboard(records: list[dict]) -> dict:"""Aggregate leaderboard: compute the Full score by weights and count problem coverage"""w_sum = sum(r["difficulty"] for r in records)full_score = 100 * sum(r["difficulty"] * r["single_pass_rate"] for r in records) / w_sumcovered = sum(r["task_passed"] for r in records)return {"full_score": round(full_score, 1), # Weighted total score consistent with the public leaderboard"covered_tasks": covered,"coverage": covered / len(records), # Proportion of problems ultimately covered under multiple attempts"weighted_attempts": sum(r["difficulty"] * r["attempts"] for r in records),}
This code embodies four key designs:
- Unified artifact structure: The agent outputs research objects as dictionaries (such as a graph’s vertex count and edge set), so the checker does not care where the model comes from.
- Independent verification logic: Constraint checking and quality comparison are separated—the former decides pass/fail, the latter decides metric quality.
- Separate statistics for single-attempt success rate and coverage: matching the two metric types discussed in Section 3.
- Weights in the computation: difficulty enters the score, preventing easy problems from diluting the result.
4.3 Preventing Data Contamination and Evaluation Distortion
In research-oriented evaluation, training-data leakage is the most common and most hidden source of contamination. Because many mathematical theorems, graph constructions, and coding bounds already have published literature, models may have “seen the answers” during training. The following measures are recommended:
- Prefer new-construction tasks: With the form “produce a construction better than the existing baseline,” even if the model has seen the relevant background, it still must search within the feasible region.
- Keep key problems private: Critical problems are used only for evaluation; their complete answers are not published.
- Refresh problems and baselines periodically: As new results are published, update the reference values and difficulty weights.
- Check consistency: For a small number of problems, cross-verify with human review or formal verification tools to ensure the checker itself has no flaws.
4.4 Resource and Security Boundaries
- Resource isolation: Each attempt runs in an independent sandbox with limits on runtime and resource usage.
- Controlled retry budget: Multiple attempts multiply costs. The retry count k should be set based on business needs: critical tasks can increase retries, while routine tasks should focus on the single-attempt success rate.
- Access control: When evaluation assets (problem sets, answers, results) are sensitive, implement proper permission management and access auditing, and keep operation logs.
5. Interpreting Results: Three Common Misreadings
Misreading 1: “First Place = Across-the-Board Lead”
As mentioned earlier, Model B succeeded on all three attempts on the PCP alphabet reliability task, while Model A failed to solve it. A total score only reflects average overall performance; specific selection should return to the scenario: if a task requires independent problem decomposition, the no-hint full-proof rate is more informative; if a task is specific reasoning within a bounded scope, per-task scores are more meaningful.
Misreading 2: “With Enough Attempts, a Model Can Solve Everything”
From “problem pass rate = 1 − (1 − p)^k,” problems with a low single-attempt success rate require a great many attempts to reach a high pass rate—and such ample attempt budgets often do not exist in practice. For example, with p = 0.05, reaching a 95% probability of at least one success requires about 59 independent attempts. So an evaluation should report both the “single-attempt success rate” and the “pass rate under a limited number of attempts,” avoiding overestimating capability by showing only the latter.
Misreading 3: “Evaluation Score = Research Ability”
TCSExam measures verifiable theoretical research output—such as construction, proof, and bound-finding. It does not cover every aspect of research, such as:
- Topic selection and research taste;
- Experiment design and resource planning;
- Paper writing and academic communication.
Therefore, an evaluation score should be seen as part of a capability profile, not a complete substitute for research ability.
6. Limitations and Outlook
The current verifiable evaluation system still has room for improvement:
- Limited verification coverage: Formal verification of proof tasks is costly, and many proofs still rely on machine-checking key steps or human review.
- Narrow task types: Problems are mainly concentrated in combinatorics and theory, making it hard to cover broader capabilities such as open-ended research and interdisciplinary synthesis.
- Statistical conventions need unification: Different retry counts, hint strategies, and difficulty weights make cross-evaluation comparisons difficult and call for a more consistent evaluation protocol.
- Capability evolution needs continuous tracking: Models iterate quickly, so a one-time leaderboard quickly becomes outdated; a periodic, incremental evaluation mechanism is needed.
Even so, the principle established by this approach is universal: evaluation objects should be verifiable, and artifacts should be reviewable. This principle applies equally to internal model selection and quality assessment in enterprises. Whether evaluating AI coding tools or assessing an agent’s data processing and analysis capabilities, teams should let “results” rather than “expression” be the basis for judgment.
In enterprise practice, Baidu AI Cloud’s general cloud services can support this kind of evaluation system:
- Use a container platform to run sandboxed verification and execution tasks;
- Use object storage to archive problem sets, artifacts, and run records;
- Use a message queue to connect the “execute–verify–score” pipeline;
- Use logging and monitoring/alerting services to track core metrics such as success rate and cost.
7. Conclusion
For the progress of “a leading agent and a Turing Award laureate joining forces to build a theoretical research evaluation system,” what developers should truly care about is not how any single ranking turns out, but the methodology it establishes: replacing subjective impressions with verifiable artifacts, replacing a single total score with multi-dimensional metrics, and replacing a vague “looks reasonable” with rigorous process records. For any team hoping to deploy large models in real business settings, this approach can be adopted directly.
