💻 computer science

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

This paper introduces a novel algorithm that validates autonomous agents' sequential behavior by learning generalized ground truth models from just 2–10 execution traces, leveraging dominator analysis and multimodal large language models to achieve high accuracy in bug detection and explainable validation across diverse domains.

Original authors: Reshabh K Sharma, Gaurav Mittal, Yu Hu

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Reshabh K Sharma, Gaurav Mittal, Yu Hu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a very smart, but slightly chaotic, robot assistant how to make a cup of coffee.

In the old days, if you wanted to check if the robot did the job right, you'd have to write a strict rulebook: "First, grab the mug. Then, press the button. Then, wait exactly 3 seconds. Then, pour." If the robot grabbed the mug, pressed the button, and poured in 2 seconds because the machine was faster that day, your strict rulebook would scream, "ERROR! You didn't wait 3 seconds!" and fail the robot, even though the coffee is perfect.

This is the problem with testing modern AI agents. They are flexible. Sometimes they take a shortcut; sometimes they wait longer. They don't follow the exact same path every time, even when they do the job correctly.

This paper introduces a new way to test these agents that is less like a strict rulebook and more like a smart mentor.

The Core Idea: Learning from "Good Days"

Instead of writing rules, the system asks the agent to perform the task successfully just 2 to 10 times. It watches these "good days" and builds a mental map of what must happen versus what can change.

Think of it like watching a group of friends navigate a city to get to a specific restaurant:

Friend A takes the subway, gets off at the main station, walks through the park, and arrives.
Friend B takes a bus, gets off two blocks away, walks past a bakery, and arrives.
Friend C takes the subway, gets off at the main station, walks through the park, but stops to tie their shoe before arriving.

A strict tester would say, "Friend B failed because they didn't take the subway!" or "Friend C failed because they stopped!"

But this new system is smarter. It looks at all three paths and realizes:

The Essential Stops (The "Dominator" Tree): Everyone must start at home and must end up at the restaurant. These are the non-negotiable checkpoints.
The Optional Stops: The park, the bakery, and the shoe-tying are just variations. They are nice to have, but not required.

How It Works (The Three Steps)

1. The "Photo Album" (Capturing Traces)
The system takes screenshots (or records actions) of the agent doing the task correctly a few times. It turns these into a flowchart, like a "Choose Your Own Adventure" book where every path that worked is recorded.

2. The "Smart Merger" (Finding the Pattern)
This is the magic part. The system uses two tools to figure out what matters:

The Eye (Visual Metrics): It looks at the screenshots. If two screens look 99% identical, it treats them as the same step.
The Brain (LLM Analysis): Sometimes screens look different but mean the same thing (e.g., a window is slightly bigger, or the time on the clock changed). The system asks a powerful AI language model: "Are these differences important, or just cosmetic?" If the AI says, "No, it's just a different font," the system ignores it.

By merging these paths, the system builds a "Dominator Tree." This is a simplified map showing only the critical milestones that every successful attempt passed through. It filters out the noise (like loading screens that appear sometimes but not others).

3. The "Checklist" (Validating New Runs)
When the agent tries the task again, the system doesn't check if it followed the exact same path. Instead, it asks: "Did you hit all the critical milestones in the right order?"

If the agent skipped the "Main Window" and went straight to "Results," the system says, "FAIL." (You missed a critical stop).
If the agent skipped the "Loading Screen" (which is optional), the system says, "PASS." (You got the job done efficiently).

Why This Matters

The paper tested this on a computer agent that had to open a code editor and search for text.

The Old Way (Self-Reporting): The agent would often say, "I did it!" even when it failed, or say, "I failed!" when it actually succeeded, because it got confused by timing issues. It was only about 82% accurate.
The New Way: By using the "Dominator Tree" learned from just 3 successful examples, the system achieved 100% accuracy. It could spot when the agent actually broke the software (a product bug) versus when the agent just stumbled due to a slow internet connection (an agent issue).

The Bottom Line

This paper presents a tool that teaches an AI how to grade itself. Instead of needing thousands of examples or a rigid rulebook, it learns the "skeleton" of a correct task from just a handful of good examples. It understands that while the journey might vary, the destination and the key landmarks must remain the same. This makes testing autonomous agents much more reliable and less prone to false alarms.

Technical Summary: Learning Correct Behavior from Examples for Autonomous Agents

Problem Statement

As autonomous agents (e.g., computer use agents, coding agents) become more sophisticated, validating their sequential behavior presents a significant challenge due to non-determinism. Unlike traditional software, autonomous systems rarely follow the exact same sequence of states and actions between executions. Variations arise from timing differences, environmental factors, and legitimate alternative paths (e.g., a loading screen appearing or disappearing, or different UI paths achieving the same goal).

Existing validation approaches suffer from critical limitations in this context:

Assertion-based testing: Requires manual specification for every check, misses visual state issues, and cannot handle alternative paths.
Record-and-replay: Brittle; fails on minor rendering differences or timing variations.
Visual regression testing: Compares screenshots in isolation without understanding execution flow or semantic meaning.
Machine learning oracles: Require thousands of training examples and lack explainability.

