DeepResearchにおける多様なクエリ生成のための劣モジュラ最適化

DeepResearchを実装する際、多様なクエリを生成する必要がある箇所が少なくとも2つあります。まず、ユーザー入力に基づいてウェブ検索クエリを生成する必要があります（ユーザー入力をそのまま検索エンジンに投げ込むのは良い方法ではありません）。次に、多くのDeepResearchシステムには、元の問題をサブ問題に分解する「リサーチプランナー」が含まれており、エージェントを並行して呼び出して個別に解決し、その結果をマージします。クエリを扱う場合でも、サブ問題を扱う場合でも、私たちの期待は変わりません。元の入力と関連性があり、元の入力に対して独自の視点を提供するのに十分な多様性を持っている必要があります。多くの場合、検索エンジンの不要なリクエストやエージェントのトークンの使用にお金を浪費しないように、クエリの数を制限する必要があります。

クエリ生成の重要性を理解している一方で、ほとんどのオープンソースのDeepResearch実装では、この最適化を真剣に受け止めていません。これらの制約を直接プロンプトに入力するだけです。一部では、LLMに追加のターンを要求して、クエリを評価および多様化する場合があります。ほとんどの実装が基本的にどのようにアプローチしているかの例を次に示します。

この記事では、文のベクトルモデルと劣モジュラ最適化を使用して、最適なクエリ生成を解決するためのより厳密なアプローチを実証したいと思います。博士課程の頃、劣モジュラ最適化はL-BFGSと並んで私のお気に入りのテクニックの1つでした。カーディナリティ制約の下で多様なクエリのセットを生成するためにそれを適用する方法を示します。これにより、DeepResearchシステムの全体的な品質を大幅に向上させることができます。

tagプロンプトによるクエリ生成

まず、プロンプトが多様なクエリを生成するための効果的なアプローチであるかどうかを確認します。また、洗練されたプロンプトが単純なプロンプトよりも効果的かどうかを理解したいと思います。以下の2つのプロンプトを比較して、調べてみましょう。

You are an expert at generating diverse search queries. Given any input topic, generate {num_queries} different search queries that explore various angles and aspects of the topic.
コピー

You are an expert research strategist. Generate an optimal set of diverse search queries that maximizes information coverage while minimizing redundancy.

Task: Create exactly {num_queries} search queries from any given input that satisfy:
- Relevance: Each query must be semantically related to the original input
- Diversity: Each query should explore a unique facet with minimal overlap
- Coverage: Together, the queries should comprehensively address the topic

Process:
1. Decomposition: Break down the input into core concepts and dimensions
2. Perspective Mapping: Identify distinct angles (theoretical, practical, historical, comparative, etc.)
3. Query Formulation: Craft specific, searchable queries for each perspective
4. Diversity Check: Ensure minimal semantic overlap between queries
コピー

元のクエリ"embeddings and rerankers"でLLMとしてgemini-2.5-flashを使用し、単純なプロンプトと構造化されたプロンプトの両方をテストして、1つから20のクエリを反復的に生成します。次に、text-matchingタスクでjina-embeddings-v3を使用して、元のクエリと生成されたクエリの間の文の類似度、および生成されたクエリ自体の類似度を測定します。以下に視覚化を示します。

右側の2つのプロットを見ると、単純なプロンプトと構造化されたプロンプトの両方がコサイン類似度スコアに大きなばらつきを示しており、多くが0.7〜0.8の類似度に達していることがわかります。これは、生成されたクエリのいくつかがほぼ同一であることを示唆しています。さらに、どちらの方法も、より多くのクエリが生成されるにつれて多様性を維持するのに苦労しています。クエリ数の増加に伴う類似度の明確な下降傾向が見られる代わりに、比較的安定した（そして高い）類似度レベルが観察されます。これは、追加のクエリが既存の視点を複製することが多いことを示しています。

1つの説明は、Wangら（2025）が発見したことです。LLMは、プロンプトステアリングを行っても、支配的なグループの意見を不均衡に反映することが多く、一般的な視点への偏りを示しています。これは、LLMのトレーニングデータが特定の視点を過剰に表現している可能性があり、モデルがこれらの一般的な視点に沿ったバリエーションを生成する原因となるためです。Abeら（2025）はまた、LLMベースのクエリ拡張が一般的な解釈を優先し、他の解釈を見落としていることを発見しました。たとえば、「AIの利点は何ですか？」は、自動化、効率、倫理性などの一般的な利点をもたらす可能性がありますが、創薬などのあまり明白ではない利点を見逃す可能性があります。

