Resumen Técnico: Autómatas a partir de Trazas de Agentes

Planteamiento del Problema

Los agentes basados en LLM ejecutan tareas complejas de múltiples pasos intercalando el razonamiento con llamadas a herramientas, generando trazas de ejecución que suelen ser largas y no estructuradas. Esta opacidad dificulta la auditoría de seguridad, la depuración y el monitoreo en tiempo de ejecución. Los enfoques existentes para el análisis del comportamiento suelen operar sobre una base por traza, dependen de filtros de solo éxito o requieren la especificación manual de flujos de trabajo. En consecuencia, no logran capturar la topología compartida trans-ejecución que vincula la predicción del siguiente paso con la predicación de fallos. Además, el aprendizaje de autómatas finitos únicamente a partir de ejemplos positivos es teóricamente imposible en el límite (Gold, 1967; Angluin, 1980), y los algoritmos de aprendizaje de autómatas existentes (por ejemplo, RPNI, EDSM) suelen producir espacios de estados masivos y sobreajustados cuando no hay ejemplos negativos disponibles.

El desafío central es recuperar una representación estructural compacta del comportamiento del agente a partir de un corpus de trazas de ejecución utilizando solo ejemplos positivos, permitiendo tanto el modelado predictivo como el monitoreo de seguridad en tiempo de ejecución sin intervención manual.

Metodología

Los autores proponen una construcción determinista y libre de hiperparámetros de un Autómata de Estados Finitos (FSM) a partir de trazas de agentes. El método aprovecha la observación de que los agentes LLM operan dentro de un conjunto limitado de herramientas y acciones, lo que resulta en alfabetos de actividad pequeños (6–42 símbolos) y una fuerte regularidad secuencial.

1. Extracción de Actividad

Las trazas se convierten en secuencias de símbolos de un alfabeto finito $\mathcal{A}$ mediante una función de extracción determinista $\phi$. La función prioriza:

1. Llamadas a herramientas: Extracción del nombre de la función.
2. Etiquetas de acción: Extracción de etiquetas de acción (p. ej., [ACTION]).
3. Extracción de comandos: Extracción del primer token de comando de los bloques de código.
   Si ninguna regla coincide, la actividad por defecto es un tipo de rol-contenido (p. ej., assistant:text).

2. Construcción del FSM

La construcción procede en tres pasos (Algoritmo A.1):

• Árbol de Prefijos: Todas las secuencias de actividad se insertan en un trie. Cada prefijo único representa un estado distinto. Esto produce un ajuste de entrenamiento perfecto pero con un recuento de estados de $O(\sum T_i)$.
• Fusión de Última Actividad: Los estados se fusionan basados en una "congruencia de derecha de la última actividad". Dos estados $q$ y $q'$ se fusionan si la actividad en la arista que entra en ellos es idéntica ($\kappa(q) = \kappa(q')$). Esto reduce el espacio de estados a $|\mathcal{A}| + 1$ estados (uno por actividad más el estado inicial), creando un autómata de directamente-sigue determinista.
• Filtrado de Transiciones Raras: Las transiciones observadas exactamente una vez se eliminan, a menos que sean la única continuación desde su estado de origen. Esto filtra digresiones de una sola vez mientras preserva la topología conductual central.

3. Garantías Teóricas

• Preservación del Ajuste (Fitness): El Teorema 2 demuestra que la operación de fusión preserva el ajuste de entrenamiento; cualquier traza aceptada por el árbol de prefijos es aceptada por el FSM fusionado.
• Determinismo y Compacidad: El Teorema 3 establece que el FSM resultante es determinista con $|\mathcal{A}| + 1$ estados. La construcción es una función determinista del corpus, lo que garantiza la reproducibilidad.
• Convergencia: La Proposición 5 proporciona una garantía de convergencia: dados $N$ trazas, el FSM extraído es igual al autómata de directamente-sigue de la población con alta probabilidad, siempre que las transiciones aparezcan con una frecuencia mínima.

4. Predicción y Monitoreo

• Predicción del Siguiente Paso: Las probabilidades $P(a_t | q_t)$ se estiman a partir de los conteos de transiciones dentro de los estados del FSM, suavizadas mediante Laplace o descuento absoluto.
• Predicción de Fallos: El sistema extrae características por estado (frecuencia de visita, longitud de mensaje, tasas de error) y características de anomalía a nivel de traza (entropía cruzada, sorpresa). Un clasificador de gradiente aumentado utiliza estas características para predecir éxito/fallo.
• Monitor en Tiempo de Ejecución: Un monitor en línea reproduce las trazas a través del FSM, calculando métricas como la "tasa de ciclo" (frecuencia de re-visitar estados). Este activa la detención temprana cuando una traza se desvía estructuralmente de los patrones exitosos (p. ej., entrar en un bucle cerrado), sin requerir un modelo de ML entrenado para la lógica de monitoreo en sí misma.

