텍스트 선택, Passage Reranking 및 컨텍스트 엔지니어링을 위한 Submodular 최적화

GitHub - jina-ai/submodular-optimization: Submodular optimization for diverse query generation

Submodular optimization for diverse query generation - jina-ai/submodular-optimization

GitHubjina-ai

DeepResearch의 팬 아웃 쿼리에 대한 submodular 최적화에 대한 이전 기사 이후, 저는 submodularity와 정보 검색 및 에이전트 검색에서의 응용에 대한 더 깊은 논의를 요청하는 많은 피드백을 받았습니다. 오늘 저는 submodular 최적화의 두 가지 응용 분야인 텍스트 선택 및 구절 재정렬을 소개하겠습니다. 둘 다 모든 DeepResearch와 유사한 시스템이 해결해야 하는 핵심 과제인 최적의 하위 집합 선택을 다룹니다.

실제 문서는 의미론적 중복성을 포함합니다. 모든 문장이 LLM의 추론에 동일한 중요성을 갖는 것은 아닙니다. 긴 문서가 있고 토큰 제한 내에서 가장 대표적인 정보를 추출해야 한다고 상상해 보세요. 이것이 텍스트 선택입니다. 카디널리티 제약 조건 하에서 문서의 본질을 포착하는 콘텐츠를 선택하는 것입니다. 우리는 서로 직교하는 선택을 원합니다. 즉, 공유 정보를 최소화하면서 전체 커버리지를 최대화합니다. 이는 문서에서 문장을 선택하거나 문장에서 토큰을 선택하는 등 여러 수준에서 적용됩니다. 텍스트 선택을 컨텍스트 최적화 또는 압축으로 생각할 수도 있습니다. 우리는 추론에 필요한 의미론적 풍부도를 유지하면서 LLM 토큰 소비를 줄입니다.

구절 재정렬은 사용자 쿼리와의 의미론적 관련성에 따라 후보 구절을 정렬합니다. Jina AI에서는 이를 위해 특수 재정렬 도구(jina-reranker-m0, jina-reranker-v2-multilingual-base)를 구축했지만, 저희의 임베딩 모델도 이 문제를 해결할 수 있습니다. 그러나 여기에는 제한 사항이 있습니다. 저희를 포함한 대부분의 재정렬 도구는 pointwise 방식으로 작동합니다. 즉, 개별 (query, document) 쌍을 독립적으로 점수화합니다. 그들은 구절 간의 공유 정보를 고려하지 않습니다. 구절 1과 구절 7이 모두 높은 점수를 받았지만 대부분 동일한 정보를 포함하고 있다면 그 중 하나만 선택하는 것으로 충분하지 않을까요?

DeepResearch에서는 이것이 매우 중요합니다. 에이전트가 검색 도구를 호출하고 웹 스니펫을 수집할 때 다음 추론 단계를 위해 어떤 스니펫이 귀중한 컨텍스트 창 공간을 차지할 자격이 있는지 결정해야 합니다. 선택은 텍스트 선택과 동일한 "중복 최소화, 커버리지 최대화" 원칙을 따르지만, 원래 쿼리와의 관련성이 우선시되어야 하는 추가 목표가 있습니다.

많은 연구자들이 컨텍스트 엔지니어링의 중요성이 커지고 있음을 인식하고 있습니다. 컨텍스트 엔지니어링에서는 보다 효과적인 에이전트 워크플로를 구축하기 위해 컨텍스트 창을 구축, 최적화 및 "정확하게 압축"(Andrej Karpathy의 말)해야 합니다. 그러나 많은 사람들이 단순히 LLM 프롬프트를 사용하여 이러한 문제를 "부드럽게" 해결합니다. 즉, 보장도 없고, 이론적 근거도 없고, 효과도 의심스럽습니다. 우리는 훨씬 더 잘할 수 있습니다.

