💻 computer science

Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents

Dieser Beitrag stellt \textsc{TraceToChain} vor, eine reproduzierbare Pipeline, die Ausführungsverläufe von LLM-Agenten als absorbierende diskrete Markov-Ketten modelliert, um unterschiedliche Zuverlässigkeitsmetriken in eine einzige Erfolgszeitverteilung zu überführen und gleichzeitig rigorose statistische Diagnosen, Unsicherheitsquantifizierung sowie hochpräzise empirische Validierung über mehrere Frameworks hinweg zu ermöglichen.

Ursprüngliche Autoren: Phat T. Tran-Truong, Xuan-Bach Le

Veröffentlicht 2026-04-28

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Phat T. Tran-Truong, Xuan-Bach Le

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie stellen einen sehr intelligenten, aber manchmal verwirrten Roboter-Assistenten ein, um ein komplexes Rätsel zu lösen. Sie geben ihm eine Aufgabe, und er beginnt zu denken, probiert Werkzeuge aus, macht Fehler und versucht es erneut. Manchmal löst er das Rätsel; manchmal gibt er auf oder stürzt ab.

Derzeit bewerten wir diese KI-Agenten meist nur mit einer einzigen Note, wie „72 % Erfolgsrate". Das ist so, als würde man ein Auto als „zuverlässig" bezeichnen, ohne zu wissen, ob es nach 10 Meilen oder nach 10.000 Meilen ausfällt oder ob eine kleine Änderung am Motor einen Absturz verursachen würde.

Dieser Artikel stellt eine neue Methode vor, um diese KI-Agenten zu messen, die TRACETOCHAIN heißt. Anstatt einer einzigen Note erstellt sie eine detaillierte „Karte" des Verhaltens des Agenten, um genau vorherzusagen, wie zuverlässig er unter verschiedenen Bedingungen ist.

Hier ist die Erklärung des Artikels, unter Verwendung einfacher Analogien:

1. Das Problem: Die „Ein-Zahlen"-Falle

Derzeit messen wir KI-Agenten mit einfachen Zahlen wie „pass@k" (hat es Erfolg gehabt, wenn wir es 5 Mal versuchen ließen?) oder „Zuverlässigkeitsabfall" (wird es schlechter, je länger es läuft?).

Die Analogie: Stellen Sie sich vor, Sie sind Pilot. Wenn jemand Ihnen sagt: „Dieses Flugzeug hat eine 90-prozentige Erfolgsrate", wissen Sie nicht, ob das bedeutet, dass es bei jedem zehnten Flug abstürzt, oder ob es nur bei stürmischem Wetter abstürzt. Sie können Fragen wie „Was passiert, wenn ich ein neues Navigationswerkzeug hinzufüge?" oder „Wie wahrscheinlich ist der Erfolg, wenn ich ihm 20 Minuten statt 10 gebe?", allein durch den Blick auf diese eine Zahl nicht beantworten.

2. Die Lösung: Die „Absorbierende Karte"

Die Autoren verwandeln die Historie des Agenten (seine „Spuren") in eine Markov-Kette.

Die Analogie: Betrachten Sie die Reise des Agenten als ein Brettspiel.
- Transiente Zustände: Das sind die „mittleren" Felder, auf denen der Agent noch arbeitet (z. B. „Planen", „Aufrufen eines Werkzeugs", „Lesen eines Fehlers").
- Absorbierende Zustände: Das sind die „Endspiel"-Felder. Sobald Sie hier landen, endet das Spiel. Es gibt nur zwei: Erfolg (Sie gewinnen!) und Misserfolg (Game Over).
- Die Karte: Die Autoren erstellen eine Karte, die die Wahrscheinlichkeit zeigt, von einem Feld zum nächsten zu gelangen. Wenn sich der Agent beispielsweise im „Fehler"-Feld befindet, besteht eine 30-prozentige Chance, dass er zurück zu „Planen" geht, eine 10-prozentige Chance, dass er zu „Erfolg" geht, und eine 60-prozentige Chance, dass er zu „Misserfolg" abstürzt.

3. Die „Prüfung" (Überprüfung der Karte)

Man kann nicht einfach eine Karte zeichnen und ihr vertrauen. Der Artikel führt einen strengen Prüfprozess ein, um sicherzustellen, dass die Karte tatsächlich mit der Realität übereinstimmt.

