💻 computer science

Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents

Cet article présente \textsc{TraceToChain}, un pipeline reproductible qui modélise les traces d'exécution d'agents LLM comme des chaînes de Markov discrètes à temps absorbant afin d'unifier des métriques de fiabilité disparates en une seule distribution de temps de succès tout en fournissant des diagnostics statistiques rigoureux, une quantification de l'incertitude et une validation empirique haute fidélité à travers plusieurs cadres.

Auteurs originaux : Phat T. Tran-Truong, Xuan-Bach Le

Publié 2026-04-28

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Phat T. Tran-Truong, Xuan-Bach Le

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous embauchiez un assistant robot très intelligent, mais parfois confus, pour résoudre un puzzle complexe. Vous lui donnez une tâche, et il commence à réfléchir, à essayer des outils, à commettre des erreurs et à réessayer. Parfois, il résout le puzzle ; parfois, il abandonne ou plante.

Actuellement, lorsque nous évaluons ces agents IA, nous leur attribuons généralement une seule note, comme « un taux de réussite de 72 % ». C'est comme dire qu'une voiture est « fiable » sans savoir si elle tombe en panne après 10 miles ou 10 000 miles, ou si un petit changement dans le moteur la ferait planter.

Ce papier introduit une nouvelle façon de mesurer ces agents IA appelée TRACETOCHAIN. Au lieu d'une seule note, il construit une « carte » détaillée du comportement de l'agent pour prédire exactement sa fiabilité dans différentes conditions.

Voici comment le papier l'explique, en utilisant des analogies simples :

1. Le Problème : Le Piège du « Chiffre Unique »

Actuellement, nous mesurons les agents IA avec des chiffres simples comme « pass@k » (a-t-il réussi si nous lui permettons d'essayer 5 fois ?) ou « déclin de fiabilité » (s'aggrave-t-il plus il fonctionne longtemps ?).

L'Analogie : Imaginez que vous êtes pilote. Si quelqu'un vous dit : « Cet avion a un taux de réussite de 90 % », vous ne savez pas si cela signifie qu'il s'écrase tous les 10 vols, ou seulement lorsque le temps est orageux. Vous ne pouvez pas répondre à des questions comme : « Que se passe-t-il si j'ajoute un nouvel outil de navigation ? » ou « Quelle est la probabilité de réussite si je lui donne 20 minutes au lieu de 10 ? » simplement en regardant ce seul chiffre.

2. La Solution : La « Carte Absorbante »

Les auteurs transforment l'historique de l'agent (ses « traces ») en une Chaîne de Markov.

L'Analogie : Considérez le parcours de l'agent comme un jeu de société.
- États Transitoires : Ce sont les cases « intermédiaires » où l'agent travaille encore (par exemple : « Planification », « Appel d'un Outil », « Lecture d'une Erreur »).
- États Absorbants : Ce sont les cases « Fin de Partie ». Une fois que vous y atterrissez, le jeu s'arrête. Il n'y en a que deux : Succès (Vous gagnez !) et Échec (Game Over).
- La Carte : Les auteurs créent une carte montrant la probabilité de passer d'une case à l'autre. Par exemple, si l'agent est dans la case « Erreur », il y a 30 % de chances qu'il retourne à « Planification », 10 % de chances qu'il aille au « Succès », et 60 % de chances qu'il plante vers l'« Échec ».

3. L'« Audit » (Vérification de la Carte)

On ne peut pas simplement dessiner une carte et lui faire confiance. Le papier introduit un processus d'audit strict pour s'assurer que la carte correspond bien à la réalité.

