Ottimizzazione submodulare per la generazione di query diversificate in DeepResearch

Quando si implementa DeepResearch, ci sono almeno due punti in cui è necessario generare query diversificate. Innanzitutto, è necessario generare query di ricerca web basate sull'input dell'utente (inoltrare direttamente l'input dell'utente al motore di ricerca non è una buona idea). In secondo luogo, molti sistemi DeepResearch includono un "pianificatore di ricerca" che suddivide il problema originale in sottoproblemi, chiama contemporaneamente gli agenti per risolverli in modo indipendente e quindi unisce i loro risultati. Che si tratti di query o sottoproblemi, le nostre aspettative rimangono le stesse: devono essere rilevanti per l'input originale e sufficientemente diversificate da fornire prospettive uniche su di esso. Spesso, è necessario limitare il numero di query per evitare di sprecare denaro richiedendo inutilmente il motore di ricerca o utilizzando i token dell'agente.

Pur comprendendo l'importanza della generazione di query, la maggior parte delle implementazioni open source di DeepResearch non prende sul serio questa ottimizzazione. Si limitano a richiedere direttamente questi vincoli tramite dei Prompt. Alcuni potrebbero chiedere all'LLM un ulteriore passaggio per valutare e diversificare le query. Ecco un esempio di come la maggior parte delle implementazioni affronta sostanzialmente questo problema:

In questo articolo, voglio dimostrare un approccio più rigoroso alla risoluzione della generazione ottimale di query utilizzando i modelli vettoriali di frasi e l'ottimizzazione submodulare. Ai tempi del mio dottorato di ricerca, l'ottimizzazione submodulare era una delle mie tecniche preferite insieme a L-BFGS. Mostrerò come applicarla per generare un insieme di query diversificate sotto un vincolo di cardinalità, che può migliorare significativamente la qualità complessiva dei sistemi DeepResearch.

tagGenerazione di query tramite Prompt

Innanzitutto, vogliamo verificare se il Prompt è un approccio efficace per generare query diversificate. Vogliamo anche capire se un Prompt sofisticato è più efficace di un Prompt semplice. Eseguiamo un esperimento confrontando i due Prompt seguenti per scoprirlo:

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

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
Copy

Utilizziamo gemini-2.5-flash come LLM con la query originale "embeddings and rerankers" e testiamo sia il Prompt semplice che quello strutturato per generare iterativamente da una a 20 query. Quindi utilizziamo jina-embeddings-v3 con l'attività text-matching per misurare la similarità delle frasi tra la query originale e le query generate, nonché la similarità all'interno delle query generate stesse. Ecco le visualizzazioni.

Guardando i due grafici sul lato destro, si può vedere che sia il Prompt semplice che quello strutturato mostrano un'ampia varianza nei punteggi di similarità coseno, con molti che raggiungono una similarità di 0,7-0,8, suggerendo che alcune query generate sono quasi identiche. Inoltre, entrambi i metodi faticano a mantenere la diversità man mano che vengono generate più query. Invece di vedere una chiara tendenza al ribasso nella similarità con l'aumentare del conteggio delle query, osserviamo livelli di similarità relativamente stabili (e alti), il che indica che le query aggiuntive spesso duplicano le prospettive esistenti.

Una spiegazione è ciò che Wang et al. (2025) hanno scoperto, ovvero che gli LLM spesso riflettono le opinioni dei gruppi dominanti in modo sproporzionato, anche con la guida del Prompt, indicando una propensione verso prospettive comuni. Questo perché i dati di addestramento dell'LLM possono sovra-rappresentare determinati punti di vista, facendo sì che il modello generi variazioni che si allineano a queste prospettive prevalenti. Abe et al. (2025) hanno anche scoperto che l'espansione delle query basata su LLM favorisce le interpretazioni popolari trascurandone altre. Ad esempio, "Quali sono i vantaggi dell'IA?" potrebbe produrre vantaggi comuni come l'automazione, l'efficienza, l'eticità, ma tralasciare quelli meno ovvi come la scoperta di farmaci.

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

tagFormulazione del problema

