acceptodds
Under review as a conference paper at ICLR 2027

Conformal Prediction Sets for Permutations as Bipartite Matching Graphs

Abstract

Permutation prediction sets may contain factorially many complete assignments, making explicit enumeration unusable even when statistical calibration is straightforward. We study how to represent such sets exactly while preserving the one-to-one constraint. A bottleneck score assigns a permutation the nonconformity of its worst selected edge; at every threshold, the accepted permutations then coincide exactly with the perfect matchings of a bipartite graph of admissible edges. The graph uses at most edges and supports membership, feasibility, representative-assignment, feasible-partner, and localization queries without enumerating its perfect matchings. Split conformal calibration selects the graph threshold and gives finite-sample marginal coverage of the complete assignment under exchangeability. We characterize the scope of this representation: every threshold set of a permutation score is exactly graph-representable if and only if the score has a bottleneck form. Across synthetic, sorting, and frozen pretrained keypoint-matching experiments, the method achieves near-nominal coverage and exposes localized and global ambiguity. In sorting, roughly 149 edges represent a median accepted permutations.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Conformal prediction, bipartite matching, permutation prediction, structured uncertainty, combinatorial prediction sets

Reviews

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

This paper studies the problem of finding a set-valued predictor that, with high probability, contains the ground truth for the matching problem. The authors connect the matching problem with conformal prediction and provide graph representations. The authors further propose a definition of the bottleneck score, which characterizes a permutation by the nonconformity of its worst-selected edge.

Critical strengths

The paper proposes a novel problem and introduces interesting notations that characterize it.

Critical weaknesses

There are several issues I have with this paper. The main issue is regarding a lack of clarity on why the problem is interesting and what the paper is trying to achieve:

  1. It is not clear how the problem setting is used in its applications and why this problem setting is interesting or studied previously. How the paper connects to conformal prediction in previous settings, and why conformal prediction is needed in this setting, are not very clear.
  2. The problem setting and the terms used are not properly defined in the experiment section. It is hard to understand why the bottleneck score is important and how graph representability is a useful property.
Questions for authors

Mentioned in the weakness.

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

This paper studies how to represent conformal prediction sets for permutation-valued outputs, i.e., one-to-one matchings. The authors propose that when the nonconformity score of a complete permutation takes a bottleneck form—the score of its worst selected edge—the accepted permutation set at any threshold coincides exactly with the set of perfect matchings of a bipartite graph of admissible edges. The graph contains at most n2n^2 edges yet can exactly represent factorially many complete assignments, and it supports membership, feasibility, representative-assignment, feasible-partner, and connected-component localization queries. The authors further prove that every threshold set of a permutation score is exactly graph-representable if and only if the score has a bottleneck form, and they use split conformal calibration to select the threshold with finite-sample marginal coverage of the complete assignment. Experiments cover synthetic matching, controlled sorting, SPair-71k, WillowObject, and PascalVOC.

Critical strengths
  1. Exact implicit representation with at most n2n^2 edges.
    The paper shows that, for a bottleneck score, every thresholded permutation set coincides exactly with the set of perfect matchings of a bipartite graph of admissible edges. This preserves the one-to-one constraint exactly while representing factorially many complete assignments without enumerating them.

  2. A sharp theoretical characterization of when exact graph representation is possible.
    Theorem 1 proves that every threshold set of a permutation score is exactly graph-representable if and only if the score has a bottleneck form. This gives a clean expressivity boundary and explains why max-aggregation is not arbitrary but necessary for exact edge-based representation.

  3. Matching-native queries plus valid split-conformal coverage, with good scalability.
    Once calibrated, the graph supports membership, feasibility, representative assignment, feasible-partner, and connected-component localization queries without enumerating perfect matchings. Split conformal calibration gives finite-sample marginal coverage of the complete assignment, and the graph remains practical at large nn, representing trillions of accepted permutations with roughly one hundred edges in the sorting experiment.

