Optimisation sous-modulaire pour la génération de requêtes diversifiées dans DeepResearch

Lors de l'implémentation de DeepResearch, il y a au moins deux endroits où vous devez générer des requêtes diverses. Premièrement, vous devez générer des requêtes de recherche Web basées sur l'entrée de l'utilisateur (il n'est pas judicieux de simplement envoyer l'entrée de l'utilisateur directement au moteur de recherche). Deuxièmement, de nombreux systèmes DeepResearch incluent un "planificateur de recherche" qui divise le problème original en sous-problèmes, appelle simultanément des agents pour les résoudre indépendamment, puis fusionne leurs résultats. Qu'il s'agisse de requêtes ou de sous-problèmes, nos attentes restent les mêmes : ils doivent être pertinents par rapport à l'entrée originale et suffisamment diversifiés pour fournir des perspectives uniques à ce sujet. Souvent, nous devons limiter le nombre de requêtes pour éviter de gaspiller de l'argent en demandant inutilement des moteurs de recherche ou en utilisant des *tokens* d'agent.

Bien qu'ils comprennent l'importance de la génération de requêtes, la plupart des implémentations DeepResearch *open source* ne prennent pas cette optimisation au sérieux. Ils se contentent d'intégrer directement ces contraintes dans le *prompt*. Certains pourraient demander au LLM un tour supplémentaire pour évaluer et diversifier les requêtes. Voici un exemple de la façon dont la plupart des implémentations abordent cette question :

Dans cet article, je souhaite démontrer une approche plus rigoureuse pour résoudre la génération optimale de requêtes à l'aide de *vecteurs modèles* de phrases et de l'*optimisation sous-modulaire*. À l'époque de mon doctorat, l'optimisation sous-modulaire était l'une de mes techniques préférées avec L-BFGS. Je vais montrer comment l'appliquer pour générer un ensemble de requêtes diverses sous une contrainte de cardinalité, ce qui peut améliorer considérablement la qualité globale des systèmes DeepResearch.

tagGénération de requêtes via le *prompting*

Tout d'abord, nous voulons vérifier si le *prompting* est une approche efficace pour générer des requêtes diverses. Nous voulons également comprendre si un *prompt* sophistiqué est plus efficace qu'un *prompt* simple. Réalisons une expérience comparant les deux *prompts* ci-dessous pour le découvrir :

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.
Copier

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
Copier

Nous utilisons gemini-2.5-flash comme LLM avec la requête originale "embeddings and rerankers" et testons les *prompts* simple et structuré pour générer de manière itérative d'une à 20 requêtes. Nous utilisons ensuite jina-embeddings-v3 avec la tâche text-matching pour mesurer la similarité des phrases entre la requête originale et les requêtes générées, ainsi que la similarité au sein des requêtes générées elles-mêmes. Voici les visualisations.

En regardant les deux graphiques sur le côté droit, on peut constater que les *prompts* simple et structuré présentent une grande variance dans les scores de similarité cosinus, beaucoup atteignant une similarité de 0,7 à 0,8, ce qui suggère que certaines requêtes générées sont presque identiques. De plus, les deux méthodes ont du mal à maintenir la diversité à mesure que davantage de requêtes sont générées. Au lieu de constater une nette tendance à la baisse de la similarité avec l'augmentation du nombre de requêtes, nous observons des niveaux de similarité relativement stables (et élevés), ce qui indique que les requêtes supplémentaires dupliquent souvent les perspectives existantes.

Une explication est ce que Wang et al. (2025) ont constaté que les LLM reflètent souvent de manière disproportionnée les opinions des groupes dominants, même avec le *prompt steering*, ce qui indique un biais envers les perspectives communes. En effet, les données d'entraînement du LLM peuvent surreprésenter certains points de vue, ce qui amène le modèle à générer des variations qui s'alignent sur ces perspectives dominantes. Abe et al. (2025) ont également constaté que l'expansion de requête basée sur le LLM favorise les interprétations populaires tout en négligeant les autres. Par exemple, "Quels sont les avantages de l'IA ?" pourrait produire des avantages courants tels que l'automatisation, l'efficacité, l'éthique, mais manquer des avantages moins évidents comme la découverte de médicaments.

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

