PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Raphael Tang, Xinyu Zhang, Xueguang Ma, Jimmy Lin, Ferhan Ture

arXiv:2310.07712v2cs.CLcs.LG

TL;DR

LLMs’ positional biases complicate listwise ranking, where prompt order can affect output quality. The paper shuffles list order across prompts and aggregates the resulting rankings into a central ranking. It reports consistent gains over ordinary decoding across sorting and passage reranking, alongside theoretical robustness results.

  • Problem

    LLM listwise rankings are sensitive to positional factors such as prompt order and input length, which can lead to misranking.

    Source: §1 · p. 1

  • Method

    Permutation self-consistency randomly shuffles list order across prompts and aggregates the resulting rankings into a central ranking minimizing total Kendall tau distance.

    Source: §1 · p. 1, §2.2 · p. 3

  • Results

    The method improves over ordinary decoding on all 15 sorting model–dataset combinations and 13 of 16 passage-reranking combinations.

    Source: §6 · p. 8

  • Takeaways & Limitations

    The method reduces the association between predicted rankings and list order, with gains reported across sorting and passage reranking.

    Source: §6 · p. 8

    The study uses automated academic evaluation, and its ranking metrics do not exactly capture human preferences; effectiveness in production search or recommendation remains undetermined.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Large language models (LLMs) exhibit positional bias in how they use context, which especially complicates listwise ranking. To address this, we propose permutation self-consistency, a form of self-consistency over 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 in the presence of random perturbations. Empirically, on five list-ranking datasets in sorting and passage reranking, our approach improves scores from conventional inference by up to 7-18% for GPT-3.5 and 8-16% for LLaMA v2 (70B), surpassing the previous state of the art in passage reranking. Our code is at https://github.com/castorini/perm-sc.

1 Introduction

LLM listwise ranking is vulnerable to positional factors: prompt order can change quality, and items in the middle of long contexts may be misranked. The paper proposes permutation self-consistency, which shuffles prompt lists and aggregates rankings to reduce positional bias.

1 Introduction

  • Permutation self-consistency shuffles input-list order across prompts, then selects the central ranking minimizing total Kendall tau distance to the sampled rankings.This aggregates outputs to marginalize prompt order as a factor.Source: §1 · p. 1
  • GPT-3.5 scores improve by up to 4–17%, GPT-4 by 9–24%, and LLaMA v2 (70B) by 8–16% across sorting and passage-reranking tasks.The paper also reports similar gains for Mistral and Zephyr.Source: §1 · p. 2
  • The method is theoretically proven to recover the true ranking under arbitrary noise distributions given enough observations and at least one correctly ordered pair per observation.The contribution summary characterizes the robustness as covering certain ranking-noise classes, including “lost-in-the-middle” noise.Source: §1 · p. 2
  • The auxiliary study finds five aggregated rankings reach 67% of the score improvement from twenty on average, while sampling temperature is ineffective.The authors suggest ranking does not require exploring varied reasoning paths.Source: §1 · p. 2
  • The authors report that positional biases depend on the pairwise positions of items in the list.Their empirical validation covers sorting and passage reranking on seven models and five datasets.Source: §1 · p. 2

2 Our Approach

The approach mitigates positional bias by ranking outputs from randomly reordered prompts with a central-ranking aggregation. Its theoretical guarantees show convergence to the true ranking under specified ranking-noise conditions.

2.1 Preliminaries

  • The preliminaries represent an n-item ranking as a permutation and describe Kendall tau distance as the number of pairwise ordering disagreements.Source: §2.1 · p. 2

2.2 Permutation Self-Consistency

  • Self-consistency does not readily generalize to listwise ranking because it targets point predictions, temperature has little effect on aggregated quality, and it does not address positional bias.Source: §2.2 · p. 2
  • Randomly permuting the input list produces rankings with different position biases; aggregating them via the central ranking that minimizes summed Kendall tau distance marginalizes out prompt order.Source: §2.2 · pp. 2–3

