acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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

Primary area:
optimization
Keywords:
combinatorial optimization, cycle consistency, multi-image matching, partial permutations, permutation synchronization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_YEsWOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper tackles permutation synchronization. CAPS is first proposed as a solver for the problem in the combinatorial form. CAPS can be solved exactly and without rounding, and each update increase the objective monotonically. CAPS is then unrolled into CLAPS with learned parameters, that learns to solve the problem in a “relaxation-free manner”. Results are reported on SPair-71k and Willow Object datasets.

Critical strengths

The mathematics is tied to a valid observation, and it is nice that each CAPS update solves a well-defined optimization problem.

The empirical improvement is quite decent.

Critical weaknesses

The relationship between the proposed method and other works in the literature is not very comprehensively discussed. It is unclear what exactly is the new technique in the core optimization algorithm. For instance, the math seems quite similar to the formulations in the works below, and more clarification of the differences would be nice:

Initialization and Coordinate Optimization for Multi-way Matching. AISTATS 2017

Towards Optimizing Large-Scale Multi-Graph Matching in Bioimaging, CVPR 2025.

Further investigations and ablations should be done to dive deeper into why CLAPS works so well. One particular issue is that there are not many baseline results with CAPS.

More experiments and baseline comparisons against other works in general would be good.

Questions for authors

How does CAPS differ mathematically from Tang and Jebara’s exact coordinate-assignment algorithm and from the exact-LAP synchronization variant of Kahl et al. 2024?

Which component accounts for CLAPS’s gains over CAPS (shown in Table S1)? E.g., learned cycle-based weights, learned update parameters, or match rejection? It would also be good to compare against some more CAPS baselines.

Despite the differences, it would still be nice to see some empirical comparisons with MatchEig, SuperGlue and LightGlue, as they all tackle similar problems.

Reviewer_atr9OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper leverages cycle consistency across multi-image matches to improve matching accuracy. Interestingly, it still achieves strong results even from a poor initialization, which relies on the close connection between cycle consistency and matching exactness. Its key feature is that it is relaxation-free. Once all other objects are fixed, each object’s subproblem becomes exactly affine, so every update is an exact linear assignment problem. CAPS is then unrolled into a lightweight learned model, CLAPS, which keeps every assignment exact, learns a per-edge trust score, and can leave outlier keypoints unmatched.

Critical strengths
  1. Clean methodological route: no relaxation and no rounding. The method stays in the space of partial permutation matrices throughout, and every update is an exact linear assignment problem, avoiding the loss of tightness and inconsistency caused by “continuous relaxation + projection/rounding.”

  2. A simple but effective core observation. Once all other objects are fixed, the subproblem for a single object becomes exactly affine, so it can be reduced to an exact LAP. The observation is not complicated, but it turns the combinatorial problem into a precisely computable step.

  3. Theoretical guarantees that match the algorithmic form. The paper provides monotone ascent, finite termination, block-wise optimality, and complexity analysis. Although the guarantee is block-wise rather than global optimality, this is reasonable for an NP-hard problem.

  4. A well-integrated combination of CAPS and CLAPS. CLAPS is an unrolled version of CAPS, and its forward pass still keeps every assignment exact; CAPS is a special case of CLAPS, so training starts from the exact solver. The model is lightweight and learnable, learning only per-layer constants and a per-edge trust score, while the opt-out mechanism allows it to reject outlier keypoints and directly addresses the partial matching setting.

