# Ten Claude Agents Proved a Faster Shortest Path in Lean

> Ten Claude Opus 5.5 agents spent 15 hours on a message board and produced C-HD, a Lean-verified shortest-path bound. What it beats, where, and the caveats.

- Author: Nitish Garg, Founder & CEO, CellCog
- Published: 2026-09-23
- Canonical (HTML): https://cellcog.ai/blog/claude-agents-shortest-path-c-hd/
- Section: Insights / Multi-agent & AI organizations
- Publisher: CellCog (https://cellcog.ai), the AI employee platform. Blog index for agents: https://cellcog.ai/blog/llms.txt

## Key points

- Vals AI, which runs public model benchmarks, put ten Claude Opus 5.5 agents on a shared message board and asked for a faster shortest-path algorithm with a Lean proof. After about 15 hours and 733 messages they had C-HD. The post is dated September 20, two days before Opus 5.5's public release.
- The claim is narrow and exact. On directed graphs with non-negative real weights and roughly n log^(3/4) n edges, C-HD's proved bound is O(n log^(11/12) n) against O(n log n) for Dijkstra with a Fibonacci heap. In that regime it also sits under the 2025 Duan et al. bound and a 2026 follow-up.
- The proof is machine-checked. The frozen Lean build passed 2,548 jobs, and two kernel replays each checked 18,994 constants in the final theorem's 266-module dependency closure, using only Lean's standard axioms.
- It is not a speedup anyone will measure. The authors call it an asymptotic result with enormous constants; at a graph with 2 to the 1000th vertices the leading terms differ by a factor of about 1.78. Outside its certified range the program falls back to Bellman-Ford.
- No outside expert has reviewed it yet. The two reviews in the package were written by the research agents themselves, and one was still provisional at the snapshot. Novelty and the computational model are open questions for human theorists.

## At a glance

- **What is C-HD?** A deterministic algorithm for exact single-source shortest paths on directed graphs with non-negative real weights, produced by ten Claude Opus 5.5 agents in a Vals AI experiment and proved correct and within its runtime bound in Lean 4. The snapshot is dated September 20, 2026.
- **Did AI beat Dijkstra's algorithm?** In one narrow regime, on paper. For graphs with about n log^(3/4) n edges, C-HD's proved upper bound is O(n log^(11/12) n) against Dijkstra's O(n log n). The authors say it is not a measured speedup and carries enormous constants.
- **Has it been peer reviewed?** Not by outside experts as of September 23, 2026. The package includes internal reviews written by the research agents, one completed and one provisional.
- **How long did it take?** About 15 hours and 733 messages on a shared message board, according to Vals AI.

**Ten Claude Opus 5.5 agents, one shared message board, 15 hours: the result is a machine-checked shortest-path bound that beats Dijkstra's in a narrow band of graphs.** Vals AI's write-up opens plainly: "We asked ten Claude Opus 5.5 agents to find a faster shortest-path algorithm and prove it in Lean." The answer, named C-HD, comes with a public Lean 4 package, a runtime theorem, and an unusually honest list of what it does not claim.

The honest list is the story as much as the bound. C-HD is not faster in any sense a programmer would notice. It is a proved asymptotic improvement, produced and self-reviewed by a team of agents, and nobody outside that team has checked it yet.

## What was claimed, and by whom

*Table: C-HD claims vs what the sources show, September 23, 2026*

| Claim | Status |
|---|---|
| Ten Claude Opus 5.5 agents produced the algorithm | Vals AI write-up by Geby Jaff, dated September 20, 2026 |
| About 15 hours and 733 messages on a message board | Vals AI write-up |
| Correctness and runtime proved in Lean 4 | Public package: build of 2,548 jobs passed, two kernel replays of 18,994 constants |
| Better than Dijkstra | Only on graphs with about n log^(3/4) n edges, as an upper bound |
| Better than the 2025 and 2026 published bounds | In that same band, by exponent arithmetic on the cited bounds |
| Practical speedup | Explicitly not claimed |
| Outside peer review | None; the reviews in the package were written by the agents |

## The bound, in plain terms

The problem is the classic one: a directed graph, non-negative real edge weights, find the exact shortest distance from one vertex to every other. Dijkstra's algorithm with a Fibonacci heap does it in O(m + n log n), where n is vertices and m is edges. In 2025 Duan and colleagues broke what had looked like a sorting barrier with O(m log^(2/3) n) ([arXiv 2504.17033](https://arxiv.org/abs/2504.17033)), a result that wins when graphs are sparse enough.

C-HD's proved bound is O(n + m + m log(2 + m/(n+1)) + m^(1/3) (n log(n+2))^(2/3)), valid while m stays under about n log^(3/4) n. The cleanest way to read it is to put every bound on the same graph. At m = n log^(3/4) n, each one becomes n times a power of log n:

*Table: Power of log n in each bound, on graphs with n log^(3/4) n edges*

| Algorithm | Bound on this profile | Power of log n |
|---|---|---|
| Duan et al. 2025 | n log^(17/12) n | 17/12 |
| 2026 follow-up cited by Vals | about n log^(5/4) n | 5/4 |
| Dijkstra, Fibonacci heap | n log n | 1 |
| C-HD | n log^(11/12) n | 11/12 |

So on this band C-HD's exponent is one twelfth below Dijkstra's, and the two recent algorithms are worse than Dijkstra there, which is why the band was worth attacking. The write-up does the arithmetic itself: at 2 to the 1000th vertices the leading terms differ by 1000^(1/12), about 1.78, "ignoring constants and lower-order terms". Then, in its own words: "This is not a measured speedup."

## What the Lean proof covers

The package on GitHub ([spicylemonade/c-hd-proof](https://github.com/spicylemonade/c-hd-proof)) is a frozen snapshot, downloaded at 23:58 UTC on September 20 with the note "The remote research agents were left running." It proves the final theorems `chd_exact_within`, `chd_CHDTarget` and `chd_gateC` with no remaining hypotheses. The full build passed 2,548 jobs, a fresh-copy rebuild passed, and two kernel replays each checked 18,994 constants in a 266-module dependency closure, depending only on Lean's standard axioms.

The same README sets the limits: "This is an asymptotic result with enormous constants. It does not claim a practical speedup, linear runtime, or an improvement on all graph densities." A wider density range in the informal paper is not formalized, and inputs outside the certified range go to a verified Bellman-Ford fallback.

## The review question

Vals required two peer reviews inside the experiment. The README is precise about what they are: "These are reviews by the research agents, not outside peer review." One review is complete and accepts the claim; the second was still provisional at the snapshot. As of September 23, 2026 we found no named theoretical computer scientist who has reviewed or disputed C-HD. The Lean proof answers whether the theorem is true as stated; whether the model and the novelty hold up is a question for people who work on shortest paths, and the first replies under Vals's post were already pointing at the 2025 paper.

## The chain, dated

*Table: The C-HD chain, dated (UTC)*

| Date | Event | Source |
|---|---|---|
| Apr 23, 2025 | Duan et al., Breaking the Sorting Barrier, on arXiv | arXiv |
| Sep 20, 2026 | Vals write-up dated; package snapshot downloaded 23:58 | Vals AI, GitHub README |
| Sep 21, 06:31 | c-hd-proof repository created | GitHub API |
| Sep 22, 16:31 | Anthropic announces Claude Opus 5.5 | Anthropic |
| Sep 22, 18:50 | Vals posts the thread on X | @ValsAI |
| Sep 23, 14:58 | No outside review found; repository at 30 stars | Our read |

The dates carry one detail worth stating: the work is dated two days before Opus 5.5 was public, so the agents ran on pre-release access, and the thread went out 2 hours 19 minutes after Anthropic's announcement.

## Why the message board is the interesting part

"After about 15 hours and 733 messages on the message board", the write-up says, the team had a proposed algorithm. Read that as an organization chart. Ten agents shared one board, split the problem, built on each other's partial results and gated the final claim behind reviews. The proof is a single artifact; the process that produced it was coordination.

That matches what we see in the other multi-agent results this month, such as [Nous Research's 1,393-agent refactor](https://cellcog.ai/blog/nous-hermes-1393-agents-refactor/) and OpenAI's [Navier-Stokes claim](https://cellcog.ai/blog/openai-navier-stokes/): the model matters, and so does the shared workspace, the roles and the record of who checked what. C-HD ran on [Claude Opus 5.5](https://cellcog.ai/blog/claude-opus-5-5-release-date/), the model every Claude tier in CellCog moved to on its release day.

## What we are watching for

- An outside theorist's read of the model and the novelty claim.
- A full rebuild of the portable package by someone outside the team.
- Formalization of the wider density range in the paper.
- Vals publishing the cost, the message log or the agent roles.
- The same setup on another open problem.

## Update log

As of September 23, 2026, 15:05 UTC: page opened.

## Sources

- Vals AI, [A Faster Shortest Path Algorithm](https://www.vals.ai/blogs/faster-shortest-path-algorithm), Geby Jaff, dated September 20, 2026, read September 23.
- GitHub, [spicylemonade/c-hd-proof](https://github.com/spicylemonade/c-hd-proof), README read September 23; repository created September 21, 2026, 06:31 UTC.
- [@ValsAI on X](https://x.com/ValsAI/status/2102470503328010349), September 22, 2026, 18:50 UTC (time from the post id).
- Duan et al., [Breaking the Sorting Barrier for Directed Single-Source Shortest Paths](https://arxiv.org/abs/2504.17033), arXiv, April 2025.
- Anthropic, [Introducing Claude Opus 5.5](https://www.anthropic.com/claude-opus-5-5), September 22, 2026.

## FAQ

**Who ran the C-HD experiment?**

Vals AI, a company that publishes model benchmarks. The write-up, A Faster Shortest Path Algorithm by Geby Jaff, is dated September 20, 2026, and Vals posted it on X on September 22 at 18:50 UTC, 2 hours 19 minutes after Anthropic announced Claude Opus 5.5. The Lean package is public on GitHub as spicylemonade/c-hd-proof.

**What exactly is proved?**

That a concrete deterministic program returns exact shortest-path distances and runs within O(n + m + m log(2 + m/(n+1)) + m^(1/3) (n log(n+2))^(2/3)) in the charged model, for graphs with at most n times floor(floor(log2 n)^(3/4)) edges. Reading input, allocating memory, sorting edges and writing output are all charged to the runtime.

**How does it compare with the 2025 sorting-barrier result?**

Duan et al.'s 2025 paper gives O(m log^(2/3) n) for directed single-source shortest paths. At m = n log^(3/4) n that is O(n log^(17/12) n), above both Dijkstra and C-HD. The 2026 follow-up the post cites comes to about O(n log^(5/4) n) there. C-HD's claim is only for this sparse, polylogarithmic-degree band, not for dense graphs.

**Will this make my route planner faster?**

No. The authors say it does not claim a practical speedup, and the constants are enormous. It is a statement about growth rates on astronomically large graphs.

**Why does a message board matter?**

Because the result came from coordination, not one long prompt: ten agents proposing, splitting work, reviewing and gating each other over 733 messages. That is the same shape as a team, and it is the part most agent products do not have: a shared place to work, roles, and a record of who checked what.

## Related

- [Nous Research Cut 1M Lines of Code With 1,393 Agents](https://cellcog.ai/blog/nous-hermes-1393-agents-refactor/index.md)
- [Navier-Stokes: OpenAI's 10,000-Agent Proof and the Dispute](https://cellcog.ai/blog/openai-navier-stokes/index.md)
- [Claude Opus 5.5 Is Out: Price, Specs, Every Leak Graded](https://cellcog.ai/blog/claude-opus-5-5-release-date/index.md)
- [Every Agent Tier Now Runs on Claude Opus 5.5, Day One](https://cellcog.ai/blog/cellcog-opus-5-5-day-one/index.md)

## The AI employee for this read

[AI Software Engineer](https://cellcog.ai/ai-employees/ai-software-engineer): I built this page. For what it covers, hire an engineer: it works in your repo behind an approval gate, so nothing reaches your world unclassified.

---

Markdown alternate of https://cellcog.ai/blog/claude-agents-shortest-path-c-hd/. Try CellCog free, no credit card needed: https://cellcog.ai/signup