Résumé Technique : TraceGraph – Paysages de Décision Partagés pour le Diagnostic et l'Amélioration des Trajectoires d'Agents

1. Énoncé du Problème

Les benchmarks d'agents actuels enregistrent de plus en plus de trajectoires d'interaction riches et entrelacées (pensées, appels d'outils, retours de l'environnement). Cependant, les pratiques d'évaluation réduisent généralement ces processus complexes à une mesure scalaire unique (par exemple, un taux de réussite/échec ou un score de récompense). Bien que ces scores permettent de classer les systèmes, ils occultent la dynamique sous-jacente du processus : ils ne révèlent pas comment les modèles naviguent dans les espaces de tâches, où ils divergent dans leurs stratégies, ou s'ils évitent les régions d'échec ou s'ils en sortent par la récupération.

Le défi central est l'absence d'un système de coordonnées partagé pour comparer les trajectoires entre différents modèles. Les états des agents sont longs, ramifiés et spécifiques à chaque benchmark, mélangeant choix d'outils, indices de fichiers et preuves partielles. Sans alignement, il est difficile de déterminer si le Modèle A a atteint un état analogue au Modèle B, s'il a évité la même région d'échec, ou s'il a récupéré via une route différente. Les méthodes existantes inspectent souvent les trajectoires individuelles de manière isolée ou reposent sur des scores agrégés qui masquent la diversité des processus.

2. Méthodologie : Le Cadre TraceGraph

TraceGraph est un cadre basé sur les graphes qui transforme les déploiements d'agents regroupés en un paysage de décision partagé. Il opère en trois étapes, construisant une carte agnostique du modèle de l'espace de tâche avant d'analyser les comportements spécifiques des modèles.

Étape 1 : Construction du Paysage Partagé

Le cadre ingère les étapes action-observation de multiples modèles et tâches.

