Субмодульная оптимизация для генерации разнообразных запросов в DeepResearch

При реализации DeepResearch есть как минимум два места, где вам нужно генерировать разнообразные запросы. Во-первых, вы должны генерировать поисковые запросы на основе ввода пользователя (непосредственная отправка ввода пользователя в поисковую систему — не лучшая идея). Во-вторых, многие системы DeepResearch включают "планировщик исследований", который разбивает исходную проблему на подзадачи, одновременно вызывает агентов для их независимого решения, а затем объединяет их результаты. Независимо от того, имеем ли мы дело с запросами или подзадачами, наши ожидания остаются прежними: они должны быть релевантны исходному вводу и достаточно разнообразны, чтобы предложить уникальные точки зрения на него. Часто нам необходимо ограничить количество запросов, чтобы не тратить деньги на ненужные запросы к поисковой системе или использование токенов агента.

Понимая важность генерации запросов, большинство реализаций DeepResearch с открытым исходным кодом не воспринимают эту оптимизацию всерьез. Они просто напрямую указывают эти ограничения в своих подсказках (Prompt). Некоторые могут попросить Большую языковую модель (LLM) о дополнительном ходе для оценки и диверсификации запросов. Вот пример того, как большинство реализаций в основном подходят к этому:

В этой статье я хочу продемонстрировать более строгий подход к решению задачи оптимальной генерации запросов с использованием векторных моделей предложений и субмодульной оптимизации. В мои дни учебы в аспирантуре субмодульная оптимизация была одной из моих любимых техник наряду с L-BFGS. Я покажу, как применить ее для генерации набора разнообразных запросов при кардинальном ограничении, что может значительно улучшить общее качество систем DeepResearch.

tagГенерация запросов с помощью Prompt

Во-первых, мы хотим проверить, является ли использование Prompt эффективным подходом для генерации разнообразных запросов. Мы также хотим понять, является ли сложный Prompt более эффективным, чем простой Prompt. Давайте проведем эксперимент, сравнив два Prompt ниже, чтобы это выяснить:

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
Копировать

Мы используем gemini-2.5-flash в качестве Большой языковой модели (LLM) с исходным запросом "embeddings and rerankers" и тестируем как простой, так и структурированный Prompt для итеративной генерации от одного до 20 запросов. Затем мы используем jina-embeddings-v3 с задачей text-matching для измерения семантической близости между исходным запросом и сгенерированными запросами, а также близости внутри самих сгенерированных запросов. Вот визуализации.

Посмотрите на два графика справа, и вы увидите, что как простой, так и структурированный Prompt демонстрируют большую дисперсию в оценках косинусной близости, причем многие достигают близости 0,7-0,8, что говорит о том, что некоторые сгенерированные запросы почти идентичны. Кроме того, обоим методам трудно поддерживать разнообразие по мере генерации большего количества запросов. Вместо того чтобы видеть четкую тенденцию к снижению близости с увеличением количества запросов, мы наблюдаем относительно стабильные (и высокие) уровни близости, что указывает на то, что дополнительные запросы часто дублируют существующие перспективы.

Одно из объяснений состоит в том, что Wang et al. (2025) обнаружили, что Большие языковые модели (LLM) часто отражают мнения доминирующих групп непропорционально, даже при управлении Prompt, что указывает на предвзятость в отношении общих точек зрения. Это связано с тем, что данные обучения Большой языковой модели (LLM) могут чрезмерно представлять определенные точки зрения, в результате чего модель генерирует варианты, которые соответствуют этим распространенным точкам зрения. Abe et al. (2025) также обнаружили, что расширение запросов на основе Большой языковой модели (LLM) отдает предпочтение популярным интерпретациям, игнорируя другие. Например, "Каковы преимущества ИИ?" может привести к общим преимуществам, таким как автоматизация, эффективность, этичность, но упустить менее очевидные, такие как открытие лекарств.

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Формулировка задачи

Кто-то может подумать, что наш предыдущий эксперимент неубедителен и что нам следует улучшить Prompt и повторить попытку. Хотя Prompt, безусловно, может в некоторой степени изменить результаты, более важно то, что мы кое-что узнали: простое увеличение количества сгенерированных запросов повышает вероятность получения разнообразных запросов. Плохая новость заключается в том, что мы также получаем кучу дублированных запросов в качестве побочного продукта.

Но поскольку генерировать большое количество запросов дешево, что в конечном итоге дает несколько хороших, почему бы нам не рассматривать это как задачу выбора подмножества?

В математике эту задачу можно сформулировать следующим образом: даны исходные входные данные $q_0$, набор запросов-кандидатов $V=\{q_1, q_2, \cdots, q_n\}$, сгенерированных LLM с использованием разработки 提示词. Выберите подмножество $X\subseteq V$ из $k$ запросов, которое максимизирует охват при минимизации избыточности.

К сожалению, для нахождения оптимального подмножества из $k$ запросов из $n$ кандидатов необходимо проверить $\binom{n}{k}$ комбинаций — экспоненциальная сложность. Только для 20 кандидатов и $k=5$ это 15 504 комбинации.

tagСубмодулярная функция

Прежде чем пытаться грубо решить задачу выбора подмножества, позвольте мне представить читателям термины субмодулярность и субмодулярная функция. Они могут показаться незнакомыми многим, но вы, возможно, слышали об идее "убывающей отдачи" — субмодулярность является математическим представлением этого.

