Wo man suchen sollte: Messung des Prior-strukturierten Suchraums von LLM-Agenten

Grundinformationen

• Paper-ID: 2510.14846
• Titel: Where to Search: Measure the Prior-Structured Search Space of LLM Agents
• Autor: Zhuo-Yang Song
• Klassifizierung: cs.AI cs.CL cs.LO
• Veröffentlichungsdatum: 16. Oktober 2025 (arXiv Preprint)
• Paper-Link: https://arxiv.org/abs/2510.14846

Zusammenfassung

Das iterative Paradigma der Generierung-Filterung-Optimierung (generate-filter-refine) auf Basis großer Sprachmodelle (LLMs) hat Fortschritte bei der Schlussfolgerung, Programmierung und der Programmentdeckung in der KI+Wissenschaft erzielt. Die Effektivität der Suche hängt jedoch davon ab, wo gesucht wird, d.h. wie Domänenpriorinformationen in einen operativen strukturierten Hypothesenraum kodiert werden. Zu diesem Zweck präsentiert dieses Paper eine kompakte formale Theorie zur Beschreibung und Messung der durch Domänenpriorinformationen geleiteten LLM-gestützten iterativen Suche. Der Autor stellt Agenten als unscharfe Relationsoperatoren auf Ein- und Ausgaben dar, um machbare Transformationen zu erfassen; Agenten werden daher durch eine feste Sicherheitshülle begrenzt. Um mehrstufiges Denken/Suchen zu beschreiben, werden alle erreichbaren Pfade durch einen einzelnen Fortsetzungsparameter gewichtet und summiert, was eine Erzeugungsfunktion ergibt; dies induziert ein Maß für die Erreichbarkeitsschwierigkeit und bietet eine geometrische Interpretation der Suche auf dem durch die Sicherheitshülle induzierten Graphen.

Forschungshintergrund und Motivation

Kernproblem

Das Kernproblem dieser Forschung ist: Wie kann man den Suchraum von LLM-Agenten systematisch messen und beschreiben? Konkret wird die Sucheffizienz in LLM-basierten iterativen Suchprozessen grundlegend durch die Frage "wo man suchen sollte" begrenzt, d.h. wie Domänenpriorinformationen in einen für den Agenten operativen Raum kodiert werden.

Bedeutung des Problems

1. Anforderungen bei langfristigen Aufgaben: Langfristige Aufgaben stellen höhere Anforderungen an Sicherheit und Kontrollierbarkeit und erfordern Operationen innerhalb verifizierbarer und kontrollierbarer Grenzen
2. Komplexitätsherausforderungen: Langfristige Probleme beinhalten oft kombinatorische Explosionen und spärliche Belohnungen; reine Heuristiken oder 0/1-Bewertungen reichen nicht aus, um die Erreichbarkeitsschwierigkeit zu quantifizieren
3. Theoretische Lücke: Die aktuelle Praxis stützt sich hauptsächlich auf technische Heuristiken (Prompt-Design, Filter, Bewertungsfunktionen usw.) und entbehrt einer einheitlichen Sprache und quantitativer Werkzeuge

Einschränkungen bestehender Methoden

• Fehlende einheitliche Sprache für Agent-Raum-Suchenmessung
• Schwierigkeit, die Erreichbarkeits- und Sicherheitskompromisse zwischen verschiedenen Agenten vergleichbar zu messen
• Mangel an klarer Charakterisierung und Erklärung der langfristigen Verhaltensmerkmale von Agenten

Forschungsmotivation

Etablierung einer prägnanten, berechenbaren, modellunabhängigen formalen Theorie, die Sicherheits- und Erreichbarkeitsmessungen vereinheitlicht und testbare Vorhersagen sowie technisch nutzbare Designprinzipien bietet.

Kernbeiträge

1. Präsentation einer prägnanten formalen Theorie: Formalisierung von Agenten als unscharfe Relationsoperatoren, einheitliche Beschreibung iterativer Suchprozesse durch Erzeugungsfunktionen
2. Etablierung eines einheitlichen Messsystems: Einführung von Fortsetzungsparameter und Abdeckungsindex, Bereitstellung einer einheitlichen Quantifizierungsmethode für Sicherheit und Erreichbarkeit
3. Bereitstellung geometrischer Interpretation: Definition geometrischer Größen auf dem durch die Sicherheitshülle induzierten gerichteten Graphen, geometrische Interpretation des Suchprozesses
4. Verifikation theoretischer Vorhersagen: Verifikation der testbaren Schlussfolgerungen der Theorie durch Mehrheitsentscheidungsinstanziierung, externe Validierung bereitgestellt

Methodische Details

Aufgabendefinition

• Eingaberaum: $C_1$ (Eingaberaum des Agenten)
• Ausgaberaum: $C_2$ (Ausgaberaum des Agenten, mit $C_2 \subseteq C_1$ zur Unterstützung von Iteration)
• Ziel: Messung und Beschreibung iterativer Suchprozesse unter Sicherheitsbeschränkungen

Mathematischer Kernrahmen

1. Agentendarstellung

