When Replanning Becomes the Bottleneck: Budgeted Replanning for Embodied Agents

Embodied agents replan frequently to recover from execution drift, partial observability, and coordination hazards, but each LLM-based replanning call can consume an accumulated textual context that grows over time and across agents. Once this context becomes large, replanning latency develops heavy tails and can miss real-time deadlines even when task success remains high, a failure mode that is hard to detect from average latency or success alone. We present BRACE, a controller that formulates replanning as a budgeted control loop by deciding whether to replan, selecting a replanning mode, and allocating an explicit token budget and latency service-level objective (SLO) while accounting for optional efficiency modules. As a reusable component, we introduce E-RECAP, a cost-aware progressive token pruning method that predicts token utility and prunes replanning contexts across transformer layers while preserving critical head and tail tokens. Across Meta Habitat, RoboFactory, and AirSim, BRACE with E-RECAP reduces replanning-call token counts by 62–92% and SLO violation rates from 85.5–100.0% to 4.7–50.0% in settings where task success is already saturated. In a harder RoboFactory setting where open-loop, frozen-plan, and No BRACE all fail, BRACE + E-RECAP reaches 80.0% success with 4.6% SLO violations, demonstrating that tail-aware per-call budgeting is effective across embodied platforms.

Robots and other embodied AI agents often need to revise their plans while acting, for example when they encounter unexpected changes, incomplete information, or coordination problems with other agents. However, repeatedly asking a large language model to update a plan can become slow because the information it must read grows throughout the task. This can cause important decisions to arrive too late, even when the agent is otherwise capable of completing the task. We introduce BRACE, a system that controls when an agent should revise its plan and limits the amount of information used for each update so that decisions can be made on time. We also develop E-RECAP, a component that removes less useful parts of the accumulated context while retaining important task information. In experiments involving navigation, robot manipulation, and multi-drone tracking, our approach substantially reduced planning cost and late decisions while preserving, and in more difficult cases improving, task completion. This work helps embodied AI systems respond more reliably under real-time constraints.