acceptodds
Under review as a conference paper at ICLR 2027

TCSExam: Evaluating frontier LLMs on the full range of TCS research

22 views

Abstract

Can large language models (LLMs) advance theoretical computer science and resolve its long-standing *open conjectures*? To study progress toward this goal, we introduce TCSExam, a unified framework and benchmark covering the full range of TCS research. It evaluates t*heorem proving*, *solver engineering*, and *constructions* alongside direct attempts to prove or refute open conjectures. TCSExam comprises 100 expert-reviewed tasks, with submissions checked by the Lean kernel or an executable task checker. Our evaluation of six frontier LLMs reveals substantial differences in theorem proving. When no proof outline is supplied, the strongest model produces complete, verified proofs in 70% of attempts, compared with at most 11.7% for any other model. Submitted solvers improve on selected public competition solutions, and constructions surpass selected reference bounds. None of the six models fully proves or refutes any of the 30 open conjectures under a budget of up to 12 hours per attempt. Individual attempts nevertheless yield independently verified mathematical results, including special cases and explicit bounds. With shared task interfaces and reproducible verification, TCSExam provides an extensible foundation for developing and evaluating LLMs for autonomous TCS research.

Primary area:
datasets and benchmarks
Keywords:
large language model, theoretical computer science, benchmark, conjectures, LEAN

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.25 over 4 reviews, above 96% of the others.
Reviewer_jzxNOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3(+1)
Soundness
3(+1)
Read review
Paper summary

This paper introduces TCSExam, a benchmark of 100 TCS research tasks in four tracks (theorem proving, solver engineering, constructions, and open conjectures), where every submission is checked by the Lean kernel or an executable task checker. Across six frontier LLMs, the authors find large differences in theorem proving, while no system resolves an open conjecture, some attempts yield verified special cases.

Critical strengths
  1. Every submission is checked by the Lean kernel or an executable task checker, so each accepted result comes with a formal or computational guarantee. The authors also check statement fidelity, test the checkers on invalid outputs, and audit the rollouts whenever a result exceeds the reference. Hence the evaluation is rigorous and reproducible.

  2. The open conjectures track produces verified mathematical results. GPT-6-Astra proves the Alon–Jaeger–Tarsi conjecture over F₅ for all n ≤ 9. This goes one dimension beyond the most recent reported range, which is a concrete example of an LLM pushing the frontier of a TCS problem with a formally verified result.

Critical weaknesses

None

Questions for authors

Appendix C.3 notes that over 40 theorem problems were retired after being solved in pilot evaluations. Since this selection depends on how the screening system performs, it can affect any comparison that involves that system, as the authors also acknowledge. Could the authors specify which system was used for screening, and report how the six evaluated systems perform on the retired problems?

1 comment
AuthorsOpenReview ↗

Response to Reviewer jzxN

Thank you for recognizing TCSExam's verification methodology, reproducibility, and independently verified mathematical results, and for finding no critical weaknesses. Your question about problem selection helps us clarify how the task set was formed.

Selection model and process. We used Kimi K3 for problem selection, task authoring, and preliminary difficulty screening. Theorem candidates first underwent a single bare-proof trial; candidates that K3 could prove in one attempt were prioritized for removal. Final selection considered difficulty, research significance, and domain representation together. During development, 17 batches of early pilot experiments covered 86 candidates, totaling 365 trial runs with grading; 43 candidates were removed after K3 proved them in bare-proof screening. This process aimed to assemble challenging research tasks, on which the main experiments compare agents' performance.

Task quality was also continually improved through interaction among human developers, K3, and Astra: questions about definitions, assumptions, or formalization arising during solving prompted checks against the original sources, revisions, and alternating retests. Overall Q2 provides the full development process, statistics, and concrete examples.

Six-model comparison on retired problems. We have not conducted a six-model comparison across all retired problems. Given the cost of long-horizon agent evaluation, we prioritized thorough evaluation of the retained problems and comparisons with additional frontier models.

