From ef104fe4f07713bf11f266d2954b7446f176f8ae Mon Sep 17 00:00:00 2001 From: YurenHao0426 Date: Sat, 1 Aug 2026 19:32:58 -0500 Subject: Record the matching battery: fifteen solvers, one amplifier Adds MATCHING_RESULTS.md. Entropic GW annealed and PATH both reach 0.961 on the reference field, above the 0.958 the project's own pipeline reached after months, and neither had been run. GW reaches 0.881 on the rank-8 field where GRAMPA reaches 0.076 -- which retires the morning's rank-ladder conclusion, since that ladder was run entirely with GRAMPA and GRAMPA degrades on clustered eigenvalues. The hard instance yields to amplification rather than a better solver: descent multiplies a partial answer by about four, so the job is to feed it a start that is 10-20% correct rather than to replace it. Co-Authored-By: Claude --- MATCHING_RESULTS.md | 144 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 144 insertions(+) create mode 100644 MATCHING_RESULTS.md (limited to 'MATCHING_RESULTS.md') diff --git a/MATCHING_RESULTS.md b/MATCHING_RESULTS.md new file mode 100644 index 0000000..645393a --- /dev/null +++ b/MATCHING_RESULTS.md @@ -0,0 +1,144 @@ +# The search was the narrow part + +*2026-08-01. What the project had tried for matching was one family, and the +cost of that was measured rather than guessed.* + +**Result in one line.** On a field whose information is 99.7% intact, fifteen +solvers spanning spectral, Birkhoff, Gromov-Wasserstein and convex-concave +relaxations all return under 5%; the instance yields not to a sixteenth solver +but to amplification — a diverse pool of cheap descents, voted, rounded, and +fed back — because exact descent on that field multiplies a partial answer by +about four. + +## A benchmark with known-reachable answers + +Natural data is a bad place to test solvers: when everything fails there, no +one can tell a weak method from an impossible instance. The anchor bound fixes +that by pricing each field's information content separately, so a benchmark can +be built where the answer is known to be reachable. + +| Field | what it is | anchor bound | previous best blind | +|---|---|---|---| +| synth-full | the world that recovers | 0.99 | 0.958 | +| rank8 | same, truncated to rank 8 | 0.93 | 0.076 | +| omit-size | same, captions never state size | 0.997 | 0.044 | +| natural | Visual Genome | 0.29 | 0.000 | + +Natural data is kept in as a negative control: a method that scores there is +reporting a bug, not a result. None did. + +## Two solvers beat the pipeline we spent months on + +| Method | synth-full | rank8 | omit-size | +|---|---|---|---| +| Umeyama | 0.540 | 0.016 | 0.014 | +| GRAMPA + exact descent *(the pipeline)* | 0.884 | 0.076 | 0.044 | +| Gromov-Wasserstein | 0.397 | **0.881** | 0.022 | +| GW, 12 restarts | 0.397 | 0.881 | 0.022 | +| GW, KL loss | 0.089 | 0.251 | 0.000 | +| entropic GW, annealed | **0.961** | **0.887** | 0.034 | +| entropic GW, deep anneal | — | 0.013 | 0.034 | +| BAPG GW | 0.418 | 0.233 | 0.012 | +| semirelaxed GW | — | 0.044 | 0.013 | +| FAQ (Frank-Wolfe) | — | — | 0.021 | +| FAQ, 30 restarts | — | — | 0.021 | +| PATH convex-concave | **0.961** | 0.866 | 0.004 | +| moment ladder tr(M^k) | 0.112 | 0.214 | 0.012 | +| consensus vote, 65 descents | 0.932 | — | 0.127 | + +Two things fall out immediately. **Entropic GW with an annealed regulariser and +PATH both reach 0.961 on the reference field, above the 0.958 that the +project's own composed pipeline reached after months of tuning** — and neither +had ever been run. And on the rank-8 field, GW reaches 0.881 where GRAMPA +reaches 0.076. + +That second number retires a conclusion drawn earlier the same day. A +rank-truncation ladder had appeared to show that the width of the shared +spectrum governs recovery; the ladder was run entirely with GRAMPA, and GRAMPA +degrades on fields with clustered eigenvalues, which is exactly what truncation +produces. **The rank ladder was measuring a spectral solver's sensitivity, not +an information limit** — the fourth time in this project that a solver +limitation has been read as an intrinsic one, and the reason the standing rule +is now to check the anchor bound before concluding anything is impossible. + +More annealing is not better. Extending the entropic schedule from five steps +ending at 2e-3 to eleven ending at 1e-3 takes rank8 from 0.887 to 0.013 and +costs 29× the time: once the coupling sharpens into a near-deterministic +transport plan it locks, and stopping while it is still soft is what works. + +## The hard instance, and why it is hard + +Deleting one word class from the synthetic captions produces a field that +defeats everything. Its diagnosis is unusual and each part was measured. + +**The information is intact.** Anchor bound 0.997 — give the solver half the +correspondence and Hungarian assignment recovers essentially all of the rest. +Five percent of the correspondence, twelve pairs, is worth 62%. + +**The truth is a strict local minimum.** Descent started exactly at the truth +does not move at all, and every solver lands at an energy 0.44 above it against +E(truth) = 0.34. + +**Its basin is wide, not a needle.** Perturb the truth by *k* random +transpositions and descend: at k=16 it returns to the exact truth in 100% of +trials, at k=32 in 67%, and at k=128 it still reaches 0.90 accuracy. + +Those three look contradictory next to fifteen failures until the basin is +measured in the right coordinate. 128 random transpositions leave about 94 of +256 scenes in place, so "k=128 works" means "a start that is already 37% +correct works". Re-running the probe in accuracy rather than distance shows +what descent actually does: + +| start accuracy | 0.05 | 0.10 | 0.15 | 0.20 | 0.30 | 0.50 | +|---|---|---|---|---|---|---| +| after descent | 0.152 | 0.420 | 0.614 | 0.783 | 0.806 | 0.875 | + +**Descent is an amplifier with a gain near four, and no sharp threshold.** The +failure was never the local search and never the information. It was that +every initialiser — spectral, GW, Birkhoff, path-following — lands in the same +systematically wrong region and cannot clear the entry price. + +## Amplification + +If the field supplies an amplifier, the job is to feed it, not to replace it. +Run a diverse pool of cheap descents from random and spectral starts, let them +vote on pairings, round the vote matrix to a permutation by Hungarian +assignment, descend from that, and rebuild the pool by perturbing the result. +Each round hands the amplifier a better start than the last. + +Two details earn their place. **Rounding the vote matrix beats taking its +argmax** — 0.207 against 0.127 on the first round — because the argmax is not a +permutation and discards the assignment constraint. And ladders vary widely, so +several are run and the best is chosen **by energy, never by accuracy**, which +keeps the selection blind; on the first trial of the tuned run this picked +0.188 out of {0.094, 0.043, 0.188}, the best of the three. + +On the instance that defeated fifteen solvers, the ladder climbs 0.13 → 0.68 → +0.72 across rounds, against 0.044 for the best solver and 0.127 for voting +alone. + +One negative result on the design. Injecting 25% fresh random starts into each +rebuilt pool, intended to rescue a plateaued ladder, instead dilutes the vote +with descents that agree on nothing and drops the first trial to 0.188. The +same shape as the annealing result: the more conservative option was worse. + +## What this changes + +The register's search rows were closed on the strength of tempering +equilibrating and spectral methods stalling, both of which are now known to be +statements about two particular algorithms. They are reopened. More usefully, +the diagnosis generalises past this instance: **wherever the anchor bound is +high and blind recovery is low, the gap is amplification, and the question is +how to buy an initial 10–20% rather than how to build a better optimiser.** +That is the same statement the anchor curve makes from the other side, where +twelve correct pairs are worth the whole problem. + +Engineering note, because it gated everything above. `steepest_descent` was +forming all 32,640 candidate permutations each step and scoring them through +the full energy, including a batched cube trace when the third-order term was +active — 203 seconds per descent, which is why three earlier gate runs produced +no output in 50 to 89 minutes. The pairwise term needs one matrix product for +the whole table: with C = A @ B, swapping p and q changes the alignment sum by +2(C_pq + C_qp − C_pp − C_qq + 2 A_pq B_pq). Checked against brute force to 1e-9 +before use. **203 s → 0.79 s**, and every experiment in this document is +downstream of that. -- cgit v1.2.3