テキスト選択、パッセージの重排器（Reranker）、およびコンテキストエンジニアリングのための劣モジュラ最適化

GitHub - jina-ai/submodular-optimization: Submodular optimization for diverse query generation

Submodular optimization for diverse query generation - jina-ai/submodular-optimization

GitHubjina-ai

以前の記事「DeepResearchにおけるファンアウトクエリのための劣モジュラ最適化」の後、劣モジュラ性と、情報検索およびエージェント検索におけるその応用について、より深く掘り下げてほしいという素晴らしいフィードバックをいただきました。今回は、劣モジュラ最適化の応用例をさらに2つご紹介します。それは、テキスト選択とパッセージの重み付けです。どちらも、DeepResearchのようなシステムが解決しなければならない、最適化されたサブセット選択という同じコアな課題に取り組むものです。

現実世界のドキュメントには、セマンティックな冗長性があります。すべての文がLLMの推論にとって等しく重要であるわけではありません。長いドキュメントがあり、トークン制限内に収まりながら、最も代表的な情報を抽出する必要があるとします。これがテキスト選択です。基数制約の下でドキュメントの本質を捉えるコンテンツを選択することです。互いに直交する選択を望みます。つまり、共有情報を最小限に抑えながら、カバレッジを最大限に高めることです。これは、ドキュメントから文を選択したり、文からトークンを選択したりするなど、複数のレベルで適用されます。テキスト選択を、コンテキストの最適化または圧縮と考えることもできます。推論に必要なセマンティックな豊かさを維持しながら、LLMのトークン消費を削減します。

パッセージの重み付けは、ユーザーのクエリに対するセマンティックな関連性によって候補パッセージを並べ替えます。Jina AIでは、このために特化した重み付け器 (jina-reranker-m0、jina-reranker-v2-multilingual-base) を構築しましたが、当社の埋め込みモデルでもこの問題を解決できます。ただし、ここには制限があります。ほとんどの重み付け器 (当社を含む) は、ポイントワイズ方式で動作します。つまり、個々の(query, document)ペアを独立してスコアリングします。パッセージ間の共有情報を考慮しません。パッセージ1とパッセージ7の両方が高いスコアを獲得したが、ほとんど同じ情報が含まれている場合、それらのうち1つだけを選択するだけで十分ではないでしょうか。

DeepResearchでは、これは非常に重要になります。エージェントが検索ツールを呼び出してウェブスニペットを収集するとき、次の推論ステップのために、どのスニペットが貴重なコンテキストウィンドウスペースに値するかを判断する必要があります。選択は、テキスト選択と同じ「重複を最小限に抑え、カバレッジを最大限に高める」という原則に従いますが、目的が1つ追加されています。つまり、元のクエリに対する関連性を優先する必要があります。

多くの研究者は、コンテキストエンジニアリングの重要性が高まっていることを認識しています。コンテキストエンジニアリングでは、より効果的なエージェントワークフローを構築するために、コンテキストウィンドウを構築、最適化し、「適切にパッキングする」必要があります (Andrej Karpathy氏の言葉)。ただし、多くの人は単にLLMのプロンプトを使用して、これらの問題を「ソフトに」解決するだけです。これには、保証がなく、理論的な根拠がなく、効果も疑わしいです。もっと良い方法があります。

この記事では、テキスト選択とパッセージの重み付けの両方が、厳密なソリューションを提供する劣モジュラ最適化につながることを示します。劣モジュラ関数に慣れていない場合は、「収穫逓減」と考えてください。まず空のセットから始めて、選択したテキストまたはパッセージを段階的に追加します。各追加は価値を提供しますが、限界利益は減少します。これは、多様で冗長性のない選択が最も価値があるという直感を捉えています。正式には、関数$f$は、任意のセット$A \subseteq B$と要素$i \notin B$に対して劣モジュラである場合：

$$f(A \cup {i}) - f(A) \geq f(B \cup {i}) - f(B)$$

この定式化は、私たちの直感を完璧に捉えています。選択した要素が、ドキュメント全体のセマンティックな空間をまとめてカバーすることを望んでいます。より多くのユニットを選択するにつれて、各新しいユニットが以前にカバーされていないセマンティックな空間をカバーする可能性は低くなります。

tag劣モジュラ最適化によるテキスト選択