Si potrebbe pensare che il nostro precedente esperimento non sia conclusivo e che dovremmo migliorare il Prompt e riprovare. Sebbene il Prompt possa certamente cambiare i risultati in una certa misura, ciò che è più importante è che abbiamo imparato qualcosa: aumentare semplicemente il numero di query generate ci rende più propensi a ottenere query diversificate. La cattiva notizia è che stiamo anche ottenendo un mucchio di query duplicate come prodotto secondario.

Ma poiché è economico generare un gran numero di query, che alla fine produce alcune buone query, perché non trattiamo questo come un problema di selezione di sottoinsiemi?

In matematica, ecco come possiamo formulare questo problema: dato un input originale $q_0$, un insieme di query candidate $V=\{q_1, q_2, \cdots, q_n\}$ generato da un LLM usando l'ingegneria del Prompt. Seleziona un sottoinsieme $X\subseteq V$ di $k$ query che massimizza la copertura minimizzando la ridondanza.

Sfortunatamente, trovare il sottoinsieme ottimale di $k$ query da $n$ candidati richiede il controllo di $\binom{n}{k}$ combinazioni - complessità esponenziale. Solo per 20 candidati e $k=5$, si tratta di 15.504 combinazioni.

tagFunzione Submodulare

Prima di provare a risolvere brutalmente il problema della selezione del sottoinsieme, vorrei introdurre ai lettori i termini submodularità e funzione submodulare. Potrebbero sembrare sconosciuti a molti, ma probabilmente avrete sentito parlare dell'idea dei "rendimenti decrescenti" - ebbene, la submodularità è la rappresentazione matematica di questo concetto.

Consideriamo di posizionare dei router Wi-Fi per fornire copertura internet in un grande edificio. Il primo router che installi offre un valore enorme: copre un'area significativa che in precedenza non aveva copertura. Anche il secondo router aggiunge un valore considerevole, ma parte della sua area di copertura si sovrappone a quella del primo router, quindi il beneficio marginale è inferiore al primo. Man mano che continui ad aggiungere router, ogni router aggiuntivo copre un'area nuova sempre minore perché la maggior parte degli spazi è già coperta dai router esistenti. Alla fine, il decimo router potrebbe fornire una copertura aggiuntiva molto limitata poiché l'edificio è già ben coperto.

Questa intuizione cattura l'essenza della submodularità. Matematicamente, una funzione di insieme $f: 2^V \rightarrow \mathbb{R}$ è submodulare se per tutti gli $A \subseteq B \subseteq V$ e qualsiasi elemento $v \notin B$:

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

In parole povere: aggiungere un elemento a un insieme più piccolo offre almeno lo stesso beneficio di aggiungere lo stesso elemento a un insieme più grande che contiene l'insieme più piccolo.

Ora applichiamo questo concetto al nostro problema di generazione di query. Si può immediatamente notare che la selezione delle query mostra un naturale rendimento decrescente:

• La prima query che selezioniamo copre uno spazio semantico completamente nuovo
• La seconda query dovrebbe coprire aspetti diversi, ma una certa sovrapposizione è inevitabile
• Man mano che aggiungiamo più query, ogni query aggiuntiva copre un terreno nuovo sempre minore

tagProgettazione di funzioni submodulari basate su Embeddings

Sia $\mathbf{e}_i \in \mathbb{R}^d$ il vettore di Embedding per la query $q_i$, ottenuto utilizzando un modello di Embedding di frasi (ad es. jina-embeddings-v3). Esistono due approcci principali per progettare la nostra funzione obiettivo:

tagApproccio 1: Posizione della struttura (basata sulla copertura)

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

Questa funzione misura quanto bene l'insieme selezionato $X$ "copre" tutte le query candidate, dove:

• $\text{sim}(\mathbf{u}, \mathbf{v}) = \frac{\mathbf{u} \cdot \mathbf{v}}{|\mathbf{u}| |\mathbf{v}|}$ è la somiglianza del coseno
• $\alpha \cdot \text{sim}(\mathbf{e}_0, \mathbf{e}_j)$ assicura la rilevanza alla query originale
• $\max_{q_i \in X} \text{sim}(\mathbf{e}_j, \mathbf{e}_i)$ misura la copertura del candidato $j$ da parte dell'insieme selezionato $X$

Un avvertimento è che questa funzione incoraggia solo implicitamente la diversità. Non penalizza esplicitamente la somiglianza all'interno dell'insieme selezionato $X$. La diversità emerge perché la selezione di query simili fornisce rendimenti di copertura decrescenti.