tagFormulation du problème

On pourrait penser que notre expérience précédente n'est pas concluante et que nous devrions améliorer le *prompt* et réessayer. Bien que le *prompting* puisse certainement modifier les résultats dans une certaine mesure, ce qui est plus important, c'est que nous avons appris quelque chose : le simple fait d'augmenter le nombre de requêtes générées nous rend plus susceptibles d'obtenir des requêtes diverses. La mauvaise nouvelle est que nous obtenons également un tas de requêtes dupliquées comme sous-produit.

Mais puisqu'il est peu coûteux de générer un grand nombre de requêtes, ce qui finit par donner quelques bonnes requêtes, pourquoi ne pas traiter cela comme un problème de sélection de sous-ensembles ?

En mathématiques, voici comment nous pouvons formuler ce problème : étant donné une entrée originale $q_0$, un ensemble de requêtes candidates $V=\{q_1, q_2, \cdots, q_n\}$ générées par un LLM en utilisant l'ingénierie de Prompt. Sélectionnez un sous-ensemble $X\subseteq V$ de $k$ requêtes qui maximise la couverture tout en minimisant la redondance.

Malheureusement, trouver le sous-ensemble optimal de $k$ requêtes parmi $n$ candidats nécessite de vérifier $\binom{n}{k}$ combinaisons - une complexité exponentielle. Pour seulement 20 candidats et $k=5$, cela représente 15 504 combinaisons.

tagFonction Sous-modulaire

Avant d'essayer de résoudre brutalement le problème de sélection de sous-ensemble, permettez-moi de présenter aux lecteurs les termes sous-modularité et fonction sous-modulaire. Ils peuvent sembler inconnus à beaucoup, mais vous avez peut-être entendu parler de l'idée de "rendements décroissants" - eh bien, la sous-modularité est la représentation mathématique de cela.

Considérez le placement de routeurs Wi-Fi pour fournir une couverture Internet dans un grand bâtiment. Le premier routeur que vous installez apporte une valeur énorme - il couvre une zone importante qui n'avait pas de couverture auparavant. Le deuxième routeur ajoute également une valeur substantielle, mais une partie de sa zone de couverture chevauche le premier routeur, de sorte que l'avantage marginal est inférieur au premier. Au fur et à mesure que vous continuez à ajouter des routeurs, chaque routeur supplémentaire couvre de moins en moins de nouvelle zone, car la plupart des espaces sont déjà couverts par les routeurs existants. Finalement, le 10e routeur pourrait fournir très peu de couverture supplémentaire, car le bâtiment est déjà bien couvert.

Cette intuition capture l'essence de la sous-modularité. Mathématiquement, une fonction d'ensemble $f: 2^V \rightarrow \mathbb{R}$ est sous-modulaire si pour tout $A \subseteq B \subseteq V$ et tout élément $v \notin B$ :

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

En termes simples : ajouter un élément à un ensemble plus petit donne au moins autant d'avantages que d'ajouter le même élément à un ensemble plus grand qui contient l'ensemble plus petit.

Appliquons maintenant ce concept à notre problème de génération de requêtes. On peut immédiatement se rendre compte que la sélection de requêtes présente des rendements décroissants naturels :

• La première requête que nous sélectionnons couvre un espace sémantique entièrement nouveau
• La deuxième requête doit couvrir différents aspects, mais un certain chevauchement est inévitable
• Au fur et à mesure que nous ajoutons des requêtes, chaque requête supplémentaire couvre de moins en moins de terrain nouveau

tagConception de Fonction Sous-modulaire Basée sur les Vecteurs Modèles

Soit $\mathbf{e}_i \in \mathbb{R}^d$ le vecteur modèle pour la requête $q_i$, obtenu en utilisant un modèle de vecteur modèle de phrase (par exemple, jina-embeddings-v3). Il existe deux approches principales pour concevoir notre fonction objectif :

tagApproche 1 : Emplacement des Installations (Basée sur la Couverture)

$$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)$$