2.3 Theoretical Guarantees

  • Under noise where each observation has a uniformly random, nonempty subset concordant with the true ranking and a random remainder, the Kemeny–Young ranking converges to the truth.Source: §2.3 · p. 3
  • For noise that preserves a uniformly random, nonempty concordant subset under any input permutation, permutation self-consistency consistently estimates the true ranking.Source: §2.3 · p. 3

3 Experiments

Experiments evaluate permutation self-consistency (PSC) on sorting and passage reranking, finding improved ranking quality alongside model- and position-specific patterns in reranking. The studies also compare PSC against individual runs and examine retrieval and reranking configurations.

3 Experiments

  • Across numerical, alphabetical, and sentence-sorting datasets, each with 100 examples, SPLADE++ adds an average of 7.26 points over corresponding BM25 models in passage reranking.Passage reranking uses TREC DL19 and DL20; reported baselines include supervised MonoT5 and RankT5 and unsupervised PRP-Best.Source: §3.1 · p. 4, §3.2 · pp. 5–6

3.1 Sorting Tasks

  • 51%: PSC raises average Kendall tau correlation over conventional inference across three sorting datasets and seven models.Gains are larger for smaller models and harder tasks; the passage reports task-wise gains of 67% for MathSort, 30% for WordSort, and 58% for GSM8KSort.Source: §3.1 · p. 4, Table 3 · p. 4
  • 1–12%: PSC beats the best individual sorting run, with larger improvements on lower-baseline tasks and models such as MathSort and GPT-3.5.Figure 3 compares PSC scores with the distribution of twenty individual runs.Source: §3.1 · p. 4, Figure 3 · p. 4

3.2 Passage Reranking Task

  • 1.28 points: SPLADE++ with PSC reaches 76.87 on DL19, above the previous best; on DL20, it reaches 78.52, 3.79 above RankVicuna.The results report nDCG@10 and compare PSC with conventional inference and prior baselines.Source: §3.2 · p. 5, Table 4 · p. 5
  • PSC improves passage-reranking scores in 13 of 16 model–dataset combinations, with average relative gains of 0.4% for RankVicuna, 2% for GPT-3.5, and 5% for GPT-4.The authors attribute RankVicuna’s mixed results as likely related to its training-time random-shuffling data augmentation, which may leave less output variation for PSC to aggregate.Source: §3.2 · pp. 5–6
  • Reversion patterns differ by model and input positions: GPT-3.5 reverses central pairs more often, while GPT-4 reverses pairs near the list end more often.The analysis also reports a GPT-3.5 pattern after position 15 and suggests that GPT-4’s reversion pattern may help explain its larger PSC gains in the single-call setting.Source: §3.2 · p. 6, Figure 4 · p. 6

4 Sensitivity Analyses

The sensitivity analyses examine aggregation size, sampling temperature, and the choice of rank-aggregation method. They find diminishing returns beyond five to ten rankings, little overall temperature effect, and stronger scores from Kemeny aggregation than RRF in most comparisons.

4.1 Hyperparameter Studies

  • Five aggregated rankings achieve 67% of the average score improvement from twenty, while quality gains sharply diminish after five to ten rankings.Scores increase monotonically with ranking count on average (ρ = 0.17); the authors retain m = 20 as their reference setting.Source: §4.1 · p. 7
  • Temperature has little overall effect on quality (ρ = −0.078), but added randomness sharply hurts GSM8KSort on both tested models.The authors use this evidence to support not using temperature for sample generation.Source: §4.1 · p. 7

4.2 Rank Aggregation Comparison

  • Kemeny beats RRF in 8 of 10 comparisons (p < 0.05) by a mean of 0.23 points; RRF reaches 93.5% of Kemeny’s boost on average.RRF’s only reported outperformance is on DL19; the authors note it may reflect its information-retrieval origins or statistical noise.Source: §4.2 · p. 7, Figure 6 · p. 7

5 Related Work and Future Directions

The paper situates PSC among prior work on rank aggregation, passage ranking, and positional bias, while identifying possible extensions to differentiable training-time use and other list-oriented tasks.

