Technical Summary: Hera – Learning Long-Horizon Coordination for Device–Cloud Collaborative LLM Agents

1. Problem Statement

Large Language Model (LLM) agents have demonstrated the ability to solve complex, long-horizon tasks through autonomous interaction with environments. However, their real-world deployment faces a fundamental device–cloud dilemma:

• Device-side constraints: On-device models (typically <10B parameters) are efficient and low-latency but often lack the reasoning depth required for complex multi-step planning, leading to performance degradation and incoherent trajectories.
• Cloud-side limitations: Powerful cloud models offer superior reasoning but introduce significant network latency, high computational costs, and privacy concerns, making them impractical for real-time applications like robotics or interactive GUI navigation.

Existing device–cloud routing methods typically make coarse, task-level decisions, assigning an entire query to either the device or the cloud based on estimated difficulty or confidence. This "all-or-nothing" approach is ill-suited for long-horizon agent tasks where execution unfolds as a sequence of interdependent steps with varying difficulty. The paper posits that a finer-grained, step-level coordination strategy is necessary to balance task success and inference cost effectively.

2. Methodology: The Hera Framework

The authors propose Hera, a lightweight step-level device–cloud coordinator designed to optimize the trade-off between task success and cloud usage. Hera is a 500M-parameter decoder-only Transformer with a binary classification head that decides, at each interaction step $t$, whether to route the state to the local device policy ($\pi_{\theta_d}$) or the cloud policy ($\pi_{\theta_c}$).

Hera employs a novel two-stage training paradigm:

Stage 1: Cold-Start via Imitation Learning (IL)

To initialize the routing policy without direct reinforcement signals, the authors use imitation learning:

1. Trajectory Collection: Both device and cloud agents are rolled out to generate trajectories for a set of tasks.
2. Filtering: Tasks where the cloud significantly outperforms the device (exceeding a margin $\delta$) are selected to define a regime where cloud assistance is necessary.
3. Supervision: The device agent is "replayed" on the cloud's successful trajectory states. A step-level consistency label $y_t$ is generated:
   • $y_t = 1$ (Route to Cloud): If the device's action $a^d_t$ disagrees with the cloud's action $a^c_t$.
   • $y_t = 0$ (Route to Device): If the actions agree.
4. Training: The router is trained as a binary classifier using Binary Cross-Entropy (BCE) loss on this dataset, aligning its latent space with the performance differential between the two models.

Stage 2: Cost-Aware Reinforcement Learning (RL) with State Grouping

The IL stage provides a prior but does not directly optimize the joint objective of maximizing return while minimizing cloud calls. Hera is refined using RL:

1. Rollouts: Multiple trajectories ($N$) are collected for each task using the current router, with stochasticity introduced via a temperature-scaled Bernoulli distribution to encourage exploration.
2. State Grouping: Identical states encountered across different rollouts are grouped. For each unique state $s$, the system estimates:
   • $\hat{R}(d; s)$: The expected trajectory return if decision $d$ (device or cloud) is made.
   • $\hat{C}(d; s)$: The expected future cloud calls (including the current step) if decision $d$ is made.
3. Preference Labeling: A preference label $y(s)$ is derived by selecting the decision with the higher estimated return. If returns are comparable (within a margin $\epsilon$), the decision with lower expected future cloud usage is preferred.
4. Optimization: The router is updated by minimizing BCE loss on these preference labels, with an $L_2$ regularization term to prevent excessive drift from the IL-initialized parameters.

3. Key Contributions

The paper claims three primary contributions:

1. First Step-Level Coordinator: Hera is presented as the first device–cloud agent coordinator operating at the step level for long-horizon tasks, addressing the performance–cost trade-off more granularly than prior task-level routers.
2. Two-Stage Training Framework: The authors develop a specific training pipeline combining imitation learning (for cold-start initialization based on action consistency) and state-grouped reinforcement learning (for joint optimization of trajectory return and cloud cost).
3. Empirical Superiority: Extensive experiments demonstrate that Hera outperforms state-of-the-art baselines, achieving a stronger Pareto frontier between task success and cloud usage.

4. Experimental Results

Hera was evaluated on three challenging long-horizon benchmarks: ALFWorld (embodied household tasks), WebShop (e-commerce navigation), and AppWorld (multi-app coding tasks). The device model was Qwen2.5-7B-Instruct, and the cloud model was Qwen-Max.

Key Findings:

• Performance-Cost Trade-off: Hera achieved 92.5% of the cloud-only success rate while using the cloud for only 46.3% of the steps.
• Comparison to Baselines:
  • On ALFWorld, Hera achieved an 86.1% success rate with a cost of $4.0 \times 10^{-3}$, significantly outperforming the cloud-only baseline (90.9% success, $11.7 \times 10^{-3}$ cost) and all other routing baselines (e.g., RouteLLM, FrugalGPT).
  • On WebShop, Hera reached 34.1% success with a cost of $8.1 \times 10^{-3}$, compared to the cloud-only 35.6% success at $14.7 \times 10^{-3}$.
  • On AppWorld, Hera achieved 19.7% success with a cost of $31.3 \times 10^{-3}$, compared to cloud-only 22.6% success at $43.8 \times 10^{-3}$.
• Latency: By reducing cloud invocations, Hera significantly lowered end-to-end latency (e.g., 105.5s vs. 174.1s on ALFWorld) while maintaining high success rates.
• Ablation Studies: Removing the RL stage resulted in lower success rates and higher cloud usage. Removing the IL stage led to unstable training and poorer performance, confirming the necessity of the two-stage pipeline.
• Micro-benchmarks: Analysis showed that Hera effectively identifies "critical steps" requiring deep context tracking or complex constraint composition, routing them to the cloud, while handling routine steps locally.

5. Significance and Claims

The paper argues that Hera represents a pivotal shift from coarse, task-level routing to fine-grained, dynamic collaboration. Its significance lies in:

• Democratizing Advanced Agents: By demonstrating that only a small fraction of critical steps require cloud intervention, Hera lowers the computational and financial barriers to deploying sophisticated agents on user devices.
• Enabling Real-Time Applications: The framework makes latency-sensitive applications (e.g., robotic control, interactive assistants) feasible on device hardware without prohibitive costs or delays.
• Scalability: Hera establishes a strong performance–cost Pareto frontier, suggesting a viable path toward scalable, sustainable, and ubiquitous autonomous agents in real-world environments where resource constraints are paramount.

The authors note limitations, including the assumption of synchronous, reliable connectivity and the lack of built-in privacy-preserving mechanisms for offloaded data, identifying these as areas for future research.