AI Built an Algorithm That Beats Dijkstra. Then You Try to Run It.

I found the news late one night.

Vals AI used 10 Claude Opus 5.5 agents. In 15 hours, they generated 289 files, built the C-HD shortest path algorithm, and passed Lean Kernel verification. The headline said: beats Dijkstra.

I stared at the screen. I have written Dijkstra, modified Dijkstra, and shipped code that depends on it. My first reaction was suspicion, not excitement. My second reaction was to read the qualifiers.

The qualifiers are long. After I finished, I wanted to write something.

This article is that something.

1. The media only mentioned O(n log^(11/12) n)

Start with the viral number.

Dijkstra on sparse graphs is O(n log n). C-HD claims O(n log^(11/12) n). The log exponent drops from 1 to 11/12. That gap is small, but in asymptotic complexity, it counts as faster.

The media stopped there.

The 11/12 is not a natural result on general graphs. C-HD's real bound is a composite function with several terms: edge relaxation, local hierarchical decomposition overhead, global pivot recursive coordination overhead, preprocessing sorting overhead, and meta-tracking state update overhead. Each term carries constants and logarithmic factors.

The media extracted the tuned leading term. The other terms were ignored asymptotically.

The method was tuning.

When edge density is limited to a specific interval, the middle term becomes lower order. The leading term's log exponent comes from adding two fractions. The middle term's log exponent is smaller, so in the asymptotic limit it is treated as a lower-order infinitesimal and erased from the upper-bound notation. The preprocessing sorting overhead is also pushed below the leading term by the density restriction, then erased.

What remains is O(n log^(11/12) n).

The algorithm does not produce this on general graphs. Parameterized tuning erases other terms inside the O notation.

That point matters more than the headline.

2. Hierarchical decomposition turns complexity into tuning

Dijkstra's bottleneck is the global priority queue. Each extract-min costs O(log n). You extract n times. Add edge relaxation, and the total is O(m + n log n). On sparse graphs, that additive relationship makes the n log n barrier hard to cross. Faster edge relaxation does not help. A faster heap has limits.

C-HD stops global sorting and switches to local search.

It introduces a parameter k, which sets the local search budget and the branching threshold of a pivot tree. The algorithm maintains invariants and prunes edges during local search, compressing useless exploration inside each subblock. The cost appears when the search crosses levels: it must recursively coordinate pivot points.

Total work becomes a function of k: local tree decomposition and pruning overhead, plus global pivot distance-order maintenance.

Roughly: f(k) = m/k + n log k.

Take the derivative. Find the stationary point. Solve for the optimal balance parameter. Plug it back into the total cost function.

That step matters. The edge and sorting costs that Dijkstra adds linearly are merged into a product term, a geometric mean. Addition becomes multiplication. The complexity problem becomes a tuning problem.

The 11/12 comes from this composite function under a carefully chosen parameter.

3. The qualifier list

C-HD requires all out-edges of all graph nodes to be fully sorted by weight before the algorithm starts. The preprocessing stage must sort each node's adjacency list. For each node, the cost is d_v log d_v, where d_v is out-degree.

It requires the edge count to satisfy a specific upper bound. The average degree must sit in a very small interval. The local topology must satisfy finely designed parameter constraints. If it does not, the algorithm cannot transition smoothly. It falls back to Bellman-Ford.

The optimal density is approximately m ≈ n (log n)^(3/4). The average degree is between sqrt(log_2 n) and (log_2 n)^(3/4).

That window is narrow.

Too sparse: not enough edges for local hierarchical decomposition. Too dense: the preprocessing sorting overhead backfires on the leading term. Only inside that narrow density window does the theoretical advantage hold. Deviate slightly, and the advantage disappears or the algorithm falls back.

More qualifiers mean a more limited result. That is a mathematical fact, not sarcasm.

4. Constant factor: about 600,000x, and the algorithm itself is 7%

Good theoretical complexity does not mean fast code. In engineering, constants decide.

C-HD's parameter k is concretized as a discrete variable, KcC. The recursive internal loop overhead is a constant operator, bodyC. Every recursive branch carries roughly a 600,000x search constant.

600,000x.

The measurements are direct:

• 1.4 to 2.8 times slower than naive Dijkstra.

• 1.8 to 2.9 times slower than the latest SOTA.

• Preprocessing takes 34% of the time slice.

• Meta-tracking state updates take 59%.

• The algorithm itself takes 7%.