We also added model results and evaluation options that are more accessible to the community. Full now includes Kimi K3.1 Pro and DeepSeek V4.1 Flash 1017, with three attempts per problem each; the 20-problem Lite further includes Opus 5.5, bringing coverage to eight agents on Full and nine on Lite. Lite was selected using the original six agents' results. After adding the later models, the Full/Lite rank correlation across the eight shared agents remains 0.93. These results demonstrate the task set's ability to distinguish new agents and offer the community a lower-cost evaluation option. See Overall: Lite, Index, and Additional Model Evaluations for detailed results.

Reviewer_42y4OpenReview ↗
Rating
4(+2)
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduce a new benchmark for TCS research. The authors proposes three separated but related tasks: theorem proving, solver engineering (including optimization tasks and decision tasks), and constructions.

The authors evaluate GPT-6-Astra, KIMI-K3, GLM-5.3, Qwen-3.8-max, and Grok-4.6.

Critical strengths
  1. This paper first proposes that TCS research tasks can be divided into three main categories.
Critical weaknesses
  1. Too few problems are involved in the benchmark. Only 100 problems are included, which may not be sufficient to comprehensively evaluate the performance of the models. Specifically, theorem proving tasks only contains 20 problems. I do not see any necessity of introducing a new benchmark with such a small number of problems.

  2. Program efficiency seems not considered in the evaluation of solver implementation tasks. I understand that in the task of solver engineering, it is not necessary to develop the most efficient program, but it is still important to consider the efficiency.

Questions for authors
  1. What is the main difference between this paper's theorem proving tasks and other theorem proving benches?
  2. Why TCSExam is proposed as one benchmark instead of four? It seems to me that 4 different kinds of tasks are unrelated in this bench.
5 comments
AuthorsOpenReview ↗

Response to Reviewer 42y4

Thank you for recognizing the paper's clarity, task taxonomy, and reliability. We clarify TCSExam's research value, scale, efficiency evaluation, and four-track design below.

1. Scale and research value (W1)

TCSExam's 100 problems are 100 research tasks supporting extended tool interaction and sustained iteration. The 20 theorem tasks come from recent papers spanning 13 TCS subfields; each Solver task evaluates a program on a collection of instances. We hope task count will be considered alongside research content, task granularity, and evaluation method.

For long-horizon agent evaluation, 100 tasks are comparable to several related benchmarks, and already require substantial resources: one Full round for each of the original six models costs approximately 23k USD in total in estimated API fees. The underlying runtime and token-usage statistics were reported in Appendix D.5 (Table 10) of the original submission; the revised manuscript expands this table in Appendix D.6 (Table 13). See Overall Q3 for benchmark sizes and cost estimates, and Overall: Lite, Index, and Additional Model Evaluations for Lite and added evaluations.

2. How does Solver evaluation account for efficiency? (W2)

Fixed execution budgets already incorporate program efficiency. Submitted solvers run within specified time, CPU, and memory limits. Optimization tasks compare valid solutions and objective values obtained within budget; decision tasks compare correctly solved instances. Algorithmic and implementation efficiency directly affect scores: more effective search, better solutions, or more solved instances within the same time improve the corresponding results.

These limits govern program execution independently of agent development time. This protocol was already described in §3.1 and §4 of the original submission and is retained in §3.1 and §4 of the revised manuscript. The Solver track assesses practical solving under resource constraints, including efficiency.

3. How does the theorem track differ from other proof benchmarks? (Q1)

Compared with Lean benchmarks such as miniF2F and PutnamBench, TCSExam's distinctive focus is TCS research problems. Its tasks draw on recent papers in algorithms, complexity, combinatorics, coding theory, and quantum computing, requiring formal proofs of specific research results.

Among concurrent TCS benchmarks, TCS-BENCH and TCSAlgBench primarily evaluate natural-language proofs through model grading; TCSExam uses fixed Lean goals and formal verification. FormalTCS also includes Lean tasks, with different proof targets and experimental designs. We also compare bare, ladder, and guided on the same proof targets, studying how intermediate lemma statements and proof ideas affect complete-proof success; the main evaluation uses bare. For the shared corners source paper, FormalTCS tests a communication-protocol property; TCSExam asks for a quantitative upper bound on corner-free sets. We welcome these efforts on research-level TCS proofs, which further demonstrate the importance of evaluating substantive research proofs. See Overall Q1 for the full comparison and our overall contributions.

