# pairwiseランキング ## 定義 pairwiseランキング(ペアワイズ法)とは、2 つのアイテム $a$, $b$ を入力として受け取り「どちらが優れるか」をモデルに問い合わせ、その応答を比較関数として使うランキング手法である。LLM を用いる場合、1 回のプロンプト呼び出しが 1 つの比較演算に対応する。Python では `functools.cmp_to_key` で任意のソートアルゴリズムに接続できる。（Source: [[joisino-LLMでソート-2026]]） ポイントワイズ法(絶対採点)・リストワイズ法(全件一括)と対比して、pairwiseランキングは相対比較に特化する。 ## ソートアルゴリズムとの接続 ペアワイズ法はソートアルゴリズムの「比較関数」を抽象化した部分に LLM を差し込む形で実現される。そのため、ソートアルゴリズム理論の成果（並列可能性・近似保証・計算量解析）をそのまま適用できる。 **LLM に特に適したアルゴリズム**: - **クイックソート / KwikSort**: ランダムピボットを選び、ピボットと全要素の比較を同時発行(並列バッチ実行)できる。$n$ 並列なら $O(\log n)$ ラウンドでソート完了 - **ヒープソート**: 前の比較結果が確定してから次の比較対象が決まるため、並列化が困難 ## 非推移性とフィードバックアーク集合問題 LLM の比較は推移性(「A が B より良く、B が C より良ければ A が C より良い」)を保証しない。このとき厳密なランキングは不可能になり、問題は**フィードバックアーク集合問題(feedback arc set problem on tournaments)**（Ailon+ JACM 2008）に帰着する。 - この問題は NP 困難である - ランダムピボットのクイックソート(KwikSort)を実行すると、**期待近似度 3** の近似アルゴリズムになることが証明されている: 矛盾するペア比較の数が最適値の期待値として高々 3 倍に抑えられる ## 位置バイアスへの対処 LLM は提示順序に敏感であり、先に置かれた選択肢を選ぶ傾向(位置バイアス)がある。Zheng+ NeurIPS Datasets 2023 は GPT-4 が GPT-3.5 と Vicuna-13B のどちらを先に置くかで判定が逆転することを実証した。 対処法（Qin+ NAACL 2024）: 1. `llm(a, b)` と `llm(b, a)` の両方を呼び出す 2. 両方で $a$ が選ばれれば $a \succ b$、両方で $b$ が選ばれれば $b \succ a$ 3. 結果が食い違う場合はタイとし、別の基準にフォールバックするか、タイを許容するソートアルゴリズムを使う ## リストワイズ法との比較 | 比較軸 | pairwise | listwise | |---|---|---| | 呼び出し数 | $O(n \log n)$ | $O(n/w)$ (スライディングウィンドウ) | | 1 回の難易度 | 低い(2 択) | 高い(多要素並び替え) | | 安定性 | 高い | 低い（欠落・重複が発生しやすい） | | 理論保証 | あり(KwikSort の近似) | なし（ヒューリスティック） | | 文脈比較 | 不可 | 可（同プロンプト内で相互参照） | ## 横断的知見 - **ペアワイズ法の採用でソート理論の知見が活きる**: 古典的なソート研究の並列化・近似・計算量解析の成果を LLM ランキングに転用できることは、LLM を比較器として扱う最大の利点である。リストワイズ法やポイントワイズ法にはこの転用先がない（Source: [[joisino-LLMでソート-2026]]） - **Chatbot Arena の人間嗜好評価と同型の構造**: Chatbot Arena は複数の人間審判によるペアワイズ勝率を Elo レーティングで集約するが、LLM ランキングでは LLM 自体が審判を担い、ソートアルゴリズムで集約する。[[LLM評価]] コンテキストではこの構造的類似が重要（Source: [[joisino-LLMでソート-2026]], [[LLM評価]]） ## 未解決の問い - タイを生じさせる双方向呼び出しを一般化ソートに組み込む場合、どのアルゴリズムが最も効率的か。 - LLM の位置バイアスはファインチューニング（RLHF・DPO）によって体系的に除去できるか、それとも根本的に残るか。 - ペアワイズ法で蓄積された比較結果（全 $\binom{n}{2}$ 対）を使い、Elo レーティングや Bradley-Terry モデルで全体順序を事後的に推定する方法は、フィードバックアーク集合問題の解として有力か。 ## 関連 - [[LLMランキング]] — 4 手法を包括する上位概念 - [[LLM比較器]] — LLM を比較器として用いる際の特性と限界 - [[LLM向け情報検索]] — リランキングへの応用 ## 出典 - [[joisino-LLMでソート-2026]] - Ailon+ JACM 2008: feedback arc set problem on tournaments, KwikSort - Zheng+ NeurIPS Datasets 2023: LLM 位置バイアスの実証 - Qin+ NAACL 2024: 双方向呼び出しによる位置バイアス緩和