Die Analogie: Stellen Sie sich vor, Sie sind Kartograf und zeichnen eine Karte eines Waldes. Bevor Sie Wanderer sie nutzen lassen, prüfen Sie zwei Dinge:
1. Macht der Pfad Sinn? (Der Artikel verwendet einen Test namens AIC, um zu sehen, ob das Gedächtnis des Agenten kurz genug ist, um einfach modelliert zu werden, oder ob eine komplexere Karte benötigt wird).
2. Entspricht die Karte dem Gelände? (Der Artikel verwendet einen Test namens KS, um zu sehen, ob der vorhergesagte Pfad mit den tatsächlichen Pfaden übereinstimmt, die der Agent genommen hat).
Wenn die Karte diese Tests nicht besteht, sagen die Autoren: „Stopp! Verwenden Sie diese Karte nicht für Vorhersagen." Dies verhindert falsches Vertrauen.

4. Was diese Karte Ihnen ermöglicht

Sobald die Karte erstellt und geprüft ist, wird sie zu einem mächtigen Werkzeug, um Fragen zu beantworten, die das alte „Ein-Zahlen"-System nicht bewältigen konnte:

Die „Zeitbudget"-Frage: „Wenn ich dem Agenten 50 Schritte statt 10 gebe, wie viel wahrscheinlicher ist dann der Erfolg?"
- Die Behauptung des Artikels: Die Karte berechnet dies sofort, ohne den Agenten 1.000 weitere Male ausführen zu müssen.
Die „Was-wäre-wenn"-Frage: „Was wäre, wenn wir ein ‚Fallback'-Werkzeug hinzufügen, das hilft, wenn der Agent feststeckt?"
- Die Behauptung des Artikels: Sie können die Karte anpassen (die Wahrscheinlichkeiten auf dem Brettspiel ändern) und sofort sehen, wie stark sich die Erfolgsrate verbessert, ohne den gesamten Benchmark erneut auszuführen.
Die „Vereinheitlichungs"-Frage: „Sind ‚pass@5' und ‚Zuverlässigkeitsabfall' verschiedene Dinge?"
- Die Behauptung des Artikels: Nein! Sie sind nur verschiedene Ansichten derselben Karte. Der Artikel zeigt mathematisch, dass alle diese verschiedenen Metriken dieselbe „First-Passage"-Verteilung (der Pfad von Start zu Erfolg) nur aus verschiedenen Blickwinkeln betrachten.

5. Der Beweis: Hat es funktioniert?

Die Autoren testeten dies an sieben verschiedenen Arten von KI-Agenten-Frameworks (wie ReAct, Reflexion und ToolFormer).

Das Ergebnis: Sie teilten die Daten in zwei Hälften: Sie bauten die Karte auf einer Hälfte und testeten sie auf der anderen Hälfte (die die Karte noch nie gesehen hatte).
Das Ergebnis: Die Karte sagte die Erfolgsrate des Agenten mit sehr hoher Genauigkeit voraus (mit einem Fehler von etwa 5 %). Die „Prüf"-Tests akzeptierten die guten Karten korrekt und lehnten die schlechten ab.

Zusammenfassung

Der Artikel argumentiert, dass wir aufhören sollten, KI-Agenten wie einen Münzwurf (Kopf/Zahl) zu behandeln, und anfangen sollten, sie wie eine Reise mit einer Karte zu behandeln.

Indem wir Rohdaten in eine verifizierte „Absorbierende Markov-Kette" verwandeln, können wir:

Den Erfolg über die Zeit vorhersagen.
Änderungen (wie neue Werkzeuge) testen, ohne teure Neudurchläufe.
Verwirrende Metriken zu einem klaren Bild vereinheitlichen.
Die Ergebnisse prüfen, um sicherzustellen, dass wir uns nicht selbst täuschen.

Die Autoren betonen, dass dies ein konditionales Werkzeug ist: Es funktioniert nur, wenn die „Karte" die Prüfung besteht. Wenn das Verhalten des Agenten zu chaotisch ist, um in die Karte zu passen, sagt das System korrekt: „Wir können dies noch nicht vorhersagen", anstatt eine irreführende Zahl zu geben.

1. Problemstellung

Large Language Model (LLM)-Agenten werden zunehmend als sequenzielle Softwaresysteme eingesetzt, die planen, Werkzeuge aufrufen, Ergebnisse beobachten und Wiederholungen durchführen. Ihre Zuverlässigkeit wird jedoch derzeit mit skalaren Benchmark-Metriken (z. B. pass@k, passk und Zuverlässigkeits-Abklingkurven oder RDC) bewertet. Diese Metriken leiden unter drei kritischen Einschränkungen:

Fehlende Verteilungseinblicke: Sie fassen Ergebnisse zu einzelnen Zahlen zusammen, ohne die zugrunde liegende Erfolg-Zeit-Verteilung zu identifizieren.
Keine Anpassungsgüte: Sie überprüfen nicht, ob die beobachteten Ausführungsprotokolle die angenommene Verteilung tatsächlich stützen.
Ignorierte Unsicherheit: Sie quantifizieren keine Unsicherheit, die aus endlichen Protokolllängen resultiert, was es schwierig macht, kontrafaktische Fragen zu beantworten (z. B. „Was passiert, wenn wir ein Fallback-Werkzeug hinzufügen?" oder „Wie ändert sich die Zuverlässigkeit bei einem größeren Schrittbudget?").