이 기사에서는 텍스트 선택과 구절 재정렬이 모두 엄격한 솔루션을 제공하는 submodular 최적화에 적합하다는 것을 보여드리겠습니다. submodular 함수에 익숙하지 않다면 "수익 체감"이라고 생각하세요. 우리는 빈 집합으로 시작하여 선택한 텍스트 또는 구절을 점진적으로 추가합니다. 각 추가는 가치를 제공하지만, 다양한 중복되지 않는 선택이 가장 가치 있다는 직관을 포착하는 한계 이익이 감소합니다. 공식적으로 함수 $f$는 임의의 집합 $A \subseteq B$ 및 요소 $i \notin B$에 대해 다음과 같은 경우 submodular입니다.

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

이 공식은 우리의 직관을 완벽하게 포착합니다. 우리는 선택한 요소가 전체 문서의 의미 공간을 집합적으로 포괄하기를 원하며, 더 많은 단위를 선택할수록 각 새 단위가 이전에 덮이지 않은 의미 공간을 덮을 가능성이 줄어듭니다.

tagSubmodular 최적화를 통한 텍스트 선택

Google Colab

부분 모듈성을 이해하는 데 필수적이고 구절 재정렬을 위한 예비 단계 역할을 하므로 텍스트 선택 문제를 해결하는 것부터 시작하겠습니다. 문제는 다음과 같습니다.

$n$개의 요소(토큰 또는 문장)가 있는 문서 $D$가 주어졌을 때, 커버리지 함수를 최대화하는 $|S| = k$인 부분 집합 $S \subseteq {1, 2, \ldots, n}$를 선택하려고 합니다.

$$f(S) = \sum_{i=1}^{n} \max_{j \in S} \text{sim}_{ij}$$

여기서 $\text{sim}_{ij}$는 요소 $i$와 $j$의 **벡터 모델** 간의 코사인 유사성을 나타냅니다. 커버리지 함수 $f$는 수확 체감의 속성을 만족하므로 부분 모듈성입니다. 최대 연산은 각 요소가 가장 가까운 선택 단위로 얼마나 잘 표현되는지 측정하여 중복 정보를 이중으로 계산하는 것을 방지합니다.

tag토큰/구절 수준 **벡터 모델** 가져오기

토큰 수준 선택을 위해 jina-embeddings-v4의 새로운 다중 벡터 **벡터 모델** 기능을 활용합니다. return_multivector=True를 설정하면 토큰당 하나의 **벡터 모델**이 반환되어 하위 단어 수준에서 선택할 수 있습니다.

구절 수준 선택의 경우 구두점이나 줄 바꿈으로 문서를 분할하고 각 구절을 독립적으로 포함합니다. 또는 후반부 청킹을 사용하여 API를 호출하여 상황별 구절 **벡터 모델**을 가져올 수도 있으며, 이는 일반적으로 다운스트림 작업에서 더 나은 성능을 제공합니다.

긴 컨텍스트 **벡터 모델**에서 후반부 청킹

컨텍스트 정보를 유지하면서 긴 문서를 청킹하는 것은 어렵습니다. 더 나은 검색 애플리케이션을 위해 긴 컨텍스트 **벡터 모델**을 활용하여 컨텍스트 청크 **벡터 모델**을 생성하는 "후반부 청킹"을 소개합니다.

Jina AIMichael Günther, Han Xiao

동종 요소 집합 내에서 의미론적 유사성을 측정하고 있으므로(구절 재정렬에서 보듯이 쿼리와 문서와 같은 이기종 요소를 비교하는 대신 동일한 기능적 역할을 수행함) jina-embeddings-v4를 text-matching LoRA 어댑터를 활성화하여 호출합니다.

Jina **벡터 모델** v4: 멀티모달 다국어 검색을 위한 범용 **벡터 모델**

Jina **벡터 모델** v4는 단일 벡터 및 다중 벡터 **벡터 모델** 출력을 모두 지원하는 멀티모달 및 다국어 검색을 위한 38억 개의 매개변수 범용 **벡터 모델**입니다.

Jina AIJina AI

tagLazy Greedy 알고리즘

