Inferring Hidden Agentic Logic from Traces for Online Fault Attribution and Workflow Optimization

Agent execution consists not only of explicit actions at each step, but also of implicit structural shifts in hidden states. Yet the behavioral logic that governs these states and their transitions remains largely opaque. We introduce HALT, a framework for recovering this hidden structure and its cross-run topology from execution traces using hidden Markov models (HMMs). HALT models observable atomic actions as emissions from latent workflow states, while state transitions capture the underlying logical structure of agent behavior. Fitted on historical traces, these HMMs provide a unified view for understanding, evaluating, and improving agents. We evaluate HALT on two downstream applications. For failure attribution, HALT trains separate HMMs on successful and failed traces, and attributes each step by contrasting its likelihood under the two models. This enables real-time, step-level failure localization without requiring access to the complete trace, and naturally supports early stopping. On Who&When, HALT achieves 37.0% step-level attribution accuracy, outperforming a fine-tuned LLM-based attributor that reads the entire trace (32.1%), while requiring no LLM calls and observing only about 27% of the trace. For workflow optimization, existing methods typically rely on manually specified building blocks to construct and refine workflows during search. HALT instead extracts reusable workflow operators from HMMs fitted to historical successful traces, turning latent structural patterns into automatically discovered building blocks for optimization. Workflows found by searching over these HMM-derived operators outperform both hand-designed and automatically searched baselines across all four tasks. On MBPP Pro with GLM-5.1, HALT reaches 86.2%, compared with 73.6% for the best baseline, while also incurring lower total cost. Together, these results position HALT as a lightweight structural primitive for inferring hidden agentic logic from traces and leveraging that structure for both online failure attribution and workflow optimization.