Multilingual Prompting for Improving LLM Generation Diversity

Large Language Models (LLMs) are known to lack cultural representation and overall diversity in their generations, from expressing opinions to answering factual questions. To mitigate this problem, we propose multilingual prompting: a prompting method which generates several variations of a base prompt with added cultural and linguistic cues from several cultures, generates responses, and then combines the results. Building on evidence that LLMs have language-specific knowledge, multilingual prompting seeks to increase diversity by activating a broader range of cultural knowledge embedded in model training data. Through experiments across multiple models (GPT-4o, GPT-4o-mini, LLaMA 70B, and LLaMA 8B), we show that multilingual prompting consistently outperforms existing diversity-enhancing techniques such as high-temperature sampling, step-by-step recall, and personas prompting. Further analyses show that the benefits of multilingual prompting vary with language resource level and model size, and that aligning the prompting language with the cultural cues reduces hallucination about culturally-specific information.

arXiv.orgQihan Wang

Wisdom from Diversity: Bias Mitigation Through Hybrid Human-LLM Crowds

Despite their performance, large language models (LLMs) can inadvertently perpetuate biases found in the data they are trained on. By analyzing LLM responses to bias-eliciting headlines, we find that these models often mirror human biases. To address this, we explore crowd-based strategies for mitigating bias through response aggregation. We first demonstrate that simply averaging responses from multiple LLMs, intended to leverage the “wisdom of the crowd”, can exacerbate existing biases due to the limited diversity within LLM crowds. In contrast, we show that locally weighted aggregation methods more effectively leverage the wisdom of the LLM crowd, achieving both bias mitigation and improved accuracy. Finally, recognizing the complementary strengths of LLMs (accuracy) and humans (diversity), we demonstrate that hybrid crowds containing both significantly enhance performance and further reduce biases across ethnic and gender-related contexts.

arXiv.orgAxel Abels

tag問題の定式化

以前の実験は結論が出ておらず、プロンプトを改善して再試行する必要があると思うかもしれません。プロンプトは確かに結果をある程度変えることができますが、より重要なのは、私たちが何かを学んだということです。生成されたクエリの数を増やすだけで、多様なクエリを取得できる可能性が高くなります。悪いニュースは、副作用として重複したクエリもたくさん取得していることです。

しかし、多数のクエリを生成するのは安価であり、最終的にはいくつか良いクエリが得られるので、これをサブセット選択の問題として扱うのはどうでしょうか？

数学では、この問題を以下のように定式化できます。元の入力 $q_0$、プロンプトエンジニアリングを使用して LLM によって生成された候補クエリの集合 $V=\{q_1, q_2, \cdots, q_n\}$ が与えられたとき、カバレッジを最大化し、冗長性を最小化する $k$ 個のクエリのサブセット $X\subseteq V$ を選択します。

残念ながら、$n$ 個の候補から最適な $k$ 個のクエリのサブセットを見つけるには、$\binom{n}{k}$ の組み合わせを調べる必要があり、これは指数関数的な複雑さになります。 たった 20 個の候補と $k=5$ の場合でも、15,504 通りの組み合わせがあります。

tag劣モジュラ関数

サブセット選択問題を力ずくで解決する前に、劣モジュラ性と劣モジュラ関数という用語を紹介します。 多くの人には馴染みがないかもしれませんが、「収穫逓減」という考え方は聞いたことがあるでしょう。 劣モジュラ性とは、それを数学的に表現したものです。

大規模な建物でインターネットカバレッジを提供するために Wi-Fi ルーターを設置することを考えてみましょう。 最初に設置したルーターは、以前はカバレッジがなかった広い範囲をカバーするため、非常に大きな価値をもたらします。 2 番目のルーターもかなりの価値を追加しますが、そのカバレッジエリアの一部は最初のルーターと重複するため、限界利益は最初のルーターよりも少なくなります。 ルーターを追加し続けると、ほとんどのスペースは既存のルーターで既にカバーされているため、追加のルーターは新しいエリアをカバーしなくなります。 最終的に、10 番目のルーターは、建物が既に十分にカバーされているため、追加のカバレッジをほとんど提供しない可能性があります。

