# LLMでソート ブログ「ジョイジョイジョイ」(著者: [[佐藤竜馬]])による、LLM を比較関数(コンパレータ)として使うソートの解説記事(2026-02-09)。ソートアルゴリズムの古典的理論と LLM の特性を結合する研究潮流をサーベイ的に整理している。 ## 核心的主張 LLM を比較関数として用いることで、従来の数値比較では扱えない「好み・優劣・関連性」などの主観的・曖昧な概念に基づいたソートが可能になる。Python の `functools.cmp_to_key` を利用すると既存ソートアルゴリズムにプラグアンドプレイで組み込める。ただし LLM 特有の呼び出しコストモデル・非推移的応答・位置バイアスが従来想定と異なるため、LLM 専用のアルゴリズム設計が必要である。 ## 応用例 - **論文の好み順ソート**: 好みを記述したプロンプトで ICLR 2026 オーラル論文をランキング - **経済ニュースの楽観度ソート**: 295 件を 2324 回比較・約 2 分半・GPT-5-mini 使用 0.85 ドル - 政治家のイデオロギー分類、バグ報告の重大度ソート等への応用が想定される ## ランキング手法の 4 分類 ### リストワイズ法(listwise) すべてのアイテムを一度に LLM に入力し、番号付きで並べ替えを出力させる方法。代表手法は **RankGPT**（Sun+ EMNLP 2023）。 - 利点: 1 回の呼び出しで完結、文脈に基づく相互比較が可能 - 欠点: アイテム数増加で出力が不安定(欠落・重複・パース失敗)、数百件を超えると実用困難 - 折衷: **スライディングウィンドウ法** — ウィンドウ幅 $w$ 個を LLM に入力し、$w/2$ ずつスライドしてソート。$O(n/w)$ 回の呼び出しで近似整列を実現（Sun+ EMNLP 2023） ### ポイントワイズ法(pointwise) 各アイテムを独立に入力し、1〜5 のスコアを出力させる方法。スコアの確率重みづけ（Liu+ EMNLP 2023）でタイを減らす改善がある。 $\text{score}(x) = \sum_{i=1}^{5} i \times P(\text{LLM が }i\text{ を出力} \mid x)$ - 利点: $n$ 回の呼び出し、アイテム数が増えても破綻しにくい - 欠点: 絶対尺度の設計が難しく、呼び出しごとに基準がずれる問題がある ### ペアワイズ法(pairwise) 2 つのアイテムを提示してどちらが優れるかを問う方法。本記事冒頭の Python コード例がこれに該当する。 - 利点: 絶対評価より比較が容易、既存ソートアルゴリズムの理論成果を活用できる - 位置バイアス対策: `llm(a, b)` と `llm(b, a)` の両方を呼び出し、結果が一致する場合のみ優劣を確定する（Qin+ NAACL 2024） ### セットワイズ法(setwise) $c$ 個のアイテムをまとめて比較し「最も良いもの」などを問う方法。 - $c$ 個の比較も 1 回の呼び出しで完結するため、LLM の呼び出しコスト構造に適合する - **$(c-1)$ 分ヒープ**: 二分ヒープを $(c-1)$ 分ヒープに拡張し、親と全子を一度に比較することで呼び出し回数を約半分に削減（Zhuang+ SIGIR 2024） ## 矛盾への対処 LLM の応答は順序の 3 公理(反対称性・推移性・完全性)を保証しない。 - **位置バイアス**: 先に置かれた選択肢が有利になる（Zheng+ NeurIPS Datasets 2023 が GPT-4 で実証）。双方向呼び出しによるタイ検出で緩和可能 - **推移性の欠如**: 非推移的な比較結果の処理は**フィードバックアーク集合問題(feedback arc set problem on tournaments)**（Ailon+ JACM 2008）に帰着する。この問題は NP 困難だが、**KwikSort**（ランダムピボットのクイックソート）が期待近似度 3 の近似アルゴリズムになることが証明されている ## 並列実行と呼び出しコスト削減 - クイックソートはピボットと各要素の比較をすべて並列発行でき、$O(\log n)$ 回のバッチ呼び出しで完了可能 - ヒープソートは前回比較結果が確定してから次の比較対象が決まるため、バッチ化が困難 ## 予測付きソート(Sorting with Predictions) Bai+ NeurIPS 2023 が提案する理論フレームワーク。低コストな「汚い」比較関数(ルールベース等)を前段に置き、本命の LLM 比較関数の呼び出しを最小限に抑える。 - 予測が良い場合: $O(n)$ 回の LLM 呼び出しでソート完了 - 予測が最悪の場合: $O(n \log n)$ 回の比較でソートできるという理論保証を維持 ## 実用的な推奨 著者による推奨: 1. **スライディングウィンドウ法**: 検索結果リランキングのように上位精度が重要で、厳密な全体順序が不要な場合 2. **クイックソート(KwikSort)**: 経済ニュースのスタンスや政治イデオロギーのように両端の並びも重要な場合。非推移性への理論保証と並列実行の両方に対応する点で LLM と相性が良い ## 引用文献 - Sun+ EMNLP 2023 — RankGPT（リストワイズ法、スライディングウィンドウ法） - Liu+ EMNLP 2023 — スコアの確率重みづけ（ポイントワイズ法改善） - Zheng+ NeurIPS Datasets 2023 — LLM 位置バイアスの実証 - Qin+ NAACL 2024 — 双方向呼び出しによる位置バイアス緩和 - Zhuang+ SIGIR 2024 — $(c-1)$ 分ヒープによるセットワイズ法 - Ailon+ JACM 2008 — フィードバックアーク集合問題と KwikSort の近似保証 - Bai+ NeurIPS 2023 — Sorting with Predictions