A15-08: the pure-R samplers waste up to 40% of draws on identity moves and cannot reach part of the neighbourhood they document

[ms609]

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

Covers red-team candidates A15-O-07, -08, -09, -10, -24. The pure-R rearrangement samplers waste a large fraction of their draws on moves that change nothing, and two of them cannot reach part of the neighbourhood they claim.

Three of these were verified as worse than originally reported. The corrected figures are used below; where they differ from the finder's, both are shown, because the required fix differs from what the original numbers would suggest.

---

1. NNISwap() returns the input tree ~1 draw in 3 (A15-O-07)

R/NNI.R:118 — samplable <- child > nTips admits the edges from the root to its internal children. Swapping across such an edge only re-roots the tree, leaving the unrooted topology unchanged.

The finder said one such edge; there are two. A root with two internal children — the typical case — makes both root-adjacent edges samplable and both self-hitting. Measured by exhaustive test:

tips	self-hit rate	finder's figure
7	40.0%	19.8%
8	33.3%	16.8%

So the rate is 2/(nTips − 2), not 1/(nTips − 2). RootedNNISwap measures 0%.

This matters for the fix: excluding one root-adjacent edge — the natural reading of the original report — halves the problem and leaves the rest in place. Both must go.

NNISwap is BootstrapTree()'s default swapper and Ratchet()'s default BootstrapSwapper, so roughly a third of ratchet perturbation draws currently do nothing.

2. NNI(tree, edgeToBreak = -1) does not return the neighbourhood it documents (A15-O-08)

Documented at R/NNI.R:22-23 as "a complete list of all trees one step from the input tree". On BalancedTree(7), measured:

• 10 trees returned
• 7 distinct, 4 equal to the input
• only 6 genuine neighbours reachable, against a true NNI neighbourhood of 2(n−3) = 8

The finder reported 9 distinct / 2 duplicates / 8 neighbours — i.e. it read this as duplication. It is not: one internal edge's entire pair of true NNI neighbours is unreachable. The function returns a list that is both padded with copies of the input and missing real neighbours.

Same root-edge cause as §1. Note NNI() is the one function whose -1 branch actually runs — #125 covers -1 being broken or absent in the other five.

3. SPRSwap() returns the input tree ~10–12% of the time (A15-O-09)

R/SPR.R:209-212 computes brokenRootDaughters and then the line adding it to nearBrokenEdge is commented out, with the author's own note:

# Why did I do this?  Breaks SPR(BalancedTree(4), 1)

AllSPR() at :316-318 does apply the mask, so the sampler and the enumerator disagree about what counts as a move.

Deterministic sub-case, reproduced exactly: on Preorder(RootTree(BalancedTree(7), 1)), breaking edge 4 has exactly one candidate merge edge and it is the identity — so that draw is a guaranteed no-op. Monte Carlo under the same rooting: 11.95% (7 tips), 9.6% (8 tips).

TBRSwap, which applies the mask correctly (R/TBR.R:171-175), is much safer — though its exact rate is rooting-sensitive (0% tip-rooted, 1.7–2.65% under BalancedTree's own rooting), so the finder's single "3.6%" figure should not be quoted as a constant.

The commented-out line is a live question, not dead code: whatever broke SPR(BalancedTree(4), 1) needs diagnosing rather than working around, since the mask is demonstrably correct in AllSPR().

4. SPRSwap() cannot reach part of its neighbourhood (A15-O-10)

R/SPR.R:180-182 always prunes the child side of the sampled edge, and .NonDuplicateRoot() (:42-54) disables the second root edge. The cherry formed by the root's tip and the root's grandchild-tip therefore can never be pruned.

Measured against independent ground truth — exact agreement with the finder here:

tips	SPRSwap reach	TBRSwap reach
7	54/56 (missing 2)	64/64
8	86/90 (missing 4)	106/106

The gap is specific to SPR and grows with tree depth.

5. Two-stage sampling is far from uniform (A15-O-24)

R/SPR.R:180-182+:234-236 and R/TBR.R:126-127+:177-184 sample edgeToBreak uniformly, then mergeEdge uniformly within it — over-weighting prunes that have few regraft sites. Measured per-neighbour visit counts on an 8-tip tree over 20,000 draws: 111–883 (SPR) and 46–777 (TBR), a 4–17× spread against a uniform expectation of ~190–220. Well beyond Monte Carlo noise.

Not proposed as a bug. This is conventional two-stage sampling, common in rearrangement code, and both the finder and the verifier agree it is defensible. It is recorded here because it is undocumented, and because it compounds §3: the over-weighted branch is often the one whose only candidate is the identity.

---

Why this cluster matters more than the individual rates

Each no-op draw is not merely a wasted iteration. R/tree_rearrangement.R:77-78 scores the unchanged tree as equal to the current best, which increments hits — so no-op moves consume the maxHits budget that terminates the search. A search can therefore stop having "hit the best score maxHits times" while having performed almost no real rearrangement. That accounting defect is filed at #131 §6; fixing either alone leaves the symptom, so they should be fixed together.

Verification

All five confirmed REAL against commit 826d332b0 by an independent verifier that built its own graph-surgery neighbourhood enumerator and validated it exactly against 2(n−3) for NNI and 2(n−3)(2n−7) for SPR, across n = 5–10 and several tree shapes, before using it as ground truth. It found and fixed a canonicalisation bug in its own harness along the way (tied n/2 | n/2 splits need lexicographic, not size-based, tie-breaking) — worth knowing for anyone rebuilding it. Functions were sourced live from the worktree rather than from the installed package. R 4.7.0-dev.

Found by /red-team area 15, 2026-08-05, opus (Opus 5). A sonnet pass over these same files earlier the same day fuzzed these samplers 600 times and confirmed only that the topologies they produce are valid — it never asked whether they cover the neighbourhood.