E co R ank: Budget-Constrained Text Re-ranking Using Large Language Models (2024)

Abstract: Large Language Models (LLMs) have achieved state-of-the-art performance in text re-ranking. This process includes queries and candidate passages in the prompts, utilizing pointwise, listwise, and pairwise prompting strategies. A limitation of these ranking strategies with LLMs is their cost: the process can become expensive due to API charges, which are based on the number of input and output tokens. We study how to maximize the re-ranking performance given a budget, by navigating the vast search spaces of prompt choices, LLM APIs, and budget splits. We propose a suite of budget-constrained methods to perform text re-ranking using a set of LLM APIs. Our most efficient method, called EcoRank, is a two-layered pipeline that jointly optimizes decisions regarding budget allocation across prompt strategies and LLM APIs. Our experimental results on four popular QA and passage reranking datasets show that EcoRank outperforms other budget-aware supervised and unsupervised baselines.

## introduction text re-ranking focuses on ranking n source documents given a specific query and is crucial for providing the relevant retrieved context to downstream tasks. it serves either as a standalone task or as an intermediate step for question answering tasks @xcite in a retrieval augmented setting, where the answer is generated from the top k relevant passages. traditional ranking methods includes bm25 @xcite and neural methods like dpr @xcite , contriever @xcite etc. recently, large language models (llms) such as @xcite have demonstrated dominant performance in text re-ranking @xcite . however, utilizing llms often comes at a cost: the process can be quite expensive, as closedsource llms charge based on the number of tokens. this expense escalates in text re-ranking due to the need to input substantial text, proportional to the number of passages to re-rank. for example, reranking 500 passages for a single query, with each passage having an average length of 100 tokens, currently costs at least 5 usd when using . this cost becomes intractable when businesses need to handle thousands of queries daily, making budget the biggest constraint. although there are many alternatives such as textsynth (tex), ai21 (ai2), cohere (coh), replicate (rep), etc., that offer llm api services at lower costs, utilizing these commercial apis may still not be sustainable with high volumes of queries. this motivates us to investigate the trade-off between cost and performance for text re-ranking. our aim is to propose a budget-aware solution for text re-ranking that maximizes performance within the constraints of a given budget. with this goal in mind, we approach budgetconstrained text re-ranking using llms as a constrained optimization problem. here, we explore various re-ranking methods with different properties and optimize for the best strategy for budgetaware text re-ranking. our work contributes to the first efforts in budgetaware modeling utilizing llms for text re-ranking, to the best of our knowledge. recent work on costaware applications of llms with llm cascading @xcite @xcite is not applicable to text re-ranking. they either focus primarily on qa or reasoning tasks @xcite , or require a fine-tuned model (with training data) to assess the generation quality of llms @xcite . on the other hand, works focusing on using llms for text re-ranking primarily aim at performance improvement without considering budgets. the three most common approaches exhibit increasing costs as the number of tokens inputted into the llms increases: 1) pointwise prompts @xcite , which input a single passage per request and output calibrated prediction probabilities before sorting; 2) listwise prompts @xcite , which input multiple passages per request as lists and ask llms to output the lists in order; 3) pairwise prompts @xcite , which input pairs of passages per query per request and use a sliding window to sort the top-k passages. approximately, the most expensive approach, namely pairwise prompts, can cost about 2 • k times more than pointwise prompts where k is the size of the sliding window. in this paper, we propose a suite of budgetconstrained methods to perform text reranking using a set of llm apis. our most efficient method, which we refer as ecorank, is a budgetconstrained llm-based text re-ranking pipeline, that jointly optimizes several objectives: 1) which prompt designs to deploy, 2) which llm apis to call, and 3) how to split budget between multiple prompts and llms. optimizing all these decisions jointly is challenging for the following reasons. (a) the provided budget may not be enough to input all input texts once to the llm api. the developed method must be able to optimize for the top-few (e.g. top-1) text. (b) different llm apis may have different strengths and limitations. (c) there is an exponential number of combinations of prompt designs and api selections. addressing these questions, we first consider various text re-ranking prompts tailored to accomplish the re-ranking task within a budget. next, we explore different llm apis and their associated costs for implementing these prompts. we then introduce a novel two-layer approach, ecorank (depicted in figure 1 ), which begins by re-ranking initially ranked passages (e.g., those ranked using bm25) with pointwise relevance filtering on a highaccuracy (and consequently expensive) llm api, utilizing a fraction of our budget. this initial reranking demotes irrelevant passages, allowing us to allocate the remaining budget to re-rank relatively relevant passages. in the second layer, we use a less accurate (and thus cheaper) llm api, applying the remaining budget to further re-rank the passages using pairwise ranking prompting. we evaluate various single or hybrid (combining more than one) prompt designs for the text re-ranking problem, for various budgets and apis on four popular datasets: natural questions (nq) @xcite , web questions (wq) @xcite , trec @xcite ) dl19, and dl20. our most efficient method ecorank achieves a gain of 14% on mrr and r@1 ranking accuracy than baselines. our contributions are summarized as follows: ## problem definition we focus on optimizing passage re-ranking under budget constraints, ranking top-k passages from a pre-ranked list. these lists are often obtained from a retriever in response to a natural language query. given a budget β, a query q, and a list of preranked n passages p 0 • • • p n with respect to q, the task is to re-rank the passages using available llm apis and retrieve top-k passages. for instance, in question answering tasks, bm25 is commonly used to produce the initial ranking, and then the main focus is typically on the top re-ranked passage (i.e. @xmath0. the following designs are critical for budget-aware text re-ranking. ## ecorank in this section, we present our novel most efficient budget-aware approach shown in figure 1 . both listwise and pairwise methods can achieve accurate rankings but they suffer from high cost. listwise methods only work with very expensive llms hence we put our focus on pairwise approach. while constrained within a budget, the number of passages that can be processed by llms impacts the final ranking accuracy. cheaper llms are able to process more passages but they lack quality. therefore, there are two key challenges that needs to be solved: 1) how to ensure quality 2) how to ensure quantity. with no budget constraint, pairwise methods may be an obvious choice due to their fine-grained accuracy but they have several limitations. we solve the challenges of pairwise designs in a budget-constrained scenario in a twostaged fashion as shown in figure 1 . first stage. only the first few passages can be compared by pairwise with a limited budget. however, as the initial ranked list is not that good, valuable tokens may be spent on irrelevant passages. thus in the first stage, we intelligently pick the passages to do pairwise comparison on. we split our budget β into two fractions x and y and use x amount to filter the passages using binary classification approach from the pointwise prompting group. we use a stronger and comparatively expensive llm l 1 with cost c 1 to generate a relevance for the passages in the form of "yes" or "no" and create an intermediate ranked list as per the binary classification strategy mentioned above. this coarse-grained strategy ensures quality as we are using a strong llm to put more relevant passages at the top for the next stage and push irrelevant ones to the bottom of the list. ## experimental evaluation to implement the supervised models, we load the available pre-trained versions in our gpu and use them to generate embeddings of the passages and queries. we use pygaggle foot_0 to re-rank the passages with the loaded model. to implement inpars, we use gpt-3.5 to generate synthetic data d fully using our budget b1, b2, b3. using b1 we could generate around 50k, using b2 10k, and using b3 5k questions. thus we have three sets of training data d b1 , d b2 , and d b3 . we randomly sampled passages from the corpus and asked gpt-3.5 to generate a new question. these are our positive examples. to get the negative examples, we use bm25 to retrieve 5 relevant passages. the passages that are not gold passages are considered as negative examples. we trained the t5-large 3 models for three budget categories with 156 steps and the same training arguments as inpars. we use the corresponding trained model to generate embeddings of the passages and re-rank. datasets. following previous work on passage retrieval, we choose the popular benchmark datasets natural questions (nq) @xcite , web questions (wq) @xcite , trec @xcite dl19, and dl20. there are total of 3610 questions on nq, 2032 on wq, 30 on dl19, and 44 on dl20 test splits. for trec datasets, there are multiple relevant passages per query contrary to nq and wq. to ensure fairness among datasets, we consider the passages with a score of 3 to be the relevant ones for trec. budget categories. we experiment with three budget categories. budgets are represented as token limits per question. the number of tokens that can be processed with each llm is mentioned in baselines. on top of the budget-constrained methods introduced above, we show comparisons with state-of-the-art supervised and unsupervised baselines. the supervised baselines are: 1) monobert (nogueira and cho, 2019): a crossencoder reranker trained on bert-large, trained on 3 https://huggingface.co/google-t5/t5-large msmarco, 2) monot5 @xcite : a sequence-to-sequence reranker based on t5, and 3) tart @xcite : a supervised instruction-tuned passage reranker based on flan-t5-xl for unsupervised approach, we consider in-pars @xcite , where we generate synthetic training data using gpt-3 and use them to train a t5-large model. for each budget category, we spend all our budget to generate synthetic data and infer the trained model in a zero-shot approach. we also consider openai text-ada-002 embedding model as a reranker baseline. we assume zero cost for the supervised baselines and no inference cost for inpars as no paid api is used. in reality, supervised models can have some costs regarding time and computing resources. for more details, please refer to b. ## related work to the best of our knowledge, we are the first to work on budget-constrained text re-ranking problem with llms. we divide the related work into llms in text re-ranking and cost aware llms. llms in text re-ranking. there are three main zero-shot prompting strategies to re-rank initially ranked passages. they are pointwise @xcite @xcite , listwise @xcite @xcite , and pairwise @xcite , which we covered in details in section 3. each strategy has their own strengths and may not work with all types of llms. very recently another prompting strategy has been introduced called setwise @xcite , which is an improvement over listwise approach where instead of outputting an ordered list of documents, a single document which is the most relevant is given as output. although this reduces the computational overhead of listwise and pairwise methods, it works best with llms which can output scores of generation. other works like distillation @xcite , rankvicuna @xcite , rankzephyr @xcite train an open source model with training data to improve listwise approaches. all these approaches do not consider the cost of llms and do not try to optimize the performance of text rankers with a budget constrain. prior to recent efforts with llms in text re-ranking, most works focused on the supervised ranking problem using monot5 @xcite or bert @xcite where they trained a pre-trained lm (plm) for re-ranking tasks. other supervised meth-ods focus on generating data to train plms like inpars @xcite , promptagator @xcite , exaranker @xcite , sptar @xcite , hyde @xcite etc. they mainly use llms as an auxiliary tool to support the training of plms and thus different from the scope of this paper. cost-aware llms. there are some works which focus on cost-aware applications of llms but in other areas than text re-ranking. frugal-gpt @xcite uses llm cascading to reduce the cost of api calls but they require a trained model to score the generation quality similar to forc @xcite which uses a trained meta-model to predict performance of llms. these trained models require fine-tuning data which may be difficult to obtain. mot @xcite uses answer sampling strategy which is not applicable in text re-ranking as llms output fixed tokens instead of open-ended. other works focus on optimizing api calls by using a neural caching system with a student model @xcite . none of these apply to our problem statement as we aim to optimize the performance in text re-ranking in a fully unsupervised fashion. ## conclusion we contribute to the first efforts of budgetconstrained text re-ranking with llms and have identified that existing works fail to consider budget while optimizing performance in text re-ranking. we propose a suite of budget-constrained methods with various ranking prompt designs and llms and extensively evaluate them on four datasets. our most efficient method ecorank, which is a two-layered pipeline that optimizes vast spaces of decisions, achieves a gain of 14% on mrr and r@1 than other approaches.