When Replanning Becomes the Bottleneck: Budgeted Replanning for Embodied Agents

1. Introduction: The Latency Blindspot in Embodied AI

In modern embodied AI architectures, agents rely on Large Language Models (LLMs) and Vision-Language-Action (VLA) models to navigate dynamic environments, manipulate complex objects, and collaborate across multi-agent systems. Because these agents operate under partial observability, actuation noise, and environmental drift, long-horizon plans can become invalid within just a few execution steps. To recover, modern embodied architectures employ a continuous closed-loop operational paradigm: observe → plan → act → replan.

In research published at ICML 2026, Liu et al. expose a critical systems failure mode inherent to this paradigm. While frequent replanning allows agents to correct execution errors, every replanning call appends new state observations, execution feedback, error traces, and multi-agent coordination messages to the system prompt. Over long horizons, this textual context accumulates rapidly. As prompt lengths inflate, the computational overhead of the underlying transformer model scales non-linearly, turning routine replanning calls into severe computational bottlenecks.

This dynamic creates a profound safety paradox in embodied systems evaluation. Standard benchmark metrics—such as aggregate task completion rates or average inference latency—frequently conceal severe, transient performance degradation. An agent may achieve a 100% task completion rate while regularly experiencing heavy-tailed latency spikes during replanning. In physical or time-sensitive settings, these latency spikes lead to severe real-time Service Level Objective (SLO) deadline violations. When an agent stalls to process an inflated context prompt, it delays critical action execution, aggravating physical drift and potentially inducing catastrophic hardware or environmental failure.

To resolve this bottleneck, Liu et al. introduce two complementary systems contributions:

• BRACE (Budgeted Replanning for Agentic Control in Embodied Systems): A closed-loop system controller that formulates replanning as a budgeted control problem, managing trigger admission, selecting execution modes, and enforcing explicit per-call token budgets and latency deadlines.
• E-RECAP (Embodied REplanning with Cost-Aware Pruning): A progressive token-pruning module designed specifically for long-horizon replanning contexts that dynamically predicts token utility across transformer layers to shrink prompt lengths while retaining vital context.

---

2. The Failure Mechanism: Context Accumulation and Tail Latency

To understand why replanning degrades real-time stability, it is necessary to examine the components of a standard replanning prompt. When an embodied agent detects execution drift or receives a failure signal, the system constructs an updated prompt containing:

1. Task Specifications: High-level goals, safety constraints, and initial environment specifications.
2. Recent State Histories: Time-series logs of raw observations, executed actions, and intermediate sensor readings.
3. Failure Traces: Diagnostic output, error flags, and execution feedback detailing why the prior plan failed.
4. Multi-Agent Coordination Summaries: In multi-robot settings, incoming message histories, task allocations, and peer status reports.

In multi-agent configurations with $K$ agents, the context length $N_t$ at step $t$ accumulates additively over time:

$N_t = N_0 + \sum_{i=1}^{t} \sum_{a=1}^{K} n_{i,a}$

where $n_{i,a}$ represents the tokens contributed by agent $a$ between step $i-1$ and step $i$.

The physical impact of multi-agent scaling is severe. As demonstrated by Liu et al. in Habitat PointNav experiments, increasing the agent count from $K=1$ to $K=8$ causes unpruned prompt contexts per replanning call to escalate from 2,847 tokens to 38,924 tokens. Consequently, average replanning latency jumps from 2.34 seconds to 29.67 seconds per call.

[Initial Task & System Prompt] (N_0)
               │
               ▼
[Step 1: Observations + Actions + Error Traces] (+n_1)
               │
               ▼
[Step 2: Multi-Agent Messages + Sub-goal Updates] (+n_2)
               │
               ▼
[Accumulated Context N_t] ──► Transformer Self-Attention O(N_t²) ──► Latency Spikes

Because transformer self-attention computational complexity scales quadratically ($\mathcal{O}(N_t^2)$) relative to sequence length $N_t$, long episodes yield severe execution stalls. In a closed loop, these computational delays trigger a destructive feedback loop:

