DeepResearch에서 다양한 쿼리 생성을 위한 부분 모듈 최적화

DeepResearch를 구현할 때, 다양한 질의를 생성해야 하는 곳이 최소 두 군데 있습니다. 첫째, 사용자 입력을 기반으로 웹 검색 질의를 생성해야 합니다(사용자 입력을 검색 엔진에 직접 넣는 것은 좋은 생각이 아닙니다). 둘째, 많은 DeepResearch 시스템에는 원래 문제를 하위 문제로 분해하는 "연구 기획자"가 포함되어 있으며, 에이전트를 동시에 호출하여 독립적으로 해결한 다음 결과를 병합합니다. 질의를 다루든 하위 문제를 다루든, 우리의 기대는 동일하게 유지됩니다. 즉, 원래 입력과 관련성이 있어야 하고, 원래 입력에 대한 고유한 관점을 제공할 수 있을 만큼 충분히 다양해야 합니다. 종종 검색 엔진 요청이나 에이전트 词元 사용에 불필요하게 돈을 낭비하지 않도록 질의 수를 제한해야 합니다.

질의 생성의 중요성을 이해하면서도 대부분의 오픈 소스 DeepResearch 구현은 이러한 최적화를 심각하게 받아들이지 않습니다. 그들은 단순히 이러한 제약 조건을 직접 프롬프트합니다. 어떤 사람들은 질의를 평가하고 다양화하기 위해 추가 턴을 위해 LLM에게 요청할 수도 있습니다. 다음은 대부분의 구현이 기본적으로 이 문제에 접근하는 방법의 예입니다.

이 글에서는 문장 向量模型 및 submodular 최적화를 사용하여 최적의 질의 생성을 해결하는 보다 엄격한 접근 방식을 설명하고자 합니다. 박사 과정 시절에 submodular 최적화는 L-BFGS와 함께 제가 가장 좋아하는 기술 중 하나였습니다. 이를 적용하여 카디널리티 제약 조건 하에서 다양한 질의 집합을 생성하는 방법을 보여드리겠습니다. 이는 DeepResearch 시스템의 전체 품질을 크게 향상시킬 수 있습니다.

tag프롬프트를 통한 질의 생성

먼저 프롬프트가 다양한 질의를 생성하는 데 효과적인 접근 방식인지 확인하려고 합니다. 또한 정교한 프롬프트가 간단한 프롬프트보다 더 효과적인지 이해하려고 합니다. 아래의 두 프롬프트를 비교하는 실험을 실행하여 알아봅시다.

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

gemini-2.5-flash를 LLM으로 사용하고 원래 질의 "embeddings and rerankers"를 사용하여 간단한 프롬프트와 구조화된 프롬프트를 모두 테스트하여 1개에서 20개까지 반복적으로 생성합니다. 그런 다음 jina-embeddings-v3와 text-matching 작업을 사용하여 원래 질의와 생성된 질의 간의 문장 유사성, 그리고 생성된 질의 자체 내의 유사성을 측정합니다. 다음은 시각화 자료입니다.

오른쪽의 두 플롯을 보면 간단한 프롬프트와 구조화된 프롬프트 모두 코사인 유사도 점수에서 큰 분산을 보이며, 많은 점수가 0.7-0.8 유사도에 도달하여 일부 생성된 질의가 거의 동일함을 시사합니다. 게다가 두 방법 모두 더 많은 질의가 생성될수록 다양성을 유지하는 데 어려움을 겪습니다. 질의 수가 증가함에 따라 유사성이 명확하게 감소하는 추세를 보이는 대신, 비교적 안정적(및 높음)인 유사성 수준을 관찰하여 추가 질의가 종종 기존 관점을 복제함을 나타냅니다.

한 가지 설명은 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개의 조합이 필요합니다.

tagSubmodular 함수

하위 집합 선택 문제를 무작정 해결하기 전에 독자들에게 submodularity와 submodular 함수라는 용어를 소개하겠습니다. 많은 사람들에게 생소하게 들릴 수 있지만 "수확 체감"이라는 개념은 들어봤을 것입니다. submodularity는 이를 수학적으로 표현한 것입니다.

