R-WoM: Retrieval-augmented World Model For Computer-use Agents

1 INTRODUCTION

• LLMs’ hallucination tendency and reliance on static parametric knowledge leave a gap in world modeling for complex, multi-turn realistic environments such as computer use.Without grounding, generated procedural steps can appear coherent yet be infeasible in the environment.Source: §1 · p. 1
• LLMs identify immediate state changes and task-relevant transitions, but their accuracy deteriorates in full-procedure planning over longer horizons.The evaluation probes next-state prediction and full-procedure planning alignment for future-state prediction, and milestone transition recognition for reward estimation.Source: §1 · p. 2
• R-WoM grounds LLM simulations in environment-specific tutorials, using query rewriting and LLM reranking to retrieve relevant evidence and listwise reward estimation to rank rollouts relatively.It uses long chain-of-thought reasoning for multi-step simulation rather than computationally expensive iterative policy–world-model rollouts.Source: §1 · p. 2
• 5.6% to 23.4% improvements over competitive baselines on WebArena and OSWorld validate R-WoM, with particular advantages in longer-horizon scenarios.The reported range is the paper’s overall comparison across the two benchmarks.Source: §1 · p. 3

2.1 PROBLEM FORMALIZATION

• A computer-use trajectory consists of a task goal and successive observation, reasoning-thought, and executed-action triples.At each step, the policy produces a thought–action pair conditioned on the goal, current observation, and prior interaction history.Source: §2.1 · p. 3

2.2 WORLD MODEL ROLLOUT

• World models perform k-step lookahead rollouts for candidate actions to estimate potential outcomes and rewards, then select the action with the highest estimated reward.The motivation is that actions in realistic environments can be irreversible or costly to undo, making naive trial-and-error exploration infeasible.Source: §2.2 · p. 3

3.1 NEXT-STATE IDENTIFICATION

• Models exceeded 75% accuracy identifying the true next observation from a current-state/action pair against a lexically similar distractor.Source: §3.1 · p. 4, Table 1 · p. 5

3.2 FULL-PROCEDURE PLANNING ALIGNMENT

• Full-procedure alignment rarely exceeded 65% across models, while retrieval improved performance across all models.Plans were assessed against tutorial-derived procedures using element attributes and operation logic.Source: §3.2 · pp. 4–5, Table 1 · p. 5

3.3 MILESTONE TRANSITION RECOGNITION

• Milestone-transition accuracy was 86.7% for Claude-3.7-Sonnet, 85.7% for Claude-3.5-Sonnet, and 83.7% for Qwen-2.5-VL-72B.The comparison used promising subsequences from successful trajectories and less effective subsequences from failed trajectories.Source: §3.3 · p. 5

3.4 DISCUSSION

• LLMs showed relatively good short-term prediction and local evaluation, but performance deteriorated in long-horizon planning aligned to specific environments.The analysis suggests they may lack robust generalization across dynamic environments and may require external guidance for extended simulations.Source: §3.4 · p. 5

4 R-WOM FRAMEWORK

• R-WoM uses retrieved tutorials to ground world-model simulations during state-transition prediction and reward estimation.The framework was motivated by the probing analysis identifying grounding as a key mechanism for environment alignment.Source: §4.1 · p. 5, §4 · p. 5

4.1 OVERVIEW

• At each step, the policy proposes candidate actions, the world model runs k-step rollouts, and estimated trajectory rewards guide action selection.Source: §4.1 · p. 5, Figure 2 · p. 6

4.2 DESIGN DETAILS

• The retrieval pipeline encodes the task goal, retrieves top-k chunks by cosine similarity, then uses an LLM reranker to form the tutorial evidence set.The knowledge base includes online documents and offline trajectories, which can be synthesized into experience-style tutorials.Source: §4.2 · p. 6
• A LongCoT rollout simulates a candidate’s multi-step trajectory in one reasoning sequence; adaptive branching and deduplication reduce unnecessary rollouts.The policy expands the candidate set when uncertain and prunes semantically equivalent actions before rollouts.Source: §4.2 · p. 7
• List-wise reward estimation ranks candidate trajectories relative to one another to reduce potential bias from absolute reward signals.Source: §4.2 · p. 7

5.1 SETUP

• The evaluation samples 87 of 361 OSWorld tasks and 113 of 301 unique WebArena templates for which tutorials are available.The experiments compare against Vanilla, retrieval-augmented generation (RAG), and WebDreamer baselines.Source: §5.1 · p. 7

5.2 RQ1: END-TO-END PERFORMANCE

• 23.4% (Claude-3.7 on OSWorld) is the largest reported gain over the strongest non-R-WoM baseline.The reported gains are +21.5% on OSWorld and +16.3% on WebArena for Qwen-2.5; +10.8% and +8.0% for Claude-3.5; and +23.4% and +5.6% for Claude-3.7, respectively.Source: Table 2 · p. 8, §5.2 · p. 8

5.3 RQ2: THE ROLE OF TUTORIALS IN GROUNDING WORLD MODELS

