Top-1 Irretrievability of Dense Retrieval

Dense image retrieval under Maximum Inner Product Search (MIPS) embeds a query and each retrievable item into a common vector space, and returns the item with the largest inner product. Each target is therefore associated with a retrieval cone of query directions from which it is uniquely top-1 ranked. Our work identifies that, when its embedding lies inside the convex hull of the other items’ embeddings, the cone is empty, and no query can top-1 retrieve the target. We quantify the extreme rarity of this occurrence in natural data, yet we show such irretrievability can be engineered with near-perfect success rates. When embeddings are normalised, exact irretrievability is impossible. We therefore introduce ϵ-retrievability, relaxing the criterion to a retrieval cone of small volume, and develop methods to make the target difficult to retrieve. We demonstrate these methods on a wide variety of embedding models for both unimodal and cross-modal retrieval tasks often with near-perfect success rate.