- 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
-
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.
-
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
-
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.
-
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
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.
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.