The proof is doing more work here than the graphics card. Computed the original way, UniFrac is a walk over the phylogeny: for each pair of samples you visit every branch, weight it by branch length, and accumulate a numerator of differences and a denominator of totals, which is why cost tracks the number of taxa in the tree and grows with the square of the number of samples [5]. Computed the new way, that same ratio is a weighted Jaccard similarity over branch values, the sum of elementwise minimums over the sum of elementwise maximums, with unweighted UniFrac equal to one minus it [7]. Weighted Jaccard is a quantity you can estimate from compact signatures, and the paper, published on nature.com, says DartUniFrac exploits sketching algorithms to do exactly that [2][11]. The text supplied does not name which sketch family.
The two headline numbers should not be multiplied together. "Up to three orders of magnitude" is a ceiling rather than a typical case [1], and against quadratic scaling in sample count a thousandfold speedup buys only about a 32-fold increase in cohort size at constant wall-clock time, since the square root of 1,000 is 31.6 [1]. The claimed jump is much larger. Twenty years of prior optimization, including Striped UniFrac and SIMD or GPU acceleration, worked at a few thousand samples [6], and going from three thousand samples to a million is a 300-fold increase in samples and roughly a hundred-thousand-fold increase in pairs, of which a thousandfold speedup accounts for about one per cent [2]. The remainder has to come from per-pair work falling away, which is what you would expect if the cost of a comparison is now set by sketch length instead of branch count [2]. Trees that large are not hypothetical: model-based estimates from 16S data put Earth's microbial species count above 10^12 [9].
The thing this does not tell you is what the approximation costs. The abstract and the opening of the main text report speed and scale; they do not state an error bound for sketched distances, nor compare sketched output against exact output [10]. That gap matters because the reason to prefer UniFrac over Bray-Curtis or plain Jaccard is statistical, not aesthetic: it tends to yield higher PERMANOVA R2 values and clearer ordinations when community turnover involves distantly related lineages [4]. A sketch that blurs small distances could hand back the separation you were paying for.
There is also a bottleneck the speed benchmark does not measure. All-versus-all on a million samples is about 5.0 x 10^11 unique pairs, and in single precision that matrix runs to roughly 2 terabytes before any ordination reads it [3]. Fast distances leave you holding an object most downstream tooling was not written to hold.
The reach is wider than 16S surveys, since the argument concerns branch values and applies wherever the unit of interest is defined, including metagenome-assembled genome species units delimited by average nucleotide identity [8]. My position, with its condition attached: for exploratory ordination on a cohort that is currently out of reach, I would run this today; before reporting a PERMANOVA R2 computed from sketched distances, I would want the error bound out of the supplementary methods and in front of me [4][10].
