H-RePlan: Hierarchical Failure Recovery for Multi-Device AI Agents Beats Full Replanning

Imagine this scenario: you ask an AI agent to complete an expense reimbursement workflow. It needs to screenshot invoices from an app on your phone, transfer them to a computer, organize them into folders, and upload them to the reimbursement system.

The agent successfully reads the invoice information from the phone. But on the computer, while running git clone to download a template, the network glitches and the command line returns an error.

What would existing multi-device agent systems do? Three options: retry the same command (likely to fail again), reassign the subtask to another device (but this task must be done on the computer), or discard the entire global plan and re-plan (using a sledgehammer to crack a nut).

None of these are smart. The real problem is simple: the command-line route is blocked, so take another route — download via browser.

This is exactly the problem solved by the H-RePlan paper from Shu Yao's team at Shanghai Jiao Tong University: when a multi-device agent hits an execution failure, how do you distinguish "this strategy doesn't work" from "this task doesn't work," and then recover appropriately.

Three Legs Are Steadier Than One

H-RePlan's core design equips each device with three interchangeable execution strategies:

• API Agent: accesses services through structured interfaces. Most reliable, but not every feature has an API.
• CLI Agent: command-line operations, suited for local computation and filesystem tasks, but depends on environment configuration.
• GUI Agent: graphical interface operations. Most universal (anything a human can use, it can use), but slowest and most expensive.

Each strategy has strengths and weaknesses. API is fast but narrow in coverage; CLI is middling but environment-dependent; GUI is slow but universal. The key insight: when one strategy fails, you can switch to another without overturning the whole plan.

It's like commuting: if the subway breaks down, take the bus; if the bus is stuck, grab a shared bike. You don't reconsider "should I go to work today" just because the subway failed — you just take a different route.

Hierarchical Recovery: Localize What's Local, Escalate What's Global

The "hierarchical" in H-RePlan refers to splitting failures into two levels:

Device level (Strategy Planner): when a strategy execution fails, the Strategy Planner first judges whether this is a strategy-level problem. If git clone fails, it might be a network issue — switching to a browser download suffices. No need to notify the global layer. The Strategy Planner can switch strategies, modify instructions, and retry within the device.

System level (Orchestrator): only if the device layer judges the failure can't be solved by strategy — for instance, the device fundamentally lacks required resources — is it escalated to the Orchestrator, which decides globally whether to reassign the task to another device or modify the global plan.

The bridge between layers is a compact abstraction called the Cross-Layer Failure Event (CLFE): the device layer packages failure information into a structured event containing failure type, strategies already attempted, failure reasons, and so on, letting the Orchestrator quickly decide whether escalation is warranted.

The key insight of this design: most failures are local and don't require global re-planning. If you overturn the global plan every time a strategy fails, you waste massive tokens on unnecessary re-planning and may lose already-completed context.

HeraBench: Deliberately Throwing Faults into the Pipeline

To evaluate hierarchical recovery, the authors built HeraBench — a fault-injection multi-device benchmark. It constructs cross-device workflows on Linux and Android devices, then deliberately injects two types of faults:

• Strategy-level faults: an execution strategy becomes unavailable (e.g., a CLI command is inaccessible)
• Device-level faults: the entire device goes down (e.g., the device goes offline)

This design lets you precisely measure: can the agent recover locally from strategy faults? Can it adjust globally from device faults?

The Numbers

Main experimental results on HeraBench:

| System | Completion | Instruction Following | Perfect Pass | Tokens/Turn | Tokens/Perfect Pass | |--------|-----------|----------------------|--------------|-------------|---------------------| | CRAB GUI | 2.16% | 9.30% | 0% | 547K | ∞ | | CRAB API | 28.84% | 42.80% | 0% | 489K | ∞ | | UFO³ GUI | 46.86% | 56.67% | 13.79% | 1.45M | 10.5M | | UFO³ API | 61.05% | 67.81% | 0% | 322K | ∞ | | H-RePlan | 75.84% | 77.72% | 36.78% | 711K | 1.93M |

Key readings:

• H-RePlan's completion rate (75.84%) is nearly 15 percentage points higher than the strongest baseline, UFO³ API (61.05%)
• The perfect pass rate (36.78%) — completing tasks fully correctly with no deviation — is nearly 23 points above UFO³ GUI (13.79%)
• UFO³ API has a decent completion rate but a 0% perfect pass rate — it finishes tasks but often deviates from instructions
• Token efficiency: H-RePlan needs 1.93M tokens per perfect pass versus 10.5M for UFO³ GUI — a 5.4x efficiency gap

The Value of Local Recovery

One set of numbers particularly illustrates the hierarchical recovery logic:

• Strategy-level faults not escalated (resolved within the device): 76.81% completion, 82.00% following
• Strategy-level faults escalated prematurely (reported globally within the first two attempts): 68.89% completion, 62.22% following

Premature escalation actually performs worse. Escalation means context loss — the Orchestrator doesn't know what the device has already tried internally, so re-planning may repeat failed paths or assign tasks to unsuitable devices.

Another data point: when strategy-level faults ultimately require reassignment, reassigning back to the original device yields a 91.7% completion rate (558K tokens), while assigning to a different device yields only 62.7% (1.01M tokens).

Counterintuitive? No. The original device has already accumulated context — it knows what the task is, what was previously tried, and what the environment state is. Switch devices, and all of that context is lost; you start from scratch. So unless the original device is confirmed to be truly broken, don't rush to switch.

What This Means

H-RePlan's contribution isn't "yet another multi-device agent framework" — it's a redefinition of "failure handling."

Existing agent systems handle failure too coarsely: retry, reassign, or re-plan. H-RePlan says: failures have levels, and recovery should too. A strategy failing doesn't need to overturn a task; a task failing doesn't need to overturn a plan.

This idea applies beyond multi-device scenarios. Any complex AI agent system — single-device or multi-agent — will encounter "this path is blocked" situations. H-RePlan's hierarchical abstraction (strategy level vs. task level vs. plan level) is a general design pattern.

From an engineering perspective, H-RePlan's API-CLI-GUI three-strategy design is also very practical. Prior multi-device systems typically exposed only one strategy per device — either GUI or CLI — limiting recovery capability. H-RePlan gives each device a choice set of three strategies. Higher implementation complexity, but a significant robustness payoff.

Honest Limitations

H-RePlan currently relies on two platforms: Linux and Android. iOS cannot provide a CLI strategy due to system restrictions, and Windows GUI automation differs completely from Linux. A unified cross-platform strategy space remains a long engineering road.

Additionally, both H-RePlan's Orchestrator and Strategy Planner rely on LLMs for decisions — meaning its recovery capability is bounded by LLM reasoning quality. If the LLM misclassifies a failure (treating a device-level fault as strategy-level), the entire hierarchical recovery logic breaks down.

But as a proof of concept for "hierarchical recovery," H-RePlan is already persuasive. The next time you design a multi-step AI agent system, ask yourself first: is my failure handling hierarchical?

Paper link: https://arxiv.org/abs/2606.20487