IRGen: Generative Modeling for Image Retrieval

(4) We add comparison to a baseline that uses PQ for tokenizer instead of RQ. The superior performance demonstrates that sequence matters in our autoregressive training.

(5) We compare with recent supervised deep quantization methods on ImageNet, including the state-of-the-art methods ADSVQ and DPQ. Notably, these methods use 100 classes from ImageNet, as indicated in their original papers. For fair comparison, we reran our model for 100 classes, whereas the results in our paper are based on the full 1000 categories of ImageNet. The table below illustrates the superiority of our approach.

[1] Klein, Benjamin, and Lior Wolf. "End-to-end supervised product quantization for image search and retrieval." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2019.

[2] Zhou, Chang, Lai Man Po, and Weifeng Ou. "Angular deep supervised vector quantization for image retrieval." IEEE Transactions on Neural Networks and Learning Systems 33.4 (2020): 1638-1649.

[3] Liu, Bin, et al. "Deep triplet quantization." Proceedings of the 26th ACM international conference on Multimedia. 2018.

[4] Liu, Haomiao, et al. "Deep supervised hashing for fast image retrieval." Proceedings of the IEEE conference on computer vision and pattern recognition. 2016.

[5] Cao, Zhangjie, et al. "Hashnet: Deep learning to hash by continuation." Proceedings of the IEEE international conference on computer vision. 2017.

4. Differentiable indexing in our approach means non-exhaustive search, whereas deep quantization methods use differentiable index for embedding compression. Our focus on image retrieval marks the first effort. We introduce a novel semantic tokenizer specifically designed for image retrieval. We add a direct comparison using NCI's hierarchical k-means tokenizer versus ours, emphasizing the effectiveness of our proposed semantic tokenizer.

5. There is a serious misunderstanding. Our model does not use image pair codes for computing the loss, as indicated in your comment. Instead, we aim to generate the codes for the nearest neighbor corresponding to the given input. The distinctions between our model and previous deep quantization methods have been elaborated in the response above. Our more end-to-end property stems from that we directly find the nearest neighbor through the learned generative model, compared to deep quantization that needs to calculate distance between query and each database's codes. When only the top-1 sample is required, beam search is unnecessary, and generation can be performed by straightforwardly selecting the identifier with the highest probability, ensuring no train-test discrepancy. However, for top-K retrieval, we leverage beam search with a configured beam size of K. In this scenario, a train-test discrepancy emerges. One potential solution is the further integration of beam search into the training process, a direction that is worth pursuing.

6. It appears that certain experiments presented in the paper may have been overlooked. The contributions of the two modules have been examined, and please refer to point (2) in the 3rd response. We have conducted a mAP comparison on two million-scale datasets, ImageNet and Places365, as in Table 3 of the paper. Regarding the remaining three datasets in Table 1 and 2, a direct mAP or mAP@100 comparison is not reasonable due to the limited number of ground truth samples, all less than 100 for each query. It is important to note that previous works, including the compared baselines, only report recall@K metric in their experiments. To provide a comprehensive comparison, we reported precision@K metric in our paper. Furthermore, we have evaluated on three widely used benchmarks and two million-scale datasets. The classical retrieval datasets, Oxford and Paris, are relatively small scale, with 5062 images for Oxford and 6412 images for Paris. These datasets are commonly employed for zero-shot retrieval scenario, particularly for pre-training models. Notwithstanding, we add comparison to Paris, which consistently validates the effectiveness of our proposed method.

Thank you for taking the time to review our paper, but there exists serious misunderstanding about our paper.

First, we address the points you mentioned in the weaknesses part.

