From 4f7ee05cc3b072478062e53645af016861c4b529 Mon Sep 17 00:00:00 2001 From: YurenHao0426 Date: Sat, 1 Aug 2026 17:59:32 -0500 Subject: The failure is the optimiser, not the information: a 257x faster descent and a benchmark The gate settles which failure mode each field is in, and refutes the symmetry hypothesis I proposed. On the caption-omitted field the truth is a STRICT local minimum -- descent started at the truth does not move at all -- the anchor bound says the information is 99.7% intact, and our solver stops 0.44 above it at 4.9% accuracy. That is a pure optimiser failure. Natural data is the opposite: descent from the truth falls a further 0.167, so the truth is not even locally optimal, which is the information-deficit signature the 0.291 bound predicted. Steepest descent was brute-forcing all 32,640 candidate permutations through the full energy every step, including a batched cube trace with the triangle term active -- 203 seconds per descent, which is why the gates were hopeless. The pairwise term needs one matrix product for the whole table: swapping p,q changes the alignment sum by 2(C_pq + C_qp - C_pp - C_qq + 2 A_pq B_pq) with C = A @ B. Verified against brute force to 1e-9 before use, and the fast descent reaches the same optimum. 203s -> 0.79s. Adds a matching benchmark with known-reachable answers and the solver families never tried on these fields: Gromov-Wasserstein, entropic GW with an annealed regulariser, BAPG. Co-Authored-By: Claude --- worldalign/synth_fast_gate.py | 51 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 51 insertions(+) (limited to 'worldalign/synth_fast_gate.py') diff --git a/worldalign/synth_fast_gate.py b/worldalign/synth_fast_gate.py index 54b6891..01fb18f 100644 --- a/worldalign/synth_fast_gate.py +++ b/worldalign/synth_fast_gate.py @@ -343,3 +343,54 @@ def main() -> None: if __name__ == "__main__": main() + + +def all_pair_swap_deltas( + permuted_text: torch.Tensor, visual: torch.Tensor +) -> torch.Tensor: + """Energy change of every transposition at once, for the pairwise term. + + The brute-force descent forms all N(N-1)/2 candidate permutations and + scores each through the full energy, which at 256 scenes means 32,640 + matrices per step and, with the triangle term active, a batched cube + trace over every one of them -- 203 seconds for a single descent. The + pairwise term does not need any of that. Writing S for the alignment sum + and C for `permuted_text @ visual`, swapping positions p and q changes S + by 2(C_pq + C_qp - C_pp - C_qq + 2 A_pq B_pq), so one matrix product + yields the entire table. + + Both fields must be symmetric with zero diagonal, which standardisation + already guarantees. Returns a dense [N, N] table of energy deltas; the + sign convention matches `ClosedFormEnergy.energy`, so negative is an + improvement. + """ + size = permuted_text.shape[-1] + product = permuted_text @ visual + diagonal = torch.diagonal(product) + gain = 2.0 * ( + product + product.T + - diagonal[:, None] - diagonal[None, :] + + 2.0 * permuted_text * visual + ) + return -2.0 * gain / (size * (size - 1)) + + +def fast_pair_descent( + text: torch.Tensor, visual: torch.Tensor, start: torch.Tensor, max_steps: int +) -> torch.Tensor: + """Steepest descent on the pairwise energy using the closed-form table.""" + size = len(visual) + current = start.clone() + triangle = torch.triu( + torch.ones(size, size, dtype=torch.bool, device=visual.device), diagonal=1 + ) + for _ in range(max_steps): + permuted = text[current[:, None], current[None, :]] + deltas = all_pair_swap_deltas(permuted, visual) + deltas = torch.where(triangle, deltas, torch.inf) + best = int(deltas.argmin()) + if float(deltas.view(-1)[best]) >= -1e-12: + break + p, q = best // size, best % size + current[[p, q]] = current[[q, p]] + return current -- cgit v1.2.3