acceptodds
Under review as a conference paper at ICLR 2027

When to Look Again: Learning from Refresh Feedback For LLM Agents

Abstract

Large language model (LLM) agents reuse information from tools, retrieval, and memory over many steps while the underlying sources keep changing, so an agent can act on an outdated copy of information it once retrieved correctly. With a small refresh budget per step, the agent must decide which copies can wait. We model independent source changes with weighted staleness costs and a shared refresh budget. The model is a restless bandit whose closed-form Whittle index sets the refresh priority and a Lagrangian lower bound evaluates the scheduler. The index reflects both the risk of staleness and how long a refresh keeps the copy fresh, i.e., faster change raises priority at short ages but lowers the priority ceiling. When rates are learned from refreshes, an upper confidence bound (UCB) on a source’s rate therefore lowers its priority and can delay the observations that would correct it. We instead maximize the index over plausible rates and rebuild the plausible set at every decision. For a two-source class, we prove that freezing the set can yield linear expected excess cost while rebuilding it keeps the excess bounded, and we give checkable conditions for bounded cost with multiple unknown sources. In numerical experiments, maximizing the index over plausible rates approaches the cost of a scheduler that knows the rates, while a UCB on the rate incurs persistent excess cost. With known rates, the index scheduler stays close to the lower bound across budgets and system sizes.

Primary area:
optimization
Keywords:
Optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_m5WROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper investigates the problem of information refresh scheduling for LLM agents operating in dynamic environments, where previously retrieved information may become outdated over time. The authors formulate the problem as a restless multi-armed bandit under a limited refresh budget and propose UCB-WIRS, a Whittle-index-based scheduling algorithm that estimates unknown source change rates from refresh feedback and leverages index-based optimism to guide refresh decisions. The paper establishes theoretical guarantees for the proposed approach and evaluates its performance through synthetic simulations and a simplified LLM agent task.

Critical strengths
  1. The paper investigates information refresh scheduling in LLM agents, which is a timely and practically relevant problem. As LLM agents increasingly operate in dynamic environments, determining when and which information to refresh becomes an important challenge. This problem is worth further investigation and has potential practical value.

  2. The paper provides substantial theoretical analysis of the proposed approach, including threshold optimality, indexability, and performance guarantees. These results provide theoretical support for the proposed method and offer insights into its effectiveness.

Critical weaknesses
  1. The proposed framework relies on several strong assumptions, such as independent and stationary source changes, noiseless refreshes, and fixed relevance weights. However, the paper provides insufficient justification for whether these assumptions are reasonable in realistic LLM agent scenarios. Since real-world information dynamics can be considerably more complex, these assumptions raise concerns about the applicability of the proposed framework to practical settings.

  2. The experimental evaluation is largely limited to synthetic settings. Even the LLM agent experiment is conducted on a simplified synthetic task rather than a realistic agent environment. The lack of experiments involving real-world information sources and dynamic agent interactions makes it difficult to assess whether the proposed approach can generalize beyond the simplified settings. Consequently, its practical effectiveness in realistic LLM agent applications remains insufficiently validated.

Questions for authors

Please see the weaknesses.

2 comments

We thank the reviewer for the assessment. Both concerns are about how far the results reach beyond the model. We answer the first with new experiments on the assumptions, and the second by stating the scope of the evidence exactly.

