Optimización submodular para la generación de consultas diversas en DeepResearch

Al implementar DeepResearch, hay al menos dos lugares donde necesitas generar diversas consultas. Primero, debes generar consultas de búsqueda web basadas en la entrada del usuario (lanzar directamente la entrada del usuario al motor de búsqueda no es una buena idea). En segundo lugar, muchos sistemas DeepResearch incluyen un "planificador de investigación" que descompone el problema original en subproblemas, llama concurrentemente a agentes para resolverlos de forma independiente y luego fusiona sus resultados. Ya sea que se trate de consultas o subproblemas, nuestras expectativas siguen siendo las mismas: deben ser relevantes para la entrada original y lo suficientemente diversas como para proporcionar perspectivas únicas sobre ella. A menudo, necesitamos limitar el número de consultas para evitar gastar dinero innecesariamente solicitando motores de búsqueda o utilizando tokens de agente.

Si bien comprenden la importancia de la generación de consultas, la mayoría de las implementaciones de código abierto de DeepResearch no se toman esta optimización en serio. Simplemente solicitan estas restricciones directamente. Algunos podrían pedirle al LLM un turno adicional para evaluar y diversificar las consultas. Aquí hay un ejemplo de cómo la mayoría de las implementaciones abordan esto básicamente:

En este artículo, quiero demostrar un enfoque más riguroso para resolver la generación óptima de consultas utilizando modelos de vectores de frases y optimización submodular. En mis días de doctorado, la optimización submodular era una de mis técnicas favoritas junto con L-BFGS. Mostraré cómo aplicarla para generar un conjunto de diversas consultas bajo una restricción de cardinalidad, lo que puede mejorar significativamente la calidad general de los sistemas DeepResearch.

tagGeneración de Consultas mediante el uso de Prompt

Primero, queremos comprobar si el uso de prompts es un enfoque eficaz para generar diversas consultas. También queremos entender si un prompt sofisticado es más eficaz que un prompt simple. Ejecutemos un experimento comparando los dos prompts siguientes para averiguarlo:

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

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
Copiar

Usamos gemini-2.5-flash como el LLM con la consulta original "embeddings and rerankers" y probamos tanto el prompt simple como el estructurado para generar iterativamente de una a 20 consultas. Luego, usamos jina-embeddings-v3 con la tarea text-matching para medir la similitud de frases entre la consulta original y las consultas generadas, así como la similitud dentro de las propias consultas generadas. Aquí están las visualizaciones.

Si observa los dos gráficos del lado derecho, se puede ver que tanto el prompt simple como el estructurado exhiben una gran varianza en las puntuaciones de similitud cosenales, y muchas alcanzan una similitud de 0.7-0.8, lo que sugiere que algunas consultas generadas son casi idénticas. Además, ambos métodos tienen dificultades para mantener la diversidad a medida que se generan más consultas. En lugar de ver una clara tendencia a la baja en la similitud al aumentar el recuento de consultas, observamos niveles de similitud relativamente estables (y altos), lo que indica que las consultas adicionales a menudo duplican las perspectivas existentes.

Una explicación es lo que Wang et al. (2025) encontraron que los LLM a menudo reflejan las opiniones de los grupos dominantes de manera desproporcionada, incluso con la dirección del prompt, lo que indica un sesgo hacia las perspectivas comunes. Esto se debe a que los datos de entrenamiento del LLM pueden sobrerrepresentar ciertos puntos de vista, lo que hace que el modelo genere variaciones que se alinean con estas perspectivas prevalentes. Abe et al. (2025) también encontraron que la expansión de consultas basada en LLM favorece las interpretaciones populares y pasa por alto otras. Por ejemplo, "¿Cuáles son los beneficios de la IA?" podría producir beneficios comunes como la automatización, la eficiencia, la ética, pero perderse otros menos obvios como el descubrimiento de fármacos.

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

tagFormulación del Problema

Uno podría pensar que nuestro experimento anterior no es concluyente y que deberíamos mejorar el prompt e intentarlo de nuevo. Si bien el uso de prompts ciertamente puede cambiar los resultados hasta cierto punto, lo que es más importante es que hemos aprendido algo: simplemente aumentar el número de consultas generadas hace que sea más probable que obtengamos diversas consultas. La mala noticia es que también estamos obteniendo un montón de consultas duplicadas como producto secundario.

