- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies the lack of cross-query comparability of similarity scores in representation learning. Conventional objectives such as InfoNCE and per-query AP surrogates optimize ranking independently for each query and therefore do not ensure that scores from different queries can be interpreted using a shared decision threshold.
The paper proposes gSAP, which flattens the similarity and relevance matrices and computes a single Smooth-AP objective over all query-candidate pairs. This introduces cross-query comparisons and encourages globally comparable similarities. The authors additionally use negative dropping to remove low-similarity negatives and reduce the computational and memory requirements. The method is evaluated on supervised metric learning, cross-modal alignment across image, video, text, and audio, self-supervised learning, and retrieval tasks containing distractor queries.
Critical strengths
- The paper addresses a practically meaningful limitation of query-wise objectives. Good within-query ranking does not imply that similarity scores are comparable across queries. This issue is consequential for open-set recognition, copy detection, and retrieval systems that must operate using a single shared threshold.
- The evaluation directly targets the claimed benefit. In addition to reporting gAP, the paper evaluates shared-threshold F1, recall at 90% precision, and robustness to distractor queries. The broad experiments across several modalities and learning paradigms provide evidence that cross-query coupling is useful beyond a single task.
Critical weaknesses
- Limited novelty and incomplete baselines. gSAP is essentially Smooth-AP applied once to the flattened similarity matrix rather than separately per query; both the smoothing technique and gAP metric already exist. The paper also omits PNP (AAAI 2022) and simpler global separation objectives. Without such comparisons, it is unclear whether the gains require AP-specific weighting or merely cross-query positive-negative separation.
- Unclear complexity and scalability. A direct implementation compares P positive pairs against B 2 flattened scores, costing O ( P B 2 ) , or O ( B 3 ) for one-to-one cross-modal batches where P = B . Negative dropping reduces practical cost but does not justify the claimed quadratic complexity. The absence of runtime, throughput, and peak-memory comparisons further weakens the “scalable drop-in replacement” claim.
Questions for authors
- What are the exact time and space complexities of gSAP before and after negative dropping? Please report wall-clock training time, throughput, and peak memory relative to InfoNCE, SigLIP, and mSAP.
- Can the authors discuss PNP and evaluate either PNP or a globalized PNP variant under the same backbone, batch size, and tuning budget? This comparison would help determine whether the reported gains require AP precision weighting or primarily arise from global positive-negative separation.
- Training optimizes a gAP surrogate within randomly sampled batches, whereas evaluation computes gAP over much larger datasets. Since AP is nonlinear, batch-level gAP is not evidently an unbiased estimator of dataset-level gAP. How sensitive is the method to batch size, batch composition, positive-pair density, and sampling strategy?
9 comments
W1 / Q2: PNP, and global separation objectives; novelty (part 2)
Matched comparisons. We evaluate PNP-D$_s$ and PNP-D$_q$ in their original per-query form and in global variants that compare each positive against all negatives of the batch, using the same backbones, batch sizes and tuning budgets as gSAP. We also evaluate CES, providing an established alternative for learning cross-query separation.
Table R3.2. CLIP fine-tuning. Retrieval averaged over Flickr8k, Flickr30k and MS COCO, text-to-image (t$\rightarrow$i) and image-to-text (i$\rightarrow$t). ZS-4: zero-shot top-1 averaged over ImageNet-1k (IN-1k) and ImageNet-V2/-R/-Sketch (ZS-4). Same setting as Table 1. PNP-D$_q$ uses , its global version .
| method | scope | retrieval / gAP | retrieval / mAP t$\rightarrow$i | retrieval / mAP i$\rightarrow$t | zero-shot top-1 / IN-1k | zero-shot top-1 / ZS-4 |
|---|---|---|---|---|---|---|
| SigLIP | threshold | 40.4 | 66.5 | 58.6 | 61.3 | 56.9 |
| PNP-D$_s$ | per-query | 37.4 | 65.2 | 57.3 | 60.2 | 55.6 |
| PNP-D$_q$ | per-query | 36.2 | 64.8 | 57.2 | 58.9 | 54.4 |
| mSAP | per-query | 37.4 | 65.5 | 57.7 | 60.0 | 55.3 |
| CES | global | 38.2 | 64.7 | 57.9 | 58.7 | 54.1 |
| PNP-D$_s$ | global | 41.1 | 66.4 | 59.6 | 60.2 | 55.9 |
| PNP-D$_q$ | global | 33.8 | 61.6 | 54.4 | 52.3 | 49.1 |
| gSAP | global | 42.1 | 67.1 | 59.7 | 61.8 | 57.3 |
Table R3.3. Metric learning. Recall@1 (R@1), mAP and gAP on two datasets, mean over three seeds (one seed for global PNP-D$_q$). Same setting as Table 5. PNP-D$_q$ uses , its global version .
| method | scope | SOP / R@1 | SOP / mAP | SOP / gAP | iNaturalist / R@1 | iNaturalist / mAP | iNaturalist / gAP |
|---|---|---|---|---|---|---|---|
| Contrastive | threshold | 85.3 | 68.4 | 53.7 | 80.6 | 42.1 | 28.0 |
| SigLIP | threshold | 86.5 | 72.6 | 57.8 | 78.3 | 41.2 | 26.0 |
| PNP-D$_s$ | per-query | 86.1 | 71.7 | 55.8 | 80.6 | 45.1 | 26.5 |
| PNP-D$_q$ | per-query | 87.0 | 73.1 | 57.9 | 81.0 | 45.0 | 28.2 |
| mSAP | per-query | 86.9 | 72.9 | 57.0 | 81.3 | 45.4 | 27.8 |
| CES | global | 81.8 | 65.9 | 52.3 | 80.0 | 43.0 | 28.7 |
| PNP-D$_s$ | global | 86.9 | 72.9 | 58.7 | 80.5 | 43.9 | 29.8 |
| PNP-D$_q$ | global | 80.2 | 59.6 | 45.3 | 75.0 | 33.6 | 18.8 |
| gSAP | global | 86.8 | 72.9 | 58.9 | 81.5 | 45.5 | 31.6 |
We have the following observations:
(i) Global comparisons bring substantial gains. Making mSAP or PNP-D$_s$ global improves gAP in every setting. The benefit therefore extends beyond AP-specific weighting.
(ii) One threshold is not enough. SigLIP, which separates all pairs against one learned threshold, stays below gSAP and global PNP-D$_s$ on gAP in every setting.
(iii) The choice of global objective matters. CES also compares across queries, but does not perform competitively. gSAP outperforms CES on all comparisons, showing that global scope alone does not explain the performance differences.
(iv) gSAP gives the strongest overall results. Global PNP-D$_s$ comes closest in gAP, but gSAP additionally improves CLIP zero-shot accuracy and iNaturalist.
(v) The AP precision weighting matters. At , global PNP-D$_q$ is gSAP with fixed to 1. It underperforms in every setting and on every metric.
Novelty. Neither gAP, sigmoid smoothing nor cross-query comparisons are new. Our contribution is gSAP: a smooth objective that optimizes AP over all query–candidate pairs, weighting errors through their effect on global precision. We analyze its cross-query consistency and low-temperature optimization, and demonstrate it as the main loss across supervised, cross-modal and self-supervised learning. The new comparisons separate the benefits of global scope from those of the particular objective.
Revision. We will discuss PNP and CES in Section 2, and add the common formulation and matched comparisons to Section 4.
W2 / Q1: complexity and scalability (part 1)
Complexity. We thank the reviewer for the careful count. For positive pairs among similarities, the exact implementation takes time and unchunked memory, where for cross-modal batches and for unimodal batches. Thus, the cost is cubic in when , or with fixed images per class. We will correct Section 3.4 and the conclusion.
Dropping a fraction of the negatives retains similarities. The comparison cost becomes in time and memory, plus the cost of selecting the hardest negatives; storing the similarity matrix still requires memory. For fixed , dropping reduces the practical cost but does not change the cubic asymptotic complexity.
Existing implementation. Our original implementation already used chunking and splitting, although these were not described in the paper. Chunking processes positives at a time and recomputes their intermediate values during the backward pass, reducing the comparison workspace to . Splitting assigns different positives to different GPUs, each ranking its share against the full batch's similarities, avoiding redundant loss computation across GPUs. Both preserve the loss and gradient.
Faster algorithm (new). The reviewers' questions motivated us to develop a new windowed implementation that avoids evaluating every comparison. It evaluates sigmoids only within a window around each positive and sums the numerically saturated contributions outside it in closed form, with truncation error far below single-precision rounding. Beyond gSAP, the same windowed computation applies to other ranking losses based on sigmoid comparisons, such as mSAP. We will describe the algorithm and release its implementation. Table R3.4 summarizes the implementation variants.
Table R3.4. Time and memory of the loss. For positive pairs among the similarities of a batch, not counting the computation of the similarities (; same for every method). is the share of negatives dropped, the number of positives per chunk, and the number of GPUs among which the positives are split, with the time and memory per GPU. is the mean number of similarities that the windowed algorithm compares exactly with a positive.
| method | time | memory |
|---|---|---|
| mSAP | ||
| InfoNCE, SigLIP | ||
| gSAP, exact | ||
| gSAP, negative dropping () | ||
| gSAP, chunking () | ||
| gSAP, splitting () | ||
| gSAP, windowed |
W1 / Q2: PNP, and global separation objectives (part 1)
Note: Following the ICLR guidelines, we keep our responses concise. We welcome follow-up questions and are happy to provide further details during the discussion. We have updated the PDF to include figures that cannot be displayed in OpenReview. We will fully revise the manuscript at the end of the discussion period.
PNP, CES, and a common formulation. We thank the reviewer for suggesting PNP (Li et al., 2022). Together with Reviewer mV9x's question about the relationship between losses, this motivated a common formulation that includes PNP, its global variants, and the existing global objective Cross-Example Softmax (CES; Veit and Wilber, 2020). The formulation distinguishes the comparison scope, kernel, positive-rank term and aggregation (Table R3.1).
Table R3.1. A common template for losses. For a positive pair p, Rp+ counts p and the positives scored above it, and Rp− the negatives scored above it, each through the kernel and within the list of p, its row for per-query losses and the whole batch for global ones. ℓ is applied to xp=Rp+/(Rp++Rp−) and averaged over the positives p; “no” in the R+ column means Rp+=1.