acceptodds
Under review as a conference paper at ICLR 2027

Global Average Precision for Representation Learning

Abstract

Standard information retrieval metrics, such as mean Average Precision (mAP), assess performance one query at a time, based on how the similarities between a query and its positives compare against those with its negatives. The same holds for common representation learning losses, such as InfoNCE and per-query AP surrogates. None of them considers whether similarities are comparable across queries, which any system with a single decision threshold relies on. Global Average Precision (gAP) does, by ranking all query–candidate pairs in one list and computing a single AP. We introduce gSAP, a differentiable surrogate of gAP. It needs only a similarity matrix and a binary matrix marking the positive pairs, the same input as existing losses, so it is a drop-in replacement for them and agnostic to the encoder, the modality, and the source of supervision. Since it considers all possible pairwise comparisons in the batch jointly, it also remains trainable at low temperatures, a regime where per-query surrogates run out of gradient. Swapping it into established recipes improves supervised metric learning, cross-modal alignment, and self-supervised pretraining, where, to our knowledge, it is the first ranking loss to replace the community standard InfoNCE in the latter two. Its similarities are more consistent across queries, which drives the gains under a universal threshold. gSAP retrieves up to four times as many positive pairs as the strongest AP surrogate at the same precision, and it degrades the least when queries with no positives in the database are added. Beyond thresholding, models trained with gSAP also learn better representations, with higher transfer, NN and zero-shot classification accuracy.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
representation learning, global average precision, cross-modal learning, self-supervised learning, meatric learning

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_au2MOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. 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.
  2. 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.
  3. 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
AuthorsOpenReview ↗

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 pp, Rp+R^+_p counts pp and the positives scored above it, and Rp−R^-_p the negatives scored above it, each through the kernel and within the list of pp, its row for per-query losses and the whole batch for global ones. ℓ\ell is applied to xp=Rp+/(Rp++Rp−)x_p=R^+_p/(R^+_p+R^-_p) and averaged over the positives pp; “no” in the R+R^+ column means Rp+=1R^+_p=1.

LossScopeKernelR+R^+ℓ(x)\ell(x)
SigLIPthresholdlogistic––
Contrastivethresholdhinge––
InfoNCEper-queryexpno−log⁡x-\log x
PNP-D$_s$per-querysigmoidno−log⁡x-\log x
PNP-D$_q$per-querysigmoidno1−xα1-x^\alpha
mSAPper-querysigmoidyes1−x1-x
CESglobalexpno−log⁡x-\log x
PNP-D$_s$globalsigmoidno−log⁡x-\log x
PNP-D$_q$globalsigmoidno1−xα1-x^\alpha
gSAPglobalsigmoidyes1−x1-x
AuthorsOpenReview ↗

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 α=4\alpha=4, its global version α=1\alpha=1.

methodscoperetrieval / gAPretrieval / mAP t$\rightarrow$iretrieval / mAP i$\rightarrow$tzero-shot top-1 / IN-1kzero-shot top-1 / ZS-4
SigLIPthreshold40.466.558.661.356.9
PNP-D$_s$per-query37.465.257.360.255.6
PNP-D$_q$per-query36.264.857.258.954.4
mSAPper-query37.465.557.760.055.3
CESglobal38.264.757.958.754.1
PNP-D$_s$global41.166.459.660.255.9
PNP-D$_q$global33.861.654.452.349.1
gSAPglobal42.167.159.761.857.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 α=4\alpha=4, its global version α=1\alpha=1.

methodscopeSOP / R@1SOP / mAPSOP / gAPiNaturalist / R@1iNaturalist / mAPiNaturalist / gAP
Contrastivethreshold85.368.453.780.642.128.0
SigLIPthreshold86.572.657.878.341.226.0
PNP-D$_s$per-query86.171.755.880.645.126.5
PNP-D$_q$per-query87.073.157.981.045.028.2
mSAPper-query86.972.957.081.345.427.8
CESglobal81.865.952.380.043.028.7
PNP-D$_s$global86.972.958.780.543.929.8
PNP-D$_q$global80.259.645.375.033.618.8
gSAPglobal86.872.958.981.545.531.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 α=1\alpha=1, global PNP-D$_q$ is gSAP with Rp+R^+_p 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.

AuthorsOpenReview ↗

W2 / Q1: complexity and scalability (part 1)