이전 기사에서와 같이 최적화 문제를 해결하기 위해 Lazy Greedy 알고리즘을 사용합니다. 단조 부분 모듈 함수의 경우 이 알고리즘은 $(1 - 1/e) \approx 0.632$ 근사 보장을 달성합니다. 이는 증명 가능한 타이트 바운드입니다. Lazy Greedy 최적화는 수확 체감과 반복 전반에 걸쳐 한계 이득 간의 상대적 순서 보존이라는 부분 모듈 함수의 두 가지 기본 속성을 활용합니다. 알고리즘은 다음과 같이 작동합니다.

1. 초기화: 모든 요소에 대한 초기 한계 이득을 계산하고 우선순위 큐에 저장합니다.
2. Lazy 평가: 각 반복에서 캐시된 이득이 가장 높은 요소를 추출합니다.
3. 검증: 이 요소의 이득이 현재 반복에서 계산된 경우 즉시 선택합니다.
4. 재계산: 그렇지 않으면 현재 한계 이득을 재계산하고 큐에 다시 삽입합니다.

이 Lazy Greedy 알고리즘은 특히 한계 이득이 요소 간에 상당한 분산을 나타내는 경우 계산 오버헤드를 크게 줄입니다.

tag부분 모듈 최적화를 통한 구절 재정렬

Google Colab

구절 재정렬 작업은 새로운 목표를 추가하여 텍스트 선택을 확장합니다. 선택한 하위 집합은 주어진 쿼리와 관련이 있어야 합니다. 텍스트 선택은 문서 내의 순수한 다양성을 최적화하는 반면 구절 재정렬은 다양성과 쿼리 관련성의 균형을 맞춰야 합니다. 다음은 주요 표기법입니다.

• $S \subseteq \{1, 2, \ldots, P\}$는 후보 구절 집합 $P$에서 선택된 구절 인덱스의 하위 집합입니다. 이는 주어진 단계에서 DeepResearch 시스템의 모든 콘텐츠 또는 메모리입니다. $S$는 다음 추론 단계로 전달하려는 체리 피킹된 하위 집합을 나타냅니다. $Q$개의 쿼리와 $P$개의 후보 구절이 있습니다. 기존 검색에서는 $|Q|=1$이지만 쿼리가 자주 재구성되고 생성되는 DeepResearch에서는 여러 쿼리를 사용할 수 있습니다.
• $s_{ij}$는 구절 $i$와 $j$ 사이의 유사성입니다. 이는 텍스트 선택 작업에서와 같이 모든 구절에 대해 task="text-matching" LoRA를 활성화한 jina-embeddings-v4의 코사인 유사성을 사용합니다.
• $r_{qi}$는 쿼리 $q$와 구절 $i$ 사이의 관련성 점수입니다. 이는 쿼리의 경우 task="retrieval", prompt_name="query"를, 구절의 경우 task="retrieval", prompt_name="passage"를 사용하여 코사인 유사성으로 계산됩니다. 이를 통해 비대칭 검색 LoRA를 활성화하고 이기종 **벡터 모델**을 생성합니다.

이제 관련성과 다양성 간의 고유한 균형을 캡처하는 두 가지 다른 부분 모듈 함수를 사용하여 이를 공식화할 수 있습니다.

tag시설 위치 공식

각 구절은 각 쿼리에 대해 해당 선택된 구절이 얼마나 관련성이 있는지에 따라 가중치가 적용된 가장 유사한 선택된 구절로 "커버"됩니다. 이 공식은 쿼리 관련성이 높고 다른 많은 구절을 대표하는 구절을 선택합니다.

$$f_{FL}(S) = \sum_{q=1}^{Q} \sum_{i=1}^{P} \max_{j \in S} r_{qj} \cdot s_{ij}$$

쿼리 관련성($r_{qj}$)과 구절 유사성($s_{ij}$) 간의 곱셈적 상호 작용은 관련성 있는 답변과 다양한 대표자라는 두 가지 목적을 모두 제공하는 "허브" 구절을 만듭니다. 관련성이 높은 구절은 유사한 많은 구절을 커버할 수 있지만 관련성이 낮은 구절은 더 나은 대표자가 없는 경우에만 커버리지를 제공합니다.

