Submodulare Optimierung für Textauswahl, Passage-Reranking & Kontext-Engineering

GitHub - jina-ai/submodular-optimization: Submodulare Optimierung für diverse Anfragegenerierung

Submodulare Optimierung für diverse Anfragegenerierung - jina-ai/submodular-optimization

GitHubjina-ai

Nach meinem vorherigen Artikel über submodulare Optimierung für Fan-Out-Abfragen in DeepResearch erhielt ich großartiges Feedback mit der Bitte um ein tieferes Eintauchen in die Submodularität und ihre Anwendungen in der Informationsbeschaffung und Agentensuchen. Heute stelle ich zwei weitere Anwendungen der submodularen Optimierung vor: Textauswahl und Passagen-Reranking. Beide befassen sich mit derselben zentralen Herausforderung – der optimalen Teilmengenauswahl – die jedes DeepResearch-ähnliche System lösen muss.

Dokumente aus der realen Welt enthalten semantische Redundanz – nicht jeder Satz ist für die Argumentation eines LLM gleich wichtig. Stellen Sie sich vor, Sie haben ein langes Dokument und müssen die repräsentativsten Informationen extrahieren und gleichzeitig ein Token-Limit einhalten. Dies ist die Textauswahl: die Auswahl von Inhalten, die die Essenz des Dokuments unter Kardinalitätsbeschränkungen erfassen. Wir wollen Auswahlen, die orthogonal zueinander sind – die gemeinsame Information minimieren und gleichzeitig die Gesamtdeckung maximieren. Dies gilt auf mehreren Ebenen: Auswahl von Sätzen aus Dokumenten oder Tokens aus Sätzen. Man kann sich die Textauswahl auch als Kontextoptimierung oder -komprimierung vorstellen. Wir reduzieren den LLM-Token-Verbrauch und erhalten gleichzeitig die semantische Fülle, die für die Argumentation erforderlich ist.

Das Passagen-Reranking sortiert Kandidatenpassagen nach ihrer semantischen Relevanz für eine Benutzerabfrage. Bei Jina AI haben wir spezielle Reranker dafür entwickelt (jina-reranker-m0, jina-reranker-v2-multilingual-base), obwohl unsere Vektor modelle das Problem auch lösen können. Aber hier ist die Einschränkung: Die meisten Reranker – auch unsere – arbeiten punktweise. Sie bewerten einzelne (query, document)-Paare unabhängig voneinander. Sie berücksichtigen nicht die gemeinsamen Informationen zwischen Passagen: Wenn Passage 1 und Passage 7 beide hoch punkten, aber größtenteils identische Informationen enthalten, wäre es dann nicht ausreichend, nur eine von beiden auszuwählen?

In DeepResearch wird dies entscheidend. Wenn Agenten Suchwerkzeuge aufrufen und Web-Snippets sammeln, müssen wir bestimmen, welche Snippets den wertvollen Kontextfensterplatz für den nächsten Argumentationsschritt verdienen. Die Auswahl folgt dem gleichen Prinzip "Überlappung minimieren, Abdeckung maximieren" wie die Textauswahl, jedoch mit einem zusätzlichen Ziel – die Relevanz für die ursprüngliche Abfrage muss Vorrang haben.

Viele Forscher erkennen die wachsende Bedeutung des Kontext-Engineerings, wo wir die Kontextfenster aufbauen, optimieren und "genau richtig packen" (von Andrej Karpathy) müssen, um effektivere agentische Workflows zu erstellen. Viele verwenden jedoch einfach LLM- Prompts, um diese Probleme "weich" zu lösen – keine Garantien, keine theoretische Grundlage, fragwürdige Wirksamkeit. Das können wir viel besser machen.

