https://joisino.hatenablog.com/entry/llmsort

ソートはコンピュータサイエンスにおける古典的なタスクですが、これが最先端の LLM と結びつき、新たな研究の潮流が生まれています。

ソートは比較関数さえ定義すれば実行することができます。従来の比較関数は身長・金額・距離のように測定可能な数値の比較を前提としていましたが、この比較関数内で LLM 呼び出しを行うことで「どちらが好みか」「どちらが優れているか」「どちらがクエリに関連するか」といった主観的で曖昧な概念を比較でき、これらの概念に基づいたソートが可能になります。

Python では、二つのオブジェクト a と b を受け取り、a を前に持ってきたければ -1 を、b を前に持ってきたければ +1 を出力する関数 cmp を実装し、functools.cmp_to_key(cmp) をソートのキーに設定すれば任意の基準でソートできます。

まずは雰囲気をつかむために応用例を見てみましょう。

論文を好みの順にソートする

例えば、以下のようなコードで私の好みの順に論文をソートすることができます。

import functools
from openai import OpenAI

client = OpenAI()

def cmp(a: dict, b: dict) -> int:
    prompt = f"""2 つの論文を比較して、より私の好みに合う方を選んでください。

私の好み:
- 「なぜ」に答える論文が好き
- 当たり前の技術の組み合わせよりもテクニカルに非自明なアイデアが好き
- 長期間にわたって活用できる汎用的な技術的テクニックが好き

これまで読んだ中で特に好きな論文:
- Adversarial Examples Are Not Bugs, They Are Features
- Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process
- The Platonic Representation Hypothesis
- Language Models Learn to Mislead Humans via RLHF
- Arithmetic Without Algorithms: Language Models Solve Math With a Bag of Heuristics

出力は必ず A または B のどちらか 1 文字だけとします。

[論文A]
Title: {a['title']}
Abstract: {a['abstract']}

[論文B]
Title: {b['title']}
Abstract: {b['abstract']}
"""
    r = client.responses.create(
        model="gpt-5-mini",
        input=prompt,
    )
    ans = (r.output_text or "").strip().upper()
    return -1 if ans == "A" else 1


# papers は辞書のリスト
ranked = sorted(papers, key=functools.cmp_to_key(cmp))

ICLR 2026 に採択されたオーラル論文をこれでソートすると以下の結果が得られました。

How Do Transformers Learn to Associate Tokens: Gradient Leading Terms Bring Mechanistic Interpretability
Verifying Chain-of-Thought Reasoning via its Computational Graph
The Spacetime of Diffusion Models: An Information Geometry Perspective
From Markov to Laplace: How Mamba In-Context Learns Markov Chains
Energy-Based Transformers are Scalable Learners and Thinkers
The Shape of Adversarial Influence: Characterizing LLM Latent Spaces with Persistent Homology
Temporal superposition and feature geometry of RNNs under memory demands
Sequences of Logits Reveal the Low Rank Structure of Language Models
Distributional Equivalence in Linear Non-Gaussian Latent-Variable Cyclic Causal Models
Reasoning without Training: Your Base Model is Smarter Than You Think
.
.
.

私好みの論文が上位に選ばれています。これで論文を読む順番を決めるのも楽になりそうです。

ニュースを楽観的なものから悲観的なものにソートする

以下の2つの経済ニュースを比較して、どちらがより「楽観的」かを判定してください。 というプロンプトで比較関数を実装し、最近の経済ニュースの見出しを楽観的なものから悲観的なものに順にソートすると以下の結果が得られました。上位 10 件と下位 10 件です。