1. Context accumulation lengthens replanning latency $\ell_t$.
2. Delayed planning responses force the physical agent to wait or execute stale plans, exacerbating actuation drift.
3. Increased drift triggers additional, higher-frequency replanning requests.
4. Repeated requests accumulate further failure traces and history, causing latency to exhibit heavy-tailed distributions ($P95$/$P99$ spikes).

Key Safety Insight: Standard evaluation metrics that focus on overall task success or mean latency obscure critical, short-duration failures. An embodied system can exhibit a 100% success rate while simultaneously missing latency SLO deadlines on almost every replanning call, concealing dangerous real-time control instabilities behind aggregate benchmarks.

---

3. Technical Architecture: BRACE and E-RECAP

Liu et al. propose a two-part framework that integrates a high-level system controller with an internal context compression module.

                  ┌─────────────────────────────────────────┐
                  │          BRACE Controller               │
                  │  (Evaluates Triggers & Budget Policy)   │
                  └────────────────────┬────────────────────┘
                                       │
                             Replan Allowed (u_t = 1)
                                       │
                                       ▼
                  ┌─────────────────────────────────────────┐
                  │       BRACE Replanning Call Path        │
                  │ ┌─────────────────────────────────────┐ │
                  │ │    E-RECAP Progressive Pruning      │ │
                  │ └──────────────────┬──────────────────┘ │
                  │                    │ Compressed Context │
                  │                    ▼ (<= B_t tokens)    │
                  │ ┌─────────────────────────────────────┐ │
                  │ │        LLM / VLA Backbone           │ │
                  │ └──────────────────┬──────────────────┘ │
                  └────────────────────┼────────────────────┘
                                       │
                                       ▼
                  ┌─────────────────────────────────────────┐
                  │ Phase Accounting & Audit Logs           │
                  │ (Tracks Token, Latency & SLO Metrics)   │
                  └────────────────────┴────────────────────┘

3.1 The BRACE Controller & Stability Mechanisms

BRACE treats replanning as a budgeted control loop rather than an unconstrained reaction to environment triggers. At step $t$, given a trigger signal vector $\tau_t$ (derived from periodic timers, execution failures, or multi-agent hazards) and an internal controller state $\sigma_t$, BRACE determines:

1. Whether to permit a replanning call ($u_t \in \{0, 1\}$).
2. The replanning mode $m_t$, per-call token budget $B_t$, and latency deadline target $SLO_t$.

To prevent high-frequency oscillations and control churn, BRACE enforces structural stability policies:

• Cooldown Windows ($\delta$): Imposes a minimum step delay following any replanning invocation before the planner can be called again ($\Delta_t \ge \delta$).
• Commit Windows ($\omega$): Mandates that once a new plan is issued, the controller must execute it for a minimum number of steps before allowing a subsequent plan override ($\kappa_t \ge \omega$).
• Failure-Aware Overrides: If execution failures persist repeatedly, the controller overrides the cooldown/commit constraints and temporarily expands the token budget $B_t$ to allow deeper reasoning for error recovery.

Formally, the baseline stability gate $u_t$ is evaluated as:

$u_t = \mathbb{I}\left[\tau_t \land (\Delta_t \ge \delta) \land (\kappa_t \ge \omega)\right]$

When $u_t = 0$, the controller skips the LLM call entirely, directing the agent to continue executing its current plan without incurring computational overhead.

A core methodological contribution of BRACE is its support for budget-matched baseline comparisons. Simply reducing context length is insufficient to prove the superiority of an efficiency module. Under BRACE’s interface, alternative context reduction strategies (such as Recency Truncation, Random Truncation, Structured Summaries, or learned KV-cache selectors like DefensiveKV and ReST-KV) are constrained to the exact same planner token budget $B_t$. This isolates the quality retention of a given context selection algorithm from pure token volume reduction.

3.2 E-RECAP: Progressive Token Pruning Across Transformer Layers

When $u_t = 1$, BRACE passes the accumulated context $C_t$ to E-RECAP, an efficiency primitive tailored for long-horizon textual replanning prompts. Unlike standard vision-language approaches that focus on per-frame visual token pruning, E-RECAP specifically target-prunes the accumulated dialogue, history, and message context within the LLM backbone.

