When Replanning Becomes the Bottleneck: Budgeted Replanning for Embodied Agents

Imagine you are the captain of a spaceship navigating a chaotic asteroid field. You have a super-smart AI co-pilot that helps you plot your course. But here's the catch: every time the ship bumps into a rock or gets lost, you ask the AI to re-calculate the entire route from the very beginning. At first, this is easy. But as your journey gets longer, the AI's "memory" of everything that happened—the rocks you dodged, the messages from other ships, the mistakes you made—grows into a massive, tangled ball of yarn. Every time you ask for a new plan, the AI has to read that entire ball of yarn again. Eventually, the AI gets so overwhelmed by its own history that it takes forever to think. By the time it finally shouts out a new direction, you've already crashed into another asteroid. This is the problem of "replanning" in the world of robots and AI agents: the more they learn and the longer they work, the slower they get at fixing their mistakes, even if they are still technically good at the job.

This paper, titled "When Replanning Becomes the Bottleneck," tackles this exact headache for "embodied agents"—robots or AI systems that live in the real world (or realistic simulations) and have to move and act. The authors, Shuaijun Liu and his team, discovered that while these robots are getting better at completing tasks, they are failing at a hidden metric: speed. They found that a robot can be 100% successful at reaching its goal, but if it takes too long to figure out how to get there after a mistake, it misses its real-time deadlines. It's like a student who gets an A on a test but takes three days to write the answer key; the grade is perfect, but the system is broken. The paper introduces a new system called BRACE (Budgeted Replanning for Agentic Control in Embodied Systems) and a smart pruning tool called E-RECAP. Think of BRACE as a strict project manager who tells the AI, "You have exactly 200 words to explain your new plan, and you must finish in 2.5 seconds. If you can't, we'll cut your story short." E-RECAP is the editor who ruthlessly deletes the boring, repetitive parts of the AI's memory while keeping the important bits, so the AI can think faster without forgetting the crucial details.

The Problem: The "Too Much History" Trap

In the world of robotics, agents (like self-driving cars or robot arms) don't just follow a single, perfect script. The real world is messy. Robots slip, sensors get confused, and other agents (like other robots or drones) do unexpected things. To handle this, modern robots use a loop: they observe what's happening, plan a move, act, and then, if things go wrong, they replan.

The problem arises because every time the robot replans, it doesn't just look at the current moment. It feeds the AI a massive prompt containing the task instructions, the entire history of what happened, the mistakes made, and messages from other agents. As the robot works longer, this "context" grows. Imagine trying to read a book where the pages keep getting added to the beginning and end every time you turn a page. Eventually, the book becomes so thick that reading it takes hours.

The authors found that as this context grows, the time it takes for the AI to replan (the "latency") starts to have "heavy tails." This means that while the average replanning time might look okay, occasionally the AI gets stuck in a "long tail" of thinking, taking way too long. In a real-time system, a single long delay can be disastrous. The paper shows that in many tests, robots were 100% successful at their tasks, but they violated their speed limits (called Service-Level Objectives, or SLOs) on up to 100% of their replanning calls. It's a bit like a runner who finishes every race but takes 10 minutes to tie their shoes before the starting gun fires; they win, but the system is inefficient and unreliable.

The Solution: BRACE and the Budget Manager

To fix this, the team created BRACE. Instead of letting the AI replan whenever it feels like it with unlimited memory, BRACE treats replanning like a budgeted resource. It acts as a controller that decides three things for every single time the robot needs to rethink:

1. Should we replan? Sometimes, the robot is just drifting a little and doesn't need a full new plan. BRACE can say "wait" to avoid unnecessary thinking.
2. How much "token budget" do we have? Tokens are the units of text the AI reads. BRACE sets a strict limit on how many tokens the AI can use for its new plan.
3. What is the time limit (SLO)? BRACE sets a hard deadline for how long the replanning process can take.

If the AI tries to use too much memory or takes too long, BRACE intervenes. It also has safety features like "cooldown windows," which prevent the robot from panicking and replanning every single second, which would just make things slower.

The Tool: E-RECAP (The Smart Editor)

Even with a budget, the AI still needs to read something. This is where E-RECAP comes in. It is a "progressive token pruning" method. Imagine the robot's memory as a long, rambling story. E-RECAP is a super-smart editor that knows which parts of the story are crucial and which are just fluff.

It works by looking at the AI's internal "hidden states" (its way of understanding the text) and scoring every word (token) based on how important it is.

• It keeps the beginning (the task instructions) and the end (the most recent events), because those are usually the most critical.
• It deletes the middle parts that are less important or repetitive.
• It does this in layers, getting progressively stricter as it moves through the AI's brain.

The result is a much shorter, cleaner story that still contains all the necessary information to make a good decision.

What They Found: Speed Without Sacrificing Success

The team tested BRACE and E-RECAP on three different platforms: Meta Habitat (a virtual world for navigation), RoboFactory (a simulation for robot arms and coordination), and AirSim (a simulator for drones and cars).

The results were striking. In the Meta Habitat navigation tests, the standard approach (called "No BRACE") achieved 100% task success but violated the speed limit on 85.5% of replanning calls. When they added BRACE and E-RECAP, the success rate stayed at 100%, but the speed limit violations dropped dramatically to just 4.7%.

In the RoboFactory tests, the improvement was even more dramatic. The standard approach violated speed limits on 100% of calls. With BRACE and E-RECAP, that number dropped to 50.0%. In an even harder setting where the standard approach failed completely (0% success), the new system managed to reach 80.0% success while keeping speed violations low at 4.6%.

The system also reduced the number of tokens the AI had to process by 62% to 92%. This means the AI was doing less work to get the same (or better) results. In the AirSim drone tests, the speed violations dropped from 100% to 4.7%.

Why This Matters

The paper argues that we need to change how we measure robot performance. Just saying "the robot succeeded" isn't enough if it took too long to figure out how. By treating replanning as a system problem with strict budgets, we can build robots that are not only smart but also fast and reliable.

The authors also tested this on a real robot arm in a lab (doing tasks like picking up fruit or pushing objects). While the simulation results were the main focus, the real-robot tests showed that the same budgeting and pruning techniques worked there too, improving success rates and reducing delays.

In short, the paper suggests that by being a little more stingy with memory and time, and by using a smart editor to cut the fluff, robots can stop getting bogged down by their own history and start moving through the world with the speed and agility they need. It's a reminder that sometimes, knowing what not to remember is just as important as remembering everything.