Learning Correct Behavior from Examples: Validating Sequential Execution in Autonomous Agents

Reshabh K Sharma ♠, Gaurav Mittal ♡, Yu Hu ♡ ♠ University of Washington, Seattle, WA, USA ♡ Microsoft, Redmond, WA, USA [email protected] , [email protected] , [email protected] · 2026

Read Learning Correct Behavior from Examples: Validating Sequential Execution in Autonomous Agents by Reshabh K Sharma ♠, Gaurav Mittal ♡, Yu Hu ♡ ♠ University of Washington, Seattle, WA, USA ♡ Microsoft, Redmond, WA, USA [email protected] , [email protected] , [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03159.txt.

Introduction

Reshabh K Sharma, Gaurav Mittal, and Yu Hu present a way to learn correct agent behavior from just a handful of passing execution traces. Checking long action sequences by hand is slow, exact matching is brittle, and training-based checks need far more examples than teams usually have.

Their algorithm merges two to ten good traces into a general model using prefix trees, multi-level equivalence checks, and compiler-style dominator analysis, with language model help for meaning. New runs are checked by subsequence matching, with coverage scores to explain verdicts. In controlled tests with three traces, it caught real bugs and false successes well.

Catalog record

CREATORReshabh K Sharma ♠, Gaurav Mittal ♡, Yu Hu ♡ ♠ University of Washington, Seattle, WA, USA ♡ Microsoft, Redmond, WA, USA [email protected] , [email protected] , [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.03159

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning Correct Behavior from Examples: Validating Sequential Execution in Autonomous Agents Reshabh K Sharma ♠, Gaurav Mittal ♡, Yu Hu ♡ ♠ University of Washington, Seattle, WA, USA ♡ Microsoft, Redmond, WA, USA [email protected] , [email protected] , [email protected] Abstract As autonomous agents become increasingly sophisticated, validating their sequential behavior presents a significant challenge. Traditional testing approaches require manual specification, exact sequence matching, or thousands of training examples. We present a novel algorithm that automatically learns correct behavior from just 2–10 passing execution traces and validates new executions against this learned model. Our approach combines dominator analysis from compiler theory with multimodal large language model-powered semantic understanding to identify essential states and handle non-deterministic behavior. The system constructs a generalized ground truth model using Prefix Tree Acceptors, merges traces through multi-tiered equivalence detection, and validates new executions via topological subsequence matching. In controlled experiments, our system achieved high accuracy in detecting product bugs and false successes using only 3 training traces. This approach provides explainable validation results with coverage metrics and works across diverse domains including UI testing, code generation, and robotic processes. Validating Sequential Execution in Autonomous Agents 1 Introduction As AI agents become more sophisticated, from computer use agents that interact with user interfaces 17 to coding agents that generate and refactor software 18 , an important question emerges. How do we know if an agent’s behavior is correct? This challenge is particularly acute because autonomous systems rarely follow the exact same sequence of states and actions between executions. Loading screens may appear or disappear based on timing, alternative UI paths can accomplish the same goal, and different but equally valid code solutions can solve the same problem. Traditional testing approaches exhibit limitations in handling these scenarios. Assertion-based testing requires manually writing assertions for every check, validates internal data but misses visual state issues, and cannot handle alternative execution paths 21 . Record-and-replay tools are brittle, failing on minor rendering differences or timing variations 15 . Visual regression testing compares individual screenshots in isolation without understanding execution flow or semantic meaning 29 ; 28 . Machine learning oracles require thousands of training examples and provide no explainability 13 ; 6 . The core problem is non-determinism 33 . Autonomous systems exhibit variations in execution sequences due to timing differences, environmental factors, and legitimate alternative paths. Consider testing a computer use agent that needs to open VS Code and search for text in files. One execution might proceed by opening the Start Menu, typing “VS Code,” launching the application, displaying a loading screen, opening the search dialog, and finally showing results. Another execution might open the Start Menu, type “VS Code,” launch the application, and then proceed directly to the search dialog and results without any loading screen. The loading screen appears or disappears based on timing, but both executions are correct. Traditional testing would either fail the second execution, being too brittle, or miss when truly essential steps are skipped, being too permissive. Consequently, there is a need for a system that can distinguish between acceptable variations and actual failures. 1.1 Our Contribution We present a novel algorithm that automatically constructs a generalized ground truth model from a small number of passing execution traces and validates new executions by checking if they follow the essential structure of this model. Our key contributions are as follows. • A three-phase algorithm combining Prefix Tree Acceptors 2 with dominator analysis 20 to automatically identify essential versus optional states from 2–10 example traces • A multi-tiered state equivalence detection system that combines visual metrics with semantic LLM analysis to handle non-deterministic behavior • Topological subsequence matching that validates execution correctness while tolerating acceptable variations Our approach is broadly applicable to any domain where sequential state transitions need validation, including UI testing, coding agents, robotic automation, and business process validation. 2 Motivating Example Consider a computer use agent that automates the task of opening VS Code and searching for specific text across files. We want to validate that the agent correctly completes this task across multiple executions. 2.1 The Challenge Traditional testing approaches would struggle with this scenario. Exact sequence matching would fail because the loading screen may or may not appear depending on system performance. Manual assertions would require specifying every possible valid path, which is impractical. Pixel-perfect screenshot comparison would fail on minor variations in window decorations or font rendering. 2.2 Our Approach We collect 3–5 passing execution traces where the agent successfully completes the task. Each trace captures sequential screenshots showing the UI state at each step along with actions taken between states such as clicks and keystrokes. For example, traces might show different paths. In Trace 1, the agent opens the Start Menu, types “VS Code,” launches the application, sees a loading screen, reaches the main window, opens the search dialog, and displays results. In Trace 2, the agent follows the same sequence but proceeds directly from launch to the main window without any loading screen. Trace 3 resembles Trace 1, again showing the loading screen before the main window. Our system automatically performs four key operations. First, it merges the traces into a unified graph structure with branches for alternative paths. Second, it identifies that the loading screen is optional because it appears in some traces but not others. Third, it extracts the dominator tree showing essential states: Start Menu, Launch, Main Window, Search Dialog, and Results. Fourth, it validates new executions by checking if they contain these essential states in order. When a new test execution arrives, the system checks whether it follows the essential structure. If the agent skips directly from Launch to Search Dialog without ever showing the Main Window, this would be flagged as a failure because Main Window is an essential state. However, if the Loading Screen is missing, this is acceptable because it has been identified as optional. This example illustrates the core challenge our work addresses. We aim to automatically learn which states are essential versus optional and validate new executions against this learned model without manual specification. 3 Design Our algorithm consists of three phases as shown in Figure 1 . The first phase captures execution traces and constructs Prefix Tree Acceptors. The second phase merges traces and extracts dominator structure. The third phase validates new executions via topological subsequence matching. Figure 1: We illustrate the workings of our algorithm using three passing traces, T1, T2, and T3 (represented as PTAs), which are merged into a graph from which a dominator tree is extracted. The incoming traces I1 and I2 are then checked for a topological match with the dominator tree. 3.1 Phase 1: Capture Execution Traces We begin by collecting 2–10 execution traces from runs that are known to be correct. Each trace contains sequential state observations such as screenshots for UI agents, code snapshots for coding agents, or sensor readings for robotic systems. Additionally, each trace records actions or transitions including clicks, keystrokes, API calls, or other operations between states. We convert each trace into a Prefix Tree Acceptor (PTA) 2 , a directed graph where nodes represent observable states and edges represent actions. The state representation is flexible and domain-dependent, making the approach applicable across diverse domains. For

Read the complete text