Weakness 1: The paper makes three assumptions (Section 2). We take them in order: what each one requires of an agent's information sources, and what happens when it fails. The revision adds a sentence on the first point after each assumption and a new appendix with the experiments. The new experiments use the instances and trajectories of Table 1; the two tests already in the paper (Figures 4 and 5) use one instance with N = 50, B = 5 and 20 trajectory seeds, and the known-rate scheduler. Assumption 1. Source (i) changes in each slot with a constant probability (p_i), independently across slots and sources. This describes sources maintained by separate processes at approximately steady rates. Some inventory counts, prices, policy documents, and API-backed records may fit this description. We have not validated this model on real sources; the experiments below examine departures from its conditions. It is the slotted form of the standard change model used in the refresh-scheduling literature (Cho & Garcia-Molina, 2003; Azar et al., 2018; Kolobov et al., 2019). Assumption 2. A refresh returns the source’s current content exactly. This describes a successful read from the source of record, but the assumption can fail when retrieval passes through caches or replicas. In the new experiment, an attempted refresh of a stale copy can fail silently. Costs increase with the failure probability, with larger relative increases at higher budgets. Known-rate WIRS, UCB-WIRS, and Thompson sampling remain the policies with the lowest costs across the tested failure probabilities and budgets, and UCB-WIRS remains close to known-rate WIRS. Here, known-rate WIRS serves as a reference rather than a lower bound. However, silent failures bias rate estimates downward, and the final plausible sets can exclude the true rates. The learning guarantees therefore do not extend to this violation of Assumption 2. Assumption 3. The weights g_i are known and remain constant over the horizon. A source’s weight is the product of its access frequency and the loss incurred by using an outdated value. The new experiments below estimate only the access-frequency component. Assumption 3 without known weights: With weights estimated online from one access per slot and rates unknown too, UCB-WIRS costs more than known-rate WIRS with the true weights. Assumption 3 without constant weights: When the weights are reassigned among sources every 5,000 slots, UCB-WIRS with the current weights is more above known-rate WIRS.I f weights never recalibrated, then it worse than using no weights. Assumption 3 without known weights An error of standard deviation 0.5 in the logarithm costs more than using no weights.

Weakness 2: The experiments are controlled, and the revision says so in the abstract and the introduction. The reasons are specific to what the paper claims. The claims are about staleness cost: closeness to a lower bound, and the cost of learning relative to a scheduler that knows the rates. Testing them requires the true change times of every source and, for the bound, the true rates. The agent benchmarks we cite (Gaia2, τ-bench, LoCoMo) do not define per-source change rates or a staleness cost, so neither the bound nor the known-rate comparator can be computed on them without first defining observable sources (Section 7). The controlled experiment tests a link the theory does not cover: whether, in a task where a stale copy gives a wrong answer, lower staleness cost gives an agent more correct answers. The scheduler affects the agent only through the copies it reads. The extended task runs eleven budgeted schedulers and a full-refresh reference with three LLMs to show it. The robustness experiments impose five departures that real sources can show (bursts, correlation, failed reads, wrong rates, wrong and drifting weights), one at a time and at magnitudes we chose, with a known ground truth. Reverting values, event-driven changes, delayed retrieval and combined departures are not tested. In a larger family (N = 100, B = 10) UCB-WIRS is 0.85% above the known-rate cost and rate optimism 37%. We do not claim an evaluation in a deployed agent environment. Section 7 states what such an evaluation needs: observable sources, corrective visits, and weights calibrated to task loss. The revision keeps this as the main limitation and scopes the abstract to controlled sources.

I thank the authors for their detailed response. However, the response mainly explains the scope and limitations of the work rather than providing direct evidence that resolves the weaknesses I raised. I will therefore maintain my original score.

Reviewer_CxWYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1(−1)
Read review
Paper summary

This paper models independent source changes with weighted staleness costs and a shared refresh budget, and maximizes the index over plausible rates and rebuilds the plausible set at every decision. More importantly, it proves threshold optimality and indexability, recovers the closed-form web-crawling index, and obtains a Lagrangian lower bound. The proposed learning scheduler UCB-WIRS, maximizes the index over plausible rates and rebuilds the set of plausible rates at every decision.

Critical strengths
  1. The theoretical analysis is strong, as the authors prove threshold optimality and indexability, recover the closed-form web-crawling index, and obtain a Lagrangian lower bound.

  2. The related work is well categorized and the motivation is well built.

