A Subgoal-driven Framework for Improving Long-Horizon LLM Agents

Taiyi Wang; Sian Gooding; Florian Hartmann; Oriana Riva; Edward Grefenstette

cs.AIMar 20, 2026

A Subgoal-driven Framework for Improving Long-Horizon LLM Agents

Authors: Taiyi Wang, Sian Gooding, Florian Hartmann, Oriana Riva, Edward Grefenstette

Organizations: Google DeepMind

Abstract

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 $s_{i}$ 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\mid 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 ( $\mathbf{z}_{t+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_{\phi}$ for final success and a Potential Critic $P_{\psi}$ 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 $\psi$ (green curve) increases monotonically as the agent completes subgoals (e.g., “Click Clone Btn”, “Click SSH Option”). This generates a dense $\Delta\psi$ 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.

Panel of Figure 9 — Figure 9: Showcase of Introspective planning of the Gemini-SGO-based Web Agent.

Panel of Figure 10 — 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.

Panel of Figure 11 — 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 ( $\approx 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 $\rightarrow$ Phase 1 $\rightarrow$ 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\times 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.

Panel of Figure 16 — Figure 16: The simplified system prompt employed in baseline agents.

Panel of Figure 17 — Figure 17: The system prompt used for the Outcome Reward Model (ORM) to verify trajectory success.

Panel of Figure 18 — 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.

Panel of Figure 19 — 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 .

$\alpha$	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

\alpha

Rank Score ( $1/\mathrm{PPL}$ )	$(0.9,1.0]$	$\mathbf{[0.5,0.9]}$	$[0.0,0.5)$	$[0.0,1.0]$
PPL Range	$[1,\tfrac{1}{0.9})$	$\mathbf{[\tfrac{1}{0.9},\tfrac{1}{0.5}]}$	$(\tfrac{1}{0.5},\infty)$	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/\mathrm{PPL}

p_{t}^{\ast}=(1-\alpha_{t})\tfrac{j}{K}+\alpha_{t}\tfrac{j+1}{K},\quad\alpha_{t}=\frac{t-t_{j}}{t_{j+1}-t_{j}}

Appendix

Algorithm 3 Training the Potential Critic

P_{\psi}

Long-Horizon LLM Agents

Long-horizon large language model agents plan, use tools, and preserve task state across extended, multi-step interactions.

See all 429 papers

HiMAC: Hierarchical Macro-Micro Learning for Long-Horizon LLM Agents
Mar 1, 2026Hongbo Jin, Rongpeng Zhu, Jiayu Ding +2Long-Horizon LLM Agents Long-Horizon Agent Tasks
School of Electronic and Computer Engineering, Peking University
Escaping the Context Bottleneck: Active Context Curation for LLM Agents via Reinforcement Learning
Apr 13, 2026Xiaozhe Li, Tianyi Lyu, Yizhao Yang +6Lost-in-the-Middle Effect LLM Context Management
Tongji University · CurrentsAI Research · Stanford University +1
M $^2$ : Dual-Memory Augmentation for Long-Horizon Web Agents via Trajectory Summarization and Insight Retrieval
Feb 28, 2026Dawei Yan, Haokui Zhang, Guangda Huzhang +8Long-Horizon LLM Agents Web Agents
Northwestern Polytechnical University, Xi’an, China · AI Business, Alibaba Group, Hangzhou, China · Xi’an University of Architecture and Technology, Xi’an, China +1

Mar 1, 2026J/K move · Enter open · S save

HiMAC: Hierarchical Macro-Micro Learning for Long-Horizon LLM Agents

Hongbo Jin, Rongpeng Zhu, Jiayu Ding, Guibo Luo+1

School of Electronic and Computer Engineering, Peking University

Long-Horizon LLM Agents Long-Horizon Agent Tasks Agentic RL RL for LLM Agents Hierarchical RL

Open paper AskPDF arXiv

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.

Abstract

Long-Horizon LLM Agents

Explore similar work

HiMAC: Hierarchical Macro-Micro Learning for Long-Horizon LLM Agents

Escaping the Context Bottleneck: Active Context Curation for LLM Agents via Reinforcement Learning

M2^22: Dual-Memory Augmentation for Long-Horizon Web Agents via Trajectory Summarization and Insight Retrieval

M $^2$ : Dual-Memory Augmentation for Long-Horizon Web Agents via Trajectory Summarization and Insight Retrieval