path: root/MATCHING_RESULTS.md

# 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.