4. Why evaluate four tracks together? (Q2)

The tracks cover important, complementary TCS research activities. Joint evaluation characterizes research capabilities from a discipline-wide perspective. Researchers need to know whether an agent (model + harness) can prove theorems, develop effective algorithms, find valuable constructions, and advance open problems. Evaluating the same agents reveals overall performance and individual strengths, informing tool selection and priorities for improving model capabilities. DeepSeek V4.1 Flash 0910, for example, completed no proofs in 60 attempts but produced a valid construction exceeding a task reference bound, showing capabilities beyond proof success rates. See Overall Q1 for results and analysis.

The activities are also connected: Figure 1 shows that solvers can search for constructions, proofs can establish their properties, and all three support open-conjecture research. We score outcome types separately while evaluating these mutually supporting activities together to reflect the range and connections of TCS research capabilities.

I am happy with the authors' response 1 and 2, which helps me clarify the work's contribution.

For response 3, does it mean it is only a domain specific proof bench focus on TCS?

For response 4, I am still not persuaded by the "so-called" overall evaluation. What is the difference between this bench and finding four benches and adding the score all together?

Another question, in evaluations, is there any agents' behavior such that one task is used in another task? Since the authors claims that these four tasks are actually connected with each other.

Thank you for continuing the discussion. We are glad our explanations of benchmark scale and Solver efficiency were helpful. We address your remaining questions below.

1. The theorem-proving track's focus

Our theorem-proving track indeed focuses on research-level TCS proofs. We turn recent TCS results into executable tasks with fixed definitions, assumptions, and Lean targets, making agents' success on these research results formally checkable. We also compare bare, ladder, and guided on the same proof targets, studying how intermediate lemma statements and proof ideas affect complete-proof success; the main evaluation uses bare.

2. What does unification add beyond combining benchmark scores?

The discipline-wide perspective and task taxonomy are part of our contribution. Starting from research outputs, we organize theorem proving, solver development, mathematical construction, and open conjectures into four complementary activities with distinct success criteria. This perspective guides task selection, development, and assessment. Existing benchmarks contain related components, but pooling their tasks and scores does not automatically provide this systematic coverage or the task definitions and verification criteria that we developed.

We turn this perspective into a common evaluation of the same agents. Under a shared development budget, we analyze track scores, task-level performance, and actual mathematical and algorithmic outputs to study whether relative strengths change across research activities. For example, on the same Lite task set, Opus completes 4/5 theorems versus Astra's 3/5, while Astra scores higher on Solver. The original submission already evaluated all four tracks and reported their scores separately; the Index added during rebuttal is an auxiliary summary for overall comparison.

Implementing this as a unified, long-horizon agentic benchmark also requires substantive development. Formal proofs, reusable programs, mathematical constructions, and conjecture proofs or refutations have different requirements for submission interfaces, tool feedback, and verification. We integrate these tasks through Harbor so agents can continually use tools, test, and improve submissions within their budget, while retaining verification and scoring appropriate to each track.

This provides a practical benefit for the community. Using several independent benchmarks often requires separate adaptations for task formats, environments, agent interfaces, and result processing. TCSExam offers a common task format and evaluation interface through which researchers can integrate new agents and evaluate all four research activities, reducing repeated adaptation and maintenance and facilitating community extensions.

3. Are connections between the activities observed in agent behavior?

Thank you for asking whether these connections appear in actual agent behavior. This question also helps us make the value of joint evaluation concrete: work on a single open problem can involve solver development, mathematical construction, and theorem proving together.

In the Paley graph case study in Appendix F, Astra developed a maximum-clique search program, found an explicit nine-vertex clique in the 229-vertex Paley graph, and formalized this construction in Lean. It then used that witness to prove that exponent 1 cannot satisfy the task's proposed bound: at 229 vertices, this exponent would allow a clique of size at most 8. This verified intermediate conclusion results from solver development, mathematical construction, and theorem proving working together, providing a concrete example of the connections illustrated in Figure 1.

