LLM Math Evaluation: New Boundaries Drawn by Theoretical Computer Science
This article explains why public math contests and routine problem sets are no longer sufficient for evaluating the research-level mathematical ability of large language models. Using theoretical computer science as the evaluation framework, it breaks down capability dimensions, benchmark construction, contamination resistance, layered grading, sampling metrics, common failure modes, and the real boundaries of current AI mathematical research. It also describes how to build verifier-in-the-loop systems that convert model output into usable engineering workflows without relying on unchecked model self-confidence.
1. Why “Math” Is No Longer Enough
In recent years, the mathematical performance of large language models has improved rapidly. Public competition problems, large question banks, and unit-test-style algorithm tasks have all been pushed to new score levels. Yet an awkward fact has emerged at the same time: as problems become more exam-like, model scores increasingly resemble a measure of test-taking ability, while mathematical research itself is still barely measured.
To understand this mismatch, it helps to separate two different perspectives.
Software engineers usually ask how to build things: which data structure to choose, how to optimize performance, and how to keep a service stable when traffic doubles. This is an engineering perspective. Theoretical computer science, or TCS, asks a different question: what is the intrinsic cost of computation? For the same problem, what is the minimum number of steps needed to move from one state to another? Are some paths fundamentally impossible? If an algorithm claims to run faster, can its correctness be proved rather than merely demonstrated on a few examples?
A useful analogy is this: engineers are like drivers thinking about engines, transmissions, and interiors, while TCS studies traffic itself—road network capacity, the limits of shortest paths, and which intersections will inevitably become congested under any scheduling strategy. The former optimizes performance under fixed conditions; the latter characterizes the boundaries of those conditions.
What makes TCS distinctive is that its primary output is proof. This gives it a property that many disciplines envy: correctness can be checked mechanically. When a conjecture is claimed to be resolved, peers do not necessarily need to rerun experiments or reproduce data collection. They can instead verify the reasoning chain step by step. This is both an opportunity for evaluating large language models and the central difficulty of doing so.
2. Breaking Down Evaluation Capabilities by Dimension
If TCS is to be used to evaluate large language models, the first question is what exactly should be tested. Calling everything “math problems” is not useful, because different subfields demand very different capabilities and have very different levels of verifiability. The table below breaks the task into dimensions.
| Capability Dimension | Typical Task Form | Answer Form | Automatability |
|---|---|---|---|
| Algorithm design and upper-bound analysis | Give an algorithm and prove a complexity upper bound | Construction + proof | Medium, with partial formal checking |
| Lower-bound proofs | Prove that a problem cannot be solved efficiently by a class of models | Pure proof | Low to medium |
| Reductions and hardness | Reduce a known hard problem to the target problem | Construction + correctness argument | Medium |
| Interactive proofs and protocols | Design a protocol between verifier and prover and argue soundness | Protocol + probabilistic analysis | Low |
| Approximation algorithms and inapproximability | Give an approximation ratio and prove tightness | Algorithm + two-sided proof | Low |
| Randomization and pseudorandomness | Analyze expected complexity or construct pseudorandom objects | Probabilistic analysis | Low to medium |
| Extremal combinatorics and Boolean function analysis | Establish inequalities or give extremal constructions | Construction + inequality chain | Medium |
| Formalization | Translate semi-formal proofs into machine-checkable scripts | Proof script | High |
The key conclusion from this table is that testability is not proportional to importance. The dimensions that can be automatically verified by scripts—formalization, arithmetic simplification, and complexity calculation—are often the more surface-level skills. In contrast, lower-bound proofs, tightness arguments, and cross-domain tool transfer, which better reflect research-level ability, are extremely difficult to grade.
This creates a design tension for TCS-style benchmarks: the more research-valuable a problem is, the harder it is to grade automatically; the more automatic the grading is, the more the problem degenerates into routine exercise. Any benchmark claiming to comprehensively evaluate theoretical computer science research ability must explain how it mitigates this tension. Otherwise, its score is just a carefully packaged question-bank accuracy rate.
3. Engineering a Reproducible Evaluation Pipeline: From Problems to Scores
A benchmark built jointly by academic researchers and a large-model team is valuable not only because it produces a scorecard, but because it turns the construction of a trustworthy, contamination-resistant, and reproducible evaluation pipeline into a reusable method. Its engineering skeleton can be broken down as follows.
1. Problem Acquisition and Compliance
Usable problem sources usually fall into three categories: published textbooks and classic exercises, which are authoritative but easily covered by training data; public problems from recent conferences and journals, which are timely but uneven in difficulty; and researcher-authored problems that have been reviewed, which are controllable but limited in throughput. For engineering purposes, each problem should record its first public date. This field is essential for later contamination analysis.
2. Contamination Resistance: Difficulty Is Not the Only Variable
The most fatal problem in large-model evaluation is not that a problem is hard, but that the model has already seen it. If a problem or its solution entered the training corpus in some form, the score loses meaning. Common methods include:
- Time-based holdout: Keep only problems first published after the model’s training cutoff as a holdout set, and report them separately from the public set.
- Semantically equivalent rewriting: Preserve the mathematical structure while changing the narrative wrapper, variable names, or parameter values, then observe score degradation. Significant degradation suggests that the model relies on memory rather than reasoning.
- Answer perturbation: Give only the problem statement without a reference answer, or provide a plausible but incorrect “standard solution,” to test whether the model can critically check answers.
- Private holdout sets: Never release core problems publicly; release only scores and aggregate statistics.
3. Metadata and Problem Statements
Problems must be structured, or the pipeline will not scale. A practical schema is shown below:
{"id": "tcs-0413","area": "lower_bound","subfield": "algebraic_complexity","difficulty": "research_frontier","statement": "... (semi-formal problem statement)","formal_statement": "optional/formal/0413.v","reference_solution": "...","checker": {"type": "formal_script","entry": "verify/0413.py","timeout_s": 120},"leakage": {"first_public_date": "2026-03-02","is_public": true},"tags": ["requires_constructive_counterexample", "long_chain"]}
The formal_statement field deserves special emphasis. For the same mathematical proposition, providing both a natural-language version and a formal version expressible in a theorem prover is the only reliable way to separate “understanding the problem” from “executing the reasoning.” Without this field, when a model gives a wrong answer, it is impossible to tell whether it misunderstood the problem or understood it correctly but made a reasoning error.
4. Layered Scoring
A single binary score erases the most informative part of the evaluation. A useful layered structure is:
- L0 final verdict: Whether the final answer or complexity expression is correct. This is cheap and automatable, but carries the least information.
- L1 structural verdict: Whether the proof skeleton contains required components, such as construction, induction base, induction step, and tightness counterexample. This can be checked with rules or classification models.
- L2 formal verdict: Pass the model-generated proof to a formal checker and verify it item by item. This is the only automated method that approaches reviewer-level credibility.
- L3 human verdict: Researchers sample and arbitrate results, used to calibrate bias in L0–L2.
A key engineering principle is that the accuracy of the scorer itself must be evaluated separately. If a model is used as a judge to evaluate other models, the agreement rate between the judge and human annotation must be reported. It is also necessary to test whether the judge has preferences for length, formatting, or its own output style. Without this step, all downstream conclusions are unsupported.
5. Sampling and Aggregation Metrics
Single-shot sampling is almost meaningless in this setting because reasoning chains are long and variance is high. The standard practice is to sample multiple times and aggregate:
# Illustrative pseudocode for aggregation in an evaluation pipelinefrom concurrent.futures import ThreadPoolExecutorimport statisticsdef solve_once(client, item, temperature=0.7):resp = client.chat(model=MODEL,messages=[{"role": "system", "content": SYSTEM_PROMPT},{"role": "user", "content": item["statement"]},],temperature=temperature,)return resp["choices"][0]["message"]["content"]def judge(client, item, answer):ck = item["checker"]if ck["type"] == "formal_script":return 1 if run_in_sandbox(ck["entry"], answer)["verified"] else 0return 1 if llm_judge(client, item["reference_solution"], answer)["pass"] else 0def evaluate(client, item, k=8):with ThreadPoolExecutor(max_workers=k) as pool:answers = list(pool.map(lambda _: solve_once(client, item), range(k)))verdicts = [judge(client, item, a) for a in answers]return {"pass@k": int(any(verdicts)),"maj@k": int(sum(verdicts) > len(verdicts) / 2),"consistency": sum(verdicts) / len(verdicts),"mean_tokens": statistics.mean(len(a.split()) for a in answers),}
These three metrics measure three different capabilities and should not be conflated:
pass@kmeasures potential ceiling—whether the model can find a correct path when allowed sufficient retries.maj@kmeasures stable usability—whether the majority vote over multiple independent attempts is reliable, which directly corresponds to real-world usage.consistencymeasures self-consistency—a score approaching 1 means the problem has become routine; a score approaching 0.5 means the model is basically guessing. The sensitive range is when consistency is between these extremes andpass@kis significantly higher thanmaj@k. This is where “the capability truly exists but is unreliable,” and it is also the most valuable research region.
From an engineering perspective, a model with high pass@k but low maj@k is not stronger than one that is low on both. The former confidently produces wrong answers, which is riskier in automated scenarios.
4. Capability Profile: Where Models Are Strong and Where They Fail
Across public evaluations, frontier models show a highly structured but uneven distribution of strengths and weaknesses on TCS-style tasks.
Relatively reliable capabilities include standard algorithm design and complexity derivation; correctly instantiating known theorems to concrete parameters; selecting and applying standard probability inequalities such as concentration bounds and union bounds; mechanically translating formal expressions; and restating definitions and relationships of concepts from the literature. These tasks share common features: transferable templates exist, reasoning chains are medium-length, and intermediate steps can be locally checked.
Clearly weak capabilities include constructing genuine lower bounds; giving tight examples and proving their tightness; transferring tools across subfields, such as applying Boolean function analysis to communication complexity; maintaining invariants over long proof chains without silently changing them; and recognizing when a problem lacks sufficient conditions or when a conjecture is actually a known open problem.
The most typical failure modes are not arithmetic errors, but four structural defects:
- False lemmas: The model cites an intermediate result that seems plausible but is false or nonexistent, and then builds the entire later argument on it. Because the prose is fluent and the notation is standard, such errors are extremely hard to detect at the natural-language level.
- Circular reasoning: The conclusion appears in weakened form inside the premises, and detecting it requires global comparison.
- Scale or magnitude drift: An inequality in the first half of the derivation has the correct direction, but at some later step in a long chain it silently reverses, while the formal layout remains normal.
- Overconfident overreach: Facing an open problem, the model does not admit uncertainty but instead produces a complete and confident “proof.” In research settings, this is far more dangerous than simply failing to answer.
These failure modes share a common explanation: the model’s strength is locally coherent sequence generation, while the correctness of mathematical proof depends on global constraint consistency. The tension between these two factors is the source of current capability boundaries.
5. The Real Position of the Current AI Mathematical Research Frontier
The core question is: where does this kind of evaluation place the frontier of mathematical research? My judgment is that the boundary is not about whether a model can calculate, but about four levels, with decreasing strength of constraint.
Level 1: Verification boundary, the hardest constraint. A model can generate proofs that look correct, but it cannot prove its own correctness. It performs well on automatically verifiable parts, but on non-automatically-verifiable parts its output cannot be distinguished from correct answers at the text-distribution level. This means current models cannot independently take on the role of “researcher.” They can only take on the role of “research assistant”—unless they are connected to external verifiers, in which case their output is merely candidate material in the eyes of human experts.
Level 2: Formalization boundary. Translating natural-language propositions into formalized propositions can be automated, but the translation process itself may introduce a drift that is not equivalent to the original intent. Formal verifiers can only ensure that “the script contains no internal contradiction”; they cannot ensure that “the script expresses the proposition you intended to prove.” This boundary is not a model capability issue, but an epistemological limitation of formal methods themselves. No model can bypass it.
Level 3: Problem-definition boundary. The hardest step in real research is deciding what to prove. Topic selection requires judging importance, feasibility, and relation to existing work, but all problems in an evaluation set have already been selected and clearly stated by humans. Models perform reasonably well on solving given problems, but their ability to propose worthwhile problems has barely been measured, and there is no evidence that they possess this ability.
Level 4: Creativity boundary, the most ambiguous constraint. Are there problems that require truly novel concepts to solve? Existing benchmarks struggle to give a definitive answer because most problems can be approximated by combining existing tools. This level should remain unknowable in the short term, rather than being claimed as already crossed or far from being crossed.
A more accurate conclusion is therefore this: current frontier models are already capable enough in TCS to serve as tireless, broad-knowledge research assistants who still require supervision throughout the process. What separates them from independent researchers is not parameter count, but verification loops, problem selection, and reliable self-assessment. The real contribution of evaluation is to turn this boundary from a vague impression into a measurable quantity.
6. From Evaluation to Deployment: Building Usable Reasoning-Augmented Systems
Once the boundary is known, the engineering question becomes: how can model capability be converted into deliverable value without crossing that boundary? The answer revolves around one idea: a verifier-in-the-loop system.
1. Put Verifiers Inside the Loop, Not Outside It
A common misuse is to ask once and directly trust the answer. The correct approach is to embed external capabilities such as symbolic computation, numerical experiments, and formal checking tools into the reasoning loop, allowing the model to self-correct based on feedback:
# Illustrative pseudocode: a reasoning loop with external verifiersSYSTEM = """You are a theoretical computer science research assistant. Constraints:1) Every lemma must be independently verifiable; do not introduce unproven assertions;2) Output a structured proof tree whose leaf nodes are mechanically checkable equations or inequalities;3) Explicitly label incomplete parts as UNSOLVED; never fabricate intermediate results;4) Every revision must cite the diagnostic information from the previous verifier."""async def research_loop(model, tools, problem, budget=6):tree = await model.propose_proof_skeleton(problem, SYSTEM)for node in tree.leaves():for _ in range(budget):check = await tools.verify(node) # symbolic simplification / numerical experiments / formal checkingif check.status == "verified":node.status = "verified"breaknode = await model.repair(node, check.diagnostics)else:node.status = "unresolved"return tree
This structure separates unreliable generation from reliable verification: the model proposes candidates, tools adjudicate, and the loop drives convergence. Its upper bound is constrained by tool capability, but its lower bound is much higher than single-shot generation. Failures are also diagnosable: one can point to which lemma failed verification, rather than vaguely saying the model “got it wrong.”
2. Suppress Overconfident Overreach with Forced Confidence Expression
Constraints should be applied at both the prompting and post-processing levels. Require the model to annotate the basis of each lemma, such as “existing theorem,” “construction in this work,” or “to be proved.” When the argument cannot be closed, require the model to output UNSOLVED instead of filling in the gap. At the same time, use consistency from multiple samples as an uncertainty signal. Low-consistency conclusions should automatically enter a human review queue. This is a direct way of moving evaluation methodology into the product workflow.
3. Engineering and Cost
Deploying such a system depends on several general engineering capabilities. Computational tasks need to run in isolated sandboxes, with timeout and resource limits enforced. Every sample, verification, and repair step should be written to auditable structured logs for regression evaluation and cost attribution. Large-scale sampling creates significant compute overhead, requiring queue-based peak shaving, cache reuse, and task-tiered retry strategies. Latency and failure rates for model calls, verifier calls, and human review should be unified into monitoring and alerting systems rather than scattered across different places. These capabilities can be assembled from general cloud service categories—containerized runtime environments, object storage for problems and logs, message queues for sampling peak shaving, logging services, and monitoring and alerting—without relying on proprietary interfaces.
4. Productize the Evaluation Itself
Every time a model is iterated, the evaluation set must be rerun. This requires the evaluation pipeline to support version management, binding problem versions, scorer versions, and prompt versions; result archiving; regression comparison; and contamination detection for newly added problems. Otherwise, after six months you will have a collection of historical scores that cannot be compared horizontally.
7. Conclusion
The most valuable aspect of TCS-style evaluation is not that it produces a new leaderboard, but that it forces the industry to separate two fundamentally different questions: whether a large model can solve math problems and whether a large model can do mathematical research. The former tests pattern recognition and template transfer. The latter requires verifiability, problem selection, and global consistency—and these are exactly the real gaps revealed by evaluation.
For developers, the conclusion is clear and actionable. Do not expect models to independently produce proofs that can be trusted without verification. Instead, position yourself as the designer of the verification loop: delegate reliable judgment to tools, delegate broad exploration to models, and explicitly expose uncertainty rather than letting fluent prose hide it. When the verification layer is strong enough, the model’s capability boundary shifts from “unusable” to “the usable upper limit.” That step is precisely where engineering creates value.