Critical weaknesses
  1. There are so many assumptions in this paper, e.g., Assumption 1 (Markov change process), Assumption 2 (Noiseless refresh) and Assumption 3. The authors should make clear why such assumptions make sense. 

  2. Only Qwen2.5-7B-Instruct is used for evaluation. More LLM agents can be applied for experiments.

  3. The direct ablation study is missing for the conclusion that "Rebuilding the candidate sets at every decision reduces the linear expected excess of frozen sets to bounded excess". In addition, Fig. 3 and Table 1 do not include a baseline for frozen-set index optimism.

  4. The proofs of THEOREM 4 and THEOREM are not provided in detail. There is currently a lack of quantifiable correspondence between multi-source experiments and multi-source theories.

  5. There is no reproducibility statement. The code and the run records can be released anonymously.

  6. The LLM agent task experiments in Table 2 only show methods such as rate optimism, MWA, and Myopic, but do not include any MLE baselines.

  7. Weights are fixed and known, whereas the priorities of agents may change during task execution; therefore, they must be calibrated.

  8. More state-of-the-art schedulers should be included for experiments.

Questions for authors
  1. For Assumption 3, the authors just assume that all weights g1, . . . , gN are known and constant over the horizon under consideration. However, no method is provided for estimating these weights, nor is there any evaluation of these weights. Are they based on task requirements, access history, or error outcomes?

  2. Regarding Assumption 1, the authors require each source to evolve independently as Change events are independent across sources and slots. Eq. (2) then accounts for the total loss across all sources following a refresh at a given time slot. In this scenario, does refreshing one source provide information about the evolution of other sources? Alternatively, are other replicas updated synchronously as a result?

2 comments

We thank the reviewer for the detailed list. Each point below is answered with a change to the paper, and most with a new experiment.

Weakness 1: The revision states, after each assumption, where it holds, and points to a new appendix that tests what happens when it fails.

Weakness 2: We ran the task with two further models under the same prompt, tools, questions, decoding and scoring: Llama-3.1-8B-Instruct and Qwen2.5-1.5B-Instruct. For the more capable models, scheduler rankings by agent accuracy closely follow those by copy accuracy, and UCB-WIRS consistently outperforms rate optimism. For the weaker model, accuracy remains limited even with fully fresh copies, indicating that model capability is the main bottleneck and improved scheduling offers little benefit. These findings indicate that gains in copy accuracy translate into better agent performance to the extent that the agent can effectively use the information it receives.

Weakness 3: We ran the ablation in the class where the corollary is proved and in the Table 1 setting. In both, the two rules differ only in when the plausible set is rebuilt. The ablation supports the separation in Corollary 1: freezing the plausible set can turn the exclusion of useful rates into permanent source abandonment and linear excess, whereas rebuilding it at every decision prevents this failure and yields bounded excess under the corollary’s assumptions. The separation becomes apparent when a short observation sequence can eliminate all useful rates. Under the default settings, abandonment is rare and the two rules perform similarly. Reopening therefore guards against permanent loss of feedback, but does not uniformly improve finite-horizon performance or guarantee bounded excess outside the theoretical assumptions. The Thompson-sampling comparison shows a similar sensitivity to update timing: retaining samples between visits can leave useful sources unvisited for prolonged periods, while resampling at every slot improves performance. This indicates that the failure mechanism extends beyond our algorithm. The revision adds frozen-set index optimism to Table 1, Figure 3, and Table 2, and reports the full ablation in a new appendix.

Weakness 4: The complete proofs has shown in Appendices C to E. The revision adds the roadmap below after each theorem and at the head of each appendix section.

Weakness 5: The revision adds a Reproducibility Statement.

Weakness 6: Table 2 now contains the three MLE variants, the frozen rule and both Thompson-sampling variants: eleven budgeted schedulers and the full-refresh reference with Qwen2.5-7B.

Weakness 7: Because the index is linear in g_i, UCB-WIRS can use the current weights at each decision without otherwise changing the algorithm, although the theoretical guarantees assume constant weights. The experiment shows that using current weights keeps performance close to the known-rate benchmark, while recalibration from access counts with forgetting recovers most of the loss caused by changing priorities and outperforms estimation without forgetting. Stale weights can perform worse than uniform weights. The revision clarifies the use of current weights in Section 2, discusses stale weights as an empirical limitation in Section 7, and reports the experiment in the robustness appendix.