インフレ：日本は好転。欧州は緩やかな回復、米国は力強い回復。株式市場と金属市場は史上最高値を更新。
NYダウ 終値で初の5万ドル突破 米景気先行きに楽観的見方で
NYダウ5万ドル、AIが変えるけん引役 キャタピラー断トツの株価2倍
日経平均株価最高値、終値2065円高の5万4720円 半導体株ラリーが再燃
26年日本株をけん引する実質賃金プラス転換と「ROE上昇」、個人投資家資金の“日本株シフト”にも期待
NYダウ初の5万ドル突破 主役交代、テックから製造業や資源に
NYダウ 515ドル値上がり 製造業の景況感 市場予想大きく上回る
グーグルの親会社 3か月決算 30％増益 AI向け事業が好調で
アマゾン 3か月決算で増収増益 クラウドなど主力事業が好調
TSMC 3ナノ先端半導体 熊本で生産へ 性能や用途は
.
.
.
ロシアＧＤＰ大幅減速、４％超から２５年は１・０％増…ウクライナ侵略で内需停滞しインフレ９％
2025年のエンゲル係数、44年ぶり高水準 12月実質消費支出は2.6%減少
ビットコインは存亡の危機に瀕している…「冬」が長く続くと予想される理由は？
中国の成長率「実際は5%よりはるかに低い」呉軍華氏
ゼレンスキー大統領 ロシアの攻撃を非難「戦争のみを優先」
中国が急ぐ「戦争準備」の衝撃 デフレ加速は避けられず
日本の金融危機と、うり二つ…債務が膨れ上がり、崖っぷちな中国経済を襲う三つの米中関係悪化リスク
日本が今、知るべき中国：中国経済はデフレスパイラル入りの危機 内需低迷に人口減少も下押し
「出口がない…」中国のデフレが日本の「失われた30年」より深刻な決定的理由
【2026年の中国経済】崩壊への時限爆弾…国有企業も見捨てられる危機、相次ぐ不動産・建設企業の破綻から金融危機へ

295 件のニュース見出しをソートすると、2324 回の比較を行い、約 2 分半でソートが完了しました。GPT-5-mini（thinking あり）を使うとかかった費用は 0.85 ドルでした。GPT-5-nano を使うと 5 分の 1 ほどになります。

このほか、政治家を左から右にソートする、バグ報告を重大な順にソートするなど、主観的で曖昧な判断が必要とされるタスクでも、LLM を用いて簡単にソートすることができます。

以上のように従来のソートにプラグアンドプレイで組み込めることは強みの一つですが、LLM の呼び出しにかかるコストは従来のソートアルゴリズムで想定されていた計算量のモデルとは異なるので、LLM を使ってソートすることを前提とした新しいソートアルゴリズムも提案されはじめています。本稿ではこの潮流について紹介します。

リストワイズ法とペアワイズ法：ナイーブなアプローチ

LLM を用いて最もナイーブにソートをしようと思うと、すべてのアイテムを LLM に渡して並べ替えて出力してもらうというものでしょう。このように、すべてのアイテムを一度に入力する方法をリストワイズ法といいます。例えば、RankGPT [Sun+ EMNLP 2023] という手法は、アイテムに番号づけて、その番号を並び替えて出力してもらう手法です。以下のようなプロンプトを用います。

以下は{{num}}個のアイテムであり、それぞれ番号識別子 [] で示されています。〇〇という基準にもとづいて並び替えてください。
[1] {{item_1}}
[2] {{item_2}}
...
[8] {{item_8}}
出力は識別子を用いて降順でリスト化し、最も良いアイテムを最初に表示します。出力形式は [] > [] > ...（例：[1] > [2] > ...）とします。

すると LLM は

[8] > [3] > [1] > [5] > [2] > [4] > [6] > [7]

のように出力するので、この出力がそのままソート結果として使えます。

リストワイズ法の良いところは、呼び出しが 1 度で済むことと、同一プロンプト内で複数候補を同時に見られるため、より多くの情報を活用して、文脈にもとづいた比較ができることです。

一方、欠点は、出力を安定させるのが難しいこと、特にアイテム数が増えるとそれだけ入力と出力が長くなり、一回の呼び出しあたりのタスクが難しくなるので破綻しやすいことです。例えば、一部アイテムの欠落、重複、パースに失敗する形式での出力が発生することがしばしばあります。アイテム数が数十程度であればなんとかなりますが、数百を超えてくると単純なリストワイズ法では難しくなります。結果を使い捨てる場合は大きな問題にはならないかもしれませんが、サービスとして安定運用をするにはナイーブな方法は不向きです。

実際には、候補となるアイテムの数が多い場合には全てのアイテムを一度に入力できないため、近似的な処理が行われることが多いです。最もよく使われるのがスライディングウィンドウ法です。