1. Figure 1 illustrates our AR training methodology that given an input image, we feed it to our transformer (encoder and decoder) and the output is supervised by the image identifier that is obtained from the query's nearest neighbor through semantic image tokenizer (which is trained before AR model). To address any misunderstandings, we kindly request more specific details regarding your concerns. We itemize our contribution as follows for clarity: (1) To the best of our knowledge, our work represents the first effort in employing a sequence-to-sequence generative model to address image retrieval in a fully end-to-end manner that directly generates the nearest neighbor's identifier givent the query. (2) We introduce a semantic image tokenizer explicitly designed for image retrieval to obtain image identifiers, facilitating autoregressive training. It is essential to note that this tokenizer differs significantly from previous quantization models, as our identifier solely represents the image and is not employed for distance computation, as is the case in quantization. (3) Extensive experiments show that our approach exhibits substantial improvements in results, achieving new state-of-the-art results. We have demonstrated its scalability to million-scale datasets and provided throughput number, showcasing its near-real-time performance.

2. We provide a more in-depth discussion comparing our approach with prior joint learning methods. In the existing literature, early methods predominantly focused on three distinct aspects: embedding learning for enhancing search accuracy, embedding compression (quantization/hashing) for reducing memory cost, and clustering (often involving quantization) or neighborhood graphs for improving search efficiency. However, as each of these components is essential for a large-scale retrieval system, integrating individual efforts may result in suboptimal solutions. Consequently, there has been a growing interest in studying joint learning. However, all these prior works (please refer to our general response for references to prior works) focus on end-to-end training of encoding and compression together while overlooking the indexing part (meaning non-exhaustive search), which is challenging to formulate as differentiable. They leverage quantization (compression index) for ANN search (with distance approximation) but still rely on linear scan in their experiments. In contrast, our approach reframes retrieval as a completely novel end-to-end task, eliminating explicit distinctions between embedding, compression, and indexing. Our method involves offline storage of image identifiers acquired from the proposed tokenizer. Notably, this differs conceptually from quantization, as we do not use the tokenized identifier for distance comparison as in quantization. Retrieving a query's nearest neighbor in our method only involves passing the query through the autoregressive (AR) model. We will incorporate this discussion into the final paper.

3. There is a serious misunderstanding that needs clarification. The codes generated by our system are intended to serve as image identifiers, not quantization codes as suggested in your comment. It's important to note that these codes are not utilized for distance computation, as is the case with quantization. Moreover, our model does not rely on the codes or codebooks during the retrieval process. Instead, it dynamically generates the codes through the autoregressive decoder based on the provided query. This methodology diverges substantially from conventional deep quantization methods. Then we address the concerns you raised in the comment. (1) We have itemized our contribution in the response above. (2) To assess the efficacy of the semantic image tokenizer, we have provided ablations in Table 5 of the paper, which involves ablating the image identifier using random IDs or hierarchical k-means IDs. For AR decoder, we have demonstrated its superior performance compared to FT-CLIP with linear scan, as indicated in Table 1 and Table 2 of the paper. Furthermore, we add additional comparison with a baseline that directly utilizes codes from the semantic tokenizer for image retrieval, akin to how conventional quantization performs retrieval. As anticipated, given the information loss inherent in quantization, this method is naturally inferior to linear scan and, consequently, to our proposed method.

(3) The distinctions between our method and previous approaches, such as deep quantization, have been elucidated in the response above.

We appreciate the time you took to review our paper.

First, we address the five points you mentioned in the weaknesses part.

1. Image retrieval is a high-level vision task, akin to extreme classification problem, reliant on a global understanding of the image, where global features are pivotal. Our method proves effective not only in general retrieval, such as ImageNet, but also excels in fine-grained tasks like Inshop clothes retrieval, CUB retrieval, and car retrieval, showcasing its ability to capture necessary details for fine-grained search using global features. Recognizing scenarios where similarity is defined over small image areas requiring spatial information, we suggest a solution involving a pre-processing step that detects these important regions. For instance, person re-identification is such a case utilizing detection before search. Alternatively, incorporating both global and local features ensures a comprehensive image representation but may entail complex models with increased computational demands. Striking a balance between efficiency and efficacy is a longstanding challenge in retrieval. This paper has successfully present a novel approach that is conceptually different from previous joint learning methods, and demonstrate state-of-the-art performance on widely used benchmarks with near-real-time inference speed.

