A15-06: TreeSearch()'s default swapper holds the root fixed, confining a mid-rooted start to ~5% of tree space (needs a design decision)

[ms609]

Severity: sev:high · Area: 15 (Legacy pure-R search API)

Red-team candidate A15-O-04. This needs a decision from whoever owns the search semantics, not just a patch.

The claim

TreeSearch() defaults to EdgeSwapper = RootedTBRSwap (R/CustomSearch.R:206). The Rooted* swappers hold the root fixed — R/TBR.R:320 (selectableEdges <- !rootEdges) and :354 (subtreeEdges <- !rootEdges & subtreeWithRoot) confine both bisection and reconnection to one side of the root. TreeSearch() never re-roots its input, so the root of whatever tree the user supplies silently determines how much of tree space the search can reach.

Measurements

An independent verifier built its own neighbourhood enumerator (bisect every edge, suppress both cut nodes, reconnect at every edge pair, canonicalise by split set) and validated it against the closed forms before use: NNI 4, 6, 8, 10, 12 = 2(n−3) and SPR 12, 30, 56, 90, 132 = 2(n−3)(2n−7), for n = 5…9 on two tree shapes. Coverage from 20,000 random swapper calls each:

Start tree	TBRSwap	RootedTBRSwap	RootedSPRSwap
BalancedTree(8), native 4|4	106/106	24/106 = 22.6%	24/90 = 26.7%
BalancedTree(7), native 4|3	64/64	14/64 = 21.9%	14/56 = 25.0%
BalancedTree(8) rooted on t1	106/106	86/106 = 81.1%	78/90 = 86.7%
BalancedTree(7) rooted on t1	64/64	50/64 = 78.1%	48/56 = 85.7%

The mechanism is worse than a per-step penalty

Over 20,000 calls every Rooted* swapper produced exactly one distinct root bipartition — the root split is a hard invariant, not merely a bias. So the per-step coverage figure understates the damage: a 150,000-step accept-everything random walk under RootedTBRSwap from the 4|3-rooted BalancedTree(7) reached 45 of 945 unrooted topologies — precisely the 15×3 trees containing that split — against 945 for TBRSwap, and 945 from a tip-rooted start.

A mid-rooted starting tree confines the entire search to ~4.8% of tree space, permanently. No amount of iteration escapes it.

The loss is pure

Root-irrelevance holds for the shipped scorer: EdgeListScore() on Lobo returns 230 for the NJ rooting and for re-rootings on tips 1, 5 and 20. So nothing is bought by holding the root fixed here — the reachability is simply given up.

RootedTBRSwap retaining the root is documented and intentional (R/Ratchet.R:22-24) for root-sensitive custom scorers. The defect is making it TreeSearch()'s default, where the default scorer is root-invariant. Ratchet() defaults to unrooted swappers and is unaffected.

Correction to the original finding — how bad is this in practice?

The finder claimed "NJTree()/rtree()/read.tree() all yield mid-rooted trees". That is wrong for NJTree(), which ends RootTree(tree, names(dataset)[[1]]) — measured root bipartitions 1|47 (Lobo) and 1|11. So the package's own ?TreeSearch example sits in the benign 78–81% regime, and the realistic exposure is narrower than first stated.

Genuinely mid-rooted and therefore confined:

• ape::rtree(30) → 24|6
• read.tree("(((a,b),(c,d)),((e,f),(g,h)));") → 4|4
• BalancedTree(20) → 10|10

RandomTree gives 1|2|45 and PectinateTree(20) gives 1|19, both benign.

So: users who build a start tree with this package's own helpers are mostly fine; users who read a tree from a file, or use ape::rtree(), can silently lose 95% of tree space. That is still a serious and entirely invisible failure mode, but it is not the universal one originally described.

The decision required

Three coherent resolutions, and someone who owns search semantics should pick:

1. Change the default to TBRSwap — matches Ratchet(), and the default scorer is root-invariant anyway.
2. Root on a tip inside TreeSearch() before searching, restoring the 78–81% regime for every input.
3. Document it plainly — state on the help page that with a mid-rooted starting tree the default explores under a quarter of the neighbourhood and cannot leave the trees containing the root split.

(1) and (2) are not equivalent: (2) preserves the Rooted* behaviour for users who chose it deliberately, while (1) changes what "default" means for root-sensitive custom scorers.

Two smaller gaps found by the same harness

Not in the original finding, both minor and worth folding into whichever fix lands:

• NNISwap/RootedNNISwap reach only 8/10 and 6/8 NNI neighbours from a mid-rooted start.
• SPRSwap (unrooted) reaches 86/90 from a tip-rooted start.

Verification

Confirmed REAL by an independent peer-tier verifier against commit 826d332b0, using its own enumerator validated against both closed forms, not the finder's harness. It independently reproduced 24/106, 24/90, 50/64 and 86/106, added the root-bipartition-invariance result and the 45/945 random-walk bound, verified EdgeListScore's root-invariance, and corrected the NJTree() claim.

Found by /red-team area 15, 2026-08-05, opus (Opus 5). Not found by a sonnet pass over the same files earlier the same day — that pass fuzzed these same samplers 600 times and checked only that the topologies produced were valid, never whether they covered the neighbourhood.