Resultados Clave

El método fue evaluado en doce conjuntos de datos públicos a través de ocho dominios de agentes (codificación, navegación web, GUI, servicio al cliente, seguridad), con tamaños de alfabeto que oscilan entre 6 y 42 símbolos.

• Compacidad y Ajuste: Los FSMs extraídos son altamente compactos, conteniendo solo de 7 a 43 estados. Logran un ajuste de reproducción de prueba $\ge 0.997$ en todos los conjuntos de datos. Comparado con la línea base RPNI, el método logra ratios de compresión de 15$\times$ a 3,036$\times$ (p. ej., reduciendo 59,510 estados RPNI a 25 estados FSM en SWE-agent).
• Predicción del Siguiente Paso: El contexto del estado del FSM supera al de la Memoria de Flujo de Trabajo de Agente (AWM) en los ocho conjuntos de datos donde AWM fue evaluado, con mejoras en la precisión de top-1 que van desde +0.8pp hasta +25.3pp. Condicionar sobre el estado del FSM reduce la entropía cruzada en 0.155 bits (21%) comparado con el contexto bruto por sí solo.
• Predicción de Fallos: Las características conductuales por estado logran un AUROC de prueba dejada fuera de hasta 0.94 (tau2-bench telecom). El método supera a las líneas base de MLP, GRU y Transformer en 20 de los 21 pares arquitectura-conjunto de datos.
• Eficiencia en Tiempo de Ejecución: La construcción del FSM se completa en 1–110 ms (frente a 7,000–36,000 ms para RPNI). La reproducción por traza toma 0.003–0.015 ms, permitiendo el monitoreo en tiempo real.
• Detención Temprana: El monitor en línea puede clasificar las ejecuciones fallidas por encima de las exitosas en el checkpoint del 25% de la traza (rank-AUROC 0.66) y activar la detención temprana al 32% de la finalización en SWE-agent, ahorrando un 68% del cómputo restante.
• Generalización: Un único FSM construido a partir de trazas de cuatro LLMs diferentes logra un ajuste de 1.000 en cada modelo individualmente, lo que indica que la topología conductual está moldeada más por el entorno de despliegue y las restricciones de las herramientas que por el LLM específico.

Significancia y Reivindicaciones

El artículo afirma que los agentes LLM, a pesar de su aparente complejidad, admiten abstracciones estructurales compactas. La principal significancia radica en proporcionar un primitivo estructural agnóstico al modelo que unifica cuatro tareas distintas —memoria de flujo de trabajo, predicción del siguiente paso, predicción de fallos y monitoreo en tiempo de ejecución— en una única construcción libre de hiperparámetros.

Las reivindicaciones clave incluyen:

1. Primacía Estructural: La topología conductual está moldeada más por el sistema (herramientas, prompts, distribución de tareas) que por el LLM, lo que permite un monitoreo invariante al modelo.
2. Tractabilidad: El alfabeto de actividad acotado de los agentes hace que el problema de aprender de ejemplos positivos sea tratable, produciendo FSMs compactos e interpretables que son estadísticamente informativos.
3. Eficiencia: El método reemplaza cuatro pipelines aprendidos especializados por un único primitivo estructural que opera en milisegundos, lo que lo hace adecuado para el despliegue en auditoría de seguridad y monitoreo en tiempo de ejecución.
4. Interpretabilidad: A diferencia de los HMM o los grandes aprendices de autómatas, los estados en este FSM corresponden directamente a la última actividad, lo que permite la descomposición por estado y un análisis de modo de fallo interpretable (p. ej., identificar que los fallos suelen manifestarse como quedarse atrapado en bucles específicos en lugar de explorar nuevos estados).

Los autores señalan limitaciones, incluyendo que el FSM acepta el cierre de directamente-sigue de las trazas observadas (no el lenguaje generador) y que la función de extracción de actividad requiere un conocimiento mínimo del dominio. Sin embargo, enfatizan que las restricciones estructurales son robustas a través de diversas granularidades de extracción y que el enfoque ofrece un sustrato desplegable para el análisis de seguridad y de comportamiento.