# When Replanning Becomes the Bottleneck: Budgeted Replanning for Embodied Agents

arXiv: https://arxiv.org/abs/2608.01428 · HTML: https://mlsanity.com/paper/2608.01428/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Tool learning and function calling, one of 16 directions in LLM agents and tool use.
- Builds on 33 of its 57 references that are in the map.
- First posted on arXiv 2 Aug 2026.

## Placed in

- LLM agents and tool use / [Tool learning and function calling](https://mlsanity.com/agents/tool-learning-and-function-calling/)

## Builds on (most cited first, 30 of 33)

- [RT-2: Vision-Language-Action Models Transfer Web Knowledge to Robotic Control](https://mlsanity.com/paper/2307.15818/) (2023)
- [OpenVLA: An Open-Source Vision-Language-Action Model](https://mlsanity.com/paper/2406.09246/) (2024)
- [Self-Instruct: Aligning Language Models with Self-Generated Instructions](https://mlsanity.com/paper/2212.10560/) (2022)
- [π0: A Vision-Language-Action Flow Model for General Robot Control](https://mlsanity.com/paper/2410.24164/) (2024)
- [Habitat: A Platform for Embodied AI Research](https://mlsanity.com/paper/1904.01201/) (2019)
- [Fine-Tuning Vision-Language-Action Models: Optimizing Speed and Success](https://mlsanity.com/paper/2502.19645/) (2025)
- [ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks](https://mlsanity.com/paper/1912.01734/) (2019)
- [AirSim: High-Fidelity Visual and Physical Simulation for Autonomous Vehicles](https://mlsanity.com/paper/1705.05065/) (2017)
- [RoboCasa: Large-Scale Simulation of Everyday Tasks for Generalist Robots](https://mlsanity.com/paper/2406.02523/) (2024)
- [ProcTHOR: Large-Scale Embodied AI Using Procedural Generation](https://mlsanity.com/paper/2206.06994/) (2022)
- [Gated Attention for Large Language Models: Non-linearity, Sparsity, and Attention-Sink-Free](https://mlsanity.com/paper/2505.06708/) (2025)
- [BabyAI: A Platform to Study the Sample Efficiency of Grounded Language Learning](https://mlsanity.com/paper/1810.08272/) (2018)
- [Habitat 3.0: A Co-Habitat for Humans, Avatars and Robots](https://mlsanity.com/paper/2310.13724/) (2023)
- [TEACh: Task-driven Embodied Agents that Chat](https://mlsanity.com/paper/2110.00534/) (2021)
- [TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate](https://mlsanity.com/paper/2504.19874/) (2025)
- [VLA-Cache: Efficient Vision-Language-Action Manipulation via Adaptive Token Caching](https://mlsanity.com/paper/2502.02175/) (2025)
- [PARTNR: A Benchmark for Planning and Reasoning in Embodied Multi-agent Tasks](https://mlsanity.com/paper/2411.00081/) (2024)
- [SP-VLA: A Joint Model Scheduling and Token Pruning Approach for VLA Model Acceleration](https://mlsanity.com/paper/2506.12723/) (2025)
- [COMBO: Compositional World Models for Embodied Multi-Agent Cooperation](https://mlsanity.com/paper/2404.10775/) (2024)
- [ChatVLA-2: Vision-Language-Action Model with Open-World Embodied Reasoning from Pretrained Knowledge](https://mlsanity.com/paper/2505.21906/) (2025)
- [VLA-0: Building State-of-the-Art VLAs with Zero Modification](https://mlsanity.com/paper/2510.13054/) (2025)
- [Turning Trash into Treasure: Accelerating Inference of Large Language Models with Token Recycling](https://mlsanity.com/paper/2408.08696/) (2024)
- [Reflective Planning: Vision-Language Models for Multi-Stage Long-Horizon Robotic Manipulation](https://mlsanity.com/paper/2502.16707/) (2025)
- [RoboFactory: Exploring Embodied Agent Collaboration with Compositional Constraints](https://mlsanity.com/paper/2503.16408/) (2025)
- [SELP: Generating Safe and Efficient Task Plans for Robot Agents with Large Language Models](https://mlsanity.com/paper/2409.19471/) (2024)
- [Fast and Accurate Task Planning using Neuro-Symbolic Language Models and Multi-level Goal Decomposition](https://mlsanity.com/paper/2409.19250/) (2024)
- [Taming the Fragility of KV Cache Eviction in LLM Inference](https://mlsanity.com/paper/2510.13334/) (2025)
- [KV Cache Transform Coding for Compact Storage in LLM Inference](https://mlsanity.com/paper/2511.01815/) (2025)
- [ReST-KV: Robust KV Cache Eviction with Layer-wise Output Reconstruction and Spatial-Temporal Smoothing](https://mlsanity.com/paper/2605.08840/) (2026)
- [Put Teacher in Student's Shoes: Cross-Distillation for Ultra-compact Model Compression Framework](https://mlsanity.com/paper/2507.04636/) (2025)

## Built on by (most cited first, 1 of 1)

- [What Can Component-Replacement Evidence Establish? A Critical Scoping Review of Local Decisions in LLM Agents](https://mlsanity.com/paper/2609.39989/) (2026)

## Abstract (arXiv)

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.