TRACE: Trajectory-robust Admission with Evidence Ordering for Efficient GUI Agents

AI summary

Overview

Research area: Efficient multimodal inference for GUI (graphical user interface) agents — specifically training-free visual token pruning and KV-cache management for multimodal large language models (MLLMs), published under the Computer Vision category (arXiv:2609.10297v1 [cs.CV], 09 Sep 2026) by authors from Dalian University of Technology, OPPO Research Institute, and The Hong Kong Polytechnic University.

Technical level: Advanced. The paper assumes familiarity with transformer KV caching, prefill/decode serving, visual token pruning and merging, orthogonal projection for diversity selection, and GUI agent benchmarks.

Scope: The paper formulates "lifecycle-aware visual pruning" as an irreversible write-time admission decision and proposes TRACE, a training-free framework that commits visual evidence once at admission and contracts it monotonically thereafter across six GUI benchmarks and three model checkpoints.

What This Paper Is About

GUI agents accumulate high-resolution screenshots as a task trajectory unfolds, and each historical screenshot carries many visual tokens that recur across steps, inflating inference latency and memory. Prior training-free token pruning methods assume the selection can be recomputed whenever the query changes, but that premise fails once visual state is cached and reused: tokens discarded at the single write-time prefill cannot be recovered without re-encoding the frame. The paper's goal is a pruning framework that makes one irreversible admission decision per frame that stays useful for unknown future targets while preserving spatial coverage of operable regions under tight token budgets.

Key Contributions

1. A new problem formulation. The paper recasts visual token pruning for GUI agents as write-time visual evidence commitment under trajectory uncertainty, formalizing three constraints: the keep set is decided from information available before the first LLM prefill, the historical keep set must be nested inside the current keep set, and retained positions must remain original (native) tokens so they can later be dropped as cache rows.

2. The TRACE framework (four components). Layout-derived Interaction Prior (LIP) derives a query-independent prior from UI layout detections; Nested Evidence Ordering (NEO) fuses that prior with instruction relevance and feature novelty into one nested order; Native-token Coverage Repair (NCR) restores spatial coverage with native tokens; and Monotone KV Contraction (MKC) contracts retired frames into reusable session state without re-encoding.

3. A nested-order mechanism that costs no accuracy. The paper reports that enforcing a nested token order costs no accuracy relative to independent re-selection, whereas independent re-selection demands re-encoding on most frames.

4. Broad empirical validation. Experiments cover six GUI benchmarks (ScreenSpot-v2, ScreenSpot-Pro, MMBench-GUI L2, OmniGUI, Mind2Web, AndroidControl), two model scales of GUI-Owl-1.5 (8B and 2B), and a cross-family backbone (UI-TARS-1.5-7B). Source code is stated to be released.

Main Findings

• Best overall accuracy at matched budgets on GUI-Owl-1.5-8B. TRACE retains 78.7% and 61.1% of dense performance at the mild (single-step r=10%; multi-step c=50%, h=10%) and tight (single-step r=5%; multi-step c=25%, h=5%) budgets, versus 72.4% (VisionTrim) and 49.2% (VisionTrim) for the next best methods, and 43.5% for the strongest tight-budget baseline PruneSID on the 8B upper bound of 100.0%.

• Single-step gains widen as budgets tighten. At the mild budget TRACE leads PruneSID by 14.94% on ScreenSpot-v2 and VisPruner by 8.12% on MMBench-GUI, while VisionTrim stays ahead by 0.89% on the icon-dense ScreenSpot-Pro. At r=5% TRACE leads on all three benchmarks; its margin over PruneSID on ScreenSpot-v2 grows to 20.99%, and the ScreenSpot-Pro comparison with VisionTrim turns to +2.08%.

• Consistent multi-step advantage. Margins over the best existing method grow from 0.54%–0.74% at the mild budget to 1.30%–3.53% at the tight budget. The largest gap appears on Mind2Web, where TRACE reaches 34.20% and VisPruner reaches 30.67%.

• Cross-scale transfer. On the smaller GUI-Owl-1.5-2B under the tight budget, TRACE retains 52.9% of dense performance on average while the best existing method, PruneSID, retains 43.5%. TRACE ranks first on four of the six benchmarks and second on Mind2Web and AndroidControl, behind FastV and PruneSID.

• Cross-family generalization. On UI-TARS-1.5-7B, TRACE achieves the best performance at both budgets, with margins over DivPrune growing from 0.39%–2.80% (mild) to 0.79%–4.92% (tight), and 17.92% versus DivPrune's 13.00% on tight Mind2Web.

• Every module contributes (GUI-Owl-1.5-8B, ScreenSpot-v2 r=10%). The prior scored by top-k reaches 32.63% and NEO alone 36.48%, while combining the two reaches 56.45% (19.97% higher than either stage alone). Adding NCR raises ScreenSpot-v2 to 73.90% and lifts tight Mind2Web from 27.79% to 34.20%.

