TCSExam: Can AI do real math research? A new benchmark checks the proofs by machine

What it's about

Can AI actually do mathematical research, or can it only solve exercises whose answers are already somewhere online? A new paper takes on that question, and it's the first time two prominent names in China's AI scene have worked on one together. The first is Andrew Chi-Chih Yao (Yao Qizhi), a Turing Award winner, member of the Chinese Academy of Sciences and dean of Tsinghua University's Institute for Interdisciplinary Information Sciences. The second is Yang Zhilin, founder of Moonshot AI (Yuezhi Anmian), the company behind the Kimi chatbot.

The result is TCSExam, an exam made of 100 research problems from theoretical computer science (TCS). The researchers tested current AI agents, meaning AI systems that work on their own over many steps, write code and use tools. The paper is on arXiv (arxiv.org/pdf/2611.07962v1). The Chinese tech outlet Leiphone covered it in detail, and this article is based on that report.

The headline: one more edge

Leiphone's report leads with a result that looks tiny at first. On a graph construction, Kimi pushed the previous reference record from 629 edges to 630. In math, a graph is a network of points (vertices) joined by lines (edges). This one has 124 vertices. In these so-called extremal constructions, you look for the largest or smallest object that still satisfies certain strict rules. The report doesn't say exactly which condition the graph has to meet.

Why does one edge matter? According to Leiphone, each extra edge often means rearranging the entire structure across all 124 points. The outlet calls it the first time an AI has beaten a human reference value on this kind of research problem. It also asks the obvious questions itself: is this a real breakthrough, or a lucky hit from brute-force computing? Does the AI understand the math behind it? TCSExam is designed to tell those cases apart.

How TCSExam works

The 100 problems fall into four areas:

Lean 4 is a programming language for mathematical proofs. You write a proof so precisely that a computer program can check every single step. A "solver" is a program that solves a particular class of problems as well as possible.

The core idea relies on a property at the heart of theoretical computer science: finding solutions is hard, but checking them is easy. So every AI has to hand in a "research certificate" that a checker can verify automatically. That's Lean code for proofs, runnable programs for solvers and concrete objects for constructions. The system also checks whether a proof contains forbidden placeholders for unfinished parts or extra assumptions (axioms).

One underrated problem is the translation into machine language. If formalizing a theorem accidentally adds a restriction, such as an upper limit on a graph's size, the AI ends up proving an easier problem. So one agent writes the formal problems, a second agent checks the definitions, quantifiers and parameters, and human experts confirm that the problems matter for research. More than 40 candidate theorems were dropped during test runs because they were solved too easily. For some solver tasks, test cases are mathematically transformed so the AI can't just reuse known answers.

Partial progress isn't a proof

There are three levels of help for proofs. Bare gives only the theorem and the definitions it needs. Ladder adds intermediate steps, known as lemmas. Guided adds a proof idea on top. Long proofs are also broken into intermediate goals called "checkpoints". Each checkpoint is checked while temporarily assuming the others are true. That creates a logical trap: if A relies on B and B relies on A, both pass their individual checks even though the overall proof is circular. That's why the main theorem has to pass at the end with no unproven assumptions.

An example shows why this matters. In one attempt, Kimi K3 cleared 7 checkpoints, or 87.5 percent coverage, but didn't manage the final step to the main theorem. The system didn't count it as a proof.

The numbers show that success rates climb sharply with help. According to the researchers, the real difficulty is finding the key lemmas yourself and organizing scattered reasoning into a complete proof. If an AI finds a completely different route that ignores the provided scaffolding, that's accepted too.

The strongest model overall was GPT-6 Astra, which proved 14 of the 20 research theorems. It also took on a logic synthesis task from the IWLS 2023 competition, where the goal is to build circuits with as few logic gates as possible. Astra produced valid circuits for all 100 test cases. 22 beat the public reference circuits, 31 matched them and 47 needed more AND gates.

The 9-dimension proof

The most impressive single result concerns the Alon–Jaeger–Tarsi conjecture. Put simply, it says that for every invertible matrix over a finite field, there's a vector whose entries are all nonzero and which still has no zeros after being multiplied by the matrix. For the five-element field, this had been shown up to 8 dimensions. Astra got to 9.

Trying every case by brute force isn't feasible in 9 dimensions, so Astra took a different route. It assumed a smallest counterexample and used the smaller cases that were already proven to narrow down its properties. Instead of looking at individual matrix entries, it counted how many coordinates are nonzero before and after the transformation, and built two 10×10 tables of nonnegative integers from those counts. It sorted pairs of matrix columns into 7 categories. Since their counts have to add up to 9, only 5005 combinations were left. Together with conditions from the inverse and transposed matrix, this produced a linear system with 204 nonnegative variables and 197 equations.

Astra combined 143 of those equations, using suitable integer factors, into an impossible equation. All 204 coefficients are nonnegative (93 positive, 111 zero), but the right-hand side is negative. Since the variables can't be negative, that's a contradiction, so the counterexample can't exist. The entire proof was independently recompiled as a project with 71 Lean modules and checked for its axioms.

Our take

TCSExam is mainly interesting as a measuring tool. Instead of testing AI on problems with known model answers, it demands results that a machine can verify independently, and it draws a clear line between partial progress and a complete proof. That makes claims like "AI solved a math problem" easier to check than many past announcements.

The limits are clear, though. The 9-dimension proof covers a special case, and the general conjecture is still open. 28 of the 30 open conjectures went unsolved. The two accepted counterexamples (for Ryser and MIRUP) came from finding and adapting results OpenAI had already published. The report doesn't settle whether the extra edge in the graph record comes from deep understanding or clever search. And when Moonshot helps build a benchmark where Kimi features prominently, that's worth keeping in mind, even though GPT-6 Astra does better in the numbers reported.

The Leiphone authors put it well in their conclusion. The remarkable part isn't "630 instead of 629" or "9 instead of 8". It's that AI can now produce new, machine-verifiable results on some research problems. Finding the key lemmas on its own and planning long proofs independently are still mostly beyond it.