Training-free sparse representations of dense vectors for scalable information retrieval

Graphical Abstract Training-free Sparse Representations of Dense Vectors for Scalable Information Retrieval Fabio Carrara, Lucia Vadicamo, Giuseppe Amato, Claudio Gennaro 𝝉𝟏… 𝝉𝟏 𝝉𝒋 … 𝝉𝒋 𝝉𝟐𝒎 … 𝝉𝟐𝒎 (space-separated codewords), e.g., − 𝝉𝟏 repeated 980 times − 𝝉,𝒋 repeated 622 times − 𝝉𝟐𝒎 repeated 628 times 1. Semi-orthogonal transformation Expands the vector dimensionality and distributes the information across the different dimensional components while preserving the dot product. Vec2Doc Transformation to Term Frequency Vector The dense real vector 𝒚 ∈ ℝ𝒅 is transformed into a positive integer vector 𝒚 ∈ ℕ𝟐𝑚 representing a term frequency vector over a codebook 𝐶 = 𝜏1, … , 𝜏2𝑚 of 2 𝑚 terms 𝒚 ∈ ℝ𝑑 𝐴∈ℝ𝑚× 𝑑 s.t. 𝐴𝑇𝐴=𝐼, 𝑚>𝑑 0.0980 0.0433 −0.0230 0.0662 −0.0628 CReLU 0.0980 0.0433 0 0.0622 0 0 0 0.0230 0 0.0628 𝑔 𝟎. 𝟎𝟗𝟖𝟎 0 0 𝟎. 𝟎𝟔𝟐𝟐 0 0 0 0 0 𝟎. 𝟎𝟔𝟐𝟖 IQ 𝟗𝟖𝟎 0 0 𝟔𝟐𝟐 0 0 0 0 0 𝟔𝟐𝟖 input 2. Positivization Transform the vector into a positive one. We used the Concatenated Rectified Linear Unit Transformation: 𝐶𝑅𝑒𝐿𝑢 𝒗 = max 𝒗, −𝒗 , 𝟎 3. Sparsification Apply a sparsification function, e.g., component-wise thresholding. ∈ ℝ𝑚 ∈ ℝ2𝑚 4. Integer Quantization Transform real components into integer, e.g., using a quantization factor 𝑠 > 1: 𝐼𝑄 𝑥 = 𝑠 ⋅ 𝑥 ∈ ℝ2𝑚 ∈ ℕ2𝑚 4. Surrogate Text A document is formed repeating the i-th term a number of times indicated by the i-th component of the text frequency vector. 5. Full-text Indexing Text is indexed with search engines based on the vector model (e.g., Apache Lucene / Elasticsearch). TF-only scoring for inner product. Highlights Training-free Sparse Representations of Dense Vectors for Scalable Information Retrieval Fabio Carrara, Lucia Vadicamo, Giuseppe Amato, Claudio Gennaro •Training-free sparse transform of dense vectors for scalable information retrieval •We allow custom-sized vocabularies in the sparse space for improved flexibility •Better effectiveness-performance trade-offs than other training-free representations Training-free Sparse Representations of Dense Vectors for Scalable Information Retrieval Fabio Carraraa,∗, Lucia Vadicamoa, Giuseppe Amatoa, Claudio Gennaroa aInstitute of Information Science and Technologies, CNR, Via G. Moruzzi 1, Pisa, 56124, , Italy Abstract In this paper, we propose and analyze Vec2Doc, a novel training-free method to transform dense vectors into sparse integer vectors, facilitating the use of inverted indexes for information retrieval (IR). The exponential growth of deep learning and artificial intelligence has revolutionized scientific problem-solving in areas such as computer vision, natural language processing, and automatic content generation. These advances have also significantly impacted IR, with a better understanding of natural language and multimodal content analysis leading to more accurate information retrieval. Despite these developments, modern IR relies primarily on the similarity evaluation of dense vectors from the latent spaces of deep neural networks. This dependence introduces substantial challenges in performing similarity searches on large collections containing billions of vectors. Traditional IR methods, which employ inverted indexes and vector space models, are adept at handling sparse vectors but do not work well with dense ones. Vec2Doc attempts to fill this gap by converting dense vectors into a format compatible with conventional inverted index techniques. Our preliminary experimental evaluations show that Vec2Doc is a promising solution to overcome the scalability problems inherent in vector-based IR, offering an alternative method for efficient and accurate large-scale information retrieval. Keywords: Inverted Index, Approximate Search, High-Dimensional Indexing, Very Large Databases, Surrogate Text Representation 1. Introduction1 Dense learned representations are foundational2 for retrieval tasks over a large span of data modal-3 ities. In large-scale settings, the most effective4 methodologies to retrieve text documents, images,5 videos, etc., are based on computing vector similar-6 ity, i.e., cosine similarity, between queries and data7 points representations extracted by neural mod-8 els such as large multimodal/language [1, 2] or9 common-space models [3, 4, 5].10 However, the nature of neural representations11 poses challenges in indexing and querying large col-12 lections. Tested and mature technology for web-13 scale retrieval is based on inverted indices and as-14 sumes sparse, high-dimensional, and positive vector15 representations. Instead, neural representations are16 often dense, signed, and lower-dimensional, making17 ∗Corresponding author the direct application of inverted indices very ineffi-18 cient. Dense retrieval approaches based on approx-19 imate nearest neighbor provide exceptional perfor-20 mance, but those solutions usually scale worse than21 disk-based inverted-file implementations, in terms22 of cost, as they often require more expensive re-23 sources like a high RAM usage or GPU accelera-24 tion. For large-scale collections, disk-based indices25 based on sparse dot products still offer an inex-26 pensive solution. Methods such as SparTerm [6]27 and SPLADE [7, 8] have been proposed for learn-28 ing sparse representations with wanted properties,29 but they require a costly training procedure for each30 collection we want to index.31 Other works explored instead training-free meth-32 ods to obtain sparse representations from the33 dense ones as faster and more general alterna-34 tives to learning-based approaches. These include35 Surrogate Text Representations (STR) — sparse36 representations that can be interpreted as term-37 frequency integer vectors and expressed as a string38 Preprint submitted to Information Systems May 22, 2025 of tokens in a custom vocabulary. This enables the39 ingest of specially crafted textual documents rep-40 resenting a generic dense vector into existing fully-41 featured text search engines like Elasticsearch and42 Apache Solr and implements any modal retrieval43 without a dedicated software stack. This approach44 ensures scalability and interoperability with widely45 adopted search infrastructures.46 In this work, we propose and evaluate Vec2Doc,47 an improved training-free dense-to-sparse trans-48 formation of vectors for maximum inner product49 search problems. Specifically, we address a key lim-50 itation of existing STR methods based on scalar51 quantization [9], which have a fixed-size output di-52 mensionality. To overcome this, we introduced a53 conceptually simple yet highly effective technique54 that enables an arbitrary choice of the number of55 dimensions in the sparse transformed space. This56 flexibility in output dimensionality is crucial as it57 enables a better balance between efficiency and re-58 trieval effectiveness. This is demonstrated by the59 performance improvements of our approach, which60 we evaluate across multiple benchmarks for ap-61 proximate nearest neighbor search on dense fea-62 tures, showing that increasing the dimensionality63 of the sparse representation consistently enhances64 the effectiveness-efficiency trade-off.65 A concrete demonstration of the practical impact66 of our approach is its successful integration into the67 2024 release of VISIONE [10, 11, 12], an interac-68 tive video retrieval system (demo available on 2,30069 hours of diverse video content at https://visione.70 isti.cnr.it/). VISIONE relies on Lucene for index-71 ing and searching multi-modal content, leveraging72 Vec2Doc to create a unified retrieval framework73 that combines semantic search over neural features74 with text-based metadata in a scalable manner.75 The effectiveness of this integration has been vali-76 dated through participation in international bench-77 marking campaigns, including the Video Browser78 Showdown (VBS) [13, 14], where VISIONE ranked79 first in the 2024 edition [15], achieving the best in-80 teractive video search system score in four out of81 seven retrieval tasks. This real-world deployment82 showcases the practical applicability of Vec2Doc,83 confirming its effectiveness in large-scale retrieval84 engines and its potential for real-world adoption.85 A preliminary version of this work appeared in86 [16]. The present contribution provides a more de-87 tailed description of the proposed approach and an88 extensive experimental evaluation, including new89 results on a large scale dataset, cross-modal search90 scenarios, and a discussion of current limitations.91 The remainder of this paper is structured as follows:92 Section 2 provides background and discusses related93 work. Section 3 presents the proposed Vec2Doc ap-94 proach, Section 4 details the experimental setup95 and discusses results and limitations, and Section96 5 concludes the paper and outlines directions for97 future research. Table 1 summarizes the notation98 used throughout the paper.99 2. Background and Related Work100 Metric search, essential for retrieving data ob-101 jects close to a given query object under a prox-102 imity function, finds wide application across var-103 ious fields of computer science, including pattern104 recognition, computational biology, and multime-105 dia information retrieval. This paradigm operates106 on the premise that data objects belong to a do-107 main equipped with a metric function that quanti-108 fies the closeness between objects [18]. Within this109 framework, the concept of similarity search arises110 naturally, where the goal shifts to identifying data111 objects similar to a given query object based on a112 similarity measure derived from the domain’s met-113 ric function.114 To overcome challenges posed by large or high-115 dimensional datasets, where exact search becomes116 impractical due to the need to analyze substan-117 tial data portions, approximate metric search meth-118 ods have emerged. These methods address issues119 such as the curse of dimensionality [19] by offering120 efficient search techniques that balance computa-121 tional efficiency with acceptable accuracy. Most of122 these approaches involve transforming original data123 objects into alternative representations to enable124 more efficient searching. Examples of such tech-125 niques include transforming metric objects into bi-126 nary sketches [20, 21], permutations [22, 23], and127 other pivot-based representations [24, 25].128 In 2010, Gennaro et al. [26] introduced a tech-129 nique that utilized the distances between data ob-130 jects and a set of reference objects (pivots) to map131 the data into a textual representation. Their ob-132 jective was to convert a global descriptor into a se-133 quence of terms resembling a text document, which134 could be processed by a text search engine such135 as Lucene. To achieve this, the mapping should136 be designed to approximate the original distance137 function, ensuring that the distance between tex-138 tual documents and queries reflects the original139 similarity between data objects and data queries.140 2 Table 1: Notation used throughout this paper Symbol Definition f:Rd→NmSpace transformation y∈Rdd-dimensional real vector y=f(y)∈NmInteger-valued vector (term frequency vector) obtained from yusing the space transformation f C={τ1,...,τm}Synthetic codebook of mterms Tf,C(y) Text document for the vector yassociated to the transformation fand the codebook C A∈Rm×dSemi-orthogonal matrix (i.e., ATA=I) with m > d R∈Rd×dRandom orthogonal matrix CReLU : Rn→R2nConcatenated Rectified Linear Unit transformation [17], i.e., CReLU(y) = max([y,−y],0) g:Rn→RnSparsification function ⌊·⌋ Floor function | · | Set cardinality <·,·>Dot product Input 𝒚 ∈ ℝ𝑑Full-text Search Engine Surrogate Text Representation using the Codebook {𝜏1, … , 𝜏𝑚} 𝑦 = 0.1, 0.3, 0, 0.7, … (Sparse) Integer Positive Vector 𝑓 𝒚 ∈ ℕ𝑚 𝑓(𝑦) = 2,0,0, 5,…,3 𝜏1𝜏1𝜏4𝜏4𝜏4𝜏4𝜏4… ……….. 𝜏𝑚𝜏𝑚𝜏𝑚 𝑓(𝒚1) 𝑡𝑖𝑚𝑒𝑠 𝑓(𝒚2)𝑡𝑖𝑚𝑒𝑠 𝑓(𝒚𝒎) 𝑡𝑖𝑚𝑒𝑠 𝑓: ℝ𝑑→ ℕ𝑚 𝑓 𝑦 will acts as a term-frequency vector over a vocabulary of 𝑛 terms (𝜏1, … , 𝜏𝑚) Text is indexed with search engines based on the vector model (e.g., Apache Lucene / Elasticsearch). TF-only scoring for inner product. A document is formed repeating the i-th term a number of times indicated by the i-th component of the text frequency vector. Figure 1: Illustration depicting the fundamental steps of an STR technique transforming a dense vector into a text representation suitable for indexing, leveraging a full-text search engine like Lucene The main advantage of encoding data objects as141 text was the ability to leverage off-the-shelf text re-142 trieval engines for performing similarity searches.143 This approach was initially referred to as the Sur-144 rogate Text Representation (STR) approach. How-145 ever, over the years, various techniques have been146 proposed to transform descriptors into textual doc-147 uments, and the term STR has come to encom-148 pass the broader family of approaches of this nature149 [9, 27, 28]. Some of these techniques have been de-150 signed to work on general metric spaces, while oth-151 ers are specialized for vector spaces.152 In this work, our focus is on STR techniques spe-153 cialized to index and search dense real vectors, such154 as data descriptors extracted with deep neural net-155 works. These techniques can be mathematically156 formalized as space transformations of the form f:157 Rd→Nm, where each original vector yis mapped158 into an integer-valued vector y=f(y). The key159 idea is to interpret yas a term frequency vector160 based on a synthetic codebook C={τ1, . . . , τm}of161 mterms. Consequently, the associated text docu-162 ment for vector yis obtained by concatenating the163 codebook terms with space separators, where each164 term τiis repeated a number of times equal to yi.165 We indicate with Tf,C(·) the overall transformation166 from the original vectors to the text documents,167 which depends on both the function fand the used168 codebook C. For example, if y= [3,1,0,2] and169 C={“A”, “B”, “C”, “D”}, the resulting text doc-170 3 ument associated with ywould be Tf,C(y) =“A A A171 B D D”. The rationale behind this approach is that172 the abstract transformation fcorresponds to the173 function that precisely generates the vectors used174 internally by the search engine based on the vector175 space model [29], particularly in the case of a sim-176 ple TF-weighting scheme. Figure 1 broadly sum-177 marizes the core idea behind the STR techniques.178 To ensure compatibility with text retrieval en-179 gines and the efficiency of the inverted index, f180 must generate a sparse vector with non-negative181 components. Various STR approaches exist, differ-182 ing in their specific methods for handling negative183 values, achieving sparsification, and performing the184 final real-to-integer discretization. For example, in185 [9, 28], the use of the Concatenated Rectified Lin-186 ear Unit (CReLU) activation function is employed187 to prevent the presence of negative values in the188 transformed vectors. In [28], a Voronoi partition-189 ing scheme is employed, where different codebooks190 are utilized for each partition. This approach aims191 to increase the sparsity of the transformed data,192 leading to more efficient indexing and retrieval pro-193 cesses.194 Several works explored learned sparse represen-195 tations [30, 6, 7, 8], where learning-to-rank proce-196 dures with sparsity constraints are used to learn f,197 often obtaining very efficient and effective inverted198 indices. However, the price is often paid in longer199 index training procedures that require optimiza-200 tion on labeled datasets or mined triplets of sam-201 ples for each indexed collection. Moreover, these202 methods are tailored to the textual modality, and203 the obtained representations are often constrained204 in their dimensionality by the explicit vocabulary205 on which they are trained, e.g., the token space of206 large language models, which, despite being big, is207 not changeable. Our proposal is instead an explo-208 ration of the effectiveness-efficiency trade-off we can209 obtain using training-free methods to obtain repre-210 sentation with a custom number of dimensions and211 sparsity level.212 3. Vec2Doc213 The Vec2Doc is a STR transformation that maps214 a dense real vector y∈Rdinto a term frequency215 vector y∈Nm. This transformation involves four216 main steps defined in the following paragraphs and217 summarized in Figure 2.218 1. Semi-orthogonal transformation. y1=Ay∈Rm,(1) where A∈Rm×dis a semi-orthogonal matrix (i.e., ATA=I) with m > d. The purpose of this transformation is to increase the vector dimensionality while preserving the dot product: < Av, Aw>=vTATAw=vTw=<v,w> . This step has two significant implications. First,219 it allows the dimensionality of the original vector220 to be disentangled from that of the final frequency221 vector, enabling the use of a vocabulary of arbitrary222 dimensions. Second, since the semi-orthogonal ma-223 trix is randomly chosen, it behaves similarly to a224 random rotation, effectively distributing informa-225 tion across the different dimensional components.226 To sample a random semi-orthogonal matrix, we227 follow [31] and apply the following recurrent for-228 mula to a random normally-distributed real-valued229 matrix230 A←A−1 2AATA−I(2) that efficiently converge into a semi-orthogonal ma-231 trix in a few iterations.232 2. Positivization. Since the final vector must be233 positive (as it represents frequencies), a crucial step234 is to positivize y1without significantly degrading235 the preservation of similarities between data pairs.236 Various functions have been tested, including Rec-237 tified Linear Unit (ReLU), Concatenated Rectified238 Linear Unit (CReLU), element-wise logistic func-239 tion σ, and softmax. The approach that gave the240 best results and was chosen is based on the use of241 CReLU [17]:242 y2= CReLU(y1)∈R2m.(3) The CReLU transformation involves concatenating243 both the original vector and its negation and then244 setting all negative values to zero, i.e., CReLU(v) =245 max([v,−v],0) with the max operation applied246 element-wise.247 3. Sparsification. y3=g(y2)∈R2m, where gis248 a sparification function. This step is crucial be-249 cause the data will be indexed using inverted lists,250 and the frequency vectors must be sparse to ensure251 each data item is saved in only a limited number252 of posting lists. This process attempts to replicate253 4 1. Semi-orthogonal transformation To expand the dimensionality of the vectors while preserving the dot product and distributing information across the different dimensional components 𝒚 ∈ ℝ𝑑 𝐴∈ℝ𝑚× 𝑑 s.t. 𝐴𝑇𝐴=𝐼, 𝑚>𝑑 0.0980 0.0433 −0.0230 0.0662 −0.0628 CReLU 0.0980 0.0433 0 0.0622 0 0 0 0.0230 0 0.0628 𝑔 𝟎. 𝟎𝟗𝟖𝟎 0 0 𝟎. 𝟎𝟔𝟐𝟐 0 0 0 0 0 𝟎. 𝟎𝟔𝟐𝟖 IQ 𝟗𝟖𝟎 0 0 𝟔𝟐𝟐 0 0 0 0 0 𝟔𝟐𝟖 input 2. Positivization Transform the vector into a positive one. We used the Concatenated Rectified Linear Unit Transformation 𝐶𝑅𝑒𝐿𝑢 𝒗 = max 𝒗, −𝒗 , 𝟎 3. Sparsification Apply a sparsification function (e.g., a component-wise thresholding) ∈ ℝ𝑚 ∈ ℝ2𝑚 4. Integer Quantization Transform real components into integer, e.g., using a quantization factor 𝑠 > 1 𝐼𝑄 𝑥 = 𝑠 𝑥 ∈ ℝ2𝑚 ∈ ℕ2𝑚 Figure 2: Illustration of the four basic steps of the Vec2Doc method. the natural occurrence in texts, where a single doc-254 ument contains only a few vocabulary words, re-255 sulting in sparse frequency vectors. We explored256 three different approaches for sparsification:257 •Top-K selection: For a fixed k, retain only the258 kelements with the largest magnitudes (those259 contributing most significantly to the dot prod-260 uct) and set the rest to zero.261 •Fixed thresholding: Use a fixed threshold γand262 set all values smaller than this threshold to263 zero.264 •α-norm-mass selection [32]: Retain the least265 number of largest-magnitude components such266 that the norm of the resulting vector is a given267 fraction α∈[0,1] of the original norm (e.g.,268 maintaining 75% of the norm).269 Experimentally, we noticed no significant differ-270 ences between these sparsification methods on the271 tested datasets, achieving all the same efficiency-272 effectiveness trade-off curves. We will consider the273 Top-K selection method in the following, as it gives274 explicit control over the index size with the kpa-275 rameter regardless of data distribution.276 4. Integer Quantization. y4=⌊sy3⌋ ∈ N2mwhere277 ⌊·⌋ denotes the floor function and s > 1 is a quan-278 tization factor to transform float components into279 integers1.280 Vec2Doc can be seen as a generalization of281 the Scalar Quantization (SQ) STR approach [9].282 Specifically, in SQ, y1=R(y−µ)∈Rdwhere283 R∈Rd×dis a random orthogonal matrix and284 µ∈Rdis set to center the data to zero mean.285 This step is used to uniform the distribution of vec-286 tor components. In particular, the random rotation287 helps distribute the information along all the com-288 ponents of the vector in order to limit the presence289 of unbalanced posting lists in the final inverted file290 (important for the efficiency of inverted indices).291 In [9], the centering operation is applied only to292 the data object but not to the queries to preserve293 dot-product similarities. The primary drawback of294 the SQ approach is its limitation in terms of the295 dimensionality of the resulting term frequency vec-296 tors, which is fixed at 2d, where drepresents the di-297 mensionality of the original vector. Consequently,298 the vocabulary size necessary for indexing the data299 1Integer quantization is introduced for the simple purpose of to express feature vectors as integers, allowing us to interpret them as term frequencies to be integrated into text search engines. This step is necessary only when floatingpoint values cannot be stored directly, and we, therefore, use the surrogate document approach. In any case, this approximation has a negligible impact on search accuracy. 5 Dataset Dim. |Q| |X|OOD Glove 100 10,000 1,183,514 ✗ NYTimes 256 10,000 290,000 ✗ LAION2B-CLIP768v2 768 10,000 102,144,212 ✗ COCO i2i 512 5,000 118,287 ✗ COCO t2i 512 5,000 118,287 ✓ Table 2: Approximate nearest neighbors datasets.|Q| = number of queries, |X|= number of samples in the search set, OOD = whether the queries are out-of-distribution with respect to search-set samples. with inverted files remains constant, posing an in-300 convenience when dealing with large datasets. To301 clarify further, if the number of posting lists is fixed,302 the length of each posting list may become excessive303 for large datasets, ultimately impacting search effi-304 ciency negatively. To address these limitations, [28]305 introduced the VP-SQ approach, where the data is306 clustered in Voronoi cells, and a different vocabu-307 lary can be used for each cell. Here, we propose a308 simple yet effective idea to expand the vocabulary309 size using semi-orthogonal transformation instead310 of centroids. Nevertheless, our new Vec2Doc ap-311 proach can be used alone or in combination with312 Voronoi partitioning strategies to further improve313 performance. Please note that the semi-orthogonal314 transformation is applied to both data and query315 vectors (without centering the former) before the316 real-to-integer discretization process.317 4. Experiments318 In this section, we present the results of our319 experimental analysis, which evaluates the per-320 formance of the proposed STR method under321 various scenarios. We first introduce the ex-322 perimental setup, followed by an in-depth dis-323 cussion and analysis of the results obtained in324 both an implementation-independent scenario and325 a Lucene-based implementation. To facilitate re-326 producibility and practical adoption, the complete327 implementation of our method is publicly available328 at https://github.com/fabiocarrara/str-encoders.329 4.1. Experimental Setup330 Datasets. We evaluated and compared our pro-331 posal on five benchmarks for approximate nearest332 neighbor search whose characteristics are reported333 in Table 2. Glove [33] and NYTimes [34] are exist-334 ing collections of dense embeddings of textual docu-335 ments. LAION2B is a publicly available large-scale336 dataset derived from LAION-5B [35], widely used337 for training and evaluating large vision-language338 models. We used we use the 100M image subset339 of the English portion of LAION2B (LAION2B-340 CLIP768v2), represented by 768-dimensional CLIP341 embeddings [36], employed in the SISAP 2024 In-342 dexing Challenge 2. To evaluate performance in343 both intra-modal and cross-modal settings, where344 queries may be out-of-distribution with respect345 to the search set samples, we additionally con-346 structed two collections by extracting CLIP [36]347 features (specifically, the CLS output token of348 OpenAI’s ViT-B/16 architecture) from the COCO349 dataset [37]. These collections simulate common350 query-by-example and text-based image retrieval351 scenarios. Specifically, we extract CLIP visual fea-352 tures from training-set images to be used as the353 search set. Then, we extract visual and textual354 features from the validation-set images and rela-355 tive captions (only the first one out of five available356 for each image) to be used as queries. When us-357 ing visual embeddings as queries, we refer to the358 image-to-image (i2i) scenario, while in the text-to-359 image (t2i) scenario, we adopt captions embeddings360 as queries. The t2i scenario has the peculiarity of361 having different distributions of query and search-362 set samples. All collections adopt the cosine simi-363 larity to compare feature vectors. We L2-normalize364 all vectors and compute cosine similarity scores as365 inner products.366 Evaluation Metrics. We report three main metrics367 to quantify the effectiveness and efficiency of each368 tested configuration, which are:369 Recall@K the fraction of ground-truth nearest370 neighbors present in the top K∈ {1,10,100}371 retrieved results.372 Search Cost the number of entries accessed in the373 inverted index needed to compute scores for374 all queries (also referred to in the literature as375 AFDA [27] or FLOPS [38]).376 Index Size the total number of entries in the in-377 verted index.378 Additionally, for machineand implementation-379 dependent results (Section 4.2.2), we report the in-380 dex build time, the average query time, and the381 index size in bytes.382 6 (a) Results on Glove 100. 10M 100M 1B 10B 100B 1T 10T 0.0 0.2 0.4 0.6 0.8 1.0 Recall ref. cost 1% 10% Recall@1 10M 100M 1B 10B 100B 1T 10T Search Cost (# posts visited) ref. cost 1% 10% Recall@10 10M 100M 1B 10B 100B 1T 10T ref. cost 1% 10% Recall@100 SQ [2] m = d m = 2 d m = 5 d m = 10 d m = 20 d m = 50 d m = 100 d (b) Results on NYTimes 256. 1M 10M 100M 1B 10B 100B 1T 10T 0.0 0.2 0.4 0.6 0.8 1.0 Recall ref. cost 1% 10% Recall@1 1M 10M 100M 1B 10B 100B 1T 10T Search Cost (# posts visited) ref. cost 1% 10% Recall@10 1M 10M 100M 1B 10B 100B 1T 10T ref. cost 1% 10% Recall@100 SQ [2] m = d m = 2 d m = 5 d m = 10 d m = 20 d m = 50 d m = 100 d (c) Results on LAION2B-CLIP768v2. 100B 1T 10T 100T 1E 10E 0.0 0.2 0.4 0.6 0.8 1.0 Recall ref. cost 1% 10% Recall@1 100B 1T 10T 100T 1E 10E Search Cost (# posts visited) ref. cost 1% 10% Recall@10 100B 1T 10T 100T 1E 10E ref. cost 1% 10% Recall@100 SQ [2] m = d m = 5 d m = 10 d m = 20 d m = 50 d Figure 3: Effectiveness (Recall@K) versus Search Cost (number of posts accessed to compute scores) on Glove 100 (a), NYTimes 256 (b), and LAION2B-CLIP768v2 (c) benchmarks. We compare our proposed method with the SQ baseline [9]. Each line is obtained by choosing the desired vocabulary size mand varying k— the number of components kept per vector after sparsification. the black dashed line represents the search cost for a sequential search on the respective dataset, providing a reference point to highlight configurations where the cost exceeds that of a brute-force approach. Additionally, a red vertical band marks the region where the search cost ranges between 1% and 10% of a sequential search, representing a reasonable computational budget for practical retrieval scenarios. 7 Table 4: Summary of the results for Search Cost, Index Size, and Recall for selected values of the parameters kand m. Percentages in parentheses refer to the reference cost and size of the full dense index. The table shows configurations that achieve search cost levels as close as possible to 5%. m k Search Cost Index Size Recall@10 (# posts visited) (# entries) Glove 100 1 25 51.5B (4.4%) 29.6M (25.0%) 16.9% 2 40 68.7B (5.8%) 47.3M (40.0%) 23.1% 5 50 49.9B (4.2%) 59.2M (50.0%) 24.2% 10 70 55.5B (4.7%) 82.8M (70.0%) 29.4% 20 100 61.5B (5.2%) 118.4M (100.0%) 36.0% 50 100 31.7B (2.7%) 118.4M (100.0%) 35.1% 100 200 62.7B (5.3%) 236.7M (200.0%) 48.2% NYTimes 256 1 77 34.0B (4.6%) 22.0M (29.7%) 50.3% 2 102 31.0B (4.2%) 29.6M (39.8%) 51.8% 5 179 38.9B (5.2%) 51.9M (69.9%) 58.6% 10 256 40.4B (5.4%) 74.2M (100.0%) 62.4% 20 256 20.9B (2.8%) 74.2M (100.0%) 60.3% 50 512 34.0B (4.6%) 148.5M (200.0%) 69.2% 100 512 17.8B (2.4%) 148.5M (200.0%) 67.7% COCO CLIP 512 image-to-image 1 51 7.7B (2.5%) 6.0M (10.0%) 33.8% 2 128 21.0B (6.9%) 15.1M (25.0%) 52.6% 5 128 14.3B (4.7%) 15.1M (25.0%) 52.7% 10 154 14.6B (4.8%) 18.1M (29.9%) 55.7% 20 205 16.4B (5.4%) 24.1M (39.8%) 60.8% 50 256 15.5B (5.1%) 30.3M (50.0%) 65.1% 100 250 11.2B (3.7%) 29.6M (48.8%) 65.4% COCO CLIP 512 text-to-image 1 128 14.1B (4.7%) 15.1M (25.0%) 9.4% 2 154 12.2B (4.0%) 18.1M (29.9%) 10.1% 5 256 13.9B (4.6%) 30.3M (50.0%) 14.9% 10 358 14.2B (4.7%) 42.3M (69.9%) 18.3% 20 512 15.6B (5.2%) 60.6M (100.0%) 22.3% 50 512 7.7B (2.5%) 60.6M (100.0%) 19.4% 100 1024 15.5B (5.1%) 121.1M (200.0%) 31.7% LAION2B-CLIP768v2 1 100 22.2T (2.8%) 10.2B (13.0%) 43.3% 2 250 60.5T (7.7%) 25.5B (32.6%) 60.5% 5 250 40.2T (5.1%) 25.5B (32.6%) 59.7% 10 250 29.3T (3.7%) 25.5B (32.6%) 60.1% 20 500 57.3T (7.3%) 51.1B (65.1%) 70.3% 50 500 37.6T (4.8%) 51.1B (65.1%) 70.7% B53D23026090001), EKEEL – Empowering Knowl-630 edge Extraction to Empower Learners” (European631 Union – Next Generation EU, P20227PEPK).632 References [1] J. Devlin, M.-W. Chang, K. Lee, K. Toutanova, BERT: Pre-training of deep bidirectional transformers for language understanding, in: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), 2019, pp. 4171–4186. [2] Y. Chang, X. Wang, J. Wang, Y. Wu, L. Yang, K. Zhu, H. Chen, X. Yi, C. Wang, Y. Wang, et al., A survey on evaluation of large language models, ACM Transactions on Intelligent Systems and Technology 15 (2024) 1–45. [3] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, G. Krueger, I. Sutskever, Learning transferable visual models from natural language supervision, in: Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, PMLR, 2021, pp. 8748–8763. URL: https://proceedings.mlr.press/v139/radford21a.html. [4] N. Messina, M. Stefanini, M. Cornia, L. Baraldi, F. Falchi, G. Amato, R. Cucchiara, Aladin: Distilling fine-grained alignment scores for efficient imagetext matching and retrieval, in: Proceedings of the 19th International Conference on Content-based Multimedia Indexing, 2022, pp. 64–70. doi:10.1145/3549555. 3549576. [5] J. Li, D. Li, C. Xiong, S. Hoi, Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation, in: International conference on machine learning, PMLR, 2022, pp. 12888– 12900. [6] Y. Bai, X. Li, G. Wang, C. Zhang, L. Shang, J. Xu, Z. Wang, F. Wang, Q. Liu, Sparterm: Learning termbased sparse representation for fast text retrieval, arXiv preprint arXiv:2010.00768 (2020). [7] T. Formal, B. Piwowarski, S. Clinchant, Splade: Sparse lexical and expansion model for first stage ranking, in: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2021, pp. 2288–2292. [8] T. Formal, C. Lassance, B. Piwowarski, S. Clinchant, Towards effective and efficient sparse neural information retrieval, ACM Transactions on Information Systems 42 (2024) 1–46. [9] G. Amato, F. Carrara, F. Falchi, C. Gennaro, L. Vadicamo, Large-scale instance-level image retrieval, Inf. Process. Manage. 57 (2020) 102100. [10] G. Amato, P. Bolettieri, F. Carrara, F. Falchi, C. Gennaro, N. Messina, L. Vadicamo, C. Vairo, Visione 5.0: Enhanced user interface and ai models for vbs2024, in: International Conference on Multimedia Modeling, Springer, 2024, pp. 332–339. [11] G. Amato, P. Bolettieri, F. Carrara, F. Falchi, C. G. CNR-ISTI, N. M. CNR-ISTI, Visione 5.0: Toward evaluation with novice users, in: 2024 International Conference on Content-Based Multimedia Indexing (CBMI), IEEE, 2024, pp. 1–6. [12] G. Amato, P. Bolettieri, F. Carrara, F. Debole, F. Falchi, C. Gennaro, L. Vadicamo, C. Vairo, The VISIONE video search system: exploiting off-the-shelf text search engines for large-scale video retrieval, Journal of Imaging 7 (2021) 76. [13] L. Vadicamo, R. Arnold, W. Bailer, F. Carrara, C. Gurrin, N. Hezel, X. Li, J. Lokoc, S. Lubos, Z. Ma, et al., Evaluating performance and trends in interactive video retrieval: Insights from the 12th vbs competition, IEEE Access (2024). [14] J. Lokoˇc, S. Andreadis, W. Bailer, A. Duane, C. Gurrin, Z. Ma, N. Messina, T.-N. Nguyen, L. Peˇska, L. Rossetto, L. Sauter, K. Schall, K. Schoeffmann, O. S. Khan, F. Spiess, L. Vadicamo, S. Vrochidis, Interactive video retrieval in the 14 age of effective joint embedding deep models: lessons from the 11th vbs, Multimedia Systems (2023). URL: https://doi.org/10.1007/s00530-023-01143-5. doi:10.1007/s00530-023-01143-5. [15] L. Rossetto, K. Schoeffmann, C. Gurrin, J. Lokoˇc, W. Bailer, Results of the 2024 video browser showdown, 2024. URL: https://arxiv.org/abs/2502.15683. arXiv:2502.15683. [16] F. Carrara, C. Gennaro, L. Vadicamo, G. Amato, Vec2doc: transforming dense vectors into sparse representations for efficient information retrieval, in: International Conference on Similarity Search and Applications, Springer, 2023, pp. 215–222. [17] W. Shang, K. Sohn, D. Almeida, H. Lee, Understanding and improving convolutional neural networks via concatenated rectified linear units, in: Proceedings of the 33rd International Conference on Machine Learning, volume 48 of ICML 2016, JMLR.org, 2016, pp. 2217–2225. [18] P. Zezula, G. Amato, V. Dohnal, M. Batko, Similarity search: the metric space approach, volume 32, Springer Science & Business Media, 2006. [19] V. Pestov, Indexability, concentration, and vc theory, Journal of Discrete Algorithms 13 (2012) 2–18. doi:10. 1016/j.jda.2011.10.002. [20] V. Mic, D. Novak, P. Zezula, Binary sketches for secondary filtering, ACM Transactions on Information Systems (TOIS) 37 (2018) 1–28. [21] N. Higuchi, Y. Imamura, V. Mic, T. Shinohara, K. Hirata, T. Kuboyama, Nearest-neighbor search from large datasets using narrow sketches., in: ICPRAM, 2022, pp. 401–410. [22] E. Ch´avez, K. Figueroa, G. Navarro, Effective proximity retrieval by ordering permutations, IEEE Transactions on Pattern Analysis and Machine Intelligence 30 (2008) 1647–1658. [23] L. Vadicamo, C. Gennaro, F. Falchi, E. Ch´avez, R. Connor, G. Amato, Re-ranking via local embeddings: a use case with permutation-based indexing and the nsimplex projection, Information Systems 95 (2021) 101506. [24] D. Novak, P. Zezula, Ppp-codes for large-scale similarity searching, Transactions on Large-Scale Data-and Knowledge-Centered Systems XXIV: Special Issue on Database-and Expert-Systems Applications (2016) 61– 87. [25] L. Vadicamo, R. Connor, E. Ch´avez, Query filtering using two-dimensional local embeddings, Information Systems 101 (2021) 101808. [26] C. Gennaro, G. Amato, P. Bolettieri, P. Savino, An approach to content-based image retrieval based on the lucene search engine library, in: International Conference on Theory and Practice of Digital Libraries, Springer, 2010, pp. 55–66. [27] G. Amato, P. Bolettieri, F. Carrara, F. Falchi, C. Gennaro, Large-scale image retrieval with elasticsearch, in: The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, 2018, pp. 925–928. [28] F. Carrara, L. Vadicamo, C. Gennaro, G. Amato, Approximate nearest neighbor search on standard search engines, in: Similarity Search and Applications: 15th International Conference, SISAP 2022, Bologna, Italy, October 5–7, 2022, Proceedings, Springer, 2022, pp. 214–221. [29] G. Salton, M. J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, USA, 1986. [30] H. Zamani, M. Dehghani, W. B. Croft, E. LearnedMiller, J. Kamps, From neural re-ranking to neural ranking: Learning a sparse representation for inverted indexing, in: Proceedings of the 27th ACM international conference on information and knowledge management, 2018, pp. 497–506. [31] D. Povey, G. Cheng, Y. Wang, K. Li, H. Xu, M. Yarmohammadi, S. Khudanpur, Semi-orthogonal low-rank matrix factorization for deep neural networks., in: Interspeech, 2018, pp. 3743–3747. [32] S. Bruch, F. M. Nardini, C. Rulli, R. Venturini, Efficient inverted indexes for approximate retrieval over learned sparse representations, in: Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2024, pp. 152–162. [33] J. Pennington, R. Socher, C. D. Manning, GloVe: global vectors for word representation, in: Empirical Methods in Natural Language Processing (EMNLP), 2014, pp. 1532–1543. [34] D. Dua, C. Graff, UCI machine learning repository, 2017. URL: http://archive.ics.uci.edu/ml. [35] C. Schuhmann, R. Beaumont, R. Vencu, C. Gordon, R. Wightman, M. Cherti, T. Coombes, A. Katta, C. Mullis, M. Wortsman, et al., Laion-5b: An open large-scale dataset for training next generation imagetext models, Advances in Neural Information Processing Systems 35 (2022) 25278–25294. [36] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, et al., Learning transferable visual models from natural language supervision, in: International conference on machine learning, PMLR, 2021, pp. 8748–8763. [37] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Doll´ar, C. L. Zitnick, Microsoft coco: Common objects in context, in: Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13, Springer, 2014, pp. 740–755. [38] B. Paria, C.-K. Yeh, I. E. Yen, N. Xu, P. Ravikumar, B. P´oczos, Minimizing flops to learn efficient sparse representations, arXiv preprint arXiv:2004.05665 (2020). [39] M. Douze, A. Guzhva, C. Deng, J. Johnson, G. Szilvasy, P.-E. Mazar´e, M. Lomeli, L. Hosseini, H. J´egou, The faiss library (2024). arXiv:2401.08281. 15