Wagner retry-exhaustion returns a constraint-violating start that the `MaximizeParsimony()` search driver captures ungated (no verify-before-capture, asymmetric to fuse)

[ms609]

Severity: P3 (→P2 if reachable) · Area: 9,13 (Wagner/Constraint)

Location: src/ts_wagner.cpp:774, 811 + src/ts_driven.cpp:1005, 1013 (line numbers re-anchored to HEAD by tidy 2026-07-27, then the ts_driven.cpp pair re-anchored again :1004→:1005 / :1012→:1013 by the second tidy the same day after ec3ce46e; the row's prose below still quotes the older :745-754/:784-797/:929)

If all 100 retry attempts still violates_constraint_posthoc, biased_wagner_tree (:745-754) / random_wagner_tree (:784-797) return the last (violating) tree with no warning — unlike the per-taxon edge-exhaustion path, which warns (constraint_fallback, :571-576). Area-13 (2026-07-03) deepened this from a warning-parity gap to a conditional correctness gap on the MaximizeParsimony() search path (T-324's original framing was AdditionTree()-scoped): (1) the per-replicate pool capture at ts_driven.cpp:929 (pool.add_collapsed(rep_result.tree, …)) has NO constraint gate — asymmetric to the fuse capture 100 lines below (:1042-1058), which maps constraint nodes, imposes, and discards on residual violation (fused_ok). (2) A violating start is not repaired by constrained TBR (regraft_violates_constraint returns true for all moves once constraint_node[s]<0, ts_constraint.cpp:354-360 → tree freezes); nni_perturb_search's impose_constraint (ts_driven.cpp:412-419) can repair it only if nni_perturb_per>0 and the heuristic succeeds — otherwise the violating start survives to :929. CORRECTED 2026-08-04 (T-402 verification, opus): this sentence is over-optimistic — in the score-better-than-constrained regime nni_perturb can NEVER repair it. best_tree = tree snapshots the violating start at src/ts_nni_perturb.cpp:80 before any repair, and the repaired (legal, therefore necessarily worse-scoring) tree is then rejected at :120 by accept = tbr_result.best_score < best_score. The illegal tree's unfairly low score is an unbeatable baseline, so a verify-and-revert gate of the T-390/T-391 shape does not fix this class; the start must be repaired or rejected before any baseline is taken. See T-402, which shares this row's downstream half verbatim. (3) No downstream filter (confirmed): ts_rcpp.cpp (post-:1390) and MaximizeParsimony.R post-search (collapse-protection only, :1028-1034) never re-check constraint satisfaction → a violating tree is returned to the user unflagged. Severity: P3 on the proven inconsistency (missing gate + missing warning); escalates to P2 (silent wrong answer for a valid user constraint) IFF reachability is confirmed — a satisfiable user constraint whose violation survives all 100 independent reshuffles. The retry loop's existence proves pass-construction/fail-posthoc trees exist; the open bit is 100-reshuffle persistence. Recommend a Hamilton hard-but-satisfiable-constraint probe to settle reachability (not local — heavy compute). Fix (do NOT mis-patch): the :929 gate must use violates_constraint_posthoc(tree, *cd) for a user constraint (has_posthoc=true), NOT the fuse-style constraint_node[s]<0 check — a posthoc-only violation (all cn>=0 but fails full-Fitch) is exactly the case the posthoc DataSet exists for and would slip a constraint_node-based gate. Also emit the missing Rf_warning on retry-exhaustion in both Wagner paths (original T-324 ask). Only user constraints reach :929 with has_posthoc=true; auto-consensus auto_cd is has_posthoc=false and engages only when no user constraint (ts_driven.cpp:724), so it is a search heuristic, not a user-facing violation. Verified REAL by orchestrator source-trace at HEAD 4b833e7 (opus); reachability UNCONFIRMED. Sibling of T-329 (same constraint machinery — coordinate fixes). RE-ANCHORED AT HEAD (tidy, 2026-07-27): still open, defect unchanged, only the line numbers moved. The ungated per-replicate pool capture is now ts_driven.cpp:1004 (interrupted path) and :1012 (normal path) — note there are two pool.add_collapsed(rep_result.tree, …) call sites, not one, so a fix must gate both. The gated fuse capture it is asymmetric to is now :1132-1157 (fused_ok). The Wagner retry-exhaustion returns are ts_wagner.cpp:774 (biased) and :811 (random); the warning-emitting per-taxon fallback is :563/:588. T-329 (the sibling) has since been fixed and archived — its .PrepareConstraint four-gamete gate now rejects impossible constraints before the kernel, which retires the impossible-constraint subset of this finding; what remains is the satisfiable-constraint case, where 100 independent reshuffles all fail posthoc. ADJACENT EVIDENCE from the T-368 perf work (2026-07-28) — read the scope limit before using it. While building a byte-identity oracle for T-368, constrained AdditionTree() was observed returning constraint-violating trees for trivially satisfiable constraints (plain monophyly groups), deterministically, on the unmodified tip — 6 of 15 cases: 100 tips/9 groups of 6, and 150 tips/8 groups of 7, all 3 fixed sequences each; 60/5x4, 100/6x5 and 130/10x3 were clean. Failure correlates with clade size (gSize 6-7 fail, 3-5 pass), not clade count. This does NOT settle T-324's reachability question, and must not be recorded as if it had. T-324 is about the 100-reshuffle retry loop in biased_wagner_tree/random_wagner_tree; AdditionTree() calls ts::wagner_tree directly (ts_rcpp.cpp:1007), so no retry loop and no violates_constraint_posthoc check is involved on this path at all. What it does establish is the weaker, still-useful claim that satisfiable user constraints reaching the Wagner constructor can produce violating output — the ingredient T-324's reachability probe would need, minus the reshuffle persistence. Also note the per-taxon constraint_fallback warning is silent here: instrumentation showed zero steps with best_above < 0 across all 1575 insertion steps, so the edge-exhaustion guard never fires and the user is never told. Mechanism is hypothesis from correlation, not traced: the cn == tree.n_tip skip abandons a constraint whenever the LCA of already-added inside tips is the root, and larger clades keep the LCA at the root for more steps. Spawned as its own investigation task rather than fixed inline.

---

Migrated 2026-08-04 from dev/red-team/findings.md; pre-tracker ID T-324. References to T-324 in source comments, dev/red-team/log.md, commit messages and PR bodies mean this issue — see dev/red-team/migration-map.tsv. Cross-repo references use the fully-qualified form agent-issues/TreeSearch#<n>; a bare #n means this repo.

[ms609]

Claimed. Branch feature/constraint-holes, worktree inspiring-pare-11a433 (C:/Users/pjjg18/GitHub/worktrees/TreeSearch/inspiring-pare-11a433). Fixing #18, #1 and #19 together: #18 and #1 share the ungated pool-capture fix site verbatim, and #19 edits the same .PrepareConstraint return and src/ts_rcpp.cpp constraint unpacking.

[ms609]

Fix opened as #59 (feature/constraint-holes, base cpp-search). ubuntu-arm64 green; the windows job fails at dependency setup on the pre-existing MaxMin resolution problem that also reddens cpp-search itself.