2. First, the proposed prefix tree only contains valid codes and thus eliminates the need of validating each generated image identifier, largely enhancing the inference speed. We then provide a comprehensive comparison of model capacity and inference cost in the table below, focusing on the million-scale ImageNet dataset. It is crucial to emphasize that a retrieval system's storage considerations extend beyond just the model; it must also store features for all database vectors, constituting a substantial portion of storage requirements, especially in the context of a large database. While compression can alleviate this concern, the performance is severely compromised due to quantization. In terms of inference cost, our CPU inference cost is 0.30s per image, which is not orders of magnitude larger compared to FT-CLIP with linear scan. Although FT-CLIP with SPANN lowers the inference cost, it comes at the expense of a substantial drop in performance. Our GPU inference cost, tested on a Tesla P100 PCIe 16GB GPU, is 0.037s/image, which is near-real-time, considering practical retrieval times at the order of 10 milliseconds. Moreover, our approach demonstrates competitive performance compared to FT-CLIP with linear scan, and significantly reduces the memory cost. For inference speed, we anticipate that the prevalent reliance on GPUs for generative models will swiftly lead to newer GPU generations with increased processing power, more efficient memory management, and improved hardware support, thereby enhancing the inference speed of our autoregressive retrieval. Additionally, our model, being GPT-based, can leverage rapidly developed acceleration techniques designed for GPT.

3. Our current objective is to showcase the effectiveness of the proposed generative based model. We have conducted experiments on three widely used retrieval benchmarks, and show the scalability on other two wellknown million-scale datasets. Further scaling to handle billion-scale datasets poses a considerable challenge due to the substantially increased demand for resources, including storage and computation, which currently exceeds our available capacity. In future work, we may address billion-scale scenario with a hybrid solution where billions of images can be clustered into millions of semantic clusters, and our proposed model IRGen can then be utilized to retrieve the relevant cluster identifiers. This approach would enable us to leverage current success in million-scale datasets and handle billion-scale datasets in a more efficient manner.

I thank the authors for preparing the rebuttal and answering my comments. After reading authors' reply and other reviews, I am keeping my original rating. Specifically, the advantage of prefix tree and the formulation is still not clear to me. Additionally, there are other concerns requiring the paper to be updated to see how the updated manuscript would look like. Furthermore, the model diagram doesn't contain all the proposed components, which in my opinion is necessary.

Thank you for your valuable feedback.

First, we address the points you mentioned in the weaknesses part.

1. We offer a detailed comparison of our approach with previous joint learning methods. Early methods in the literature primarily concentrated on three key aspects: embedding learning to enhance search accuracy, embedding compression (quantization/hashing) to reduce memory cost, and clustering (often involving quantization) or neighborhood graphs to improve search efficiency. However, integrating these essential components individually may lead to suboptimal solutions for large-scale retrieval systems. As a result, there is a growing interest in the study of joint learning. However, all prior works (please refer to our general response for references to prior works) focus on end-to-end training of encoding and compression together while overlooking the indexing part (meaning non-exhaustive search), which is challenging to formulate as differentiable. They leverage quantization (compression index) for ANN search (with distance approximation) but still rely on linear scan in their experiments. In contrast, our approach reframes retrieval as a completely novel end-to-end task, eliminating explicit distinctions between embedding, compression, and indexing. Our method involves offline storage of image identifiers acquired from the proposed tokenizer. Notably, this differs conceptually from quantization, as we do not use the tokenized identifier for distance comparison as in quantization. Retrieving a query's nearest neighbor in our method only involves passing the query through the autoregressive (AR) model.

2. Thank you for acknowledging our results with million-scale datasets. Handling billion-scale datasets presents a significant challenge, given the heightened resource demands, including storage and computation, that currently surpass our available capacity. Our primary goal is to highlight the effectiveness of the proposed generative model. To demonstrate this, we conducted experiments on three retrieval benchmarks and two additional million-scale datasets. In future endeavors, we aim to address the billion-scale scenario through a hybrid solution. This involves clustering billions of images into millions of semantic clusters, allowing our model IRGen to efficiently retrieve relevant cluster identifiers. This approach would enable us to handle billion-scale datasets in a more efficient manner.