대형 건물에 인터넷 커버리지를 제공하기 위해 Wi-Fi 라우터를 배치한다고 가정해 보겠습니다. 처음 설치하는 라우터는 엄청난 가치를 제공합니다. 이전에는 커버리지가 없었던 중요한 영역을 커버합니다. 두 번째 라우터도 상당한 가치를 더하지만 커버리지 영역의 일부가 첫 번째 라우터와 겹치므로 한계 이익은 첫 번째 라우터보다 적습니다. 라우터를 계속 추가하면 대부분의 공간이 이미 기존 라우터로 커버되어 있기 때문에 추가 라우터마다 새로운 영역을 점점 더 적게 커버합니다. 결국 10번째 라우터는 건물이 이미 잘 커버되어 있기 때문에 추가적인 커버리지를 거의 제공하지 못할 수 있습니다.

이러한 직관은 submodularity의 본질을 포착합니다. 수학적으로 집합 함수 $f: 2^V \rightarrow \mathbb{R}$는 모든 $A \subseteq B \subseteq V$와 임의의 요소 $v \notin B$에 대해 submodular입니다.

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

평범한 영어로: 더 작은 집합에 요소를 추가하면 더 작은 집합을 포함하는 더 큰 집합에 동일한 요소를 추가하는 것보다 최소한 더 많은 이점을 제공합니다.

이제 이 개념을 쿼리 생성 문제에 적용해 보겠습니다. 쿼리 선택은 자연스러운 수확 체감을 나타냅니다.

• 처음 선택하는 쿼리는 완전히 새로운 의미 공간을 커버합니다.
• 두 번째 쿼리는 다른 측면을 커버해야 하지만 약간의 중복은 불가피합니다.
• 쿼리를 더 추가할수록 추가 쿼리마다 새로운 영역을 점점 더 적게 커버합니다.

tag向量模型 기반 Submodular 함수 설계

문장 向量模型 (예: jina-embeddings-v3)을 사용하여 얻은 쿼리 $q_i$에 대한 向量模型 벡터를 $\mathbf{e}_i \in \mathbb{R}^d$라고 하겠습니다. 목표 함수를 설계하는 데는 두 가지 주요 접근 방식이 있습니다.

tag접근 방식 1: Facility Location (커버리지 기반)

$$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$의 커버리지를 측정합니다.

한 가지 주의할 점은 이 함수는 암묵적으로 다양성을 장려할 뿐이라는 것입니다. 선택한 집합 $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두 가지 접근 방식의 차이점

두 공식 모두 submodularity를 유지합니다.

Facility location 함수는 잘 알려진 submodular 함수입니다. max 연산으로 인해 submodularity를 나타냅니다. 선택한 집합에 새 쿼리 $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)$는 선택한 집합과 선택하지 않은 집합 간의 "컷"을 측정하기 때문에 submodular입니다. 더 작은 선택 집합에 새 쿼리를 추가하면 더 큰 선택 집합에 추가하는 것보다 선택하지 않은 쿼리에 대한 더 많은 새 연결이 생성됩니다.

Facility location 접근 방식은 커버리지 경쟁을 통해 암묵적인 다양성에 의존하는 반면, 명시적 접근 방식은 다양성을 직접 측정하고 최적화합니다. 따라서 둘 다 유효하지만 명시적 접근 방식은 관련성-다양성 절충을 보다 직접적으로 제어할 수 있습니다.

tag구현

GitHub - jina-ai/submodular-optimization

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

GitHubjina-ai

함수가 submodular이므로 $(1-1/e) \approx 0.63$ 근사 보장을 제공하는 greedy 알고리즘을 사용할 수 있습니다.

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

다음은 암묵적인 다양성이 있는 Facility Location (커버리지 기반)을 최적화하는 코드입니다.

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

균형 매개변수 $\alpha$는 관련성과 다양성 간의 절충을 제어합니다.

• 높은 $\alpha$ (예: 0.8): 원래 쿼리와의 관련성을 우선시하고 다양성을 희생할 수 있습니다.
• 낮은 $\alpha$ (예: 0.2): 선택한 쿼리 간의 다양성을 우선시하고 원래 의도에서 벗어날 수 있습니다.
• 중간 $\alpha$ (예: 0.4-0.6): 균형 잡힌 접근 방식은 실제로 종종 잘 작동합니다.

tagLazy Greedy 알고리즘

위의 코드에서 다음을 알 수 있습니다.

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

각 반복에서 모든 나머지 후보에 대한 한계 이익을 계산합니다. 이보다 더 잘할 수 있습니다.