Cette fonction mesure à quel point l'ensemble sélectionné $X$ "couvre" toutes les requêtes candidates, où :

• $\text{sim}(\mathbf{u}, \mathbf{v}) = \frac{\mathbf{u} \cdot \mathbf{v}}{|\mathbf{u}| |\mathbf{v}|}$ est la similarité cosinus
• $\alpha \cdot \text{sim}(\mathbf{e}_0, \mathbf{e}_j)$ assure la pertinence par rapport à la requête originale
• $\max_{q_i \in X} \text{sim}(\mathbf{e}_j, \mathbf{e}_i)$ mesure la couverture du candidat $j$ par l'ensemble sélectionné $X$

Un inconvénient est que cette fonction n'encourage qu'implicitement la diversité. Elle ne pénalise pas explicitement la similarité au sein de l'ensemble sélectionné $X$. La diversité émerge parce que la sélection de requêtes similaires offre des rendements de couverture décroissants.

tagApproche 2 : Couverture Explicite + Diversité

Pour un contrôle plus direct sur la diversité, nous pouvons combiner la couverture et un terme de diversité explicite :

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

où la composante de diversité peut être formulée comme :

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

Ce terme de diversité mesure la similarité totale entre les requêtes sélectionnées et les requêtes non sélectionnées - il est maximisé lorsque nous sélectionnons des requêtes qui sont différentes des candidats restants (une forme de fonction de coupe de graphe).

tagDifférence Entre les Deux Approches

Les deux formulations maintiennent la sous-modularité.

La fonction d'emplacement des installations est une fonction sous-modulaire bien connue. Elle présente une sous-modularité en raison de l'opération max : lorsque nous ajoutons une nouvelle requête $q$ à notre ensemble sélectionné, chaque requête candidate $j$ est couverte par la "meilleure" requête de notre ensemble (celle avec la plus grande similarité). L'ajout de $q$ à un ensemble plus petit $A$ est plus susceptible d'améliorer la couverture de divers candidats que l'ajout à un ensemble plus grand $B \supseteq A$ où de nombreux candidats sont déjà bien couverts.

Dans la fonction de diversité de coupe de graphe, le terme de diversité $\sum_{q_i \in X} \sum_{q_j \in V \setminus X} \text{sim}(\mathbf{e}_i, \mathbf{e}_j)$ est sous-modulaire car il mesure la "coupe" entre les ensembles sélectionnés et non sélectionnés. L'ajout d'une nouvelle requête à un ensemble sélectionné plus petit crée plus de nouvelles connexions aux requêtes non sélectionnées que l'ajout à un ensemble sélectionné plus grand.

L'approche d'emplacement des installations repose sur une diversité implicite grâce à la concurrence de la couverture, tandis que l'approche explicite mesure et optimise directement la diversité. Les deux sont donc valables, mais l'approche explicite vous donne un contrôle plus direct sur le compromis pertinence-diversité.

tagImplémentations

GitHub - jina-ai/submodular-optimization

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

GitHubjina-ai

Puisque notre fonction est sous-modulaire, nous pouvons utiliser l'algorithme glouton qui fournit une garantie d'approximation de $(1-1/e) \approx 0.63$ :

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

Voici le code pour optimiser l'emplacement des installations (basé sur la couverture) - celui avec une diversité implicite.

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)
Copier

Le paramètre d'équilibre $\alpha$ contrôle le compromis entre la pertinence et la diversité :

• $\alpha$ élevé (par exemple, 0,8) : donne la priorité à la pertinence par rapport à la requête originale, peut sacrifier la diversité
• $\alpha$ faible (par exemple, 0,2) : donne la priorité à la diversité parmi les requêtes sélectionnées, peut s'éloigner de l'intention originale
• $\alpha$ modéré (par exemple, 0,4 à 0,6) : approche équilibrée, fonctionne souvent bien dans la pratique

tagAlgorithme Glouton Paresseux

On peut remarquer dans le code ci-dessus :

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

Nous calculons le gain marginal pour tous les candidats restants à chaque itération. Nous pouvons faire mieux que cela.