5 Related Work and Future Directions

  • Unlike Borda-count bootstrapping, PSC finds the central ranking that is optimal across individual rankings in Kendall tau distance.The related-work discussion contrasts this with Hou et al. (2023).Source: §5 · p. 8
  • Passage-ranking work progressed from BERT- and T5-based models to RankGPT and LRL; PSC could be reformulated as differentiable for training-time use in models such as RankVicuna.The discussion also describes PRP as a pairwise method using open-source LLMs to compare two items at a time.Source: §5 · p. 8
  • The authors identify LLM evaluation and human-feedback annotation as possible PSC applications, alongside denoising weakly labeled training sets generated by teacher models.They note that teacher-generated weak labels have been shown to be important to listwise-ranking LLMs.Source: §5 · p. 8
  • Prior studies examine prompt-order effects and positional bias; the authors describe their work as the first, to their knowledge, to characterize passage-ranking bias by pairwise item positions and propose a correction.They note that prompting-based mitigation techniques could complement PSC.Source: §5 · p. 8
  • The paper builds on self-consistency and other generation meta-algorithms, adapting its shuffle–aggregate template to listwise ranking.The authors say they based their design on the original self-consistency approach to keep it simple.Source: §5 · p. 8

6 Conclusions

The conclusion presents permutation self-consistency as a decoding method that reduces sensitivity to list order by shuffling prompts, collecting rankings, and aggregating them. It reports consistent empirical gains, theoretical robustness, and sensitivity analyses supporting its design choices.

6 Conclusions

  • PSC improves ordinary decoding on all 15 sorting model–dataset combinations and 13 of 16 passage reranking combinations.The conclusion also reports robustness to arbitrary, fixed noise distributions and sensitivity analyses supporting 20 output rankings, zero sampling temperature, and Kemeny ranking.Source: §6 · p. 8
  • The method shuffles prompt list order, generates multiple rankings, and returns an aggregate with less association with list order.The conclusion identifies the aggregation statistic as the Kemeny ranking method.Source: §6 · p. 8
  • The conclusion reports theoretical robustness to arbitrary, fixed noise distributions.It also says sensitivity analyses justify the choices of 20 output rankings and zero sampling temperature.Source: §6 · p. 8

Limitations

The study notes limits in evaluation scope and model transparency, as well as additional call costs associated with its method. These constraints qualify what can be inferred about deployment and practical value.

Limitations

  • Permutation self-consistency requires multiple LLM calls, potentially increasing financial cost, so quality gains must be weighed against expense.The authors report that a few calls help, with returns rapidly diminishing past 5–10 calls.Source: Limitations · p. 9
  • GPT-3.5 and GPT-4 are proprietary models whose internals lack official documentation.The authors partially address this by also running experiments on open-source Mistral, Zephyr, LLaMA 2, and RankVicuna where possible.Source: Limitations · p. 9
  • Evaluation is restricted to automated academic settings, and Kendall’s tau and nDCG@10 do not exactly capture human preferences.Effectiveness in production web search or recommendation remains undetermined.Source: Limitations · p. 9

A Proofs of Propositions

The appendix proves consistency of Kemeny-based aggregation under specified noise assumptions by bounding the probability of excess discordance. It also records the computational environment used for the experiments.

A Proofs of Propositions

  • For the uniformly noisy-ranking case, the Kemeny-optimal ranking recovers the true ranking with probability 1 as the number of observations tends to infinity.This follows because Kemeny optimality minimizes pairwise discordance, and the proof's upper bound tends to zero.Source: A Proofs of Propositions · pp. 10–11
  • With independent rankings containing uniformly random, nonempty concordant subsets and random remaining elements, the Kemeny–Young ranking converges in probability to the true ranking.The proof bounds the probability that discordant pairs outnumber concordant pairs and shows the bound approaches zero as sample size grows.Source: A Proofs of Propositions · pp. 10–11
  • Under a noise distribution whose shuffled outputs retain a uniform, nonempty concordant subset with the true ranking, permutation self-consistency is a consistent estimator.The proof transforms these premises to those of Proposition 2.1.Source: A Proofs of Propositions · p. 11