• Scoring-factor ablation inside NEO. Removing any single factor degrades all four benchmarked tasks; removing the layout prior costs the most, up to −23.74% on ScreenSpot-v2, followed by −15.57% for instruction relevance and −5.35% for diversity.

• Ordering-rule ablation. Doubling the likelihood weight, using log-mean-exp pooling, or collapsing the query to the mean row costs 3.61%–10.53% on the two grounding benchmarks.

• LIP attribute ablation. Removing any single energy attribute lowers accuracy on both benchmarks; containment and resonance contribute most (−2.91% and −2.28% on ScreenSpot-v2) while entropy contributes least (−0.08%).

• Repair-rule choice differs by frame type. Stride tokens beat feature medoids on the current frame (67.92% versus 58.65% on ScreenSpot-v2; 37.63% versus 30.11% on ScreenSpot-Pro), while the preference reverses on history frames, where stride tokens cost 1.40% on OmniGUI. TRACE therefore uses stride for current frames and medoids for history.

• The layout prior transfers but is not sufficient alone. Grafting the interaction prior onto four existing methods at the tight budget improves every method by +0.16% to +12.11%, yet the best reaches only 34.36%, far below TRACE's 55.19%; the prior used as the selector alone scores just 17.06%.

• Coverage repair rescues targets. NCR reduces uncovered targets on most frames at the same budget, rescuing the target on 44 frames while losing it on only 5. On one ScreenSpot-v2 screen with four instruction targets, the instruction-conditioned keep falls from four covered targets to one, while the repaired keep still retains three of four at r=5%.

• Serving efficiency. On one CUDA-synchronized GPU, TRACE reduces time-to-first-token from 1116.8 ms to 452.7 ms and the visual KV cache from 697 MB to 292 MB — 2.4x faster than dense re-prefill. MKC alone lowers TTFT to 487.4 ms at unchanged accuracy; adding the full selector lowers it to 452.7 ms (mild) and 397.8 ms (tight), cutting the remaining LLM prefill from 328.6 ms to 140.6 ms and 101.9 ms and repaying the 67.4 ms / 47.0 ms selection cost several times over. Porting DivPrune, VisPruner and ZOO-Prune onto the same MKC path improves their TTFT by 1.8–2.0x, yet all three still lag TRACE.

• Window truncation is a poor alternative. Keeping fewer dense frames is non-selective: three recent frames still spend 90% of the dense budget, and one frame still costs 1.66x TRACE's cost.

• Lifecycle compliance differs sharply across baselines. Under the paper's three-constraint contract, FastV fails conditions (i) and (ii) because it scores with LLM self-attention of the live prompt; PruMerge+, TRIM and VisionTrim fail condition (iii) because synthetic tokens cannot later be dropped as cache rows; VisPruner and PruneSID nest only after modification; DivPrune, CDPruner, ZOO-Prune and TRACE satisfy all three under their official rules.

Methodology in Plain English

The researchers start from an operational observation: once screenshots are cached and reused, dropping a visual token at the moment a frame is first encoded is permanent. That reframes pruning as an admission decision that has to be made with only what is known before the first language-model pass — the instruction, the current frame's visual tokens, and the already-admitted history.

To make that decision well, they use four pieces:

1. Layout-derived Interaction Prior (LIP). They run a layout detector (OmniParser) to find UI boxes such as buttons and text fields, compute four per-box attributes — entropy, contrast, containment and resonance — sum them into an interaction energy, divide by the number of UI tokens the box covers to get a density, scatter that density onto the visual-token grid, and turn it into a soft per-token mass that biases selection toward operable regions without making any token ineligible.

2. Nested Evidence Ordering (NEO). Each visual token gets a relevance weight from its similarity to the instruction embeddings (with a z-score and softmax normalization), and features are reweighted by the layout prior. Tokens are then picked one at a time by a greedy rule that trades off relevance against novelty, measured as the squared residual after projecting onto the already-selected set. Because selection is greedy and incremental, every smaller budget is simply a prefix of the same order, which is what lets a retiring frame drop a suffix instead of being re-selected.

3. Native-token Coverage Repair (NCR). A portion of the budget is set aside for spatially spread tokens. For the current frame, coverage tokens are drawn by stride sampling from the complement of the protected prefix; for history, the space is split into near-equal regions and one native "medoid" token (the token minimizing summed squared feature distance to others in its region) is kept per region. Both keep the nested property and use real tokens.

4. Monotone KV Contraction (MKC). Serving proceeds in three phases — prepare, retire, append. When a new screenshot arrives, the previous current frame is cropped to its stored history prefix by indexing alone (no recomputation), and the retained rows are restored in the next merged forward pass together with the new frame's freshly encoded tokens. Only the newest frame is ever encoded.

