Evaluating LLM Research Capabilities: Verifiable Proofs and Capability Boundaries

    This article examines how to evaluate large language models as research assistants in mathematics and theoretical computer science by requiring machine-checkable outputs rather than plausible prose. It covers proof, construction, and optimization tasks; the role of intermediate lemmas; hidden variants and anti-cheating checks; closed-loop research agents; capability boundaries; multidimensional metrics; and future directions in formalization, hybrid verification, and human-machine research protocols.

    1. From Answering Questions to Reproducible Checks: The Core Shift in Research Evaluation

    Large language models are moving from question-answering systems toward research assistants, but research scenarios differ fundamentally from ordinary Q&A: an answer must not only look plausible, but also be independently verifiable. A proof can be fluent yet logically broken; a construction can appear complex yet fail counting, boundary, or invariant checks; a program optimization can pass tests while violating constraints. Evaluation for mathematics and theoretical computer science should therefore not ask only what the model said, but establish a closed loop: task normalization → candidate generation → machine checkability → traceable failures → reproducible metrics.

    The key is to place research-process outputs inside the same verifiable system. Such a system should include at least four kinds of objects: formal statements, executable checkers, constraints, and failure logs. If a model output cannot be consumed by a checker, it remains explanatory text. Only when a checker can accept it, produce a counterexample, or identify a missing lemma does it begin to resemble a research assistant.

    2. What to Evaluate: Proofs, Constructions, and Tightening Upper Bounds

    Tasks in theoretical computer science broadly fall into three categories. The first is proof-oriented work, which requires a chain from axioms and lemmas to conclusions and should expose intermediate justification as much as possible. Without intermediate lemmas, models may skip steps, making errors harder to locate. The second is construction-oriented work, which requires explicit objects such as graphs satisfying forbidden-subgraph conditions, coding tables, combinatorial designs, or parameter configurations. These tasks can often be checked quickly through program enumeration, randomized search, or structured construction. The third is optimization-oriented work, which requires improving known bounds under constraints, for example tightening an existing upper bound from 84 to 82 or constructing an edge count better than a reference value.

    A high-quality benchmark should not count only final correctness. It should record four dimensions: attempts, passes, coverage, and stability. Attempts reflect search resilience; passes reflect verifiable success rate; covered theorems reflect task diversity; stability across multiple samples reveals whether the model truly has the capability or merely hit the target by chance. For long-horizon reasoning, a single high score may come from luck, while cross-task coverage and low-variance passes are closer to the capability itself.

    3. Why Intermediate Lemmas Are a Dividing Line

    In proof tasks, whether intermediate lemmas are provided significantly changes difficulty. Without lemmas, the model must fill them in: identify key lemmas, choose induction or contradiction paths, maintain symbol consistency, and stitch local conclusions into a global argument. With lemmas provided, the task reduces to more controllable lemma ordering and conclusion assembly, closer to proof planning.

    In engineering practice, layered prompts can be introduced: layer zero gives only the proposition; layer one provides a proof skeleton; layer two provides candidate lemmas but requires dependency annotations; layer three requires machine-parsable intermediate goals. Comparing pass rates across layers can locate whether the model’s weakness lies in problem decomposition, lemma discovery, or final formalization. If a model can complete some theorems without a skeleton but fails extensively when required to justify its basis, it is more like a strong heuristic search than a stable deductive system.

    4. Constructions and Counterexamples: Where Real Breakthroughs and Cheating Are Most Likely

    The appeal of construction tasks is that answers can be brute-force verified. Consider an extremal graph task: construct a graph with no triangles and no quadrilaterals while maximizing the number of edges. If the model returns an object with 124 vertices and 630 edges, the checker only needs to validate the adjacency list, confirm the girth constraints, and count the edges. Such results are harder to fake than an abstract proof because the object itself is the evidence.

    Construction tasks also carry risks: models may memorize common instances or accidentally satisfy weak constraints during randomization. Evaluation should include hidden variants, such as changing the number of vertices, raising the target edge count, restricting degree distributions, or requiring a generation algorithm rather than only a result. A stricter approach requires a constructor + seed + validation script: the same constructor must reproduce results under different random seeds, and only then are pass rate and stability acceptable. For enterprise R&D pipelines, this resembles continuous integration: a single green run does not prove capability; stable green runs count as regression passes.

    5. From Model Capability to Systems Engineering: Verifiable Research Agents

    A genuinely usable research agent needs to connect generation, execution, checking, and backtracking into a closed loop. An illustrative workflow is as follows:

    1. Task specification
    2. ├─ Proposition / constraints / objective function
    3. ├─ Resource budget: time, call count, memory
    4. └─ Output protocol: proof script | construction data | checker results
    5. ↓
    6. Candidate generator: LLM proposes proof paths, object structures, or search parameters
    7. ↓
    8. Execution and checking: formal kernel, SMT / constraint solving, graph validation, unit tests
    9. ↓
    10. Failure attribution: logical break, constraint violation, timeout, memory blowup, format error
    11. ↓
    12. Memory and retry: retain passed lemmas, isolate counterexamples, repair locally rather than answer globally

    There are three engineering principles here. First, the checker must be independent of the generator to avoid the system judging itself. Second, all success evidence should be archived for review, comparison, and audit. Third, failures should be encoded as states rather than returned only as natural-language complaints. Logging services, object storage, container platforms, and monitoring alerts in general cloud environments can support such a loop, but the value lies not in any proprietary component, but in bringing uncontrollable generation into an observable, rollback-capable, and recomputable process.

    6. Capability Boundaries: Solving Problems Is Not the Same as Choosing Them

    Evaluation conclusions should distinguish three kinds of capability. The relatively mature one is local breakthrough under a clear objective: when the problem statement is clear, feedback is immediate, and budget is sufficient, models can complete some proofs, improve constructions, and optimize program paths. The less stable one is cross-task transfer: strong performance on one class of graph construction does not mean the same level of performance on coding-theory upper bounds or probabilistically checkable proof-related tasks. The one still led by humans is problem selection: deciding which open problem is worth investing in, estimating proof difficulty, identifying the importance of a conclusion, and deciding whether to release partial results.

    This is closely related to research management. If a model is treated as an tireless junior researcher, it can expand the search space; if it is treated as a collaborator that sets its own agenda, it can waste substantial compute in the wrong direction. A more robust division of labor is: humans propose questions that are theoretically valuable and decomposable; machines generate candidates, counterexamples, and intermediate lemmas; checkers reject invalid results; humans make value judgments and correct direction.

    7. Designing Metrics: Don’t Let Averages Hide Structure

    Common leaderboards favor a single total score, but research capability is more like a terrain map. At minimum, report the following metrics: pass rate by task type; the difference between conditions with and without intermediate lemmas; target improvement in construction tasks and improvement relative to reference bounds; variance across random seeds; failure-type distribution; and benefit per unit of compute, such as effective theorems per GPU hour or per call. For long-context systems, also measure whether intermediate conclusions remain consistent after context exhaustion.

    Be especially wary of high-score, low-capability combinations: a model may repeatedly score on an easily auto-verifiable subset while stalling on tasks requiring novel lemmas; it may also bypass concise proofs through verbose reasoning, appearing successful but remaining unmaintainable. Metrics such as relative bound tightening, explicit constructions, and multi-theorem coverage are usually closer to real research contribution than broad accuracy.

    8. Future Directions: Formalization, Hybrid Verification, and Human-Machine Research Protocols

    The next step is not simply to keep scaling parameters, but to increase verifiable density. Formal proof languages and proof assistants can serve as a final review layer even if generation remains in natural language; constraint solvers, SAT/SMT, graph isomorphism and counting tools can act as low-cost judges; retrieval augmentation can introduce published bounds, standard constructions, and common lemmas. More important is protocol design: require models to output content that can be falsified, such as explicit parameters, candidate objects, and lemma dependency graphs, rather than only conclusive prose.

    From an industry perspective, these capabilities will change how R&D organizations work. In areas such as mathematical modeling, chip constraints, protocol correctness, and scheduling optimization, “let the model give suggestions” can be upgraded to “let the model submit evidence.” When evidence can enter version control, regression tests, and third-party review, AI moves from a talking copilot to auditable research infrastructure. The boundary remains clear: taste in major open problems, trade-offs in proof aesthetics, and judgments about the impact of conclusions should remain with humans in the short term; search, verification, recomputation, and local repair will increasingly be delegated to machines.