  Phylogenetics is a classical methodology in computational biology that today
has become highly relevant for medical investigation of single-cell data, e.g.,
in the context of cancer development. The exponential size of the tree space
is, unfortunately, a substantial obstacle for Bayesian phylogenetic inference
using Markov chain Monte Carlo based methods since these rely on local
operations. And although more recent variational inference (VI) based methods
offer speed improvements, they rely on expensive auto-differentiation
operations for learning the variational parameters. We propose VaiPhy, a
remarkably fast VI based algorithm for approximate posterior inference in an
augmented tree space. VaiPhy produces marginal log-likelihood estimates on par
with the state-of-the-art methods on real data and is considerably faster since
it does not require auto-differentiation. Instead, VaiPhy combines coordinate
ascent update equations with two novel sampling schemes: (i) SLANTIS, a
proposal distribution for tree topologies in the augmented tree space, and (ii)
the JC sampler, to the best of our knowledge, the first-ever scheme for
sampling branch lengths directly from the popular Jukes-Cantor model. We
compare VaiPhy in terms of density estimation and runtime. Additionally, we
evaluate the reproducibility of the baselines. We provide our code on GitHub:
\url{https://github.com/Lagergren-Lab/VaiPhy}.
