Found in the Middle: Permutation Self-Consistency Improves Listwise Ranking in Large Language Models (2024)

Abstract: Large language models (LLMs) exhibit positional bias in how they use context, which especially affects listwise ranking. To address this, we propose permutation self-consistency, a form of self-consistency over the ranking list outputs of black-box LLMs. Our key idea is to marginalize out different list orders in the prompt to produce an order-independent ranking with less positional bias. First, given some input prompt, we repeatedly shuffle the list in the prompt and pass it through the LLM while holding the instructions the same. Next, we aggregate the resulting sample of rankings by computing the central ranking closest in distance to all of them, marginalizing out prompt order biases in the process. Theoretically, we prove the robustness of our method, showing convergence to the true ranking under random perturbations.Empirically, on five datasets in sorting and passage reranking, our approach improves scores from conventional inference by up to 34-52% for Mistral, 7-18% for GPT-3.5, 8-16% for LLaMA v2 (70B). Our code is at https://github.com/castorini/perm-sc.

## introduction large language models (llms) respond cogently to free-form textual prompts and represent the state of the art across many tasks @xcite . their quality, however, varies with nuisance positional factors such as prompt order and input length. as a descriptive example, consider this prompt: arrange the following passages in decreasing relevance to the query, "what are shrews?" (1) cats hunt small mammals, such as shrews ... figure 1 : the conventional decoding process for listwise ranking with input prompt (a), language model (c), and output ranking (d). the grey item (b) is "lost in the middle" by the llm, resulting in its misranking (e). with the instruction fixed, we shuffle the input list for prompts (a), producing outputs with different mistakes. we aggregate (b) these output rankings into one (c). a long context and use the middle portion poorly, which suggests that the middle passage (2) in the example may get misranked (e.g., 3, 1, 2). @xcite find prompt order to affect quality, with some orders outperforming others; if items 1 and 3 were swapped in the prompt, the llm would perhaps generate the mistaken ranking (2, 1, 3). in this paper, we mitigate positional biases for listwise-ranking llms. we propose permutation self-consistency, a novel decoding strategy for improving the quality, consistency, and prompt-order invariance of black-box llms. first, we construct prompts with randomly permuted input lists, then feed them into an llm to generate a set of output rankings. then, we aggregate these outputs into the central ranking that minimizes the kendall tau distance to all of them, marginalizing out prompt order as a factor; see figures 1 and 2 . as related work, @xcite train direction-unaware probes on the representations of language models to detect order consistency, but their evaluation reveals the ranking direction of test examples to the model, deviating from standard practices. next, we assess the effectiveness of permutation self-consistency, both theoretically and empirically. theoretically, we prove in section 2.3 that it recovers the true ranking under arbitrary noise distributions with enough observations and at least one correctly ordered pair in each observation. experimentally, we apply our method to tasks in math and word sorting, sentence ordering, and passage reranking @xcite , consistently increasing the scores of gpt-3.5, gpt-4, and llama v2 (70b; @xcite by up to 4-17%, 9-24%, and 8-16%, respectively. we achieve similar gains for mistral @xcite and zephyr @xcite . we conclude that permutation self-consistency improves listwise ranking in llms. in line with our premises, we observe positional bias, as shown in section 3.2. finally, we conduct auxiliary analyses to justify our design choices. in section 4.1, our hyperparameter study finds that quality quickly rises with the number of aggregated output rankings: the score improvement from using five aggregated rankings reaches 67% of twenty, on average, suggesting that a few suffice for quality gain. we further demonstrate that sampling temperature is ineffective for us, unlike the original self-consistency work @xcite in chain-of-thought reasoning, likely because listwise ranking does not require exploration of various reasoning paths. our contributions are as follows: ## experiments we experiment on sorting and passage ranking, two distinct types of problems in listwise ranking. ## sensitivity analyses in this section, we investigate and characterize each component of permutation self-consistency to justify our modeling choices. ## related work and future directions the holistic direction of our work is in enhancing the ranking ability of large language models. along a similar vein, contrast-consistent ranking @xcite proposes to train order-unaware probes on the latent vectors of large language models for detecting nondirectional rank consistency. their evaluation reveals the ranking direction of test examples to the models, deviating from standard practices, as their purpose is not to increase ranking quality but rather to detect consistency. another related work is @xcite , which uses a different rank aggregation algorithm from ours. in contrast to their heuristic bootstrapping method (i.e., borda count) of summing up the ranks of each ranking, our approach is theoretically optimal in that it finds the best central ranking to all individual rankings in terms of the tau distance. the specific empirical tasks in this paper have also seen recent progress. for passage ranking using language models, bert-based @xcite and t5-tuned @xcite approaches represent the earliest language models for passage ranking. rankgpt @xcite and lrl @xcite spearheaded much of the post-chatgpt work, beating the supervised state of the art with an unsupervised llm for the first time. along a non-listwise direction, prp @xcite is a pairwise method leveraging open-source large language models comparing two items at a time, as reported in our sorting tasks for llms have had attention as well, mostly in the context of evaluation, with big-bench @xcite , an llm benchmark, providing more than 200 distinct tasks, including one in alphabetical ordering (word_sorting), which we enlarge and expand on in wordsort. @xcite also constructed fact-based synthetic sorting datasets for listwise ranking, but they are private and hence noncomparable. in the future, psc can be applied to any list-oriented ranking task involving llms. examples include using llms for evaluation @xcite and annotating human feedback judgments with language models. additionally, psc is applicable at training time, such as denoising weakly labeled training sets generated by teacher models, shown to be crucial to the success of listwise-ranking llms @xcite . we are not the first to establish positional biases in llms. @xcite are among the earliest to relate prompt order to the quality of in-context learning. the main difference in setup is that they assume the presence of a training set, whereas we do not, which especially matters for passage ranking, as many tasks only have evaluation sets. recently, @xcite and @xcite characterized positional bias in the context of list-oriented tasks, such as question answering and response evaluation. however, we are to our knowledge the first to characterize the position biases of passage-ranking llms with respect to pairwise item positions, and our work also proposes a correction technique. moreover, @xcite and @xcite apply prompting-based techniques for mitigating positional bias. prompting is not mutually exclusive of our psc, and it could be complementary. lastly, our paper is connected to all the metaalgorithms for improving llm generation. as a pertinent example, @xcite study prompt order on in-context learning classification tasks, proposing an entropy-based statistic over development sets to find performant permutations of few-shot examples. aggarwal et al. (2023) make self-consistency more efficient, halting the procedure when enough samples have been collected. to keep our method in its simplest form, as selfconsistency had not been applied to listwise ranking to begin with, we based our design on the original approach @xcite . ## conclusions we introduce a novel decoding method to improve the ranking ability of black-box llms by mitigating potential sensitivities and biases to list item order. we intervene on prompt list order to produce multiple rankings then return an aggregated statistic as the prediction, which has less association with list order. theoretically, we prove the robustness of our method to arbitrary, fixed noise distributions. empirically, our method consistently improves upon ordinary decoding on all 15 of our sorting model-dataset combinations and 13 out of 16 of our passage reranking ones. finally, our sensitivity analyses justify our design choices of 20 output rankings, zero sampling temperature, and the kemeny ranking method.