A phylogenetic tree can be built one species at a time. Each new leaf is attached to one of the branches already present, and the record of those choices is a short integer vector that maps one-to-one onto tree shapes. Current neural samplers that build trees this way choose the branch mostly from the shape of the partial tree. The DNA data enter mainly through the reward that scores the finished tree. This note proposes a different way to score each candidate branch. Every branch cuts the current tree into two sides. We score a branch by contrasting how well the new species' sequence fits each side, and by checking whether the species not yet placed would also respect that cut. This is the "look left, look right" idea from video action detection, where a boundary is judged by contrasting what comes before it with what comes after it. Here it is moved onto the bipartition that a tree branch defines.
The motivation is that tree space is far too large to search blindly. There are $(2n-5)!!$ unrooted topologies for $n$ species, more than $10^{22}$ at 20 species (Variational Combinatorial Sequential Monte Carlo for Bayesian Phylogenetics in Hyperbolic Space). Samplers that can reach every tree pay for it with noisy training, because they waste samples on implausible topologies (ARTree). Samplers that restrict themselves to bootstrap-preselected splits risk missing the posterior mode (Variational Bayesian Phylogenetic Inference). The claim is that data-driven contrast across each candidate cut concentrates a full-support sampler on plausible trees. It should do so without hard support restriction, and it should reduce the compounding of early mistakes that fixed insertion orders cause.
Core Claim
The proposed sampler parameterizes each entry of an Ordered Leaf Attachment vector with a cut-contrast scorer. Ordered Leaf Attachment, from Vector Encoding of Phylogenetic Trees by Ordered Leaf Attachment, is a linear-time bijection that records, for each added leaf, the label of its new sister node. The claim is that this sampler gives lower KL divergence to long-run MCMC posteriors and lower lower-bound variance than topology-feature autoregressive models, at comparable wall-clock cost. Most of the gain should come from the two-sided contrast and from a "completeness" signal computed from unplaced species, not from simply feeding sequences into the network.
The concrete mechanism works as follows. At step $i$, leaf $x_i$ is to be attached to one of the $2i-3$ existing edges. For a candidate edge $e$, let $a_e$ and $b_e$ be the per-site conditional likelihood vectors on the two sides of $e$. These are the "below" and "above" partial likelihoods that Felsenstein's two-pass pruning algorithm computes for every edge in one postorder and one preorder sweep. Let $u_e$ summarize how the not-yet-inserted species divide between the two sides. The attachment distribution is
$$p_\theta(v_i = e \mid v_{<i}) \propto \exp\big( f_\theta( g(a_e, x_i),\; g(b_e, x_i),\; g(a_e, b_e),\; u_e ) \big),$$
where $g$ is a learned site-pooled comparison of two conditional likelihood profiles and $f_\theta$ is a small network. The first two arguments are the "left" and "right" contexts of the cut. The third measures how distinct the two sides are. The fourth plays the role of the completeness classifier in Temporal Action Detection with Structured Segment Networks, which judges a candidate segment by whether its start and end transitions are complete rather than by its interior alone.
Unrooted trees are handled by fixing taxon 0 as the root pendant. This turns unrooted $n$-taxon trees bijectively into rooted $(n-1)$-taxon OLA vectors. It removes the rooted/unrooted mismatch that the file flags for Phylo2Vec and OLA on the DS1–DS8 benchmarks.
Why this is different from what exists
Two groups of prior work motivate the proposal. The first is sequential bijective tree models. ARTree attaches leaves sequentially with graph neural network and recurrent edge scoring, and it achieves full support at the cost of higher bound variance. MDTree shows that ARTree's fixed insertion order causes exposure bias. Its fix is to learn the order (using DNABERT2 embeddings and diffusion) and to insert in parallel. Neither scores an edge by contrasting sequence evidence on its two sides. MDTree changes which leaf goes next; we change how a branch is judged.
The second group is the vector encodings themselves. These are Phylo2Vec, OLA, and PhyloVAE, which learns a latent space over such vectors. We use them as the action space. Unlike PhyloVAE, we do posterior inference, not unsupervised embedding.
The video work supplies the method. SSN pools starting, course, and ending phases separately. DiGIT forces attention onto regions flanking a candidate. Contrast Based Evaluation Networks score inside-versus-outside contrast. compressed-video boundary detection measures divergence between windows before and after a frame. Those methods leave open how wide the flanking window should be. On a tree this problem has a principled answer: conditional likelihoods already weight each side's species by branch length under an evolutionary model. The "window" is therefore set by the substitution model, not by a hyperparameter.
Some work constrains the design. GradME, in Leaping through tree space, relaxes Phylo2Vec continuously but costs $O(n^5)$ and optimizes a distance criterion. We stay discrete and likelihood-based so that the per-step cost stays at the two-pass pruning cost. GeoPhy shows that full-support continuous relaxations need heavy control variates (leave-one-out plus learned baselines) to converge. That is evidence that variance, not expressiveness, is the bottleneck we target.
Research Program
We will build the sampler on top of ARTree's training pipeline. This means the same multi-sample lower bound with the VIMCO gradient estimator for topology, and the same branch-length model. The only change is the edge-scoring head, so that differences can be attributed to it.
The two-pass conditional likelihoods are recomputed incrementally after each insertion. Only the path from the new leaf toward the root changes. With site-pattern compression, the extra cost per step is one partial sweep over the alignment, in the same order as one likelihood evaluation. The comparison function $g$ pools over sites with a learned attention over site patterns. This is the tree analogue of DiGIT's adjacent-region attention, applied to sites rather than frames.
The future-context term $u_e$ is computed cheaply from pairwise distances between unplaced species and the leaves on each side. We will also test a likelihood-based version.
Beyond benchmark accuracy, we will analyze two things. The first is order sensitivity. The file notes that Phylo2Vec and OLA distances depend on leaf indexing. We will measure how much the learned posterior's KL and the bound variance change across random insertion orders. Our hypothesis is that two-sided contrast plus future context makes early decisions less order-dependent, which would cut the dispersion across orders. The second is where probability mass goes. We will count distinct topologies drawn, and the fraction of samples outside the 95% credible set of the MCMC posterior. This directly tests the claim about concentrating full-support samplers.
Baselines
The naive reference point is a sampler that draws each OLA entry uniformly from its allowed range. That is a uniform distribution over topologies, with the same branch-length model. It anchors how hard each dataset is and shows how much any learned topology model buys.
The strongest non-learned competitor, and the one most likely to embarrass the proposal, is a tempered greedy placement proposal. At each step it samples the edge with probability proportional to the exact single-leaf placement likelihood raised to a learned temperature. This is a sequential importance sampler in the spirit of Variational Combinatorial Sequential Monte Carlo. It uses the same conditional likelihoods we compute but contrasts nothing and looks at no future species. It will get the same alignment and the same number of likelihood evaluations. Its single temperature parameter will be tuned on the same validation bound. Beating it means lower KL to the MCMC posterior on at least six of eight datasets at an equal number of likelihood evaluations.
The strongest existing learned methods are ARTree and MDTree, rerun from their released settings on DS1–DS8 with identical training iterations, sample counts, and GPU budget. MDTree reports that it reduced runtime by "41.72% to 44.46%" relative to ARTree on DS1–DS8 while consistently achieving lower KL (MDTree). I found no reported per-dataset KL or marginal-likelihood numbers on Lacuna for ARTree or MDTree in the file. Both will therefore be reproduced, and success means lower KL than MDTree at no worse wall-clock time than ARTree.
We also include VBPI with bootstrap-restricted subsplit support (Variational Bayesian Phylogenetic Inference) to measure the cost of avoiding preselection. PhyloGFN serves as the reference for tail calibration. It reports a Pearson correlation of "~0.90 to 0.99" between sampling probability and posterior density across probability strata, versus "~0.46" for VBPI-GNN on low-probability trees (PhyloGFN). We will report the same stratified correlation, using its released code (zmy1116/phylogfn) where retraining is affordable.
Three ablations isolate the key ingredient, each keeping everything else fixed. The first, a one-sided scorer, uses only $g(a_e, x_i)$, the interior of the clade below the cut, mirroring the "pool inside the window only" detectors that the video literature found ambiguous. The second, a no-future scorer, drops $u_e$. The third, a node-feature model, concatenates per-taxon sequence embeddings into ARTree's graph network without any explicit cut construction.
Why not just…?
Why not just run MrBayes longer? MCMC remains the reference, and we use it as ground truth. But DS1–DS8 posteriors are obtained with one to ten billion iterations (PhyloGFN; A Variational Approach to Bayesian Phylogenetic Inference). Rugged landscapes trap local moves (Biological causes and impacts of rugged tree landscapes). The proposal does not compete on correctness in the limit. It competes on reaching a given KL with far fewer likelihood evaluations, and we will plot KL against evaluations for both.
Why not just sample edges by their placement likelihood, with no learning? This is the real threat. The contrast features are built from the same conditional likelihoods, so a well-tempered greedy proposal might capture most of the benefit. The tempered-placement baseline exists to settle this. The theoretical reason to expect a gap is that greedy placement is myopic. It places leaf $i$ ignoring leaves $i+1$ onward, which is exactly the exposure bias MDTree documents. The future-context term addresses this, and the greedy proposal cannot. If the learned scorer does not beat tempered placement, the correct conclusion is that the contribution is the likelihood features, not the network. We would then report a learning-free sampler as the result.
Why not just add sequence embeddings to ARTree's graph network? A graph network can in principle learn two-sided comparisons, because message passing sees both endpoints of an edge. But it must discover the bipartition structure from node features. The cut construction gives that structure directly, with model-weighted context on each side. The node-feature ablation tests this. If it matches the cut scorer, the explicit boundary formulation is unnecessary, and we will say so.
Why not just learn the insertion order as MDTree does? Ordering and edge scoring address different failure points, and they are compatible. We will therefore also run cut-contrast scoring under MDTree's learned order. If MDTree's ordering alone closes the gap to the cut scorer under a fixed order, our method's value reduces to its lower cost, since it needs no pretrained genomic language model.
Proposed Experiments
The main evaluation uses DS1–DS8 (27 to 64 taxa), with KL divergence to the long-run MrBayes posterior, marginal log-likelihood by importance sampling, and the variance of the lower bound across seeds as primary metrics.
The decisive check is the pairing of three comparisons: against tempered placement at matched likelihood evaluations, against the one-sided ablation, and against the no-future ablation. The proposal stands only if the full scorer beats all three. The second decisive check is order robustness. We train under 10 random insertion orders per dataset and compare the spread of KL across orders with ARTree's spread. A clearly smaller spread would support the claim that two-sided contrast reduces dependence on leaf indexing. Third, we report PhyloGFN-style correlation between sampling probability and posterior density, stratified by posterior probability. This checks that lower variance does not come from dropping the tails.
For scale, we will run on the larger alignments used by A Variational Approach to Bayesian Phylogenetic Inference (influenza, dengue, and hepatitis C at 25 to 100 taxa) and report wall-clock time per effective sample. Here the incremental conditional-likelihood update must stay roughly linear in the number of taxa per step for the method to be practical. We will report this cost honestly against MDTree's reported runtime savings.
References
- Variational Combinatorial Sequential Monte Carlo for Bayesian Phylogenetics in Hyperbolic Space
- ARTree: A Deep Autoregressive Model for Phylogenetic Inference
- Variational Bayesian Phylogenetic Inference
- Vector Encoding of Phylogenetic Trees by Ordered Leaf Attachment
- Temporal Action Detection with Structured Segment Networks
- MDTree: A Masked Dynamic Autoregressive Model for Phylogenetic Inference
- Phylo2Vec: A vector representation of binary trees
- PhyloVAE: Unsupervised Learning of Phylogenetic Trees via Variational Autoencoders
- DiGIT: Multi-Dilated Gated Encoder and Central-Adjacent Region Integrated Decoder for Temporal Action Detection Transformer
- Weakly Supervised Temporal Action Localization Through Contrast Based Evaluation Networks
- End-to-End Compressed Video Representation Learning for Generic Event Boundary Detection
- Leaping through Tree Space: Continuous Phylogenetic Inference for Rooted and Unrooted Trees
- GeoPhy: Differentiable Phylogenetic Inference via Geometric Gradients of Tree Topologies
- PhyloGFN: Phylogenetic inference with generative flow networks
- A Variational Approach to Bayesian Phylogenetic Inference
- Biological causes and impacts of rugged tree landscapes in phylodynamic inference