Google Colab

まずはテキスト選択問題を解くことから始めましょう。これは劣モジュラ性を理解する上で不可欠であり、パッセージの重み付けをやり直すための予備段階となります。問題は以下の通りです。

n個の要素（トークンまたは文）を持つドキュメント $D$ が与えられたとき、$S \subseteq {1, 2, \ldots, n}$ で $|S| = k$ であるサブセットを選択し、カバレッジ関数を最大化します。

$$f(S) = \sum_{i=1}^{n} \max_{j \in S} \text{sim}_{ij}$$

ここで、$\text{sim}_{ij}$ は要素 $i$ と $j$ のベクトルモデル間のコサイン類似度を表します。カバレッジ関数 $f$ は、収益逓減性を持つため、劣モジュラであることを注記しておきます。max演算により、各要素が最も近い選択されたユニットによってどの程度適切に表現されているかを測定し、冗長な情報の二重カウントを回避できます。

tagトークン/パッセージレベルのベクトルモデルを取得する

トークンレベルの選択では、jina-embeddings-v4 の新しいマルチベクトルモデル機能を利用します。return_multivector=True を設定すると、トークンごとに1つのベクトルモデルが返され、サブワードレベルでの選択が可能になります。

パッセージレベルの選択では、句読点または改行でドキュメントを分割し、各パッセージを個別に埋め込むだけです。または、遅延チャンクでAPIを呼び出して、コンテキストに応じたパッセージベクトルモデルを取得することもできます。これにより、通常、下流タスクのパフォーマンスが向上します。

長文コンテキスト埋め込みモデルにおける遅延チャンク

コンテキスト情報を保持しながら長いドキュメントをチャンクに分割することは困難です。より優れた検索アプリケーションのために、長文コンテキスト埋め込みモデルを活用してコンテキストに応じたチャンク埋め込みを生成する「遅延チャンク」を紹介します。

Jina AIMichael Günther, Han Xiao

同種の要素セット内のセマンティック類似度を測定しているため（クエリとドキュメントのような異種の要素を比較するのではなく、すべて同じ機能的な役割を果たしています。パッセージの重み付けのやり直しで説明します）、text-matching LoRAアダプターを有効にして jina-embeddings-v4 を呼び出す価値があります。

Jina Embeddings v4：マルチモーダル多言語検索のためのユニバーサルベクトルモデル

Jina Embeddings v4 は、シングルベクトルモデルとマルチベクトルモデルの両方の出力をサポートする、マルチモーダルおよび多言語検索向けの38億パラメーターのユニバーサルベクトルモデルです。

Jina AIJina AI

tag遅延貪欲法

以前の記事と同様に、遅延貪欲法を使用して最適化問題を解決します。単調劣モジュラ関数の場合、このアルゴリズムは $(1 - 1/e) \approx 0.632$ の近似保証を実現します。これは証明可能なタイトな範囲です。遅延貪欲最適化は、劣モジュラ関数の2つの基本的な特性（収益逓減性と、反復処理における限界利益の相対的な順序の保持）を利用します。アルゴリズムは次のように機能します。

1. 初期化：すべての要素の初期限界利益を計算し、優先度キューに格納します。
2. 遅延評価：各反復で、キャッシュされた最大の利益を持つ要素を抽出します。
3. 検証：この要素の利益が現在の反復で計算された場合、すぐに選択します。
4. 再計算：それ以外の場合は、現在の限界利益を再計算し、キューに再挿入します。

この遅延貪欲法は、特に限界利益が要素間で大きく異なる場合に、計算のオーバーヘッドを大幅に削減します。

tag劣モジュラ最適化によるパッセージの重み付けのやり直し

Google Colab

パッセージの重み付けのやり直しタスクは、新しい目的（選択されたサブセットが与えられたクエリに関連している必要がある）を追加することでテキスト選択を拡張します。テキスト選択はドキュメント内の純粋な多様性を最適化しますが、パッセージの重み付けのやり直しでは、多様性とクエリの関連性のバランスを取る必要があります。主な表記法は次のとおりです。

