Validating agentic behavior when “correct” isn’t deterministic

When “correct” has more than one shape

Traditional testing leans on a premise that starts to wobble the moment autonomous agents enter the picture: correct behavior is repeatable, step for step. For deterministic code, that holds. For agentic systems that browse UIs, operate inside IDEs, or drive containerized environments via “Computer Use,” the same task can complete through any number of valid paths. A loading spinner may appear on one run and vanish on the next; a hotkey might replace a menu click. The outcome is the same, but the execution trace is not.

That variability exposes a real weakness in CI pipelines built on rigid assertions. An agent can succeed at a task while the test still fails, purely because the execution path drifted from a recorded script. This isn’t a failure of the agent—it’s a failure of the validation layer to distinguish incidental noise from critical defects.

The trust gap in agent-driven testing

Consider a GitHub Actions workflow that relies on a Cloud agent to validate real workflows inside a containerized environment. On Tuesday, the build is green. On Wednesday, with no code changes, the same test fails. A network hiccup on the hosted runner delayed a loading screen by a few seconds. The agent adapted, waited, and completed every required action. The pipeline still flagged the run as failed—not because the task wasn’t done, but because the timing no longer matched the assertion script.

That scenario distills into three recurring pain points:

• False negatives: the task succeeded, but the test runner couldn’t tolerate variation.
• Fragile infrastructure: tests fail because of timing, rendering, or environmental noise unrelated to correctness.
• The compliance trap: a correct outcome is flagged as a regression because the agent’s behavior diverged from what the test expected.

Traditional validation tools are built for fixed execution paths. They break down when behavior branches—not because they’re poorly engineered, but because they assume a stable sequence. Four common paradigms illustrate the problem:

• Assertion-based testing demands manually specified checks for every step and can’t accommodate valid alternative paths.
• Record-and-replay tools are highly sensitive to noise; small rendering or timing shifts trigger false failures.
• Visual regression testing compares screenshots in isolation, without understanding the broader execution flow.
• ML oracles are black boxes requiring thousands of training examples, offering no explainability when they flag behavior as incorrect.

They share a structural assumption: correctness is defined by adherence to a specific sequence of observable states. For agentic systems, that assumption no longer holds.

Reframing correctness around essential outcomes

Correct agentic executions don’t need to look identical—they need to share a logical structure. The shift is from “did this specific thing happen?” to “what had to happen for success to be real?”

Take a Computer Use-enabled coding agent searching in VS Code inside a containerized environment. In one run, a loading screen lingers for seconds; in another, the UI renders instantly. A traditional test sees these as different results. A developer sees the loading screen as incidental—it doesn’t change whether the task succeeded. That intuition sorts agent behavior into three categories:

• Essential states: milestones that must occur for success to be real, like reaching the “Search Results” screen.
• Optional variations: incidental states such as spinners or UI decoration that vary with environment.
• Convergent paths: different sequences of actions (hotkey vs. menu) that rejoin at the same outcome.

The distinction between “must-have” and “incidental” has a formal foundation in compiler theory: dominator relationships. In a control-flow graph, node A dominates node B if every path from the start to B passes through A. Applying that analysis to agent execution traces automatically identifies which states are mandatory, which are optional, and where divergent paths converge.

Modeling executions as graphs, not scripts

Linear traces can’t represent branching or convergence. A graph-based structure—the Prefix Tree Acceptor (PTA)—handles both. In this model:

• Nodes are observable states: screenshots for UI agents, code snapshots for development agents.
• Edges are transitions: the clicks, keystrokes, or API calls that move between states.

Branching captures non-deterministic environmental changes like the appearance of a loading screen. Convergence marks where those different paths rejoin, signaling that the agent navigated a variation and returned to the core task flow. This representation stops penalizing agents for taking different paths and starts validating whether they followed a logically sound one.

A structural validation algorithm

A practical validation framework can learn from just 2–10 successful sessions, constructing a ground-truth model that separates valid variations from genuine failures. The workflow has three stages:

1. Capture (PTA Construction): collect successful execution traces and convert them into PTAs, where nodes are observable UI states and edges are actions.
2. Generalize (Semantic Merging): merge multiple traces into a unified graph, using a three-tier equivalence detection framework to decide whether two states are logically the same.
3. Extract the Skeleton (Dominator Analysis): apply dominator analysis to the merged graph to identify essential states—milestones every successful run must pass through—while automatically filtering out optional states like loading spinners.

The approach requires no manual specification and no large-scale model training. Because the resulting model is a graph of actual execution states, decisions are explainable. When validation fails, the algorithm identifies exactly which essential state was missed.

State equivalence: the hard part

Deciding when two screenshots represent the same logical UI state is the core challenge. The framework solves it with a three-tier equivalence detector:

• Visual metrics: fast perceptual hashes and structural similarity (SSIM) catch near-identical states immediately.
• Semantic analysis via LLM: when visual metrics are ambiguous, a multimodal LLM determines if differences are meaningful—ignoring a timestamp change, flagging a missing UI control or a different error message.
• Conservative merging: states are merged only when the model is certain they’re equivalent, letting the graph branch naturally where paths genuinely diverge.