tag포화 커버리지 공식

각 구절에 대해 쿼리 관련성 또는 가장 잘 선택된 대표자로 얼마나 잘 커버되는지의 최소값과 동일한 크레딧을 받습니다. 이를 통해 다른 많은 구절의 관련성을 "포화"시킬 수 있는 구절을 선택할 수 있습니다.

$$f_{SC}(S) = \sum_{q=1}^{Q} \sum_{i=1}^{P} \min(r_{qi}, \max_{j \in S} s_{ij})$$

최소 연산은 관련성 상한을 만듭니다. 구절에 대한 고유한 관련성보다 더 많은 커버리지 크레딧을 받을 수 없습니다. 이 공식은 보다 보수적이며 다양하지만 관련성이 없는 구절을 과도하게 선택하는 것을 방지합니다.

두 함수 모두 단조적이고 부분 모듈성이므로 동일한 Lazy Greedy 알고리즘을 $(1-1/e)$ 근사 보장으로 사용할 수 있습니다.

tag실험 결과

당사의 구현에서는 Jina Reader를 사용하여 이전 블로그 게시물에서 일반 텍스트를 가져오고 구절 재정렬을 사용하여 다양한 쿼리를 평가합니다. 독자들이 자신의 기사를 사용하여 Google Colab 노트북을 실험해 볼 것을 적극 권장합니다. 가장 익숙한 콘텐츠는 가장 의미 있는 통찰력을 제공할 것입니다.

당사의 실험에서는 각 문서에서 상위 10개의 구절을 선택합니다. 쿼리 관련성만, 시설 위치, 포화 커버리지의 세 가지 알고리즘 모두 단조성을 나타냅니다. 즉, 더 큰 $k$를 선택해도 처음 $k-1$ 요소의 순위가 변경되지 않습니다. 예를 들어 $k=9$, $k=10$ 또는 $k=11$을 비교할 때 상위 9개의 구절은 모든 값에서 동일하게 유지됩니다. 결과는 아래와 같습니다.

다음은 몇 가지 주요 관찰 사항입니다. 첫째, 부분 모듈 최적화 알고리즘은 쿼리 관련성 점수를 대략적으로 따르지만 전략적 재정렬을 도입합니다. 순위에서 구절이 "위아래로 이동"합니다. 이러한 동작은 순수한 관련성보다는 중복 최소화를 위해 최적화하기 때문에 예상과 일치합니다. 결과 순위는 강력한 품질을 보여줍니다.

일부 독자는 첫 번째, 두 번째 및 네 번째 예에서 부분 모듈 최적화 결과가 초기에 "포화"되어 정렬된 구절 0, 1, 2 등을 출력하는 것처럼 보일 수 있습니다. 이는 알고리즘 오류가 아니라 기존의 어떤 Reranker도 약속할 수 없는 부분 모듈 최적화의 가장 가치 있는 기능 중 하나를 보여줍니다.

이러한 포화 동작을 더 잘 이해하기 위해 문서의 최대 구절 수인 1부터 가능한 모든 집합 크기 $k$에 대한 부분 모듈 함수 값을 플롯합니다. 이를 통해 작동 중인 수확 체감의 속성을 알 수 있습니다.

위의 플롯은 선택 크기를 늘릴 때 Facility Location 및 Saturated Coverage 함수가 어떻게 동작하는지 보여줍니다. 둘 다 고전적인 부분 모듈 패턴을 나타냅니다.

• 빠른 초기 성장: 가장 가파른 이득은 처음 몇 번의 선택에서 발생합니다.
• 수확 체감: 추가 구절은 점진적으로 더 적은 한계 이익을 제공합니다.
• 포화 고원: 함수 값이 평탄해져 추가로 추가해도 이점이 최소화됨을 나타냅니다.

