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.** Fifteen solvers spanning spectral, Birkhoff,
Gromov-Wasserstein and convex-concave relaxations return under 5% on the
caption-omitted field; every one of them is purely quadratic or purely
spectral, and adding a single permutation-invariant **node-level term** to the
objective reaches 0.837 in 1.4 seconds — which is the information-theoretic
ceiling, because that field has 51 exact automorphisms and no blind method can
exceed 0.836.

**Three numbers in the first draft of this document were artifacts of my own
code and are corrected below**: the anchor bound was inflated by a tie-break
(0.997 → 0.920), the truth is a plateau rather than a strict local minimum
(51 transpositions have exactly zero energy delta), and the "FAQ with 30
restarts" row never ran restarts at all. The corrections were found by an
adversarial review that was pointed at the artifacts, and each was reproduced
here before being accepted.

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

---

# Resolution: the missing term was unary

*Appended 2026-08-01 after an adversarial review of the artifacts.*

## The ceiling was never 1.0

The caption-omitted field was built by deleting one word class, and that makes
scenes which differed only in that class **exactly interchangeable in the text
field**. Not approximately: `T[s,s]` is bitwise identical to `T` for 51
transpositions `s`, so every objective of the form `f(V, P T P^T)` is invariant
under them at every order. Blind matching can pick at most one member per orbit.

| Field | automorphisms of T | ambiguous scenes | blind ceiling |
|---|---|---|---|
| noisy 0.35 | 0 | 0 | 1.000 |
| rank8 | 0 | 0 | 1.000 |
| synth-full | 7 | 14 | 0.973 |
| **omit-size** | **51** | **76** | **0.836** |
| omit-count | 145 | 106 | 0.719 |
| omit-colour | 381 | 210 | 0.402 |

Every accuracy in this project's synthetic benchmark was being divided by the
wrong denominator. It also explains the caption ladder's monotone collapse in a
way that has nothing to do with information: deleting a word class manufactures
automorphisms, and the ceiling falls with them.

## What the fifteen had in common

They are all purely quadratic or purely spectral. **None carries a node-level
term.** The instance flattens precisely the coarse second-order statistics that
family reads, while leaving scenes distinguishable in the shape of their own
similarity profiles — and a row-order statistic is not a spectral statistic.

Give each node eight moments of its own row of the field, z-score them jointly
across both node sets, and use the descriptor distance as a linear cost blended
with the quadratic term through Frank-Wolfe:

| Field | blind ceiling | fused unary+quadratic | energy gap to truth | previous best |
|---|---|---|---|---|
| omit-size | 0.836 | **0.837** | **+0.00e+00** | 0.044 |
| rank8 | 1.000 | 0.884 | −6.2e-03 | 0.088 |
| synth-full | 0.973 | 0.956 | −5.5e-04 | 0.961 |
| natural | — | 0.012 | −1.1e-01 | 0.027 |

1.4 seconds, nineteen times the previous best, and an energy gap of exactly
zero — it finds a configuration with the truth's energy, which given 51
automorphisms is all there is to find.

**The term must stay in the loop.** Using the descriptor only to seed a
pure-quadratic descent scores 0.21, because the descent discards it immediately
and wanders back into the decoy region. Pinned through the Frank-Wolfe
iterations, the same descriptor scores 0.84. That distinction is the entire
result, and it is why amplification — which is also pure-quadratic — plateaued
at 0.508 no matter how large the pool grew.

Negative energy gaps on rank8, synth-full and natural say something different
and worth keeping: there the solver finds states **below** the truth, so what
remains is the objective, not the search. On natural data the gap is −0.113,
which is the same information deficit the 0.336 anchor bound reports.

## The corrected gate table

With the tie-break fixed, the bound no longer credits itself with resolving
exact twins by presentation order:

| Field | anchor bound (corrected) | blind recovery | gap |
|---|---|---|---|
| synth-full | 0.983 | 0.958 | +0.025 |
| omit-size | 0.920 | 0.837 | +0.083 |
| rank8 | 0.930 | 0.884 | +0.046 |
| natural | 0.336 | 0.000 | +0.336 |

All three synthetic instances are now solved to within 0.08 of their bounds.
**Visual Genome is the only field left with a real gap, and all of it sits in
the bound** — the representation, not the search. Its bound is unaffected by
the correction because natural data has no exact twins.

## What this cost and what it bought

Three published numbers were wrong because the code that produced them had
bugs that flattered it, and the fourth conclusion — "the truth is a strict
local minimum, so this is a pure optimiser failure" — was built on one of them.
The amplification work that followed was aimed at a target that was 0.16 lower
than believed and reached 0.508 of it by brute pool size, when 1.4 seconds of
the right objective reaches the ceiling. Amplification is not wrong; it is a
pure-quadratic method and inherits the blind spot.

The rule this adds to the standing gate: **before concluding that an instance
is hard, check whether the field has exact automorphisms.** It costs one sorted
row-hash per node and it bounds everything downstream.