🤖 AI

Executable Agentic Memory for GUI Agent

This paper introduces Executable Agentic Memory (EAM), a structured Knowledge Graph-based framework that replaces fragile, step-wise LLM interactions with a robust retrieval-and-execution process using value-guided graph search, thereby achieving superior performance, lower costs, and reduced latency in long-horizon GUI automation tasks.

Original authors: Zerui Qin, Sheng Yue, Xingyuan Hua, Yongjian Fu, Ju Ren

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zerui Qin, Sheng Yue, Xingyuan Hua, Yongjian Fu, Ju Ren

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

The Problem: The "Amnesiac" Robot

Imagine you hire a robot to help you use your smartphone. Every time the robot looks at a new screen (like opening a settings menu), it has to forget everything it just did, re-read the screen from scratch, and guess what to do next.

This is how most current AI agents work. They are like amnesiac tourists in a giant, confusing city.

They see a street sign (the screen).
They guess which way to go.
They take a step.
Then, they see a new street sign, forget the previous one, and guess again.

If they make a small mistake early on, they get lost. They might wander into a dead-end alley (a wrong app screen) and keep guessing, wasting time and money. This is called a "fragile" system, especially for long tasks like "Turn on Bluetooth, then find a specific photo, then email it."

The Solution: EAM (The "Living Map")

The authors propose a new system called Executable Agentic Memory (EAM). Instead of guessing every step, the robot builds a structured, living map of the phone's interface.

Think of EAM not as a list of text notes, but as a giant, interactive subway map.

The Stations: These are the different screens on your phone.
The Tracks: These are the buttons and actions you can click.
The Connections: The map knows exactly which button leads to which screen.

Once this map is built, the robot doesn't need to "guess" what happens when it clicks a button. It just looks at the map, sees the track, and follows it.

How They Build the Map (Offline Phase)

Before the robot can use the map, someone has to draw it. The paper describes a smart way to do this without wasting time:

The Explorer (DFS): Imagine a very organized explorer sent into the phone's apps. Instead of wandering randomly, they use a "Depth-First Search" strategy. They go down one path as far as it goes, mark the dead ends, and then backtrack to try the next path. This ensures they find every possible route without getting stuck in loops.
The Condenser (Action Group Mining): Sometimes, a task requires clicking five buttons in a row (e.g., "Open Settings" -> "Network" -> "Wi-Fi" -> "Scan"). Doing this one by one is slow. The system looks for these frequent patterns and glues them together into a single "Super Button" (like a subway express train). This makes the map much smaller and faster to navigate.

How the Robot Uses the Map (Online Phase)

When you give the robot a task (e.g., "Turn on Wi-Fi"), it doesn't just guess. It uses a GPS Navigator to find the best route on the map.

The GPS (Q-Model): The robot has a small, smart brain (a lightweight AI model) that acts like a GPS. It looks at the map and says, "If I take this track, there is a 90% chance I reach the goal. If I take that one, there's only a 10% chance."
The Search (MCTS): The robot simulates a few possible routes in its head (like checking Google Maps for traffic) to pick the absolute best path.
The Execution: Once the path is chosen, the robot executes the steps. Because the path comes from a verified map, it is guaranteed to be valid. It won't accidentally click a button that doesn't exist or lead to a broken screen.

Why This is a Big Deal

The paper claims this approach solves three major problems:

Reliability: Because the robot follows a pre-verified map, it doesn't get lost or hallucinate (make things up). It's like following a subway map vs. asking a stranger for directions who might be guessing.
Speed: The robot is much faster. Instead of asking a giant, slow AI (like GPT-4) to think about every single step, it uses a small, fast AI to read the map. The paper says it's 6 times cheaper in terms of computing costs and takes only 2.8 seconds per step.
Long Tasks: It can handle long, complicated tasks without forgetting where it started. The map keeps the whole journey in view.

The Results

The researchers tested this on real-world Android phone tasks.

Success Rate: Their system beat the current best AI models (like UI-TARS-7B) by a significant margin (up to 19.6% better).
Efficiency: It used far fewer computer resources (tokens) than the big cloud-based models.

Summary Analogy

Old Way: A tourist trying to cross a city by asking a different stranger for directions at every single intersection. They get tired, confused, and often end up in the wrong neighborhood.
EAM Way: A tourist with a perfect, pre-drawn subway map and a smart GPS. They know exactly which train to take, which stop to get off at, and they never get lost. They get to their destination quickly, cheaply, and reliably.

The paper concludes that by treating the phone's interface as a structured machine (the map) rather than a series of random images to be guessed, we can make AI agents much more reliable and efficient for long-term automation.

Technical Summary: Executable Agentic Memory for GUI Agent

1. Problem Statement

Modern GUI agents, typically powered by Large Language Models (LLMs), operate under a model-centric, step-wise interaction paradigm. In this paradigm, an LLM must re-interpret the User Interface (UI) and re-decide actions at every screen. This approach is inherently fragile for long-horizon tasks because small perceptual or reasoning errors compound, leading to hallucinated actions and incorrect detours. Furthermore, maintaining task progress within the context window is inefficient, and reliance on repeated generation introduces high latency and token costs.