Weakness 8: The revision adds four more state-of-the-art schedulers: Thompson sampling on the grid posterior; UCWhittle (Wang et al., 2023), the optimistic Whittle-index learner for restless bandits; BLLCε (Kolobov et al., 2019), the learning crawler; and its planner BinaryLambdaCrawl(ε) (after Azar et al., 2018) run with the true rates, as a known-rate scheduler from the crawling literature. UCWhittle and BLLCε are our ports of the published algorithms to refresh feedback and a hard slot budget; a new appendix lists the adaptations.

Question 1: All three sources the reviewer names are admissible, and they enter as a product: g_i is the rate at which the agent uses source i times the expected loss when the value it uses is outdated. The first factor comes from the access history. The second comes from the task requirements or from observed error outcomes. In our agent task a stale use costs one wrong answer and questions are drawn with probability g_i/Σ_j g_j, so the weight is the access frequency.

Question 2: Under Assumption 1 the answer to both questions is no. Changes are independent across sources, so the bit returned by refreshing one source carries no information about another; this is the step in the proof of Proposition 1 that makes the age vector a controlled Markov chain. A refresh replaces only the copy of the refreshed source, and the other copies keep their content and their ages. The cost in Eq. (2) sums the weights of the copies that are stale after the slot's refreshes: a refreshed copy contributes zero, and every other copy contributes if it is stale.

I totally agree with reviewer m5WR that the proposed framework relies on strong assumptions and lacks sufficient practical justification. In addition, the theoretical guarantees lack rigorous support from empirical results, while dynamic weight estimation, baseline comparisons, and reproducibility remain inadequately addressed. Thus, I maintain my original score.

Reviewer_tm4MOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper models LLM agent cache refresh problem as restless bandit under a per-slot refresh budget. Each source changes independently at a constant rate and stale copies incur weighted costs.

With known rates, the authors prove threshold optimality and indexability, and recover the closed-form Whittle index of Avrachenkov & Borkar (2018), and derive a Lagrangian lower bound. With unknown rates, the authors demonstrate that the index ceiling is g/p and decreases with p, so taking a UCB on the rate leads to lower priority and can starve the source of the observations that would correct the estimate. The authors propose UCB-WIRS, which maximizes the index over a likelihood-ratio confidence set and rebuilds that set at every decision. With two-source class with B=1, they prove frozen sets give Ω(T) excess while reopening gives O(1). The extensions cover off-grid rates and multiple unknown sources under capacity margin and common cycle mean conditions. Experiments include synthetic sources and an agentic task that uses Qwen2.5-7B to answer order questions from cached supplier records.

Critical strengths
  1. critical insight is clear and correct. Parametric optimism is not equal to the optimism in decision due to the fact that the index is non-monotone in the rate. Under censored feedback, this problem will self-reinforce: the unvisited source does not provide observations and its rate estimation cannot be corrected. The description of this failure mode is clear in Proposition 3 and Corollary 2. The observation is also generally helpful to restless bandit domains.

  2. The theory part is clear and detailed. The Theorem 2 has a clear proof and the analysis cover off-grid rate, critical case c>=g2/p∗c >= g_2/p* and the the analysis of localization is comprehensive in Appendix C.

  3. Experimental results are consistent and significant. In table 1, when B=1, rate optimism accumulative excess cost is 286k, while UCB-WIRS is 7k. In table 2, when B=1, the accuracy gap is 19 points for 2 learners.

Critical weaknesses
  1. The contribution of known-rate is limited. Threshold optimality, indexability, and closed-form index and Lagrangian lower-bound is well-known, which together take about 1.5 pages of the main text.

  2. The novelty of Index optimism and reopening is less surprising. Wang et al. (2023) has maximized Whittle index in the confidence region, which is mentioned also in the related work. The novelty of this work is that feedback is censored, and the observation time is based on the policy itself. This should be strengthened in the paper.

  3. Strong baselines are required. Thompson sampling based on grid posterior is a natural comparison. It does not rely on the monotonicity of the index, so it may avoid the rate-optimism failure and the grid likelihoods are already computed. Also, the BLLC learner in Kolobov et al. (2019) and Wang et al. (2023) is discussed in related work, but not in the experiments section.

  4. Presentation issues. AI use statements has the mark "[TODO: Required]", and the critical Theorem 6 and Figure 5 is in the appendix rather than the main text.