• Retrieval recall improves most when query rewriting and reranking are combined, reaching over 85% and 90% recall@5, respectively.The paper describes query rewriting and reranking as complementary: rewriting helps with vague task phrasing, while reranking filters semantically irrelevant candidates.Source: Figure 3 · p. 8, §5.3 · pp. 8–9
• Performance rises monotonically from ungrounded WebDreamer to retrieved-tutorial R-WoM and oracle-tutorial R-WoM as grounding quality improves.The oracle setting uses a manually annotated most-relevant tutorial for each task.Source: Figure 4 · p. 9, §5.3 · p. 9

5.4 RQ3: ABLATION STUDIES OF IMAGINATION HORIZON

• On both benchmarks, R-WoM maintains higher success across horizons, with gains lasting up to horizon three before decreasing.WebDreamer initially gains but plateaus and can decline beyond two steps; the comparison varies horizon from one to four.Source: Figure 5 · p. 9, §5.4 · p. 9

5.5 RQ4: EXTENSION TO SCENARIOS WHERE EXISTING TUTORIALS ARE SCARCE.

• R-WoM consistently improves over other baselines on tutorial-scarce OSWorld tasks using synthesized tutorials from self-play trajectories.The authors use 2,000 open-sourced trajectories to synthesize approximately 1,300 tutorials, with no task overlap between those trajectories and the test tasks.Source: §5.5 · pp. 9–10, Table 3 · p. 10

6.1 COMPUTER-USE AGENT

• Computer-use work includes agent frameworks, native or action-grounding models, and world models that simulate action outcomes or state transitions.WebDreamer uses LLM-simulated outcomes and discrete LLM-judge rewards; later approaches include natural-language state summaries and co-evolving policies and world models.Source: §6.1 · p. 10

6.2 TUTORIAL-USE

• Unlike tutorial-based offline trajectory generation, R-WoM uses tutorials to ground LLM world models at inference time.The cited tutorial-use approaches convert tutorials into demonstrations or generate trajectories using tutorial completion, replay, or interaction.Source: §6.2 · p. 10

• R-WoM incorporates environment-specific tutorial knowledge during imagination rollouts and reward prediction to reduce hallucinations and stale knowledge.The conclusion reports consistent outperformance over competitive baselines in browser-use and computer-use scenarios.Source: §7 · p. 10

• The study uses publicly available OSWorld and WebArena benchmarks, but remains confined to controlled environments.The authors note that retrieval-augmented methods may inherit biases from external sources.Source: §8 · p. 11
• The authors provide the R-WoM algorithm and describe the experimental setup and implementation details.Source: §8 · p. 11

Appendix roadmap

• Appendix A.1–A.3 cover probe design, tutorial collection and retrieval, and R-WoM implementation, including action-space and prompt design.Source: A APPENDIX · p. 14
• Appendix A.4 discusses cost-performance tradeoffs and further cost optimization of R-WoM.Source: A APPENDIX · p. 14
• Appendix A.5 analyzes R-WoM failure cases, and A.6 presents additional ablation results.Source: A APPENDIX · p. 14

Prompt format

• The prompt supplies the previous page state, current action, and two candidate next states, then requests a rationale and an A/B choice.Source: PROMPT FOR NEXT STATE IDENTIFICATION · p. 14

Task 1: Next-state identification

• Next-state identification tests whether the model distinguishes the true immediate observation from a lexically similar distractor using 100 WebArena trajectory samples.Source: PROMPT FOR NEXT STATE IDENTIFICATION · p. 14

Task 2: Full-procedure planning alignment

• Full-procedure planning alignment evaluates generated multi-step plans against tutorial procedures for realistic interface elements, operation sequences, and interaction methods across 40 OSWorld and WebArena samples.Source: PROMPT FOR NEXT STATE IDENTIFICATION · p. 14

PROMPT FOR FULL-PROCEDURE PLANNING ALIGNMENT

• Plans are rejected when tutorial-referenced text, location, sequence, interaction method, or attributes misalign; additional steps beyond tutorial scope are accepted.The prompt frames alignment as checking that referenced operations follow tutorial methodology, while allowing extra operations.Source: PROMPT FOR FULL-PROCEDURE PLANNING… · p. 14

A.2 TUTORIAL PROCESSING

• R-WoM combines WikiHow’s general step-by-step guidance with official environment-specific documentation in a knowledge base of over 30k tutorial chunks.Tutorial availability determines coverage: OSWorld has references for 85 of 361 tasks, and WebArena for 113 of 301 unique templates; one oracle tutorial chunk is annotated per task.Source: §A.2 · pp. 16–17

PROMPT FOR SYNTHESIZING TUTORIALS FROM TRAJECTORIES

• For domains lacking tutorials, R-WoM synthesizes skill-level tutorials from AgentNet trajectories, then groups them by domain and vector similarity for deduplication and merging.The synthesis instructions generalize task details and operations, note blockers, and organize skills into concrete actions.Source: §A.2 · p. 17, PROMPT FOR SYNTHESIZING TUTORIALS FROM… · pp. 17–18

