The two structures HNSW rests on·6 min
The level dice
0 / 1
On insert, every element is assigned a maximum layer, drawn from an exponentially-decaying distribution. Most points live only on layer 0; a few reach higher. That distribution is what makes the top layers sparse express lanes and the bottom layer the dense street grid.
The level draw
l = floor( -ln(unif(0,1)) * mL ) where mL = 1 / ln(M)
With M = 8, mL = 1/ln(8) ≈ 0.4809.
unif = 0.5→-ln(0.5)·0.4809 ≈ 0.693·0.4809 ≈ 0.333→floor = 0(layer 0).unif = 0.05→-ln(0.05)·0.4809 ≈ 2.996·0.4809 ≈ 1.441→floor = 1.unif = 0.001→-ln(0.001)·0.4809 ≈ 6.908·0.4809 ≈ 3.322→floor = 3.
So P(layer ≥ 1) ≈ 1/M, P(layer ≥ 2) ≈ 1/M² — a geometric decay with p = 1/M.
Guard the unif = 0 case
unif must exclude 0, or -ln(0) = +∞. The provided mulberry32 PRNG returns values in [0, 1), so a draw can be exactly 0 — clamp it to a tiny positive value (or, like hnswlib, draw 1 - unif). The reference clamps to 1e-12; match that so your level array is byte-identical.