In diesem Artikel werde ich zeigen, dass sowohl die Textauswahl als auch das Passagen-Reranking der submodularen Optimierung unterliegen, die rigorose Lösungen bietet. Wenn Sie mit submodularen Funktionen nicht vertraut sind, denken Sie an "abnehmende Erträge". Wir beginnen mit einer leeren Menge und fügen schrittweise ausgewählten Text oder Passagen hinzu. Jede Ergänzung bietet einen Wert, aber der Grenznutzen nimmt ab – was die Intuition erfasst, dass vielfältige, nicht redundante Auswahlen am wertvollsten sind. Formal ist eine Funktion $f$ submodular, wenn für beliebige Mengen $A \subseteq B$ und Element $i \notin B$ gilt:

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

Diese Formulierung erfasst unsere Intuition perfekt: Wir möchten, dass ausgewählte Elemente gemeinsam den semantischen Raum des gesamten Dokuments abdecken. Je mehr Einheiten wir auswählen, desto unwahrscheinlicher ist es, dass jede neue Einheit zuvor nicht abgedeckten semantischen Raum abdeckt.

tagTextauswahl über submodulare Optimierung

Google Colab

Beginnen wir mit der Lösung des Textauswahlproblems, da es für das Verständnis der Submodularität unerlässlich ist und als vorbereitender Schritt für das Passage-Reranking dient. Das Problem ist wie folgt:

Gegeben sei ein Dokument $D$ mit $n$ Elementen (Tokens oder Sätze). Wir möchten eine Teilmenge $S \subseteq {1, 2, \ldots, n}$ mit $|S| = k$ auswählen, die die Coverage-Funktion maximiert:

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

wobei $\text{sim}_{ij}$ die Kosinusähnlichkeit zwischen den VektorModellen der Elemente $i$ und $j$ darstellt. Beachten Sie, dass die Coverage-Funktion $f$ submodular ist, da sie das Gesetz des abnehmenden Grenzertrags erfüllt. Die Max-Operation stellt sicher, dass wir messen, wie gut jedes Element durch die nächstgelegene ausgewählte Einheit repräsentiert wird, wodurch eine doppelte Zählung redundanter Informationen vermieden wird.

tagToken-/Passage-Level VektorModelle abrufen

Für die Auswahl auf Token-Ebene nutzen wir die neue Multi-Vektor-Embedding-Funktion von jina-embeddings-v4. Wenn return_multivector=True eingestellt ist, wird ein Embedding pro Token zurückgegeben, was unsere Auswahl auf Subword-Ebene ermöglicht.

Für die Auswahl auf Passage-Ebene teilen wir Dokumente einfach durch Interpunktion oder neue Zeilen und betten jede Passage unabhängig ein. Alternativ kann man unsere API auch mit Late Chunking aufrufen, um kontextbezogene Passage-VektorModelle zu erhalten, was im Allgemeinen zu einer besseren Leistung bei nachgeschalteten Aufgaben führt.

Late Chunking in Long-Context Embedding Models

Das Chunking langer Dokumente unter Beibehaltung von Kontextinformationen ist eine Herausforderung. Wir stellen das „Late Chunking“ vor, das Long-Context Embedding Models nutzt, um kontextbezogene Chunk-VektorModelle für bessere Retrieval-Anwendungen zu generieren.

Jina AIMichael Günther, Han Xiao

Es ist erwähnenswert, dass wir, da wir die semantische Ähnlichkeit innerhalb einer homogenen Menge von Elementen messen – die alle die gleiche funktionale Rolle erfüllen, anstatt heterogene Elemente wie Abfragen mit Dokumenten zu vergleichen (wie wir beim Passage-Reranking sehen werden) – jina-embeddings-v4 mit aktiviertem text-matching LoRA-Adapter aufrufen.

Jina Embeddings v4: Universal Embeddings for Multimodal Multilingual Retrieval

Jina Embeddings v4 ist ein universelles Embedding Model mit 3,8 Milliarden Parametern für multimodalen und multilingualen Retrieval, das sowohl Single-Vektor- als auch Multi-Vektor-Embedding-Ausgaben unterstützt.

Jina AIJina AI

tagLazy-Greedy-Algorithmus

