# TCSExam: Evaluating Frontier LLMs on the Full Range of TCS Research

> TCSExam benchmark shows frontier LLMs can prove research theorems, improve solver references, and exceed construction records, with GPT-6 Astra leading at 71.9 index points.

- **Source:** [arXiv](https://arxiv.org/abs/2611.07962)
- **Published:** 2026-11-14
- **Permalink:** https://picx.dev/p/P7FSRa
- **Whiteboard:** https://picx.dev/p/P7FSRa/image

## Summary

# TCSExam: Evaluating Frontier LLMs on the Full Range of TCS Research

## Summary (Overview)

- **New benchmark framework**: TCSExam is a unified evaluation framework covering the full range of theoretical computer science (TCS) research through four tracks: theorem proving, solver engineering, constructions, and open-conjecture settlement.
- **Two benchmark suites**: TCSExam-Full contains 100 expert-reviewed tasks with outcomes verified by the Lean kernel or executable task checkers; TCSExam-Lite selects 20 tasks (five per track), reducing task attempts by 80% at the same per-attempt budget.
- **Key results**: GPT-6 Astra leads Full (Index: 71.9) with a 70.0% theorem-proving success rate; Opus 5.5 leads Lite (72.3), solving four of five theorem tasks. Full and Lite rankings are strongly aligned (Spearman's ρ = 0.93).
- **Verified research advances**: Agents produced improved solver outputs, exceeded construction references (e.g., a 630-edge girth-5 graph and a [[25,7,6]] quantum code), and proved independently verified special cases of open conjectures, including the Alon–Jaeger–Tarsi conjecture over $\mathbb{F}_5$ for all $n \leq 9$.
- **Extensible infrastructure**: The framework provides task sources, Docker build recipes, and evaluation tools for reproducible use and extension to additional problems.

## Introduction and Theoretical Foundation

The paper addresses a fundamental evaluation challenge: **how to measure whether LLMs can advance theoretical computer science and resolve long-standing open conjectures**. When a conjecture remains unresolved, the final outcome alone reveals little about which research tasks an LLM can perform or where its limitations lie.

The authors identify **three forms of research output** that provide concrete ways to examine LLM capabilities:

1. **Theorem proving**: Complete arguments for research-level mathematical statements
2. **Solver engineering**: Reusable programs tested across problem instances
3. **Constructions**: Explicit mathematical objects with verified properties that establish or improve bounds

These outputs have independent research value and can interact: solvers search for candidate objects, proofs establish their properties, and constructions can supply witnesses or counterexamples.

**Existing benchmarks** address only selected aspects of TCS research (Table 1):

| Benchmark / track | # Tasks | Theorem proving | Solver engineering | Constructions | Open conjectures |
|---|---|---|---|---|---|
| TCS-BENCH | 300 | ✓ | ✕ | ✕ | ✕ |
| FormalTCS | 143 | ✓ | ✕ | ✕ | ✕ |
| FrontierCS | 240 | ✕ | ✓ | ✓ | ✕ |
| FrontierCS 2 | 48 | ✕ | ○ | ✕ | ✕ |
| EdgeBench-Formal | 13 | ✓ | ✕ | ✕ | ○ |
| EdgeBench-Optimization | 19 | ✕ | ✓ | ○ | ✕ |
| **TCSExam** | **100** | **✓** | **✓** | **✓** | **✓** |

✓ evaluated; ✗ outside scope; ◦ related tasks with a different scope.

TCSExam uniquely brings all four forms of TCS research output into one extensible framework with distinct success criteria and common procedures for task development, verification, and version control.

## Methodology

### Task Design and Four Tracks

**Theorem proving (20 tasks)**: Models submit Lean 4 proofs for research theorems. Three settings vary the supplied context:
- **Bare**: main statement, fixed definitions, mathematical assumptions
- **Ladder**: additionally provides intermediate lemma statements
- **Guided**: further supplies proof ideas

**Solver engineering (30 tasks)**: Models receive a problem specification, naive baseline, and public instances, then submit a reusable solver program judged on hidden instances.

**Constructions (20 tasks)**: Models submit explicit mathematical objects (codes, geometric configurations, graph colorings) with certificates, scored against documented records.

**Open conjectures (30 tasks)**: Models receive formalized conjectures (e.g., log-rank, Ryser) and must prove either the statement or its negation in Lean.

### Scoring

**Theorem proving**: Complete proof scores 100.0%; incomplete scores 0.0%. Ladder/guided tasks receive partial credit for checkpoints passed.

**Solver engineering**: Optimization tasks measure the fraction of the gap between baseline $B$ and reference $K$ recovered by the solver. A **Kimi K3-relative score** standardizes raw outcomes against repeated Kimi K3 runs using a Gaussian cumulative-distribution transform.

**Constructions**: Scores measure attainment relative to a trivial construction and documented record; matching the record scores 100.0%, surpassing it can exceed 100.0%.

**Open conjectures**: Verified proof of either direction scores 100.0%; all else scores 0.0% on the resolution criterion.

**TCSExam Index** combines all four tracks:

$$
I = 30P + 30S + 30C + 10O \tag{1}
$$

where $P$, $S$, $C$, and $O$ are mean theorem, Solver, construction, and open-conjecture scores on their original scales.

### Task Curation and Validation

Tasks were selected for research significance, coverage across TCS areas, and verifiable outcomes. An authoring agent prepares statements and checkers; a review agent verifies correspondence to research sources. Over 40 theorem problems were retired after being solved in pilot evaluations. Every submission is checked by the Lean kernel or executable task checker.

### Experimental Setup

- **Agents evaluated**: GPT-6 Astra, Kimi K3, Kimi K3.1 Pro, GLM-5.3, Qwen3.8 Max (0902), Grok 4.6, DeepSeek V4.1 Flash 0910, DeepSeek V4.1 Flash 1017 (all on Full and Lite), plus Opus 5.5 (Lite only)
- **Resources**: 12-hour wall-clock development budget per attempt; Kimi K3, Kimi K3.1 Pro, and both DeepSeek versions contribute three attempts per task; others contribute one
- **Protocols**: Full uses an external online self-test service; Lite runs self-tests in the development environment

## Empirical Validation / Results

### Overall Performance (TCSExam-Full)

| Agent | Theorem Success (%)↑ | Solver Relative (%)↑ | Constructions Task score (%)↑ | Open Conjectures Resolved (%)↑ | Index Points ↑ |
|---|---|---|---|---|---|
| **GPT-6 Astra** | **70.0** | **64.7** | **104.9** | 0.0 | **71.9** |
| Kimi K3.1 Pro | 38.3 | 54.1 | 98.6 | 1.1 | 57.4 |
| Kimi K3 | 11.7 | 48.7 | 95.5 | 0.0 | 46.8 |
| DeepSeek V4.1 Flash 1017 | 6.7 | 53.1 | 91.8 | 5.6 | 46.0 |
| GLM-5.3 | 5.0 | 49.1 | 97.7 | 0.0 | 45.5 |
| Qwen3.8 Max (0902) | 5.0 | 49.2 | 95.1 | 0.0 | 44.8 |
| Grok 4.6 | 5.0 | 43.8 | 86.2 | 0.0 | 40.5 |
| DeepSeek V4.1 Flash 0910 | 0.0 | 48.3 | 86.6 | 0.0 | 40.4 |

**Key findings**:
- GPT-6 Astra completes 14 of 20 theorems (70.0%) without supplied lemmas; four theorems remain unproved by all agents
- Astra matches construction references on 17 tasks and exceeds them on three
- DeepSeek V4.1 Flash 0910 produces a verified construction exceeding a task reference despite completing zero theorem-proving attempts

### Lite Results and Consistency with Full

| Agent | Theorem Success (%)↑ | Solver Relative (%)↑ | Constructions Task score (%)↑ | Open Conjectures Resolved (%)↑ | Index Points ↑ |
|---|---|---|---|---|---|
| **Opus 5.5** | **80.0** | 60.5 | 100.4 | 0.0 | **72.3** |
| GPT-6 Astra | 60.0 | **63.0** | 100.4 | 0.0 | 67.0 |
| Kimi K3.1 Pro | 40.0 | 50.0 | 88.3 | 0.0 | 53.5 |
| Kimi K3 | 33.3 | 48.9 | 79.8 | 0.0 | 48.6 |
| GLM-5.3 | 20.0 | 46.1 | 90.7 | 0.0 | 47.0 |
| Qwen3.8 Max (0902) | 20.0 | 51.0 | 80.3 | 0.0 | 45.4 |
| DeepSeek V4.1 Flash 1017 | 6.7 | 54.3 | 80.2 | 0.0 | 42.4 |
| Grok 4.6 | 20.0 | 41.0 | 79.3 | 0.0 | 42.1 |
| DeepSeek V4.1 Flash 0910 | 0.0 | 50.4 | 79.7 | 0.0 | 39.0 |

Full and Lite rankings show **Spearman's ρ = 0.93** across the eight shared agents, with 26 of 28 agent pairs in the same order. The two reversed pairs involve DeepSeek V4.1 Flash 1017.

### Verified Construction Improvements

- **Erdős girth-5 extremal graph**: Kimi K3 constructs a 124-vertex, 630-edge graph without 3- or 4-cycles, exceeding the 629-edge reference
- **Quantum stabilizer code**: Kimi K3 constructs a binary [[25, 7, 6]] code, improving minimum distance from 5 to 6
- **Coding theory bound**: Astra proves $A(22, 10) \leq 82$, improving the published upper bound of 84

### Proof Guidance Effects

Supplying intermediate lemmas and proof ideas increases solved theorems:
- Kimi K3: 3 (bare), 4 (ladder), 7 (guided) theorems solved at least once
- DeepSeek V4.1 Flash 0910: 0 (bare), 2 (ladder), 6 (guided) theorems solved

### Open Conjecture Results

- Kimi K3.1 Pro and DeepSeek V4.1 Flash 1017 retrieved and adapted OpenAI's published counterexamples for Ryser and the modified integer round-up conjecture (MIRUP)
- GPT-6 Astra proved the **Alon–Jaeger–Tarsi conjecture over $\mathbb{F}_5$ for every $n \leq 9$**: every invertible $n \times n$ matrix $A$ admits a vector $x$ such that $x$ and $Ax$ have no zero coordinates. The $n = 9$ case extends prior dimensional ranges ($n \leq 7$ from Yu 1999; $n \leq 8$ from a recent preprint)
- Four further verified cases concern a six-variable Fourier entropy–influence bound, an exact high-rank Hilbert-matrix rigidity formula, an influence bound for quadratic polynomials, and finite-instance online-matching bounds

## Theoretical and Practical Implications

**For TCS research**:
- TCSExam demonstrates that frontier LLMs can complete research-level formal proofs, produce reusable solvers that improve on existing references, and construct mathematical objects exceeding documented records
- The framework provides a structured way to measure progress toward resolving open conjectures, capturing intermediate results (special cases, bounds) that have independent mathematical value
- The verified Alon–Jaeger–Tarsi result for $n \leq 9$ over $\mathbb{F}_5$ exemplifies how LLM attempts at open problems can yield publishable mathematical contributions

**For model development**:
- The four-track evaluation reveals complementary strengths: an agent may excel at constructions while failing at theorem proving (DeepSeek V4.1 Flash 0910), highlighting the need for diverse capability development
- Proof-guidance results show that supplying intermediate lemmas and proof ideas meaningfully improves success rates, informing how to design human-AI collaboration interfaces
- The strong Full–Lite rank correlation (ρ = 0.93) validates Lite as a cost-effective evaluation protocol, reducing task attempts by 80%

**For benchmark design**:
- The combination of expert review with Lean-kernel or executable verification provides both research significance and reproducible correctness
- The extensible framework (shared task interfaces, Docker recipes, version control) supports community contribution of new problems

## Conclusion

TCSExam provides a unified, extensible framework for evaluating agents across the full range of TCS research, connecting theorem proving, solver engineering, and explicit constructions with open-conjecture settlement. The evaluations across nine agents reveal substantial differences in research capabilities, with GPT-6 Astra leading Full (71.9) and Opus 5.5 leading Lite (72.3).

The results demonstrate complementary strengths across agents in proof completion, solver performance, and construction quality. Submitted programs and mathematical objects improve selected task references, and open-conjecture attempts yield independently verified special cases and bounds. The accompanying task sources, Docker build recipes, and evaluation tools support reproducible use and extension.

**Future directions**:
- Evaluating agents without Internet access on conjectures still open at the time of testing
- Adding new problems through the shared task interfaces and verification protocols
- Studying how to leverage the demonstrated capabilities (e.g., proof guidance, solver-construction interactions) for deeper progress on open conjectures

The authors note that AI coding assistants were used in task authoring, formalization, checker implementation, and iterative review, with evaluated model outputs identified as experimental submissions and checked under the relevant task protocol.

---

_Markdown view of https://picx.dev/p/P7FSRa, served by PicX — AI-generated visual whiteboard summaries of research papers._