Decision diagrams encode discrete optimization problems as directed acyclic graphs — each path from root to terminal represents a solution, and the structure enables pruning that exact methods cannot match. The standard implementation stores arcs explicitly: every connection between nodes is materialized in memory. For a diagram of width w and depth d, this means O(w²) work per layer to enumerate all possible arcs.
Note (2026-11-13; read against the paper's full text): the essay gives the standard cost as O(w squared) per layer and the gain as a full factor of w. The paper separates two cases: restricted decision diagrams go from O(w log w) to O(w) per layer, and relaxed ones from O(w squared) to O(w). The comparison with Gurobi is on randomly generated Subset Sum instances (1000 instances), where the paper reports a median speedup of 2.2 times for the default solver and 45.5 times when variables are sorted by coefficient magnitude; it calls the solver a research prototype rather than a production solver, and says the gap between a fast subroutine and a broadly competitive solver is wide. The solver is also described as highly optimized low-level engineering built on the implicit representation, so 'a structural insight, not a new algorithm, beats brute engineering' is the essay's framing.
Rudich and Rousseau (arXiv:2602.20793) show that storing arcs implicitly — computing them on demand rather than enumerating them — reduces per-layer complexity to O(w). The improvement is a full factor of w. They prove this is optimal: any framework that treats state-update and merge operations as black boxes cannot do better.
The proof of optimality is the key contribution. It means the algorithmic frontier has been reached. Further improvement requires breaking the abstraction — exploiting structure inside the operations that the decision diagram framework treats as opaque. The focus shifts from algorithm design to implementation engineering.
The practical consequence: an open-source Julia solver built on implicit decision diagrams outperforms Gurobi on Subset Sum problems. Gurobi is one of the most engineered commercial optimization solvers. The implicit representation — a structural insight, not a new algorithm — beats brute engineering.
The general observation: the representation of a computation constrains its cost. The same algorithm — decision diagram with the same width and depth — has different complexity depending on whether arcs are explicit or implicit. The computation didn't change; the way it was stored did. Sometimes the bottleneck is not the algorithm but the data structure.