Complexity. We thank the reviewer for the careful count. For KK positive pairs among MM similarities, the exact implementation takes O(KM)O(KM) time and unchunked memory, where M=B2M=B^2 for cross-modal batches and M=B(B−1)M=B(B-1) for unimodal batches. Thus, the cost is cubic in BB when K=BK=B, or K=B(ρ−1)K=B(\rho-1) with fixed ρ\rho images per class. We will correct Section 3.4 and the conclusion.

Dropping a fraction α\alpha of the negatives retains L=K+⌈(1−α)(M−K)⌉L=K+\lceil(1-\alpha)(M-K)\rceil similarities. The comparison cost becomes O(KL)O(KL) in time and memory, plus the cost of selecting the hardest negatives; storing the similarity matrix still requires O(M)O(M) memory. For fixed α<1\alpha<1, 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 cc positives at a time and recomputes their intermediate values during the backward pass, reducing the comparison workspace to O(cL)O(cL). 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 KK positive pairs among the B2B^2 similarities of a batch, not counting the computation of the similarities (O(B2d)O(B^2 d); same for every method). α\alpha is the share of negatives dropped, cc the number of positives per chunk, and GG the number of GPUs among which the positives are split, with the time and memory per GPU. wˉ\bar w is the mean number of similarities that the windowed algorithm compares exactly with a positive.

methodtimememory
mSAPO(KB)O(KB)O(KB)O(KB)
InfoNCE, SigLIPO(B2)O(B^2)O(B2)O(B^2)
gSAP, exactO(KB2)O(KB^2)O(KB2)O(KB^2)
gSAP, negative dropping (α\alpha)O(B2+K(K+(1−α)B2))O(B^2+K(K+(1-\alpha)B^2))O(B2+K(K+(1−α)B2))O(B^2+K(K+(1-\alpha)B^2))
gSAP, chunking (cc)O(KB2)O(KB^2)O(cB2)O(cB^2)
gSAP, splitting (GG)O(KB2/G)O(KB^2/G)O(KB2/G)O(KB^2/G)
gSAP, windowedO(B2log⁡B+Kwˉ)O(B^2\log B+K\bar w)O(B2+Kwˉ)O(B^2+K\bar w)
Reviewer_mV9xOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper advocates for using global average precision to evaluate and optimize a metric learning problem. The authors claim and show empirically, that their idea is superior in various representation learning setups. The authors justify this approach intuitively by noting that this gAP metric is consistent with the single relevancy threshold paradigm.

Critical strengths
  • I like the idea of making gAP differentiable and applying it to the metric learning literature.
  • The most critical strength of this submission is the extensive empirical study and the thorough comparison with SoTA baselines.
  • I think the superiority of the proposed method for the gAP metric and single threshold result (Tables 5 and 6) is useful and will be well received by the community.
    • On the flip side I would like to hear the author's thoughts on why optimizing gAP would be better than optimizing mAP even when mAP is being used as the evaluation metric (Table 5).
Critical weaknesses
  • While the idea itself appears novel, smooth surrogates for ranking losses identical to the method presented here is well-explored. The novelty lies solely in the idea of "global average precision", in my opinion.
  • There are extensive empirical results, which I appreciate. However, I cannot understand theoretically why this method would be better for any of the optimization problems presented.
Questions for authors

I'm curious about the mathematical relationship between sigLIP and the proposed gAP loss. sigLIP treats each pairwise score as a binary classification problem. You seem to be doing something similar. What does the loss plot look like, if you take a random batch, and vary a single pairwise score? Is it convex? How does it compare with well known binary classification losses?

I'm guessing it looks like a smoothed step function (but I don't know for sure), in which case how do you justify your method in principle (or in theory) against a convex loss function?

8 comments
AuthorsOpenReview ↗

W1: novelty and the Kaggle “Global Average Precision”

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.

The metric is not ours, and the paper does not claim it. gAP goes back at least to Perronnin et al. (2009), cited in Section 1 (L38) with the benchmarks that adopt it (L40-42), among them GLDv2 (Weyand et al., 2020), whose Kaggle challenges defined the metric at the reviewer's link.

Our contribution is a global AP-based ranking loss for representation learning. The distinction is which similarities are ranked together. Using the same smooth AP building block, the objectives are

