How AI Agents Conduct Research Experiments: From Hypothesis to Formal Verification in Lean

AI-Agent Research Experiment — is a process in which several language models jointly search for an idea, test it with counterexamples, and translate the result into a form that can be checked by a formal system. In the experiment described, ten agents based on Claude Opus, according to the authors, proposed the CHD shortest-path algorithm and formally proved its properties in Lean in approximately 15 hours.

This story matters not as ready-made proof of the new algorithm's practical superiority. The work has not undergone independent scientific peer review, and CHD's acceleration on large real-world graphs has not yet been tested. The authors associate the experiment's value primarily with the ability of AI systems to carry out a lengthy research chain in which the idea, software implementation, and mathematical verification are connected.

What Research Tasks Can Be Delegated to a Group of Agents

A multi-agent setup is suitable for tasks whose results combine several independent types of work. One stream searches for an algorithmic construction, another tries to find a counterexample, a third compares the idea with known methods, and a separate agent translates the claims into the language of formal verification. The human specifies the problem class, constraints, and stopping criteria, rather than treating the first persuasively written answer as a research result.

• Hypothesis formulation. An agent describes the algorithm's structure, scope of applicability, and assumed complexity estimate.
• Searching for weaknesses. Another agent checks edge cases, constructs small graphs, and searches for situations in which the idea violates the stated property.
• Comparison. A separate role compares the new approach with Dijkstra's algorithm and previously published solutions, recording differences in the computational model.
• Formalization. An agent translates definitions, lemmas, and theorems into Lean, where the system's kernel performs the checking.
• Editing the result. The final agent assembles the proofs, code, applicability conditions, and limitations into a single description.

This division reduces the risk of a situation in which one model invents the idea, selects convenient examples, and declares the check successful on its own. Independent roles do not guarantee correctness, but they create points at which an error is easier to detect.

How to Distribute the Search for Ideas, Counterexamples, and Proofs

It is better to structure the workflow not as a sequential chat, but as a cycle with separate artifacts. First, the coordinator records the exact task: what counts as a graph, what constraints are imposed on sparsity, which query to the algorithm is being measured, and what the complexity is compared with. Without this specification, agents may prove different claims under the same name.

1. Setup. The coordinator records the definitions, input data, permitted operations, and required result.
2. Divergence. Several agents propose different constructions without seeing one another's conclusions, or receive them only after the first round.
3. Attack. Reviewing agents search for counterexamples on small graphs, analyze invariants, and check edge cases.
4. Convergence. The coordinator retains only ideas for which it is clear what claims need to be proved and how to measure computational cost.
5. Formalization. The agent breaks the main result down into definitions and lemmas, while Lean checks the consistency of the dependencies.
6. Repeated attack. After obtaining the proof, another agent tries to find an error in the formulation, without trusting the mere fact of successful compilation.

The key principle here is simple: the agent that proposes a hypothesis should not be the only one checking it. A counterexample is more useful than another retelling of the idea. If a claim does not withstand small test graphs, formal notation will not save the research; it will merely record an incorrectly posed problem.

What Exactly Does Lean Check

Lean is a formal verification system that allows mathematical definitions and proofs to be written in a language checked by a kernel. Successful verification of a theorem means that the formalized claim has been derived from formalized premises using permitted rules. It does not mean that the researcher chose the correct problem model, a useful class of graphs, or a realistic cost for the operations.

In the case of CHD, formal verification can confirm the correctness of individual properties of the algorithm: for example, that the path found satisfies the definition of a shortest path under the given assumptions. It does not confirm the implementation's speed, memory consumption, quality of the engineering code, or superiority on graphs that are not part of the formalized class.

And what happens if an overly strong assumption has entered the formalization? Lean will conscientiously check the conclusion derived from that assumption. This is precisely why a publication should contain not only the final theorem, but also the definitions, initial axioms, auxiliary lemmas, and limits of applicability. The reader needs to see which part of the result the system checks and which part the researcher left outside the formal model.

Why a Proof Does Not Replace an Experimental Benchmark

