Technical Summary: AQuaUI: Visual Token Reduction for GUI Agents with Adaptive Quadtrees

Problem Statement

Large Multimodal Models (LMMs) have become the backbone for Graphical User Interface (GUI) agents, which interpret high-resolution screenshots to perform tasks. However, processing these screenshots generates a massive number of visual tokens, leading to high computational costs, increased inference latency, and limited context window capacity for conversation history.

Existing solutions face two primary limitations:

1. Training Dependency: Many token reduction methods require retraining the model, limiting their applicability to off-the-shelf agents.
2. Inappropriate Compression: Methods designed for natural images (e.g., attention-based pruning) often fail on GUIs because they ignore the unique spatial structure of GUI screenshots. GUIs exhibit highly non-uniform information density: large regions are often homogeneous (backgrounds, margins), while critical information is concentrated in small, structured areas (text, icons). Treating all tokens as equally important or relying solely on attention maps can discard essential spatial context or fail to exploit the regular layout of UIs.

Methodology: AQuaUI

The paper proposes AQuaUI, a training-free, inference-time framework that reduces visual tokens by exploiting the structural layout of GUI screenshots. The method consists of three core components:

1. Adaptive Quadtree Tokenization

Instead of uniform patching, AQuaUI constructs an adaptive quadtree on the input screenshot to partition the image based on information density.

• Grid Alignment: Since GUI dimensions are not always powers of two, the image is decomposed into a central region (tilable with square chunks) and boundary margins. The quadtree is built independently within each chunk.
• Splitting Criteria: Nodes are recursively split based on a score function $s(n)$. The default criterion is area-weighted grayscale variance ($s(n) = w_n h_n \cdot \text{Var}(\text{grey}(n))$). A node splits if $s(n) > 1000 \cdot \alpha$. This ensures homogeneous regions are represented by large leaves (coarse), while complex regions are divided into smaller cells (fine).
• Token Selection: For each final leaf node, a single representative token is selected (defaulting to the center block of the leaf). This token, along with its original spatial coordinates, is passed to the language model.

2. Conditional Quadtree Refinement

To address temporal consistency in multi-step GUI interactions (where consecutive screenshots are often nearly identical), AQuaUI introduces a heuristic algorithm that conditions the current quadtree on previous screenshots within the same request.

• State Classification: The algorithm classifies the relationship between the current chunk and the previous chunk into three modes:
  • Static: The region is nearly identical (similarity $\ge \tau_{static}$). The previous quadtree partition is reused.
  • Shifted: The region has undergone a scroll or translation. The algorithm searches for a block-level shift $\delta$ that maximizes similarity over the overlapping area. If a valid shift is found, the coarse leaves from the previous frame are translated and reused.
  • Replaced: If neither static nor shifted conditions are met, a new quadtree is constructed from scratch.
• Fine-Grained Preservation: This mechanism ensures that fine-grained details preserved in earlier frames are not accidentally merged away in later frames due to minor shifts, maintaining reasoning continuity.

3. Position Encoding Consistency

A critical technical contribution is the preservation of spatial positions throughout the pipeline. The selected tokens retain their original merged-token coordinates. These coordinates are injected into the model's position encoding mechanisms (e.g., M-RoPE), ensuring the model interprets the sparse tokens in their correct geometric context rather than as a compacted grid.

Key Contributions

1. Training-Free Framework: AQuaUI is a plug-and-play method applicable to any downstream LMM without requiring model retraining.
2. Structural Exploitation: It utilizes adaptive quadtrees to align token reduction with the inherent non-uniform information density and spatial regularity of GUIs, outperforming generic token pruning methods.
3. Temporal Consistency: The conditional quadtree algorithm leverages the continuity between consecutive screenshots to preserve fine-grained partitions across static or mildly shifted states, crucial for multi-step navigation.
4. Implementation: The authors implemented AQuaUI on state-of-the-art models (Qwen2-VL, Qwen3-VL, ShowUI, GUI-Owl, MAI-UI) and validated it across multiple benchmarks.

Experimental Results

The authors evaluated AQuaUI on grounding benchmarks (UI-Vision, ScreenSpot-Pro, ScreenSpot-V2, OSWorld-G, MMBench-GUI) and navigational benchmarks (AndroidControl, AndroidWorld).

• Accuracy-Efficiency Trade-off: AQuaUI consistently achieves better accuracy-latency trade-offs compared to baselines like ShowUI's UI-guided token selection and random token dropping.
  • On Qwen3-VL-32B-Instruct, AQuaUI achieves a 13.22% speedup and reduces visual tokens by 29.52% while retaining 99.06% of the full-token performance.
  • On Qwen2-VL-7B-Instruct, it reduces tokens by ~27% with a smaller accuracy drop (3.29 points) compared to ShowUI (5.95 points).
• Model Scalability: The latency benefits become more pronounced as model size increases. For larger backbones (8B, 32B), the savings in visual token computation outweigh the overhead of the quadtree construction, resulting in net latency gains. Smaller models (2B) show less latency improvement due to the fixed overhead of the reduction logic.
• Ablation Studies:
  • Quadtree vs. Random: Random token dropping causes significant accuracy degradation, confirming that the adaptive structure is essential.
  • Conditional Refinement: Removing the conditional quadtree mechanism leads to a consistent drop in success rates on long-horizon navigation tasks (AndroidWorld), proving its value in maintaining temporal consistency.
  • Score Functions: Variance-based splitting offers more stable performance, while gradient-based splitting allows for higher compression at the cost of stability under aggressive settings.

Significance and Claims

The paper claims that AQuaUI demonstrates that spatial redundancy in GUI screenshots can be effectively exploited at inference time without retraining.

The authors emphasize that efficient GUI perception should not merely focus on which tokens are important (a common focus in natural image compression) but also where the tokens are located. By preserving the spatial layout through adaptive partitioning and conditional refinement, AQuaUI allows GUI agents to operate with significantly fewer tokens while maintaining high fidelity in grounding and navigation tasks. This approach offers a practical path to reducing inference costs and enabling longer interaction histories for GUI agents, particularly on larger, more capable models.