LLMs Can Solve Problems but Not Do Research: A TCS Evaluation Framework

    Frontier large language models have recently been credited with AI-assisted mathematical results, yet peer review has questioned many of them: key proofs contain gaps and some claims resist reproduction. A public benchmark in theoretical computer science (TCS) offers a more measured view: when facing genuinely open conjectures, none of the tested frontier models cracked them independently. This article uses TCS as a lens to explain why "passing exams" is not the same as "doing research," and how engineering teams can design, implement, and interpret an evaluation that measures a model's research ability. It covers three blind spots in benchmark design, why TCS yields machine-verifiable research problems, how to slice research ability into four question types, a three-layer evaluation framework with a unified runner and automatic grading, and three common misreadings of evaluation scores.

    Introduction: When “AI-Completed” Results Need Verification

    According to public reports, several math results completed with AI assistance have recently entered public discussion. The number of results looks impressive, but subsequent peer review has questioned many of them: some key proofs contain gaps, and some claims are hard to reproduce. This shows that the barrier to AI participating in mathematical research is falling, while verification mechanisms must keep pace.

    At the same time, a public benchmark targeting theoretical computer science delivered a more restrained conclusion: when facing genuinely unresolved open conjectures, none of the frontier large models tested were able to crack them independently. Putting these two signals together reveals a pattern: large models can assist research, but “independently solving open problems” remains a strength of human researchers.

    For engineering teams, the real question is not whether the model can generate answers, but how we judge that the model is “getting stronger.” New leaderboards appear frequently, and rising scores may mean a model is better at taking tests, not necessarily better at thinking. Using theoretical computer science (TCS) as a thread, this article discusses how to design, implement, and interpret an evaluation that tests a model’s research ability.

    One: Solving Problems ≠ Doing Research — Three Blind Spots in Evaluation Design

    1. Memory Contamination: Testing Memory, Not Reasoning

    The problems and answers in public benchmarks have long been widely available on the internet and may have entered the model’s pre-training corpus. After a model “memorizes” a solution path, a rising score does not necessarily reflect improved reasoning. Therefore, publicly available problems should not be the sole basis for measuring research potential. A self-built evaluation should reserve a portion of a private problem pool and continuously generate same-source variants.

    2. Closed-Book Standard Problems: Can’t Test “Creating Something from Nothing”

    Most existing evaluations use multiple-choice, fill-in-the-blank, or short-answer questions with standard answers, scored by exact matching or human-defined rules. This format suits testing existing knowledge but struggles to cover real research. Real research has no ready-made steps; no one knows in advance whether it will succeed, and for some problems even the person posing the question does not know the answer. For an evaluation to approach research ability, it must accommodate open, generative, verifiable, and original tasks.

    3. The Grading Bottleneck: Harder Than Writing the Problems

    Open-ended answers are hard to grade automatically. When a model outputs dozens of pages of “proof,” reviewing it line by line is extremely costly. Even ordinary mathematical proofs often still require judgment by domain experts; only when a proof has been formalized — for example, with formal verification tools such as Lean, Coq, or Isabelle — can a machine possibly check its correctness step by step. Therefore, when designing an evaluation, prefer tasks that are naturally verifiable, reproducible, and automatically gradable.

    Two: Why Choose Theoretical Computer Science — Research-Type Problems That Can Be Graded

    TCS studies “computation” itself. Concepts such as complexity, algorithms, lower bounds, reductions, randomness, and interactive proofs all have precise formal definitions. A problem can be stated rigorously: given a computational model, input size, and resource limits, does there exist an algorithm that meets a performance guarantee; can a given problem be reduced to a known hard problem. Every conclusion either has a rigorous proof or a clear counterexample.

    Most TCS results are machine-verifiable, falling into three main categories:

    • Algorithm problems: after writing an algorithm, its output can be checked against a large number of test cases.
    • Proof problems: formalized proofs can be checked by assistants such as Lean, Coq, and Isabelle to verify the reasoning chain.
    • Counting and combinatorics problems: many are computationally hard, but verifying a given answer takes only polynomial time.

    On this basis, you can adopt a “generate–verify” pipeline:

    1. The problem setter, or another model, generates a large number of candidate problems;
    2. Keep only problems whose correctness can be judged automatically;
    3. Provide each problem with an automatic verifier that is independent of the answering process.

    This turns the grading challenge of a research evaluation into an executable engineering problem.

    Three: Question Design — Slicing Problems into Measures of Research Ability

    A TCS evaluation need not chase volume but should cover different levels of research activity. A workable problem set can contain four types:

    Type Corresponding research activity Automatic grading method
    Knowledge reproduction Reviewing core concepts and classic results Comparing against a reference proof
    Algorithm design Designing an algorithm and proving its correctness Test cases + correctness checks
    Lower-bound proof Proving that any algorithm requires sufficient resources Standard proof comparison or formal verification
    Open problems Cracking unresolved conjectures Human verification or formal verification

    The evaluation should retain a few “zero-score anchors.” If all problems can be solved by mainstream models, the evaluation degrades into an ordinary exam. Open problems both measure the current upper limit of models and leave observable room for improvement for future models.

    Design principles for developers include:

    • Automatically gradable: every problem must have a repeatable verifier.
    • Memory-resistant: problems do not rely on public web sources, and private variants are continuously added.
    • Robust to chance: sample multiple times and report pass rates, to avoid lucky guesses.
    • Discriminative: cover a difficulty range from “most models can solve” to “no one can currently solve.”
    • Reproducible: record the model version, sampling parameters, grading script version, and runtime environment.

    Four: Building a Self-Hosted Evaluation Framework — Directory, Interface, and Automatic Grading

    You can adopt a three-layer structure of “problem directory + unified runner + summary report”:

    1. tcs_eval/
    2. ├── dataset/
    3. │ └── tcs_0001/
    4. │ ├── item.json # item metadata (type, difficulty, expected result)
    5. │ ├── problem.md # problem statement
    6. │ └── verify.py # automatic verifier
    7. ├── answers/ # model answers (tcs_0001.md, etc.)
    8. ├── run_eval.py # evaluation runner
    9. └── reports/ # evaluation reports

    Each verifier follows the same interface: it receives --problem and --answer and prints one line of JSON to standard output. verdict can be pass or fail, and reason explains the basis for the decision. The runner computes the score by comparing verdict with the expected answer for the problem.

    Runner example:

    1. # run_eval.py
    2. import json
    3. import subprocess
    4. import sys
    5. import time
    6. from pathlib import Path
    7. VERIFIER_TIMEOUT = 60
    8. def judge(item_dir: Path, answer_path: Path) -> dict:
    9. cmd = [
    10. sys.executable, str(item_dir / "verify.py"),
    11. "--problem", str(item_dir / "problem.md"),
    12. "--answer", str(answer_path),
    13. ]
    14. try:
    15. proc = subprocess.run(cmd, capture_output=True, text=True, timeout=VERIFIER_TIMEOUT)
    16. except subprocess.TimeoutExpired:
    17. return {"ok": False, "verdict": None, "reason": "verifier_timeout"}
    18. if proc.returncode != 0:
    19. return {"ok": False, "verdict": None, "reason": "verifier_crash"}
    20. try:
    21. result = json.loads(proc.stdout.strip())
    22. except json.JSONDecodeError:
    23. return {"ok": False, "verdict": None, "reason": "invalid_verifier_output"}
    24. expected = json.loads((item_dir / "item.json").read_text(encoding="utf-8"))["expected"]
    25. return {
    26. "ok": result["verdict"] == expected["verdict"],
    27. "verdict": result["verdict"],
    28. "reason": result.get("reason", ""),
    29. }
    30. def summarize(rows: list[dict]) -> dict:
    31. groups = {}
    32. for r in rows:
    33. g = groups.setdefault(r["category"], {"passed": 0, "total": 0, "unverifiable": 0})
    34. if r["verdict"] is None:
    35. g["unverifiable"] += 1
    36. else:
    37. g["total"] += 1
    38. g["passed"] += int(r["ok"])
    39. for g in groups.values():
    40. g["pass_rate"] = round(g["passed"] / g["total"], 3) if g["total"] else None
    41. return groups
    42. def main() -> None:
    43. base = Path(__file__).parent
    44. dataset_dir = base / "dataset"
    45. answers_dir = base / "answers"
    46. report_dir = base / "reports"
    47. report_dir.mkdir(exist_ok=True)
    48. start = time.time()
    49. rows = []
    50. for item_dir in sorted(p for p in dataset_dir.iterdir() if p.is_dir()):
    51. meta = json.loads((item_dir / "item.json").read_text(encoding="utf-8"))
    52. row = {
    53. "id": meta["id"],
    54. "category": meta["category"],
    55. "difficulty": meta.get("difficulty"),
    56. }
    57. answer_path = answers_dir / f"{meta['id']}.md"
    58. if not answer_path.exists():
    59. row.update(ok=False, verdict=None, reason="missing_answer")
    60. else:
    61. row.update(judge(item_dir, answer_path))
    62. rows.append(row)
    63. print(f"[{row['id']}] {'PASS' if row['ok'] else 'FAIL'} ({row['reason']})", flush=True)
    64. report = {
    65. "summary": summarize(rows),
    66. "errors": [
    67. {"id": r["id"], "verdict": r["verdict"], "reason": r["reason"]}
    68. for r in rows
    69. if not r["ok"]
    70. ],
    71. "elapsed_sec": round(time.time() - start, 1),
    72. }
    73. stamp = time.strftime("%Y%m%d_%H%M%S")
    74. (report_dir / f"report_{stamp}.json").write_text(
    75. json.dumps(report, ensure_ascii=False, indent=2), encoding="utf-8"
    76. )
    77. print(json.dumps(report["summary"], ensure_ascii=False, indent=2))
    78. if __name__ == "__main__":
    79. main()

    Verifier Example for an Algorithm-Design Problem

    Take “given that only adjacent elements may be swapped, find the minimum number of swaps needed to sort into ascending order” as an example. The key point is that the minimum number of adjacent swaps equals the number of inversions, a value that is exact and achievable.

    1. # dataset/tcs_0001/verify.py
    2. import argparse
    3. import json
    4. import random
    5. from pathlib import Path
    6. def theoretical_minimum_swaps(nums: list[int]) -> int:
    7. """Return the theoretical minimum number of swaps: the inversion count, exact and achievable."""
    8. return sum(nums[i] > nums[j] for i in range(len(nums)) for j in range(i + 1, len(nums)))
    9. def count_swaps(nums: list[int]) -> int:
    10. """Function under evaluation: replace with the implementation generated by the model under test.
    11. The current implementation is only a runnable baseline, using bubble sort to count swaps.
    12. """
    13. arr = nums.copy()
    14. swaps = 0
    15. for i in range(len(arr)):
    16. for j in range(0, len(arr) - i - 1):
    17. if arr[j] > arr[j + 1]:
    18. arr[j], arr[j + 1] = arr[j + 1], arr[j]
    19. swaps += 1
    20. return swaps
    21. def build_test_cases() -> list[list[int]]:
    22. """Generate random test cases."""
    23. cases = []
    24. for n in (7, 9, 12):
    25. for _ in range(5):
    26. cases.append(random.sample(range(100), n))
    27. return cases
    28. def main() -> None:
    29. parser = argparse.ArgumentParser()
    30. parser.add_argument("--problem", type=Path)
    31. parser.add_argument("--answer", type=Path)
    32. parser.parse_args()
    33. try:
    34. cases = build_test_cases()
    35. passed = 0
    36. for nums in cases:
    37. expected = theoretical_minimum_swaps(nums)
    38. if count_swaps(nums) == expected:
    39. passed += 1
    40. verdict = "pass" if passed == len(cases) else "fail"
    41. reason = f"matched theoretical minimum on {passed}/{len(cases)} cases"
    42. except Exception as exc:
    43. verdict = "fail"
    44. reason = f"execution_error: {exc}"
    45. print(json.dumps({"verdict": verdict, "reason": reason}, ensure_ascii=False))
    46. if __name__ == "__main__":
    47. main()

    This code has three key design points:

    • The problem is verifiable: the verifier only needs to check whether the algorithm’s output reaches the theoretical minimum, without understanding all of the model’s reasoning.
    • The interface is standardized: all verifiers follow the same input/output convention, so adding problems does not require changing the runner.
    • Exceptions count as failure: when the answer code throws an exception, the verifier still outputs valid JSON, preventing a single problem’s exception from interrupting the whole evaluation round.

    Five: From Evaluation Scores to Research Ability — Three Common Misreadings

    Misreading one: a high pass rate means the model can do research. The pass rate only reflects the model’s performance on the current problem pool. If the problems come from public material, a high score may come from memory rather than reasoning. It is advisable to continuously track private-problem scores and the stable pass rate across multiple independent samples.

    Misreading two: failing to solve open problems means the model is useless. The value of open problems lies not in the score but in drawing the boundary of ability. Engineering teams can break a large task into small steps such as candidate-idea generation, intermediate lemma proofs, and counterexample construction, then assess at which step the model is more reliable.

    Misreading three: AI producing results in bulk equals scientific progress. To judge whether AI output is credible, look at at least three things: whether there is independent verification; whether the key lemmas are complete; and whether the conclusion can be reproduced by others. What an evaluation can provide is a chain of verifiable evidence, not a count of results.

    Six: Engineering Practice — Building Your Own Research-Grade Evaluation

    1. Build a private evaluation set. Select automatically gradable problems in line with your business scenarios, such as scheduling, cache eviction, hash collisions, and data structure complexity.
    2. Prioritize automated grading. Design an independent verifier for each problem, with a unified interface and structured output, and use queues and containers to parallelize grading.
    3. Make metrics multidimensional. In addition to pass rates, record error types, the gap between a model’s self-assessed confidence and its actual accuracy, token consumption, and so on.
    4. Keep continuous regression. Rerun the evaluation after each model upgrade, bind the score curve to version information, and avoid regressions after an upgrade.
    5. Close the loop with human spot checks. Sample-review automatically graded results, periodically revisit error samples, and keep evaluation quality stable over the long term.

    Conclusion

    From solving problems to doing research, large models still have a long way to go. A theoretical computer science evaluation provides a clear layering: models already perform well on tasks such as knowledge reproduction and routine algorithm design, but on genuinely open problems, they have not yet produced a convincing breakthrough. For engineers, the more valuable thing to focus on is a transferable methodology: use verifiable question types to measure ability, use automatic grading to control cost, and use a private problem pool to ensure credibility. Whoever does the verification solidly can turn AI capability into reliable output.