Wie im vorherigen Artikel verwenden wir den Lazy-Greedy-Algorithmus, um das Optimierungsproblem zu lösen. Für monotone submodulare Funktionen erreicht dieser Algorithmus eine $(1 - 1/e) \approx 0.632$ Approximationsgarantie – eine Grenze, die nachweislich eng ist. Die Lazy-Greedy-Optimierung nutzt zwei grundlegende Eigenschaften submodularer Funktionen: abnehmende Grenzerträge und die Beibehaltung der relativen Reihenfolge zwischen marginalen Gewinnen über Iterationen hinweg. Der Algorithmus funktioniert wie folgt:

1. Initialisierung: Berechnen Sie die anfänglichen marginalen Gewinne für alle Elemente und speichern Sie sie in einer Prioritätswarteschlange.
2. Lazy Evaluation: Extrahieren Sie in jeder Iteration das Element mit dem höchsten zwischengespeicherten Gewinn.
3. Validierung: Wenn der Gewinn dieses Elements in der aktuellen Iteration berechnet wurde, wählen Sie ihn sofort aus.
4. Neuberechnung: Andernfalls berechnen Sie den aktuellen marginalen Gewinn neu und fügen Sie ihn wieder in die Warteschlange ein.

Dieser Lazy-Greedy-Algorithmus reduziert den Rechenaufwand erheblich, insbesondere wenn marginale Gewinne eine erhebliche Varianz über Elemente hinweg aufweisen.

tagPassage-Reranking über submodulare Optimierung

Google Colab

Die Aufgabe des Passage-Reranking erweitert die Textauswahl um ein neues Ziel: Die ausgewählte Teilmenge muss für die angegebene Abfrage relevant sein. Während die Textauswahl auf reine Vielfalt innerhalb eines Dokuments optimiert, muss das Passage-Reranking die Vielfalt gegen die Abfragerelevanz abwägen. Hier sind die wichtigsten Notationen:

• $S \subseteq \{1, 2, \ldots, P\}$ ist die ausgewählte Teilmenge von Passageindizes aus der Kandidatenmenge von $P$ Passagen – alle Inhalte oder Erinnerungen im DeepResearch-System in einem bestimmten Schritt. $S$ stellt die handverlesene Teilmenge dar, die wir zum nächsten Denkschritt weiterleiten möchten. Wir haben $Q$ Abfragen und $P$ Kandidatenpassagen. In der traditionellen Suche gilt $|Q|=1$, aber in DeepResearch, wo Abfragen häufig umformuliert und generiert werden, können wir mehrere Abfragen zur Hand haben.
• $s_{ij}$ ist die Ähnlichkeit zwischen Passagen $i$ und $j$. Dies verwendet die Kosinusähnlichkeit von jina-embeddings-v4 mit aktiviertem task="text-matching" LoRA für alle Passagen, wie wir es in der Textauswahlaufgabe getan haben.
• $r_{qi}$ ist der Relevanzwert zwischen Abfrage $q$ und Passage $i$. Dies wird als Kosinusähnlichkeit unter Verwendung von jina-embeddings-v4 mit task="retrieval", prompt_name="query" für Abfragen und task="retrieval", prompt_name="passage" für Passagen berechnet, wodurch das asymmetrische Retrieval LoRA aktiviert und heterogene VektorModelle erzeugt werden.

Wir können dies nun mithilfe von zwei verschiedenen submodularen Funktionen formulieren, die jeweils einen deutlichen Kompromiss zwischen Relevanz und Vielfalt erfassen.

tagFacility-Location-Formulierung

Jede Passage wird von ihrer ähnlichsten ausgewählten Passage "abgedeckt", gewichtet danach, wie relevant diese ausgewählte Passage für jede Abfrage ist. Diese Formulierung wählt Passagen aus, die sowohl für die Abfrage relevant ALS AUCH repräsentativ für viele andere Passagen sind.

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

Die multiplikative Interaktion zwischen Abfragerelevanz ($r_{qj}$) und Passageähnlichkeit ($s_{ij}$) erzeugt "Hubs" – Passagen, die als relevante Antworten und als vielfältige Repräsentanten dienen. Eine hochrelevante Passage kann viele ähnliche Passagen abdecken, während eine weniger relevante Passage nur dann eine Abdeckung bietet, wenn kein besserer Repräsentant existiert.