An asymptotic estimate describes how runtime changes as the input size grows. Practical performance also depends on constants, memory structure, the cost of constructing auxiliary data, graph access, implementation quality, and the characteristics of the specific hardware. According to the description of the experiment, CHD has large constants, so a theoretical advantage does not automatically mean a gain on real-world data.

For a certain class of sparse graphs, the authors claim asymptotic complexity superior to that of the classic Dijkstra algorithm and some previously published solutions. The description provided also mentions a theoretical advantage of approximately 1,78 times for a graph with n = 2^1000 vertices. This example illustrates asymptotics, but does not replace measurements: a graph of this size cannot be used as an ordinary practical test, and the constants may make the new method slower at every reachable size.

A proper benchmark should compare identical conditions. The researcher fixes the graph generator or real-world dataset, edge density and distribution, query source, hardware, compiler, index structure, and preprocessing time. Structure construction, query execution, peak memory consumption, and post-warm-up time are measured separately. One successful run does not show that the result is robust, so repetitions and a range of input sizes are needed.

How to Check the Result Without Independent Peer Review

The absence of peer review does not make a result false, but it changes its status. What we have before us is a research claim, not an established scientific fact. A reviewer should distinguish three levels: what the authors claim, what the formal code confirms, and what an independent experiment has shown.

A useful verification procedure begins with independently reading the formulations, continues with building the formal project in a clean environment, and ends with another team reproducing the tests. If the source code, Lean version, dependencies, or execution scripts have not been published, the reviewer should state explicitly which part of the result remains unchecked.

How to Reproduce the Experiment on Your Own Class of Graphs

First, formulate a narrow hypothesis. For example, do not test the claim that “CHD is faster than everything else,” but rather the claim about shortest-path search time on sparse graphs of a certain type under a fixed preprocessing regime. This formulation makes it possible to choose the metrics in advance and avoid changing the success criterion after obtaining convenient results.

1. Describe the class of graphs and the constraints on edge weights.
2. Formulate the algorithm's correctness and the expected complexity estimate.
3. Ask some agents to propose solutions and others to search for counterexamples.
4. Implement the baseline Dijkstra algorithm and the methods being compared in the same environment.
5. Formalize the key lemmas in Lean, beginning with small, checkable claims.
6. Run a series of tests on synthetic and real-world graphs, separating preparation from query processing.
7. Record negative results, proof failures, and cases in which the theoretical estimate did not appear in practice.

AI agents are useful here as accelerators for enumeration and formalization, but the final experimental design should be controlled by the researcher. Otherwise, the system will begin optimizing an easily measured objective, such as the number of successfully compiled lemmas, instead of a scientifically significant result.

What Artifacts Need to Be Published

Reproducibility requires more than a polished description of the algorithm. The minimum package includes the source code, the formal Lean project, a dependency file, exact graph definitions, test-data generators, execution scripts, and tables of raw measurements. For the multi-agent component, it is useful to preserve query logs, agent roles, the order of rounds, rejected hypotheses, and reasons for stopping.

• problem formulation and list of assumptions;
• source code for the algorithm and baseline comparison methods;
• Lean proofs together with library versions;
• description of the hardware, compiler, and execution parameters;
• graph generators and reference datasets;
• raw measurement results, including failed runs;
• a log of changes between the hypothesis and the final implementation;
• a separate list of properties that have been formally proved, measured, or merely claimed so far.

This set makes it possible to assess the AI contribution separately from the quality of the algorithm itself. Even if CHD shows no practical speedup, the experiment will remain useful as an evaluation of the multi-agent process: it will show at which stage errors arise, which lemmas can be formalized, and where human oversight remains mandatory.

Conclusion

The multi-agent research process combines hypothesis generation, counterexample search, programming, and formal verification. In the case described, ten agents, according to the authors, reached the CHD algorithm and a proof of its claimed properties in Lean within a limited time. However, the absence of independent peer review, large-scale practical tests, and an evaluation of constants means that practical superiority cannot be considered established.

A reliable conclusion emerges only after separating three questions: Is the algorithm correct in the given model? Does it have the required asymptotic complexity? Does it outperform alternatives on real-world data? Lean primarily answers the first question and the formalized part of the second. Benchmarks, independent verification, and publication of artifacts are needed for the rest.