Die Autoren argumentieren, dass die Zuverlässigkeit für LLM-Agenten als First-Passage-Problem (wie schnell ein Lauf vor einem Fehler zum Erfolg gelangt) mit expliziter Unsicherheit und Modellvalidierung behandelt werden sollte, und nicht als eine einfache Durchgangsrate am Ende.

2. Methodik: TRACETOCHAIN

Das Paper stellt TRACETOCHAIN vor, eine reproduzierbare Pipeline, die rohe Agenten-Ausführungsprotokolle in eine auditierte Absorbierende Diskrete-Zeit-Markov-Kette (DTMC) umwandelt. Die Methodik besteht aus vier Hauptphasen:

A. Zustandskonstruktion (Merkmalsabbildung & Clustering)

Eingabe: Rohprotokolle bestehend aus Denk-Schritten, Werkzeugaufrufen und Beobachtungen.
Prozess:
1. Merkmalsabbildung (Featurization): Schritte werden mithilfe regelbasierter Merkmale (z. B. Werkzeugtyp, Fehlercodes) oder erlernter Encoder in Vektordarstellungen abgebildet.
2. Clustering: Agglomerative Ward-Linkage gruppiert diese Vektoren in diskrete transiente Zustände ( $S_T$ ). Die Anzahl der Cluster wird über den Silhouette-Score ausgewählt.
3. Ergebniszusammenführung: Protokolle enden entweder in Erfolg ( $\oplus$ ) oder Fataler Fehler ( $\ominus$ ), die als absorbierende Zustände dienen.

B. Schätzung der Übergänge

Modell: Das System passt eine DTMC $\hat{M} = (\hat{Q}, \hat{R}^\oplus, \hat{R}^\ominus)$ an, wobei $\hat{Q}$ Übergänge zwischen transienten Zuständen darstellt und $\hat{R}^\oplus, \hat{R}^\ominus$ die Wahrscheinlichkeiten für den Austritt in Erfolg oder Fehler repräsentieren.
Schätzung: Parameter werden mittels Laplace-geglätteter Maximum-Likelihood-Schätzung (MLE) geschätzt, um Null-Wahrscheinlichkeiten für nicht beobachtete, aber plausible Übergänge zu verhindern.

C. Anpassungsgüte-Protokoll (GoF)

Um sicherzustellen, dass die Markov-Abstraktion gültig ist, setzt die Pipeline einen zusammengesetzten diagnostischen Test ein:

Kolmogorov–Smirnov (KS)-Test: Vergleicht die empirische kumulative Verteilungsfunktion (CDF) der First-Passage-Zeiten (Zeit bis zum Erfolg) mit der analytischen CDF, die aus der angepassten Kette abgeleitet wurde.
Akaike-Informationskriterium (AIC): Vergleicht das Markov-Modell erster Ordnung mit einer Alternative zweiter Ordnung, um sicherzustellen, dass die Speicheranforderungen erfüllt sind.

Entscheidung: Die Kette wird nur akzeptiert, wenn $p_{KS} > 0.05$ und $\Delta AIC > 0$ . Bei Ablehnung muss das Protokollkorpus segmentiert oder neu merkmalsbasiert aufbereitet werden.

D. Quantifizierung der Unsicherheit

Die Pipeline liefert Konfidenzintervalle für alle Zuverlässigkeitsmetriken unter Verwendung von:

Dirichlet-Hintergrundintervallen: Abgeleitet aus der Laplace-geglätteten MLE, um Parameterunsicherheit zu quantifizieren.
Nicht-parametrischem Bootstrap: Resampling von Protokollen zur Schätzung der Variabilität in der angepassten Kette.

3. Hauptbeiträge & Theoretischer Rahmen

A. Vereinheitlichung der Metriken

Das Paper beweist, dass pass@k, passk und die Zuverlässigkeits-Abklingkurve (RDC) keine konkurrierenden Metriken sind, sondern Projektionen einer einzigen Erfolg-First-Passage-Verteilung:

RDC ( $R(d)$ ): Wahrscheinlichkeit eines Erfolgs innerhalb von $d$ Schritten.
$pass_k$ : Wahrscheinlichkeit, dass $k$ unabhängige Versuche alle erfolgreich sind ( $R_\infty^k$ ).
$pass@k$: Wahrscheinlichkeit, dass mindestens einer von $k$ Versuchen erfolgreich ist ( $1 - (1-R_\infty)^k$ ).
Theorem: Diese Beziehungen gelten unter i.i.d.-Annahmen; Abweichungen deuten auf versteckte Korrelationen zwischen den Versuchen hin.