Evaluation is done on frozen, native GUI agent models with all methods compared at matched visual-token budgets, and the pixel-input detector is run concurrently with the vision encode so that its cost is charged to TRACE's critical path.

Why This Matters

Impact on research. The paper argues that a widely assumed property of visual token pruning — that selections are revisable — does not hold in cached, multi-step serving, and that this changes which selection rules are even admissible. It supplies an explicit three-constraint contract (pre-prefill decision, nested keep sets, index-level native rows) and classifies nine existing pruning and merging methods against it, which gives the field a concrete yardstick for evaluating pruning under reuse rather than only under single-shot inference. It also shows the layout prior is portable, improving four unrelated baselines, while demonstrating that the prior alone is far from sufficient.

Real-world applications:

• Mobile and desktop automation agents that execute long multi-step tasks (booking, form filling, settings navigation) where each screen must be re-read across many steps and latency compounds over the trajectory.
• Remote or cloud-hosted GUI agent serving, where a 697 MB to 292 MB reduction in visual KV cache per session directly raises how many concurrent sessions fit on a GPU.
• Accessibility and assistive agents that continuously perceive a changing interface and must keep small but operable controls (buttons, text fields) inside a tight token budget.
• Robotic process automation and software QA, where agents replay long interface workflows and are sensitive to per-step time-to-first-token in interactive loops.

Industry relevance. The work originates partly from an industrial research institute (OPPO Research Institute), targets a serving-side cost (TTFT and KV-cache memory) rather than an accuracy-only metric, and requires no retraining or architecture change — it operates on frozen checkpoints including a different model family (UI-TARS-1.5-7B). That combination is what makes it practical for deployed GUI agents, where model weights are fixed and cost per interaction is the binding constraint.

Future Directions

• A learned or automatically tuned admission policy. The layout prior's strength is controlled by a coefficient (α) and the coverage doses (ρ_cur, ρ_hist) are chosen per frame type; the paper reports fixed choices rather than an adaptive rule, leaving open whether these could be predicted per screen or per task.
• Reducing dependence on an external layout detector. LIP relies on OmniParser detections; the paper notes the prior alone scores only 17.06% and that gains come from the ordering machinery, which raises the question of whether the layout signal could be obtained more cheaply or from the model itself.
• Extending the lifecycle contract to long-horizon or multi-window tasks. The formulation assumes a monotone retirement of frames into a shrinking prefix; how far this scales in episode length and whether frames should ever be re-admitted is not settled by the reported experiments.
• Closing the remaining accuracy gap to dense inference. Even at the best reported setting, TRACE retains 78.7% of dense performance on GUI-Owl-1.5-8B at the mild budget, so the roughly one-fifth of dense accuracy lost under tight budgets remains an open target — particularly on the small 2B checkpoint, where dense retention is 52.9% at the tight budget.

Target Audience

This paper is most useful to systems and inference-efficiency researchers working on multimodal LLM serving, particularly those handling long visual contexts and KV-cache reuse; to GUI/VLM agent researchers who need to run agents over long screenshot trajectories under latency and memory budgets; and to engineers deploying mobile, desktop or web automation agents who must choose a pruning or compression strategy that is compatible with cached, multi-step serving. Readers without background in attention caches, prefill/decode serving, and visual token pruning will find the method sections demanding.

Authors’ abstract

GUI agents accumulate high-resolution screenshots as the trajectory unfolds, increasing inference latency and memory usage. Training-free visual token pruning can reduce this cost, but cache reuse introduces a fundamental constraint. Once tokens are discarded, the corresponding visual evidence cannot be recovered without re-encoding. Pruning therefore becomes an \textit{irreversible admission decision} that must remain useful for unknown future targets while preserving coverage of operable regions under tight budgets. To address these challenges, we propose \textbf{\method{}}, a training-free framework for \emph{\textbf{T}rajectory-\textbf{r}obust \textbf{A}dmission and \textbf{C}overage-aware \textbf{E}vidence ordering}. Specifically, we combine a query-independent layout-derived interaction prior with instruction relevance and feature novelty to rank visual evidence according to both potential future utility and diversity. Then, we reserve part of the budget for native visual tokens distributed across the screen, repairing missing spatial coverage without breaking the ordering. Together, these mechanisms produce a nested token order, allowing retained visual evidence to shrink monotonically across budgets while remaining reusable throughout the trajectory. Finally, our monotone KV contraction incrementally contracts retired frames into compact session state, avoiding repeated visual encoding or pruning. Extensive experiments across six GUI benchmarks and diverse models verify the effectiveness of our proposed \method{} under tight budgets. The source code will be released.