この直感は、劣モジュラ性の本質を捉えています。 数学的には、集合関数 $f: 2^V \rightarrow \mathbb{R}$ は、すべての $A \subseteq B \subseteq V$ と任意の要素 $v \notin B$ に対して、次の場合に劣モジュラです。

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

平易な英語で言うと、小さい集合に要素を追加すると、小さい集合を含む大きい集合に同じ要素を追加するのと同じくらいの利益が得られます。

次に、この概念をクエリ生成の問題に適用しましょう。 クエリの選択は、自然な収穫逓減を示すことにすぐに気付くでしょう。

• 最初に選択したクエリは、完全に新しいセマンティックスペースをカバーします
• 2 番目のクエリは異なる側面をカバーする必要がありますが、ある程度の重複は避けられません
• クエリを追加するにつれて、追加のクエリは新しい領域をカバーしなくなります

tagベクトルモデルに基づく劣モジュラ関数の設計

$\mathbf{e}_i \in \mathbb{R}^d$ を、文のベクトルモデル（例：jina-embeddings-v3）を使用して取得したクエリ $q_i$ のベクトルモデルとします。 目的関数を設計するには、主に 2 つのアプローチがあります。

tagアプローチ 1：施設配置（カバレッジベース）

$$f_{\text{coverage}}(X) = \sum_{j=1}^{n} \max\left(\alpha \cdot \text{sim}(\mathbf{e}_0, \mathbf{e}_j), \max_{q_i \in X} \text{sim}(\mathbf{e}_j, \mathbf{e}_i)\right)$$

この関数は、選択された集合 $X$ がすべての候補クエリをどの程度「カバー」しているかを測定します。ここで：

• $\text{sim}(\mathbf{u}, \mathbf{v}) = \frac{\mathbf{u} \cdot \mathbf{v}}{|\mathbf{u}| |\mathbf{v}|}$ はコサイン類似度です
• $\alpha \cdot \text{sim}(\mathbf{e}_0, \mathbf{e}_j)$ は、元のクエリとの関連性を保証します
• $\max_{q_i \in X} \text{sim}(\mathbf{e}_j, \mathbf{e}_i)$ は、選択された集合 $X$ による候補 $j$ のカバレッジを測定します

注意点の 1 つは、この関数が暗黙的に多様性を促進することです。 選択された集合 $X$ 内の類似度を明示的にペナルティしません。 多様性は、類似したクエリを選択すると、カバレッジの収益が減少するために生じます。

tagアプローチ 2：明示的なカバレッジ+多様性

多様性をより直接的に制御するには、カバレッジと明示的な多様性項を組み合わせることができます。

$$f(X) = \lambda \cdot f_{\text{coverage}}(X) + (1-\lambda) \cdot f_{\text{diversity}}(X)$$

ここで、多様性コンポーネントは次のように定式化できます。

$$f_{\text{diversity}}(X) = \sum_{q_i \in X} \sum_{q_j \in V \setminus X} \text{sim}(\mathbf{e}_i, \mathbf{e}_j)$$

この多様性項は、選択されたクエリと選択されていないクエリの間の総類似度を測定します。これは、残りの候補とは異なるクエリを選択した場合に最大化されます（グラフカット関数の形式）。

tag2 つのアプローチの違い

どちらの定式化も劣モジュラ性を維持します。

施設配置関数は、よく知られた劣モジュラ関数です。 これは、max 演算のために劣モジュラ性を示します。新しいクエリ $q$ を選択された集合に追加すると、各候補クエリ $j$ は、集合内の「最良の」クエリ（最も類似性の高いクエリ）によってカバーされます。 $q$ を小さい集合 $A$ に追加すると、多くの候補が既に十分にカバーされている大きい集合 $B \supseteq A$ に追加するよりも、さまざまな候補のカバレッジが向上する可能性が高くなります。

グラフカット多様性関数では、多様性項 $\sum_{q_i \in X} \sum_{q_j \in V \setminus X} \text{sim}(\mathbf{e}_i, \mathbf{e}_j)$ は、選択された集合と選択されていない集合の間の「カット」を測定するため、劣モジュラです。 新しいクエリを小さい選択された集合に追加すると、大きい選択された集合に追加するよりも、選択されていないクエリへの新しい接続がより多く作成されます。

