- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper introduces GraceBench for evaluating the execution stability of mobile GUI agents. The authors construct UI Transition Graphs (UTGs) through app exploration and manual review, extract task-specific UTG subgraphs containing reference paths and alternative valid routes, and align action-synchronized execution videos with the graphs to diagnose stagnation, deviation, looping, and recovery. The benchmark contains 169 tasks across 10 applications and evaluates 11 models under detailed and concise instructions, yielding 3,718 trajectories. The experiments show that 51.24% of successful trajectories still contain a deviation or loop, and that identical task outcomes and completion rates can correspond to different process metrics. Overall, GraceBench provides graph-aligned video evidence and process-level diagnostics for deviations, loops, and recovery weaknesses, supporting future research on state tracking, loop detection, and recovery policies.
Critical strengths
-
The research question has practical significance. Final success rate alone cannot fully characterize unnecessary actions, repeated loops, or recovery after errors during execution. These behaviors increase interaction costs and may introduce noise into performance measurements and logs collected along the trajectory. Evaluating task outcomes separately from execution process quality is a valuable research direction.
-
The benchmark construction and data collection are substantial, and the associated procedures are described in detail. The paper details app exploration, state normalization, task-subgraph extraction, execution recording, and metric calculation. The tasks and trajectories collected from real applications, together with paired detailed and concise instructions for the same task, provide a resource for analyzing behavior under different execution conditions. The authors also provide substantive human auditing and statistical analyses. Outcome-controlled comparisons, statistical analyses that cluster by task, and cross-task ranking consistency analyses support the view that process metrics contain information beyond final success rate.
Critical weaknesses
-
The measurement validity of the graph reference and stability metrics has not been sufficiently established. Section 3.3 labels steps that leave the task subgraph or enter a state outside the application-level UTG as deviations, and treats a return to the task subgraph as recovery. However, graphs obtained through finite exploration do not cover all valid task paths. Although the authors manually verify the validity of the collected states and transitions, this does not establish that actions outside the graph are necessarily erroneous or unstable. The paper does not quantify what proportion of deviation labels actually correspond to valid routes not captured by the graph, reasonable exploration, or transient environment states, nor whether these cases affect the main metrics and conclusions. The graph sizes and one-hop neighborhood statistics in Appendix D.1 also do not directly establish adequate coverage of valid paths.
This issue also affects the interpretation of metrics such as completion rate (CR). Appendix B defines CR as the fraction of required transitions completed, while Appendix C.1 explicitly distinguishes final-state success from prescribed-path coverage. It therefore remains necessary to clarify how the required transitions are constructed for multi-path tasks and whether CR should be interpreted as task progress or reference-path coverage. If equal CR does not imply equal semantic task progress, the interpretation of outcome-controlled comparisons based on CR matching is also limited.
-
The video-based evaluator is insufficiently specified, and the benefits of its components are not adequately validated. Section 3 outlines synchronized screen recording, video segmentation based on action timestamps, and graph-aligned diagnosis, but details of the video-based evaluation model remain missing. These details determine whether the core evaluation method can be reproduced and audited. The human audit in Appendix E provides meaningful support for reliability, but uses five-frame ordered storyboards and does not directly validate the additional benefit of full video over screenshots. Moreover, the audit excludes 676 GUI-specific model trajectories for which media files are unavailable; whether its reliability findings extend to these records requires further verification. The paper also presents video-grounded evaluation as a core contribution of the benchmark, yet does not directly compare diagnostic performance using pre-action and post-action screenshots, multiple frames, and video, or isolate the respective contributions of the graph reference and video evidence.
Questions for authors
-
Section 4.3 and Appendices C.4-C.5 provide evidence of process differences and associations beyond SR/CR. Despite this, could the authors further use direct comparisons or representative real trajectories to show which specific agent weaknesses GraceBench additionally identifies relative to existing process evaluation methods or simple trajectory statistics, such as the fraction of repeated states or excess steps?
-
The conclusion suggests that these diagnostics can support research on state tracking, loop detection, and recovery policies. Could the authors use a real trajectory example to explain how the behavioral labels help localize a specific system weakness or inform an improvement? Which failure causes can be inferred from the diagnostic evidence, and which require additional evidence?
8 comments
Response to Reviewer X76j [2/4]
W1(a) "Graphs obtained through finite exploration do not cover all valid task paths. Although the authors manually verify the validity of the collected states and transitions, this does not establish that actions outside the graph are necessarily erroneous or unstable."
A: For valid routes not captured by the graph, we clarified the review rules for unmatched states and valid alternative routes, which are detailed in Appendix F and summarized below:
Valid alternative routes.
- Identify routes that leave the task subgraph and follow them until their first return. Keep a candidate only if its first return is to a different, later reference node, both endpoints have unique reference positions, and its action count does not exceed the directed shortest-path distance between them in the task subgraph.
- Review candidates against the task requirements. Reject routes with unexpected side effects or unrelated pages.
- Change
deviationandrecoverylabels toon_pathonly after both checks pass. Skipped reference transitions are not counted as completed.
Unmatched states.
- Match states first to the task subgraph, then to the application-level UI Transition Graphs(UTG).
- Keep the visible state description if no match is found.
- Finally, we use the task goal, constraints, and full trajectory to review unmatched steps ,and label these steps as
on_path,stagnation, ordeviation. An unmatched state alone does not mean deviation.
We have further clarified this in section 3.3 of the revised paper:
- "A step is labeled
deviationwhen it enters or remains in a task-irrelevant branch confirmed by independent validation (Appendix F), or violates task constraints." - "GraceBench uses to identify missing required transitions, persistent deviation, repeated no-progress actions, loops, successful recovery after deviation, and to check the behavior labels of unmatched states. Appendix F gives the corresponding review rules."
W1(b) "The paper does not quantify what proportion of deviation labels actually correspond to valid routes not captured by the graph, reasonable exploration, or transient environment states, nor whether these cases affect the main metrics and conclusions. "
A:
Following your suggestion, we manually audited 226 sampled deviation labels from 100 trajectories against the task requirements and full execution evidence. Only 2.65% were valid routes absent from the subgraph.
| Audit category | Label count (approx.) | Percentage | Interpretation |
|---|---|---|---|
| Unnecessary detours or redundant actions | 179 | 79.20% | Actual deviations; The automatic labels are correct |
| Valid alternative routes | 6 | 2.65% | Valid off-graph routes labeled as deviations |
| Insufficient evidence | 17 | 7.52% | Available evidence does not allow a definitive judgment on whether the flagged actions constitute deviations. |
| Other labeling errors | 24 | 10.62% | Labeling errors during the audit |
| Total | 226 | 100% | Across the 100 sampled trajectories |
Unnecessary detours or redundant actions accounted for 79.20%, valid alternatives wrongly labeled as deviations for 2.65%, insufficient evidence for 7.52% and other labeling errors for 10.62%. These errors do not change our main conclusions.
Response to Reviewer X76j [3/4]
W1(c) "It therefore remains necessary to clarify how the required transitions are constructed for multi-path tasks and whether CR should be interpreted as task progress or reference-path coverage. "
A: We clarified the completion rate (CR) calculation in Appendices A and F.
CR is the fraction of required transitions completed along a valid path in the task subgraph that is compatible with the actual execution. It measures task progress along that path.
We calculate CR as follows:
- Map the execution to the task subgraph and select the transition sequence for the branch taken. Exclude mutually exclusive branches that were not taken.
- Divide the number of completed required transitions by the total required transitions in that sequence.
- If only a common prefix is completed and the execution does not yet distinguish two valid branches, use the average required-transition count of the two compatible complete paths as the denominator.
CR therefore measures normalized completion for the task graph and route. This follows the same basic idea as ColorBench's multi-solution milestone evaluation [1] and Mobile-Agent-v2's operation completion ratio [2]: measuring partial progress through completed task elements. We added the CR calculation procedure to Appendix A and the corresponding rules to Appendix F.
Equal CR does not necessarily mean equal semantic task progress, but CR still measures normalized completion of required transitions. Our ablation shows that runs with the same SR and CR can differ in detours, repeated actions, and recovery after errors. Task completion alone therefore does not capture process stability.
References
[1] Yuanyi Song et al. ColorBench: Benchmarking Mobile Agents with Graph-Structured Framework for Complex Long-Horizon Tasks. arXiv:2510.14621, 2025.
[2] Junyang Wang et al. Mobile-Agent-v2: Mobile Device Operation Assistant with Effective Navigation via Multi-Agent Collaboration. arXiv:2406.01014, 2024.
Response to Reviewer X76j [1/4]
All authors are grateful for your time devoted to reviewing this paper and your constructive suggestions. Please see our detailed responses to your comments and suggestions below.
Q1 "Could the authors further use direct comparisons or representative real trajectories to show which specific agent weaknesses GraceBench additionally identifies relative to existing process evaluation methods or simple trajectory statistics, such as the fraction of repeated states or excess steps?"
A: For the requested real trajectory example, we add a case to Appendix G showing how GraceBench detects unstable behavior that simple trajectory statistics miss and helps localize specific agent weaknesses. See the anonymous execution video.
In this trajectory, the agent completed all required transitions and returned to the task path, but an extra visual effect added during the deviation remained in the final state. Semantic state completion, excess steps, and the fraction of repeated states do not show this side-effect risk. GraceBench flags the risk through its
deviationlabels.Q2 "Could the authors use a real trajectory example to explain how the behavioral labels help localize a specific system weakness or inform an improvement? Which failure causes can be inferred from diagnostic evidence, and which require additional evidence?"
A: In the example above, GraceBench shows where the agent chose the wrong UI entry and introduced a side-effect risk, and whether it later returned to the correct page.
This helps localize problems in UI entry selection and instruction following. The example also reveals incomplete recovery after a deviation introduced a side effect. The labels point to the failing steps; whether the side effect persisted to the final state and whether the recovery was complete still requires a manual check of the execution video.