Attention in Large Language Models Yields Efficient Zero-Shot Re-Rankers

We sincerely appreciate the reviewer's recognition of our experiment setup, clear analyses, and writing quality. We address the concerns as follows:

W1/Q1 Missing important unsupervised baseline UPR:

We acknowledge that UPR is also a zero-shot re-ranking method and have cited UPR in the related works section. However, we argue that UPR is not a necessary baseline as it has shown to significantly underperform RankGPT 3.5 [1] and ICR (Mistral 7B) can already match the performance of RankGPT 3.5.

W2/Q2 The impact of document order:

We agree with the reviewer that the robustness to document order is an important aspect of a re-ranking method. In our paper, we did mention ICR first reverses the document order returned by the retriever and concatenates them in the prompt (line 194-196), which works better than using the original order from the retriever empirically. When using randomly shuffled order, ICR has better performance than RankGPT with lower standard deviation. Please refer to the response to reviewer d1gB’s W2/Q1 for a quantitative comparison.

W3 Can ICR enhance the performance of stronger retrievers for single-hop evaluations?

Yes, ICR also works with other retrievers such as ColBERTv2. We follow existing work [1,2,3] and choose BM25 as the base retriever in the paper. To address the reviewer’s concern, we show the re-ranking performance (nDCG@10) on Trec-covid and SciFact using ColBERTv2’s top-100 results below:

As shown in the table, using dense retrievers such as ColBERTv2 may not always yield better performance. ICR can also improve the quality of retrieval results returned by ColBERTv2. We will add more comprehensive results in the revised paper.

Q3 Why is the top20 instead of top100 utilized for multi-hop evaluations?

So far, multi-hop retrieval has gained much less attention in the community. Our multi-hop evaluation follows earlier works [4,5] which use the documents for all questions as the retrieval corpus. The total number of supporting documents and distractors for each question in these datasets is no more than 20. The number of supporting documents are also relatively small (2-4 for MuSiQue and 2WikiMultiHopQA, and 2 for HotpotQA). Therefore, we believe re-ranking top-20 retriever outputs and reporting recall@2 and recall@5 is a reasonable experimental setup.

We hope our response can address the reviewer’s main concerns and respectfully request adjustment to the evaluation.

[1] Sun, Weiwei, Lingyong Yan, Xinyu Ma, Shuaiqiang Wang, Pengjie Ren, Zhumin Chen, Dawei Yin, and Zhaochun Ren. "Is ChatGPT good at search? investigating large language models as re-ranking agents." arXiv preprint arXiv:2304.09542 (2023).

[2] Pradeep, Ronak, Sahel Sharifymoghaddam, and Jimmy Lin. "Rankvicuna: Zero-shot listwise document reranking with open-source large language models." arXiv preprint arXiv:2309.15088 (2023).

[3] Qin, Zhen, Rolf Jagerman, Kai Hui, Honglei Zhuang, Junru Wu, Le Yan, Jiaming Shen et al. "Large Language Models are Effective Text Rankers with Pairwise Ranking Prompting." In Findings of the Association for Computational Linguistics: NAACL 2024, pp. 1504-1518. 2024.

[4] Gutiérrez, Bernal Jiménez, Yiheng Shu, Yu Gu, Michihiro Yasunaga, and Yu Su. "HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Models." arXiv preprint arXiv:2405.14831 (2024).

[5] Trivedi, Harsh, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. "Interleaving retrieval with chain-of-thought reasoning for knowledge-intensive multi-step questions." arXiv preprint arXiv:2212.10509 (2022).

We are excited that the reviewer deems our motivation "interesting" and our method "technically sound" and "effective". We present additional explanations on our intuition below:

Weakness/Q4: lack explanations for more high-level intuition and ICR’s relationship with instruction-following.

Why does the proposed method work intuitively?

The intuition behind our method is based on the reasonable assumption that, in a well-trained LLM, more relevant documents will receive more attention when conditioned on the semantics of the query, given their strong QA and IE performance. On the other hand, when the query is content-free, the LLM should assign approximately equal attention to all documents. Therefore, we propose a calibration method to capture the intrinsic biases and remove them from the ranking score, which proves to be effective.

What are the advantages and disadvantages of the proposed method intuitively?

