- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper investigates the geometric conditions under which an item in dense retrieval becomes impossible or difficult to retrieve as the top-1 result. It establishes that an item is exactly irretrievable under maximum inner product search (MIPS) if its embedding lies inside the convex hull of the other indexed embeddings. For normalized embeddings, where exact irretrievability is impossible, the authors introduce ε-retrievability based on the normalized volume of the retrieval cone. They propose two decoy-insertion methods that manipulate embedding geometry while keeping the encoder fixed and the target unchanged. Experiments across nine retrieval models and multiple retrieval settings demonstrate high hiding rates, although the results for discrete text decoys are considerably weaker.
Critical strengths
- Proposition 1 establishes the equivalence between convex-hull containment, an empty retrieval cone, and zero cone volume (Eq. 3). This provides a precise and interpretable foundation for analyzing top-1 irretrievability.
- Figure 3 systematically examines decoy count, perturbation budget, index size, and embedding dimension, providing useful insights into the method's operating conditions.
Critical weaknesses
- The main experiments use 48 Flickr30K targets, while several ablations use only 24 targets (Sections 3.3–4.2). Most principal tables report point estimates without uncertainty intervals, making it difficult to assess the variability and generalizability of the reported success rates.
- Appendix A acknowledges the absence of direct comparisons with existing methods. Although related approaches are discussed in Section 5, the paper does not establish comparative effectiveness under matched perturbation budgets and computational constraints.
- The cone-volume definition assumes uniformly sampled query directions (Eq. 2), whereas practical queries follow model-dependent distributions.
Questions for authors
-
For the results in Tables 3 and 5 that use embedding-level tangent-direction correction, can the authors demonstrate that the corrected embeddings can be realized by actual inputs and that the reported performance persists after re-encoding those inputs?
-
Can the authors evaluate whether the observed relationship between cone volume and retrieval success holds across alternative query distributions, rather than relying primarily on uniformly sampled directions or a particular query-search procedure?
5 comments
Q1: For the results in Tables 3 and 5 that use embedding-level tangent-direction correction, can the authors demonstrate that the corrected embeddings can be realized by actual inputs and that the reported performance persists after re-encoding those inputs?
Yes. The correction of App. D.7 removes an optimisation error that all decoys of a target share. We traced this error to the cause described in Section 3.2, where in some directions the embedding responds only weakly to the pixels. Section 3 handles this with Eq. (18) in its loss, and we use it in the same way to build these decoys as actual images, with no correction of their embeddings. On MobileCLIP2, a longer run of the paper's own loss is already enough without the correction. We do not observe any significant changes that can affect the conclusion of our study.
| Entry | With the correction | Actual images only |
|---|---|---|
| Table 3, MobileCLIP2 L/14, | 100% | 100% |
| Table 5, DINOv2-B/14, | 100% | 95.8% |
| Table 5, DINOv2-B/14, | 85.4% | 81.3% |
| Table 5, DINOv2-B/14, | 35.4% | 14.6% |
| Table 5, DINOv3-L/16, | 100% | 95.8% |
| Table 5, DINOv3-L/16, | 41.7% | 100% |
| Table 5, DINOv3-L/16, | 2.1% | 16.7% |
These only affect a small subset of our results. We will update Tables 3 and 5 as well as the appendices to reflect these changes, so that no result in the paper relies on the correction.
Q2: Can the authors evaluate whether the observed relationship between cone volume and retrieval success holds across alternative query distributions, rather than relying primarily on uniformly sampled directions or a particular query-search procedure?
We do not use uniformly sampled directions during evaluation. On ViT-B/32, for each of the 44 decoy configurations (number of decoys and angle ) of Fig. 4, we measured how often the target is retrieved under six query distributions and correlated the result with the cone volume with Spearman correlation:
| Query distribution | Measure of retrieval | Correlation with cone volume |
|---|---|---|
| Adaptive text search (as in Table 3) | target retrieved | 0.91 |
| The target's own captions (as in Table 2) | target in the top 10 | 0.96 |
| Corpus captions nearest to the target's own | target in the top 10 | 0.96 |
| All 155,070 captions of the corpus | target in the top 10 | 0.97 |
| All other images of the index, used as queries | target in the top 10 | 0.77 |
| Random queries at / from the target | target ranked first | 0.16 / 0.15 |
We observe that a smaller cone makes retrieval of the target harder under any query distribution / scenarios tested.
I hope these can address the reviewer's concerns, and help them adjust their scores accordingly
I do not see the relevant changes highlighted in the main text. The author may highlight the changes made with colors.
The limited size of target set in ablations is mainly due to our limited resources required to accommodate the extensive amount of ablations in our study. With Wilson intervals for the success rates, on 48 targets the interval follows: 100% gives [92.6%, 100%], 97.9% [89.1%, 99.6%], 95.8% [86.0%, 98.8%] and 0% [0%, 7.4%]. Almost every entry of the decoy-insertion row of Table 1 and of the C=64 column of Tables 3 and 4 is one of the first three, so each has a lower bound at 95% confidence of at least 86.0%. In Table 2 the comparison is paired, and every one of the 48 targets is ranked lower with decoys on every encoder (by 10 to 58 places at C=64).
Table 2 with 95% intervals for the median caption rank:
We understand the reviewer's concern. We note that the problem Section 3 aims to tackle is unique in the context of retrieval. To our best knowledge, for constructions detailed in Section 3, there is no directly comparable algorithm. For Section 4, our discussion is a strict generalisation (e.g. α=0) to the existing algorithms.
For this response, we ported the objectives of the two algorithms closest to our Section 3 from data poisoning, Convex Polytope and Bullseye Polytope. We tested these on ViT-B/32 under the same experimental setting. None achieved hull enclosure (guranteed irretrievability).
For Section 4, the closest method is FoggySight, which optimises the decoys' embeddings onto the target's. We ran its objective (which is exactly equivalent to α=0 in our construction) in our pipeline:
At α=0 all decoys are optimised towards the same point, so they end up on one side of the target due to optimisation noise and its cone stays far larger. With 64 decoys, the search still retrieves a quarter of the targets at α=0 and none at α=5∘.
The uniform measure in Eq. (2) is only used to define the cone size, but this uniformality is never used in our evaluation. Table 2 uses human captions and Table 3 uses text query search. We have not identified any particular problem with the way the cone size is defined in our study and experiments.