Questions for authors
  1. Under table 1 setting, what is the performance of UCB-WIRS compared to Thompson sampling, Wang et al. (2023) and BLLC?

  2. Is there any practical systems update rate estimations like frozen rules? What is the practical meanings of Corollary 1?

2 comments

We thank the reviewer for the careful reading and the concrete suggestions. We ran the three baselines that were asked for and report the results for all three. Weakness 1: Threshold optimality, indexability, the closed-form index of Avrachenkov & Borkar (2018) and the Lagrangian bound are established, and the contributions of this paper are in learning. The revision reflects this in the following ways.

  1. Section 3 becomes background. The threshold and indexability theorems are merged into one statement credited to prior work, and their proof sketches move to Appendix A. The Lagrangian bound is shortened to one paragraph with its formal statement kept, since we use it to evaluate schedules and to certify the optimum in Proposition 2 and Theorem 6.
  2. The known-rate results are no longer listed as a contribution. Two known-rate items stay in the main text because the learning results depend on them: the closed form with Remark 1 (the index is non-monotone in the rate, with ceiling g/p), and Proposition 2, the exact hard-budget optimum of the two-source class against which our regret is measured.

Weakness 2: We agree that maximizing the index over a confidence region appears in Wang et al. (their problem P_m), and the revision says so directly. What is new here comes from the feedback model. However, Wang et al. observe every arm’s state at every step, regardless of whether it is pulled. Our sources return a single (Bernoulli(1-(1-p)^h)) bit only upon refresh at the policy-chosen age. The policy thus determines whether its errors can be corrected, with three consequences absent under observed states: a rate UCB can permanently stop observation (Proposition 3, Corollary 2); the timing of rebuilding the plausible set separates linear from bounded excess (Corollary 1); and Fisher information tends to zero with age, requiring bounded visit ages before concentration applies (Theorem 4). Wang et al. analyze UCW-value but leave index maximization (UCW-penalty) as an unanalyzed heuristic. In our model, the value-maximizing transition uses the smallest plausible rate for every penalty and state. And then we analyze index maximization itself. Their (O(H\sqrt{T\log T})) regret is against the Whittle threshold policy under the Lagrangian objective. Our two-source result gives (O(1)) expected excess over the exact hard-budget optimum when the unknown rate is on the grid and (c<g_2/p^*), and vanishing average excess otherwise (Theorem 4). For multiple unknown sources, excess over known-rate WIRS is bounded under Theorem 6’s capacity and cycle conditions. Moreover, we also tested UCWhittle under refresh feedback, which confidence region requires observed transition counts. The revision adds a paragraph on refresh feedback to Section 4 and clarifies these distinctions from Wang et al. in the introduction and related work.

Weakness 3: We implemented all three from the original papers, ported them to refresh feedback and the slot budget, and ran them on the instances and paired trajectories of Table 1.

Weakness 4: These presentation issues have been fixed.

Question 1: We have added the comparison to Table 1.

Question 2: Yes. The frozen rule is the event-driven design: per-source state is recomputed when a fetch returns and is then used unchanged until the next fetch. It is the natural implementation, because the point estimate changes only when new data arrive, and it costs O(B) updates per slot in place of O(N). For example: HTTP caches compute a heuristic freshness lifetime when a response is stored, commonly a fraction of the time since its last modification, and do not revise it until revalidation; Adaptive time-to-live schemes and crawl schedulers that enqueue a next-due time at fetch time work the same way; and change-rate estimators in incremental crawlers are updated at each access.

Thank you for the response. Most of my concerns are resolved and I raise my score to 3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.