Critical weaknesses
  1. Limited novelty relative to existing components. Alternating optimization, linear assignment, unrolled networks, straight-through gradients, and edge-wise trust functions are all well established. The main novelty is the observation that fixing all other objects makes each per-object subproblem exactly affine, combined with a relaxation-free exact-LAP update and lightweight learning. This is clean and useful, but the overall innovation is incremental rather than foundational.

  2. Empirical evaluation is somewhat limited, and the contribution of learning is unclear. The experiments are conducted on relatively small standard benchmarks, and the gains are moderate, mainly in precision. Since CAPS is already competitive with the strongest baselines and CLAPS adds only a small improvement with very few learned parameters, it is unclear whether the learned component is essential or whether similar gains could be obtained by careful manual tuning.

  3. The comparison protocol may raise fairness concerns. All baselines are passed through the same exact block LAP rounding, and FCC is handled specially, while several methods are excluded on cycle-consistency grounds. Although these choices are explained, they narrow the comparison and may be perceived as favoring the proposed method; additional justification or ablations would strengthen the claims.

  4. The theoretical analysis is correct but relatively shallow. The monotone ascent, finite termination, block-wise optimality, and complexity results are valid and appropriately matched to the algorithm, but they are fairly standard and stop at block-wise optimality. There is no convergence-rate analysis, no deeper characterization of local optimality, and no further theoretical exploration of the relationship between cycle consistency and matching exactness.

Questions for authors

See weaknesses

Reviewer_4zowOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper CAPS a solver for permutation synchronization. The problem of permutation synchronization arrises from the problem where a collection of feature points on multiple objects shall be matched between multiple objects. There is a universe of points, which are partly represented at each object. Each matching of partial points is represented by a partial permutation matrix. The problem can be formulated as a quadratic optimization problem over a collection of partial permutation matrices. The problem is known to be NP-hard.

There are various relaxation techniques for addressing this problem. The partial permutation matrices can be relaxed to be stochastic matrices or orthogonal matrices. However, here in the method CLAPS, introduced by the authors, the approach is not to relax the matrices but keep them as partial permutation matrices. The approach is to use an alternating method where an LAP is solved in each iteration and the objective is shown to be monotonically increasing.

The authors then introduce CLAPS, a lightweight network that learns per-layer constants and a per-edge trust function end-to-end and rejects outliers. The performance of the introduced framework is compared to previously published methods.

Critical strengths

The main method presented in this paper is easy to understand and is presented in a clear manner. A key strength is that it is a method that preserves the so-called cycle-consistency and is relaxation free. There is no need for rounding or projection onto the set of partial permutation matrices. Although the presented idea of alternating optimization by solving LAPs is not conceptually new, the presented framework is conceptually clean and has claimed low computational complexity.

Critical weaknesses

The proposed method is not really novel. In some sense there is a block-coordinate ascent-like procedure where individual blocks are updated by solving an LAP. This is in spirit similar to power methods or generalizations thereof such as orthogonal iterations, where orthogonal matrices instead of unit vectors are optimized for in a sequential manner.

There is also a relation to Bernard et al., "HiPPI: Higher-order Projected Power Iterations for Scalable Multi-Matching" (ICCV 2019), where a more general fourth-order objective was considered, but where LAPs were solved in each iteration for permutations. The idea is not really new. One can see this as a form of projected gradient ascent and the concept can be generalized to any compact set (not necessarily partial permutation matrices.

The convergence guarantees follow naturally for this type of objectives (quadratic form maximization over a compact set, where the W-matrix is PD).

For evaluation, the reviewer had some difficulties to see how much the performance increase was due to the CLAPS or CAPS. In essence how significant was CLAPS. The performance increase in comparison to comparison methods published a decade ago was minor. Willow: Best baseline: 62.7%, CLAPS: 63.9%. SPair-71k: Best baseline: 39.1%, CLAPS: 40.0%.

Questions for authors

Could the authors clarify what comprises the fundamental algorithmic novelty of CAPS compared to established methods, particularly HiPPI? Furthermore, the stated convergence guarantees appear to follow from standard properties of exact block-coordinate ascent on a compact. What is the novel theoretical contribution of the convergence analysis beyond these classical results?

It is not entirely clear how much of the reported performance improvement is due to the CAPS and how much is duet to the learned components introduced in CLAPS. Could the authors provide a more explicit comparison between CAPS and CLAPS to quantify the benefit of the learned extension?

The improvements in F-score over the strongest baselines are relatively modest: from 62.7% to 63.9% on Willow and from 39.1% to 40.0% on SPair-71k. Given that some of the competing methods date back more than a decade, how do the authors assess the practical significance of these improvements?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.