L'Analogie : Imaginez que vous êtes un cartographe dessinant une carte d'une forêt. Avant de permettre aux randonneurs de l'utiliser, vous vérifiez deux choses :
1. Le chemin a-t-il du sens ? (Le papier utilise un test appelé AIC pour voir si la mémoire de l'agent est suffisamment courte pour être modélisée simplement, ou s'il a besoin d'une carte plus complexe).
2. La carte correspond-elle au terrain ? (Le papier utilise un test appelé KS pour voir si le chemin prédit correspond aux chemins réels empruntés par l'agent).
Si la carte échoue à ces tests, les auteurs disent : « Stop ! N'utilisez pas cette carte pour des prédictions. » Cela évite une fausse confiance.

4. Ce Que Cette Carte Vous Permet de Faire

Une fois la carte construite et audité, elle devient un outil puissant pour répondre à des questions que l'ancien système « chiffre unique » ne pouvait pas traiter :

La Question du « Budget de Temps » : « Si je donne 50 étapes à l'agent au lieu de 10, quelle est l'augmentation de sa probabilité de réussite ? »
- L'Affirmation du Papier : La carte calcule cela instantanément sans avoir besoin d'exécuter l'agent 1 000 fois de plus.
La Question du « Et Si » : « Et si nous ajoutions un outil de « repli » qui aide lorsque l'agent est bloqué ? »
- L'Affirmation du Papier : Vous pouvez modifier la carte (changer les probabilités sur le jeu de société) et voir instantanément dans quelle mesure le taux de réussite s'améliore, sans relancer tout le benchmark.
La Question de l'« Unification » : « « pass@5 » et « déclin de fiabilité » sont-ils des choses différentes ? »
- L'Affirmation du Papier : Non ! Ce sont simplement différentes vues de la même carte. Le papier montre mathématiquement que toutes ces différentes métriques ne font qu'examiner la même distribution de « Premier Passage » (le chemin du Départ au Succès) sous différents angles.

5. La Preuve : Cela a-t-il Fonctionné ?

Les auteurs ont testé cela sur sept types différents de cadres d'agents IA (comme ReAct, Reflexion et ToolFormer).

Le Résultat : Ils ont divisé les données en deux : ils ont construit la carte sur la première moitié et l'ont testée sur l'autre moitié (que la carte n'avait jamais vue).
Le Résultat Final : La carte a prédit le taux de réussite de l'agent avec une très grande précision (avec une erreur d'environ 5 %). Les tests d'« audit » ont correctement accepté les bonnes cartes et rejeté les mauvaises.

Résumé

Le papier soutient que nous devrions cesser de traiter les agents IA comme un lancer de pièce (Pile/Face) et commencer à les traiter comme un voyage avec une carte.

En transformant des données brutes en une « Chaîne de Markov Absorbante » vérifiée, nous pouvons :

Prédire la réussite dans le temps.
Tester des changements (comme de nouveaux outils) sans exécutions coûteuses supplémentaires.
Unifier des métriques confuses en une image claire.
Auditer les résultats pour nous assurer que nous ne nous trompons pas nous-mêmes.

Les auteurs soulignent que c'est un outil conditionnel : il ne fonctionne que si la « carte » passe l'audit. Si le comportement de l'agent est trop chaotique pour s'adapter à la carte, le système dit correctement : « Nous ne pouvons pas prédire cela pour le moment », plutôt que de donner un chiffre trompeur.

1. Énoncé du problème

Les agents de modèles de langage (LLM) sont de plus en plus déployés en tant que systèmes logiciels séquentiels qui planifient, appellent des outils, observent les résultats et réessaient. Cependant, leur fiabilité est actuellement évaluée à l'aide de métriques de référence scalaires (par exemple, pass@k, passk et les courbes de déclin de fiabilité ou RDC). Ces métriques souffrent de trois limitations critiques :

Absence d'insight distributionnel : Elles résument les résultats en des nombres uniques sans identifier la distribution sous-jacente du temps de succès.
Absence de test d'adéquation : Elles ne vérifient pas si les traces d'exécution observées soutiennent réellement la distribution supposée.
Ignorance de l'incertitude : Elles ne parviennent pas à quantifier l'incertitude découlant de la longueur finie des traces, rendant difficile la réponse à des questions contrefactuelles (par exemple, « Que se passe-t-il si nous ajoutons un outil de repli ? » ou « Comment la fiabilité change-t-elle avec un budget d'étapes plus large ? »).

Les auteurs soutiennent que la fiabilité des agents LLM doit être traitée comme un problème de premier passage (la rapidité avec laquelle une exécution atteint le succès avant l'échec) avec une incertitude explicite et une validation du modèle, plutôt que comme un taux de réussite terminal.

2. Méthodologie : TRACETOCHAIN

L'article présente TRACETOCHAIN, un pipeline reproductible qui transforme les traces brutes d'exécution d'agents en une Chaîne de Markov Discrète en Temps Absorbante (DTMC) auditée. La méthodologie se compose de quatre étapes principales :

A. Construction d'états (Féaturisation et Clustering)

Entrée : Traces brutes composées d'étapes de raisonnement, d'appels d'outils et d'observations.
Processus :
1. Féaturisation : Les étapes sont mappées à des représentations vectorielles utilisant des caractéristiques basées sur des règles (par exemple, type d'outil, codes d'erreur) ou des encodeurs appris.
2. Clustering : Le lien de Ward agglomératif regroupe ces vecteurs en états transitoires discrets ( $S_T$ ). Le nombre de clusters est sélectionné via le score de silhouette.
3. Mappage des résultats : Les traces se terminent soit par un Succès ( $\oplus$ ) soit par un Échec Fatal ( $\ominus$ ), qui servent d'états absorbants.

B. Estimation des transitions

Modèle : Le système ajuste une DTMC $\hat{M} = (\hat{Q}, \hat{R}^\oplus, \hat{R}^\ominus)$ , où $\hat{Q}$ représente les transitions entre états transitoires, et $\hat{R}^\oplus, \hat{R}^\ominus$ représentent les probabilités de sortie vers le succès ou l'échec.
Estimation : Les paramètres sont estimés à l'aide de l'Estimation du Maximum de Vraisemblance (MLE) lissée par Laplace pour éviter les probabilités nulles pour des transitions non observées mais plausibles.

C. Protocole de test d'adéquation (GoF)

Pour garantir que l'abstraction de Markov est valide, le pipeline emploie un test de diagnostic composite :

Test de Kolmogorov–Smirnov (KS) : Compare la fonction de répartition cumulative (CDF) empirique des temps de premier passage (temps jusqu'au succès) avec la CDF analytique dérivée de la chaîne ajustée.
Critère d'information d'Akaike (AIC) : Compare le modèle de Markov du premier ordre avec une alternative du second ordre pour s'assurer que les exigences de mémoire sont satisfaites.

Décision : La chaîne n'est acceptée que si $p_{KS} > 0.05$ et $\Delta AIC > 0$ . Si elle est rejetée, le corpus de traces doit être segmenté ou re-féaturisé.

D. Quantification de l'incertitude

Le pipeline fournit des intervalles de confiance pour toutes les métriques de fiabilité en utilisant :

Intervalles de posterior Dirichlet : Dérivés du MLE lissé par Laplace pour quantifier l'incertitude des paramètres.
Bootstrap non paramétrique : Rééchantillonnage des traces pour estimer la variabilité de la chaîne ajustée.

3. Contributions clés et cadre théorique

A. Unification des métriques

L'article prouve que pass@k, passk et la courbe de déclin de fiabilité (RDC) ne sont pas des métriques concurrentes mais des projections d'une seule distribution de premier passage au succès :

RDC ( $R(d)$ ) : Probabilité de succès dans un délai de $d$ étapes.
$pass_k$ : Probabilité que $k$ essais indépendants réussissent tous ( $R_\infty^k$ ).
$pass@k$ : Probabilité qu'au moins un des $k$ essais réussisse ( $1 - (1-R_\infty)^k$ ).
Théorème : Ces relations tiennent sous des hypothèses i.i.d. ; les déviations indiquent des corrélations cachées entre les essais.

B. Outils analytiques pour le déploiement

En utilisant la matrice fondamentale $N = (I - \hat{Q})^{-1}$ , les auteurs dérivent des solutions analytiques pour :

Fiabilité de l'horizon : Calculer $R(d)$ pour n'importe quel budget d'étapes sans relancer les références.
Sensibilité aux perturbations : Estimer l'impact de changements locaux (par exemple, ajouter un outil de repli) sur la fiabilité globale en utilisant une analyse de sensibilité du premier ordre.
Limite NHPP : Montrer que dans les régimes de défaillance rare, la chaîne d'agent ajustée converge vers le modèle classique de processus de Poisson non homogène (NHPP) de Goel–Okumoto, faisant le pont entre la fiabilité moderne des agents et la théorie classique de la fiabilité logicielle.

4. Résultats et validation

Les auteurs ont validé TRACETOCHAIN par le biais d'études de simulation et d'études de cas empiriques :

Étude de simulation SS1 (Numérique) : A vérifié que les calculs de fiabilité analytiques correspondent aux simulations de Monte Carlo à travers diverses tailles de chaînes.
Étude de simulation SS7 (Diagnostics GoF) :
- A correctement accepté 100 % des traces générées à partir de chaînes de Markov d'ordre 1 réelles.
- A correctement rejeté 100 % des traces générées à partir de chaînes d'ordre 2 (où la couche AIC a détecté la dépendance).
Étude de simulation SS9 (Validation sur données tenues en réserve) :
- Testé sur 7 cadres de style MAST contrôlés avec une séparation stricte 50/50 ajustation/test.
- Résultats : Les chaînes ajustées ont prédit avec précision les courbes de déclin de fiabilité tenues en réserve.
  - Erreur maximale $L_{RDC}^\infty$ : 0,053 (Médiane : 0,048).
  - Valeurs p du test KS : Tous les cadres ont réussi ( $p > 0.05$ ), avec une valeur p minimale de $p = 0.78$ .
- Cela démontre que le pipeline récupère la distribution sous-jacente du temps de succès sans surajuster les données d'entraînement.
Études de cas empiriques (SS6) : Appliqué à 7 cadres d'agents réels (par exemple, ReAct, Reflexion, ToolFormer). Le pipeline a classé avec succès les cadres par fiabilité asymptotique ( $R_\infty$ ) et visualisé leurs formes RDC spécifiques.

5. Signification et impact

Du scalaire à la structure : Passe l'évaluation des agents LLM de scores scalaires statiques à un modèle de fiabilité dynamique et auditable qui capture le processus d'exécution, et non seulement le résultat.
Fiabilité auditable : Fournit un « certificat » (tests GoF + intervalles d'incertitude) pour les affirmations de fiabilité, abordant la nature « boîte noire » de l'évaluation des agents.
Raisonnement contrefactuel : Permet aux ingénieurs de répondre à des questions « et si » (par exemple, « Comment l'ajout d'un mécanisme de réessai affecte-t-il la fiabilité ? ») en utilisant l'analyse de perturbation sur la chaîne ajustée, évitant ainsi le coût de la réexécution complète des références.
Réconciliation des métriques : Résout la confusion entre différentes métriques de référence en montrant qu'elles sont des projections mathématiquement liées d'une même distribution sous-jacente.
Utilité pratique : Le pipeline est prêt à être utilisé avec des données de traces contrôlées (comme MAST), avec des travaux futurs prévus pour des références complexes comme SWE-bench et $\tau$ -bench une fois que des caractéristiques stables au niveau des étapes seront disponibles.

En résumé, TRACETOCHAIN fournit un cadre rigoureux et mathématiquement fondé pour transformer les traces brutes d'agents LLM en un modèle fiable, diagnostique et prédictif de la dépendabilité du système.