💻 computer science

A Machine-Checked Cost Analysis of the BMSSP Recurrence in Isabelle/HOL With a Non-Vacuous Size-Parametric Runtime Witness

This paper presents the first machine-checked formalization in Isabelle/HOL of the BMSSP recurrence underlying the 2025 deterministic O(m log²/³ n) SSSP algorithm, providing a non-vacuous, size-parametric proof of its O(|V|·(ln|V|)²/³) runtime on an unbounded graph family without relying on axioms or unproven assumptions.

Original authors: Arthur Ramos, David Hulak, Ruy de Queiroz

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Arthur Ramos, David Hulak, Ruy de Queiroz

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a delivery driver trying to find the fastest route to every house in a massive, sprawling city. For decades, the best map we had (Dijkstra's algorithm) was like a meticulous librarian who had to sort every single address alphabetically before handing out directions. This sorting step was the "bottleneck"—it took so much time that no matter how smart the driver got, they couldn't beat the time it took to just sort the list.

In 2025, a team of researchers (Duan, Mao, Mao, Shu, and Yin) invented a new way to drive. Instead of sorting the whole city at once, they broke the city into smaller, manageable neighborhoods and solved the routes recursively. This new method, called BMSSP, is faster than the old librarian method.

What this paper does:
The authors of this paper didn't just read about this new driving method; they built a digital twin of it inside a "mathematical robot" called Isabelle/HOL. Think of Isabelle as a super-strict, unblinking referee that checks every single step of a proof to ensure it is 100% logically true, with no room for human error or "I think this works" guesses.

Here is a breakdown of their work using simple analogies:

1. The "Robot Referee" (Formal Verification)

Usually, when computer scientists say an algorithm is fast, they write a paper explaining the math and hope the reader follows the logic. This paper says, "We don't just hope; we proved it."

The Analogy: Imagine a chef claiming they can bake a perfect cake in 5 minutes. A normal paper is the chef writing down the recipe. This paper is the chef handing the recipe to a robot that bakes the cake, weighs every ingredient, times every second, and issues a certificate saying, "Yes, this cake was baked exactly as described, and it took exactly 5 minutes."
The Result: They proved the new "BMSSP" driving method is correct and calculated its speed limit mathematically.

2. The "Bucket System" (The Data Structure)

The new algorithm uses a special way of organizing data called a "bucketed partition."

The Analogy: Imagine you have a huge pile of mail. The old way was to look at every single letter to find the one with the lowest zip code. The new way uses a set of buckets. You have a directory that tells you which bucket to look in. You don't search the whole pile; you just search the directory and then the specific bucket.
The Catch: The authors had to prove that this bucket system actually works as fast as the paper claimed. They built a digital version of these buckets and proved that the "search cost" inside the bucket is indeed much lower than searching the whole pile.

3. The "Ghost in the Machine" (The Non-Vacuous Witness)

This is the most unique part of the paper. In math, you can sometimes prove a statement is true simply because the situation it describes never happens. This is called a "vacuous truth."

The Analogy: Imagine a rule that says, "If you can fly to the moon, you get a prize." If no one can fly to the moon, the rule is technically true (because no one broke it), but it's useless.
The Problem: The authors tried to prove the speed of their algorithm on a specific type of road (a long, straight line of houses). They first tried to couple the "driving schedule" too tightly to the "number of houses." They discovered that on this specific road, the tight schedule would cause the driver to get stuck after the first house. The proof would be "true" only because the driver never actually finished the trip.
The Fix: They realized they had to loosen the schedule slightly (letting the driver plan for a slightly larger city than the one they are actually driving in) to ensure the driver actually finishes the route.
The Achievement: They proved that:
1. The city (the family of graphs) actually gets bigger and bigger (it's not a fixed size).
2. The driver can actually finish the trip (the run exists).
3. The time it takes is indeed fast, even on this infinite road.

They call this a "Non-Vacuous Size-Parametric Runtime Witness." In plain English: "We proved the algorithm is fast, and we proved it actually works on a road that keeps getting longer, so the proof isn't just a trick."

4. What They Did NOT Do

The authors are very honest about the limits of their work.

They didn't build a real car: They didn't verify the entire 2025 algorithm from start to finish in a way that you could download and run on your laptop to save time.
They didn't measure real time: They didn't measure how many seconds it takes on a real computer. They measured "operation counts" (how many steps the math takes).
They didn't claim it works for every possible road: They proved it works perfectly for a specific, infinite family of "straight line" roads. They admit that proving it for every possible road shape is a much harder job for the future.

Summary

This paper is a mathematical quality control report. The authors took a brand-new, complex, and very fast algorithm for finding shortest paths, built a perfect digital model of it, and used a robot referee to prove two things:

The algorithm gives the right answers.
The algorithm is fast, and this speed claim is real (not a trick based on a situation that never happens).

They also found a "trap" in their own logic where a stricter version of the proof would have failed, and they documented exactly how they avoided that trap. It is a rigorous, "no-sorry" (no gaps allowed) verification of a cutting-edge computer science breakthrough.

Technical Summary: A Machine-Checked Cost Analysis of the BMSSP Recurrence

Problem Statement
The paper addresses the formal verification of the Bounded Multi-Source Shortest Path (BMSSP) recurrence, the core engine of the 2025 deterministic algorithm by Duan, Mao, Mao, Shu, and Yin that breaks the long-standing $O(m + n \log n)$ "sorting barrier" for directed single-source shortest paths (SSSP). While the original algorithm achieves a running time of $O(m \log^{2/3} n)$ , formalizing its correctness and, crucially, its amortized cost analysis in a proof assistant presents significant challenges. These include the complexity of recursive correctness arguments involving sets of sources and bounded distance ranges, the delicacy of amortized accounting over custom partition data structures, and the risk of "vacuous" asymptotic theorems—statements that are technically true but meaningless because the input family is bounded or the required runs do not exist.

Methodology
The authors present a complete formalization in Isabelle/HOL (Isabelle2025-2) structured into six distinct, layered theories to ensure modularity and rigorous separation of concerns. The development imports only HOL and HOL-Library, with no external axioms, sorry, or oops statements.

Semantic Foundations: The authors define finite weighted digraphs, simple walks, and distance metrics. They establish structural lemmas regarding unique shortest walks and strict tie-breaking, which form the basis for all subsequent arguments.
Recursive Correctness: An abstract model of the BMSSP recurrence is formalized, including the FindPivots routine, base cases, and the partition loop. A machine-checked proof establishes that the abstract algorithm correctly computes shortest distances for any well-formed graph.
Executable Artifact: The abstract model is refined into an executable function (bmssp_distances) using natural-number vertices and weights. The authors prove bmssp_correct_strong, confirming that the executable output matches the semantic definition of shortest distances, verified via evaluation on a specific five-vertex example.
Cost Model: An abstract partition interface (Insert, BatchPrepend, Pull) is defined with cost predicates. The authors prove an amortized cost envelope of $O(m \log^{2/3} n)$ for this abstract recurrence. Crucially, they implement a bucketed partition data structure that faithfully realizes the paper's logarithmic schedule, proving the decisive $O(\log(N/M))$ insert scale required for the speedup.
Operational Refinements: Two operational layers are defined:
- Exact-Concrete: Couples the recursive child's output strictly to the incremental range slice.
- Charged: Decouples the output, charging only the incremental slice.
  The authors machine-check that the exact-concrete relation is non-total over the intended inputs (specifically on path families), forcing an obstruction where complete runs cannot exist.
Size-Parametric Layer: The authors construct an unbounded family of unit-weight directed paths ( $P_n$ ). They prove that the charged relation is total and that a complete run exists. To ensure totality without altering the asymptotic class, they employ an "inflated" schedule index ( $N = n \cdot n$ ), which ensures the bucket capacity covers the path while preserving the $O(\log^{2/3} n)$ factor.

Key Contributions

First Mechanized Formalization: This is the first machine-checked formalization of the BMSSP recurrence and its running-time analysis.
Non-Vacuous Size-Parametric Witness: The paper provides a fully unconditional theorem witnessing that on the unbounded family of unit-weight directed paths, the charged running time is $O(|V| \cdot (\ln |V|)^{2/3})$ . This result is non-vacuous because the authors explicitly prove (via a "non-vacuity ledger") that the family grows without bound, a complete run provably exists, and the operating regime is realized.
Formal Diagnosis of a Coupling Obstruction: The authors formally identify and prove a defect in a naive, tightly coupled cost relation (the exact-concrete model). They demonstrate that this relation forces the algorithm to take at most one step on path families, rendering any size-parametric bound based on it vacuous. This obstruction is recorded as a machine-checked lemma, and the headline result is derived using the decoupled charged relation to bypass it.
Executable Verification: The development includes an executable shortest-distance function with a correctness proof that is validated by code evaluation within the build process.

Results
The headline theorem, path_nonvac_runtime_bigo_card_V_unconditional, states:
$(\lambda n. \text{real}(\text{path\_nonvac\_time } n)) \in O(\lambda n. \text{real}(\text{card}(\text{path\_k\_V } n)) \cdot (\ln(\text{real}(\text{card}(\text{path\_k\_V } n)) + 2))^{2/3})$
This bound is:

Unconditional: It carries no hypotheses regarding run existence or graph properties beyond the definition of the path family.
Size-Parametric: The asymptotic variable is the true graph size ( $|V|$ ), not a fixed parameter.
Non-Vacuous: It bounds the cost of a least-cost run that is proven to exist.

The paper also establishes the $O(m \log^{2/3} n)$ bound for the abstract cost model realized by the concrete bucketed structure, confirming the $O(\log(N/M))$ insert scale.

Significance and Scope
The authors explicitly frame the significance of this work as a rigorous formalization of the BMSSP recurrence's correctness and charged running-time analysis, rather than a full end-to-end verification of the Duan–Mao–Mao–Shu–Yin SSSP implementation.

What is Claimed: The paper claims to have verified the correctness of the recurrence logic and the validity of the charged operation-cost analysis, including a non-vacuous asymptotic bound for a specific unbounded family.
What is Not Claimed: The authors do not claim to have verified the machine-step complexity of the exported SML code, nor do they claim a universal bound for all graphs or all runs. They explicitly state that the size-parametric headline bounds the least-cost run of a specific family, as a universal bound is false for this family.
Methodological Contribution: The paper highlights the importance of "non-vacuity" as a first-class proof obligation in mechanized complexity. It demonstrates that asymptotic theorems can be logically valid yet empty if the input family is bounded or runs do not exist. The "non-vacuity ledger" (proving growth, run existence, and regime realization) is presented as a reusable template for future formalizations of recursive complexity arguments.

In summary, the work provides a high-assurance, machine-checked foundation for the BMSSP recurrence, rigorously separating the functional correctness from the cost analysis and carefully diagnosing and navigating the pitfalls of formalizing amortized complexity to ensure the resulting asymptotic bounds are meaningful.