まずルールベースなどの簡単な基準でソートしたアイテム列を用意します。このうち下位 $w$ 個を LLM に入力し、並び替えを行います。次にウィンドウを $w/2$ 個上にスライドし、再度並び替えを行います。この操作を先頭に到達するまで繰り返します。これにより、 $O(n/w)$ 回の LLM 呼び出しで要素を並べられます。これは不完全なソートではありますが、古典的な基準で取りこぼしたアイテムを LLM の比較で浮上させることができ、かつ厳密なソートの $O(n \log n)$ 回の比較を避けられるため、折衷案として人気です。特に、検索結果のリランキングのように厳密なソートが必要なく、上位の結果を洗練させたい場合にはこのようなアプローチが有効でしょう。

リストワイズ法と対極に位置するのがポイントワイズ法です。ポイントワイズ法は、各アイテムを独立に入力し、そのスコアを LLM に出力させます。例えば以下のようなプロンプトを用います。

以下の論文が私の好みの基準にどれだけ合致しているか、1から5のスケールで評価してください。
タイトル：{title}
概要：{abstract}
評価スコア（1-5）:

LLM にこの続きを生成させると

のように評価が得られます。あとはこのスコアをキーとして従来のソートアルゴリズムを実行すれば良いです。ただし、1 から 5 までを出力するだけだと大量のタイが発生してしまいます。これを避けるため、それぞれの数字トークンを出力する確率をもとに重みづけする手法が提案されています [Liu+ EMNLP 2023]。

\begin{align} \text{score}(x) = \sum_{i = 1}^5 i \times P(\text{LLM outputs `} i \text{`} \mid x) \end{align}

これにより、LLM が 2 点をつけるか 3 点をつけるか迷った場合にも、その微妙なニュアンスをとらえて繊細にスコアリングできます。

ポイントワイズ法の良いところは、呼び出しが n 回で済むことと、リストワイズ法と比べるとアイテム数が増えても破綻しづらいことです。欠点は絶対尺度の設計が難しいことです。ポイントワイズ法では他の要素を見ずに点数を付けることになります。本来はライバルの品質が低いのであれば甘めにつけてもよく、ライバルの品質が全体的に高いのであれば厳しめにつけて見分けがつけられるようにするべきなのですが、独立に点数を付けるとこのような配慮ができません。呼び出しのたびに基準がずれて、たまたま LLM の「機嫌が良い」ときに呼び出されたアイテムが高い位置にランクしてしまうことがあります。

これらと比べて、冒頭で述べたように、LLM に二つのアイテムを提示してどちらが良いかを尋ねる手法をペアワイズ法といいます。ペアワイズ法のメリットは絶対評価や一度のソートよりも比較の方が簡単なことです。人間であっても、アイテムの絶対評価を下したり、すべてを一度に並べ替えたりするよりも、2 つのアイテムを比較する方が簡単かと思います。LLM も同様であり、相対的な比較を行う方が簡単であり安定します。これは差が小さく微妙なニュアンスまでくみ取って比較しなければいけないときに特に顕著です。

また、ソートアルゴリズムの歴史はとても長いですから、単純なソートだけでなく、並列可能性や近似的な比較が行える場合など、ソートにはさまざまなアルゴリズムや分析結果が存在します。ペアワイズ法はそれらの結果を享受できることも強みの一つです。

セットワイズ法

ペアワイズ法とリストワイズ法の中間に位置するのがセットワイズ法です。セットワイズ法では $ⅽ$ 個のアイテムをまとめて比較し、「最も良いもの」や「どこに挿入すべきか」などを答えさせます。このようにすることで、一度の LLM 呼び出しで複数の比較を行えるため、呼び出し回数を削減できます。LLM のコストは呼び出し回数に強く支配されるため、このような呼び出し回数を削減手法が効果的です。

例えば、従来のヒープソートは二分ヒープ（二分木）を用いることが一般的です。これは古典的な計算モデルでは、 $c$ 個のアイテムの比較には $\Omega(c)$ のコストがかかるため、2 個ずつ比較するのが自然だからです。一方、LLM は 2 個のアイテムを比較も $c$ 個のアイテムの比較も一度の呼び出しででき、そのコストはあまり変わりません。このため、従来の二分ヒープを用いた手法が最適でない可能性があります。シェンヤオ・ジュアンら [Zhuang+ SIGIR 2024] はここに着目し、ヒープソートにおいて二分ヒープではなく $(c − 1)$ 分ヒープを用い、自身とすべての子の比較を一度の LLM 呼び出しで行うことで呼び出し回数を削減する手法を提案しました。これにより、性能を保ちつつコストを半分ほど削減しています。