This illustrates the value of examining the four activities within a common research perspective. Although the full conjecture remains unresolved, the attempt produced verified progress through algorithmic search, construction, and proof. Our tracks distinguish final research outputs and success criteria; completing a task in one track can draw on capabilities associated with the others. Studying them together lets us examine both agents' performance on each activity and how these capabilities contribute jointly to work on open problems.

Our current evaluation runs tasks independently. Your question about cross-task reuse also suggests a valuable future direction: linked tasks across tracks around a common research problem. A program developed in a Solver task could be used to find a construction, which could then support a proof or refutation. This would directly evaluate whether reusing research outputs across tasks helps agents advance subsequent work.

Reviewer_tLSzOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces a benchmark, TCSExam, for testing whether large language models can carry out research tasks in theoretical computer science. It includes 100 tasks in four areas 1) theorem proving, 2) solver engineering, 3) mathematical constructions, and 4) open conjectures. The authors evaluate six frontier models and use Lean 4 or executable checkers to verify submitted results. GPT-6-Astra proves 14 of 20 (70%) research theorems in the bare setting, while the other models have much lower success rates. The paper also reports solver improvements, constructions above selected reference bounds, and verified partial results for open conjectures. No model fully solves any of the open conjectures.

Critical strengths
  • The benchmark covers a broad set of tasks that reflect different parts of actual TCS research. Instead of testing only formal theorem proving, it also asks models to write reusable solvers, find explicit mathematical constructions, and work on open conjectures. These tasks require different skills and give a more useful picture of research ability than a single type of question. The authors also select tasks from several areas of TCS and have them reviewed by experts. As a dataset and benchmark submission, I appreciate the authors initiative to work on curating broad coverage of tasks but I have questions about this (see weakness and questions).
  • The authors put substantial effort into making results easy to check and validate. Theorem proofs are checked with Lean 4, while solver and construction tasks use executable tests or certificates. The authors also discuss checks that make sure a formal statement matches its source and that a submitted proof does not rely on unproved assumptions.
  • The benchmark has clear task interfaces and scoring rules that match the outputs being evaluated. Complete theorem proofs and conjecture resolutions receive binary scores, while solvers and constructions receive graded scores. The paper also reports task-level results rather than relying only on one combined number.