Представьте себе размещение Wi-Fi роутеров для обеспечения интернет-покрытия в большом здании. Первый установленный вами роутер дает огромную ценность — он покрывает значительную площадь, где раньше не было покрытия. Второй роутер также добавляет существенную ценность, но некоторая часть его зоны покрытия перекрывается с первым роутером, поэтому предельная выгода меньше, чем от первого. По мере того как вы продолжаете добавлять роутеры, каждый дополнительный роутер покрывает все меньше и меньше новой площади, поскольку большинство мест уже покрыто существующими роутерами. В конце концов, 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)$$

Проще говоря: добавление элемента к меньшему множеству дает по крайней мере столько же выгоды, сколько добавление того же элемента к большему множеству, которое содержит меньшее множество.

Теперь давайте применим эту концепцию к нашей задаче генерации запросов. Можно сразу понять, что выбор запросов демонстрирует естественную убывающую отдачу:

• Первый выбранный нами запрос охватывает совершенно новое семантическое пространство
• Второй запрос должен охватывать разные аспекты, но некоторое перекрытие неизбежно
• По мере того как мы добавляем больше запросов, каждый дополнительный запрос охватывает все меньше и меньше новой территории

tagРазработка субмодулярной функции на основе 向量模型

Пусть $\mathbf{e}_i \in \mathbb{R}^d$ — вектор 向量模型 для запроса $q_i$, полученный с помощью модели 向量模型 предложений (например, jina-embeddings-v3). Существует два основных подхода к разработке нашей целевой функции:

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)$ измеряет покрытие кандидата $j$ выбранным набором $X$

Одна оговорка заключается в том, что эта функция только косвенно поощряет разнообразие. Она не наказывает явно за сходство внутри выбранного набора $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)$$

Этот член разнообразия измеряет общее сходство между выбранными и невыбранными запросами — он максимизируется, когда мы выбираем запросы, которые отличаются от остальных кандидатов (форма функции разреза графа).

tagРазница между двумя подходами

Обе формулировки сохраняют субмодулярность.

Функция размещения объектов является хорошо известной субмодулярной функцией. Она демонстрирует субмодулярность из-за операции 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 имел более высокий предельный прирост, чем элемент B, на итерации $t$, то A все равно будет иметь более высокий предельный прирост, чем B, на итерации $t+1$ (из-за свойства субмодулярности).

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]
Копировать

Жадный алгоритм с отложенным вычислением работает следующим образом:

1. Поддерживает очередь с приоритетами элементов, отсортированных по их предельным выгодам.
2. Повторно вычисляет предельную выгоду только для верхнего элемента.
3. Если после пересчета он все еще является самым высоким, выбирает его.
4. В противном случае вставляет его в правильную позицию и проверяет следующий верхний элемент.

Это может значительно ускорить процесс, поскольку мы избегаем повторного вычисления предельных выгод для элементов, которые явно не будут выбраны.

tagРезультаты

Давайте снова проведем эксперимент. Мы используем тот же простой 提示词 для создания от одного до 20 различных запросов и выполняем те же измерения косинусной близости, что и раньше. Для субаддитивной оптимизации мы выбираем запросы из 20 сгенерированных кандидатов, используя различные значения k, и измеряем сходство, как и раньше. Результаты показывают, что запросы, выбранные с помощью субаддитивной оптимизации, более разнообразны и показывают более низкое сходство внутри набора.

tagФинальный вопрос: почему важна субаддитивная формулировка?

Вам может быть интересно: зачем утруждать себя формулированием этого как задачи субаддитивной оптимизации? Почему бы просто не использовать эвристики или другие подходы к оптимизации?

Короче говоря, субаддитивная формулировка преобразует специальную эвристику "выбрать разнообразные запросы" в строгую задачу оптимизации с **доказуемыми гарантиями**, **эффективными алгоритмами** и измеримыми целями.

tagГарантированная эффективность

Как только мы докажем, что наша целевая функция является субаддитивной, мы получим мощные теоретические гарантии и эффективный алгоритм. Жадный алгоритм, который выполняется за время $O(nk)$ по сравнению с проверкой $\binom{n}{k}$ комбинаций, достигает $(1-1/e) \approx 0.63$ приближения к оптимальному решению. Это означает, что наше жадное решение всегда как минимум на 63% так же хорошо, как и наилучшее возможное решение. **Никакая эвристика не может этого обещать.**

Более того, жадный алгоритм с отложенным вычислением значительно быстрее на практике благодаря математической структуре субаддитивных функций. Ускорение происходит из-за **уменьшения отдачи**: элементы, которые были плохим выбором в более ранних итерациях, вряд ли станут хорошим выбором позже. Поэтому вместо проверки всех $n$ кандидатов, жадному алгоритму с отложенным вычислением обычно требуется только повторно вычислить выгоды для нескольких лучших кандидатов.

tagНет необходимости в разработанных вручную эвристиках

Без принципиальной структуры вы можете прибегнуть к специальным правилам, таким как "убедиться, что запросы имеют косинусное сходство < 0,7" или "сбалансировать различные категории ключевых слов". Эти правила трудно настраивать, и они не обобщаются. Субаддитивная оптимизация дает вам принципиальный, математически обоснованный подход. Вы можете систематически настраивать гиперпараметры, используя наборы валидации, и отслеживать качество решения в производственных системах. Когда система выдает плохие результаты, у вас есть четкие метрики для отладки того, что пошло не так.

Наконец, субаддитивная оптимизация — это хорошо изученная область с десятилетиями исследований, позволяющая использовать передовые алгоритмы, выходящие за рамки жадных (например, ускоренный жадный алгоритм или локальный поиск), теоретические представления о том, когда определенные формулировки работают лучше всего, и расширения для обработки дополнительных ограничений, таких как бюджетные ограничения или требования справедливости.

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