施設配置アプローチは、カバレッジの競合を通じて暗黙的な多様性に依存しますが、明示的なアプローチは多様性を直接測定および最適化します。 したがって、どちらも有効ですが、明示的なアプローチを使用すると、関連性と多様性のトレードオフをより直接的に制御できます。

tag実装

GitHub - jina-ai/submodular-optimization

Contribute to jina-ai/submodular-optimization development by creating an account on GitHub.

GitHubjina-ai

関数は劣モジュラであるため、$(1-1/e) \approx 0.63$ の近似保証を提供する貪欲アルゴリズムを使用できます。

$$\max_{X \subseteq V} f(X) \quad \text{subject to} \quad |X| \leq k$$

次に、施設配置（カバレッジベース）を最適化するためのコードを示します。これは暗黙的な多様性を持つものです。

def greedy_query_selection(candidates, embeddings, original_embedding, k, alpha=0.3):
    """
    Greedy algorithm for submodular query selection
    
    Args:
        candidates: List of candidate query strings
        embeddings: Matrix of query embeddings (n x d)
        original_embedding: Embedding of original query (d,)
        k: Number of queries to select
        alpha: Relevance weight parameter
    """
    n = len(candidates)
    selected = []
    remaining = set(range(n))
    
    # Precompute relevance scores
    relevance_scores = cosine_similarity(original_embedding, embeddings)
    
    for _ in range(k):
        best_gain = -float('inf')
        best_query = None
        
        for i in remaining:
            # Calculate marginal gain of adding query i
            gain = compute_marginal_gain(i, selected, embeddings, 
                                       relevance_scores, alpha)
            if gain > best_gain:
                best_gain = gain
                best_query = i
        
        if best_query is not None:
            selected.append(best_query)
            remaining.remove(best_query)
    
    return [candidates[i] for i in selected]

def compute_marginal_gain(new_idx, selected, embeddings, relevance_scores, alpha):
    """Compute marginal gain of adding new_idx to selected set"""
    if not selected:
        # First query: gain is sum of all relevance scores
        return sum(max(alpha * relevance_scores[j], 
                      cosine_similarity(embeddings[new_idx], embeddings[j]))
                  for j in range(len(embeddings)))
    
    # Compute current coverage
    current_coverage = [
        max([alpha * relevance_scores[j]] + 
            [cosine_similarity(embeddings[s], embeddings[j]) for s in selected])
        for j in range(len(embeddings))
    ]
    
    # Compute new coverage with additional query
    new_coverage = [
        max(current_coverage[j], 
            cosine_similarity(embeddings[new_idx], embeddings[j]))
        for j in range(len(embeddings))
    ]
    
    return sum(new_coverage) - sum(current_coverage)
コピー

バランスパラメータ $\alpha$ は、関連性と多様性の間のトレードオフを制御します。

• 高い $\alpha$ （例：0.8）：元のクエリとの関連性を優先し、多様性を犠牲にする可能性があります
• 低い $\alpha$ （例：0.2）：選択されたクエリ間の多様性を優先し、元の意図からずれる可能性があります
• 中程度の $\alpha$ （例：0.4〜0.6）：バランスの取れたアプローチで、多くの場合、実際にうまく機能します

tag怠惰な貪欲アルゴリズム

上記のコードでは、次のことに気付くでしょう。

for i in remaining:
    # Calculate marginal gain of adding query i
    gain = compute_marginal_gain(i, selected, embeddings, 
                               relevance_scores, alpha)
コピー

各反復で、残りのすべての候補に対して限界利益を計算しています。 これよりも良い方法があります。

怠惰な貪欲アルゴリズムは、不要な計算を回避するために劣モジュラ性を利用する巧妙な最適化です。 重要な洞察は、要素 A が反復 $t$ で要素 B よりも高い限界利益を持っていた場合、A は反復 $t+1$ でも B よりも高い限界利益を持つということです（劣モジュラ性のため）。

import heapq