Critical weaknesses
  • My main concern is that the new research contribution is not clear beyond putting several task types into one benchmark. Earlier work already studies formal theorem proving, solver performance, or mathematical constructions, and brings these parts together. For example, in Table 1, if we combine all these existing benchmarks (FormalTCS, FrontierCS, and TCSExam), we end up with at least 143 tasks in each category except open conjectures (which can't be solved by any models). But this paper does not clearly show what new scientific questions become answerable because they are under one benchmark/framework?. As we see in the result except GPT-6-Astra in theorem proving, all models' performance are close to each other in other tasks, none of the model solves any open conjectures.
  • Next, in Table 2, the model comparison looks inconsistent and hard to interpret. Are we evaluating the model only or the agent harness itself ?? For instance, the paper uses Codex for GPT-6-Astra, Kimi Code for Kimi-K3, Claude Code for several other models, and Grok Build for Grok-4.6. Also, Kimi-K3 and DeepSeek-Flash have three attempts per task, while the other models have one. Although the authors report per-attempt success, different tools and harnesses may still affect the results. As a result, it is unclear how much of the gap comes from only the model and how much comes from the harness. A controlled comparison is needed to make a strong conclusion.
  • Also the overall result relies heavily on agent-assisted formalization and fidelity review. Expert review is described mainly as assessing research significance. This is something interesting to know. Are there any misformalized Lean statements?? which make tasks trivially easy, unprovable, or different from the source. The authors do not quantify how many statements a human expert checked line-by-line against the source.
Questions for authors
  • (Q1) Would the authors clarify what new insights TCSExam provides compared with combining existing benchmarks such as TCS-BENCH, FormalTCS and FrontierCS?
  • (Q2) Could the authors provide a controlled experiment using the same harness and number of attempts for at least a subset of the models and tasks?
  • (Q3) What fraction of the formal statements (theorems and conjectures) received full line-by-line human expert comparison with the source??
  • (Q4) Is it possible to release an anonymous sample version of the benchmark during review periods? Like 2-3 sample task definitions, verification scripts, and evaluation settings.
1 comment
AuthorsOpenReview ↗

Response to Reviewer tLSz

Thank you for recognizing TCSExam's coverage, verification, interfaces, and scoring.

1. What does joint evaluation reveal? (W1, Q1)

Joint evaluation addresses two scientific questions: Does an agent's theorem-proving performance represent its broader TCS research capabilities? Do agents' relative strengths change across tracks?

DeepSeek V4.1 Flash 0910 completed no proofs in 60 theorem-track attempts, yet produced a valid construction exceeding a task reference. Astra leads Full theorem proving, Solver, and construction. Full Solver scores span 43.7–64.6%, and construction scores 86.2–104.9%. Open-conjecture attempts also yielded Astra's independently verified Alon–Jaeger–Tarsi result over the five-element field through dimension 9, extending the prior dimensional range (original §5.5; revised §5.6). These outcomes reveal broad and track-specific research capabilities. Overall Q1 explains the four-track design and differences from combining existing benchmarks.

2. Evaluation target, harnesses, and attempts (W2, Q2)

We evaluate agents: model + harness combinations, using common harnesses suited to each model. Terminal-Bench also reports model-harness combinations. Compatibility issues between some model APIs and non-native harnesses further constrain using one harness.

To address your request for a common harness and equal attempt counts: GLM, Qwen, and both DeepSeek versions use Claude Code at maximum reasoning effort, with a 12-hour development budget. We select attempt 1 on each Full task for all four models. Scores are percentages.

AgentTheorem proving ↑Solver ↑Constructions ↑Open conjectures ↑
GLM-5.35.049.097.70.0
Qwen3.8 Max (0902)5.049.295.10.0
DeepSeek V4.1 Flash 09100.048.489.80.0
DeepSeek V4.1 Flash 101710.052.190.16.7†

† The accepted refutations adapt published OpenAI results, discussed in Overall: Lite, Index, and Additional Model Evaluations.

DeepSeek 1017 leads in theorem proving and Solver; GLM leads in constructions. Relative strengths vary across tracks. We are willing to extend shared-harness comparisons as resources and compatibility allow.

Where resources allowed, Kimi K3 and DeepSeek received three attempts per task; for other models, we prioritized broader coverage. Main tables average all reported attempts. Added results appear in Overall: Lite, Index, and Additional Model Evaluations.

3. Consistency between formalizations and sources (W3, Q3)

Formalizing research statements requires explicit conventions, quantifiers, assumptions, and boundary conditions. We independently developed joint human-agent checks and iterative revision based on solving feedback. Formal Conjectures §3.4 reports similar checks, underscoring the need for ongoing mathematical review and testing.

All 70 Lean-related tasks underwent collaborative review with expert participation. Humans, K3, and Astra jointly compared source papers, natural-language statements, and Lean definitions and goals. Specific concerns during solving triggered source reinspection, cross-checking, and revision, followed by alternating tests. See Overall Q2 for the process, pilot statistics, and examples.

On the final versions, Astra proved 14 of 20 theorems. We individually reviewed trajectories for all 20 tasks. Successful submissions followed task rules and passed Lean verification, with no goal changes or verification bypasses. We also found no specific concerns raised by Astra in these trajectories about inconsistencies between natural-language statements and Lean goals.

We made sustained efforts to improve quality through cross-checks, solving tests, and revisions. Formalizations may still contain omissions, so open-sourcing will also enable continued community review; we will promptly investigate and correct reported issues. Formal Conjectures likewise improves its tasks through public community collaboration, see its public revision record.

4. Anonymous task materials during review (Q4)

Anonymous Supplementary Material was uploaded with the submission. Download the ZIP through the entry of that name on the paper's OpenReview page to inspect task materials and evaluation implementations, including definitions, verification scripts, and configurations.

After acceptance, we plan to release and maintain the complete benchmark and evaluation infrastructure, supporting reproduction, evaluation of new agents, and community contributions to task expansion and verification methods.

Reviewer_4r5COpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces a novel benchmark for frontier LLMs on theoretical computer science (TCS) problems. The benchmark (TCSExam) consists of 100 overall tasks consisting of theorem proving, solver engineering, construction and verification of mathematical objects, and end-to-end resolution of open conjectures. Tasks are initially selected by experts, and then co-developed for formalisation and standardised execution environments by autonomous agents with a final expert review. The paper then performs an extensive benchmark of six models, demonstrating that GPT Astra significantly outperforms the other considered models on theorem proving, and that no model is able to fully resolve any of the open conjectures.

Critical strengths
  • The benchmark seems well-constructed: it involves expert review for problem selection and final correctness checks, covers a wide breadth of TCS areas, and uses automatic Lean verification and standardised execution protocols for task assessment.
  • The separation into different task types is interesting: besides pure theorem proving, the proposed benchmark also covers solver engineering and construction (and verification) of mathematical objects, as well as resolution of open conjectures.
  • The benchmark of the six models is quite extensive and the experimental protocol seems to be fair. The results are interesting, with GPT Astra significantly outperforming the other models in theorem proving, and interesting results on the effects of guidance. The analysis of open conjectures and the intermediate results is further useful for the field.
Critical weaknesses
  • The related work section compares the proposed benchmark to existing benchmarks, but further comparison on a problem-level would be appreciated. Specifically, do existing benchmarks already cover open research problems? Are any of the problems in the proposed benchmark shared with previous benchmarks? A discussion of the overlap here would be useful.
  • The experimental comparison does not include any current Claude or Gemini models. This would be an important and interesting comparison, since Astra clearly dominates the other models considered in the study, and these two model families are crucial for the claim of evaluating frontier models.
  • Relating to the last point, Astra already solves 70% of theorem proving tasks zero-shot in a single attempt. While this is informative for the comparison to the other considered models, there is a concern that these tasks will soon be saturated by novel models, yielding uninformative high success rates across the board. This is particularly noteworthy given that over 40 theorem-proving tasks were already retired after being solved during pilot evaluations. A discussion of how the benchmark will maintain sufficiently challenging, yet verifiably solvable (i.e. not open conjectures), tasks would be appreciated.
  • Further details on the selection procedure used to exclude tasks would strengthen the paper. This is currently only described briefly, and raises potential concerns about selection bias.
Questions for authors

Which models were used for screening (and discarding) tasks in the selection procedure?

3 comments
AuthorsOpenReview ↗

Response to Reviewer 4r5C

Thank you for recognizing TCSExam's coverage, verifiable results, protocol, and analysis of proof guidance and intermediate research outcomes.

1. Existing benchmarks and task overlap (W1)

Existing benchmarks do include open research problems. Formal Conjectures covers formalized research problems across mathematics; we recognize its contribution in Related Work. TCSExam selects tasks for their TCS research significance and domain representativeness, considering existing coverage. For open conjectures, we also consider clear research starting points and opportunities for verifiable progress within a finite budget. We evaluate them alongside theorem proving, solver development, and mathematical construction.

Comparing the primary sources of our 20 theorem tasks, two tasks share source papers with FormalTCS or TCS-BENCH, with different proof targets. For the corners paper, FormalTCS tests a communication-protocol property; TCSExam asks for a quantitative upper bound on corner-free sets. We also compare bare, ladder, and guided on the same proof targets, studying how intermediate lemma statements and proof ideas affect complete-proof success; the main evaluation uses bare. Other tracks also share problems: both we and FrontierCS use AHC041 tree partitioning, where we retain the official 2-second per-instance budget and FrontierCS uses 10 seconds; both we and Formal Conjectures include Tuza's conjecture. Our contribution comprises concrete tasks organized around TCS research objectives and cross-track capability analyses from joint evaluation. See Overall Q1 for positioning and research value.

2. Claude, Gemini, and added coverage (W2)

We agree that Claude and Gemini matter for frontier-model comparisons. We added Opus 5.5 on Lite and Kimi K3.1 Pro and DeepSeek V4.1 Flash 1017 on Full: Full now covers eight agents (model + harness combinations), and Lite nine.

On the same Lite tasks, Opus solves 4/5 theorems with an Index of 72.3, versus Astra's 3/5 and 67.0. Kimi K3.1 Pro's 38.3% Full theorem success rate further extends the original comparison. We are actively coordinating resources for Gemini Argon, aiming to add results during rebuttal; otherwise, we plan to include them in the final version. See Overall: Lite, Index, and Additional Model Evaluations for experiments, Lite, and evaluation plans; see Overall Q3 for sizes and costs.

3. Discriminative power and updates (W3)

Under our 12-hour agent setting, the theorem track still clearly distinguishes agents. Astra achieves 70.0%, while others have substantial room to improve. Version comparisons also show sensitivity to progress:

AgentFull theorem-proving success (%) ↑
GPT-6 Astra70.0
Kimi K3.1 Pro38.3
Kimi K311.7
DeepSeek V4.1 Flash 10176.7
DeepSeek V4.1 Flash 09100.0

These results show differences across agents and improvements within model families on research-level proofs, providing useful progress signals and supporting TCSExam's usefulness for tracking research capabilities.

We agree that stronger models require continued additions of challenging research theorems. We will release tasks, environment build recipes, and evaluation infrastructure. We will maintain the collection and welcome new tasks, verification tools, and community reviews. Following the Artificial Analysis Intelligence Index's evolving evaluation composition, we are considering versioned expansions using harder research results already proved in the literature.

4. Screening model and selection process (W4 and Question)

We used Kimi K3 for selection, task development, and preliminary difficulty screening. Success in a single bare-proof trial favored removal; final selection also considered difficulty, research significance, and domain representativeness.

The main evaluation began with Astra. Humans, K3, and Astra jointly checked specific concerns from its solving trajectories; confirmed issues prompted revisions or consideration of replacements. This comprises development-stage difficulty screening and task-quality checks triggered by solving feedback. Overall Q2 gives the process, development statistics, and examples of alternating human/two-model revisions and retesting.

Many thanks for the reply. I think this is overall a valuable benchmark and maintain my acceptance recommendation.

Thank you for revisiting our response and for your continued support of TCSExam. Your questions about task overlap and coverage of newer models helped us clarify the benchmark's positioning and strengthen the empirical comparison.

Comments on the paper

5 comments
AuthorsOpenReview ↗

Overall Response from Authors

We thank all reviewers for their careful reading and constructive feedback. We particularly appreciate the recognition from several reviewers of TCSExam's taxonomy and coverage of research tasks, as well as the verifiability of its results. We also thank reviewer jzxN for the positive assessment, with “None” listed under Critical Weaknesses.

TCSExam addresses a central question: what substantive research work in theoretical computer science can agents accomplish, and how much? Starting from research outputs, we systematically organize four types of tasks—theorem proving, solver development, mathematical construction, and open conjectures—and verify submissions through formal proofs or executable checks. This design allows us to examine both different forms of research capability and the mathematical and algorithmic results that agents actually produce. It provides evidence for researchers deciding how to use agents and for model developers identifying differences in capability. The following Overall Q1-Q3 posts address shared questions about the benchmark design, task development, and scale. A separate post presents Lite, the Index, and additional model evaluations; individual replies address each reviewer's specific comments.

We have updated the manuscript and its appendices with the additional results and clarifications discussed below. Major substantive additions and revisions are highlighted in blue.

AuthorsOpenReview ↗

Overall Q1: Unified Benchmark and Research Value

Q1: Why combine four tracks in a single benchmark? What does TCSExam add beyond merging existing benchmarks?

The four tracks reflect a systematic consideration of the types of research outputs in TCS. Solvers can search for mathematical constructions; constructions can provide existence witnesses, counterexamples, or new bounds; and proofs establish algorithmic guarantees and properties of constructions. Each of these activities has research value, and together they support work on open conjectures. We therefore define tracks by their submitted outputs and success criteria, and evaluate the same set of agents across them to examine capabilities across different types of TCS research work.

We are pleased that concurrent work, including FormalTCS, TCS-BENCH, and TCSAlgBench, also addresses research-level TCS proofs, highlighting the importance of this direction.

Proof-task design. TCS-BENCH and TCSAlgBench primarily use model judges to assess natural-language proofs; TCSExam provides fixed Lean targets and uses formal verification. FormalTCS also includes Lean proof tasks and examines theorem statement formulation and autoformalization. We also compare bare, ladder, and guided on the same proof targets, studying how intermediate lemma statements and proof ideas affect complete-proof success; the main evaluation uses bare.

Solver and broader research coverage. FrontierCS's algorithmic track adapts Codeforces, NOIP, and similar contest problems to optimize query counts, operation counts, and related metrics; its research track focuses on engineering optimization for GPUs, databases, and distributed systems. TCSExam uses research competitions such as PACE to evaluate solver development for classical hard problems, and systematically evaluates mathematical constructions and longstanding open conjectures.

Simply merging existing task sets would still leave these TCS research objectives without systematic coverage. TCSExam specifically selects and develops tasks for these objectives, specifying mathematical goals, submitted outputs, and verification criteria. This additional research content constitutes a contribution that a combination of existing benchmarks cannot replace.

Evaluating all four TCSExam tracks together answers the following questions: does an agent's theorem-proving performance represent its broader TCS research capability? Do agents' relative strengths change across tracks? Results from the same set of agents under a common development budget provide direct evidence. For example, DeepSeek V4.1 Flash 0910 completed no proofs in 60 attempts in the theorem-proving track, yet generated a graph with 124 vertices and 630 edges containing no 3- or 4-cycles, exceeding the task reference of 629 edges. An evaluation based solely on proof success rates would miss this valid construction. Evaluating the four tracks together connects different capabilities with their actual outputs, enabling a more comprehensive assessment of the TCS research work agents can undertake.

TCSExam's value thus lies in both the substantive task design within each track and the analysis of research capabilities across tracks for the same set of agents. We implement all four tracks as Harbor tasks, enabling agents to use tools, test, and improve submissions throughout their development budget, with track-specific checkers verifying the outputs. A common task format, execution protocol, and evaluation interface also make it easier for the community to reproduce experiments, integrate different agents, and extend the research tasks.

AuthorsOpenReview ↗

Overall Q2: Task Development, Selection, and Quality

Q2: How were tasks developed and selected? How were the accuracy of their statements and formalizations checked?

Task development follows the process shown in Figure 2, combining expert selection, agent-assisted writing and review, execution checks, and pilot runs, with repeated revisions based on feedback.

During development, we used Kimi K3 for task selection, authoring, and preliminary difficulty screening. Through multiple rounds of interaction, human reviewers and agents jointly checked the correspondence among source publications, natural-language statements, and Lean definitions and targets. They investigated questions using counterexamples, small test cases, and compilation results, and iteratively revised tasks through cross-review. For the theorem-proving track, a single pilot run in the bare proof setting was an important input to difficulty screening: candidates that K3 could prove in one attempt were prioritized for removal. During development, 17 early batches of K3 pilot experiments covered 86 candidates, totaling 365 task-solving and grading runs; development records show that 43 candidates were removed because K3 proved them during this screening. Final selection considered difficulty, research significance, and representativeness across areas.

At the start of the main evaluation, we ran Astra first and used its solving feedback for further task checks. When trajectories raised specific questions about assumptions, definitions, boundary cases, or formalization, human reviewers worked with K3 and Astra to revisit the source publications and task implementations. They assessed whether the concerns were valid, how to revise the tasks, and whether tasks needed to be removed or replaced. After revision, tasks were recompiled, rerun, and regraded. The two models continued testing in alternation, with human reviewers participating in subsequent adjustments based on new feedback.

Positive-body chasing provides a concrete example of this process. Astra identified a boundary-case counterexample during solving. Through interactions involving human reviewers and both models, K3 reconstructed the counterexample and checked it against the paper, Astra drafted a fix, and K3 checked the revision and applied it consistently across the three prompting settings. The two models then resumed alternating rounds of testing and revision. After revision, a group of four theorem-proving tasks that included this task underwent three K3 solving runs under each of the three prompting conditions, totaling 36 runs, and was tested again by Astra.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.