Beyond Reasoning: Horizon Length as the Hidden Bottleneck in LLM Agent Training
On Training Large Language Models for Long-Horizon Tasks: An Empirical Study of Horizon Length
This empirical study investigates the training dynamics of Large Language Models (LLMs) on long-horizon tasks, identifying "horizon length" as a fundamental training bottleneck independent of reasoning complexity. Using controlled Sudoku and Rush Hour tasks, the authors demonstrate that increasing sequence length leads to severe RL instability and performance collapse, while introducing "horizon reduction" (macro actions and subgoal decomposition) stabilizes training and enables SOTA-level long-horizon generalization.
Executive Summary
TL;DR: While LLM research often obsesses over reasoning depth, this paper identifies horizon length—the number of interaction steps—as a distinct, structural bottleneck. Even when a task's logic is easy, a high step count triggers RL collapse due to exploration exhaustion and credit assignment "noise." The solution isn't a bigger model; it's Horizon Reduction (e.g., macro actions), which allows models to solve tasks they previously crashed on and generalize to even longer sequences.
Context: This is a foundational empirical study that repositions long-horizon failures as an optimization problem rather than a lack of "intelligence." It provides a bridge between classical Hierarchical RL and modern LLM post-training.
The "Long Horizon" Crisis: Why Models Collapse
The authors pose a provocative question: If an LLM can solve a Sudoku puzzle in one shot (proxy task), why does it fail when asked to solve it cell-by-cell over 50 turns?
The root cause lies in Asymmetric Gradient Dynamics. In RL, a positive advantage focuses the model on a specific token. However, a negative advantage (common in long, failing trajectories) provides a "diffuse" update. Because the vocabulary is massive (~100k+), a negative signal essentially tells the model to lower the probability of its last action and indiscriminately boost thousands of irrelevant tokens. Over a long horizon, this noise accumulates, leading to catastrophic collapse where the model begins generating gibberish or repeats entries until it hits the max token limit.
Methodology: Shrinking the Horizon
To solve this, the paper introduces two primary strategies to reduce the Effective Horizon ():
- Macro Actions: Instead of "Move car A to cell 3," the agent uses "Move car A to cell 5" (skipping intermediate steps). This reduces the number of decision points.
- Subgoal Decomposition: Breaking the task into verifiable chunks (e.g., solving one 3x3 box in Sudoku at a time).
System Architecture & Logic
The study uses a specialized RL pipeline called rllm, which solves a critical "Training-Inference Mismatch." By using Token-level Importance Sampling (TIS) and Geometric-Mean Masked IS (Geo-MIS), they ensure that the gradients calculated during training actually reflect the sampling probability of the tokens generated during high-throughput inference (vLLM).
Figure 1: Core contribution mapping - How horizon reduction leads to stability and generalization.
Experimental Proof: Capacity is Not Enough
A striking finding: scaling the model doesn't fix the horizon bottleneck. When testing a 4B model against a 1.7B model, both collapsed under the default long horizon.
However, when Horizon Reduction was applied (Macro Actions), both models stayed stable.
- Sudoku (L3-L4): Performance jumped from near-zero to over 90% success.
- Rush Hour: The curriculum strategy (training on short horizons, then medium) proved that establishing competence on short horizons is a prerequisite for long-range success.
Figure 2: Performance comparison - Macro actions (blue/orange) consistently outperform atomic actions (green/red) as the goal distance () increases.
The Prize: Horizon Generalization
Perhaps the most exciting result is Horizon Generalization. Models trained on tasks requiring 20 actions started successfully solving tasks requiring 45+ actions at inference time. This suggests that by stabilizing the learning of the reasoning primitives through horizon reduction, the model naturally learns a policy that can "re-apply" those primitives infinitely.
Critical Analysis & Future Outlook
Takeaways:
- Design for Micro-Decisions: If you are building a coding agent, don't ask it to write code line-by-line. Ask it to write functions or modules (Macro Actions).
- Process Rewards Matter: Use subgoal verification to provide dense rewards, effectively "resetting" the credit assignment clock.
Limitations:
- The study is primarily on synthetic, text-based games (Sudoku, Rush Hour). While they validated on WebShop, real-world noise (visual errors, changing environments) might introduce new variables not captured here.
- Technique Generalization: While the model scales to longer horizons, it does not automatically learn harder reasoning techniques (e.g., shifting from "Naked Singles" to "X-Wings" in Sudoku). RL amplifies existing skills but struggles to invent new reasoning primitives.
Conclusion
This work serves as a vital reminder: in the race for "AGI," the structure of the task environment is just as important as the architecture of the model. Managing the effective horizon is the hidden key to transforming brittle LLMs into robust, long-running agents.