=1-\frac{1}{M}\sum_{i=1}^{M} \widetilde{\mathrm{AP}}(S_i,Y_i), \qquad \mathcal{L}_{\mathrm{gSAP}} =1-\widetilde{\mathrm{AP}}(\operatorname{vec}(S), \operatorname{vec}(Y)).$$ The former optimizes each query's ranking separately; the latter couples all query–candidate pairs through one ranking. This changes the training objective: a positive is compared with similarities from other queries, directly encouraging cross-query consistency. The larger comparison set also sustains gradients at low temperatures where per-query optimization stalls (Figure 3). We demonstrate this objective as the main training loss in supervised metric learning, cross-modal alignment and self-supervised learning. The experiments establish its practical benefit: improved global ranking and shared-threshold performance while maintaining competitive per-query quality.
AuthorsOpenReview ↗

S&W2: why optimizing gAP can help mAP; why the method is better, in principle

Why gSAP helps, including on mAP. Most evaluated tasks rely on ranking similarities, including retrieval, kkNN classification and zero-shot classification. Three properties help explain the observed gains:

  1. A stricter ranking requirement. Perfect gAP requires every positive to rank above every negative across all queries. This implies perfect mAP, but the converse does not hold (Appendix E, Examples 1–2). When perfect global ranking is attainable, gAP's optima are therefore a subset of mAP's: global ranking additionally requires consistency across queries. This statement concerns the exact metrics, not the optima of their finite-temperature surrogates.

  2. Cross-query consistency. Adding a constant to a query's similarities preserves its AP and within-query sigmoid comparisons, but can change gAP. The global objective addresses this additional requirement. Appendix E decomposes the gAP difference into ranking and consistency terms: consistency contributes on both datasets, with ranking contributions marginally (Table T). Performing similar analysis on CLIP attributes 64–100% of gSAP's gain over InfoNCE and SigLIP to consistency on MS COCO and Flickr30k.

  3. More comparisons sustain the gradient. A positive whose within-query comparisons have saturated can still receive gradients from cross-query comparisons under gSAP. In Figure 3, at τ=10−4\tau=10^{-4}, gSAP has more than a hundred unsaturated comparisons per positive on average, against fewer than one for mSAP, which trains far more slowly. On a CC12M batch of 512 pairs at τ=10−3\tau=10^{-3}, the corresponding counts are 59 in the global list and 0.3 within the positive's row and column. This additional signal helps explain why gSAP can also improve per-query ranking.

Observed gains in mAP. gSAP approximately matches mSAP on SOP and iNaturalist (Table 5), while improving mAP by 1.2 points on ILIAS (Table Q), and in CLIP, it improves text-to-image mAP from 65.5 to 67.1 and image-to-text mAP from 57.7 to 59.7 (OpenReview Table R3.2).

Revision. We will clarify the relationship between the metric optima and add the CLIP decomposition to Appendix E alongside Table T.

AuthorsOpenReview ↗

Q: relationship with SigLIP, the loss for one varied similarity, convexity

One template. We thank the reviewer for this question, which led us to write the losses as instances of one template. For a positive pair pp in a list (its own row, or the whole similarity matrix), let

