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

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

The agent successfully reads invoice data from the phone. But when executing git clone on the computer to download a template, the network glitches and the command line throws an error.

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

None of these is smart, because the real problem is simple: the command-line route is blocked—switch routes and download via a browser instead.

This is exactly the problem Shu Yao's team at Shanghai Jiao Tong University tackles in the H-RePlan paper: when a multi-device agent encounters an execution failure, how do you distinguish "this strategy failed" from "this task failed," and recover appropriately?

Three Legs Are Steadier Than One

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

• API Agent: accesses services through structured interfaces—most reliable, but not everything has an API
• CLI Agent: command-line operations, great for local computation and filesystem work, but depends on environment configuration
• GUI Agent: graphical interface operations, the 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 mid-tier 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 to work: if the subway breaks down, take the bus; if the bus is stuck in traffic, grab a shared bike. You don't need to rethink "should I go to work today" just because the subway failed—you just need a different route.

Hierarchical Recovery: Localize When Possible, Escalate When Necessary

H-RePlan's "hierarchical" aspect lies in splitting failures into two levels:

Device level (Strategy Planner): when a strategy execution fails, the Strategy Planner first decides whether this is a strategy-level problem. If git clone fails, it might be a network issue—switching to browser download solves it without notifying anyone globally. The Strategy Planner can switch strategies, modify instructions, and retry within the device.

System level (Orchestrator): if the device level determines the failure can't be solved by strategy switching—for example, the device simply lacks necessary resources—only then is it escalated to the Orchestrator, which decides whether to reassign the task to another device or modify the global plan.

Bridging the two is a compact abstraction called Cross-Layer Failure Event (CLFE): the device level packages failure information into a structured event containing failure type, strategies already attempted, failure cause, and more, letting the Orchestrator quickly decide whether escalation is warranted.

The key insight behind this design: most failures are local and don't require global replanning. If you tear down the global plan every time a strategy fails, you waste enormous tokens on unnecessary replanning and may lose completed context.

HeraBench: Deliberately Injecting Faults into Pipelines

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 stops working)
• Device-level faults: an 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 when devices fail?

The Numbers Speak

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 takeaways:

• H-RePlan's completion rate (75.84%) is nearly 15 percentage points above the strongest baseline, UFO³ API (61.05%)
• Perfect pass rate (36.78%)—completing tasks exactly 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 vs. UFO³ GUI's 10.5M—a 5.4x efficiency gap

The Value of Local Recovery

One set of results in the paper especially 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 hurts. Escalation means context loss—the Orchestrator doesn't know what was already attempted inside the device, so replanning may repeat failed paths or assign tasks to unsuitable devices.

Another data point: when a strategy-level fault ultimately requires reassignment, assigning back to the original device yields 91.7% completion (558K tokens), while assigning to another device drops to 62.7% (1.01M tokens).

Counterintuitive? Not really. The original device has accumulated context—it knows what the task is, what was tried before, what the environment state is. Switch devices and all of that is lost, requiring a fresh start. So unless the original device is confirmed 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 failures too coarsely: retry, reassign, or replan. H-RePlan argues: failures are hierarchical, and recovery should be too. A strategy failure shouldn't overturn a task; a task failure shouldn't overturn a plan.

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

From an engineering perspective, H-RePlan's API-CLI-GUI three-strategy design is also practical. Prior multi-device systems typically exposed only one strategy per device—either GUI or CLI—limiting recovery capability. H-RePlan gives every device a choice of three strategies; the implementation is more complex, but the robustness gains are substantial.

Honest Limitations

H-RePlan currently relies on Linux and Android. iOS cannot provide a CLI strategy due to system restrictions, and Windows GUI automation works completely differently 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 type (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 convincing. 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