Existing attempts to improve robustness by injecting external knowledge (e.g., workflow patterns or vector databases) often remain unreliable. These methods typically rely on the LLM's contextual understanding to reason over retrieved text, failing to leverage the inherent structured information of historical trajectories. Consequently, they struggle to reproduce executable paths reliably and incur substantial costs due to repeated step-wise generation and retrieval.

2. Methodology

The paper proposes Executable Agentic Memory (EAM), a framework that shifts GUI planning from free-form generation to a robust retrieval-and-execution process based on a structured Knowledge Graph (KG). The system comprises two main phases:

A. Offline Knowledge Graph Construction

The goal is to build a persistent, structured representation of the environment's interaction logic ( $G = (S, A, E)$ ), where $S$ represents GUI states, $A$ represents actions, and $E$ represents transitions.

Autonomous Exploration: The system employs a task-oriented, state-aware Depth-First Search (DFS) strategy. An MLLM generates candidate sub-goals based on interactable elements (anchors) and evaluates progress (Continue, Backtrack, or Complete). This ensures comprehensive coverage of task-relevant transitions while naturally forming a prefix tree structure.
Transition-Aware Knowledge Mining: Collected trajectories are merged into a Directed Acyclic Graph (DAG). A dual-layer filtering mechanism (embedding similarity followed by Vision-Language Model verification) handles state deduplication. Semantic attributes (page descriptions and action functions) are extracted from state transitions to enrich the graph.
Action Group Mining: To compress multi-step routines, the authors propose a statistical approach inspired by Byte Pair Encoding (BPE). Frequent adjacent action pairs are iteratively merged into new "action group" nodes, transforming the KG from atomic operations into a hierarchy of reusable high-level skills.

B. Online Knowledge-Augmented Reasoning

Given a user instruction, the agent extracts an executable path from the KG using a Value-Guided Monte Carlo Tree Search (MCTS).

Q-Model Guided MCTS: Unlike generative agents that map tokens to the graph, this agent operates directly on the graph topology. A lightweight Q-function model ( $Q_\theta$ ) predicts the probability of task success for state-action pairs. The MCTS algorithm uses this Q-model to initialize node values and guide the search via the UCT criterion, selecting high-reward paths from the constrained action space.
Self-Training Pipeline: The Q-model is refined through an iterative process:
- Initialization: Trained via preference learning on expert trajectories using a Bradley-Terry ranking loss to establish initial action rankings.
- Iterative Refinement: The agent executes MCTS guided by the current Q-model to generate search trees. Target Q-values are computed via bottom-up Bellman backups (averaging over uniform random policies). The model is then updated using binary cross-entropy loss with these soft labels, progressively improving its ability to distinguish promising paths.

3. Theoretical Contributions

The paper provides theoretical guarantees for the proposed framework:

Bias Consistency: The authors establish that the learned Q-model is bias-consistent with the reference value function ( $Q_{\pi_u}$ ) on the critical set of state-actions required for optimal path recovery. The error bound decreases as the number of training samples increases.
Sample Complexity: A finite-sample complexity bound is derived for the MCTS process. The analysis shows that the number of simulations required to recover the optimal path scales polynomially with the horizon and branching factor, and inversely with the squared effective action gap. Crucially, as the Q-model improves (reducing bias), fewer MCTS simulations are needed.

4. Experimental Results

The method was evaluated on three benchmarks: AndroidWorld, MobileMiniWob++, and DroidTask.

Performance: EAM significantly outperforms state-of-the-art baselines. On AndroidWorld, it achieves a 52.6% success rate, surpassing the SOTA UI-TARS-7B (33.0%) by 19.6%. It also outperforms GPT-4o-based frameworks like M3A (40.5%) and achieves comparable results to larger, knowledge-enhanced agents like AppAgentX and GUI-Explorer, despite using a smaller 3B parameter model for path extraction.
Efficiency: EAM reduces token costs by approximately 6× compared to GPT-4o (8.3K tokens vs. 50.8K per step) and achieves an average latency of 2.8 seconds. This efficiency stems from the "plan-then-execute" framework, which requires only a single cloud call to filter the retrieved path, rather than iterative API calls for every step.
Ablation Studies:
- Self-Training: Iterative self-training consistently improves success rates across different model sizes (0.5B to 3B).
- Action Groups: Merging frequent sequences into action groups significantly reduces search complexity and latency.
- Generalization: A Q-model trained on one environment (AndroidWorld) improves performance on unseen environments (DroidTask, MobileMiniWob++), suggesting the model captures transferable GUI navigation patterns.

5. Significance and Claims

The paper claims that EAM represents a paradigm shift for GUI agents by treating the Knowledge Graph not merely as a retrieval source for in-context injection, but as an executable state machine.

Reliability: By grounding decision-making in a structured graph of valid transitions, EAM guarantees that the agent stays on executable paths, mitigating the hallucinations common in free-form generation.
Efficiency: The combination of action group compression and value-guided search allows small models to perform long-horizon tasks with low latency and cost, bridging the reasoning gap between small language models and frontier LLMs.
Scalability: The theoretical guarantees and empirical results suggest that this approach is scalable and robust, offering a viable path toward reliable, real-time GUI automation without the prohibitive costs of current cloud-based, step-wise generation methods.

The authors acknowledge limitations regarding the assumption of a relatively static UI environment, noting that significant app updates may require mechanisms for incremental graph evolution, which remains a direction for future work.