More Proof Machinery, More Compute: What TCSAlgBench Says About Research Agents

TL;DR for operators

When a research agent fails on a difficult proof, the next question is how much more inference to spend: another independent attempt, verifier feedback, decomposition into intermediate claims, search across alternative proof branches, or a larger revisable plan. TCSAlgBench makes that allocation problem measurable on research-level theoretical computer science.

In a controlled GPT-5.5 xhigh comparison, trying each challenge independently several times increased the share solved by at least one run from 21.1% with prover-verifier discussion alone to 23.4% with root-level decomposition, 24.1% when decomposition was combined with tree search, and 25.4% with adaptive planning. But the most elaborate workflow did not dominate every measure: tree search produced higher first-run acceptance than agentic planning, while sampled average input-token use rose from 12.1 million for discussion alone to 60.4 million for agentic planning.

For AI research-assistant teams, repeated sampling, verifier feedback, decomposition, search, and planning are therefore separate resource-allocation choices rather than steps on a simple capability ladder. The evidence supports comparison under this benchmark protocol, not a claim that the systems can conduct research reliably on their own: most accepted proofs are judged by automated verifiers, most challenge statements did not receive the reported manual review, and the token-cost estimates come from a 10-challenge subsample.

The deployment question is how much inference to spend on one hard problem

Suppose a research assistant fails to prove a difficult result on its first attempt. A system designer has several options: sample another independent proof, ask a verifier to critique the first one, split the theorem into intermediate claims, explore alternative proof branches, or maintain a larger plan that can be revised when one intermediate claim fails.

Each option consumes additional inference. The question is not merely whether more computation helps. It is whether the extra computation produces enough additional successful problems to justify its cost and latency.

TCSAlgBench, introduced by Yang and colleagues, makes that trade-off measurable on recent research-level theoretical computer science.¹ Its 398 challenges span algorithmic fairness, differential privacy, learning theory, optimization, sampling, and other TCS topics.

The benchmark also distinguishes a single successful attempt from breadth across repeated attempts. If the same challenge is tried independently five times, five-run coverage asks whether at least one of those runs produces a verifier-accepted proof. That is different from asking how often the first run succeeds.

This distinction becomes central once proof agents start spending substantial compute searching for alternative solution paths.

The benchmark removes source-paper shortcuts before testing proof discovery

Turning a published theorem into a benchmark problem creates an immediate validity problem: enough context must remain for the theorem to be understandable, but leaving intermediate lemmas or construction details in place can reveal much of the solution.

The TCSAlgBench construction pipeline starts from TeX sources and proof-dependency graphs. It assembles definitions, assumptions, notation, relevant prior-work context, information-access rules, and quantitative guarantees, then applies repair passes designed to remove intermediate source-paper results. When discovering an algorithm is itself part of the task, named algorithms can be rewritten as existence claims rather than supplied directly.

The resulting prover receives the challenge plus a fixed offline library of cited prior work. It does not receive the target source paper, target proof, or source construction graph.

This matters for organizations evaluating research assistants because benchmark freshness alone is insufficient. A recently published problem can still be an easy test if its statement carries too much of the original solution structure. TCSAlgBench’s more reusable contribution may therefore be the paper-to-challenge pipeline: it treats leakage control as part of benchmark construction rather than as a post-hoc contamination check.

More structure raises coverage, but not on one monotonic curve

The paper compares four proof-agent workflows using the same GPT-5.5 xhigh backbone, problem input, tool access, model-call opportunities, and per-call generation limits.

A long proof can first be divided into dependent intermediate claims. Root-only decomposition performs this split once. A more elaborate workflow then treats alternative intermediate proof goals as branches to explore; the paper uses Monte Carlo tree search, or MCTS, to decide which open goals deserve further attempts. Agentic planning goes further by maintaining a revisable directed dependency graph of intermediate claims rather than committing to a fixed decomposition.

The results are:

Agentic planning therefore covers 17 more of the 398 challenges across five runs than discussion without decomposition: 101 versus 84. But it processes roughly five times as many sampled input tokens.

It also does not dominate every metric. MCTS has the highest seed-1 acceptance, at 19.3%, compared with 18.1% for agentic planning. The planning workflow’s advantage appears when independent runs are combined and the objective becomes covering more distinct challenges.