Then we answer the questions below.

1. Refer to the weaknesses section for an in-depth explanation. The mentioned example also involves joint learning of encoding and compression (referred to as embedding index in the paper), relying on linear scan search in their experiments. In contrast, our approach defines retrieval as a novel end-to-end task, directly retrieving a query's nearest neighbor by passing through the AR model, without explicit modeling for embedding, compression, and indexing.

2. Traditional methods tend to witness a decline in precision with an increasing retrieval set size (K). While they initially achieve high precision by prioritizing the most relevant images in the top ranks, the precision drops rapidly as K grows due to the retrieval of irrelevant and confusing images. This indicates a struggle to retrieve harder positive images, often necessitating a reranking stage after the initial retrieval. In contrast, our AR decoder consistently retrieves relevant samples as the retrieval list lengthens. Our top-K performance even exhibits a slight increase with a larger K, showcasing its proficiency in handling challenging examples. This capability can be attributed to our approach of randomly sampling codes from images in the same class as the query image during training, enhancing the model's capacity to handle difficult samples. This advantage potentially mitigates the need for a post-reranking stage in our model to some extent.

3. In scenarios where more new data come in and the distribution of gallery data has changed drastically, all existing data-dependent retrieval methods, including embedding model in image retrieval as well as dense retrieval methods in document retrieval, have to re-train the model and re-construct the data index. Essentially, dynamic updates only support a small number of new data that do not substantially alter the distribution. Our experiments have demonstrated the capability of handling this case through adding new, unseen data within the same class, showcasing the model's adaptability to minor distribution changes. Nevertheless, it's important to highlight that data-dependent models continue to be preferred due to their superior performance. In future work, there is a potential extension of IRGen towards an adaptive structure capable of capturing evolving distribution during training. For our experiment, the other baseline models employed the same treatment for fair comparison, and we will provide further clarification in the revised version.

Thank you for your detailed review.

First, we address the three points you mentioned in the weaknesses part.

1. The procedure begins by defining a beam size, denoted as K in our case. Initially, the beam comprises the start-of-sequence token, and the algorithm extends the current set of candidate sequences by considering the next potential tokens in the sequence. For each candidate sequence, the algorithm outputs probabilities for multiple potential next tokens and adds them to the beam. The expanded set of sequences is then scored based on the probabilities assigned by the model. The top-k sequences with the highest scores are retained, while the others are discarded. This selection process, which can be implemented with a priority queue in linear time with the candidate list size, is repeated until the end-of-sequence token is encountered. In the case of beam search with a prefix tree, the search process is constrained to consider only valid next tokens, as determined by the prefix tree, rather than all the possible next tokens. This constraint ensures that the search process results in valid image identifiers corresponding to specific images in the dataset. We will provide a detailed explanation of the beam search algorithm in the Appendix.

2. We find the noted weakness a bit perplexing, particularly in the absence of specific details regarding the particular benefit that may not be enjoyed by retrieval with an autoregressive approach. Our interpretation is based on our best understanding of the context. Maximum inner-product search (MIPS) pertains to a similarity search problem where the objective is to efficiently locate the data point in a collection that maximizes the inner product with a given query vector. Nonetheless, if the ultimate goal is to retrieve similar data, our methodology allows us to formulate and address this challenge optimally in an end-to-end manner, rather than a two-step process involving initial feature embedding followed by maximum inner-product search. We acknowledge the potential scenarios where data embedding becomes imperative, such as compact feature learning for transmission purposes. In such cases, one could also treat the embedded data as input and train an autoregressive model to identify the query's nearest neighbor, bypassing the tedious tuning over the joint integration of compression and indexing.