• Advantages: (1) ICR gets rid of the generation process which leads to high efficiency. (2) ICR can leverage various internal signals related to re-ranking, which might be overlooked in the text generation process, as detailed in Section 5.3. (3) ICR is an unsupervised and zero-shot method, making it easily applicable to any decoder-only LLMs.

• Disadvantages: ICR relies on the attention pattern of the base LLM, thus its success highly depends on the quality of the base LLM. On tasks where training data is easily obtainable, ICR could underperform supervised methods.

Why does the proposed method work well although the model’s instruction following ability is poor?

We believe that good ‘instruction following’ ability takes two assumptions: (1) the LLM can understand the instruction and carry out required computation internally. (2) The LLM must be able to reflect the result of (1) through text generation, usually in a specialized format. Generative re-ranking methods require strong capabilities in both (1) and (2). However, ICR frees the LLM from the burden of (2) and reveals potentially hidden re-ranking capacities. This is best illustrated by the drastic improvement on Mistral 7B, whose limited generation ability results in low ranking success rate with RankGPT (usually <20%).

Q1 Why use "N/A" as the special token?

We would like to clarify that "N/A" is just a string, not a special token added to the LLM’s vocabulary. We follow Contextual Calibration [1] and use "N/A" in the paper. Empirically, we do not see a significant difference between using "N/A" and other calibration queries, such as "None", as long as they are content-free.

Q2 High-level intuition of $s_{d_i}$, can it be considered as distance between the actual query and calibration query?

We thank the reviewer for bringing up this interesting perspective. As explained in the paper, the ranking score $s_{d_i}$ measures the change of attention weights received by document $i$ conditioned on query semantics. We agree with the reviewer that $s_{d_i}$ can reflect the semantic differences between two queries based on document $i$. However, since $s_{d_i}$ is dependent on the candidate documents, it does not qualify as a distance metric for queries mathematically. Nevertheless, this looks like a very interesting direction for future research.

Q3 Why sharing KV cache is effective when you put query tokens at the end?

This is because when we put the query tokens at the end of the prompt, document token representations are not conditioned on the query and stay the same for different queries. We can therefore reuse the document tokens’ KV cache when processing different queries, instead of encoding all prompt tokens from scratch. In practice, the overhead is only 30%, rather than 100% for processing the two queries.

Q5 How does the overall distribution look like in terms of calibration scores?

We provide detailed analysis and illustration for calibration scores in Section 5.1 of the paper. We are also happy to address more specific questions regarding calibration scores.

We hope our response can help the reviewer better understand the intuitions behind ICR’s design and will add more explanations to the revised paper for better readability.

[1] Zhao, Zihao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. "Calibrate before use: Improving few-shot performance of language models." In International conference on machine learning, pp. 12697-12706. PMLR, 2021.

I agree with the reviewer NMvY on the needs of the API calls. The paper claims to reduce time complexity from O(N) to O(1), it needs to be revisited and think carefully. Changing the score because of that.

We are grateful that the reviewer finds the proposed method "novel" and "effective". Below, we address the reviewer’s concern on experimental setup and further analysis.

W1 Although the paper compares ICR with RankGPT, highlighting improvements, it would be strengthened by comparisons with more methods, especially other zero-shot listwise methods.

We appreciate the reviewer’s suggestion on comparing ICR with supervised alternatives. The focus of ICR is presenting a novel method for efficient zero-shot re-ranking using decoder-only LLMs, which is also applicable to supervised fine-tuned LLMs such as RankVicuna. Considering the sizable efficiency improvement, we believe comparing with RankGPT can already support our main claims, as other methods usually further incur additional cost in training or inference time.

To resolve the reviewers’ concern, we present a comparison with supervised (RankVicuna [1]) and listwise (setwise re-ranking [2]) approaches the reviewer mentioned in the following table:

*The performance of the setwise method [2] is copied from its paper.

We notice that RankVicuna and setwise methods show better performance on NFCorpus, DBPedia, and Trec-Covid, as expected. Both methods incur additional cost in training (RankVicuna) or inference time (Setwise methods). Similar to our findings in the paper, ICR shows impressive performance on SciFact, outperforming supervised methods without specialized training. We will include this comparison in the revised version for comprehensiveness.

W2 A clear comparison between ICR and fine-tuning (FT) methods, highlighting the performance gap and cases where fine-tuning might be preferable:

We acknowledge that supervised re-ranking methods may have stronger performance when data and compute for training is available. As discussed above, we find ICR to still excel in more challenging tasks that demand reasoning, such as SciFact. 

Additionally, we highlight the following advantages of ICR compared to fine-tuning methods:

• Length Generalization: With fine-tuning methods such as RankVicuna, we usually observe a decline in performance when the number of documents increases. As noted by RankZephyr [3], fine-tuned models struggle to generalize to sliding window sizes unseen during training, even when the context window of the LLM is long enough. In comparison, by leveraging the attention patterns in general QA or IE tasks which are relatively sufficiently trained during instruction tuning, ICR can make full use of the context window of LLMs and show improved performance (Figure 3 in our manuscript).

• Ease of Use: To keep a model up-to-date, fine-tuned methods need to retrain a new model when a stronger base model is developed or when better training data is constructed, leading to extra cost in development. In contrast, ICR is an unsupervised and inference-time method that can be applied to any new LLMs without modification. Therefore, ICR can effortlessly leverage the ever-growing capabilities of latest LLMs.

We will add a discussion on supervised methods in the revised version.

[1] Pradeep, Ronak, Sahel Sharifymoghaddam, and Jimmy Lin. "Rankvicuna: Zero-shot listwise document reranking with open-source large language models." arXiv preprint arXiv:2309.15088 (2023).

[2] Zhuang, Shengyao, Honglei Zhuang, Bevan Koopman, and Guido Zuccon. "A setwise approach for effective and highly efficient zero-shot ranking with large language models." In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 38-47. 2024.

[3] Pradeep, Ronak, Sahel Sharifymoghaddam, and Jimmy Lin. "RankZephyr: Effective and Robust Zero-Shot Listwise Reranking is a Breeze!." arXiv preprint arXiv:2312.02724 (2023).

We are delighted that reviewer NMvY finds our focus "crucial", our writing "well-crafted" and the proposed method "versatile". We will clarify ICR’s claim of $O(1)$ forward pass complexity and address other questions below.

W1/Q1 ICR’s claim of $O(1)$ forward passes

We would like to kindly remind reviewer NMvY that the $O(N)$ forward passes required by LLM-based generative re-ranking methods are not caused by the sliding window strategy alone. Applying a sliding window mechanism to any listwise re-ranking method will introduce a $O(N/l)$ factor to complexity where $l$ is the stride.  Since the sliding window mechanism is not a necessary part of any re-ranking method, we do not consider it when comparing complexity in the paper.

Our method ICR can also be used with a sliding window strategy to handle more documents. Given the practical constraint on the context length of LLMs, we present the following complexity comparison with and without using sliding window when re-ranking $N$ documents:

• Without sliding window: Let us first assume an LLM has infinite context length. An LLM generates one token in one forward pass. Consequently, for an LLM to generate a ranking list of N document identifiers, which has $O(N)$ tokens, it requires $O(N)$ forward passes. In this case, ICR only requires two forward passes, one with the calibration query and another with the actual query, to get the ranking scores and calibration scores for all documents. Therefore, ICR’s complexity is $O(1)$.

• With sliding window: In the case of using a sliding window of size $k$ and stride $l$, a total of $(N-k)/l+1$ iterations are needed. The LLM needs to generate $O(k)$ tokens in each iteration, resulting in a total of $O(Nk/l)$ forward passes. In this case, ICR also needs $O(N/l)$ sliding window iterations and $O(1)$ forward passes in each iteration, leading to a total of $O(N/l)$ forward passes. Therefore, ICR is still more efficient than generative methods by a factor of $O(k)$, which is commonly set to 20 in existing literature. We argue that this is still not a trivial speed up. 

In practice, we find ICR to be much more memory efficient than RankGPT due to the absence of text generation. Therefore, ICR could support a larger window size compared to RankGPT with the same hardware. It is also worth noting that, in addition to the limited context window, an important reason that generative methods require a sliding window mechanism is that LLMs often show a decline in generative capabilities as the context length grows. This is discussed in detail in the response to reviewer d1gB’s W2.

W2 ICR can’t be used with commercial LLMs:

As the reviewer noted, “this is less of a technical issue but rather a commercial decision”. ICR is theoretically compatible with any decoder-only transformer LLMs by design. Companies who own a commercial LLM can choose to adopt ICR if they find it useful, just like what they have probably been doing for many public research ideas.