The core problem is distinguishing between acceptable variations (non-essential states) and actual failures (skipped essential states) without manual specification.

Methodology

The paper proposes a novel algorithm that automatically learns a generalized ground-truth model from a small number of passing execution traces (2–10) and validates new executions against this model. The approach consists of three phases:

Phase 1: Capture and Prefix Tree Construction

The system collects execution traces from known-correct runs. Each trace includes sequential state observations (e.g., screenshots for UI agents) and actions (e.g., clicks, keystrokes). These traces are converted into Prefix Tree Acceptors (PTAs), directed graphs where nodes represent observable states and edges represent actions.

Phase 2: Merge and Generalize

This phase merges multiple PTAs to handle non-determinism and identify essential versus optional states.

Multi-Tiered State Equivalence Detection: To determine if different screenshots represent the same logical state, the system uses a three-tiered approach:
- Tier 1 (Visual Metrics): Uses perceptual hashing, Structural Similarity Index (SSIM), and pixel change ratios.
- Tier 2 (Semantic Analysis): If visual metrics are ambiguous, a multimodal Large Language Model (LLM) performs side-by-side comparison to distinguish between semantically meaningful differences (e.g., form errors) and irrelevant ones (e.g., window decorations, timestamps).
- Tier 3 (Smart Merging): Constructs a unified graph capturing branches for alternative paths (e.g., with/without loading screens) and convergence points.
Dominator Extraction: Using dominator analysis from compiler theory, the system identifies states that "dominate" others (i.e., every path from the initial state to a specific state must pass through the dominator). By tracing backward from terminal states to the initial state, the system extracts a dominator tree containing only essential states (e.g., "Main Window," "Search Dialog") while filtering out optional variations (e.g., "Loading Screen").

Phase 3: Validation via Topological Subsequence Matching

When a new test trace arrives, the system checks if its sequence of states contains a topological subsequence matching a path in the learned dominator tree.

Matching Logic: If the reference states are $A \to B \to C \to D$ and the test trace is $A \to X \to B \to Y \to C \to D$ , it is a MATCH because the essential states appear in the correct order, with $X$ and $Y$ treated as allowed extras.
Metrics: The system calculates coverage ( $\frac{\text{matched states}}{\text{total reference states}}$ ) and checks if the terminal state matches.
Output: Results are PASS or FAIL, accompanied by explainable metrics (coverage percentage, missing states) rather than black-box classifications.

Key Contributions

Three-Phase Algorithm: A novel integration of Prefix Tree Acceptors and dominator analysis to automatically identify essential versus optional states from 2–10 example traces.
Multi-Tiered Equivalence Detection: A hybrid system combining visual metrics with multimodal LLM semantic analysis to robustly handle non-deterministic behavior and distinguish functional equivalence from visual noise.
Topological Subsequence Matching: A validation mechanism that verifies execution correctness while tolerating acceptable variations, providing explainable coverage metrics.

Experimental Results

The authors conducted a controlled case study using a synthetic VS Code extension bug detection scenario with 28 agent executions (3 for training, 25 for testing).

Accuracy: The system achieved 100% accuracy in detecting product bugs (11/11), agent issues (3/3), false successes (1/1), and missed bugs (1/1).
Comparison: Compared against a baseline where the Computer Use Agent (CUA) self-reports success/failure, the proposed approach significantly outperformed the baseline:
- Accuracy: 100% vs. 82.2% (+17.8pp).
- Recall: 100% vs. 60.0% (+40.0pp).
- F1-Score: 100% vs. 69.8% (+30.2pp).
Root Cause Analysis: The system demonstrated the ability to distinguish between "agent execution errors" and "product bugs," achieving a 52.2% F1-score in identifying "not a bug" scenarios (where the agent stumbled but the product was fine), whereas the CUA baseline failed to identify these scenarios entirely (0% F1-score).

Significance and Claims

The paper claims that reliable behavioral validation for autonomous agents does not require massive training corpora, brittle exact-match specifications, or manual assertions. By learning from just a few passing traces, the system:

Reduces Setup Cost: Eliminates the need for hundreds or thousands of training examples required by ML-based oracles.
Provides Explainability: Generates interpretable dominator trees and precise coverage metrics, unlike black-box ML classifiers.
Handles Non-Determinism: Successfully tolerates acceptable variations (like loading screens) while enforcing essential structural behavior, addressing a key weakness of record-and-replay and visual regression tools.
Broad Applicability: While demonstrated on UI testing, the authors claim the approach is applicable to coding agents (validating development patterns), robotic process automation (compliance checkpoints), and reinforcement learning (filtering training data).

The authors acknowledge limitations, including the reliance on visual state representation (less effective for backend services), the need for passing traces (cannot learn from failures alone), and the dependency on LLMs for semantic equivalence. However, they posit that this approach offers a practical, low-shot, and interpretable mechanism for ensuring the reliability of autonomous agents in complex production environments.