3. We provide a comprehensive comparison of model capacity and inference cost in the table below, focusing on the ImageNet dataset. It is crucial to emphasize that a retrieval system's storage considerations extend beyond just the model; it must also store features for all database vectors, constituting a substantial portion of storage requirements, especially in the context of a large database. In terms of inference cost, our CPU inference cost is 0.30s per image, which is not orders of magnitude larger compared to FT-CLIP with linear scan. Although FT-CLIP with SPANN lowers the inference cost, it comes at the expense of a substantial drop in performance. Our GPU inference cost, tested on a Tesla P100 PCIe 16GB GPU, is 0.037s/image, which is near-real-time, considering practical retrieval systems at the order of 10 milliseconds. Moreover, our approach demonstrates competitive performance compared to FT-CLIP with linear scan, and significantly reduces the memory cost. We anticipate that the prevalent reliance on GPUs for generative models will lead to newer GPU generations with increased processing power, more efficient memory management, and improved hardware support, thereby enhancing the inference speed of our autoregressive retrieval. Additionally, our model, being GPT-based, can leverage rapidly developed acceleration techniques designed for GPT. Our model also opens avenues for the integration of GPT in the development of more intelligent and context-aware information retrieval and generation systems.

2. We add a comparison with recent supervised deep quantization methods on ImageNet, including the state-of-the-art methods ADSVQ and DPQ. Notably, these methods exclusively utilize 100 classes from ImageNet, as indicated in their original papers, making it a substantially easier case. To ensure a fair comparison, we reran our model for 100 classes, whereas the results in our paper are based on the full 1000 categories of ImageNet. The table below illustrates the superiority of our approach.

[1] Klein, Benjamin, and Lior Wolf. "End-to-end supervised product quantization for image search and retrieval." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2019.

[2] Zhou, Chang, Lai Man Po, and Weifeng Ou. "Angular deep supervised vector quantization for image retrieval." IEEE Transactions on Neural Networks and Learning Systems 33.4 (2020): 1638-1649.

[3] Liu, Bin, et al. "Deep triplet quantization." Proceedings of the 26th ACM international conference on Multimedia. 2018.

[4] Liu, Haomiao, et al. "Deep supervised hashing for fast image retrieval." Proceedings of the IEEE conference on computer vision and pattern recognition. 2016.

[5] Cao, Zhangjie, et al. "Hashnet: Deep learning to hash by continuation." Proceedings of the IEEE international conference on computer vision. 2017.

3. In Figure 5 of the paper, we present a throughput comparison on the Inshop dataset. The table below offers a comprehensive assessment of model capacity and inference cost, focusing specifically on the ImageNet dataset. It is crucial to emphasize that a retrieval system's storage considerations extend beyond just the model; it must also store features for all database vectors, constituting a substantial portion of storage requirements, especially in the context of a large database. While compression can alleviate this concern, the performance is severely compromised due to quantization. In terms of inference cost, our CPU inference cost is 0.30s per image, which is not orders of magnitude larger compared to FT-CLIP with linear scan. Although FT-CLIP with SPANN lowers the inference cost, it comes at the expense of a substantial drop in performance. Our GPU inference cost, tested on a Tesla P100 PCIe 16GB GPU, is 0.037s/image, which is near-real-time, considering practical retrieval systems at the order of 10 milliseconds. Moreover, our approach demonstrates competitive performance compared to FT-CLIP with linear scan, and significantly reduces the memory cost. For inference speed, we anticipate that the prevalent reliance on GPUs for generative models will lead to newer GPU generations with increased processing power, more efficient memory management, and improved hardware support, thereby enhancing the inference speed of our autoregressive retrieval. Additionally, our model, being GPT-based, can leverage rapidly developed acceleration techniques designed for GPT.

4. We itemize our contribution as follows: (1) To the best of our knowledge, our work represents the first effort in employing a sequence-to-sequence generative model to address image retrieval in a fully end-to-end manner that directly generates the nearest neighbor's identifier givent the query. (2) We introduce a semantic image tokenizer explicitly designed for image retrieval to obtain image identifiers, facilitating autoregressive training. It is essential to note that this tokenizer differs significantly from previous quantization models, as our identifier solely represents the image and is not employed for distance computation, as is the case in quantization. (3) Extensive experiments show that our approach exhibits substantial improvements in results, achieving new state-of-the-art results. We have demonstrated its scalability to million-scale datasets and provided throughput number, showcasing its near-real-time performance.