Source-linked AI summary
LIMBO: Lifelong Inference-Time Memory and Budget Optimization for LLM Agents
Siddharth Sharma, Nilesh Prasad Pandey, Onat Gungor, Tajana Rosing
TL;DR
Lifelong agents need to reuse past experience while balancing the inference-time costs of replay, yet existing approaches do not adapt replay and compute budgets to each task. LIMBO learns those allocation choices online with a contextual bandit. Across three LLM backbones, it achieves better cost–accuracy tradeoffs than memory-augmented baselines, reducing inference cost by up to ∼83% while maintaining comparable performance.
Problem
Replay can help lifelong agents reuse past interactions, but its cost competes with other inference resources and fixed policies do not account for task-dependent trajectory value.
Source: §I · p. 1Method
LIMBO uses a gradient-free contextual bandit to choose replay strategies and inference budgets online for each task, without modifying the underlying agent.
Source: §I · p. 2, D. LIMBO Controller · p. 4Results
Across three LLM backbones on LifelongAgentBench, LIMBO achieves better cost–accuracy tradeoffs than memory-augmented baselines, reducing inference cost by up to ∼83% (∼53% on average) while maintaining comparable performance.
Source: §V · p. 8Takeaways & Limitations
The learned policies adapt across models and environments, showing that effective memory allocation can be discovered online rather than manually specified.
Source: §V · p. 8
Abstract
from arXiv · showhide
As LLM agents become integrated into increasingly complex workflows, they must continually acquire new capabilities while retaining competence on previously learned tasks. Lifelong agents address this through experience replay, injecting past interactions into the prompt to leverage prior experience during inference. However, replay is not free: every replayed trajectory competes with retrieval, reasoning, tool use, and verification for the same limited prompt and compute budget, making effective resource allocation essential. Existing approaches allocate these resources using fixed replay policies, regardless of whether replay is beneficial for the current task. We identify this as inference-time memory allocation, a distinct problem class for lifelong agents, and introduce LIMBO: the first online framework to our knowledge that treats memory as a controllable inference-time resource and jointly optimizes memory strategy and inference budget for each incoming task. Unlike prior approaches that fix the replay policy or require model weights, teacher supervision, or offline retraining, LIMBO learns this allocation online in a single pass, explicitly balancing task performance and inference cost without modifying the underlying agent. Across three LLM backbones on LifelongAgentBench, LIMBO achieves better cost-accuracy tradeoffs than state-of-the-art memory-augmented baselines and nearly matches all strongest such baselines at up to ~83% lower inference cost (~53% on average). LIMBO adapts its policy across models and environments without retraining, demonstrating that effective allocation can be learned online rather than manually specified.
I. INTRODUCTION
Lifelong agents must balance the value of replaying past experience against inference-time costs, but existing memory approaches do not jointly adapt replay and compute to each task. LIMBO treats these resources as online allocation decisions.
I. INTRODUCTION
- Replay can help agents reuse past tool-use patterns, but its token overhead grows with the task stream and individual trajectories vary in relevance.Uniform replay can spend context and computation on trajectories that provide limited benefit for the current task.Source: §I · p. 1
- Memory, retrieval, reasoning, tool use, and verification compete for limited context and computation, making resource allocation a central lifelong-agent challenge.Fixed replay buffers can incur rapidly growing inference costs for diminishing performance gains.Source: §I · pp. 1–2
- Across three LLM backbones, LIMBO achieves comparable or superior performance to the strongest fixed replay baseline while reducing inference cost by up to ∼83%.The framework learns different allocation policies across model and environment configurations.Source: §I · p. 2
- LIMBO selects a memory strategy and compute budget for each incoming task using a lightweight contextual bandit, without modifying the underlying agent.Its allocation framework covers existing memory mechanisms, including fixed replay, compression, selective replay, and memory-augmented agents.Source: §I · p. 2
II. RELATED WORK
- Prior work addresses lifelong agent evaluation [10], inference efficiency [5]–[9], replay compression,, replay selection, [13], and memory retrieval [14], [15], but not unified cost-aware replay allocation.LIMBO casts inference-time compute control in the lifelong setting and treats memory use itself as a controllable action.Source: §II · p. 2
III. LIMBO FRAMEWORK
LIMBO turns replay into an online allocation decision, choosing a memory mode and compute budget before each task. It updates its memory bank and controller from the completed task’s observed outcome and cost.
A. Overview
- For each task, LIMBO uses prompt, retrieval-state, and runtime features to compare memory modes and compute budgets, then updates its memory bank and controller from observed correctness and cost.The agent executes once after the selected action determines how much history enters the prompt and how much execution budget it receives.Source: A. Overview · p. 2
B. Problem Setup
- The memory buffer holds previously successful sessions, whose usefulness for a new task depends on shared operations, schemas, or action formats.A relevant trajectory may transfer value, while an unrelated one adds prompt overhead.Source: B. Problem Setup · pp. 2–3
- LIMBO measures cost from prompt and generation tokens using provider or standardized local-backbone pricing, then normalizes it to [0, 1] against a running maximum.The cost weight controls the accuracy-cost tradeoff and is set to 0.5 in reported experiments.Source: B. Problem Setup · p. 3
- Memory injection can lengthen prompts, raise API spend, and destabilize action formatting, so the framework aims to allocate memory adaptively.Source: B. Problem Setup · p. 3
C. Memory Actions
LIMBO’s memory actions range from no replay to full, compressed, and retrieved replay. The retrieved mode ranks past sessions for the current task, while trajectory rendering can trim verbose outputs without removing agent commands.
C. Memory Actions
- The memory modes include no replay, fixed-count verbatim replay, question-aware compressed replay, and retrieval of relevant trajectories from a larger memory bank.Compressed replay uses the current task instruction as its query, with each trajectory treated as a separate context block.Source: C. Memory Actions · p. 3
- DBBench retrieval scores sessions using instruction, skill-set, and table-identifier matches, with a recency bonus, then injects the top k trajectories.The scoring weights were tuned on a held-out development subset and held fixed across retrieval-based variants.Source: C. Memory Actions · p. 3
- Trajectories can be rendered verbatim or as trimmed traces that shorten verbose environment outputs while preserving all agent-issued commands.This differs from token-level compression, which can damage the structured action syntax required by interactive environments.Source: C. Memory Actions · p. 3
D. LIMBO Controller
LIMBO frames lifelong memory and inference-budget allocation as an online, gradient-free contextual-bandit problem. It selects task-specific actions from pre-call features, then updates its estimates from observed outcomes and costs.
D. LIMBO Controller
- LIMBO extends LinUCB with two heads that predict correctness and cost to allocate replay and inference budget online without modifying model weights.The design targets black-box compatibility, single-pass learning, bounded per-task overhead, and an explicit accuracy-cost objective.Source: D. LIMBO Controller · pp. 3–4
- Its 12 pre-call features combine prompt shape, recent runtime state, and the previous task’s success or error outcome.These features let the controller account for prompt composition, recent costs and accuracy, and recent failures without model-weight access.Source: D. LIMBO Controller · p. 4
- Before replay injection, the controller scores candidate actions using predicted correctness, predicted cost, and a cost weight to select a memory mode and compute budget.Selection makes memory use a primary decision rather than fixed prompt preprocessing.Source: D. LIMBO Controller · p. 4
- Controller overhead is under 0.5 ms per task on one CPU core, with O(|A| d^2) total work for |A| actions and feature dimension d.In the reported experiments, d = 12 and |A| ≤ 12.Source: D. LIMBO Controller · p. 5
- After each task, LIMBO updates its bandit state from the observed outcome and cost, adapting continuously without a separate offline training phase.The algorithm interleaves action selection with post-task updates throughout deployment.Source: D. LIMBO Controller · pp. 4–5
E. Instantiation in This Work
LIMBO is evaluated with three action-space designs that vary the available memory strategies and whether a confidence-triggered second pass is included.
E. Instantiation in This Work
- The retrieval-gated design offers no replay, full recent replay, or relevance-retrieved replay from a 64-session memory bank, with k ∈ {4, 8, 16} tested as separate configurations.The retrieved trajectories are selected from the bank by relevance.Source: E. Instantiation in This Work · p. 5
- The compression-gated design chooses among no replay, full recent replay, and LongLLMLingua-compressed replay.Source: E. Instantiation in This Work · p. 5
- The retrieval-gated-plus-rescue design adds a confidence-triggered second pass that reruns low-confidence samples with maximum retrieved context.Source: E. Instantiation in This Work · p. 5
- Together, the designs distinguish which memories to use from when memory is worth spending tokens on, while allowing different answers to the first question.Source: E. Instantiation in This Work · p. 5
A. Setup
The evaluation uses sequential DB and OS tasks from LifelongAgentBench across three backbones, comparing LIMBO with replay and voting-based baselines under a shared configuration.
A. Setup
- The benchmark uses 500-task sequential slices in DB (SQL) and OS (bash), evaluated with three backbones across six model-environment settings.The backbones are Qwen2.5 7B Instruct, Llama 3.1 8B Instruct, and GPT-4o mini.Source: A. Setup · p. 5
- LIMBO and baseline points are averaged over three matched seeds: 42, 43, and 44.Source: A. Setup · p. 5
- Baselines include no replay, fixed replay of the N most recent successful trajectories, LongLLMLingua compression, and Group Self-Consistency at usc=1.Fixed replay uses deterministic trimmed-trace rendering that preserves executable action structure; on Qwen OS at k=1, it scores 51.5% versus 49.4% for token-level compression.Source: A. Setup · p. 5
- All six LIMBO points use the same controller, features, online update, and four memory actions paired with three generation-budget tiers.The memory actions are none, full, compressed, and retrieved; budget tiers are low ≤512, medium 768, and high ≥1024.Source: A. Setup · p. 5
- The study reports accuracy and total token cost per 500-task run, using greedy decoding with a 512-token response cap.Local-model dollar values are standardized proxies, not measured serving expense.Source: A. Setup · p. 5
B. Overall Cost–Accuracy Tradeoff
Across all six model–environment settings, LIMBO achieves competitive accuracy at lower inference cost than fixed replay and other memory-augmented baselines. Its strongest gains include large savings against costly replay and strict Pareto dominance over selected baselines.
B. Overall Cost–Accuracy Tradeoff
- Figure 3 compares cost and accuracy across three backbones and two environments; LIMBO generally occupies a low-cost, competitive-accuracy region, while highest-accuracy fixed-replay configurations often cost substantially more.Markers distinguish no replay, fixed replay, retrieval, LongLLMLingua, GSC, and LIMBO.Source: Figure 3 · p. 6
- Across all six settings, LIMBO lies on the empirical cost–accuracy Pareto frontier and matches or exceeds the strongest memory-augmented baseline’s accuracy within −3.8 to +0.6 points while reducing cost by 26–83%.On GPT-4o mini OS, it exceeds LongLLMLingua by 0.6 points at 40.5% lower cost.Source: B. Overall Cost–Accuracy Tradeoff · p. 6, Figure 3 · p. 6
- LIMBO strictly dominates GSC in all four matched settings, with higher accuracy and lower cost; on Llama DB, its accuracy advantage is 26 points.The comparison covers Qwen DB, Qwen OS, Llama DB, and Llama OS.Source: B. Overall Cost–Accuracy Tradeoff · p. 6
- The largest cost reductions, approximately 83%, occur on Qwen DB and GPT-4o mini DB, where the strongest baseline uses a k=16-scale replay budget and no-replay accuracy is already strong.On Llama DB, no-replay accuracy is 20.8%, while LIMBO reaches 66.2% at less than half the strongest baseline’s cost.Source: B. Overall Cost–Accuracy Tradeoff · p. 6
C. Policy Across Backbones and Environments
Under the same controller and hyperparameters, LIMBO selects different memory-and-compute policies across model–environment settings. The policies range from near no-replay when replay adds little, to retrieved replay when prior demonstrations matter.
C. Policy Across Backbones and Environments
- On the 500-task Qwen OS stream, retrieved replay rises from 48.7% in the first window to a 72.7% mean across windows 2–10, while no-replay falls from 17.3% to 3.8%.Compressed replay is selected on 0% of tasks throughout.Source: Figure 5 · p. 7
- On Qwen and GPT-4o mini DB, LIMBO places approximately 78% of tasks on no-replay because replay adds only 2–3 accuracy points at a 5–6× cost multiplier.The policy pairs no-replay with the lowest generation-budget tier.Source: C. Policy Across Backbones and… · p. 7
- On Qwen OS, LIMBO uses retrieved k=1 on approximately 70% of tasks and full replay on approximately 25%, matching fixed-replay accuracy at 34% lower cost.The higher generation-budget tiers are used more than half the time.Source: C. Policy Across Backbones and… · p. 7
- On Llama DB, where no-replay accuracy is 20.8%, LIMBO assigns approximately 85% of tasks to retrieved replay and reaches 66.2% accuracy at less than half the strongest baseline’s cost.Most tasks still use the lowest generation-budget tier.Source: C. Policy Across Backbones and… · p. 7
- On GPT-4o mini OS, LIMBO selects retrieved k=1 on approximately 88% of tasks; accuracy improves by 3.4 points over no-replay while aggregate cost stays within approximately 6% of no-replay.The paper describes this as an observed operating point, not demonstrated causal adaptation to pricing.Source: C. Policy Across Backbones and… · p. 7
- LIMBO’s policy varies by setting rather than following a global replay rule: DB settings with strong no-replay performance favor no replay, while Llama DB and OS settings use replay more heavily.The same controller, features, and hyperparameters are used across cells.Source: C. Policy Across Backbones and… · p. 7
D. Online Adaptation over the Task Stream
The Qwen OS stream shows LIMBO changing its action mix over time, alongside a declining uncertainty bonus. Together, these observations provide evidence that its converged policy is learned during the stream rather than fixed in advance.
D. Online Adaptation over the Task Stream
- In Qwen OS, the first 50 tasks are more exploratory than the later policy: no-replay falls from 17.3% to a 3.8% mean, full replay from 34.0% to 23.5%, and retrieved replay rises from 48.7% to 72.7%.Later values are means across windows 2–10; cross-seed standard deviations remain below 0.017 in every window.Source: D. Online Adaptation over the Task… · p. 7
- The selected-action α-scaled UCB uncertainty bonus falls 67% from 0.347 in the first 100 tasks to 0.115 in the last 100 as per-action precision matrices accumulate observations.The decline is monotonic in eight of nine window transitions; the one small reversal stays within cross-seed standard deviation.Source: D. Online Adaptation over the Task… · p. 7
- The changing action mix and contracting exploration bonus jointly support that the Figure 4 policy is learned online rather than fixed beforehand.The reported trajectory averages three seeds over a 500-task Qwen OS stream.Source: D. Online Adaptation over the Task… · p. 7
E. Discussion
LIMBO approaches the cost-efficient frontier across models and environments by recovering much of the accuracy of memory-augmented baselines near the no-replay cost floor. It controls when to use memory and how much compute to allocate, complementing methods that improve memory representation or retrieval.
E. Discussion
- On Qwen OS, LIMBO matches fixed replay within 0.1 points at 34% lower cost; on Llama DB, it stays within 3.8 points of fixed k=16 at 54% lower cost.Source: E. Discussion · p. 7
- On GPT-4o mini OS, LIMBO Pareto-dominates LongLLMLingua by +0.6 points at 40% lower cost, while improving no-replay accuracy by +3.4 points.Source: E. Discussion · p. 8
- On DBBench, LIMBO matches the standard fixed-replay baseline at one-sixth its cost, operating close to the no-replay cost floor.Source: E. Discussion · p. 8
- LIMBO allocates memory use and compute at inference time rather than changing memory representation, and can incorporate improved representations as replay actions.Source: E. Discussion · p. 8
V. CONCLUSION
- Across three LLM backbones on LifelongAgentBench, LIMBO reduces inference cost by up to ∼83% (∼53% on average) while maintaining comparable performance.Source: §V · p. 8