Pero dado que es barato generar una gran cantidad de consultas, lo que eventualmente produce algunas buenas, ¿por qué no tratamos esto como un problema de selección de subconjuntos?

En matemáticas, así es como podemos formular este problema: dado una entrada original $q_0$, un conjunto de consultas candidatas $V=\{q_1, q_2, \cdots, q_n\}$ generadas por un LLM usando ingeniería de Prompt. Seleccionar un subconjunto $X\subseteq V$ de $k$ consultas que maximicen la cobertura y minimicen la redundancia.

Desafortunadamente, encontrar el subconjunto óptimo de $k$ consultas de $n$ candidatos requiere verificar $\binom{n}{k}$ combinaciones - complejidad exponencial. Para solo 20 candidatos y $k=5$, eso es 15,504 combinaciones.

tagFunción Submodular

Antes de intentar resolver brutalmente el problema de selección de subconjuntos, permítanme presentarles a los lectores el término submodularidad y función submodular. Puede que les suene desconocido a muchos, pero es posible que hayan oído hablar de la idea de "rendimientos decrecientes"; pues bien, la submodularidad es la representación matemática de eso.

Consideremos la colocación de routers Wi-Fi para proporcionar cobertura de Internet en un edificio grande. El primer router que instalas da un valor tremendo: cubre un área significativa que antes no tenía cobertura. El segundo router también añade un valor sustancial, pero parte de su área de cobertura se solapa con el primer router, por lo que el beneficio marginal es menor que el primero. A medida que sigues añadiendo routers, cada router adicional cubre cada vez menos área nueva porque la mayoría de los espacios ya están cubiertos por los routers existentes. Eventualmente, el décimo router podría proporcionar muy poca cobertura adicional, ya que el edificio ya está bien cubierto.

Esta intuición captura la esencia de la submodularidad. Matemáticamente, una función de conjunto $f: 2^V \rightarrow \mathbb{R}$ es submodular si para todo $A \subseteq B \subseteq V$ y cualquier elemento $v \notin B$:

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

En lenguaje sencillo: añadir un elemento a un conjunto más pequeño da al menos tanto beneficio como añadir el mismo elemento a un conjunto más grande que contiene el conjunto más pequeño.

Ahora apliquemos este concepto a nuestro problema de generación de consultas. Uno puede darse cuenta inmediatamente de que la selección de consultas exhibe rendimientos decrecientes naturales:

• La primera consulta que seleccionamos cubre un espacio semántico completamente nuevo
• La segunda consulta debería cubrir diferentes aspectos, pero es inevitable que haya alguna superposición
• A medida que añadimos más consultas, cada consulta adicional cubre cada vez menos terreno nuevo

tagDiseño de función submodular basada en Vectores Modelo

Sea $\mathbf{e}_i \in \mathbb{R}^d$ el vector de Vectores Modelo para la consulta $q_i$, obtenido usando un modelo de Vectores Modelo de frases (por ejemplo, jina-embeddings-v3). Hay dos enfoques principales para diseñar nuestra función objetivo:

tagEnfoque 1: Ubicación de instalaciones (basado en la cobertura)

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

Esta función mide lo bien que el conjunto seleccionado $X$ "cubre" todas las consultas candidatas, donde:

• $\text{sim}(\mathbf{u}, \mathbf{v}) = \frac{\mathbf{u} \cdot \mathbf{v}}{|\mathbf{u}| |\mathbf{v}|}$ es la similitud coseno
• $\alpha \cdot \text{sim}(\mathbf{e}_0, \mathbf{e}_j)$ asegura la relevancia para la consulta original
• $\max_{q_i \in X} \text{sim}(\mathbf{e}_j, \mathbf{e}_i)$ mide la cobertura del candidato $j$ por el conjunto seleccionado $X$

Una advertencia es que esta función solo fomenta la diversidad de forma implícita. No penaliza explícitamente la similitud dentro del conjunto seleccionado $X$. La diversidad surge porque la selección de consultas similares proporciona rendimientos de cobertura decrecientes.

tagEnfoque 2: Cobertura explícita + Diversidad