• $S \subseteq \{1, 2, \ldots, P\}$ は、$P$ 個のパッセージの候補セットから選択されたパッセージインデックスのサブセットです。これは、特定の手順における DeepResearch システム内のすべてのコンテンツまたはメモリです。$S$ は、次の推論ステップに進めたい厳選されたサブセットを表します。$Q$ 個のクエリと $P$ 個の候補パッセージがあります。従来の検索では $|Q|=1$ ですが、クエリが頻繁に言い換えられ、生成される DeepResearch では、複数のクエリが手元にある場合があります。
• $s_{ij}$ はパッセージ $i$ と $j$ の類似度です。これは、テキスト選択タスクで行ったように、すべてのパッセージに対して task="text-matching" LoRA を有効にした jina-embeddings-v4 のコサイン類似度を使用します。
• $r_{qi}$ はクエリ $q$ とパッセージ $i$ の関連性スコアです。これは、クエリの場合は task="retrieval", prompt_name="query" 、パッセージの場合は task="retrieval", prompt_name="passage" で jina-embeddings-v4 を使用してコサイン類似度として計算され、非対称検索 LoRA を有効にし、異種のベクトルモデルを生成します。

これで、関連性と多様性の間の明確なトレードオフをそれぞれキャプチャする2つの異なる劣モジュラ関数を使用して、これを定式化できます。

tag施設配置の定式化

各パッセージは、最も類似した選択されたパッセージによって「カバー」され、その選択されたパッセージが各クエリにどの程度関連しているかによって重み付けされます。この定式化では、クエリに関連性があり、他の多くのパッセージの代表でもあるパッセージを選択します。

$$f_{FL}(S) = \sum_{q=1}^{Q} \sum_{i=1}^{P} \max_{j \in S} r_{qj} \cdot s_{ij}$$

クエリの関連性 ($r_{qj}$) とパッセージの類似性 ($s_{ij}$) の乗法的な相互作用により、「ハブ」（関連性の高い回答と多様な代表の両方として二重の目的を果たすパッセージ）が作成されます。関連性の高いパッセージは多くの類似したパッセージをカバーできますが、関連性の低いパッセージは、より適切な代表が存在しない場合にのみカバレッジを提供します。

tag飽和カバレッジの定式化

各パッセージについて、クエリの関連性または最適な選択された代表によるカバレッジの程度のうち、最小のものに等しいクレジットを受け取ります。これにより、他の多くのパッセージの関連性を「飽和」させることができるパッセージを選択することが推奨されます。

$$f_{SC}(S) = \sum_{q=1}^{Q} \sum_{i=1}^{P} \min(r_{qi}, \max_{j \in S} s_{ij})$$

min演算は関連性の天井を作成します。パッセージのクエリに対する固有の関連性よりも多くのカバレッジクレジットを得ることはできません。この定式化はより保守的であり、多様だが無関係なパッセージの過剰な選択を防ぎます。

どちらの関数も単調で劣モジュラであり、$(1-1/e)$ の近似保証を備えた同じ遅延貪欲法を有効にします。

tag実験結果

実装では、Jina Reader を使用して以前のブログ投稿からプレーンテキストを取得し、パッセージの重み付けのやり直しを使用してさまざまなクエリを評価します。読者の皆様が、独自の記事を使用して Google Colab ノートブックを試してみることを強くお勧めします。最もよく知っているコンテンツは、最も有意義な洞察を提供します。

実験では、各ドキュメントから上位10個のパッセージを選択します。3つのアルゴリズム（クエリの関連性のみ、施設配置、および飽和カバレッジ）はすべて単調性を示します。$k$ が大きいほど、$k-1$ 個の要素のランキングは変わりません。たとえば、$k=9$、$k=10$、または $k=11$ を比較すると、上位9個のパッセージはすべての値で同一のままです。結果を以下に示します。

重要な観察点がいくつかあります。まず、劣モジュラ最適化アルゴリズムは、クエリの関連性スコアに緩やかに従いますが、戦略的な並べ替えを導入します。つまり、ランキングにおいてパッセージが「上下に移動」します。この挙動は、これらのアルゴリズムが純粋な関連性よりも冗長性の最小化を最適化するため、私たちの予想と一致します。結果として得られるランキングは、高い品質を示しています。

一部の読者は、最初、2番目、4番目の例で、劣モジュラ最適化の結果が早期に「飽和」し、順序付けられたパッセージ0、1、2などを単純に出力することに気付くかもしれません。これはアルゴリズムの失敗ではありません。既存のどの**重排器**も約束できない、劣モジュラ最適化の最も価値のある機能の1つを明らかにしています。