The token figures require another boundary: they are averages from 10 randomly selected challenges across five seeds, not measurements over the entire 398-challenge benchmark. And the experiment matches opportunities to make model calls, not realized token consumption. Equal call budgets can therefore hide large differences in infrastructure load.

For a research platform, this suggests at least two distinct operating regimes. A latency-sensitive interactive assistant may care heavily about first-run success. An offline research pipeline may accept repeated attempts and larger search structures to increase the set of problems that eventually receive an accepted proof.

Reasoning effort is another configuration variable, not a guaranteed upgrade

The non-monotonicity is not limited to agent architecture.

Under direct inference, Fable 5 high covers 58 challenges across ten runs, while its xhigh setting covers 45. GPT-5.6 Sol xhigh and max also solve overlapping but non-identical sets of challenges: across five-run discussion coverage, 10 challenges are solved only by xhigh and 16 only by max.

That pattern argues against reducing system evaluation to a single “reasoning effort” dial. More inference effort can change the trajectory a model follows rather than merely improving the same trajectory.

Repeated sampling has similar implications. GPT-5.6 Sol max reaches 75 accepted challenges on the first discussion run and 94 when successes from five independent runs are combined. The additional runs are finding complementary solutions, not simply reproducing the first run more reliably.

For deployment testing, aggregate score should therefore be accompanied by overlap analysis: which tasks are newly solved, which disappear under another configuration, and how much compute is required to obtain the union.

One benchmark score hides several operational properties

TCSAlgBench reports more than overall coverage, and those diagnostics answer different engineering questions.

Topic performance, for example, is highly uneven. GPT-5.6 Sol max covers 94 of 398 challenges after five discussion runs, or 23.6%, but only 2 of 33 differential-privacy challenges. A team working primarily on privacy research would therefore learn something quite different from the aggregate number.

Verifier sensitivity is a separate issue. The primary evaluation uses three independently sampled GPT-5.5 high-effort voters and requires a majority PASS. When the same generated proofs are rescored with an Opus 4.8 high-effort verifier, absolute counts move for several configurations, although the reported five-run ordering across the eight shared configurations remains unchanged.

That sensitivity analysis supports the comparative ordering reported here. It does not make automated judging equivalent to formal proof checking.

The paper also experiments with formalization, retaining 221 compiler-valid Lean candidate statements after automated semantic screening. The baseline agents produce zero accepted sorry-free Lean proofs on those candidates. The 221 statements are provisional resources, however, not expert-validated formalizations of the original theorems.

The results support system comparison, not a claim of autonomous research

Several boundaries materially affect how these numbers can be used.

First, proof correctness is primarily an automated label. The reported human audit covers 10 accepted GPT-5.5 xhigh discussion proofs from the manually reviewed statement subset; all 10 were judged correct, but that sample is too small to convert verifier acceptance into an estimate of benchmark-wide proof correctness.

Second, only 61 of the 398 challenge statements received the reported manual review for fidelity and self-containment. The remaining headline-evaluation problems came through the construction pipeline without that same stated review.

Third, publication dates do not solve contamination measurement. The paper finds no consistent advantage for challenges dated before assumed model-family knowledge cutoffs, but explicitly notes that these splits cannot identify training-set membership. Pre- and post-cutoff groups may also differ in topic and difficulty.

The evidence is consequently strongest for comparing systems under the benchmark’s common protocol. It is weaker as evidence about absolute proof correctness or general autonomous research capability.

Research-agent design becomes a budget-allocation problem

For teams building research-oriented agents, TCSAlgBench changes the unit of comparison.

The relevant question is no longer only which backbone model produces the highest benchmark number. A system also chooses how many independent attempts to make, whether to introduce verifier feedback, whether to decompose a theorem, whether to search alternative proof structures, and whether to maintain a globally revisable plan.

Those choices produce different success sets and different compute profiles.

The practical evaluation target should therefore resemble a frontier rather than a single leaderboard score: coverage against latency, tokens, verifier dependence, and domain-specific performance. The most elaborate workflow may be appropriate when one additional solved research problem justifies substantial compute. In a high-volume assistant serving many queries, a smaller coverage gain may not justify a fivefold increase in sampled input-token use.

TCSAlgBench does not resolve that business decision. It makes the trade-off visible enough for teams to measure it.

Cognaptus: Automate the Present, Incubate the Future.