Research-Oriented Evaluation Exposes LLM Limits in Theoretical Computer Science

    Research-oriented benchmarks test whether large language models can move beyond solving familiar problems to tackling tasks with unknown answers. Theoretical computer science offers a useful testing ground because many outputs can be checked mechanically. This article examines the principles behind verifiable, contamination-resistant evaluation, explains the limits reported on open conjectures, and outlines practical lessons for engineering teams building their own assessments.

    1. From Solving Problems to Conducting Research

    Large language model benchmarks evolve quickly, with new leaderboards appearing regularly. Most, however, address the same question: Can a model produce an answer close to the expected solution for an existing problem?

    These evaluations are useful for measuring knowledge coverage, reasoning, and code generation. They are less effective at answering a more demanding question: Can a model perform work resembling real research when there is no established procedure, the answer is unknown, and even the person posing the problem may not know whether the proposed conclusion is true?

    Problem-solving and research differ structurally. Solving a standard problem resembles following a well-tested recipe: the ingredients, steps, and expected result are defined. Research is closer to navigating unfamiliar terrain. It requires formulating questions, defining concepts, finding counterexamples, constructing proofs, and recognizing directions that are unlikely to succeed.

    Research tasks may have no single correct answer, and some remain unresolved for years. This creates two evaluation challenges:

    1. Processes are difficult to standardize. Research has no fixed workflow, so matching a model’s steps against a reference solution is insufficient.
    2. Results can be expensive to verify. A model may generate hundreds of pages of reasoning that experts must inspect. If it claims to have solved a long-standing problem, assessing that claim itself requires specialized expertise.

    A meaningful research benchmark therefore needs tasks that resemble research but can still be graded by machines. Theoretical computer science (TCS) provides one way to meet both requirements.

    2. Why Theoretical Computer Science Is a Useful Testing Ground

    TCS studies computation itself: whether a problem is solvable in principle, how many resources it requires, whether better algorithms exist, and whether certain structural conditions make a task impossible. At the intersection of mathematics and computer science, its research centers on definitions, theorems, proofs, and counterexamples.

    Compared with many experimental or engineering disciplines, TCS has an important evaluation advantage: many results can be formalized or checked mechanically. A proof checker can validate a formal proof. A deterministic program can test a proposed counterexample. Constraint-solving tools or independent checking programs can verify whether a construction satisfies specified requirements.

    This verifiability makes evaluation more scalable. Assessors can obtain relatively objective grading signals without relying entirely on experts to read every submission.

    The case for starting with TCS is not that the field is easier than other disciplines. Rather, its outputs are often more amenable to machine verification.

    The publicly described benchmark contains 100 problems organized around four typical activities in TCS research. The overview does not detail those four categories, but its design objective is clear: make tasks resemble real research while preserving the feasibility of automated grading.

    3. Benchmark Design: Verifiability, Contamination Resistance, and Difficulty Levels

    A research-oriented benchmark needs more than a collection of difficult questions. Credible results depend on several design principles.

    Machine-Verifiable Answers or Proofs

    Evaluations should prioritize tasks whose outputs can be checked by deterministic verifiers. These may include formal proof checkers, constraint checkers, deterministic answer comparators, or independent validation programs written for particular structures.

    The verification logic should remain separate from the model being evaluated, reducing opportunities for a model to exploit the grading mechanism rather than solve the task.

    Separation from Training Data

    Once research problems become public, they may enter subsequent training datasets. Evaluators therefore need data separation, time-based splits, and contamination checks.

    Possible measures include retaining unpublished variants, dynamically generating parameterized instances, and checking whether model outputs reproduce known solutions. Without such controls, a high score may reflect memorization rather than research ability.

    Coverage Across Task Types and Difficulty Levels

    A benchmark should not rely on a single task format. TCS research includes problem formalization, conjecture generation, proof construction, counterexample search, complexity analysis, and reduction design.

    Organizing problems around four research activities can help reveal strengths and weaknesses at different stages of research instead of compressing performance into one overall score.

    Cost Tracking and Reproducibility

    Research-oriented evaluation often involves long outputs and repeated verification. The evaluation pipeline should record model-call costs, latency, verification time, and failure reasons so that models can be compared under equivalent constraints.

    For open-ended problems, evaluation should also distinguish among outcomes such as:

    • Solving a task independently
    • Making progress with hints
    • Producing verifiable partial results

    A binary pass-or-fail judgment can obscure meaningful differences in capability.

    4. Interpreting the Results: Open Conjectures Remain a Major Barrier

    The conclusion reported in the public materials is sobering: none of the evaluated frontier models independently solved the unresolved open conjectures included in the evaluation.

    This finding requires careful interpretation.

    It does not mean that LLMs have no value in mathematics or TCS. Models can help organize definitions, draft proofs, identify known lemmas, propose candidate counterexamples, and flag obvious gaps in reasoning. When subtasks have reliable verifiers, researchers can quickly filter model outputs and reduce repetitive work.

    However, producing professional-looking proof text is not the same as achieving a research breakthrough. Open conjectures often require new constructions, new invariants, or insights connecting different fields. Pattern-based generation alone does not reliably produce those advances.

    Models may also generate errors that are difficult to check. Even after an error is identified, they may respond with a revised argument containing a new chain of mistakes. Without reliable verification, fluent writing can conceal these failures.

    The value of research-oriented evaluation therefore extends beyond ranking models. It helps establish boundaries: which tasks models can reliably support, which still require human leadership, and which are suitable for decomposition into human–AI workflows.

    5. Practical Lessons for Engineering Teams

    Developers and enterprise engineering teams can apply these evaluation principles to internal model selection and capability assessment.

    Do Not Rely Solely on General-Purpose Leaderboards

    General benchmarks are useful for initial screening, but they cannot replace evaluations built around actual workloads.

    Teams that need formal verification, complex reasoning, or high-reliability code generation should build private test sets with verifiable answers. They should also define task types, difficulty levels, and acceptable failure rates.

    Prioritize Verifiers over Grading Prompts

    Asking another model to score an output can introduce grading bias. A more dependable approach is to use deterministic validation programs, formal checks, constraint checks, or unit tests where appropriate.

    For tasks that cannot be fully verified automatically, teams can combine sampled expert review with analysis of agreement among multiple reviewers.

    Build Contamination Controls and Versioning into the Process

    Evaluation datasets should be versioned and separated into development, validation, and hidden test sets. For parameterized tasks, random seeds should be refreshed periodically.

    Teams should also record:

    • Model versions
    • Prompt templates
    • Decoding parameters
    • Verifier versions

    Without these records, results are difficult to reproduce, and apparent gains may be impossible to distinguish from evaluation leakage.

    Report Multiple Metrics Instead of One Score

    A useful evaluation report should include at least:

    • Independent completion rate
    • Verification pass rate
    • Average verification cost
    • Human review intervention rate
    • Error-type distribution
    • Reliability across long outputs

    For research-oriented tasks, the number of verifiable partial results and the time needed to locate errors can also provide a more realistic measure of collaborative value.

    A simplified evaluation pipeline might look like this:

    1. evaluate(model, benchmark):
    2. for task in benchmark.tasks:
    3. response = model.solve(task.prompt, constraints=task.constraints)
    4. verdict = verifier.check(task, response)
    5. record(task.id, task.category, verdict,
    6. cost=response.cost, latency=response.latency,
    7. error_type=verdict.error_type)
    8. return aggregate_by_category_and_difficulty(records)

    In an engineering implementation, cloud object storage can hold tasks and outputs, a container platform can isolate verifier execution environments, and logging services can preserve the full evaluation trace.

    Teams using Baidu AI Cloud could likewise assemble a pipeline from these general service categories, subject to the services available in their deployment environment. The essential requirements remain verification logic, data separation, and reproducibility—not a particular provider or interface.

    6. Toward Verifiable Research Capability

    Research-oriented evaluation is not primarily about creating another leaderboard. It asks a more precise question: Can a model contribute meaningful results when answers are unknown, the process is open-ended, and conclusions must be verified?

    The machine-checkable nature of many TCS outputs makes the field a useful testing ground. The reported results indicate that frontier models have not crossed the threshold of independently resolving the evaluated open conjectures. Nevertheless, they can still assist with verifiable subtasks, proof drafts, and error screening.

    For engineering teams, the practical lesson is to place less weight on a single benchmark score and invest more in private evaluations that are verifiable, resistant to contamination, and reported by task type and difficulty. Models should be assessed within human–AI workflows, rather than treating fluent output as evidence of a reliable conclusion.

    The goal is not to dismiss model capabilities, but to measure their boundaries clearly and reproducibly.