L'algorithme glouton paresseux est une optimisation intelligente qui exploite la sous-modularité pour éviter les calculs inutiles. L'idée clé est la suivante : si l'élément A avait un gain marginal plus élevé que l'élément B à l'itération $t$, alors A aura toujours un gain marginal plus élevé que B à l'itération $t+1$ (en raison de la propriété de sous-modularité).

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]
Copier

L'algorithme glouton paresseux fonctionne comme ceci :

1. Maintenir une file d'attente prioritaire d'éléments triés par leurs gains marginaux.
2. Ne recalculer que le gain marginal de l'élément supérieur.
3. S'il est toujours le plus élevé après le recalcul, le sélectionner.
4. Sinon, le réinsérer dans la position correcte et vérifier l'élément supérieur suivant.

Cela peut fournir des accélérations significatives, car nous évitons de recalculer les gains marginaux pour les éléments qui ne seront clairement pas sélectionnés.

tagRésultats

Réalisons à nouveau l'expérience. Nous utilisons le même Prompt simple pour générer de 1 à 20 requêtes diverses et effectuons les mêmes mesures de similarité cosinus qu'auparavant. Pour l'optimisation sous-modulaire, nous sélectionnons des requêtes parmi les 20 candidats générés en utilisant différentes valeurs de k et mesurons la similarité comme auparavant. Les résultats montrent que les requêtes sélectionnées par l'optimisation sous-modulaire sont plus diverses et présentent une similarité intra-ensemble plus faible.

tagDernière question : pourquoi la formulation sous-modulaire est-elle importante ?

Vous vous demandez peut-être : pourquoi s'embêter à formuler cela comme un problème d'optimisation sous-modulaire ? Pourquoi ne pas simplement utiliser des heuristiques ou d'autres approches d'optimisation ?

En bref, la formulation sous-modulaire transforme une heuristique ad-hoc "sélectionner des requêtes diverses" en un problème d'optimisation rigoureux avec des garanties prouvables, des algorithmes efficaces et des objectifs mesurables.

tagEfficacité garantie

Une fois que nous prouvons que notre fonction objectif est sous-modulaire, nous obtenons de puissantes garanties théoriques et un algorithme efficace. L'algorithme glouton qui s'exécute en temps $O(nk)$ comparé à la vérification des combinaisons $\binom{n}{k}$ atteint une approximation de $(1-1/e) \approx 0.63$ de la solution optimale. Cela signifie que notre solution gloutonne est toujours au moins 63 % aussi bonne que la meilleure solution possible. Aucune heuristique ne peut promettre cela.

De plus, l'algorithme glouton paresseux est beaucoup plus rapide en pratique en raison de la structure mathématique des fonctions sous-modulaires. L'accélération provient des rendements décroissants : les éléments qui étaient de mauvais choix lors des itérations précédentes sont peu susceptibles de devenir de bons choix plus tard. Ainsi, au lieu de vérifier les $n$ candidats, l'algorithme glouton paresseux n'a généralement besoin de recalculer les gains que pour les quelques meilleurs candidats.

tagPas besoin d'heuristiques artisanales

Sans cadre fondé sur des principes, vous pourriez recourir à des règles ad hoc comme "s'assurer que les requêtes ont une similarité cosinus < 0,7" ou "équilibrer différentes catégories de mots-clés". Ces règles sont difficiles à affiner et ne se généralisent pas. L'optimisation sous-modulaire vous offre une approche fondée sur des principes et mathématiquement étayée. Vous pouvez affiner systématiquement les hyperparamètres à l'aide d'ensembles de validation et surveiller la qualité de la solution dans les systèmes de production. Lorsque le système produit de mauvais résultats, vous disposez de mesures claires pour déboguer ce qui n'a pas fonctionné.

Enfin, l'optimisation sous-modulaire est un domaine bien étudié avec des décennies de recherche, vous permettant de tirer parti d'algorithmes avancés au-delà du glouton (comme le glouton accéléré ou la recherche locale), des connaissances théoriques sur les moments où certaines formulations fonctionnent le mieux et des extensions pour gérer des contraintes supplémentaires telles que les limites budgétaires ou les exigences d'équité.

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