• Encodage : Chaque étape $i$ est encodée comme un ensemble épars de clés observables $K_i$, incluant les types d'outils/actions, les classes de commandes, les motifs d'observation (ex: traces d'erreur), les indices de fichiers et les phases temporelles. Pour les tâches de recherche, des clés spécifiques pour les domaines d'URL et la nouveauté des requêtes sont ajoutées.
• Similitude et Construction du Graphe : La similitude par paire est calculée à l'aide d'un chevauchement de Jaccard pondéré par l'IDF sur les ensembles de clés. Les clés rares et informatives (ex: motifs de traceback spécifiques) pèsent plus lourd que les clés génériques.
• Topologie : Un graphe mutual-$k$NN est construit sur l'ensemble des étapes regroupées. Ce graphe est décomposé en composantes biconnectées (BCC) et points d'articulation (portes).
  • Les BCC regroupent les étapes présentant une similitude mutuelle dense, représentant des états d'agent partagés grossiers.
  • Les points d'articulation marquent les transitions de stratégie ou de phase où un déploiement peut bifurquer vers des continuations qualitativement différentes.
• Agnosticisme du Modèle : L'identité du modèle est exclue de la signature et de la construction du graphe. Le paysage est défini uniquement par l'espace d'état observable.

Étape 2 : Superpositions Informées par les Résultats

Une fois la structure du graphe fixée, le cadre superpose les données de résultats pour identifier les "cœurs productifs" et les "régions de pièges".

• Diffusion de la Récompense : Pour chaque bloc BCC, une récompense lissée par la méthode de Laplace est assignée en fonction des résultats terminaux des déploiements visitant ce bloc. Cette récompense est ensuite diffusée à travers le graphe quotient des blocs pour lisser le bruit local.
• Définition des Régions :
  • Cœur Productif ($C_t$) : Quantiles hautement positifs du champ de récompense diffusé.
  • Régions de Pièges ($B_t$) : Quantiles bas négativement du champ de récompense diffusé.
• Ces superpositions sont descriptives, localisant où le trafic de résultats élevés et bas se concentre, plutôt que de prédire les résultats pour des exécutions non vues.

Étape 3 : Résumé des Événements de Déploiement

La trajectoire de chaque modèle est résumée par trois événements discrets définis sur les superpositions cœur/piège :

1. Accès ($A_r$) : Le déploiement a-t-il intersecté le cœur productif ?
2. Exposition au Piège ($E_r$) : Le déploiement a-t-il intersecté une région de piège ?
3. Réparation ($R_r$) : Le déploiement a-t-il visité un piège et a-t-il par la suite atteint un cœur ?

Analyse : Profils d'Offre et de Demande

TraceGraph génère deux profils descriptifs :

• Offre du Modèle : La moyenne centrée sur la tâche des événements d'un modèle par rapport à la moyenne des modèles. Cela révèle un "style de navigation" (ex: accès élevé/réparation élevée vs navigation conservatrice/superficielle).
• Demande du Benchmark : Le contraste pondéré par la récompense entre le trafic de résultats élevés et bas. Cela révèle ce qu'un benchmark spécifique récompense (ex: évitement de pièges vs récupération).

3. Contributions Clés

1. Cadre TraceGraph : Une méthode pour construire des graphes de tâches agnostiques aux modèles à partir de déploiements regroupés et superposer des régions informées par les résultats pour créer un paysage de décision partagé.
2. Profils de Processus Compacts : Une démonstration que, sur cinq divisions de benchmarks (7 329 enregistrements, 427 tâches, 5 modèles), les événements d'Accès, d'Exposition au Piège et de Réparation séparent les styles de navigation des modèles et les demandes des benchmarks que les scores agrégés réduisent à néant.
3. Pipeline de Récupération Guidé par TraceGraph : Une application pratique sur SWE-bench où les régions de pièges dérivées du graphe servent de déclencheurs au moment de l'exécution. Lorsqu'un agent en direct entre dans une région de piège historique, une politique de récupération légère est activée.

4. Résultats Expérimentaux

Aperçus Diagnostiques

• Diversité des Modèles : Les scores agrégés cachent souvent les différences de processus. Par exemple, sur un paysage partagé, DeepSeek-V3.2 présente un style "accès élevé, réparation élevée", tandis que Qwen3-Next montre un style "accès faible, réparation faible" (navigation conservatrice et superficielle).
• Hétérogénéité des Benchmarks : Les benchmarks imposent des demandes de processus différentes :
  • $\tau^2$-bench, MCPBench, TerminalBench : Fortement averses aux pièges (les résultats élevés sont corrélés à l'évitement des régions à bas résultats).
  • SWE-bench : Fortement exigeants en réparation (les résultats élevés sont corrélés à la récupération de l'état de piège après un échec initial).
  • Recherche : Récompense l'accès à des preuves productives avec une récupération occasionnelle.

Expérience de Récupération (SWE-bench)

Les auteurs ont instancié un pipeline de fork de préfixe conscient des pièges sur des instances SWE-bench Verified (500 au total).

• Mécanisme : Un détecteur se déclenche lorsqu'un déploiement en direct correspond à une signature de piège canonisée. Lors du déclenchement, l'agent continue à partir du même état sous trois politiques :
  1. Baseline : Continuation standard ($T=0.6$).
  2. Hot : Diversité d'échantillonnage accrue ($T=0.9$).
  3. Note : Une note de diagnostic conservatrice, fondée sur les preuves, ajoutée au contexte (sans patchs "gold").
• Résultats :
  • Sur le sous-ensemble par fournisseur déclenché ($n=616$), la meilleure politique groupée (Hot) a augmenté le taux de résolution de 40,4 % à 43,5 % (+3,1 pp, $p=0,016$).
  • Sur le sous-ensemble de déclenchement commun ($n=288$), la politique Hot a augmenté le taux de 41,0 % à 44,8 % (+3,8 pp, $p=0,045$).
  • Spécificité par Fournisseur : La composante de récupération active variait selon le fournisseur. Qwen3.6-35B-A3B a le plus bénéficié de la note de diagnostic, tandis que GLM-5.1 et DeepSeek-V4-Pro ont le plus bénéficié de l'augmentation de la température.

5. Signification et Revendications

Le papier positionne TraceGraph non pas comme un nouveau score scalaire ou un prédicteur aveugle de succès, mais comme un vocabulaire de processus pour l'évaluation des agents.

• Pouvoir Descriptif : Il révèle ce qu'un benchmark teste (ex: évitement vs récupération) et où les modèles divergent sur un paysage partagé.
• Orientation Actionnable : Il démontre que les pièges dérivés de graphes peuvent guider des interventions en aval. En identifiant les régions d'échec historiques, le cadre permet des politiques de récupération ciblées qui améliorent les taux de résolution des tâches sans nécessiter d'informations oracle ou de réentraînement complet.
• Modestie : Les auteurs soulignent que le pipeline de récupération est une intervention locale sur un sous-ensemble spécifique de SWE-bench et ne prétend pas être un mécanisme universel de réparation d'agent. Le cadre est un instrument analytique pour expliquer la concentration du trafic, et non un contrôleur pour tous les comportements d'agents.

En résumé, TraceGraph déplace l'attention de "combien de tâches l'agent a-t-il résolues ?" vers "comment l'agent a-t-il navigué dans le paysage de la tâche, et où s'est-il bloqué ou a-t-il récupéré ?", fournissant une base structurelle pour comprendre et améliorer les trajectoires des agents.