tagFormulierung der gesättigten Abdeckung

Für jede Passage erhalten Sie eine Gutschrift in Höhe des Minimums ihrer Abfragerelevanz oder wie gut sie von Ihrem besten ausgewählten Repräsentanten abgedeckt wird. Dies fördert die Auswahl von Passagen, die die Relevanz vieler anderer Passagen "sättigen" können.

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

Die Min-Operation erzeugt eine Relevanzobergrenze – Sie können nicht mehr Abdeckungsgutschrift erhalten als die inhärente Relevanz einer Passage für die Abfrage. Diese Formulierung ist konservativer und verhindert die Überauswahl von vielfältigen, aber irrelevanten Passagen.

Beide Funktionen sind monoton und submodular, was den gleichen Lazy-Greedy-Algorithmus mit $(1-1/e)$-Approximationsgarantien ermöglicht.

tagExperimentelle Ergebnisse

In unserer Implementierung verwenden wir Jina Reader, um den Klartext aus unseren vorherigen Blogbeiträgen abzurufen und verschiedene Abfragen mithilfe des Passage-Reranking auszuwerten. Ich empfehle den Lesern dringend, mit unserem Google Colab Notebook mit ihren eigenen Artikeln zu experimentieren – Inhalte, mit denen sie am besten vertraut sind, liefern die aussagekräftigsten Erkenntnisse.

In unseren Experimenten wählen wir die Top-10-Passagen aus jedem Dokument aus. Beachten Sie, dass alle drei Algorithmen – nur Abfragerelevanz, Facility Location und gesättigte Abdeckung – die Monotonie aufweisen: Die Auswahl eines größeren $k$ ändert die Rangfolge der ersten $k-1$ Elemente nicht. Wenn wir beispielsweise $k=9$, $k=10$ oder $k=11$ vergleichen, bleiben die Top-9-Passagen über alle Werte hinweg identisch. Die Ergebnisse sind unten dargestellt.

Hier sind einige wichtige Beobachtungen. Erstens folgen die submodularen Optimierungsalgorithmen lose den Query-Relevanz-Scores, führen aber strategische Neuanordnungen ein – Passagen "verschieben sich in den Rankings nach oben und unten". Dieses Verhalten entspricht unseren Erwartungen, da diese Algorithmen eher die Redundanzminimierung als die reine Relevanz optimieren. Die resultierenden Rankings zeigen eine hohe Qualität.

Einige Leser werden vielleicht feststellen, dass in den ersten, zweiten und vierten Beispielen die Ergebnisse der submodularen Optimierung frühzeitig zu "sättigen" scheinen und einfach geordnete Passagen 0, 1, 2 usw. ausgeben. Dies ist kein algorithmisches Versagen – es zeigt eines der wertvollsten Merkmale der submodularen Optimierung, das kein bestehender Reranker versprechen kann.

Um dieses Sättigungsverhalten besser zu verstehen, stellen wir die submodularen Funktionswerte für alle möglichen Setgrößen $k$ von 1 bis zur maximalen Anzahl von Passagen im Dokument dar. Dies zeigt das Gesetz des abnehmenden Grenznutzens in Aktion.

Die obigen Diagramme zeigen, wie sich Facility Location und Saturated Coverage Funktionen verhalten, wenn wir die Auswahlgröße erhöhen. Beide weisen das klassische submodulare Muster auf:

• Schnelles anfängliches Wachstum: Die steilsten Zuwächse treten bei den ersten wenigen Auswahlen auf
• Abnehmende Erträge: Jede zusätzliche Passage bietet einen progressiv geringeren Grenznutzen
• Sättigungsplateau: Die Funktionswerte flachen ab, was auf einen minimalen Nutzen durch weitere Ergänzungen hinweist

