How Theoretical Computer Science Challenges Assess LLM Research Capabilities

    Public benchmark scores fall short in evaluating the actual research capabilities of Large Language Models (LLMs). This article explores how theoretical computer science problems with formally verifiable conclusions can be used to assess LLMs. It covers the rationale for this approach, task design covering typical research scenarios, machine-verifiable scoring mechanisms, result interpretation, and practical steps for implementing such evaluations.

    1. Why Benchmark Scores Cannot Measure Research Capability

    Public evaluation scores for large language models (LLMs) are updated frequently, but most benchmarks test problems with standard answers and fixed solution paths. These tasks are akin to cooking with a recipe: the steps are known, the outcome is standardized, and scoring is easily automated.

    Scientific research does not work this way. Research questions often lack a predetermined path, outcomes are uncertain in advance, and sometimes even the problem setters do not know the answer. Therefore, relying solely on benchmark scores makes it difficult to determine whether a model can engage in genuine research.

    Research scenarios also introduce two practical challenges:

    1. Large output volume. A model might generate very long proofs in a single pass, making manual line-by-line review costly.
    2. Difficult result verification. When a model claims to have solved a long-standing open problem, reviewers must spend a significant amount of time confirming its correctness.

    Institutions have previously released large batches of AI-generated mathematical manuscripts. The sheer volume of these materials indicates an equally massive verification workload. While output generation is easy, verification is hard—this is the most prominent contradiction when evaluating research-oriented models today.

    2. Machine Grading for Theoretical Problems: Selecting Verifiable Conclusions

    Mathematics and theoretical computer science possess a distinct advantage: many conclusions can be checked formally. Sudoku provides an intuitive analogy. Solving a Sudoku puzzle is difficult, but verifying a completed one takes only seconds.

    Theoretical computer science focuses on computation itself, including how fast algorithms can run, whether problems have efficient solutions, and whether certain classes of problems are inherently unsolvable. Most of these conclusions can be written as explicit propositions and verified through the following methods:

    • Verifying derivations step-by-step against formal definitions.
    • Constructing specific instances and running programs to check the conclusions.
    • Exhaustively searching small-scale inputs to verify boundary cases.

    When selecting problems, consider the following dimensions:

    Dimension General Open Research Problems Machine-Verifiable Theoretical Problems
    Grading cost High, requires expert page-by-page review Lower, can use checking programs or formal tools
    Standard answer May be entirely unknown Usually verifiable
    Conclusion reliability Depends on peer review Can be directly confirmed by running checks
    Coverage Broad Narrow

    The narrow coverage is the trade-off of this approach. This methodology applies only to theoretical problems that can be expressed formally or checked via execution. It is not applicable to experimental science conclusions requiring wet labs, engineering system performance in real-world environments, or open research questions lacking formal definitions. Therefore, evaluation results represent capabilities for this specific category of tasks and cannot be directly generalized to all research work.

    3. Task Design: Covering Typical Research Scenarios

    A research-oriented evaluation should cover several typical stages of a researcher’s daily work. Below are examples categorized by task type, with explanations of their grading methods.

    1. Proof Completion

    The problem provides a theorem statement and a partial proof, requiring the model to complete the missing inference steps. For grading, the reasoning can be converted into a formal language and verified by a proof checker, or it can be broken down into several sub-propositions and checked individually.

    The difficulty with these tasks is that models often skip steps that seem obvious. A proof checker directly exposes such issues.

    2. Counterexample Construction

    The problem provides a conjecture and requires the model to construct an instance that satisfies the premises but violates the conclusion. The grading program only needs to run the instance and check the conclusion, without needing to understand the proof process.

    The grading criteria for counterexample tasks are highly explicit: a valid counterexample scores, an invalid one does not.

    3. Algorithm Design and Complexity Analysis

    The problem describes a computational challenge, requiring the model to provide an algorithm and analyze its time or space complexity. Grading involves two steps: first, run the algorithm on small-scale instances to check if the output is correct; second, compare the claimed complexity against known results for that problem to determine its plausibility.

    The second step is only applicable to problems with known optimal complexity or provable upper/lower bounds. For other problems, comparisons should be made against public baseline algorithms or provable lower bounds, rather than against a non-existent “standard answer.”

    Furthermore, correctness on small-scale instances does not guarantee general correctness. Instance sizes and coverage must be carefully designed.

    4. Solvability and Reduction Determination

    The problem requires determining which complexity class a given problem belongs to and providing a reduction explanation. The correctness of the reduction can be sampled using small-scale instances:

    1. def check_reduction(reduce_fn, solve_src, solve_tgt, small_instances):
    2. """Check for each small instance: the answer of the source problem matches the answer of the reduced target problem."""
    3. for x in small_instances:
    4. if solve_src(x) != solve_tgt(reduce_fn(x)):
    5. return False
    6. return True

    This check only provides necessary conditions and cannot prove the reduction is correct. The polynomial-time nature of the reduction and the argument that it holds for all inputs still require manual review.

    4. Scoring Mechanisms: Turning Correctness into Executable Checks

    The key to scoring is converting the model’s output into an independently executable check. Below is a schematic implementation of a counterexample checker using graphs as an example. The instance submitted by the model is a dictionary containing the number of vertices n and a list of edges edges.

    1. def is_well_formed(candidate, max_size):
    2. """Validate the structure and size of the instance; reject invalid inputs directly."""
    3. if not isinstance(candidate, dict):
    4. return False
    5. n = candidate.get("n")
    6. edges = candidate.get("edges")
    7. if not isinstance(n, int) or not (1 <= n <= max_size):
    8. return False
    9. if not isinstance(edges, list) or len(edges) > n * (n - 1) // 2:
    10. return False
    11. for e in edges:
    12. if not (isinstance(e, (list, tuple)) and len(e) == 2):
    13. return False
    14. u, v = e
    15. if not (isinstance(u, int) and isinstance(v, int)):
    16. return False
    17. if not (0 <= u < n and 0 <= v < n) or u == v:
    18. return False
    19. return True
    20. def check_counterexample(candidate, conjecture, max_size=12):
    21. """Check if the counterexample provided by the model is valid.
    22. candidate: The instance provided by the model, must pass structure and size validation first.
    23. conjecture: The proposition to be tested, returns True if the proposition holds for the instance.
    24. """
    25. if not is_well_formed(candidate, max_size):
    26. return "invalid_instance" # Invalid structure or size exceeded, judged as invalid directly
    27. if conjecture(candidate):
    28. return "not_counterexample" # Proposition holds, not a counterexample
    29. return "valid" # Proposition does not hold, a valid counterexample

    When implementing such checkers, note the following:

    1. Treat model output as untrusted input. Validate the structure and size before performing computations to prevent oversized inputs from exhausting resources.
    2. Execute in an isolated environment. When running model-generated code or instances, use a sandbox to restrict network access, file read/write permissions, and execution time. The conjecture function should also run under the same restrictions.
    3. The checker itself needs validation. Test the checker with known correct and known incorrect samples to ensure it can distinguish between the two.
    4. Avoid loopholes for partial credit. If the checker awards points for answers that “look almost correct,” the evaluation results will exceed the actual capability. Scoring should be a binary pass/fail unless the problem itself defines a grading rubric.

    5. Interpreting Results: Distinguishing Unsolved from Incapable

    Evaluation results must be interpreted cautiously. Suppose a group of models fails to solve an open conjecture in the test. The only conclusion to be drawn is that, within the scope of the tested problems, these models could not independently solve the open problem. This does not mean the models are entirely useless for known conclusions, nor does it mean they will never be able to conduct research.

    When reporting results, the following information should be provided: the number of problems and their type distribution, model names and versions, scoring criteria, the number of runs per problem, and the confidence interval of the results. If there are only a few dozen problems and a small number of models, the conclusion only explains their performance on this set of problems and cannot be generalized into an overall judgment of research capability.

    When interpreting results, the following principles can be followed:

    • Report by task type. Scores for proof completion, counterexample construction, and open problems should be listed separately to avoid masking differences with a single total score.
    • Distinguish known from unknown results. A model’s ability to restate known theorems is a different capability from its ability to discover new conclusions.
    • Record error types. Common errors include skipping key steps, citing non-existent theorems, and conclusions that only hold on small-scale instances. Error types are more informative than error counts.
    • Verify novelty claims. When a model claims to have solved a problem, check the literature first to confirm whether the conclusion has already been recorded.

    6. How to Evaluate LLM Research Capabilities: Practical Steps

    If a team wants to evaluate a model’s performance on research-oriented tasks, they can proceed with the following steps:

    1. Define the output format first, requiring the model to provide proofs, counterexamples, or algorithms in a parseable format.
    2. Write a separate grader for each type of problem and run it in an isolated environment.
    3. Validate the graders using known correct and known incorrect samples.
    4. Compile results by problem type separately and record typical errors.
    5. For new conclusions claimed by the model, conduct a literature search for plagiarism first, then discuss its value.
    6. Prevent training data contamination. This can be achieved by: using only new problems published after the model’s training cutoff date; keeping a portion of private, unexposed problems as a test set; regularly rotating the problem bank to eliminate published problems; and conducting spot checks quarterly to review whether the graders and problems remain valid.

    The purpose of evaluation is to provide a basis for decision-making, not to rank models. When grading criteria are clear and errors are traceable, evaluation results can genuinely help a team determine which parts of the research workflow a model can handle.