Large language model (LLM)-based agents have emerged as powerful autonomous controllers for digital environments, including mobile interfaces, operating systems, and web browsers. Web navigation, for example, requires handling dynamic content and long sequences of actions, making it particularly challenging. Existing LLM-based agents struggle with long-horizon planning in two main ways. During online execution, they often lose track as new information arrives, lacking a clear and adaptive path toward the final goal. This issue is further exacerbated during reinforcement learning (RL) fine-tuning, where sparse and delayed rewards make it difficult for agents to identify which actions lead to success, preventing them from maintaining coherent reasoning over extended tasks. To address these challenges, we propose two contributions. First, we introduce an agent framework that leverages proprietary models for online planning through subgoal decomposition. Second, we present MiRA (Milestoning your Reinforcement Learning Enhanced Agent), an RL training framework that uses dense, milestone-based reward signals. The real-time planning mechanism improves proprietary models such as Gemini by approximately a 10% absolute increase in success rate (SR) on the WebArena-Lite benchmark. Meanwhile, applying MiRA to the open Gemma3-12B model increases its success rate from 6.4% to 43.0%. This performance surpasses proprietary systems such as GPT-4-Turbo (17.6%) and GPT-4o (13.9%), as well as the previous open-model state of the art, WebRL (38.4%). Overall, our findings demonstrate that combining explicit inference-time planning with milestone-based rewards significantly improves an agent's long-horizon capabilities, paving the way for more robust and general-purpose autonomous systems.
Figures & tables
Figure 1: Overview of the Milestoning the Agents
Category
Hardcoded Rules
Stop at Wrong Page ( Wrong Termination )
The agent called the exit() function or terminated, but the message was judged incorrect by the final benchmark rules.
Get Stuck Midway
The agent failed and exhibited repetition, characterized by identical last N actions or a short action-state sequence repeating M times.
Fail to Make Reasonable Attempt
The agent already reached the right page, but didn’t attempt to exit() OR The agent failed very early, either by an immediate, short exit() call or by clicking a nonsensical, distracting element as its first action.
Others ( System error, etc. )
The agent failed, but did not trigger Rules A, B, or C, indicating a general deviation from the success path.
Table 1: Hardcoded Rules for Failure Mode Classification
Figure 2: Automated Identification of Key Decision Steps. The analyzer compares the agent’s trajectory against task intent and known successful patterns to pinpoint the exact step (e.g., Step 3) where a critical deviation occurred.
Failure Type
Score
Stuck in Midway
10/10
Wrong Termination
10/10
Fail Attempt
8/10
Others
9/10
Table 2: Agreement between automated analyzer and human labels ( N=40 ).
Figure 3: Overview of Failure mode distribution of existing out-of-box models
Figure 4: Validation of graded subgoal agreement. (Left) The ROC curve, using the fraction of completed subgoals si as a score, yields a high AUROC of 0.84. (Right) The Monotonicity Calibration plot shows a strictly increasing probability of success P(y=1∣m) as more subgoals m are completed. Both plots confirm the subgoals are a reliable progress signal.
Figure 5: Dynamic Milestoning Framework for Enhanced LLM Agent Inference. The architecture depicts the real-time feedback loop where the online agent’s actions are monitored against a SubGoals Checklist . The reasoning model itself uses trace reflection to determine progress ( zt+1 ), providing a dense, grounded signal that directs the agent’s next planning step and enables self-correction.
Figure 6: The MiRA-RL Training Pipeline. During the interaction phase, the agent generates trajectories—such as the successful “Add a bicycle” task or the failed “Find recent orders” task. These are evaluated by an Auto Rater (binary final success) and a SubGoal Checker (intermediate progress). This data trains two distinct critics: a Value Critic Vϕ for final success and a Potential Critic Pψ that models progress. The Actor policy is updated using shaped rewards, with updates stabilized by Actor Perplexity Filtering.
Figure 7: Potential-Based Reward Shaping. (Left) A comparison of supervision signals: (A) Imitation learning focuses on exact step matching; (B) Outcome Reward Models (ORM) provide sparse feedback only at termination; (C) MiRA utilizes Shaped Rewards via a learned potential function. (Right) An execution trajectory for a successful task “Clone best GAN repo”. The predicted progress score ψ (green curve) increases monotonically as the agent completes subgoals (e.g., “Click Clone Btn”, “Click SSH Option”). This generates a dense Δψ reward at every timestep t .
Figure 8: Online Curriculum Training Pipeline for Patching the Model. The framework alternates between offline RL training and online environment interaction . Failed trajectories are analyzed to generate harder task distributions for subsequent phases.
Models
#Params
Reddit
Gitlab
CMS
Map
OSS
Avg. SR
Proprietary LLMs
GPT-4-Turbo
N/A
10.5
16.7
14.3
36.7
13.3
17.6
GPT-4o
N/A
10.5
10.0
20.0
20.0
11.1
13.9
Gemini-2.5-flash
N/A
21.1
33.3
14.3
11.5
24.4
20.6
Gemini-2.5-pro
N/A
31.6
30.0
34.3
15.4
13.3
23.0
Gemini-2.5-pro-SGO (ours)
N/A
26.3
50.0
37.1
23.1
28.9
32.1
Table 3: Task Success Rate (SR) Comparison (WebArena-Lite). Comparison of our models (Gemini-SGO and Gemma3 + MiRA) against proprietary and open-sourced baselines. Our models demonstrate superior performance in their respective categories. We report Pass@1 here to emphasize immediate task completion capability.
Failure Mode
Gemini 2.5 Flash
Gemini 2.5 Pro
Gemini 2.5 SGO
Stuck Midway
45.12
48.41
39.87
Wrong Termination
10.98
9.52
12.03
Fail Attempt
12.20
6.35
6.96
Others
10.37
11.11
8.86
Table 4: Failure distribution ratio in all traces (%) across Gemini model variants. The SGO framework significantly reduces navigation stalls compared to the base models.
Figure 9: Showcase of Introspective planning of the Gemini-SGO-based Web Agent.
Figure 10: Multi-Phase and Domain-Level Success Rate Trends. The left panel tracks the overall training progress over curriculum phases, while the right panel breaks down SR improvements per website domain. MiRA demonstrates stable, cumulative gains and broader generalization across domains. Results are averaged from 5 runs.
Figure 11: Robustness and Component Analysis. (a) MiRA consistently outperforms the baseline across all sample budgets ( k ). (b) Ablation results confirm that removing key components degrades success rates toward the SFT baseline ( ≈31% ), validating the necessity of the full MiRA framework.
Figure 12: Subgoal Completion Pattern. Average subgoal completion probabilities across time steps for consecutive training rounds (Phase 0 → Phase 1 → Phase 6). Phase 0 shows stagnation at Subgoal 1, while Phase 6 exhibits a diagonal gradient, indicating that the agent has learned to sequentially chain subgoals over the episode horizon.
Figure 13: Shift in Failure Distribution Post-Training. Comparison of failure modes across Base, SFT, and RL-tuned models. MiRA (dark red) significantly reduces the “Stuck Midway” error rate compared to SFT and standard WebRL baselines, indicating that the potential-based curriculum successfully helps the agent break out of local optima and navigation loops.
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 14: Overall Success Rate on WA-Lite and Inference Time vs. Thinking Budget. The ‘‘Auto (Dynamic) Thinking’’ mode from Gemini agent outperforms most static budgets, while static budgets show a clear trade-off between accuracy and rising inference time. 6 6 6 The inference times reported here are calculated from the averaged step-wise interactions across 25 identical tasks run at each budget level.
Website
User Intent
Generated Subgoals
Reddit
Ask for product recommendations for running shoes within a budget of $100 in r/sports
1. Navigate to the “r/sports” subreddit. 2. Initiate the creation of a new post. 3. Write a title and body asking for shoes under $100. 4. Submit the post.
Like all submissions created by CameronKelsey in subreddit earthporn
1. Navigate to the subreddit ‘earthporn’. 2. Search for posts by user ‘CameronKelsey’. 3. Click the ‘like‘ button on the first post. 4. Repeat for all other visible posts.
Gitlab
Create a new public project “awesome-llms” and add primer, convexegg, abishek as members
1. Navigate to new project creation page. 2. Enter “awesome-llms”, set visibility to public. 3. Finalize project creation. 4. Add primer, convexegg, and abishek in members page.
Display issues in kkroening and ffmpeg-python with labels related to questions
1. Navigate to kkroening/ffmpeg-python repo. 2. Go to the “Issues” tab. 3. Open “Labels” filter menu. 4. Select label related to “questions”.
Shopping Admin (CMS)
Tell me the grand total of invoice 000000002
1. Navigate to sales/invoices section. 2. Search for invoice 000000002. 3. Open details for the invoice. 4. Identify grand total amount.
Tell me the status of my latest order and when will it arrive
1. Navigate to “My Account” or “Profile”. 2. Go to “Orders” or “Order History”. 3. Identify most recent order. 4. Extract status and estimated arrival date.
Appendix
Table 5: Examples of generated subgoals. See Figure 5 for online usage.
Method
Hyperparameter
Value
SFT
learning rate
1×10−5
lr scheduler type
cosine
warmup ratio
0.1
batch size
128
training epoch
1
cutoff length
16384
Appendix
Table 6: Hyperparameters used in baseline methods.
Figure 15: The input and output format of MiRA and baselines, where the input is composed of task instruction (in green), action history (in blue), and HTML of the current webpage (in orange). The output (in red) is the action taken on the current webpage.
Figure 16: The simplified system prompt employed in baseline agents.
Figure 17: The system prompt used for the Outcome Reward Model (ORM) to verify trajectory success.
Figure 18: The standard system prompt (Set-of-Marks Style) used for large proprietary models (e.g., GPT-4, Gemini) in WebArena, utilizing a text-based accessibility tree observation space.
Figure 19: The multimodal prompt used to decompose tasks into four structured subgoals (Taking fixed 4 subgoals in total as example) via Gemini-2.5-pro. Prompt and examples used are optimized based on our discussions in section 5.1 .
α
0.0
0.1
0.3
0.5
0.8
SR (%)
30.9
31.5
36.4
28.5
25.5
Appendix
Table 7: Impact of reward shaping factor α .
Rank Score ( 1/PPL )
(0.9,1.0]
[0.5,0.9]
[0.0,0.5)
[0.0,1.0]
PPL Range
[1,0.91)
[0.91,0.51]
(0.51,∞)
Full Range
SR (%)
27.9
36.4
23.6
29.1
Appendix
Table 8: Impact of replay buffer filtering based on perplexity (PPL) and rank score ( 1/PPL ).
Large language model (LLM) agents have recently demonstrated strong capabilities in interactive decision-making, yet they remain fundamentally limited in long-horizon tasks that require structured planning and reliable execution. Existing approaches predominantly rely on flat autoregressive policies, where high-level reasoning and low-level actions are generated within a single token sequence, leading to inefficient exploration and severe error propagation over extended trajectories. In this work, we propose HiMAC, a hierarchical agentic RL framework that explicitly decomposes long-horizon decision-making into macro-level planning and micro-level execution. HiMAC models reasoning as a structured blueprint generation process followed by goal-conditioned action execution, enabling robust long-horizon planning within LLM-based agents. To train this hierarchy efficiently, we introduce a critic-free hierarchical policy optimization paradigm that extends group-based reinforcement learning to bi-level structures through hierarchical relative advantage estimation. Furthermore, we propose an iterative co-evolution training strategy that alternates between planner exploration and executor adaptation, mitigating the non-stationarity inherent in hierarchical learning. Extensive experiments on ALFWorld, WebShop, and Sokoban demonstrate that HiMAC consistently outperforms strong prompting and reinforcement learning baselines, achieving state-of-the-art performance and substantially improved sample efficiency across both text-based and visually grounded environments. Our results show that introducing structured hierarchy, rather than increasing model scale alone, is a key factor for enabling robust long-horizon agentic intelligence.
Hongbo Jin, Rongpeng Zhu, Jiayu Ding +2
School of Electronic and Computer Engineering, Peking University
Large Language Models (LLMs) struggle with long-horizon tasks due to the "context bottleneck" and the "lost-in-the-middle" phenomenon, where accumulated noise from verbose environments degrades reasoning over multi-turn interactions. To address this issue, we introduce a symbiotic framework that decouples context management from task execution. Our architecture pairs a lightweight, specialized policy model, ContextCurator, with a powerful frozen foundation model, TaskExecutor. Trained via reinforcement learning, ContextCurator actively reduces information entropy in the working memory. It aggressively prunes environmental noise while preserving reasoning anchors, that is, sparse data points that are critical for future deductions. On WebArena, our framework improves the success rate of Gemini-3.0-flash from 36.4% to 41.2% while reducing token consumption by 8.8% (from 47.4K to 43.3K). On DeepSearch, it achieves a 57.1% success rate, compared with 53.9%, while reducing token consumption by a factor of 8. Remarkably, a 7B ContextCurator matches the context management performance of GPT-4o, providing a scalable and computationally efficient paradigm for autonomous long-horizon agents.
Xiaozhe Li, Tianyi Lyu, Yizhao Yang +6
Tongji University · CurrentsAI Research · Stanford University +1
Multimodal Large Language Models (MLLMs) based agents have demonstrated remarkable potential in autonomous web navigation. However, handling long-horizon tasks remains a critical bottleneck. Prevailing strategies often rely heavily on extensive data collection and model training, yet still struggle with high computational costs and insufficient reasoning capabilities when facing complex, long-horizon scenarios. To address this, we propose M2, a training-free, memory-augmented framework designed to optimize context efficiency and decision-making robustness. Our approach incorporates a dual-tier memory mechanism that synergizes Dynamic Trajectory Summarization (Internal Memory) to compress verbose interaction history into concise state updates, and Insight Retrieval Augmentation (External Memory) to guide the agent with actionable guidelines retrieved from an offline insight bank. Extensive evaluations across WebVoyager and OnlineMind2Web demonstrate that M2 consistently surpasses baselines, yielding up to a 19.6% success rate increase and 58.7% token reduction for Qwen3-VL-32B, while proprietary models like Claude achieve accuracy gains up to 12.5% alongside significantly lower computational overhead.
Dawei Yan, Haokui Zhang, Guangda Huzhang +8
Northwestern Polytechnical University, Xi’an, China · AI Business, Alibaba Group, Hangzhou, China · Xi’an University of Architecture and Technology, Xi’an, China +1