CLAPS: Relaxation-Free Permutation Synchronization with Exact Per-Object Assignment

In permutation synchronization, the goal is to recover cycle-consistent correspondences among the keypoints of a collection of objects, such as images, from noisy pairwise matchings. In this work, we propose $\text{CAPS}$, a solver that keeps the problem in its original combinatorial form throughout, unlike methods that relax it into a continuous domain, losing tightness, and then round the solution back. We show that, once the assignments of all other objects are fixed, the objective is exactly affine in the assignment of the remaining object, because the feasibility constraints alone remove every interaction between its keypoints. Each update of CAPS is therefore a linear assignment problem with a totally unimodular constraint matrix, solved exactly and without rounding. We prove that CAPS increases the objective monotonically, terminates after finitely many passes at a block-wise optimal assignment, and costs time linear in the number of observed matches per pass. We further unroll CAPS into a lightweight network, $\text{CLAPS}$, that learns per-layer constants and a per-edge trust function end-to-end, which allows it to decline outliers, while every assignment step remains exact. On the SPair-71k and Willow Object benchmarks, CLAPS outperforms the state of the art in both precision and F-score.