Most of the runtime is not shortest-path computation. It is preparation and meta-state maintenance.

Dijkstra needs no preprocessing, no meta-tracking, and has good locality. One is a hammer in a craftsman's hand. The other is a precision instrument that needs three hours to warm up, two days to calibrate, and can hammer one nail in a vacuum.

5. Scale threshold: 2^(10^36) nodes

There is a more absurd number.

The derivation says roughly 2^(10^36) nodes, meeting specific requirements, are needed to theoretically beat Dijkstra.

The universe contains about 10^80 atoms.

2^(10^36) is far greater than 10^80. Not a little greater. So much greater that language cannot describe it.

Turn every atom in the universe into a graph node. The algorithm still will not run faster than Dijkstra.

This is the absurdity of asymptotic advantage. It holds mathematically and fails physically. It was designed for complexity formulas, not the real world.

6. The parameterized complexity patch

C-HD's controversy is that it exploits the edge of parameterized complexity rules.

In the 1990s, Rod Downey and Michael Fellows proposed parameterized complexity theory, turning exponential factors into constants. Reviewers at the time were stunned. Later, theoretical computer science patched this kind of operation: at minimum, use fixed-parameter tractable analysis and label the complexity honestly.

C-HD is a parameterized single-source shortest path algorithm based on parameter k. Its complexity should be labeled as: f(k) · n^O(1).

Once labeled that way, the constant f(k) is visible. It has exploded.

In publicity, f(k) was hidden inside asymptotic notation, leaving the tuned leading term. This is like inventing an algorithm with complexity 2^(2^(2^n)) + n, then saying that for large n the first term is lower order, so the complexity is O(n).

Mathematically correct. Physically insane.

The same method could prove P = NP. Turn all exponential factors into constants, hide the exploding constant in f(k), and report only n^O(1). A reviewer who ignores f(k) will think you solved a Millennium Prize Problem.

7. The value of AI4Science is not in the algorithm

After all this criticism, I have to admit something. The interesting part of C-HD is not the algorithm.

The interesting part is that 10 Claude Opus 5.5 agents, in 15 hours, generated 289 files and passed Lean Kernel machine verification. A multi-agent system can collaborate across the entire process from proposing an algorithm to formal verification. AI can automatically construct complex proofs in Lean. The threshold for formal verification is dropping.

That capability matters.

It also exposes a problem. AI can find the optimal solution inside the rules. It may not understand the trade-offs outside them. The objective function was "asymptotically strictly beat Dijkstra." So it tuned parameters, exploited rule edges, and squeezed the exponent. Whether the algorithm can run, how large the constant is, how narrow the density window is, how absurd the scale threshold is, it does not care. It only cares about the formal system's "pass."

This is not AI's failure. It is the objective function's failure.

Let AI win a game in complexity notation, and it will win. The way it wins may turn the game into a meaningless number game. A human reviewer asks, "What is this for?" AI asks, "Does this satisfy the objective function?"

8. Why Dijkstra is still Dijkstra

In 1956, Edsger W. Dijkstra designed this algorithm in twenty minutes. No agent collaboration, no Lean proof, no 289 files. One person, a blackboard, twenty minutes.

It is simple. It is elegant. It is universal. It has good locality. It has small constants.

It does not need preprocessing to sort all out-edges.
It does not need meta-tracking state.
It does not need a density restriction.
It does not need a 600,000x search constant.
It does not need 2^(10^36) nodes.
It does not need to fall back to Bellman-Ford.

It is the gold standard of algorithm engineering.

C-HD theoretically beats Dijkstra on specific graphs, at a specific density, in a specific parameterized setting. That is like someone in a parallel universe running faster than Bolt. There is theoretical significance. There is almost no engineering significance.

9. Conclusion

The most interesting part of C-HD is not that it beats Dijkstra.

It is that 10 Claudes wrote 289 Lean files in 15 hours. It is that AI learned to find loopholes in mathematical rules. It is that theoretical computer science may see an AI-driven exploration of parameterized rules. It is that formal verification is moving from human manual labor to a human-machine pipeline.

C-HD itself.

More qualifiers mean a more limited result. It achieved an extreme inside a carefully drawn density window. It remains far from general engineering use. It proves that AI can prove. It does not prove that Dijkstra should retire.

I turned off the screen when the sky was almost light.

Dijkstra is still there. 1956, twenty minutes. Simple, universal, usable.

Some results cannot be surpassed by a fraction in a complexity formula.