PRP -Graph: Pairwise Ranking Prompting to LLM s with Graph Aggregation for Effective Text Re-ranking (2024)

Abstract: Pairwise Ranking Prompting (PRP) demonstrates impressive effectiveness in zero-shot document re-ranking tasks with large language models (LLMs). However, in the existing methods, PRP only outputs the same label for the comparison results of different confidence intervals without considering the uncertainty of pairwise comparison, which implies an underutilization of the generation probability information of LLMs. To bridge this gap, we propose PRP-Graph, a novel pairwise re-ranking approach, based on a refined scoring PRP unit that exploits the output probabilities of target labels to capture the degree of certainty of the comparison results. Specifically, the PRP-Graph consists of two stages, namely ranking graph construction and ranking graph aggregation. Extensive experiments conducted on the BEIR benchmark demonstrate the superiority of our approach over existing PRP-based methods. Comprehensive analysis reveals that the PRP-Graph displays strong robustness towards the initial ranking order and delivers exceptional re-ranking results with acceptable efficiency. Our code and data are available at https://github.com/Memelank/PRP-Graph.

## introduction large language models (llms) such as gpt-3 @xcite , flant5 @xcite , and palm @xcite have demonstrated exceptional performance across a diverse array of natural language processing tasks within the zero-shot paradigm @xcite . consequently, these llms have been adapted for zero-shot document ranking tasks, showcasing remarkable capabilities @xcite @xcite . the methodologies utilized llms in zero-shot ranking tasks focus on prompting the llms to provide relevance estimations for a query along with candidate documents @xcite . in both basic and scoring prp units, two compared documents d i and d j are fed into llm twice using prompt texts u(q, d i , d j ) and u(q, d j , d i ). different from just obtaining determined passage labels (namely, d i ) in basic prp unit, prp-graph with scoring prp unit captures the uncertainty (namely, s(d @xmath0, and further employs a graph aggregation strategy to obtain the final ranking. notably, recent research has shown that pairwise ranking prompting (prp) is effective for zeroshot re-ranking with moderate-sized, open-sourced llms and can produce state-of-the-art re-ranking performance with simple prompting and scoring mechanism @xcite . prp involves building a pairwise prompting to determine which of two documents is more relevant to query with the help of llms, then using the prp as a basic scoring unit to serve different ranking mechanisms. despite their effectiveness, we posit that existing prp does not fully capitalize on the potential of llms. firstly, current practices utilize prp to simply ascertain the more relevant document relative to the query, disregarding a more granular analysis of generation probabilities, which represent the llm's confidence in its judgment. secondly, the inherent sensitivity of llms to the text orders in prompt @xcite has led to the verification of consistency by alternating the pairwise order of documents within the prompt and consulting the llm twice. only consistent outputs from both inquiries are valid, which does not take full advantage of the capabilities of llms. finally, the comparison selection strategies in use, which are derived from sorting algorithms, lack the flexibility to enhance ranking quality through increased comparisons and are highly sensitive to the sequence order of input documents. to this end, we propose scoring pairwise ranking prompt (prp) unit and a novel pairwise approach, termed prp-graph, building upon the scoring prp unit's performance. as illustrated in figure 1 , unlike the current prp unit @xcite , which yields discrete judgments, our scoring prp unit captures more granular correlation information for each pairwise order in prompt through the generation probability of judgment labels by llms, thus effectively utilizing the generative capability and order sensitivity of llms. prp-graph operates in two phases. the first phase continuously identifies document pairs for comparison, representing them as vertices connected by bidirectional edges within a ranking graph. the weights of vertices and edges are iteratively refined based on the scoring prp unit's outputs. the second phase aggregates these signals across the ranking graph to produce a cohesive final document ranking that encapsulates the entire graph's sorting information. we conduct experiments to evaluate our proposed prp-graph on flan-t5 models @xcite . our results on beir @xcite indicate that prp-graph surpasses existing prpbased zero-shot re-ranking techniques. further ablation studies confirm the effectiveness of individual components within our method, and our analyses demonstrate the influence of comparison rounds on prp-graph's performance as well as its robustness against initial ranking order. our contributions are threefold: 1) we introduce the prp-graph, a novel pairwise approach underpinned by an innovative scoring prp unit that exploits the full potential of llms by leveraging the probability scores from pairwise ranking prompts. 2) benefiting from the graph-based nature of prp-graph, which relies less on the initial rankings produced by the first-stage retriever, it demonstrates a more effective interpolation with bm25 than current prp-based methods. 3) extensive experimental validation shows that our prp-graph method significantly outperforms contemporary approaches, establishing it as a superior choice for zero-shot document re-ranking tasks. ## preliminaries as aforementioned, several recent text re-ranking approaches implement pairwise ranking prompting (prp) as an atomic ranking unit to extract specific textual labels via the generative capabilities or logit outputs of llms. this section provides an initial overview of the prp construct, subsequently outlining the landscape of text re-ranking approaches that integrate the basic prp unit. basic prp unit. the prompt in prp is shown in figure 2 (a), wherein it asks the llm to answer which document is more relevant to the query. akin to @xcite , we denote this prp prompt text as u(q, d i , d j ) for a query q and two documents d i and d j . as seen in figure 2 (b), the basic prp unit, applied in existing work @xcite , is only designed to obtain an answer to a question in the prompt. specifically, there are two modes to obtain the answer, the first is generation mode wherein llm directly generates the passage label ("passage a" or "passage b"), and the second is scoring mode wherein the loglikelihood of llm generates the target label is used for a scoring comparison for the answer. as it is known that llms can be sensitive to text orders in the prompt @xcite , the order of these two documents within the prompt will be swapped and inquire the llm twice, namely u(q, d i , d j ) and u(q, d j , d i ). only if the output of two inquiries is consistent, the llm's judgment will have a clear preference as shown in figure 2(b ). text re-ranking via basic prp unit. given a set of n candidate documents, two principal approaches leveraging the prp unit to achieve reranking have emerged: the exhaustive allpair method and the sorting-based method @xcite . the allpair approach applies the prp unit to every possible document pair, calculating a cumulative score for each document based on pairwise preferences, yet it incurs a substantial o(n 2 ) computational cost and does not assure the most effective result according to previous work @xcite . on the other hand, sorting algorithms such as heapsort and bubblesort utilize llm-derived pairwise preferences for ordering documents. these methods improve efficiency (e.g. heapsort operates at o(n log n ) complexity), but their effectiveness is bounded by the reduced comparative scope and sensitivity to the initial ranking order @xcite . the basic prp unit, as used in recent approaches, performs llm inference twice for d i and d j in the transposition order then the results of the two inferences are integrated to make a judgment. (c) our scoring prp unit, considers the probability of generating "passage a" as the probability that the current preorder document is more relevant to the query than the subsequent document. ## method our prp-graph introduces a refined scoring prp unit that leverages llms' output probabilities for target labels, transforming these outputs into numerical scores for enhanced text ranking. the prp-graph operates in two main stages: ranking graph construction and ranking graph aggregation. in the first stage, document pairs are selectively compared to form a ranking graph with documents as vertices linked by bidirectional edges, where the scoring prp unit informs the iterative updating of weights. the second stage performs an aggregation of these weighted interactions to derive the final document ranking, fully encapsulating the sorting information across the graph. ## related work in the realm of zero-shot text re-ranking with llms, there are three main prompting approaches categorized broadly into pointwise @xcite , listwise @xcite @xcite , and pairwise @xcite . pointwise approaches rank candidate documents based on prompting llms for query-document pair relevance judgment, such as prompting llms to generate whether the provided query-document pairs are relevant @xcite and using the llms generation likelihood of query for the corresponding document as ranking score @xcite . listwise approaches involve sorting a list of documents at once, wherein llms are prompted to generate a ranked list of document labels based on the relevance of their corresponding documents to the query. current listwise approaches @xcite use sliding window approaches to work within the input length limits of llms, involving re-ranking the candidate document window from the bottom of the entire candidate documents list and progressing upwards. pairwise approaches determine the relevance order of two documents for a query at a time, wherein llms are prompted with a query alongside a pair of documents to choose the label indicating which document is more relevant to the query, namely pairwise ranking prompting (prp). exiting methods for obtaining the final re-ranking through pairwise comparisons between candidate documents can be classified into aggregation and sorting methods. allpair is a basic aggregation method @xcite , which conducts pairwise comparisons on all possible pairings within the candidate documents and aggregates the result of each comparison into the ranking score of the document. other aggregation methods exist focusing on sampling from all possible pairings to increase efficiency @xcite , but it hasn't been used in llms yet. sorting methods rely on pairwise comparisons as a basic comparison unit to run sorting algorithms, such as heapsort and bubblesort @xcite . these algorithms make use of efficient data structures to compare document pairs selectively. however, existing methods only utilize prp to obtain the same label for the comparison results of different confidence intervals without considering the uncertainty of pairwise comparisons. in contrast, our proposed prp-graph, based on a new scoring prp unit that quantifies the certainty of the pairwise comparisons from llms, exploits the potential of llms on zero-shot re-ranking. ## conclusion in our work, we propose a novel prp-graph approach based on a refined scoring pairwise ranking prompting (prp) unit to promote the potential of llms on text re-ranking tasks. benefiting from the consideration of the uncertainty of pairwise comparison in scoring prp unit, the prp-graph builds a ranking graph via the comparison results of the scoring prp unit and aggregates global signals of the ranking graph, surpassing existing prp-based zero-shot re-ranking techniques on the beir benchmark. in future work, we plan to explore a more efficient ranking graph aggregation strategy.