LLM Research Capability Benchmarks: Can Models Solve Problems or Actually Do Research?
LLMs keep setting records on math competitions, coding problems, and standardized tests, which makes it easy to assume that research capability has already been cracked. This article explains why that assumption does not hold up, and why theoretical computer science (TCS) is a better evaluation target. It walks through the shift in paradigm from answer comparison to conclusion verification and process diagnosis, separates decidability from verifiability, describes a benchmark design of roughly 100 problems organized around four research activities (theorem proving, algorithm construction, counterexample construction, and reduction analysis), and reports illustrative observations showing where models stall when facing open conjectures. Readers will also get practical guidance on judging whether a benchmark measures real research ability, plus a reproducible checklist covering problem selection, verifier choice, process logging, contamination control, and the fields a results table should record.
1. Solving Problems Is Not Doing Research: Why the Evaluation Paradigm Has to Change
Large language models keep setting new records on math competitions, coding problems, and standardized tests, which makes it easy to assume that models are already close to doing research. The catch is that most mainstream leaderboards still revolve around “here is the problem, give the answer”: the problem statement is well bounded, the answer can be compared immediately, and grading is cheap and rarely contested. Real research does not work that way. Researchers face problems that often have no canonical statement and no known answer, and whether a problem can be solved, which path gets you there, and how long the argument needs to be are all unclear in advance.
Sudoku is a useful analogy. Filling in a Sudoku grid is genuinely hard, but once it is full, checking it takes seconds. Many math and programming problems share this “quickly checkable answer” property. That makes them well suited to training, competitions, and engineering acceptance tests, but not sufficient on their own to measure the ability to do research. A research capability benchmark needs to ask a different question: not whether a model can produce an answer whose solution is already known, but whether it can produce a new conclusion that can be verified when no answer is available to guide it.
So the core shift in evaluation paradigm is from answer comparison to conclusion verification and process diagnosis. That is why this article focuses on theoretical computer science (TCS).
2. What Is Theoretical Computer Science, and Why Does It Suit Research Capability Evaluation?
Theoretical Computer Science (TCS) studies the mathematical foundations of computation. It asks whether an algorithm can finish within a given time bound, whether a problem has an unbeatable lower bound, what a given computational model can express, whether a class of structures is decidable, and whether an algorithm design meets a strict performance target. An ordinary developer cares about how to build a system and which interfaces to call; a TCS researcher is closer to planning the underlying traffic system of computation: which routes are viable, which are doomed to be inefficient, and which problems have no general solution at all.
Typical TCS research activities fall into four categories:
- Theorem proving: giving rigorous proofs of claims about algorithmic complexity, data structures, communication complexity, cryptographic protocols, and similar topics.
- Algorithm construction: designing algorithms or data structures under resource constraints, together with correctness proofs and complexity analysis.
- Counterexample construction: refuting a conjecture that looks plausible by building an instance that satisfies the premises and provably contradicts the claim.
- Reduction analysis: mapping the difficulty of one problem onto another to establish lower bounds, hardness of approximation, or undecidability.
These activities suit research capability evaluation not only because they resemble real research, but because their outputs can often be expressed formally. An algorithm construction can come with pseudocode, a correctness argument, and complexity analysis; a counterexample can come with a concrete instance and checkable conditions; a reduction can include a proof that the transformation preserves the property in question. Outside TCS, formal mathematics, program verification, complexity proofs, algorithm lower bounds, and counterexample construction can serve as comparable settings.
3. From Decidability to Verifiability: Two Concepts That Must Be Kept Separate
A common mistake when discussing TCS benchmarks is treating decidability as equivalent to machine-checkable conclusions. The two must not be conflated.
Decidability usually refers to whether there exists an algorithm that decides truth or falsity for arbitrary inputs in finitely many steps. Some theoretical fragments are decidable, but many important theories are not, and open conjectures are certainly not settled by running an automated decision procedure.
Verifiability is different. Given a candidate proof, construction, counterexample, or reduction, a checker can verify whether it satisfies the rules. In other words, even if an open conjecture remains unsolved, a proof submitted by a model can still be checked: is each inference step legitimate, does the conclusion actually follow from the premises, does the counterexample satisfy every constraint, does the reduction preserve difficulty in the correct direction.
Formal verification is one important way to achieve verifiability. Formal languages, proof assistants, executable tests, or purpose-built checkers can validate the soundness of a proof or a construction. One point deserves emphasis: what the benchmark uses is machine-checkable proofs, constructions, and counterexamples — not an automatic determination of whether an open conjecture is true or false. Nor should anyone claim that all conclusions in TCS can be decided automatically. The accurate statement is that TCS offers a relatively large number of tasks that can be expressed formally and checked mechanically, which makes it a good approximation of a research capability benchmark.
4. How Do You Build Such a Benchmark? 100 Problems and Four Research Activities
A research capability benchmark has to answer two questions: what to test, and how to score it. A typical design sets around 100 problems and organizes them along the everyday activities of TCS researchers, so that the evaluation covers different capability dimensions rather than a single question type.
| Activity Category | Typical Problem Types | Verification Method | Failure Signals to Watch For |
|---|---|---|---|
| Theorem proving | Prove the amortized complexity of a data structure operation, or prove a lower bound for an algorithm | Proof checker, expert review, formal proof artifact | Missing lemmas, circular reasoning, uncovered edge cases, quietly shifting the conclusion |
| Algorithm construction | Design an algorithm that meets a given time or space target under stated constraints | Unit tests, complexity proof, formal specification, executable verification | Fitting only the sample cases, ignoring the worst case, overstated complexity bounds |
| Counterexample construction | Refute a conjecture by exhibiting an instance that satisfies the premises but violates the conclusion | Small-scale enumeration, formal counterexample, human verification | Counterexample violating the premises, omitted conditions, insufficient enumeration |
| Reduction analysis | Reduce problem A to problem B to establish a hardness relationship | Reduction correctness proof, transformation script, instance comparison | Incomplete reduction, distorted complexity, wrong mapping direction |
The benefit of this categorization is that different question types correspond to different reasoning moves, which keeps a model from scoring by relying on a single memorized pattern. Difficulty should be layered as well: include basic problems that can be checked quickly, plus a small number of open conjecture problems. Basic problems establish the baseline; open problems probe the boundary.
The applicability conditions must be stated plainly: verifiable evaluation requires formal languages, checkers, or executable test environments, and what is being verified is whether the submitted proof, algorithm, counterexample, or reduction is valid — not whether the evaluation system can answer “is this open conjecture true or false” on its own. Without verification tooling, open problems can only serve as observational items; they cannot be handled as simple right-or-wrong questions.
5. What Happened in Front of Open Conjectures: What This Limited Sample Shows
The conclusion first: in this limited, illustrative sample evaluation, no tested model was observed to produce a complete and correct solution to an open conjecture on its own. That judgment needs to be tightly bounded and must not be widened into a blanket denial covering all frontier models or all open research tasks.
Because the source material provides no public benchmark provenance, no complete model list, no version numbers, no time window, and no verification details, this article does not state it as absolute fact but restates it as an illustrative observation. A more defensible template would read: in an evaluation of roughly 100 problems, the subjects were fixed versions of several publicly accessible frontier models, the evaluation ran over a given time window, and the problems covered theorem proving, algorithm construction, counterexample construction, and reduction analysis, with open conjecture problems making up a small share; verification combined automated proof checkers, executable test scripts, and human review. If the result is used in a formal report, the real source, model names, versions, dates, problem counts, and verifier versions should be supplied.
To make the point concrete, the passage can be restated as an illustrative evaluation setup: the tested models are fixed versions of several publicly accessible frontier models (for example, 3 closed-source versions and 2 open-source versions), the time window is one evaluation period, there are 100 problems in total of which 15 are open conjecture problems, and verification combines automated proof checkers, executable test scripts, and human review. If the original material has no public provenance, this must be labeled as an illustrative observation and cannot be cited as a formal experiment.
From the limited observations, three points can be separated out.
First, performance on basic and open problems differs sharply. Models tend to do reasonably well on problems with clear answers and clear patterns, but on open problems that demand long reasoning chains, boundary clarification, and rigorous proof they often stall at partial lemmas, take a wrong direction, or leave a construction unfinished.
Second, failure modes are more informative than scores. A model may produce plausible-looking reasoning while dropping a premise; it may construct an invalid counterexample; it may reverse the direction of a reduction; or it may generate only fragments without ever closing the proof. These errors reveal where the model is weak within the research workflow.
Third, evaluation results do not extrapolate. They depend on sample size, model version, problem difficulty, prompting style, tool access, and verification cost. Failing open problems in one evaluation does not mean a model fails at all open research tasks, nor that its reasoning ability is useless. The more reasonable conclusion is that under this setup, open conjectures exposed the key weakness that separates “solving problems” from “doing research.”
6. How Can You Tell Whether a Benchmark Measures Research Capability?
This is the question evaluators ask most often: how do you know a benchmark is not simply rewarding memorized problems, but actually measuring real research ability? Four aspects help.
First, are the conclusions verifiable. A good benchmark should prioritize tasks that a machine or an expert can re-check, such as proofs, constructions, counterexamples, reductions, and program verification. When an answer depends on subjective taste or vague criteria, results are easily distorted.
Second, are the problems non-trivial. They should not be standard problems that appear frequently in training data, and should not offer an obvious pattern to follow. The evaluation should include variant problems, newly constructed problems, problems that appeared after the training cutoff, or human-designed problems that are hard to absorb through memorization.
Third, does it cover multiple reasoning moves. Testing only theorem proving leans toward formal reasoning; testing only algorithm construction leans toward engineering implementation; testing only counterexample construction leans toward search ability. A research capability benchmark should cover proving, constructing, refuting, and reducing.
Fourth, does it include a small number of open problems. Open problems should not make up too high a share, or the cost becomes excessive and interpretability drops; but they should not be missing entirely. A few open problems help reveal the paths, failure modes, and boundaries of models in realistic research settings.
7. Designing a Reproducible Research Capability Benchmark: A Practical Checklist
Beyond principles, you need a process. The checklist below can be used directly to build or review an evaluation.
1. Problem selection checklist
- Prioritize problems that have no public standard answer, or whose answers are non-trivial.
- Cover all four activity categories: theorem proving, algorithm construction, counterexample construction, and reduction analysis.
- Define three difficulty tiers: basic, advanced, and open.
- Check whether problems might contaminate training data; prefer variant problems, private problems, or newly written ones.
- State the allowed input scope for each problem, for example whether calculators, proof assistants, or retrieval tools may be used.
2. Verifier selection
- For theorem proving, use a formal proof checker or expert review.
- For algorithm construction, use executable tests, complexity proofs, and boundary condition checks.
- For counterexample construction, use enumeration scripts, formal condition checks, and human confirmation.
- For reduction analysis, inspect the transformation function, the proof text, and the instance mapping.
- Make clear that the object of verification is the submission, not the open proposition itself.
3. Process logs
- Record prompts, tool calls, retrieval results, attempt counts, and failure reasons.
- For open problems, retain the full reasoning trace rather than looking only at the final submission.
- Annotate whether and on what grounds the model changed its conclusion along the way.
4. Contamination control
- Freeze model versions, prompt templates, and tool versions.
- Prohibit undeclared online retrieval or external problem banks.
- Deduplicate, rewrite, or replace known public problems with new problems of the same kind.
- Monitor output similarity against existing answers to detect memorization or leakage.
5. Result table fields
| Field | Description |
|---|---|
| Model name | Identity of the tested model |
| Model version | Precise to version or snapshot date |
| Evaluation time | Date window in which the evaluation was run |
| Problem ID and category | The corresponding activity category and difficulty tier |
| Submission | Proof, algorithm, counterexample, reduction, or explanation |
| Verifier version | Version of the automated checker or script |
| Automated verification result | Pass, fail, or partial pass |
| Human review | Whether expert judgment was required, and its conclusion |
| Failure type | Reasoning error, missed boundary, invalid construction, and so on |
| Runtime cost | Time, tokens, or tool call cost |
| Notes | Prompt differences, tool permissions, anomalies |
These fields turn an evaluation from a one-off leaderboard into a reproducible, comparable, auditable engineering process.
8. Conclusion
High scores on math and coding leaderboards make it tempting to conclude that research capability has been solved. Evaluating theoretical computer science offers a more sober perspective: when a problem has no standard answer, the path is unknown, and the conclusion requires rigorous verification, a model’s performance reveals its real boundaries. Between solving problems and doing research, the gap is not only difficulty — it is the evaluation paradigm itself.
At the same time, every benchmark has limits. Sample size, model version, problem difficulty, prompting style, tool access, and verification cost all shape the conclusions. We cannot claim that models are incapable of participating in open research on the strength of one limited evaluation, and we cannot ignore research weaknesses because of high scores on conventional leaderboards. A genuinely reliable assessment holds to verifiability, non-triviality, broad coverage, and a small number of open problems, and it publicly documents model versions, problem sources, and verification methods. Only then can researchers see clearly whether a model currently stands at “solving problems” or at “doing research.”
