ScreenSearch: Uncertainty-Aware OS Exploration
Michael Solodko, Justin Wagle
Abstract
Desktop GUI agents operate under partial observability: visually similar screens can correspond to different underlying workflow states, so locally plausible actions can lead to sharply different outcomes. We frame this as a problem of computer/OS state exploration, where effective behavior requires both expanding the reachable frontier and reducing ambiguity before committing. We present ScreenSearch, a system that combines structural screen retrieval and deduplication with an ambiguity-aware PUCT graph-bandit for large-scale desktop exploration. The retrieval layer converts UIA trees into location-aware structural features, indexes related screens through sparse token search and metadata filters, and maintains a shared deduplicated state graph across VM workers. On top of this graph, we define a scalable ambiguity signal based on matched-action outcome dispersion. If similar screens produce different next states under the same action signature, the state should be probed further rather than treated as resolved. We use this signal together with frontier rewards to drive large-scale exploration and replay-start policy evaluation over the shared graph. Across 11 desktop applications, ScreenSearch collects over 1M screenshots and over 30K deduplicated states, yielding large exploration corpora with substantial cross-application and within-application diversity. On a fixed replay-start slice, we observe a clear novelty--ambiguity trade-off: some policies reduce ambiguity quickly while discovering little frontier. Ambiguity reduction alone is therefore not a sufficient exploration objective. Appendix ablations show that stronger proposal priors can materially improve unique-state discovery during corpus building. These results suggest that state identity, proposal quality, and ambiguity-aware search all matter when deciding when to probe and when to commit.
AI Impact Assessments
(1 models)Scientific Impact Assessment: ScreenSearch: Uncertainty-Aware OS Exploration
1. Core Contribution
ScreenSearch addresses a genuine challenge in desktop GUI agent research: partial observability causing perceptual aliasing, where visually similar screens correspond to different underlying workflow states. The paper introduces three interlinked contributions: (1) a structural screen representation and retrieval system based on UIA trees that enables deduplication and near-duplicate detection; (2) a scalable ambiguity score based on matched-action outcome dispersion; and (3) a PUCT graph-bandit exploration policy that balances frontier expansion with ambiguity reduction over a shared deduplicated state graph.
The framing of desktop exploration as requiring both novelty-seeking and disambiguation is conceptually clean and well-motivated. The distinction between "probe" and "commit" actions provides an intuitive lens for understanding when an agent should gather more information versus act decisively.
2. Methodological Rigor
The methodology has several strengths but also notable gaps:
Strengths: The screen representation pipeline is well-engineered, converting UIA trees into location-aware sparse features with bounded Jaccard verification for deduplication. The ambiguity score (Equation 1) with confidence shrinkage is a principled design choice that avoids overconfidence in rarely-visited states. The system architecture supporting distributed VM workers with shared state graphs is practical for large-scale data collection.
Weaknesses: The experimental evaluation is surprisingly thin for the claims made. The core replay-start evaluation (Table 3, Section 9) is based on only three replay-start episodes from a single application (Notepad)—arguably the simplest application in the corpus. This is an extremely narrow evaluation basis for drawing general conclusions about exploration strategies. The paper acknowledges this indirectly by noting results should be read as "evidence" rather than definitive findings, but the gap between the system's ambition (11 applications, 1M+ screenshots) and the evaluation granularity is striking.
The comparison between reactive baselines and the PUCT graph-bandit is also underwhelming: on the reported slice, the PUCT graph-bandit with uniform prior is actually outperformed by reactive GPT-5-mini variants on both frontier and ambiguity metrics. The paper frames this as a "novelty-ambiguity trade-off," but it could equally be interpreted as the PUCT bandit simply being less effective than strong language model priors on this task.
The deduplication threshold (τ=0.93) and other hyperparameters appear to be set without systematic tuning or sensitivity analysis. While Table 1 lists values, there is no ablation on these critical parameters. The pixel-change analysis in Figure 9 provides some reassurance about deduplication quality but doesn't validate whether semantically distinct states are incorrectly merged.
3. Potential Impact
The paper's most tangible contribution is the large-scale exploration corpus itself—over 1M screenshots across 11 desktop applications with 30K+ deduplicated states. If released, this dataset could serve as a foundation for training and evaluating desktop GUI agents, analogous to how web-based datasets have supported web agent research.
The structural retrieval and deduplication pipeline is practically useful and could be adopted by other desktop agent systems needing state tracking. The ambiguity score concept could inform exploration strategies beyond desktop GUIs, potentially applicable to any domain with perceptual aliasing.
However, the impact is limited by the fact that the system is not demonstrated to improve downstream task performance. The paper explicitly avoids claiming that exploration quality translates to better task completion, focusing instead on corpus statistics and exploration diagnostics. This makes the practical value somewhat speculative.
4. Timeliness & Relevance
The paper is timely. Desktop GUI agents are an active research frontier (OSWorld, WebArena), and the community recognizes that exploration and data collection are bottlenecks. The partial observability framing is relevant as agents move from constrained web environments to full OS settings where hidden state is pervasive.
The use of GPT-5 variants (nano, mini) as baselines suggests access to very recent model capabilities, though the paper doesn't deeply analyze how model scale interacts with exploration quality beyond surface-level comparisons.
5. Strengths & Limitations
Key Strengths:
Notable Limitations:
Additional Observations:
The paper reads more as a systems contribution and empirical investigation than as a paper with strong theoretical or algorithmic novelty. The PUCT bandit and intrinsic exploration rewards are fairly standard; the novelty lies in their application to GUI exploration with structural screen retrieval. The writing is clear but the ratio of system description to evaluation depth is imbalanced. The "contribution" of showing that proposal priors matter is somewhat expected rather than surprising.
The corpus-level statistics (Table 2) are informative but the connection between exploration statistics and meaningful agent capabilities remains unexplored. The 1-7% unique screen discovery rate raises questions about exploration efficiency that aren't fully addressed.
Generated May 18, 2026
Comparison History (27)
ScreenSearch addresses a fundamental challenge in GUI agent research—partial observability and state ambiguity—with a novel framework combining structural retrieval, deduplication, and ambiguity-aware exploration (PUCT graph-bandit). Its large-scale methodology (1M+ screenshots, 30K states across 11 apps) and insights about the novelty-ambiguity trade-off provide foundational contributions applicable broadly to autonomous agent research. WebGameBench, while useful as a benchmark for coding agents, is more narrowly scoped as an evaluation suite rather than introducing new algorithmic or conceptual advances. ScreenSearch's methodological depth and broader applicability to OS-level agent systems give it higher potential impact.
ScreenSearch addresses a more broadly impactful problem—GUI agent exploration under partial observability—with a scalable system tested across 11 applications generating over 1M screenshots. It introduces novel concepts (ambiguity-aware PUCT, structural screen deduplication, novelty-ambiguity trade-off) relevant to the rapidly growing field of autonomous desktop agents. Paper 1 tackles an interesting but narrower problem (commitment validation in personalized LLM systems) with a framework that, while rigorous, achieves low availability (0.49-0.60) and very low recall (0.012), limiting practical adoption. Paper 2's infrastructure and insights have broader cross-field applicability.
Paper 2 demonstrates higher potential scientific impact by addressing a critical bottleneck in the rapidly growing field of autonomous GUI agents: state exploration under partial observability. While Paper 1 introduces an innovative hierarchical training method for creative writing, Paper 2's ambiguity-aware PUCT graph-bandit approach solves fundamental methodological challenges in agentic UI navigation. This has massive real-world applications across automation, human-computer interaction, and reinforcement learning. By enabling scalable, uncertainty-aware OS exploration, Paper 2 provides foundational infrastructure that will broadly impact how computer-use agents are trained and deployed.
Paper 1 addresses a critical bottleneck in LLM agents—long-term memory retrieval—by introducing a novel causal inference approach rather than relying on semantic similarity. Its methodology has broad applicability across various LLM tasks, potentially reducing hallucinations and improving reasoning over long horizons. While Paper 2 presents a strong system for GUI agent exploration, Paper 1's foundational contribution to LLM memory mechanics and the introduction of a causally annotated benchmark give it a higher potential for widespread theoretical and practical impact across the AI community.
Paper 2 addresses a fundamental and transformative challenge in Brain-Computer Interfaces (BCI): non-invasive sentence-level EEG-to-text decoding. The integration of RAG and LLMs to decode brain signals has profound potential for assistive technologies and neuroscience. While Paper 1 presents an impressive and practically useful system for GUI agents, bridging human neural signals with language models (Paper 2) represents a deeper scientific breakthrough with broader implications for human-computer interaction, medical applications, and cognitive science.
Paper 1 introduces a highly novel metacognitive approach to multi-agent LLMs, addressing the critical issue of agent overconfidence and hallucination. Its self-assessment and boundary learning mechanisms have broad applicability across any domain utilizing autonomous agents. While Paper 2 presents valuable work in GUI exploration and contributes a large dataset, Paper 1's framework has wider theoretical implications for AI cognitive architectures and demonstrates strong, efficient empirical gains that will likely influence a broader range of AI research.
Paper 2 bridges artificial intelligence, cognitive neuroscience, and human-computer interaction to address the highly timely issue of AI hallucinations. By revealing the neural mechanisms behind human susceptibility to these errors, it offers broad, cross-disciplinary implications for AI safety, interface design, and cognitive science. In contrast, Paper 1 presents a solid but more specialized technical advancement in the narrower subfield of GUI agent navigation and state exploration.
Paper 1 targets a core, timely limitation in RLVR for LLM reasoning—token-level credit assignment and late-stage collapse—with a novel combination of reflection bottlenecks and sparse CIG-based advantage shaping. If validated, it could generalize across many RL-aligned LLM settings (math, science, tool use) and influence training algorithms broadly. Paper 2 is strong and practical for GUI-agent data collection, but its contributions are more system/engineering-specific and likely narrower in cross-field methodological impact than a broadly applicable RL training advance.
NGM presents a training-free, plug-and-play module applicable to any LLM, demonstrating consistent improvements across multiple model sizes and diverse benchmarks including code, knowledge, and multimodal tasks. Its broad applicability to the widely-used LLM ecosystem, simplicity of integration (no training required), and demonstrated gains on established benchmarks give it higher near-term scientific impact. ScreenSearch, while novel in framing GUI exploration as a state-space search problem, addresses a narrower domain (desktop GUI agents) and primarily contributes an exploration corpus and empirical analysis rather than a widely adoptable method.
Paper 1 tackles a critical technical bottleneck in autonomous GUI agents (partial observability) with a novel algorithmic approach (ambiguity-aware PUCT). Its large-scale empirical results and direct applicability to the rapidly growing field of AI agents suggest a higher potential for driving immediate technological advancements and citations compared to the mapping repository presented in Paper 2.
Paper 1 offers a novel, rigorous analysis revealing that reasoning failures in LLMs concentrate on sparse early 'decision tokens,' providing both mechanistic insight and a practical inference-time intervention that recovers reasoning performance with minimal compute. This finding has broad implications for understanding and improving LLMs across the field. Paper 2 addresses an interesting but narrower problem (desktop GUI exploration), with contributions more incremental in nature—combining existing retrieval and bandit techniques. Paper 1's insights are more fundamental, widely applicable, and timely given the centrality of LLM reasoning research.
Paper 1 presents a concrete, technically novel system for a timely and high-impact problem (scalable OS/GUI agent exploration under partial observability), with clear methodological elements (retrieval/dedup state graph, ambiguity signal, PUCT-style graph bandit) and substantial empirical evidence (11 apps, 1M screenshots, 30K states, ablations). It is directly actionable for building agent training corpora and evaluation infrastructure, with likely reuse across HCI, RL, and agentic systems. Paper 2 is broader and potentially influential conceptually, but reads more like a framing monograph with less testable, rigorously validated methodology.
Paper 2 addresses a critical bottleneck in embodied AI by enabling compact, local models to perform complex household reasoning efficiently. Its focus on privacy, compute constraints, and physical real-world grounding offers broader real-world applicability and higher potential robotics impact than the GUI-focused OS exploration presented in Paper 1.
Paper 2 (ScreenSearch) addresses a more timely and broadly impactful problem—autonomous desktop GUI agents operating under partial observability—which connects to the rapidly growing field of LLM-based agents. Its contributions (structural screen retrieval, ambiguity-aware exploration, large-scale corpus building across 11 applications) establish foundational infrastructure and insights for training and evaluating desktop agents. Paper 1, while technically solid, addresses a relatively incremental extension of combinatorial optimization routing problems with a plug-and-play framework. Paper 2's relevance to the AI agent paradigm gives it broader cross-field impact and greater timeliness.
Paper 2 likely has higher scientific impact due to strong methodological rigor (randomized controlled experiment), high timeliness, and broad cross-field relevance (education, labor economics, HCI, AI policy/management). Its core construct (AI Interaction Competence) and evidence on heterogeneous treatment effects plus a mitigating intervention are directly actionable and generalizable to real-world GenAI adoption, affecting many domains. Paper 1 is novel and technically valuable for GUI agent exploration, but its impact is narrower to OS/agent systems research and depends more on downstream uptake and benchmarking standards.
Paper 1 introduces a foundational benchmarking and simulation framework (ShopGym) for e-commerce web agents. In AI research, comprehensive benchmarks and simulation environments (like OpenAI Gym) historically have exceptionally high scientific impact as they become the standard testbeds for evaluating new algorithms. While Paper 2 presents a strong exploration method for OS agents, Paper 1 solves a critical methodological bottleneck (the tradeoff between realism and reproducibility) that will likely anchor future research and attract broad citations across the web agent community.
Paper 2 has higher potential impact due to a clearer systems contribution with immediate real-world applicability to OS/GUI agents: large-scale state exploration under partial observability with deduplication, retrieval, and an ambiguity-aware PUCT search. It reports substantial empirical scale (11 apps, 1M screenshots, 30K states) and introduces an actionable ambiguity signal tied to action-outcome dispersion. Its methods generalize to robotics/HCI/agent benchmarking and are timely given rapidly growing GUI-agent work. Paper 1 is novel and useful for interpretability of LLM deliberation, but impact may be narrower and more sensitive to modeling assumptions.
Paper 2 likely has higher impact due to broader applicability and timeliness: uncertainty-aware exploration for desktop/OS agents addresses a central bottleneck (partial observability and state aliasing) across many real-world automation settings. Its ambiguity signal plus PUCT-style graph bandit and shared deduplicated state graph enables scalable data collection (1M screenshots, 30K states) and a reusable exploration corpus, which can influence agent training/evaluation beyond a single task. Paper 1 is valuable but more incremental (memory management heuristics and calibration) and narrower to long-horizon recall settings.
EmbodiSkill demonstrates stronger scientific impact through its clear, quantifiable performance gains (93.28% task success, outperforming GPT-5.2 by 31.58%) on established benchmarks, offering a practical training-free framework for embodied agent skill evolution. Its distinction between skill-content errors and execution lapses is a novel conceptual contribution with broad applicability. Paper 2 (ScreenSearch) addresses an important exploration problem for desktop GUI agents but presents more preliminary findings focused on data collection and trade-off observations rather than demonstrating clear downstream task performance improvements, limiting its immediate impact.
Paper 1 introduces a formally grounded framework for counterfactual reasoning with event-graph substrates, proving a novel duality theorem and demonstrating strong empirical results on established benchmarks (CLEVRER) plus a new benchmark. It addresses fundamental questions in causal/counterfactual AI with broad applicability across domains. Paper 2, while addressing a practical problem in GUI exploration, is more narrowly scoped to desktop agent exploration and presents primarily empirical/engineering contributions without comparably deep theoretical insights or demonstrated downstream task improvements.