Kimi Breaks Graph Theory Record in Yao Qizhi & Yang Zhilin's New TCSExam Benchmark

TCSExam: A New Benchmark for Theoretical Computer Science

On November 5, a paper co-authored by Turing Award winner Yao Qizhi and Moonshot AI founder Yang Zhilin was posted on arXiv. The research team introduced TCSExam , a benchmark of 100 problems drawn from theoretical computer science papers (2023–2026), public competitions, and instance libraries. The benchmark evaluates whether large language models can prove theorems, write reusable solver programs, or produce mathematical constructions that surpass existing results.

Benchmark Construction Process

The team used an agent-assisted pipeline: one agent helped write problem statements, submission interfaces, and scoring programs; a second agent cross-checked against original publications to ensure fidelity and verifier correctness. Issues found during trial runs were sent back for revision, followed by final review by domain experts.

Four Problem Categories

20 Theorem Proving tasks – submit a Lean 4 proof. Three prompt tiers: (1) theorem, definitions, assumptions only; (2) plus intermediate lemma statements; (3) plus proof sketches.

30 Solver tasks – submit a reusable program. Models may develop on public instances; final programs run on hidden instances. Example: logic synthesis where the checker verifies circuit correctness and counts AND gates.

20 Mathematical Construction tasks – submit a concrete object (e.g., a graph, a quantum error correction code) and verification material. Objects must satisfy constraints; scores are 100% for meeting the reference value, higher for exceeding it.

30 Open Conjecture tasks – submit a full proof or disproof in Lean, with separate slots for proving the conjecture and its negation. Counterexamples must be proven to refute the original claim.

Key Results

Theorem Proving

In the full-version test (one attempt per problem):

GPT-6 Astra solved 14 out of 20 (70%).

Kimi K3.1 Pro attempted each problem three times, achieving 23 successes across 9 distinct theorems (38.3% per-attempt). Notably, Kimi solved a PCP-related theorem in all three attempts while Astra failed its single attempt.

All other six systems scored ≤11.7%.

Mathematical Constructions

Two models produced constructions that beat published references:

Kimi K3 constructed a graph on 124 vertices with 630 edges that contains no triangles or quadrilaterals, surpassing the previous best of 629 edges. The construction passed independent verification.

Kimi K3 also submitted a quantum error correction code encoding 7 logical qubits into 25 physical qubits, raising the minimum distance from 5 to 6.

GPT-6 Astra independently achieved the same two construction milestones (630-edge graph and distance-6 quantum code).

Open Conjectures

Only two of the 30 conjecture problems received fully verified submissions:

Kimi K3.1 Pro solved the Ryser conjecture once in three attempts, leveraging results OpenAI had recently published.

DeepSeek V4.1 Flash 1017 submitted verified proofs for both the Ryser conjecture and the Modified Integer Rounding conjecture, also by rewriting existing public results into the required Lean format.

The remaining 28 conjectures received no fully verified solutions. However, GPT-6 Astra advanced a special case of the Alon–Jaeger–Tarsi conjecture from dimension 8 to 9 over GF(5); this proof passed Lean verification but earned zero points because the full conjecture remains open. The paper highlights this partial result for future work toward dimension 10.

Overall Scores

Full version: GPT-6 Astra 71.9 , Kimi K3.1 Pro 57.4 , Kimi K3 46.8 .

Lightweight version (only solver and construction tasks): Opus 5.5 72.3 (top).

Availability

TCSExam is open-sourced on GitHub. The paper also releases the exact model–tool pairings (Codex, Kimi Code, Claude Code, Grok Build) and run configurations used in the evaluation.