（上）二分ヒープと二項比較による従来のヒープ操作、（下）三分ヒープと四項比較によるヒープ操作 [Zhuang+ SIGIR 2024]

矛盾への対処

LLM による評価は強力ですが、LLM の出力は一貫性が保証されておらず、順序の公理に反する出力をすることがあります。ソートアルゴリズムは基本的に、以下の公理を満たすと仮定しています。

反対称性: $x_i \succ x_j$ かつ $x_j \succ x_i$ なら $x_i = x_j$
推移性: $x_i \succ x_j$ かつ $x_j \succ x_k$ なら $x_i \succ x_k$
完全性: $x_i \succ x_j$ または $x_j \succ x_i$ が成り立つ

しかし、LLM の返答はこの公理を満たすとは限りません。

LLM の位置バイアスが反対称性や完全性の問題になることがあります。LLM は比較が行われるとき、先に置かれた選択肢を選ぶようバイアスがかかることがあります。例えば、リェンミン・ジェンら [Zheng+ NeurIPS Datasets 2023] は GPT-3.5 と Vicuna-13B の生成文のどちらが良いかを GPT-4 に尋ねました。GPT-3.5 の生成文を先に提示すると GPT-4 は GPT-3.5 を選びましたが、Vicuna-13B を先に置くと Vicuna-13B を選びました。つまり GPT-4 の回答は一貫しておらず、この場合どちらが良いかを決定することはできません。このことを考慮せずに LLM を比較関数に用いると、偶然先に提示されることが多かった要素が不当に有利になる可能性があります。このバイアスを改善するため、llm(a, b) と llm(b, a) の両方を呼び出し、一貫して $a$ が選ばれれば $a \succ b$ とし、一貫して $b$ が選ばれれば $b \succ a$ とし、結果が食い違えばタイとする方法が提案されています [Qin+ NAACL 2024]。タイの場合は、タイを扱えるソートアルゴリズムを用いるか、別の基準にフォールバックするなどの対処が考えられます。

LLM の出力には推移性がないので、厳密な意味ではソートができません。LLM が A よりも B が良いと言い、B よりも C が良いと言い、C よりも A が良いと言った場合、どれを前に持ってきても不都合が生じます。このことを考慮せずにソートを実行しても、ソートアルゴリズムによってはこのために全く動作しなかったり、停止しなかったりする可能性があります。推移性がないソートは理論的にはトーナメント上の帰還枝集合問題 (feedback arc set problem on tournaments) という問題に対応しています [Ailon+ JACM 2008]。この問題は、 $n$ 個の要素とそれらの間の $_nC_2$ 個のペア比較結果が与えられたとき、最も多くのペア比較結果に従うような要素の並び替えを見つける問題です。この比較結果は非推移的であってもよく、そのような場合には、矛盾するペア比較結果を最小限に抑えるような並び替えを見つけることが求められます。この問題は NP 困難ですが、何も考えずにクイックソートを実行すると期待近似度 3 の（つまり平均的には矛盾するペアの数が最適値の高々 3 倍に抑えられる）良い近似アルゴリズムになることが知られています [Ailon+ JACM 2008]。具体的には、ピボット要素をランダムに選び、このピボットとの比較結果のみをもとに要素を左右に分割し、再帰的にソートします。この手法はクイックソート (QuickSort) をもじり KwikSort と呼ばれます。従来のソートでは推移性が満たされることが多いのでこのようなことを考えることが少ないですが、LLM を用いる場合には推移性がないので、このような性質をもつソートアルゴリズムを用いることが効果的と考えられます。

同時実行の考慮

LLM を用いる場合にはバッチサイズも重要です。GPU は並列に実行する能力が高いので、バッチサイズが 1 のときとバッチサイズが 2 のときの処理時間は変わらないことがよくあります。このため、複数の比較をバッチにまとめてリクエストできると効率がよくなります。ヒープソートでは、比較する対象は前回の比較結果がわからないと決まらないのでバッチ化が難しいです。一方、クイックソートはピボットと $x_1$ の比較、ピボットと $x_2$ の比較、...、ピボットと $x_n$ の比較をすべて並列に実行できます。 $n$ 個の比較を同時に実行できるほど並列度が高い場合、最大で $n$ 倍高速化でき、 $O(\log n)$ 回のバッチ呼び出しでソートを完了できます。API を用いるときにはコストを下げられないかもしれませんが、複数のリクエストを同時に発行することで、レイテンシを削減できます。