def lazy_greedy_query_selection(candidates, embeddings, original_embedding, k, alpha=0.3):
    """
    Lazy greedy algorithm for submodular query selection
    More efficient than standard greedy by avoiding unnecessary marginal gain computations
    """
    n = len(candidates)
    selected = []
    
    # Precompute relevance scores
    relevance_scores = cosine_similarity(original_embedding, embeddings)
    
    # Initialize priority queue: (-marginal_gain, last_updated, query_index)
    # Use negative gain because heapq is a min-heap
    pq = []
    for i in range(n):
        gain = compute_marginal_gain(i, [], embeddings, relevance_scores, alpha)
        heapq.heappush(pq, (-gain, 0, i))
    
    for iteration in range(k):
        while True:
            neg_gain, last_updated, best_idx = heapq.heappop(pq)
            
            # If this gain was computed in current iteration, it's definitely the best
            if last_updated == iteration:
                selected.append(best_idx)
                break
            
            # Otherwise, recompute the marginal gain
            current_gain = compute_marginal_gain(best_idx, selected, embeddings, 
                                               relevance_scores, alpha)
            heapq.heappush(pq, (-current_gain, iteration, best_idx))
    
    return [candidates[i] for i in selected]
コピー

Lazy greedyは次のように機能します。

1. 限界利益でソートされた要素の優先度付きキューを維持します。
2. 上位要素の限界利益のみを再計算します。
3. 再計算後もそれがまだ最高であれば、それを選択します。
4. それ以外の場合は、正しい位置に再挿入し、次の上位要素を確認します。

これにより、選択されないことが明らかな要素の限界利益を再計算することを回避できるため、大幅な高速化が可能です。

tag結果

実験を再度実行してみましょう。同じ単純なプロンプトを使用して、1〜20個の多様なクエリを生成し、以前と同様にコサイン類似度の測定を実行します。劣モジュラ最適化では、kの異なる値を使用して生成された20個の候補からクエリを選択し、以前と同様に類似度を測定します。結果は、劣モジュラ最適化によって選択されたクエリはより多様であり、セット内類似度が低いことを示しています。

tag最後の質問：なぜ劣モジュラルの定式化が重要なのか

なぜ、これを劣モジュラル最適化問題として定式化するのに苦労するのか疑問に思うかもしれません。ヒューリスティックや他の最適化アプローチを使用するだけではいけないのでしょうか？

簡単に言うと、劣モジュラルの定式化は、アドホックな「多様なクエリを選択する」ヒューリスティックを、証明可能な保証、効率的なアルゴリズム、および測定可能な目的を持つ厳密な最適化問題に変換します。

tag保証された効率

目的関数が劣モジュラルであることが証明されると、強力な理論的保証と効率的なアルゴリズムが得られます。$\binom{n}{k}$の組み合わせをチェックするのと比較して、$O(nk)$時間で実行されるgreedyアルゴリズムは、最適解への$(1-1/e) \approx 0.63$近似を達成します。これは、greedy解が常に可能な限り最良の解の少なくとも63％の精度であることを意味します。これを約束できるヒューリスティックはありません。

さらに、lazy greedyアルゴリズムは、劣モジュラル関数の数学的構造により、実際には劇的に高速です。高速化は、収穫逓減から来ています。以前の反復で選択肢として不適切だった要素は、後で適切な選択肢になる可能性は低いです。したがって、すべての$n$個の候補をチェックする代わりに、lazy greedyは通常、上位のいくつかの候補のゲインを再計算するだけで済みます。

tag手作りのヒューリスティックは不要

原則的なフレームワークがない場合、「クエリのコサイン類似度が0.7未満であることを確認する」または「異なるキーワードカテゴリのバランスを取る」のようなアドホックなルールに頼る可能性があります。これらのルールは調整が難しく、一般化されません。劣モジュラル最適化は、原則に基づいた、数学的に根拠のあるアプローチを提供します。検証セットを使用してハイパーパラメータを体系的に調整し、本番システムでソリューションの品質を監視できます。システムが不十分な結果を生成した場合、何が問題だったのかをデバッグするための明確なメトリックがあります。

最後に、劣モジュラル最適化は数十年にわたる研究が行われている分野であり、greedyを超える高度なアルゴリズム（加速されたgreedyやローカル検索など）、特定の定式化がいつ最適に機能するかについての理論的な洞察、および予算制限や公平性の要件などの追加の制約を処理するための拡張を活用できます。

submodularity.org: Tutorials, References, Activities and Tools for Submodular Optimization