E-RECAP executes progressive pruning across a designated set of intermediate transformer layers $\mathcal{P} \subset \{1, \dots, L\}$:

• Layer-Wise Scoring: At each pruning layer $l \in \mathcal{P}$, E-RECAP passes the intermediate hidden state $h_i^{(l)} \in \mathbb{R}^d$ of each token $i$ through a lightweight linear-GELU-linear predictor module to compute an importance score $\pi_i^{(l)}$.
• Predictor Training: To ensure generalizability across diverse contexts, the predictor module is trained across intermediate transformer layers using a data mixture combining general instruction-tuning datasets (e.g., Dolly, Alpaca) and auxiliary embodied environments (e.g., ALFRED, TEACh, BabyAI).
• Target Sequence Length: Given a per-layer keep ratio $r_l \in (0, 1]$, the target sequence length for the subsequent layer is set to $N_{l+1} = \lfloor r_l N_l \rfloor$.
• Context Preservation Strategy: E-RECAP prevents critical loss of context by explicitly preserving fixed structural bounds before applying score-based filtering:
  • Head Tokens ($H_l$): Retains initial task specifications and system prompt constraints.
  • Tail Tokens ($T_l$): Retains the most recent state observations and immediate action feedback window.
  • Score Selection: Fills the remaining dynamic token budget by selecting top-ranking tokens based on their predicted utility $\pi_i^{(l)}$ from the intermediate sequence:

$I_{l+1} = H_l \cup T_l \cup \text{TopK}\left( \{\pi_i^{(l)}\}_{i=1}^{N_l} \setminus (H_l \cup T_l), \; N_{l+1} - |H_l| - |T_l| \right)$

By progressively pruning across layers, the quadratic self-attention complexity drops from $\mathcal{O}(N^2)$ to $\mathcal{O}(r^2 N^2)$, keeping the resulting context strictly within the per-call budget $B_t$.

3.3 Phase Accounting and Auditable Logs

To isolate delays accurately, BRACE instruments the complete call path with phase-level audit logging. End-to-end replanning latency $\ell_t$ is recorded as the total wall-clock time from call path entry to plan dispatch. The framework logs individual latencies across distinct execution phases:

$\text{Latency } \ell_t = t_{\text{compress}} + t_{\text{retrieve}} + t_{\text{plan}} + t_{\text{dispatch}}$

System performance is evaluated using the explicit SLO Violation Rate ($v$):

$v = \frac{1}{T} \sum_{t=1}^{T} \mathbb{I}[\ell_t > SLO]$

Logging phase-level latencies ensures that computational overhead added by compression, retrieval, or plan caching is transparently accounted for, preventing misattribution of latency spikes solely to the underlying LLM backbone. Crucially, empirical measurements on Meta Habitat confirm that E-RECAP’s compression phase overhead ($t_{\text{compress}}$) adds only $\approx 35\text{ ms}$ relative to $\approx 2.4\text{ s}$ of main planner latency ($t_{\text{plan}}$). This demonstrates that context pruning introduces negligible computational overhead and does not re-introduce scheduling bottlenecks.

---

4. Empirical Evaluation & Cross-Platform Benchmarks

Liu et al. evaluated BRACE and E-RECAP across three simulated embodied platforms—Meta Habitat (navigation), RoboFactory (multi-arm manipulation), and Microsoft AirSim (multi-agent UAV/car coordination)—as well as physical single-arm robot setups.

4.1 Cross-Platform Performance Comparison

The table below contrasts the performance of unconstrained replanning (No BRACE) against the budgeted, pruned architecture (BRACE + E-RECAP) across identical environments.

Platform / Scenario	Method	Success Rate (%)	Avg Tokens	P95 Latency (ms)	SLO Target (ms)	SLO Violations (%)
Meta Habitat (Navigation)	No BRACE	100.0	235	2,677	2,500	85.5
Meta Habitat (Navigation)	BRACE + E-RECAP	100.0	20	2,500	2,500	4.7
RoboFactory (Pass-Shoe)	No BRACE	100.0	1,566	1,604	250	100.0
RoboFactory (Pass-Shoe)	BRACE + E-RECAP	100.0	319	1,213	250	50.0
Microsoft AirSim ($K=8$ Intersection)	No BRACE	100.0	2,934	8,520	2,500	100.0
Microsoft AirSim ($K=8$ Intersection)	BRACE + E-RECAP	100.0	1,114	1,640	2,500	4.7

