Interpretable Early Termination of Web Navigation Agents via Closed Sequential Pattern Mining

Sergio Talavera, Magdalini EirinakiarXiv 2026 · arXiv

TL;DR

This paper introduces an interpretable method for stopping failing web navigation agents early, saving significant computational costs. By using closed sequential pattern mining (BIDE+), the authors generate a human-readable library of failure signatures that can terminate unrecoverable trajectories with 92% precision, saving over 26% of total tokens.

What Problem Does This Paper Address?

Large Language Model (LLM) agents are increasingly used for complex web tasks, but they are prone to failure. A major issue is that these agents often "fail late"—they get stuck in loops or unrecoverable states early on but continue to execute until they hit a step limit. Because LLM agents typically replay the entire history at every step, token costs grow quadratically with the length of the trace.

While recent research has proposed "early termination" to save costs, these existing methods are often "black boxes" that provide a single numerical score. They don't tell a human operator why the agent was stopped. This lack of transparency makes it difficult to diagnose architectural defects or trust the system in production environments.

Methods

The authors propose a two-phase methodology to make early termination both effective and explainable:

  1. Symbolization: They convert messy, heterogeneous agent traces (reasoning, actions, and environment observations) into discrete symbolic sequences. For example, a step might be encoded as CLICK_BID_SUCCESS__R_VERIFY, indicating a successful click on a specific element type accompanied by "verification" reasoning.
  2. Pattern Mining (BIDE+): They apply the BIDE+ algorithm to the first $K$ steps of labeled training traces to find "closed sequential patterns"—subsequences that appear frequently in failures but rarely in successes.
  3. Failure Taxonomy: The resulting library (32 patterns) is organized into a four-category taxonomy:
  4. Recovery Failures: Unparseable actions and loss of coherence.
  5. Validation Failures: Repeated clicks and re-checking loops.
  6. Navigation Failures: Extended click sequences without task progress.
  7. Context Failures: Excessive repetitive typing or premature stops.
  8. Online Termination: During live execution, the system matches the current trace against this library. If the "coverage score" exceeds a threshold, the run is terminated, and the system provides the specific matching pattern and its category as a justification.

Datasets

The study evaluated the methodology using:

  • MiniWoB++: 1,544 traces collected across 10 medium-difficulty tasks.
  • WebArena: 577 shopping traces used for cross-benchmark transfer analysis.
  • Backbone Models: The traces were generated using three open-weight models: Llama-3.2-3B, Qwen-2.5-7B, and Mistral-7B-Instruct-v0.3.

The authors also introduced a "multi-variant evaluation protocol" to ensure results weren't inflated by "contamination artifacts," such as zero-step crashes or very short successes that make trace length an accidental proxy for failure.

Key Insights and Ideas

  • Interpretability vs. Performance: The authors found a distinct trade-off. While neural models like Bi-LSTMs perform better at longer trace lengths ($K=10$), pattern mining is superior at very early stages ($K=3$). This makes pattern mining ideal for "short-prefix termination," where the goal is to stop a failure before it consumes even 10% of the budget.
  • The "Length" Trap: A key insight was the need for a "Step Count" control. Many failure detection methods appear successful simply because failures tend to be longer than successes. By explicitly removing these artifacts, the authors proved their method extracts actual behavioral signals.
  • Backbone Sensitivity: Failure patterns are not universal. A library mined for one LLM might not work as well for another, as different models have different "failure styles" (e.g., Qwen tends to have long failing traces, while Llama's failures and successes overlap more in length).

Key Results

The BIDE Coverage method proved highly effective for early-stage detection:

  • Early Accuracy: On the "Exclude-errors" configuration, it achieved the highest F1 score (0.717) at $K=3$ compared to seven other methods, including neural and statistical baselines.
  • Token Savings: In a deployment configuration, the system saved 26.3% of total tokens while maintaining 92% precision. This means it rarely killed successful runs (only a 3.2% "Success Kill Rate").
Table 1: Variant C balanced (natural failures vs. successes). BIDE Coverage leads from K=5. Step Count is a length-only control: methods that fail to exceed it are not extracting behavioral signal.
Table 2: Online detection operating points on Exclude-errors at K=5. The boldface row is the recommended operating point: 92% precision, 3.2% impact on successful traces, 26.3% overall token savings.

Limitations and Future Work

  • Generalization: The patterns mined on MiniWoB++ did not transfer perfectly to WebArena, suggesting that "benchmark-native" mining is currently necessary.
  • Human-in-the-loop: While the patterns are structurally interpretable, the authors have not yet conducted a formal user study to see if these explanations actually help human operators fix agents faster.
  • Neural Hybridization: Future work could involve combining the raw power of neural classifiers at long trace lengths with the interpretability of pattern mining at short lengths.

Summary updated

Abstract

Web navigation agents built on open-weight language models fail often and fail late, with most of the tokens spent after the trajectory has become unrecoverable. Recent work has shown that early termination is a viable cost-reduction strategy, but existing approaches produce opaque termination decisions that do not support diagnosis or human oversight. In this work we apply closed sequential pattern mining (BIDE+) to K-step prefixes of agent execution traces to produce a small, human-reviewable failure-signature library that organizes into a four-category failure taxonomy with associated repair recommendations. We use a multi-variant evaluation protocol that explicitly removes contamination artifacts (zero-step crashes and trivially separable single-step successes) so that reported detection accuracy reflects behavioral discrimination rather than trace-length distributions. We evaluate our methodology on 1,544 MiniWoB++ traces collected from three open-weight language models, achieving the best F1 at K=3 on the Exclude-errors configuration across eight methods (0.717), recovering 88% of test-set failures within three steps, and supporting an early-termination policy that saves 26.3% of tokens at 92% precision.
BibTeX
@misc{talavera2026interpretable,
  author = {Sergio Talavera and Magdalini Eirinaki},
  title = {{Interpretable Early Termination of Web Navigation Agents via Closed Sequential Pattern Mining}},
  year = {2026},
  eprint = {2611.04142},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.04142},
}
Figure