\qquad R^+_p=1+\sum_{p'\in\mathcal P_p\setminus\\{p\\}} \tilde h(s_{p'}-s_p), \qquad \mathrm{P}_p=\frac{R^+_p}{R^+_p+R^-_p}.$$ with $\mathcal N_p$, $\mathcal P_p$ the negatives and positives of the list, and $\mathcal L=\frac1{|\mathcal P|}\sum_p\ell(\mathrm{P}_p)$. The losses differ in the scope of the list, the kernel $\tilde h$, whether $R^+$ is kept, and the aggregation $\ell$ (Table R2.1). **Table R2.1.** **The losses as one template.** Convex: as a function of one similarity, all others fixed. In the $R^+$ column, “no” means $R^+_p=1$. | method | scope | kernel | $\boldsymbol{R^+}$ | $\boldsymbol{\ell}$ | term per positive (or pair) | convex | | --- | --- | --- | --- | --- | --- | --- | | **SigLIP** | threshold | logistic | – | – | $\log\bigl(1+e^{-z_{ij}(ts_{ij}+b)}\bigr)$ per pair | yes | | **Contrastive** | threshold | hinge | – | – | $d_{ij}$ or $[m-d_{ij}]_+$ per pair, $d$ Euclidean | in $d$ | | **InfoNCE** | per-query | exp | no | $-\log x$ | $\log(1+R^-_p)$ | yes | | **mSAP (Smooth-AP)** | per-query | sigmoid | yes | $1-x$ | $1-\mathrm{P}_p$ | no | | **gSAP** | global | sigmoid | yes | $1-x$ | $1-\mathrm{P}_p$ | no | **Relationship with SigLIP.** Both losses act on all pairs of the batch with one rule shared by all queries, but differ in what each similarity is compared with. SigLIP compares each similarity with one learned threshold, $-b/t$. gSAP compares each similarity with the similarity of every positive, so each positive sets a threshold and gAP averages the precision at all of them. gSAP thus trains classification at every operating point set by the positives, while SigLIP operates on a single operating point set by the learned threshold. This matters because the deployed threshold is chosen afterwards, for example for 90% precision. The two also focus on different errors. SigLIP's gradient on a pair depends only on how far the pair lies from the threshold, while gSAP weighs each misordered pair by the precision it costs, which is largest near the top of the batch-wide ranking, as in gAP. **The loss as one similarity varies.** PDF Figure R2.1, included in the appendix of updated PDF, compares the losses on a real batch as one positive or one negative similarity varies, with all other similarities fixed. As the reviewer anticipated, varying a negative similarity produces a bounded, monotonically increasing, non-convex curve resembling a smoothed staircase, with transitions around the positive similarities. **Figure R2.1.** See the updated paper PDF, Appendix F, **“Rebuttal Figures,” p. 37**. **Why a non-convex loss.** gSAP is indeed non-convex in the similarities, as is Smooth-AP (mSAP). Its motivation is to directly approximate the ranking metric. Although a convex loss in the similarities does not make optimization through a deep encoder convex, the shape of the loss still matters, particularly where sigmoid saturation produces small gradients. Our evidence here is empirical. The demonstrated retrieval results support its practical effectiveness, without establishing a general convergence guarantee or theoretical superiority over convex losses. We welcome the reviewer's suggestions for further analysis and would be happy to conduct additional targeted experiments during the discussion. **Revision.** A new appendix section gives the template, PDF Figure R2.1 and the comparisons of Reviewer au2M-W1, and Section 3 relates gSAP to SigLIP and to convex losses.
Reviewer_hpAdOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The authors train with a smooth AP loss over all pairs in a batch, so similarities from different queries enter the same ranking. They drop easy negatives to reduce the cost. Experiments cover supervised metric learning, CLIP and CLAP fine-tuning, MoCo v3 pretraining, and retrieval with distractor queries. The main result is better global ranking and more consistent similarities across queries, usually without sacrificing per-query retrieval quality.

Critical strengths
  1. The strongest results are those that separate global ranking from per-query quality. On SOP, gSAP and mSAP both reach 72.9 mAP, while gAP rises from 57.0 to 58.9 and shared-threshold F1 from 57.6 to 59.3 (Tables 5 and 6). On Met, their gAP is identical without distractor queries, but gSAP gains 4.5 points when distractors are included. These comparisons make a convincing case for training across queries.
  2. The authors have tested the idea thoroughly. Table L repeats the comparison with four AP approximations and finds the same pattern, which supports the choice of objective rather than a particular sigmoid approximation. The regularizer and score-normalization comparisons cover sensible alternatives. The CLIP, CLAP and self-supervised experiments broaden the case, and the fine-grained transfer gains in Table H are substantial. The ImageNet linear-probing results are more mixed, as the paper reports.
Critical weaknesses
  1. The cost needs a clearer account. Directly evaluating Equation (10) using Equation (3) compares each of K positive pairs with B² similarities: O(KB²) work. With one positive per query, K grows with B, giving cubic cost in batch size. This does not agree with the linear-in-similarities claim in Section 3.4 or the quadratic-in-batch-size claim in the conclusion, unless the implementation uses a faster algorithm that has not been described. Negative dropping, the feasible batch sizes in Tables B and M, and the chunked backpropagation in Appendix C.3 show how memory is managed. They do not tell us the training overhead. Please give the implemented complexity and representative step times and peak memory against the other losses at the same batch size and on the same hardware. The accuracy results stand, but the cost determines how practical this replacement is.
  2. Table 6 is missing the precision achieved on the evaluation classes. Appendix C.3 fits a threshold for 90% precision on fitting classes, then applies it to disjoint classes. Without the latter precision, the iNaturalist result cannot yet be read as fourfold recall at the same held-out precision: the models may differ in how well the fitted threshold transfers. Please report both precision and recall, including variation across the existing seeds or class splits. Since deployment with one threshold is a central motivation, this is an important part of the result. The absolute recall, 0.7% versus 3.0%, should also remain clear when describing the fourfold gain.