Idealer Agent definiert als unscharfer Relationsoperator: $T(f,g) := \mu_f(g), \quad \mu_f: C_2 \to [0,1]$

Spröder idealer Agent (Sicherheitshülle): $\mu_f(g) \in \{0,1\}, \quad 0 \leq T(f,g) \leq T_0(f,g)$

2. Erzeugungsfunktion

Einführung eines Fortsetzungsparameters $p \in [0,1]$, Definition der Erzeugungsfunktion von $f$ zu $g$: $P_{f,g}(p) := \sum_{n=0}^{\infty} \sum_{S_T: f^{(0)}=f, f^{(n)}=g} p^n \prod_{i=0}^{n-1} \mu_{f^{(i)}}(f^{(i+1)})$

Wenn $C_1, C_2$ abzählbar sind, kann dies in Matrixform dargestellt werden: $P(p) = \sum_{n \geq 0} p^n M^n = (I - pM)^{-1}$

3. Wichtige geometrische Größen

• Kürzeste Distanz: $d_0(f,g) := \inf\{n \in \mathbb{N}: N_n(f,g) \geq 1\}$
• Anzahl kürzester Pfade: $N_{d_0}(f,g)$
• Kritischer Parameter: $p_c(f,g) := \inf\{p \in [0,1]: P_{f,g}^{ideal}(p) \geq 1\}$
• Abdeckungsindex: $R_c(f,g) := 1 - p_c(f,g)$

Technische Innovationen

1. Einheitliche Messprache

Durch unscharfe Relationsoperatoren wird eine einheitliche Agentendarstellung ermöglicht, sodass Sicherheit und Erreichbarkeit mit denselben mathematischen Symbolen und geometrischen Größen gemessen werden können.

2. Fortsetzungsparameter-Mechanismus

Einführung eines einzelnen Fortsetzungsparameters $p$ zur Gewichtung der Trajektorielänge, vermeidung der Komplexität probabilistischer Interpretationen, Bereitstellung einer berechenbaren Messmethode.

3. Geometrische Interpretation

Definition der Suchgeometrie auf dem durch die Sicherheitshülle induzierten gerichteten Graphen, Umwandlung abstrakter Suchprozesse in konkrete graphentheoretische Probleme.

4. Testbare Hypothesen

Präsentation zweier Schlüsselhypothesen für LLM-konstruierte iterative Agenten:

• Hypothese 1: Näherungsweise unidirektionale Suche (geschlossene Schleifen sind selten)
• Hypothese 2: Niedrigordnungsterme dominieren (sehr lange Trajektorien sind relativ selten)

Experimentelle Einrichtung

Experimentelle Umgebung

• Suchraum: Zweidimensionales Gitter $G_N := \{0,\ldots,N-1\}^2$
• Gittergröße: $N = 3, 5, 8$
• Zielpunkte: Jeweils $(1,2), (3,4), (6,7)$

Agentenkonstruktion

1. LLM-Modellsatz: gpt-4-mini, gpt-4, qwen3, qwen-plus, gemini-2.5-flash, deepseek-v3, grok-4, doubao
2. Mehrheitsentscheidungsmechanismus: Für jede Position $f$ unabhängig $m=5$ Mal samplen, Modus als Entscheidung nehmen
3. Idealer Agent: $\mu_f^{(t)}(g) := \frac{1}{n}\sum_L \mu_f^{(L,t)}(g)$
4. Sicherheitshülle: $\mu_f^{0,(t)}(g) := \mathbf{1}\{\mu_f^{(t)}(g) > 0\}$

Bewertungsindikatoren

• Kürzeste Distanz $d_0(f,t)$
• Anzahl kürzester Pfade $N_{d_0}(f,t)$
• Verifikation der Ungleichung: $\log N_{d_0}(f,g) \ll d_0(f,g)$

Experimentelle Ergebnisse

Hauptergebnisse

1. Graphenstrukturmerkmale

Experimente zeigen, dass die durch LLM induzierte Sicherheitshülle auf 2D-Gittern unidirektionale und anisotrope erreichbare Strukturen erzeugt, die streng zur Manhattan-Distanz des Ziels abnehmen, konsistent mit der endlichen Termvoraussetzung von Hypothese 1.

2. Verifikation geometrischer Beziehungen

Abbildung 2 zeigt die Beziehung zwischen $(d_0, N_{d_0})$ bei drei Gittergrößen:

• Datenpunkte liegen unterhalb der theoretisch vorhergesagten empirischen Obergrenze
• Wenn $d_0$ größer ist, passt die Ungleichung $\log N_{d_0} \ll d_0$ besser
• Unterstützt die empirische Regel im Grenzfall kleiner $R_c$

3. Hypothesenverifikation

• Unidirektionale Graphenstruktur: Die beobachtete Graphenstruktur weist unidirektionale Merkmale auf und unterstützt Hypothese 1
• Endliche Pfadzählung: Endliche Pfadzählung stimmt mit der Einstellung von Hypothese 2 überein
• Komplexitätsdominanz: Verifikation der Charakteristik, dass Komplexität (kürzeste Distanz) dominiert, während Pfadvielfalt begrenzt ist

Experimentelle Erkenntnisse