Para un control más directo sobre la diversidad, podemos combinar la cobertura y un término de diversidad explícito:

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

donde el componente de diversidad se puede formular como:

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

Este término de diversidad mide la similitud total entre las consultas seleccionadas y las consultas no seleccionadas; se maximiza cuando seleccionamos consultas que son diferentes de los candidatos restantes (una forma de función de corte de grafo).

tagDiferencia entre los dos enfoques

Ambas formulaciones mantienen la submodularidad.

La función de ubicación de instalaciones es una función submodular bien conocida. Exhibe submodularidad debido a la operación max: cuando añadimos una nueva consulta $q$ a nuestro conjunto seleccionado, cada consulta candidata $j$ es cubierta por la consulta "mejor" en nuestro conjunto (la que tiene la mayor similitud). Añadir $q$ a un conjunto más pequeño $A$ es más probable que mejore la cobertura de varios candidatos que añadirlo a un conjunto más grande $B \supseteq A$ donde muchos candidatos ya están bien cubiertos.

En la función de diversidad de corte de grafo, el término de diversidad $\sum_{q_i \in X} \sum_{q_j \in V \setminus X} \text{sim}(\mathbf{e}_i, \mathbf{e}_j)$ es submodular porque mide el "corte" entre los conjuntos seleccionados y no seleccionados. Añadir una nueva consulta a un conjunto seleccionado más pequeño crea más conexiones nuevas con consultas no seleccionadas que añadirla a un conjunto seleccionado más grande.

El enfoque de ubicación de instalaciones se basa en la diversidad implícita a través de la competencia de cobertura, mientras que el enfoque explícito mide y optimiza directamente la diversidad. Así que ambos son válidos, pero el enfoque explícito te da un control más directo sobre el equilibrio entre relevancia y diversidad.

tagImplementaciones

GitHub - jina-ai/submodular-optimization

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

GitHubjina-ai

Dado que nuestra función es submodular, podemos usar el algoritmo voraz que proporciona una garantía de aproximación de $(1-1/e) \approx 0.63$:

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

Aquí está el código para optimizar la ubicación de instalaciones (basado en la cobertura) - el que tiene diversidad implícita.

def greedy_query_selection(candidates, embeddings, original_embedding, k, alpha=0.3):
    """
    Algoritmo voraz para la selección de consultas submodulares
    
    Args:
        candidates: Lista de cadenas de consulta candidatas
        embeddings: Matriz de Vectores Modelo de consulta (n x d)
        original_embedding: Vectores Modelo de la consulta original (d,)
        k: Número de consultas para seleccionar
        alpha: Parámetro de ponderación de relevancia
    """
    n = len(candidates)
    selected = []
    remaining = set(range(n))
    
    # Precalcular las puntuaciones de relevancia
    relevance_scores = cosine_similarity(original_embedding, embeddings)
    
    for _ in range(k):
        best_gain = -float('inf')
        best_query = None
        
        for i in remaining:
            # Calcular la ganancia marginal de añadir la consulta 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):
    """Calcular la ganancia marginal de añadir new_idx al conjunto seleccionado"""
    if not selected:
        # Primera consulta: la ganancia es la suma de todas las puntuaciones de relevancia
        return sum(max(alpha * relevance_scores[j], 
                      cosine_similarity(embeddings[new_idx], embeddings[j]))
                  for j in range(len(embeddings)))
    
    # Calcular la cobertura actual
    current_coverage = [
        max([alpha * relevance_scores[j]] + 
            [cosine_similarity(embeddings[s], embeddings[j]) for s in selected])
        for j in range(len(embeddings))
    ]
    
    # Calcular la nueva cobertura con la consulta adicional
    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)
Copiar

El parámetro de equilibrio $\alpha$ controla el equilibrio entre relevancia y diversidad:

• $\alpha$ alto (por ejemplo, 0.8): Prioriza la relevancia para la consulta original, puede sacrificar la diversidad
• $\alpha$ bajo (por ejemplo, 0.2): Prioriza la diversidad entre las consultas seleccionadas, puede desviarse de la intención original
• $\alpha$ moderado (por ejemplo, 0.4-0.6): Enfoque equilibrado, a menudo funciona bien en la práctica

tagAlgoritmo Voraz Perezoso