This isn’t naive pixel comparison, nor is it asking an LLM to judge the whole task. The LLM is used sparingly, to resolve specific ambiguities, keeping the framework robust to UI noise while still catching real regressions.

Dominator analysis: isolating what matters

Once traces are merged, dominator analysis extracts the core skeleton of the task. State A dominates state B if every path from start to B must pass through A. A state is essential if it’s a dominator for successful completion. States that dominate nothing—like a loading screen bypassed in faster runs—are correctly flagged as optional variations.

In VS Code experiments, the “Search Dialog” state is a mathematical dominator: it’s impossible to reach results without triggering search first. A loading screen, by contrast, dominates nothing. The algorithm therefore treats it as noise.

Extracting these essential nodes into a dominator subtree produces a ground-truth model—a minimal, explainable definition of correctness. Validation then focuses not on the steps an agent took, but on the critical checkpoints it was required to hit. This “Trust Layer” alerts only when a critical step is missed, not when the environment fluctuates.

Structural validation: from gold traces to live runs

Once a dominator tree is built from reference executions, validating a new trace becomes a structural comparison instead of an exact-match search. A cloud agent that hits all “must-have” milestones is free to navigate the environment or adapt its integrated Computer Use path however it chooses.

The validation algorithm extracts the sequence of states from the incoming execution and checks it against the dominator tree using topological subsequence matching:

• Relative order, not identity: The new trace need not match the reference exactly; essential states merely need to appear in the correct relative order.
• Extra states are noise: If the reference is A → B → C and the agent produces A → X → B → Y → C, the test passes; X and Y are treated as incidental.
• Failure triggers: The test fails only when an essential state is skipped or states appear out of required logical order.

Beyond pass/fail

Output goes further than a binary result, providing a coverage metric and diagnostic reasoning:

• Coverage: The percentage of matched essential states relative to the total number of states in the reference model.
• Failure explanation: A failed trace reports exactly which state was missing — for example, “Failed: State ‘Search Results’ never reached after ‘Search Dialog’.”

That detail turns validation from a black box into a debugging tool developers can use to diagnose both agent and environment issues.

Evaluation: structure beats self-reporting

To test the approach under real conditions, we ran a controlled comparison of the Dominator Tree method against the Computer-Use Agent’s (CUA) own self-assessment. The test scenario was a Copilot Agent custom VS Code extension suite, with executions designed to separate genuine product failures from agent execution errors.

The agent frequently misreported its own failures as successes — often timing out or misreading its internal state. The Dominator Tree achieved perfect differentiation by checking whether essential milestones were reached.

The biggest practical gain shows up in false alarms:

• Self-verification gap: The agent’s internal self-assessment scored 0% F1 at detecting “Not a Bug” scenarios — agents cannot yet grade their own homework reliably in non-deterministic environments.
• Structural advantage: Using state and action equivalence in the dominator model, the Trust Layer scored a 52.2% F1 at identifying when a failure was an agent mistake rather than a product regression.

Structural validation clearly outperforms self-reported success. Moving the source of truth from the agent’s internal logic to an external learned structure cuts manual review time spent on flaky tests and false positives in CI.

Fit into existing workflows

The framework integrates into areas of the development lifecycle where automation reliability matters most:

• GitHub Actions Pipelines: Reducing false negatives from environmental noise — transient loading screens and the like — keeps automated builds from blocking unnecessarily.
• Regression testing: A few verified traces from a stable release create the ground truth model used to validate future updates automatically.
• Agent evaluation: Structural validation measures how often an agent reaches essential milestones, instead of trusting its own reports.
• UI automation: Desktop and web app automation becomes more robust even when UI paths shift slightly between versions.

Because failures point clearly to a missing essential state, developers gain the transparency required to treat autonomous agents as production infrastructure rather than experimental demos.

Current boundaries and next steps

The framework has known limits. It learns from passing examples only, requiring 2–10 successful traces to construct the ground truth model. Semantic equivalence checking depends on multimodal LLM access, adding an external API dependency and latency. And the current implementation validates event ordering but cannot yet flag duration problems — like a loading spinner persisting too long.

Ongoing work addresses those gaps in several directions:

• Temporal and negative constraints: Capturing timing requirements (e.g., “loading must resolve within five seconds”) and learning from failure logs to block known bad paths.
• Hierarchical and multimodal abstraction: Clustering screenshots into high-level concepts like a “Launch Sequence” and incorporating DOM structures, accessibility trees, and network signals.
• Online learning: Recomputing dominators as new runs are validated, refining what counts as essential in real time.

The motivation is straightforward: AI agents are moving from demos to production systems, and validation must become resilient rather than brittle. Rather than having black-box models judge other black-box models, developers need structural guarantees they can inspect and trust. Combining classic compiler theory — dominator analysis — with multimodal AI shows it is possible to learn an explainable, robust definition of success from a handful of examples. That foundation offers efficient learning from passing traces, robustness to non-deterministic behavior, and transparent, actionable failure reporting — the properties needed for autonomous agents to be regarded as trustworthy components in the development workflow.