Evaluating LLM Math and Theoretical Computer Science Capabilities: A Methodology Guide
As public benchmarks fill up and stop separating top models, researchers are turning to harder, more rigorous evaluations. Theoretical Computer Science (TCS) is one such pressure test. This article reviews the methodology behind building a TCS-style evaluation suite for frontier LLMs: the capability dimensions it covers, the five key steps for constructing a high-quality benchmark, the boundaries current models reveal, and the engineering considerations for running evaluation at scale.
1. Why General Leaderboards Are No Longer Enough
Over the past few years, large language models have climbed quickly on math and code benchmarks, and many public leaderboards have been progressively “maxed out.” Once high scores no longer separate good models from bad ones, researchers have shifted toward evaluation directions that are closer to real research work, harder, and more demanding of rigorous reasoning.
Theoretical Computer Science (TCS) is an ideal pressure test for exactly this reason: its problems usually require little domain prior knowledge, yet place extremely high demands on the completeness of the logic chain and the rigor of the proof.
A research team led by a Turing Award laureate, together with academic and industry researchers, built a TCS evaluation system for frontier LLMs along these lines. Setting aside specific project names, this article reconstructs—from a methodology perspective—how such an evaluation should be built, what conclusions it can yield, and the key considerations for engineering it in practice.
2. The Target: The TCS Capability Spectrum
TCS is not a single discipline but a collection spanning multiple subfields. A well-designed evaluation set typically covers the following capability dimensions:
- Algorithms and data structures: complexity analysis, correctness and termination proofs;
- Complexity theory: reductions, hierarchy relationships, decidability boundaries;
- Combinatorics and graph theory: extremal constructions, matching and coloring, network flows;
- Number theory and algebra fundamentals: modular arithmetic, basic properties of groups, rings, and fields;
- Cryptography fundamentals: reduction-based security arguments, protocol correctness;
- Logic and automata: formal languages, computability, fixed points, and more.
A common trait of these problems is that the correct answer usually requires a proof rather than a computation. The answer space is not a single value but a logically self-consistent line of argument. This is fundamentally different from traditional applied math word problems (plugging values into formulas), and it therefore better exposes a model’s weaknesses in long-chain reasoning and constructive thinking.
3. Five Key Steps to Building a High-Quality Evaluation Set
3.1 Problem Source and Originality
High-quality evaluation problems must be as “new” as possible, avoiding problems already widely circulated in training corpora. Common practices include: original problems written by domain experts, problems distilled from recent academic discussions, or structured rewrites of classic problems that stay superficially similar while changing the core reasoning path.
3.2 Difficulty Stratification
The evaluation set should span the full difficulty spectrum, from “slightly harder than an ordinary model” to “no current model can reliably solve.” Only by retaining a certain number of high-discrimination hard problems does the evaluation maintain its lasting discriminative power and avoid quickly becoming obsolete as models improve.
3.3 Guarding Against Data Contamination
This is the lifeline of evaluation credibility. You need to detect whether evaluation problems overlap with training data. One engineering approach is dual detection based on semantic fingerprints and n-gram matching:
def detect_contamination(benchmark_item, corpus_index, n=8):"""Detect data contamination risk using dual n-gram overlapand semantic fingerprinting."""grams = to_ngrams(benchmark_item, n=n)overlap = 0for g in grams:if corpus_index.contains(g): # query the training corpus indexoverlap += 1fingerprint_hit = semantic_similarity(benchmark_item, corpus_index) > 0.92return overlap / len(grams), fingerprint_hit
If a problem has too high an overlap rate or triggers a semantic fingerprint hit, it should be down-weighted or removed during scoring, to avoid overestimating capability caused by “memorizing the answer.”
3.4 Answer Verifiability
TCS problems should be objectively gradable as far as possible. Viable approaches include: requiring the model to output intermediate steps that a program can verify, using binary judgments (proof holds / does not hold), or introducing a dual-track mechanism that combines an independent review model with human review.
3.5 Scoring and Statistical Measures
A single evaluation run has high variance, so you should use multiple samplings, report confidence intervals, and distinguish between “fully correct” and “correct in approach but flawed.” This avoids a single accuracy figure masking the model’s true capability distribution.
4. The AI Math Research Boundaries the Evaluation Reveals
Synthesizing observations from this kind of frontier evaluation, a few clear boundaries emerge:
- Strong at routine problem-solving, weak at constructive proofs: Models can skillfully handle problems with standard routines, but struggle noticeably when they must “construct from scratch” a counterexample or an existence proof.
- Long-chain reasoning decays: As the number of reasoning steps grows, errors accumulate, and models often suffer a logic break after dozens of steps—yet still confidently deliver a conclusion.
- Cannot distinguish correct from seemingly correct: Models lack effective self-verification and metacognition, and readily assign high confidence to flawed arguments.
- Open research problems remain a forbidden zone: Problems that sit at the true research frontier and have no standard answer are essentially beyond the effective reach of current models.
In other words, today’s LLMs are more like “skilled problem-solvers” than “explorers with independent research capability.” This boundary is precisely where the evaluation system delivers its greatest value.
5. Engineering Practice for Evaluation Infrastructure
A sustainable evaluation system is essentially a combination of “high-concurrency inference + large-scale data processing.” Using the general capabilities of platforms such as Baidu AI Cloud, you can quickly build one from standard product categories:
- Question bank and corpus storage: use object storage to hold evaluation problems, reference answers, and training corpus indexes, supporting reliable archiving of massive numbers of small files;
- Task scheduling and concurrent inference: elastically scale inference services through a container platform, combine with message queues to smooth out traffic peaks and troughs, and run hundreds to thousands of problems in parallel;
- Result archiving and observability: use a logging service to centrally collect the input and output of each evaluation run, and track scoring fluctuations and anomalies through a monitoring and alerting system to ensure the evaluation is reproducible;
- Elastic compute: request elastic compute dynamically per evaluation wave, releasing it when idle and scaling up when busy, balancing cost and throughput.
This combination of “storage + scheduling + observability + elastic compute” lets evaluation evolve from a one-off script into a sustainable, platform-level capability that can be iterated on.
6. Takeaways for Developers
First, designing an evaluation is itself an engineering effort that requires deep involvement from domain experts—it cannot be built by simply piling up problems with automated scripts. Second, contamination resistance and answer verifiability determine whether an evaluation stays trustworthy over the long term, and should be treated as first-class citizens in the design. Third, the value of an evaluation lies not in ranking models, but in precisely characterizing where the capability boundary is and why it exists, so as to guide subsequent model improvement and inference-optimization direction.
For developers who want to adopt LLMs in their own products, building a small, domain-specific, reproducible, contamination-resistant evaluation set is the most pragmatic starting point for safeguarding application quality. The methodology offered by TCS evaluation can be transferred in full to scenarios such as finance, law, and healthcare that place even higher demands on reasoning rigor.
