Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents

1. Probleemstelling

Grote Taalmodellen (LLM)-agenten worden steeds vaker ingezet als sequentiële softwaresystemen die plannen, hulpmiddelen aanroepen, resultaten observeren en opnieuw proberen. Hun betrouwbaarheid wordt momenteel echter geëvalueerd aan de hand van scalar benchmark-metrics (bijvoorbeeld pass@k, passk en Reliability Decay Curves of RDC). Deze metrics lijden aan drie kritieke beperkingen:

1. Gebrek aan distributie-inzicht: Ze vatten uitkomsten samen tot enkele getallen zonder de onderliggende succes-tijdsdistributie te identificeren.
2. Geen goedheid-van-passing: Ze verifiëren niet of de waargenomen uitvoeringstraces daadwerkelijk de aangenomen distributie ondersteunen.
3. Genegeerde onzekerheid: Ze kwantificeren geen onzekerheid die voortvloeit uit eindige trace-lengtes, waardoor het moeilijk is om contrafactuele vragen te beantwoorden (bijvoorbeeld: "Wat gebeurt er als we een fallback-tool toevoegen?" of "Hoe verandert de betrouwbaarheid met een groter stappenbudget?").

De auteurs betogen dat betrouwbaarheid voor LLM-agenten moet worden behandeld als een first-passage-probleem (hoe snel een run succes bereikt vóór falen) met expliciete onzekerheid en modelvalidatie, in plaats van als een terminale slaagkans.

2. Methodologie: TRACETOCHAIN

Het artikel introduceert TRACETOCHAIN, een reproduceerbare pijplijn die ruwe agent-uitvoeringstraces transformeert in een geauditeerde Absorberende Discrete-Tijd Markov-keten (DTMC). De methodologie bestaat uit vier hoofdfasen:

A. State Constructie (Featurization & Clustering)

• Input: Ruwe traces bestaande uit redeneerstappen, tool-aanroepen en observaties.
• Proces:
  1. Featurization: Stappen worden gemapt naar vectorrepresentaties met behulp van op regels gebaseerde features (bijvoorbeeld tool-type, foutcodes) of geleerde encoders.
  2. Clustering: Agglomeratieve Ward-linkage cluster deze vectoren tot discrete transient states ($S_T$). Het aantal clusters wordt geselecteerd aan de hand van de silhouette-score.
  3. Outcome Mapping: Traces eindigen in ofwel Succes ($\oplus$) ofwel Fatale Fout ($\ominus$), die dienen als absorberende states.

B. Transition Estimation

• Model: Het systeem past een DTMC $\hat{M} = (\hat{Q}, \hat{R}^\oplus, \hat{R}^\ominus)$, waarbij $\hat{Q}$ transities tussen transient states voorstelt, en $\hat{R}^\oplus, \hat{R}^\ominus$ de kansen voorstellen om naar succes of fout te gaan.
• Estimation: Parameters worden geschat met behulp van Laplace-gesmoothde Maximum Likelihood Estimation (MLE) om nul-kansen voor niet-waargenomen maar plausibele transities te voorkomen.

C. Goodness-of-Fit (GoF) Protocol

Om te waarborgen dat de Markov-abstractie geldig is, hanteert de pijplijn een samengestelde diagnostische test:

1. Kolmogorov–Smirnov (KS) Test: Vergelijkt de empirische cumulatieve distributiefunctie (CDF) van first-passage times (tijd tot succes) met de analytische CDF afgeleid van de aangepaste keten.
2. Akaike Information Criterion (AIC): Vergelijkt het eerste-orde Markov-model met een tweede-orde alternatief om te waarborgen dat geheugenvereisten worden voldaan.

• Besluit: De keten wordt alleen geaccepteerd als $p_{KS} > 0.05$ en $\Delta AIC > 0$. Bij afwijzing moet het trace-corpus worden gesegmenteerd of opnieuw worden gefeaturiseerd.

D. Onzekerheidskwantificering

De pijplijn biedt betrouwbaarheidsintervallen voor alle betrouwbaarheidsmetrics met behulp van:

• Dirichlet Posterior Intervallen: Afgeleid van de Laplace-gesmoothde MLE om parameteronzekerheid te kwantificeren.
• Niet-parametrische Bootstrap: Herhaling van traces om variabiliteit in de aangepaste keten te schatten.

3. Belangrijkste Bijdragen & Theoretisch Kader

A. Unificatie van Metrics

Het artikel bewijst dat pass@k, passk en de Reliability Decay Curve (RDC) geen concurrerende metrics zijn, maar projecties van één enkele succes-first-passage distributie:

• RDC ($R(d)$): Kans op succes binnen $d$ stappen.
• $pass_k$: Kans dat $k$ onafhankelijke trials allemaal slagen ($R_\infty^k$).
• $pass@k$: Kans dat minstens één van de $k$ trials slaagt ($1 - (1-R_\infty)^k$).
• Stelling: Deze relaties gelden onder i.i.d.-aannames; afwijkingen wijzen op verborgen correlaties tussen trials.

B. Analytische Hulpmiddelen voor Implementatie

Met behulp van de fundamentele matrix $N = (I - \hat{Q})^{-1}$ leiden de auteurs gesloten-formule oplossingen af voor:

1. Horizon Betrouwbaarheid: Het berekenen van $R(d)$ voor elk stappenbudget zonder benchmarks opnieuw te draaien.
2. Perturbatie Sensitiviteit: Het schatten van de impact van lokale veranderingen (bijvoorbeeld het toevoegen van een fallback-tool) op de globale betrouwbaarheid met behulp van first-order sensitiviteitsanalyse.
3. NHPP Limit: Het aantonen dat in regimes met zeldzame fouten, de aangepaste agent-keten convergeert naar het klassieke Goel–Okumoto Non-Homogeneous Poisson Process (NHPP)-model, waardoor moderne agent-betrouwbaarheid wordt verbonden met klassieke softwarebetrouwbaarheidstheorie.

4. Resultaten & Validatie

De auteurs hebben TRACETOCHAIN gevalideerd via simulatiestudies en empirische casestudies:

• Simulatiestudie SS1 (Numeriek): Verifieerde dat de gesloten-formule betrouwbaarheidsberekeningen overeenkomen met Monte Carlo-simulaties over verschillende ketengroottes.
• Simulatiestudie SS7 (GoF Diagnostics):
  • Accepteerde correct 100% van de traces gegenereerd uit ware 1e-orde Markov-ketens.
  • Reageerde correct 100% van de traces gegenereerd uit 2e-orde ketens af (waarbij de AIC-laag de afhankelijkheid detecteerde).
• Simulatiestudie SS9 (Held-Out Validatie):
  • Getest op 7 gecontroleerde MAST-achtige frameworks met een strikte 50/50 fit/test-split.
  • Resultaten: De aangepaste ketens voorspelden de aangehouden Reliability Decay Curves nauwkeurig.
    • Maximum $L_{RDC}^\infty$ fout: 0.053 (Mediaan: 0.048).
    • KS-test p-waarden: Alle frameworks slaagden ($p > 0.05$), met een minimale $p = 0.78$.
  • Dit toont aan dat de pijplijn de onderliggende succes-tijdsdistributie herstelt zonder overfitting op de trainingsdata.
• Empirische Casestudies (SS6): Toegepast op 7 real-world agent frameworks (bijvoorbeeld ReAct, Reflexion, ToolFormer). De pijplijn slaagde erin frameworks te rangschikken op asymptotische betrouwbaarheid ($R_\infty$) en hun specifieke RDC-vormen te visualiseren.

5. Betekenis en Impact

• Van Scalar naar Structureel: Verplaatst de evaluatie van LLM-agenten van statische scalar scores naar een dynamisch, auditabel betrouwbaarheidsmodel dat het proces van uitvoering vastlegt, niet alleen het resultaat.
• Auditabele Betrouwbaarheid: Biedt een "certificaat" (GoF-tests + onzekerheidsintervallen) voor betrouwbaarheidsclaims, waardoor de "black box"-aard van agent-evaluatie wordt aangepakt.
• Contrafactueel Redeneren: Maakt het ingenieurs mogelijk om "what-if"-vragen te beantwoorden (bijvoorbeeld: "Hoe beïnvloedt het toevoegen van een retry-mechanisme de betrouwbaarheid?") met behulp van perturbatieanalyse op de aangepaste keten, waardoor de kosten van het opnieuw draaien van volledige benchmarks worden vermeden.
• Metric Reconciliatie: Lost verwarring tussen verschillende benchmark-metrics op door te laten zien dat ze wiskundig gekoppelde projecties zijn van dezelfde onderliggende distributie.
• Praktische Bruikbaarheid: De pijplijn is klaar voor gebruik met gecontroleerde trace-data (zoals MAST), met toekomstig werk gepland voor complexe benchmarks zoals SWE-bench en $\tau$-bench zodra stabiele stap-niveau features beschikbaar zijn.

Kortom, TRACETOCHAIN biedt een rigoureus, wiskundig onderbouwd kader om ruwe LLM-agent-traces om te zetten in een betrouwbaar, diagnostisch en voorspellend model van systeemafhankelijkheid.