Research map / Multi-agent systems and games / LLM agents

When Replanning Becomes the Bottleneck: Budgeted Replanning for Embodied Agents

ICML 2026 · Multi-agent systems and games › LLM agents · approach: Robust and efficient agent execution · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes BRACE, a budgeted replanning controller with token/latency SLO accounting, and E-RECAP, a learned progressive token-pruning module for replanning contexts, showing large SLO-violation reductions on Habitat, RoboFactory, and AirSim.

Problem

LLM-based replanning in embodied agents operates on accumulating textual context, causing heavy-tailed latency and SLO deadline misses even when task success stays high; average latency and success metrics hide this.

Approach

Treat each replanning call as a budgeted control decision (whether to replan, which mode, token budget B_t and latency SLO_t) with cooldown/commit stability gates, plus E-RECAP, which predicts token importance from hidden states and progressively prunes the replanning prompt across transformer layers while keeping head and tail tokens.

Key results

• On Meta Habitat, BRACE + E-RECAP cuts SLO violations from 85.5% to 4.7% and tokens from 235 to 20 at 100% success.
• In the harder RoboFactory Pass-Shoe setting, BRACE + E-RECAP reaches 80.0% success with 4.6% SLO violations, while open-loop, frozen-plan, and No BRACE all reach 0% success.
• E-RECAP on Habitat PointNav reduces tokens per replanning call by 71-76% and yields 2.09-2.64x replanning speedups across K=1,4,8 agents.

Surprising findings

• Recency truncation at the same budget B=20 achieves 0.0% SLO violation on Habitat, outperforming the learned E-RECAP pruner on that metric.
• Success saturates at 100% on most platforms while replanning violates the latency SLO on most calls, so success alone hides deadline misses.

Limitations

• Real-robot evaluation is limited to two tasks with a single arm and small episode counts.
• Stability property is a controller-side structural property, not a full theorem-level guarantee, as the authors state.
• SLO values are domain-specific and chosen by the authors; results depend on the chosen thresholds.

Experimental setup

Datasets: Dolly Alpaca Self-Instruct ALFRED TEACh BabyAI Meta Habitat MP3D

Benchmarks: Meta Habitat PointNav Meta Habitat ObjectNav RoboFactory Pass-Shoe Microsoft AirSim intersection RoboSuite LIBERO

Metrics: success rate SPL P95 latency SLO violation rate tokens per replanning call coordination wait

Baselines: No BRACE Random truncation Recency truncation Structured summary KVTC TurboQuant ReST-KV DefensiveKV

Builds on: token pruning (visual token pruning) KV cache compression

Closest papers by meaning

• ReCAP: Recursive Context-Aware Reasoning and Planning for Large Language Model Agents (NeurIPS 2025 · similarity 0.85)
• AOrchestra: Automating Sub-Agent Creation for Agentic Orchestration (ICML 2026 · similarity 0.85)
• Done, But Not Sure: Disentangling World Completion from Self-Termination in Embodied Agents (NeurIPS 2026 · similarity 0.85)
• ECHO: Terminal Agents Learn World Models for Free (NeurIPS 2026 · similarity 0.85)
• RePO-VLA: Recovery-Driven Policy Optimization for Vision-Language-Action Models (NeurIPS 2026 · similarity 0.85)
• Efficient Skill Grounding via Code Refactoring with Small Language Models (ICML 2026 · similarity 0.84)