Jenseits dieser Punkte werden die Grenzerträge vernachlässigbar. Dies erklärt, warum unsere früheren Ranking-Experimente eine sequentielle Anordnung (0, 1, 2, ...) zeigten – die Algorithmen erkannten korrekt, dass zusätzliche Passagen nur einen minimalen Wert beitragen.

Dieses Verhalten manifestiert direkt die mathematische Eigenschaft der Submodularität. Die abnehmenden Grenzerträge, die wir beobachten, sind keine algorithmischen Artefakte, sondern grundlegende Eigenschaften der Coverage-Funktionen. Wenn der Funktionswert ein Plateau erreicht hat, haben wir den Punkt erreicht, an dem:

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

für alle verbleibenden Passagen $i \notin S$ gilt.

tagSchlussfolgerungen

Context Engineering hat sich zu einem Schlagwort in der KI entwickelt. Es wird häufig als Paradigmenwechsel hin zum Aufbau von agentischen Systemen gepriesen, die die relevantesten Informationen kuratieren, um das Kontextfenster eines LLM zu füllen. Dies beginnt oft mit dem Abrufen externer Daten über RAG.

Textauswahl und Passage-Reranking sind integrale Bestandteile des Context Engineering, insbesondere in den Prozessen der Wissensbasis-Auswahl, des Abrufens und der Kontextkomprimierung. Passage-Reranking verfeinert dies dann, indem es die ausgewählten Texte basierend auf der Query-Relevanz neu ordnet, um sicherzustellen, dass das LLM zuerst die nützlichsten Informationen erhält, wodurch eine Überlastung vermieden und die Ausgabequalität verbessert wird.

Die submodulare Optimierung bietet drei überzeugende Vorteile gegenüber traditionellen Ansätzen für die Textauswahl und das Passage-Reranking:

tagTheoretische Strenge mit rechnerischer Effizienz

Im Gegensatz zu heuristischen Methoden bietet die submodulare Optimierung nachweisbare Garantien. Der Lazy-Greedy-Algorithmus läuft in $O(nk \log n)$ Zeit – verglichen mit $\binom{n}{k}$ Kombinationen für die vollständige Suche – und erreicht gleichzeitig eine $(1-1/e) \approx 0.632$ Approximation der optimalen Lösung. Dies bedeutet, dass unsere Lösung mathematisch garantiert mindestens 63 % so gut ist wie die theoretisch bestmögliche Auswahl. Keine Prompt-basierte Heuristik kann dieses Leistungsniveau versprechen.

tagIntelligente Abbruchkriterien

Das von uns beobachtete Sättigungsverhalten bietet einen automatischen Stoppmechanismus: Wenn sich die Grenzerträge Null nähern, wissen wir, dass wir aufhören müssen, Elemente hinzuzufügen. Diese Fähigkeit ist mit bestehenden punktweisen oder listenweisen Rerankern nicht erreichbar, die unabhängig voneinander an jedem Element arbeiten, ohne die abnehmenden Grenzerträge auf Set-Ebene zu verstehen. Die Funktion selbst sagt uns, wann wir eine ausreichende Abdeckung erreicht haben.

tagMulti-Query-Erweiterung

Das Framework lässt sich auf natürliche Weise auf Multi-Query-Szenarien erweitern – die in DeepResearch üblich sind, wo Queries häufig umgeschrieben und umformuliert werden. Die gleichen theoretischen Grundlagen und Lazy-Greedy-Algorithmen gelten nahtlos. Prompt-basierte Ansätze verfügen nicht über diese systematische Erweiterbarkeit und erfordern oft Ad-hoc-Lösungen für jedes neue Szenario.

Diese Vorteile ergeben sich aus den mathematischen Grundlagen der Submodularität und nicht aus Engineering-Tricks. Während sich andere auf Prompt-Tuning verlassen und auf gute Ergebnisse hoffen, sollten Sie die submodulare Optimierung erlernen, die einen prinzipiellen Rahmen mit formalen Garantien bietet – ein entscheidender Vorteil beim Aufbau von zuverlässigem, skalierbarem Context Engineering.