不完全な比較の活用

LLM の呼び出しはどうしてもコストがかかります。そこで、ルールベースなど低コストな比較をうまく活用しつつ、必要な場面で LLM を呼び出してコストを下げる手法も開発されています。

理論的には、これは 予測付きソート (Sorting with Predictions) [Bai+ NeurIPS 2023] に対応しています。この研究では、本命の比較関数で厳密にソートするために二つの問題設定を考えています。第一は「汚い」比較関数が使える設定です。この比較関数は無料で呼び出すことができますが、本命の比較関数と一致する保証はありません。この比較関数を活用しつつ、最終的には本命の比較関数をもとに厳密にソートすることを目指します。第二の問題設定は各要素の位置の予測が与えられる設定です。この予測は正確である保証はありませんが、この予測を活用しつつ、最終的には本命の比較関数をもとに厳密にソートすることを目指します。シンジエン・バイらの手法は、いずれの問題設定でも、予測が良いときには本命の比較関数を $O(n)$ 回呼び出すだけでソートを完了でき、予測に悪意がある最悪のケースでも、予測のないときと同じ $O(n \log n)$ 回の比較でソートできる理想的な結果が得られています。例えば第一の設定では、本命の比較関数をもとに平衡二分探索木を構築します。新しいアイテムが登場すると、まずは汚い比較関数をもとに比較を行い二分探索木の挿入位置を推定します。このあと、本命の比較関数をもとに葉から順番に上って汚い比較を検証しなおし、挿入位置を修正して正確に挿入しなおします。

汚い比較による仮の挿入位置の特定と、本命の比較による位置の修正 [Bai+ NeurIPS 2023]

汚い比較関数がある程度品質が高ければ、第一段階でおおよそ正しい位置が特定され、ローカルな修正だけで済むので定数時間で挿入が完了します。汚い比較が全くのデタラメでも、葉から根まで検証しなおし、新しい葉まで下りなおすだけなので、高々二倍の $O(\log n)$ 回の比較で挿入が完了します。LLM を用いたソートでも、ルールベースの単純な比較関数を「汚い」比較関数として用いて、LLM による本命の比較を助けることで、LLM の呼び出しを最小限に留めながら高品質なランキングが得られるようになります。

まとめ

ここまで、LLM を用いたさまざまなソートアルゴリズムの設計原則を紹介しました。実際に使ってみたいという場合はまずはスライディングウィンドウ法かクイックソート (KwikSort) がおすすめです。検索結果のリランキングのように厳密なソートが必要なく、上位の結果を洗練させたい場合にはスライディングウィンドウ法で済ませて、経済ニュースのスタンスや政治イデオロギーなど、片側だけでなく両側や中道側の並びも重要なときにはクイックソートで全体をソートするのが良いでしょう。特にクイックソートは推移性が成り立たなくても理論的な保証が得られ、並列実行にも対応しているので LLM と相性が良いです。さらに進化させたい場合は本稿で紹介した設計技法を取り入れていただければ幸いです。

おわりに

ソートというと枯れた技術のように思われがちですが、最先端の LLM と結びついて現在進行形で進化を遂げています。LLM ソートを用いることで、これまでの手法では困難であった、論文のランキング付けや、経済ニュースのスタンスのソート、政治イデオロギーのソートなどを、専門のモデルを開発することなく、LLM 呼び出しのみで実現できます。ソートはコンピュータサイエンスにおける古典的タスクの一例であり、このような LLM を活用する潮流はソートだけでなく、さまざまな古典的問題に対して広がっていくと考えられます。本稿がこの潮流を理解する助けになれば幸いです。

著者情報

この記事がためになった・面白かったと思った方は SNS などで感想いただけると嬉しいです。

新着記事やスライドは @joisino_ (Twitter) にて発信しています。ぜひフォローしてくださいね。

佐藤竜馬（さとうりょうま）

京都大学情報学研究科博士課程修了。博士（情報学）。現在、国立情報学研究所助教。著書に『』『』『最適輸送の理論とアルゴリズム』がある。

プロフィールを見る