B.1 Computational Environment

  • Experiments ran on Ubuntu 22.04 with two Nvidia A6000 GPUs, an AMD Epyc Milan 7B13 CPU, and 256GB of ECC RAM.The listed frameworks include PyTorch 2.1.0, Transformers 4.36.1, PuLP 2.7.0, and CUDA 12.2.Source: §B.1 · p. 12

B.2 Sorting Tasks

The sorting-task appendix describes prompt extraction and dataset construction choices for WordSort and MathSort. The listed prompts fit within a 4096-token context size.

B.2 Sorting Tasks

  • All sorting-task prompts fit within a 4096-token context size, and regexes extracted rankings from well-formed model outputs.The authors report that all models generated well-formed, extractable text.Source: §B.2 · p. 12
  • WordSort examples mix five consecutively ordered English words with five randomly picked words to add difficulty.The passage illustrates this with words such as “aardvark” and “dog.”Source: §B.2 · p. 12
  • Each MathSort example contains 10 expressions with unique evaluated values, and no task lists are duplicates.Source: §B.2 · p. 12

B.3 Passage Reranking Task

The passage-reranking setup follows prior prompts and extraction procedures, estimates GPT endpoint reproduction costs, and provides figure captions comparing rerankings with and without PSC.

B.3 Passage Reranking Task

  • The passage-reranking prompts follow prior work, and output extraction uses the official codebases’ procedures for a faithful comparison.The prompts are listed in Table 6.Source: §B.3 · p. 12
  • Reproducing the GPT passage-ranking results is estimated to cost $100–200 USD, with GPT-4 accounting for most of the expense.The estimate uses public endpoint prices of $0.002 and $0.03 per one thousand tokens for GPT-3.5 Turbo and GPT-4, respectively.Source: §B.3 · p. 12
  • Figures 7 and 8 show DL19 queries reranked without PSC on the left and with PSC on the right; Figure 8 uses GPT-4 as the model.Source: Figure 7 · p. 13, Figure 8 · p. 13

C Qualitative Examples

The examples compare PSC and non-PSC rerankings on DL19, while supplementary discussion reports reviewer-suggested experiments and a sorting-task comparison with PRP-10.

C Qualitative Examples

  • For “define visceral?”, PSC improves GPT-3.5 but not GPT-4 because GPT-4’s original output is already correct; with PSC, GPT-4 ranks document #3641634 higher than without PSC.These illustrations suggest that PSC’s quantitative improvements are not merely illusory.Source: C Qualitative Examples · p. 13

D Supplementary Results and Discussion

  • The authors include most experiments suggested by reviewers and incorporate the remaining feedback into related work.This describes the supplementary results and discussion added during peer review.Source: D Supplementary Results and Discussion · p. 14

D.1 Sorting Tasks

  • PSC outperforms PRP-10 by 15 points in Kendall’s tau on average, with higher gains on GPT-3.5; the methods are compared in Table 8.PRP-10 was chosen because its computation time most closely matches PSC.Source: §D.1 · p. 14, Table 8 · p. 14

D.2 Passage Reranking Task

The passage-reranking discussion reports results for reversing input order and for replacing Borda-count aggregation, then weighs PSC’s computational burden against its parallelizability.

D.2 Passage Reranking Task

  • Reversing passage input orders yields an average 3.2-point improvement, mitigating position bias regardless of sliding-window order.Reversal does not apply to sorting because its underlying dataset is unordered.Source: §D.2 · p. 14
  • PSC consistently outperforms bootstrapping/Borda count on GPT-3.5 and GPT-4, with average gains of 0.39 and 0.42 points, respectively.The authors suggest Kemeny ranking’s theoretical optimality as a possible reason and conclude that aggregation choice matters.Source: §D.2 · p. 14

D.3 Computational Burden

  • PSC’s computation time is a general limitation, but five parallel instances roughly match one baseline’s runtime, and aggregation takes under 0.05 CPU seconds.In the reported experiments, 20 parallel calls add no more than 25% to a single call’s running time; the scaling advantage assumes parallel computing.Source: §D.3 · p. 14

Related papers

Loading 2310.07712v2…