lazy greedy 알고리즘은 불필요한 계산을 피하기 위해 submodularity를 활용하는 영리한 최적화입니다. 핵심 아이디어는 요소 A가 반복 $t$에서 요소 B보다 한계 이익이 더 높으면 A는 submodularity 속성으로 인해 반복 $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]
Copy

Lazy greedy는 다음과 같이 작동합니다.

1. 한계 이득으로 정렬된 요소의 우선순위 큐를 유지합니다.
2. 최상위 요소의 한계 이득만 다시 계산합니다.
3. 다시 계산한 후에도 여전히 가장 높으면 선택합니다.
4. 그렇지 않으면 올바른 위치에 다시 삽입하고 다음 상위 요소를 확인합니다.

이렇게 하면 선택되지 않을 요소에 대한 한계 이득을 다시 계산하지 않아도 되므로 상당한 속도 향상을 얻을 수 있습니다.

tag결과

실험을 다시 실행해 보겠습니다. 이전과 동일한 간단한 프롬프트로 1~20개의 다양한 쿼리를 생성하고 이전과 동일한 코사인 유사도 측정을 수행합니다. 서브모듈 최적화의 경우 k 값을 다르게 하여 생성된 20개의 후보에서 쿼리를 선택하고 이전과 같이 유사도를 측정합니다. 결과는 서브모듈 최적화를 통해 선택된 쿼리가 더 다양하고 집합 내 유사도가 더 낮은 것으로 나타났습니다.

tag마지막 질문: 서브모듈 공식화가 중요한 이유는 무엇입니까?

다음과 같은 의문이 들 수 있습니다. 왜 서브모듈 최적화 문제로 공식화하는 번거로움을 겪어야 할까요? 휴리스틱이나 다른 최적화 접근 방식을 사용하면 안 될까요?

간단히 말해서 서브모듈 공식화는 임시 "다양한 쿼리 선택" 휴리스틱을 증명 가능한 보장, 효율적인 알고리즘 및 측정 가능한 목표를 가진 엄격한 최적화 문제로 변환합니다.

tag보장된 효율성

목표 함수가 서브모듈임을 증명하면 강력한 이론적 보장과 효율적인 알고리즘을 얻을 수 있습니다. $\binom{n}{k}$ 조합을 확인하는 데 비해 $O(nk)$ 시간에 실행되는 그리디 알고리즘은 최적 솔루션에 대한 $(1-1/e) \approx 0.63$ 근사치를 달성합니다. 즉, 그리디 솔루션은 항상 가능한 최상의 솔루션보다 최소 63% 이상 좋습니다. 어떤 휴리스틱도 이를 약속할 수 없습니다.

또한 lazy greedy 알고리즘은 서브모듈 함수의 수학적 구조로 인해 실제로 훨씬 빠릅니다. 속도 향상은 수익 체감에서 비롯됩니다. 즉, 이전 반복에서 잘못된 선택이었던 요소는 나중에 좋은 선택이 될 가능성이 낮습니다. 따라서 모든 $n$개의 후보를 확인하는 대신 lazy greedy는 일반적으로 상위 몇 개 후보에 대한 이득만 다시 계산하면 됩니다.

tag수작업 휴리스틱이 필요 없음

원칙적인 프레임워크가 없으면 "쿼리의 코사인 유사도가 0.7 미만인지 확인" 또는 "다른 키워드 범주 간의 균형 조정"과 같은 임시 규칙에 의존할 수 있습니다. 이러한 규칙은 조정하기 어렵고 일반화되지 않습니다. 서브모듈 최적화는 원칙적이고 수학적으로 근거한 접근 방식을 제공합니다. 유효성 검사 집합을 사용하여 하이퍼파라미터를 체계적으로 조정하고 프로덕션 시스템에서 솔루션 품질을 모니터링할 수 있습니다. 시스템에서 잘못된 결과가 생성되면 무엇이 잘못되었는지 디버깅할 수 있는 명확한 메트릭이 있습니다.

마지막으로 서브모듈 최적화는 수십 년 동안 연구된 잘 연구된 분야이므로 그리디(가속화된 그리디 또는 로컬 검색과 같은)를 넘어선 고급 알고리즘, 특정 공식이 가장 잘 작동하는 시기에 대한 이론적 통찰력, 예산 제한 또는 공정성 요구 사항과 같은 추가 제약 조건을 처리하기 위한 확장 기능을 활용할 수 있습니다.

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