Data Source: Liu et al. (ICML 2026)

Across saturated success domains, No BRACE frequently violates latency SLOs on 85.5% to 100.0% of all calls due to unconstrained prompt growth. Integrating BRACE + E-RECAP reduces per-call token counts by 62% to 92%, cutting $P95$ tail latencies significantly and dropping SLO violation rates down to 4.7%–50.0% without sacrificing task completion rates.

Furthermore, under budget-matched evaluations on the RoboFactory Pass-Shoe anchor at a fixed token limit $B=128$, E-RECAP achieves superior latency stability compared to alternative context management techniques. While simple heuristics like Recency Truncation ($P95$ latency 204.9 ms) and learned KV selectors like DefensiveKV ($P95$ latency 239.09 ms) or ReST-KV ($P95$ latency 231.95 ms) operate under the same token budget, E-RECAP achieves lower latency ($P95$ latency 207.09 ms) and minimal SLO violations (0.49%), confirming that utility-aware layer-wise pruning preserves vital reasoning context far more effectively than indiscriminate truncation.

4.2 Harder Settings & Real-Robot Physical Execution

• Harder RoboFactory Environment: In an un-saturated manipulation scenario where execution drift is fatal, traditional unbudgeted and open-loop approaches fail entirely. Systems running Open-loop, Frozen plan, or No BRACE achieved a 0.0% task success rate (with No BRACE incurring a 27.6% SLO violation rate and substantial coordination stall delays). In contrast, BRACE + E-RECAP achieved an 80.0% task success rate while maintaining an SLO violation rate of just 4.6%.
• Real-Robot Single-Arm Validation: To evaluate physical execution, Liu et al. deployed the framework onto a single-arm robotic manipulator running dynamic tasks (PICKFRUIT and PUSHT). Open-loop execution without closed-loop replanning (One-Shot) fails almost completely, yielding 8.0% success on PICKFRUIT and 0.0% success on PUSHT, emphasizing the necessity of continuous replanning.
  • PICKFRUIT: No BRACE achieved a 24.0% success rate with $P95$ replanning latencies of 29.4s and an SLO violation rate of 42.7%. BRACE + E-RECAP increased task success to 40.0%, lowered $P95$ latency to 22.8s, and reduced SLO violations to 18.6%.
  • PUSHT: No BRACE reached a 12.0% success rate with $P95$ replanning latencies of 34.7s and a 61.3% SLO violation rate. BRACE + E-RECAP elevated task success to 32.0%, lowered $P95$ latency to 26.1s, and cut the SLO violation rate to 27.5%.

---

5. Takeaways & Guidance for AI Safety Researchers

The empirical findings from Liu et al. provide essential guidelines for practitioners, red-teamers, and safety engineers designing real-time autonomous systems:

• Look Beyond Task Completion: Aggregate success rates and mean latency metrics mask safety-critical tail latency spikes. Safety evaluations for embodied agents must monitor call-granularity tail distribution metrics ($P95$/$P99$ latency) and explicit SLO violation rates.
• Budget the Mitigation Loop: Recovery mechanisms and error-handling prompts introduce substantial computational overhead. Error recovery systems must be metered as bounded, budgeted system primitives; unbudgeted mitigation logic can easily become the primary source of operational failure.
• Combine Budgeting with Selective Pruning: Enforce strict per-call token budgets at the system controller level and pair them with utility-aware token pruning modules. Preserving structural head tokens (task goals) and tail tokens (recent state) while selectively pruning intermediate layers protects functional plan quality while lowering computational overhead.
• Implement Control-Side Stability Gates: Token pruning alone cannot eliminate back-to-back replanning cascades. Systems must incorporate structural stability mechanisms—such as cooldown counters, plan commit windows, and failure-aware overrides—to prevent rapid thrashing, reduce coordination wait times, and stabilize real-time execution.

Read the full paper on arXiv · PDF