この飽和の挙動をより良く理解するために、ドキュメント内の最大パッセージ数までの、可能なすべてのセットサイズ$k$に対する劣モジュラ関数の値をプロットします。これにより、作用における収穫逓減の法則が明らかになります。

上記のプロットは、選択サイズを増やすにつれて、施設配置関数と飽和カバレッジ関数がどのように動作するかを示しています。どちらも古典的な劣モジュラパターンを示しています。

• 急速な初期成長：最初のいくつかの選択で最も急な増加が発生します。
• 収穫逓減：追加のパッセージごとに、限界利益が徐々に減少します。
• 飽和プラトー：関数値が平坦になり、それ以上の追加からの利益が最小限であることを示します。

これらの点を超えると、限界利益はごくわずかになります。これは、以前のランキング実験で順次順序（0、1、2、...）を示した理由を説明しています。アルゴリズムは、追加のパッセージが最小限の価値しか貢献しないことを正しく識別しました。

この挙動は、劣モジュラ性の数学的特性を直接示しています。私たちが見る限界利益の減少は、アルゴリズムのアーチファクトではなく、カバレッジ関数の基本的な特性です。関数値が横ばいになると、次の点に達したことになります。

$$\Delta_i(S) = f(S \cup \{i\}) - f(S) \approx 0$$

残りのすべてのパッセージ$i \notin S$について。

tag結論

コンテキストエンジニアリングはAIにおける流行語として登場しており、**LLM**のコンテキストウィンドウを埋めるために最も関連性の高い情報をキュレートするエージェントシステムの構築に向けたパラダイムシフトとして頻繁に喧伝されており、これはしばしばRAGを介して外部データを取得することから始まります。

テキスト選択とパッセージの**重排**は、コンテキストエンジニアリングの不可欠な構成要素であり、特にナレッジベースの選択、検索、およびコンテキストの圧縮のプロセスにおいて重要です。パッセージの**重排**は、クエリの関連性に基づいて選択されたテキストを並べ替えることによって、これをさらに洗練し、**LLM**が最初に最も有用な情報を受け取るようにし、過負荷を回避して出力品質を向上させます。

劣モジュラ最適化は、テキスト選択とパッセージの**重排**に対する従来のアプローチよりも、3つの説得力のある利点を提供します。

tag計算効率を備えた理論的厳密性

ヒューリスティックな方法とは異なり、劣モジュラ最適化は証明可能な保証を提供します。レイジーグリーディアルゴリズムは$O(nk \log n)$時間で実行されます。これは、徹底的な検索のための$\binom{n}{k}$の組み合わせと比較して、最適なソリューションへの$(1-1/e) \approx 0.632$近似を達成します。これは、私たちのソリューションが数学的に保証されており、理論的に可能な最良の選択肢の少なくとも63％の良さであることを意味します。**プロンプト**ベースのヒューリスティックは、このレベルのパフォーマンス保証を約束することはできません。

tagスマートな停止基準

私たちが見た飽和の挙動は、自動停止メカニズムを提供します。限界利益がゼロに近づくと、要素の追加を停止することがわかります。この機能は、セットレベルの収穫逓減を理解せずに各アイテムを個別に操作する、既存のポイントワイズまたはリストワイズの**重排器**では実現できません。関数自体が、十分なカバレッジを取得したかどうかを教えてくれます。

tagマルチクエリ拡張

このフレームワークは、クエリが頻繁に書き換えられ、言い換えられるDeepResearchで一般的な、マルチクエリシナリオに自然に拡張されます。同じ理論的基礎とレイジーグリーディアルゴリズムがシームレスに適用されます。**プロンプト**ベースのアプローチには、この体系的な拡張性が欠けており、多くの場合、新しいシナリオごとにアドホックなソリューションが必要です。

これらの利点は、エンジニアリングのトリックではなく、劣モジュラ性の数学的基盤に由来します。他の人が**プロンプト**チューニングに依存して良い結果を期待する一方で、信頼性が高くスケーラブルなコンテキストエンジニアリングを構築する際には不可欠な利点である、正式な保証を備えた原則的なフレームワークを提供する劣モジュラ最適化を学ぶ必要があります。