tagApproccio 2: Copertura esplicita + Diversità

Per un controllo più diretto sulla diversità, possiamo combinare la copertura e un termine di diversità esplicito:

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

dove la componente di diversità può essere formulata come:

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

Questo termine di diversità misura la somiglianza totale tra le query selezionate e le query non selezionate: viene massimizzato quando selezioniamo query diverse dai candidati rimanenti (una forma di funzione di taglio del grafico).

tagDifferenza tra i due approcci

Entrambe le formulazioni mantengono la submodularità.

La funzione di posizione della struttura è una funzione submodulare ben nota. Mostra submodularità a causa dell'operazione max: quando aggiungiamo una nuova query $q$ al nostro insieme selezionato, ogni query candidata $j$ viene coperta dalla query "migliore" nel nostro insieme (quella con la massima somiglianza). Aggiungere $q$ a un insieme più piccolo $A$ ha più probabilità di migliorare la copertura di vari candidati rispetto ad aggiungerlo a un insieme più grande $B \supseteq A$ dove molti candidati sono già ben coperti.

Nella funzione di diversità del taglio del grafico, il termine di diversità $\sum_{q_i \in X} \sum_{q_j \in V \setminus X} \text{sim}(\mathbf{e}_i, \mathbf{e}_j)$ è submodulare perché misura il "taglio" tra gli insiemi selezionati e non selezionati. Aggiungere una nuova query a un insieme selezionato più piccolo crea più nuove connessioni alle query non selezionate rispetto ad aggiungerla a un insieme selezionato più grande.

L'approccio di localizzazione della struttura si basa sulla diversità implicita attraverso la competizione di copertura, mentre l'approccio esplicito misura e ottimizza direttamente la diversità. Quindi entrambi sono validi, ma l'approccio esplicito offre un controllo più diretto sul compromesso rilevanza-diversità.

tagImplementazioni

GitHub - jina-ai/submodular-optimization

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

GitHubjina-ai

Poiché la nostra funzione è submodulare, possiamo usare l'algoritmo greedy che fornisce una garanzia di approssimazione di $(1-1/e) \approx 0.63$:

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

Ecco il codice per ottimizzare la posizione della struttura (basata sulla copertura) - quella con diversità implicita.

def greedy_query_selection(candidates, embeddings, original_embedding, k, alpha=0.3):
    """
    Algoritmo greedy per la selezione submodulare delle query
    
    Args:
        candidates: Elenco di stringhe di query candidate
        embeddings: Matrice di Embedding delle query (n x d)
        original_embedding: Embedding della query originale (d,)
        k: Numero di query da selezionare
        alpha: Parametro di peso della rilevanza
    """
    n = len(candidates)
    selected = []
    remaining = set(range(n))
    
    # Precalcola i punteggi di rilevanza
    relevance_scores = cosine_similarity(original_embedding, embeddings)
    
    for _ in range(k):
        best_gain = -float('inf')
        best_query = None
        
        for i in remaining:
            # Calcola il guadagno marginale dell'aggiunta della 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):
    """Calcola il guadagno marginale dell'aggiunta di new_idx all'insieme selezionato"""
    if not selected:
        # Prima query: il guadagno è la somma di tutti i punteggi di rilevanza
        return sum(max(alpha * relevance_scores[j], 
                      cosine_similarity(embeddings[new_idx], embeddings[j]))
                  for j in range(len(embeddings)))
    
    # Calcola la copertura attuale
    current_coverage = [
        max([alpha * relevance_scores[j]] + 
            [cosine_similarity(embeddings[s], embeddings[j]) for s in selected])
        for j in range(len(embeddings))
    ]
    
    # Calcola la nuova copertura con la query aggiuntiva
    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)
Copy

Il parametro di bilanciamento $\alpha$ controlla il compromesso tra rilevanza e diversità:

• $\alpha$ alto (ad es. 0,8): dà la priorità alla rilevanza alla query originale, può sacrificare la diversità
• $\alpha$ basso (ad es. 0,2): dà la priorità alla diversità tra le query selezionate, può allontanarsi dall'intento originale
• $\alpha$ moderato (ad es. 0,4-0,6): approccio bilanciato, spesso funziona bene nella pratica

tagAlgoritmo Greedy Pigro

Si può notare nel codice sopra:

for i in remaining:
    # Calcola il guadagno marginale dell'aggiunta della query i
    gain = compute_marginal_gain(i, selected, embeddings, 
                               relevance_scores, alpha)
Copy

Stiamo calcolando il guadagno marginale per tutti i candidati rimanenti a ogni iterazione. Possiamo fare di meglio.

L'algoritmo greedy pigro è un'ottimizzazione intelligente che sfrutta la submodularità per evitare calcoli non necessari. L'intuizione chiave è: se l'elemento A aveva un guadagno marginale maggiore dell'elemento B nell'iterazione $t$, allora A avrà ancora un guadagno marginale maggiore di B nell'iterazione $t+1$ (a causa della proprietà di submodularità).

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

Il lazy greedy funziona così:

1. Mantiene una coda di priorità degli elementi ordinati in base ai loro guadagni marginali
2. Ricalcola solo il guadagno marginale dell'elemento in cima
3. Se è ancora il più alto dopo il ricalcolo, lo seleziona
4. Altrimenti, lo reinserisce nella posizione corretta e controlla l'elemento successivo in cima

Questo può fornire accelerazioni significative perché evitiamo di ricalcolare i guadagni marginali per gli elementi che chiaramente non verranno selezionati.

tagRisultati

Eseguiamo di nuovo l'esperimento. Utilizziamo lo stesso semplice prompt per generare da 1 a 20 query diverse ed eseguiamo le stesse misurazioni di similarità del coseno di prima. Per l'ottimizzazione submodulare, selezioniamo le query dai 20 candidati generati utilizzando diversi valori di k e misuriamo la similarità come prima. I risultati mostrano che le query selezionate tramite l'ottimizzazione submodulare sono più diverse e mostrano una similarità in-set inferiore.

tagDomanda finale: perché la formulazione submodulare è importante

Potresti chiederti: perché prendersi la briga di formulare questo come un problema di ottimizzazione submodulare? Perché non usare semplicemente euristiche o altri approcci di ottimizzazione?

In breve, la formulazione submodulare trasforma un'euristica ad-hoc "seleziona query diverse" in un rigoroso problema di ottimizzazione con garanzie dimostrabili, algoritmi efficienti e obiettivi misurabili.

tagEfficienza garantita

Una volta dimostrato che la nostra funzione obiettivo è submodulare, otteniamo potenti garanzie teoriche e un algoritmo efficiente. L'algoritmo greedy che viene eseguito in tempo $O(nk)$ rispetto al controllo delle combinazioni $\binom{n}{k}$ raggiunge un'approssimazione $(1-1/e) \approx 0.63$ alla soluzione ottimale. Ciò significa che la nostra soluzione greedy è sempre almeno il 63% buona quanto la migliore soluzione possibile. Nessuna euristica può promettere questo.

Inoltre, l'algoritmo lazy greedy è notevolmente più veloce nella pratica grazie alla struttura matematica delle funzioni submodulari. L'accelerazione deriva dai rendimenti decrescenti: è improbabile che gli elementi che erano scelte sbagliate nelle iterazioni precedenti diventino buone scelte in seguito. Quindi, invece di controllare tutti gli $n$ candidati, il lazy greedy in genere deve solo ricalcolare i guadagni per i primi candidati.

tagNon c'è bisogno di euristiche artigianali

Senza un framework basato su principi, potresti ricorrere a regole ad-hoc come "assicurarsi che le query abbiano una similarità del coseno < 0.7" o "bilanciare diverse categorie di parole chiave". Queste regole sono difficili da ottimizzare e non si generalizzano. L'ottimizzazione submodulare ti offre un approccio basato su principi e matematicamente fondato. Puoi ottimizzare sistematicamente gli iperparametri utilizzando set di convalida e monitorare la qualità della soluzione nei sistemi di produzione. Quando il sistema produce risultati scadenti, hai metriche chiare per eseguire il debug di ciò che è andato storto.

Infine, l'ottimizzazione submodulare è un campo ben studiato con decenni di ricerca, che ti consente di sfruttare algoritmi avanzati oltre al greedy (come il greedy accelerato o la ricerca locale), approfondimenti teorici su quando determinate formulazioni funzionano meglio ed estensioni per gestire vincoli aggiuntivi come limiti di budget o requisiti di equità.

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