Critical weaknesses
  1. Only marginal coverage, not conditional coverage.
    The conformal guarantee holds on average over the calibration and test distributions, but it does not guarantee coverage conditional on problem size nn, difficulty, category, or a specific input. The paper itself shows that pooled calibration can undercover some size groups, and size-aware calibration can become uninformative when calibration groups are small.

  2. The bottleneck score is conservative, and the graph representation is not universally compact.
    Because a permutation is scored by its worst selected edge, one poor true edge can inflate the threshold and retain many unnecessary edges. On SPair-71k, for example, the graph has a median of about 325 edges, while an additive-regret explicit list has a median of only 2 complete assignments. The graph’s advantage is strongest when local ambiguity produces a huge number of complete assignments, not in general.

  3. The empirical scope is narrow and does not fully test realistic matching settings.
    The main real-data experiment uses SPair-71k with n∈[3,20]n \in [3,20], an intersection filter that removes unmatched keypoints and outliers, and a single frozen COMMON checkpoint. The method is therefore not well validated for partial matching with outliers, larger-scale real tasks, multiple matchers, matcher updates, or distribution shift.

Questions for authors

See Weaknesses

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

This paper proposes an exact graph representation of conformal prediction sets for permutations. Using a bottleneck nonconformity score, the accepted permutations are precisely the perfect matchings of a thresholded bipartite graph. Split conformal calibration provides finite-sample marginal coverage of the complete assignment under exchangeability. The paper also establishes that bottleneck scores are necessary and sufficient for every threshold set to admit such a representation. Experiments evaluate coverage, representation size, query efficiency, and localization on synthetic data, controlled sorting, and pretrained keypoint matching.

Critical strengths
  • The paper addresses a relevant problem in structured uncertainty quantification: a prediction set may be statistically valid but impractical to enumerate or query. The proposed representation preserves the one-to-one constraint and supports useful operations, including identifying partners that extend to a complete accepted assignment.

  • Theorem 1 provides a clear characterization of the score family compatible with exact graph representation at every threshold. This strengthens the methodological motivation beyond simply choosing a computationally convenient score. The proof appears sound.

  • The experiments provide convincing examples of the representational benefit. Table 3 reports approximately 79 edges on average and a median set cardinality of nearly eight million assignments, while retaining small local matching sets. Table 2 demonstrates practical query costs at larger problem sizes. The paper also appropriately distinguishes representation size from set cardinality and acknowledges cases where adaptive mass or short explicit lists are preferable.

Critical weaknesses

My main concern is that the tradeoff against an implicitly represented additive prediction set is not yet sufficiently established. An additive-regret set can be represented exactly by its cost matrix and a total-cost cutoff—the optimal assignment cost plus the calibrated regret threshold—without enumerating the accepted assignments. For a simple four-item sorting example, suppose the cutoff is 0.7. To check whether item A can occupy position 2, fix that assignment, with cost 0.2, and solve the minimum-cost matching of the remaining three items to positions 1, 3, and 4. If the remaining minimum cost is 0.4, the total is 0.6, so there exists an accepted assignment containing that edge. This query is exact and can be solved in polynomial time without enumeration.

Repeated constrained assignment solves may be substantially more expensive than the graph-based support algorithm, so this alternative does not eliminate the computational motivation for the proposed method. Indeed, Table 9 already shows faster support extraction for the graph on SPair: 0.244 ms versus 1.147 ms for additive regret using constrained assignment solves. However, the construction and storage comparisons focus on explicit lists, and the relative sizes of the feasible-partner sets at comparable coverage remain unclear.

Questions for authors

Q1:Could the authors extend Table 5 to include an implicit additive-regret representation, reporting storage in comparable units, construction time without list materialization, and all-partner query time on the same SPair and sorting instances?

Q2:At comparable coverage, how do the graph and additive-regret predictors compare in feasible-partner set sizes? In which settings does the graph provide a more favorable tradeoff between partner-set size and computational efficiency?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.