B. Analytische Werkzeuge für den Einsatz

Unter Verwendung der Fundamental-Matrix $N = (I - \hat{Q})^{-1}$ leiten die Autoren geschlossene Lösungen ab für:

Horizont-Zuverlässigkeit: Berechnung von $R(d)$ für jedes beliebige Schrittbudget ohne erneutes Durchlaufen von Benchmarks.
Störungsempfindlichkeit: Schätzung der Auswirkungen lokaler Änderungen (z. B. Hinzufügen eines Fallback-Werkzeugs) auf die globale Zuverlässigkeit mittels Sensitivitätsanalyse erster Ordnung.
NHPP-Grenzwert: Zeigen, dass in Regimen seltener Fehler die angepasste Agenten-Kette gegen das klassische Goel–Okumoto-Modell für Nicht-homogene Poisson-Prozesse (NHPP) konvergiert und so moderne Agenten-Zuverlässigkeit mit der klassischen Software-Zuverlässigkeitstheorie verbindet.

4. Ergebnisse & Validierung

Die Autoren validierten TRACETOCHAIN durch Simulationsstudien und empirische Fallstudien:

Simulationsstudie SS1 (Numerisch): Verifizierte, dass die geschlossenen Zuverlässigkeitsberechnungen mit Monte-Carlo-Simulationen über verschiedene Kettengrößen hinweg übereinstimmen.
Simulationsstudie SS7 (GoF-Diagnostik):
- Akzeptierte korrekt 100 % der Protokolle, die aus echten Markov-Ketten erster Ordnung generiert wurden.
- Lehnte korrekt 100 % der Protokolle ab, die aus Ketten zweiter Ordnung generiert wurden (wobei die AIC-Schicht die Abhängigkeit erkannte).
Simulationsstudie SS9 (Held-Out-Validierung):
- Getestet an 7 kontrollierten MAST-artigen Frameworks mit einem strikten 50/50-Aufteilung in Trainings- und Testdaten.
- Ergebnisse: Die angepassten Ketten sagten die zurückgehaltenen Zuverlässigkeits-Abklingkurven genau voraus.
  - Maximale $L_{RDC}^\infty$ -Fehler: 0,053 (Median: 0,048).
  - KS-Test-p-Werte: Alle Frameworks bestanden ( $p > 0.05$ ), mit einem minimalen $p = 0.78$ .
- Dies zeigt, dass die Pipeline die zugrunde liegende Erfolg-Zeit-Verteilung wiederherstellt, ohne die Trainingsdaten zu überanpassen.
Empirische Fallstudien (SS6): Angewendet auf 7 reale Agenten-Frameworks (z. B. ReAct, Reflexion, ToolFormer). Die Pipeline rangierte Frameworks erfolgreich nach asymptotischer Zuverlässigkeit ( $R_\infty$ ) und visualisierte ihre spezifischen RDC-Formen.

5. Bedeutung und Auswirkung

Von Skalaren zu Strukturellen: Verschiebt die Bewertung von LLM-Agenten von statischen skalaren Scores zu einem dynamischen, auditierbaren Zuverlässigkeitsmodell, das den Prozess der Ausführung erfasst, nicht nur das Ergebnis.
Auditierbare Zuverlässigkeit: Liefert ein „Zertifikat" (GoF-Tests + Unsicherheitsintervalle) für Zuverlässigkeitsbehauptungen und adressiert die „Black-Box"-Natur der Agentenbewertung.
Kontrafaktisches Schließen: Ermöglicht Ingenieuren, „Was-wäre-wenn"-Fragen (z. B. „Wie wirkt sich das Hinzufügen eines Wiederholungsmechanismus auf die Zuverlässigkeit aus?") mittels Störungsanalyse an der angepassten Kette zu beantworten, ohne die Kosten für das erneute Durchlaufen vollständiger Benchmarks.
Metrik-Rekonkiliation: Klärt Verwirrung zwischen verschiedenen Benchmark-Metriken auf, indem gezeigt wird, dass sie mathematisch verknüpfte Projektionen derselben zugrunde liegenden Verteilung sind.
Praktischer Nutzen: Die Pipeline ist einsatzbereit mit kontrollierten Protokolldaten (wie MAST), wobei zukünftige Arbeiten für komplexe Benchmarks wie SWE-bench und $\tau$ -bench geplant sind, sobald stabile Schritt-level-Merkmale verfügbar sind.

Zusammenfassend bietet TRACETOCHAIN ein rigoroses, mathematisch fundiertes Framework, um rohe LLM-Agenten-Protokolle in ein zuverlässiges, diagnostisches und prädiktives Modell der Systemzuverlässigkeit zu transformieren.