Uno puede notar en el código anterior:

for i in remaining:
    # Calcular la ganancia marginal de añadir la consulta i
    gain = compute_marginal_gain(i, selected, embeddings, 
                               relevance_scores, alpha)
Copiar

Estamos calculando la ganancia marginal para todos los candidatos restantes en cada iteración. Podemos hacerlo mejor que esto.

El algoritmo voraz perezoso es una optimización inteligente que explota la submodularidad para evitar cálculos innecesarios. La idea clave es: si el elemento A tenía una ganancia marginal mayor que el elemento B en la iteración $t$, entonces A seguirá teniendo una ganancia marginal mayor que B en la iteración $t+1$ (debido a la propiedad de submodularidad).

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

El método greedy perezoso funciona así:

1. Mantener una cola de prioridad de elementos ordenados por sus ganancias marginales.
2. Solo volver a calcular la ganancia marginal del elemento superior.
3. Si sigue siendo la más alta después del recálculo, selecciónela.
4. De lo contrario, vuelva a insertarla en la posición correcta y compruebe el siguiente elemento superior.

Esto puede proporcionar aceleraciones significativas porque evitamos volver a calcular las ganancias marginales para los elementos que claramente no se seleccionarán.

tagResultados

Volvamos a ejecutar el experimento. Utilizamos el mismo *Prompt* simple para generar de una a 20 consultas diversas y realizamos las mismas mediciones de similitud coseno que antes. Para la optimización submodular, seleccionamos consultas de los 20 candidatos generados utilizando diferentes valores de k y medimos la similitud como antes. Los resultados muestran que las consultas seleccionadas mediante la optimización submodular son más diversas y muestran una menor similitud en el conjunto.

tagPregunta final: Por qué es importante la formulación submodular

Puede que se pregunte: ¿por qué tomarse la molestia de formular esto como un problema de optimización submodular? ¿Por qué no utilizar simplemente heurísticas u otros enfoques de optimización?

En resumen, la formulación submodular transforma una heurística *ad-hoc* de "seleccionar consultas diversas" en un problema de optimización riguroso con **garantías demostrables**, **algoritmos eficientes** y objetivos medibles.

tagEficiencia garantizada

Una vez que demostramos que nuestra función objetivo es submodular, obtenemos potentes garantías teóricas y un algoritmo eficiente. El algoritmo *greedy* que se ejecuta en tiempo $O(nk)$ en comparación con la comprobación de combinaciones $\binom{n}{k}$ logra una aproximación de $(1-1/e) \approx 0.63$ a la solución óptima. Esto significa que nuestra solución *greedy* es siempre al menos un 63% tan buena como la mejor solución posible. **Ninguna heurística puede prometer esto.**

Además, el algoritmo *greedy* perezoso es drásticamente más rápido en la práctica debido a la estructura matemática de las funciones submodulares. La aceleración proviene de **rendimientos decrecientes**: es poco probable que los elementos que fueron malas elecciones en iteraciones anteriores se conviertan en buenas elecciones más adelante. Por lo tanto, en lugar de comprobar los $n$ candidatos, el *greedy* perezoso normalmente solo necesita volver a calcular las ganancias para los pocos candidatos principales.

tagNo hay necesidad de heurísticas hechas a mano

Sin un marco de trabajo basado en principios, podría recurrir a reglas *ad-hoc* como "asegurarse de que las consultas tengan una similitud coseno < 0.7" o "equilibrar diferentes categorías de palabras clave". Estas reglas son difíciles de ajustar y no se generalizan. La optimización submodular le proporciona un enfoque basado en principios y con fundamentos matemáticos. Puede ajustar los hiperparámetros sistemáticamente utilizando conjuntos de validación y supervisar la calidad de la solución en los sistemas de producción. Cuando el sistema produce resultados deficientes, tiene métricas claras para depurar lo que salió mal.

Por último, la optimización submodular es un campo bien estudiado con décadas de investigación, lo que le permite aprovechar algoritmos avanzados más allá del *greedy* (como el *greedy* acelerado o la búsqueda local), conocimientos teóricos sobre cuándo ciertas formulaciones funcionan mejor y extensiones para manejar restricciones adicionales, como límites de presupuesto o requisitos de equidad.

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