이러한 지점을 넘어서면 한계 이득은 무시할 수 있게 됩니다. 이는 이전 순위 실험에서 순차적 정렬(0, 1, 2, ...)을 보여준 이유를 설명합니다. 알고리즘은 추가 구절이 최소한의 가치를 제공한다고 올바르게 식별했습니다.

이러한 동작은 부분 모듈성의 수학적 속성을 직접적으로 나타냅니다. 우리가 관찰하는 한계 이득 감소는 알고리즘의 인위적인 산물이 아니라 커버리지 함수의 기본적인 특징입니다. 함수 값이 고원에 도달하면 다음 지점에 도달한 것입니다.

$$\Delta_i(S) = f(S \cup \{i\}) - f(S) \approx 0$$

남은 모든 구절 $i \notin S$에 대해.

tag결론

컨텍스트 엔지니어링은 AI 분야에서 유행어가 되었으며, LLM의 컨텍스트 창을 채우기 위해 가장 관련성이 높은 정보를 큐레이팅하는 에이전트 시스템 구축을 향한 패러다임 전환으로 자주 환영받고 있으며, 이는 종종 RAG를 통해 외부 데이터를 검색하는 것으로 시작됩니다.

텍스트 선택 및 구절 재정렬은 특히 지식 기반 선택, 검색 및 컨텍스트 압축 프로세스에서 컨텍스트 엔지니어링의 필수 구성 요소입니다. 그런 다음 구절 재정렬은 쿼리 관련성을 기반으로 선택된 텍스트를 재정렬하여 LLM이 가장 유용한 정보를 먼저 수신하도록 하여 과부하를 피하고 출력 품질을 향상시킵니다.

부분 모듈 최적화는 텍스트 선택 및 구절 재정렬에 대한 기존 접근 방식보다 세 가지 강력한 이점을 제공합니다.

tag계산 효율성을 갖춘 이론적 엄격성

휴리스틱 방법과 달리 부분 모듈 최적화는 증명 가능한 보증을 제공합니다. Lazy Greedy 알고리즘은 $O(nk \log n)$ 시간 내에 실행되며, 이는 완전 탐색에 대한 $\binom{n}{k}$ 조합에 비해 최적 솔루션에 대한 $(1-1/e) \approx 0.632$ 근사치를 달성합니다. 즉, 우리 솔루션은 수학적으로 이론상 가능한 최상의 선택보다 최소 63% 더 나은 성능을 보장합니다. Prompt 기반 휴리스틱은 이러한 수준의 성능 보증을 약속할 수 없습니다.

tag스마트 중지 기준

우리가 관찰한 포화 동작은 자동 중지 메커니즘을 제공합니다. 한계 이득이 0에 가까워지면 요소 추가를 중지해야 한다는 것을 알 수 있습니다. 이러한 기능은 집합 수준의 수확 체감을 이해하지 않고 각 항목에서 독립적으로 작동하는 기존의 pointwise 또는 listwise Reranker로는 달성할 수 없습니다. 함수 자체는 우리가 충분한 커버리지를 캡처했는지 알려줍니다.

tag다중 쿼리 확장

이 프레임워크는 쿼리가 자주 다시 작성되고 재구성되는 DeepResearch에서 흔히 발생하는 다중 쿼리 시나리오로 자연스럽게 확장됩니다. 동일한 이론적 토대와 Lazy Greedy 알고리즘이 원활하게 적용됩니다. Prompt 기반 접근 방식은 이러한 체계적인 확장성이 부족하여 각 새로운 시나리오에 대해 임시 솔루션이 필요한 경우가 많습니다.

이러한 이점은 엔지니어링 트릭이 아닌 부분 모듈성의 수학적 기초에서 비롯됩니다. 다른 사람들은 Prompt 튜닝에 의존하고 좋은 결과를 기대하지만, 신뢰할 수 있고 확장 가능한 컨텍스트 엔지니어링을 구축할 때 중요한 이점인 공식적인 보증이 있는 원칙적인 프레임워크를 제공하는 부분 모듈 최적화를 배워야 합니다.