1. Schwellenwertverhalten: Bei kleinen Fortsetzungsparametern befindet sich die Suche in einem unzureichend erweiterten Zustand, wobei der kürzeste Pfadterm das Verhalten von $P_{f,g}(p)$ dominiert
2. Geometrische Beschränkungen: Die semantischen Beschränkungen von LLMs führen dazu, dass der Graph eine unidirektionale Struktur aufweist, die den Suchraum effektiv begrenzt
3. Erreichbarkeitsmuster: Die beobachtete $(d_0, N_{d_0})$-Beziehung stimmt mit der Obergrenzentrendvorhersage der Theorie überein

Verwandte Arbeiten

Hauptforschungsrichtungen

1. LLM-Schlussfolgerungsparadigmen: ReAct, Tree of Thoughts, Chain-of-Thought und andere iterative Schlussfolgerungsmethoden
2. Planung und Werkzeugnutzung: Plan-and-Solve, Toolformer, Voyager und andere Agenten-Frameworks
3. KI+Wissenschaft-Anwendungen: LLM-Anwendungen in Programmsuche, Algorithmusentdeckung, wissenschaftlichen Berechnungen und anderen Bereichen

Vorteile dieses Papers

• Bietet einen einheitlichen theoretischen Rahmen, während bestehende Methoden meist empirische Heuristiken sind
• Etabliert einen messbaren Sicherheits-Erreichbarkeitskompromissmechanismus
• Bietet eine modellunabhängige formale Beschreibung

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

1. Theoretischer Beitrag: Etablierung einer prägnanten formalen Theorie für LLM-gestützte iterative Suche
2. Messwerkzeuge: Bereitstellung operativer Werkzeuge zur einheitlichen Messung von Sicherheit und Erreichbarkeit
3. Geometrische Einsichten: Enthüllung der geometrischen Struktur und Beschränkungsmechanismen von Suchprozessen
4. Empirische Verifikation: Verifikation testbarer Vorhersagen der Theorie durch Mehrheitsentscheidungsinstanziierung

Einschränkungen

1. Experimentelle Skalierung: Aktuelle Verifikation beschränkt sich auf kleine 2D-Gitter, erfordert Verifikation bei größeren Skalen und komplexeren Aufgaben
2. Modellabdeckung: Obwohl mehrere LLMs verwendet werden, ist eine breitere Modell- und Aufgabenabdeckung erforderlich
3. Theoretische Vollständigkeit: Einige theoretische Vorhersagen (wie direkte Schätzung von $R_c$) wurden in Experimenten noch nicht vollständig verifikiert

Zukünftige Richtungen

1. Detaillierte experimentelle Verifikation: Testen der Theorieeffektivität bei komplexeren Aufgaben
2. Verbindung zu Verstärkungslernen: Verbindung theoretischer Indikatoren mit Verstärkungslernbelohnungen und Trainingsprozessen
3. Praktische Anwendung: Anwendung von Messwerkzeugen auf Agenten-Design und Training bei komplexen Aufgaben

Tiefgreifende Bewertung

Stärken

1. Starke theoretische Innovation: Erste Präsentation einer formalen Mestheorie für LLM-Agenten-Suchraum
2. Strenger mathematischer Rahmen: Solide mathematische Grundlagen basierend auf unscharfen Relationsoperatoren und Erzeugungsfunktionen
3. Hoher praktischer Wert: Bereitstellung operativer Messwerkzeuge und Designrichtlinien
4. Ausreichende Verifikation: Externe Verifikation der Theorie durch konkrete Instanziierung

Mängel

1. Begrenzte experimentelle Skalierung: Verifikationsexperimente sind relativ einfach, es fehlen Tests bei komplexen realen Aufgaben
2. Hypothesenabhängigkeit: Theoretische Vorhersagen hängen von der Erfüllung spezifischer Hypothesen ab (Unidirektionalität, Niedrigordnungsdominanz)
3. Rechenkomplexität: Bei großen Problemen kann die Berechnung der Erzeugungsfunktion auf Komplexitätsprobleme stoßen

Einfluss

1. Akademischer Beitrag: Bereitstellung neuer theoretischer Grundlagen und Analysewerkzeuge für LLM-Agenten-Forschung
2. Praktischer Wert: Quantitative Anleitung für Agenten-Design bei komplexen Aufgaben
3. Reproduzierbarkeit: Bereitstellung detaillierter experimenteller Einrichtungen und Code mit guter Reproduzierbarkeit

Anwendungsszenarien

• LLM-Agenten-Design mit Sicherheitsbeschränkungen
• Leistungsanalyse bei langfristigen Schlussfolgerungs- und Planungsaufgaben
• Strukturierte Analyse und Optimierung komplexer Suchräume
• Vergleich und Bewertung von Multi-Agenten-Systemen

Referenzen

Das Paper zitiert 32 verwandte Literaturquellen, die wichtige Arbeiten in mehreren Bereichen wie LLM-Schlussfolgerung, Verstärkungslernen, Constraint-Optimierung und unscharfe Systeme abdecken und eine solide Grundlage für die Theoriekonstruktion bieten.