Questions for authors
  1. Does the implementation evaluate all K×B² sigmoid comparisons, or use a faster algorithm? What are its time and memory costs as batch size and the number of positives increase? Measurements from the existing runs would help.
  2. What precision does the threshold fitted for 90% precision actually achieve on the evaluation classes in Table 6? How much do precision and recall vary across the existing seeds?
  3. Exact ranks are invariant to increasing per-query transformations, but finite-temperature sigmoid surrogates change when similarity gaps change. Appendix E makes the zero-temperature qualification. Can Section 2 do the same, and qualify its broader claim that per-query losses leave similarities across queries unconstrained?
6 comments
AuthorsOpenReview ↗

W1 / Q1: cost (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.

Complexity. We thank the reviewer for the careful count. The exact implementation of gSAP evaluates every comparison, each of the KK positive pairs against all B(B−1)B(B-1) similarities of a unimodal batch (B2B^2 for cross-modal pairs). The time is therefore O(KB2)O(KB^2), that is O(B3)O(B^3) with one positive per query (cross-modal and self-supervised learning) and O(ρB3)O(\rho B^3) with ρ\rho samples per class, i.e. K=B(ρ−1)K=B(\rho-1) positives (metric learning and other tasks). The memory is O(KB2)O(KB^2) as well. In Section 3.4, “linear in the number of pairwise similarities” referred to the number of positive–similarity comparisons, and “quadratic in the batch size” in the conclusion to the cost of each positive pair. We fully agree that, as written, both read as the total cost in the batch size. We will revise both phrases.

Loss implementation. Keeping the loss practical is a trade-off between performance, speed, and memory. Three techniques avoid most of its cost in time and memory while sacrificing as little performance as possible. Only negative dropping changes the loss. Chunking and splitting compute exactly the same loss and gradient.

  1. Negative dropping (mentioned in the paper) keeps every positive and only the hardest negatives, those with the highest similarities, found by a top-kk over the negatives of the batch. The drop rate α\alpha sets how many comparisons are skipped, and so how much time and memory is saved.

  2. Chunking (implemented; not mentioned) splits the positive pairs into chunks of cc and computes the loss one chunk at a time, recomputing each chunk in the backward pass instead of keeping its values, as in gradient checkpointing. The comparisons of all positives are never held in memory at once, so the memory of the loss falls from O(KB2)O(KB^2) to O(cB2)O(cB^2) whatever the number of positives. The loss and its gradient are unchanged, and the time stays O(KB2)O(KB^2) at the price of one more forward pass per chunk.

  3. Splitting (implemented; not mentioned) divides the positives among the GPUs of a multi-GPU run. Each GPU ranks its share against the full similarity matrix gathered from all GPUs, which gives the exact full-batch gradient without computing the whole loss on every GPU.

Faster algorithm (new). We thank the reviewer for motivating a faster implementation of gSAP. This new windowed implementation evaluates sigmoids only within a window around each positive and sums the numerically saturated contributions outside it in closed form. It computes the loss and gradient with a truncation error per comparison far below single-precision rounding. In full training runs, all reported metrics differ from the exact implementation by at most 0.2 in metric learning and CLIP fine-tuning experiments. We will describe the windowed implementation in detail in the appendix. Note that, the same acceleration also applies to other ranking losses based on sigmoid comparisons, such as mSAP.

Table R1.1. Time and memory of the loss. For KK positive pairs among the B2B^2 similarities of a batch, not counting the computation of the similarities (O(B2d)O(B^2 d); same for every method). α\alpha is the share of negatives dropped, cc the number of positives per chunk, and GG the number of GPUs among which the positives are split, with the time and memory per GPU. wˉ\bar w is the mean number of similarities that the windowed algorithm compares exactly with a positive.

methodtimememory
mSAPO(KB)O(KB)O(KB)O(KB)
InfoNCE, SigLIPO(B2)O(B^2)O(B2)O(B^2)
gSAP, exactO(KB2)O(KB^2)O(KB2)O(KB^2)
gSAP, negative dropping (α\alpha)O(B2+K(K+(1−α)B2))O(B^2+K(K+(1-\alpha)B^2))O(B2+K(K+(1−α)B2))O(B^2+K(K+(1-\alpha)B^2))
gSAP, chunking (cc)O(KB2)O(KB^2)O(cB2)O(cB^2)
gSAP, splitting (GG)O(KB2/G)O(KB^2/G)O(KB2/G)O(KB^2/G)
gSAP, windowedO(B2log⁡B+Kwˉ)O(B^2\log B+K\bar w)O(B2+Kwˉ)O(B^2+K\bar w)
AuthorsOpenReview ↗

W1 / Q1: cost (part 2)

Measurements. Tables R1.2 and R1.3 report training-step time, excluding data loading, and peak memory. At the paper's batch sizes, exact gSAP adds 4% over mSAP in metric learning and 59% over InfoNCE in CLIP with chunking and GPU splitting. Windowed gSAP keeps these overheads at 2–3% and 10–13%, respectively, across all batch sizes tested, without running out of GPU memory. Note that, in wall-clock time, a full CLIP fine-tuning at B=2,304B=2{,}304 takes 4.2–4.4 h for every loss, since reading the data sets the pace, and a full metric-learning run on SOP at BB = 1,000 takes 94–96 min, since the backbone dominates each step.

Table R1.2. Metric learning: training time and memory. Seconds per training step / peak memory in GiB, with time overhead relative to mSAP in parentheses. DINOv3 on SOP using one H200 GPU. α\alpha is the fraction of negatives dropped. OOM: out of memory.

methodalgorithmα\alphaB=1,000B=1{,}000B=2,000B=2{,}000B=4,000B=4{,}000
mSAP––1.53 / 14.73.07 / 14.76.14 / 14.7
gSAPexact0%1.59 (+4%) / 22.7OOMOOM
gSAPexact90%1.54 (+1%) / 14.73.12 (+2%) / 18.5OOM
gSAPexact99%1.54 (+1%) / 14.73.07 (+0%) / 14.76.18 (+1%) / 16.0
gSAPwindowed0%1.56 (+2%) / 14.73.13 (+2%) / 14.76.30 (+3%) / 14.7

Table R1.3. CLIP: training time and memory. Seconds per training step / peak memory per GPU in GiB, with time overhead relative to InfoNCE in parentheses. ViT-B/32 on 8 GPUs using CC12M batches held in memory. Chunk gives the positives per chunk; split distributes positives across GPUs. OOM: out of memory.

methodalgorithmchunksplitB=512B=512B=1,024B=1{,}024B=2,304B=2{,}304B=4,096B=4{,}096
InfoNCE–––0.127 / 5.00.199 / 7.30.375 / 12.70.625 / 20.4
SigLIP–––0.127 (+0%) / 5.00.199 (+0%) / 7.30.375 (+0%) / 12.70.623 ($-$0%) / 20.4
mSAP–––0.128 (+1%) / 5.00.199 (+0%) / 7.30.378 (+1%) / 12.70.630 (+1%) / 20.8
gSAPexact–✓0.163 (+28%) / 5.00.268 (+35%) / 8.40.676 (+80%) / 29.5OOM
gSAPexact64–0.151 (+19%) / 5.00.367 (+84%) / 7.92.126 (+467%) / 17.410.7 (+1612%) / 36.1
gSAPexact64✓0.133 (+5%) / 5.00.221 (+11%) / 7.90.596 (+59%) / 17.41.888 (+202%) / 36.1
gSAPwindowed–✓0.143 (+13%) / 5.00.222 (+12%) / 7.30.414 (+10%) / 13.20.706 (+13%) / 22.7

More positives per row. For timing, we group kk consecutive image–text pairs per class (Table R1.4). Up to k=8k=8, windowed gSAP adds at most 16% step time and 1.4 GiB per GPU over InfoNCE, while exact gSAP's time overhead grows linearly with kk.

Table R1.4. Training time and memory with kk positives per row. Seconds per step / peak memory per GPU in GiB at B=2,304B=2{,}304, with time overhead relative to InfoNCE in parentheses.

losskk = 1kk = 2kk = 4kk = 8
InfoNCE0.376 / 12.70.377 / 12.70.376 / 12.70.377 / 12.7
mSAP0.378 (+1%) / 12.70.381 (+1%) / 12.70.385 (+2%) / 13.00.392 (+4%) / 13.6
gSAP, exact (paper)0.596 (+59%) / 17.40.816 (+116%) / 17.41.253 (+233%) / 17.42.131 (+465%) / 17.4
gSAP, windowed (new)0.415 (+10%) / 13.20.419 (+11%) / 13.20.427 (+14%) / 13.40.438 (+16%) / 14.1

Revision. Section 3.4 and the conclusion will revise the cost. The appendix will add Tables R1.1–R1.4 and the windowed implementation with its code.

AuthorsOpenReview ↗

W2 / Q2: precision on the evaluation classes in Table 6

Held-out precision. We agree that a recall must be read with the precision it comes at. Table 6 selects the threshold on half of the test classes, the fitting classes, and applies it to the other half, the evaluation classes. Table R1.5 gives the precision and the recall (R@P90) it reaches on the evaluation classes, with the standard deviation over the three seeds, and the recall at exactly 90% precision with the threshold selected on the evaluation classes themselves (oracle).

Table R1.5. Transfer of the threshold set for 90% precision. The threshold is selected on the fitting classes of Table 6 and applied to its evaluation classes, where its precision and recall (R@P90) are measured. The oracle is R@P90 with the threshold selected on the evaluation classes. Mean and standard deviation over three seeds, in %.

methodSOP / precisionSOP / recallSOP / oracleiNaturalist / precisioniNaturalist / recalliNaturalist / oracle
RS@kk90.2 ± 0.2418.3 ± 0.2918.5 ± 0.5386.2 ± 0.510.6 ± 0.220.2 ± 0.04
mSAP90.1 ± 0.2818.7 ± 0.6118.8 ± 0.6887.2 ± 0.790.7 ± 0.040.2 ± 0.06
gSAP89.9 ± 0.2821.0 ± 0.5920.7 ± 0.8388.3 ± 1.463.0 ± 0.632.2 ± 0.18

On iNaturalist, no loss's threshold reaches 90% precision on the evaluation classes on average, and gSAP's comes closest (88.3, against 87.2 for mSAP), so its R@P90, four times that of mSAP (3.0 against 0.7), comes with a higher precision, not a looser threshold. At exactly 90% precision on the evaluation classes the gap is about tenfold. On SOP the threshold transfers for all three losses, and gSAP leads in R@P90 (21.0 against at most 18.7). On both datasets, gSAP is ahead in R@P90 on every seed.

Revision. Table 6 will add the precision on the evaluation classes, the standard deviation over seeds and the oracle R@P90. The abstract and Section 4 will state the fourfold gain as 3.0% against 0.7% recall, at a threshold set for 90% precision on other classes.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response

We thank all reviewers for their valuable feedback. We answer the questions and address the weaknesses in a comment under each review. The manuscript's appendix now includes the figures we refer to within our responses. Additional results are reported as tables within our responses. We are happy to provide any further analysis or clarification during the discussion. Afterwards, we will update the manuscript with the new results; within each response we state what will be added.

AuthorsOpenReview ↗

Revised manuscript uploaded

Dear Reviewers and Area Chair,

Thank you for a very constructive discussion. Your questions led to new experiments, analyses and clarifications that we believe have made the paper substantially stronger.

We have now uploaded the revised PDF, with changes marked in red. We list the main changes:

  • Cost (hpAd, au2M): corrected complexity in Section 3.4 and the conclusion; Appendix B.6 gives the complexity, step time and peak memory, and describes the new windowed implementation.
  • One threshold for all queries (hpAd): Table 6 now reports the held-out precision and the oracle recall, and the fourfold gain is stated with its absolute recall.
  • Finite temperature (hpAd): the invariance claims are qualified in Sections 1, 2 and 3.5 and in Appendix E.1, with a new table.
  • PNP, CES and the role of the AP weighting (au2M, mV9x): both are discussed in Section 2 and added to Tables 1–3 and 5; the common template is in Appendix E.4 and the global variants in Appendix B.5.
  • Loss shape, hard negatives and training from scratch (mV9x): Appendix E.4, with CLIP trained from scratch in Section 4.1 and Appendix B.7.
  • Batch-level vs. dataset-level gAP, and sensitivity (au2M): Appendices B.3 and F.

This version prioritises completeness over polish: some of the new material still needs better structure and tighter wording. For the final version we will polish the text and the organization.

Thank you again for your time and for the discussion.

Sincerely,
The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.