MPS: Relaxation-Free Solving for Blind Vision–Language Matching at Scale

In blind vision–language matching, the goal is to recover the correspondence between the class representations of a vision encoder and those of a language encoder without access to a single paired example. The task is naturally posed as the minimization of the Gromov–Wasserstein distortion between the intra-modal distance kernels of the two modalities, an instance of the quadratic assignment problem. We treat this problem entirely within its combinatorial domain, so that the search never leaves the set of permutations and no relaxation, in the sense of losing tightness, is introduced at any stage. Reducing the fourth-order Lawler formulation to an equivalent Koopmans–Beckmann trace maximization removes the cost tensor whose size otherwise limits the problems that can be posed. Shifting the spectrum of each kernel then makes the objective convex, and its minorization–maximization analysis shows why a single search trajectory halts short of the optimum, while a closed-form identity for the entire exchange neighbourhood, obtained from a single matrix product, makes a population-based search affordable at scale. We prove monotone ascent, convergence of the objective sequence and finite termination of the iterates. On benchmarks extending well beyond the scales previously studied, where the dual approach no longer delivers its guarantee of optimality, our solver outperforms state-of-the-art and benchmark methods in distortion at every problem size, matches more classes correctly than the dual solver on average, and remains interruptible at any moment with a feasible matching in hand.