Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents

1. Declaração do Problema

Agentes de Modelos de Linguagem (LLM) estão sendo cada vez mais implantados como sistemas de software sequenciais que planejam, chamam ferramentas, observam resultados e tentam novamente. No entanto, sua confiabilidade é atualmente avaliada usando métricas de benchmark escalares (por exemplo, pass@k, passk e Curvas de Decaimento de Confiabilidade ou RDC). Essas métricas sofrem de três limitações críticas:

1. Falta de Insight Distribucional: Elas resumem os resultados em números únicos sem identificar a distribuição subjacente de tempo até o sucesso.
2. Sem Ajuste de Bondade (Goodness-of-Fit): Elas não verificam se os traços de execução observados realmente suportam a distribuição assumida.
3. Ignorância da Incerteza: Elas falham em quantificar a incerteza decorrente de comprimentos de traço finitos, tornando difícil responder a perguntas contrafactuais (por exemplo, "O que acontece se adicionarmos uma ferramenta de fallback?" ou "Como a confiabilidade muda com um orçamento de etapas maior?").

Os autores argumentam que a confiabilidade para agentes LLM deve ser tratada como um problema de primeira passagem (quão rápido uma execução atinge o sucesso antes da falha) com incerteza explícita e validação de modelo, em vez de uma taxa de aprovação terminal.

2. Metodologia: TRACETOCHAIN

O artigo introduz o TRACETOCHAIN, um pipeline reproduzível que transforma traços brutos de execução de agentes em uma Cadeia de Markov Discreta Absorvente Auditada (DTMC). A metodologia consiste em quatro etapas principais:

A. Construção de Estados (Featurização e Agrupamento)

• Entrada: Traços brutos consistindo em etapas de raciocínio, chamadas de ferramentas e observações.
• Processo:
  1. Featurização: As etapas são mapeadas para representações vetoriais usando características baseadas em regras (por exemplo, tipo de ferramenta, códigos de erro) ou codificadores aprendidos.
  2. Agrupamento (Clustering): O agrupamento hierárquico de Ward agrupa esses vetores em estados transitórios discretos ($S_T$). O número de agrupamentos é selecionado via pontuação de silhueta.
  3. Mapeamento de Resultados: Os traços terminam em Sucesso ($\oplus$) ou Falha Fatal ($\ominus$), que servem como estados absorventes.

B. Estimativa de Transição

• Modelo: O sistema ajusta uma DTMC $\hat{M} = (\hat{Q}, \hat{R}^\oplus, \hat{R}^\ominus)$, onde $\hat{Q}$ representa transições entre estados transitórios, e $\hat{R}^\oplus, \hat{R}^\ominus$ representam probabilidades de saída para sucesso ou falha.
• Estimação: Os parâmetros são estimados usando Estimação de Máxima Verossimilhança (MLE) com Suavização de Laplace para evitar probabilidades zero para transições não observadas, mas plausíveis.

C. Protocolo de Ajuste de Bondade (GoF)

Para garantir que a abstração de Markov seja válida, o pipeline emprega um teste diagnóstico composto:

1. Teste de Kolmogorov–Smirnov (KS): Compara a função de distribuição acumulada (CDF) empírica dos tempos de primeira passagem (tempo até o sucesso) contra a CDF analítica derivada da cadeia ajustada.
2. Critério de Informação de Akaike (AIC): Compara o modelo de Markov de primeira ordem contra uma alternativa de segunda ordem para garantir que os requisitos de memória sejam atendidos.

• Decisão: A cadeia é aceita apenas se $p_{KS} > 0.05$ e $\Delta AIC > 0$. Se rejeitada, o corpus de traços deve ser segmentado ou re-featurizado.

D. Quantificação de Incerteza

O pipeline fornece intervalos de confiança para todas as métricas de confiabilidade usando:

• Intervalos Posteriores Dirichlet: Derivados da MLE com suavização de Laplace para quantificar a incerteza dos parâmetros.
• Bootstrap Não Paramétrico: Reamostragem de traços para estimar a variabilidade na cadeia ajustada.

3. Contribuições Principais e Estrutura Teórica

A. Unificação de Métricas

O artigo prova que pass@k, passk e a Curva de Decaimento de Confiabilidade (RDC) não são métricas concorrentes, mas projeções de uma única distribuição de primeira passagem para o sucesso:

• RDC ($R(d)$): Probabilidade de sucesso dentro de $d$ etapas.
• $pass_k$: Probabilidade de que $k$ ensaios independentes tenham todos sucesso ($R_\infty^k$).
• $pass@k$: Probabilidade de que pelo menos um de $k$ ensaios tenha sucesso ($1 - (1-R_\infty)^k$).
• Teorema: Essas relações mantêm-se sob suposições i.i.d.; desvios indicam correlações ocultas entre os ensaios.

B. Ferramentas Analíticas para Implantação

Usando a matriz fundamental $N = (I - \hat{Q})^{-1}$, os autores derivam soluções de forma fechada para:

1. Confiabilidade de Horizonte: Cálculo de $R(d)$ para qualquer orçamento de etapas sem reexecutar benchmarks.
2. Sensibilidade a Perturbações: Estimativa do impacto de mudanças locais (por exemplo, adicionar uma ferramenta de fallback) na confiabilidade global usando análise de sensibilidade de primeira ordem.
3. Limite NHPP: Mostrando que, em regimes de falha rara, a cadeia ajustada do agente converge para o modelo clássico de Processo de Poisson Não Homogêneo (NHPP) de Goel–Okumoto, unindo a confiabilidade moderna de agentes com a teoria clássica de confiabilidade de software.

4. Resultados e Validação

Os autores validaram o TRACETOCHAIN através de estudos de simulação e estudos de caso empíricos:

• Estudo de Simulação SS1 (Numérico): Verificou que os cálculos de confiabilidade de forma fechada correspondem às simulações de Monte Carlo em vários tamanhos de cadeia.
• Estudo de Simulação SS7 (Diagnósticos GoF):
  • Aceitou corretamente 100% dos traços gerados a partir de cadeias de Markov de 1ª ordem verdadeiras.
  • Rejeitou corretamente 100% dos traços gerados a partir de cadeias de 2ª ordem (onde a camada AIC detectou a dependência).
• Estudo de Simulação SS9 (Validação em Dados Retidos):
  • Testado em 7 frameworks controlados estilo MAST com uma divisão estrita de 50/50 entre ajuste e teste.
  • Resultados: As cadeias ajustadas previram com precisão as Curvas de Decaimento de Confiabilidade retidas.
    • Erro máximo $L_{RDC}^\infty$: 0.053 (Mediana: 0.048).
    • Valores-p do teste KS: Todos os frameworks passaram ($p > 0.05$), com um valor mínimo $p = 0.78$.
  • Isso demonstra que o pipeline recupera a distribuição subjacente de tempo até o sucesso sem superajuste aos dados de treinamento.
• Estudos de Caso Empíricos (SS6): Aplicado a 7 frameworks de agentes do mundo real (por exemplo, ReAct, Reflexion, ToolFormer). O pipeline classificou com sucesso os frameworks por confiabilidade assintótica ($R_\infty$) e visualizou suas formas específicas de RDC.

5. Significado e Impacto

• Do Escalar para o Estrutural: Move a avaliação de agentes LLM de pontuações escalares estáticas para um modelo de confiabilidade dinâmico e auditável que captura o processo de execução, não apenas o resultado.
• Confiabilidade Auditável: Fornece um "certificado" (testes GoF + intervalos de incerteza) para alegações de confiabilidade, abordando a natureza de "caixa preta" da avaliação de agentes.
• Raciocínio Contrafactual: Permite que engenheiros respondam a perguntas do tipo "e se" (por exemplo, "Como adicionar um mecanismo de nova tentativa afeta a confiabilidade?") usando análise de perturbação na cadeia ajustada, evitando o custo de reexecutar benchmarks completos.
• Reconciliação de Métricas: Resolve a confusão entre diferentes métricas de benchmark ao mostrar que elas são projeções matematicamente ligadas da mesma distribuição subjacente.
• Utilidade Prática: O pipeline está pronto para uso com dados de traços controlados (como MAST), com trabalho futuro planejado para benchmarks complexos como SWE-bench e $\tau$-bench, assim que características estáveis em nível de etapa estiverem disponíveis.

Em resumo, o TRACETOCHAIN fornece um framework rigoroso e matematicamente fundamentado para transformar traços brutos de agentes LLM em um modelo confiável, diagnóstico e preditivo da dependabilidade do sistema.