PROMPT FOR CONSOLIDATING TUTORIALS; PROMPT FOR QUERY REWRITING; PROMPT FOR RERANKING

• At inference, reasoning-based retrieval rewrites task queries to anonymize and generalize them, then uses LLM reranking to reduce false negatives from cosine similarity alone.Similar skills are consolidated while preserving alternative methods and the prerequisite/action format.Source: PROMPT FOR CONSOLIDATING TUTORIALS · p. 18, PROMPT FOR QUERY REWRITING · p. 18

A.3 IMPLEMENTATION DETAILS OF R-WOM

• For OSWorld rollouts, R-WoM uses GTA-1-7B to help ground generated actions and supplies the top 5 retrieved document chunks to the LLM context by default.The auxiliary grounding model addresses challenges in direct action-coordinate mapping for Qwen-series models and Claude-3.5-Sonnet.Source: §A.3 · p. 19

PROMPT FOR GENERATING ACTION CANDIDATES (ADAPTIVE BRANCHING); PROMPT FOR DEDUPLICATION

• The action-candidate prompt branches from one candidate on unambiguous progress to multiple diverse candidates when stuck or after failures, while deduplication invokes the world model only for meaningful strategic or target differences.Candidate actions must be valid for the current observation and avoid repeating an action when the interface state is unchanged.Source: PROMPT FOR GENERATING ACTION… · p. 20

PROMPT FOR RETRIEVAL-AUGMENTED FUTURE STATE ROLLOUTS

• Future-state rollouts use tutorials to predict efficient workflow outcomes when the current situation matches standard tutorial operations, otherwise relying on internal world knowledge.The prompt also asks the model to account for visible elements and their states, as well as off-screen affordances revealed by interaction or scrolling.Source: PROMPT FOR RETRIEVAL-AUGMENTED FUTURE… · p. 21

PROMPT FOR RETRIEVAL-AUGMENTED FUTURE STATE ROLLOUTS; PROMPT FOR RETRIEVAL-AUGMENTED REWARD ESTIMATION

• Rollout prompts track cursor, caret, and selection state plus file, network, and OS-dialog changes; reward prompts favor tutorial-aligned action sequences and rank candidates with a rationale.The reward prompt emphasizes tutorial operations, milestones, and conditions relevant to task progress.Source: PROMPT FOR RETRIEVAL-AUGMENTED FUTURE… · p. 21, PROMPT FOR RETRIEVAL-AUGMENTED REWARD… · p. 21

A.4 COST-PERFORMANCE TRADEOFF

• Less than 2% of OSWorld end-to-end latency comes from retrieval, making multi-step generation the main computational bottleneck.Reported retrieval time includes query rewriting and reranking.Source: §A.4 · pp. 21–22, Table 5 · p. 22
• 66.37%: adaptive R-WoM with Claude-4.5-Sonnet gains 12% relative over Vanilla and 10% over RAG, close to full R-WoM at 67.84%.The ablation removes adaptive action branching and action deduplication while retaining most of the performance advantage.Source: §A.4 · p. 22, Table 6 · p. 22

A.5 FAILURE MODE ANALYSIS.

• Retrieval works best for explicit action semantics; on retrieval failures, R-WoM behaves like WebDreamer, with reranker and rollout filters limiting irrelevant tutorials.The reranker assesses semantic relevance, while rollout policy uses retrieved content only when it fits the observation and goal.Source: §A.5 · p. 23, Table 9 · p. 23, Table 10 · p. 23
• Content-modification tasks fail more often than information-seeking or navigation tasks, often because goals are ambiguous or UI manipulation requires precise grounding and multi-step reasoning.The task taxonomy follows Chae et al. (2024); the authors suggest multimodal or more agentic, step-aware retrieval as future directions.Source: §A.5 · pp. 23–24, Table 11 · p. 24

A.6 MORE ABLATION STUDIES

• Full-procedure alignment judgments remain broadly consistent across Claude-3.7-Sonnet, GPT-4.1, and Gemini-2.5-Pro; R-WoM also improves performance with Claude-4-Sonnet and Claude-4.5-Sonnet.The stronger-backbone evaluation uses OSWorld and the same experimental setup as Section 5.1.Source: §A.6 · p. 24, Table 12 · p. 24, Table 13 · p. 24
• Listwise relative reward outperforms absolute reward, while increasing candidate actions from 2 to 3 improves all models; expansion to 5 has diminishing returns for weaker models.The absolute reward variant assigns 0, 0.5, and 1.0 to failure, on-progress, and success, respectively.Source: §A.6 · p. 25, Table 14 · p. 25, Table 15 · p. 25

A.7 USE OF LARGE LANGUAGE MODELS

• LLMs supported manuscript editing and minor boilerplate coding; authors reviewed, modified, and tested all generated outputs.Source: §A.7 · p. 25