PaperlayerView exact revision on arXiv

Source-linked AI summary

When Should Agents Check External State? Budgeting Observations for Stored Intentions

Zhengkun Di, Bin Shi, Kai Sun, Yiming Xu, Bo Dong

arXiv:2609.37125v3cs.AI

TL;DR

Stored intentions can require costly external checks, but existing systems do not allocate repeated checks under a shared budget. BudgetPM trains local-value and future-aware policies with hard-budget execution; across benchmarks and backbones, Static leads adapted memory-agent workflows, while Sequential improves results under severe scarcity.

  • Problem

    Prospective-memory systems decide when intentions need attention but do not allocate repeated external-state checks when those checks compete for limited observation capacity.

    Source: §1 · p. 1

  • Method

    BudgetPM trains Static to estimate current check value and Sequential to imitate offline full-episode schedules, then deploys both with pre-query information through a shared hard-budget executor.

    Source: §1 · p. 2, §6 · p. 9

  • Results

    Across two benchmarks and three backbones, Static leads adapted Mem0/PMA workflows; under severe scarcity, Sequential exceeds the strongest natural schedule by 1.92–2.58 Set F1 points.

    Source: §6 · p. 9

  • Takeaways & Limitations

    Local-value learning suffices when capacity covers useful checks, while future-aware allocation adds value when present and future checks compete.

    Source: §6 · p. 9

Abstract

from arXiv · show

Prospective memory allows an agent to retain an intention tied to a future condition, but the stored intention does not reveal whether that condition currently holds. Checking it may require web access, multi-step tool use, and paid calls. Existing systems decide when intentions require attention, but do not allocate the resulting observations under a shared budget. We introduce the first resource-allocation formulation for the external observations required by stored intentions under a shared episode budget. BudgetPM offers two policy variants that share a hard-budget executor. BudgetPM-Static uses a lightweight Logistic scorer to learn whether a check improves the current decision. BudgetPM-Sequential distills full-episode hindsight schedules into a lightweight policy that decides when to spend or reserve capacity using only pre-query information at deployment. We evaluate BudgetPM against two public memory-agent systems, five matched controls, and four hand-designed monitoring or budget-adaptation rules. Across two benchmarks and three backbones, BudgetPM-Static outperforms adapted Mem0 and PMA workflows. On PM-Bench, its Logistic scorer reaches competitive quality--cost operating points alongside higher-capacity scorers and retains 99.9--100\% of unconstrained quality with 42--54\% fewer observations. Under severe scarcity and the same hard caps, BudgetPM-Sequential exceeds the strongest tested natural monitoring schedule by 1.92--2.58 Set F1 points. It reaches the same Set F1 and on-time recall with 16--33\% fewer observations. Matched attribution, exact-cost analysis, and a fixed-budget load intervention link this gain to competition between present and future opportunities. These results yield a demand--capacity design rule: local gating works when capacity covers demand, while future-aware supervision adds value when observations compete across time.

1 INTRODUCTION

Stored intentions can require costly external checks, but existing prospective-memory systems do not allocate repeated checks under a shared capacity limit. BudgetPM learns local or future-aware allocation policies, and its evaluations report quality gains and reduced observation use.

1 INTRODUCTION

  • A remembered instruction may require portal access and multiple tool calls to determine whether its external condition has been met, making repeated checks costly.The cited cost sources are Kapoor & Nair (2025) and Liu et al. (2025).Source: §1 · p. 1
  • Prospective-memory systems decide when an intention needs attention, but do not allocate repeated external checks when they compete for limited observation capacity.The passage cites Liu & Gabriel (2026), Wu et al. (2026), Zhang et al. (2026c), and Zhao & Wu (2026).Source: §1 · p. 1
  • Fixed intervals, deadline-focused checks, and backoff can work with predictable triggers or ample capacity, but preset schedules do not compare checking now with preserving capacity for later.When timing varies, these rules may delay detection, miss early changes, waste calls, or postpone detection after unchanged observations.Source: §1 · pp. 1–2
  • Across two benchmarks and three backbones, Static achieves the highest end-to-end task quality; Sequential beats the strongest natural schedule by 1.92–2.58 Set F1 points under severe scarcity.On PM-Bench, Static retains 99.9–100% of unconstrained quality with 42–54% fewer observations; Sequential matches the schedule’s Set F1 and on-time recall with 16–33% fewer observations.Source: §1 · p. 2
  • BudgetPM treats checks required by stored intentions as consumers of a shared episode budget and combines local-value estimation, offline schedule supervision, and hard-budget execution.Sequential distills full-episode schedules into a lightweight policy; future information is used only for offline supervision.Source: §1 · p. 2

2 RELATED WORK

Related work studies memory construction and retrieval, prospective triggers, cost-aware tool use, and sequential information gathering. BudgetPM focuses on allocating repeated external-state checks for stored intentions under limited capacity.

2 RELATED WORK

  • Memory and prospective-memory systems improve retention, retrieval, and trigger response, while BudgetPM addresses how repeated external-state checks should share limited capacity.The passage distinguishes systems such as PMA, which decides when to surface a reminder (Wu et al., 2026), and PIS, which decides whether a hidden-state query is needed (Zhao & Wu, 2026).Source: §2 · p. 2
  • Cost-aware interaction systems allocate computation or tool calls under cost, workload, or quota constraints; BudgetPM treats intention-driven checks as consumers of a shared call budget.The passage names FrugalGPT, RouteLLM, and WISERouter (Chen et al., 2023; Li et al., 2026), as well as BATS, CostBench, and When2Tool (Liu et al., 2025; 2026b; Sun et al., 2026).Source: §2 · p. 2
  • Sequential information-gathering frameworks connect present choices to future resource availability; BudgetPM tests when current-value selection suffices and when allocation across time matters.It constructs full-episode schedules offline and distills them into a lightweight deployment policy.Source: §2 · p. 3

3 BUDGETPM: ALLOCATING EXTERNAL-STATE CHECKS

BudgetPM allocates queries to external-state resources identified by active intentions. Static learns whether a check improves the current decision, while Sequential imitates budget-constrained full-episode schedules; both share a hard-cap executor.

3 BUDGETPM: ALLOCATING EXTERNAL-STATE CHECKS

  • BudgetPM receives active intentions, derives candidate resources, and routes either policy’s proposals through a shared executor that enforces per-step and episode budgets.Frozen trajectories supply local Outcome labels for Static and hindsight-DP schedule labels for Sequential; deployment uses only pre-query inputs.Source: §3 · p. 3, Figure 1 · p. 3

3.1 PROBLEM FORMULATION

  • The problem is to select queryable resources across episode steps under a total cost budget, with task quality measured over the resulting trajectory.A resource may serve several intentions, and querying it incurs a known positive cost.Source: §3.1 · pp. 3–4

3.2 BUDGETPM-STATIC: LOCAL OUTCOME SUPERVISION

  • Static labels a resource as useful when adding its cached evidence improves the current decision under a comparison set that excludes that resource.Recomposition holds the recorded pre-query state fixed and creates training labels; it does not describe deployment state updates.Source: §3.2 · p. 4

3.3 BUDGETPM-SEQUENTIAL: FUTURE-AWARE SCHEDULE SUPERVISION

  • Sequential uses dynamic programming to maximize the frozen episode score under budget, removing partial schedules dominated on the statistics used by the score.Full-episode information constructs offline targets only.Source: §3.3 · p. 4

3.4 POLICY FITTING AND ONLINE ALLOCATION

  • Both policies score candidates before any external call, threshold proposals, and pass the resulting plan to an executor that enforces remaining-budget and per-step limits.Sequential adds observable budget and history features; fitting and threshold calibration use development data and out-of-fold predictions.Source: §3.4 · pp. 4–5

3.5 EXACT-COST STRUCTURAL HEADROOM

  • Exact-cost structural headroom compares hindsight DP with current-greedy at the same query cost; a positive difference means a better full-episode allocation exists at that cost.Both teachers use the same current-step outcomes; only DP compares future opportunities, so headroom diagnoses temporal allocation potential rather than learned-policy gains.Source: §3.5 · p. 5

4 EXPERIMENTAL SETUP

The evaluation separates end-to-end system performance, matched supervision and scorer comparisons, and tests of temporal allocation. It uses two benchmarks, explicit observation budgets, paired comparisons, and a fixed-budget opportunity-load intervention.

4 EXPERIMENTAL SETUP

  • The evaluation measures end-to-end effectiveness, isolates local and temporal supervision with matched controls, and tests whether allocation across time can improve quality.Exact-cost teachers and a fixed-budget load intervention probe when temporal allocation can help.Source: §4 · p. 5
  • PM-Bench reports episode Set F1 and temporal on-time recall, while GoodAI LTM reports macro accuracy across prospective-memory and trigger-response components.PM-Bench includes visible, temporal, and latent-state cues; GoodAI gates semantic-verifier calls.Source: §4 · p. 6
  • PM-Bench caps B5–B80 permit 10–168 queries, and GoodAI caps B20–B80 permit 10–41; PM-Bench temporal tests use unit costs and a two-query per-step cap.The caps are based on mean feasible-query counts of 209.4 for PM-Bench and 51.5 for GoodAI.Source: §4 · p. 6
  • PM-Bench Outcome labels use singleton-versus-empty effects, and its schedule teacher retains cumulative true-positive and false-positive states while removing dominated states.Scenario timing and provider events are fixed independently of query decisions, so policies face the same opportunity sequence.Source: §4 · p. 6
  • At B60, Static is compared with Mem0 and PMA across 30 seeds and three backbones; matched tests share the candidate space, controller, and executor.The named backbones are Llama-3-8B, Qwen2.5-14B, and Qwen3-14B.Source: §4 · p. 6
  • Matched Due changes only the supervision label versus Outcome-trained Static, which shares its features, Logistic model, development data, calibration, ordering, and executor; LambdaMART and fixed hurdle/pairwise Ensemble replace the Logistic scorer.The three natural schedules are swept over 20 caps to form Set F1 and on-time recall curves against realized observation cost; the B10 intervention fixes a 21-query cap and adds 21 latent-state opportunities at k = 3.Source: §4 · pp. 6–7

5 RESULTS

BudgetPM-Static leads complete-system comparisons, while Sequential improves observation efficiency under severe scarcity. Future-aware allocation adds value when observation demand competes across time, but not when capacity covers demand.

5.1 BUDGETPM-STATIC LEADS COMPLETE-SYSTEM COMPARISONS ACROSS BACKBONES

  • Across six backbone–benchmark combinations, BudgetPM-Static achieves the highest end-to-end task quality, beating strongest Mem0/PMA workflows by 0.362–0.452 PM-Bench Set F1 and 0.433–0.920 GoodAI accuracy.With Qwen3-14B, the workflow reaches 0.885 PM-Bench Set F1 and 0.944 GoodAI accuracy; a gate trained with Llama transfers to both Qwen backbones without retraining or recalibration.Source: §5.1 · p. 7, Table 1 · p. 7

5.2 A LIGHTWEIGHT OUTCOME GATE REACHES THE LEARNED QUALITY–COST FRONTIER

  • Static retains 99.9% of unconstrained All relevant F1 at B60 with 54.1% fewer queries, and preserves full 0.820 F1 at B80 with 41.9% fewer.At matched costs, Static and LambdaMART lead at different operating points, so additional scorer capacity does not produce a consistent gain.Source: §5.2 · p. 8, Table 2 · p. 8
  • On GoodAI, Static reaches 0.946/0.951 accuracy at B60/B80, gaining 1.33/1.67 percentage points over the task-specific Due gate while using 0.24/0.44 fewer mean queries.These results extend the quality–cost advantage to semantic verification.Source: §5.2 · p. 8

5.3 SEQUENTIAL IMPROVES OBSERVATION EFFICIENCY OVER NATURAL MONITORING

  • Under the same hard caps, Sequential exceeds Deadline-Outcome by 1.92–2.58 Set F1 points at B5/B10 and matches its Set F1 and on-time recall with 33% and 16–17% fewer observations.Sequential also has higher mean F1 than Pacing-LB in all four comparisons.Source: §5.3 · p. 8, Table 3 · p. 8

5.4 FUTURE-AWARE SUPERVISION EXPLAINS THE LOW-BUDGET GAIN; 5.5 OPPORTUNITY COMPETITION DETERMINES THE SCARCITY BOUNDARY

  • Sequential improves over Myopic on both disjoint tests; at the same cost, hindsight DP exceeds current-greedy by +0.00737 F1 at B5 and +0.00367 at B10.Requiring the same number of queries at every step removes the gap, attributing it to allocation across time.Source: §5.4 · p. 8, Figure 2 · p. 9, §5.5 · p. 9

5.5 OPPORTUNITY COMPETITION DETERMINES THE SCARCITY BOUNDARY

  • Future-aware gains and exact-cost headroom are positive at B5/B10 and zero at B15/B20; at fixed B10, raising opportunity load from k = 0 to k = 3 raises headroom from 0 to +0.00652 F1.On boundary weeks, Static exhausts the B5 and B10 budgets while 544 and 277 positive opportunities remain, respectively, spread nearly uniformly across episode quarters.Source: §5.4 · pp. 8–9, Figure 2 · p. 9, §5.5 · p. 9

6 DISCUSSION AND CONCLUSION

BudgetPM frames external-state checks for stored intentions as a resource-allocation problem, with local-value policies for sufficient capacity and future-aware allocation when checks compete. Its experiments show advantages for Static across benchmarks and for Sequential under severe scarcity.

6 DISCUSSION AND CONCLUSION

  • BudgetPM treats checks for stored intentions as resource allocation: Static estimates current observation value, while Sequential distills future-aware offline schedules into a pre-query policy.Both variants use lightweight policies and a shared executor that enforces hard budgets.Source: §6 · p. 9
  • Across two benchmarks and three backbones, Static leads adapted Mem0/PMA workflows; under severe scarcity, Sequential exceeds the strongest natural schedule by 1.92–2.58 Set F1 points.The natural schedule needs 1.19–1.50× as many observations to match Sequential’s Set F1 and on-time recall.Source: §6 · p. 9
  • The demand–capacity boundary separates regimes: local-value learning suffices when capacity covers useful checks, while future-aware allocation adds value when present and future checks compete.The paper frames stored intentions as future demand for external evidence and proposes jointly managing intentions and the observations needed to act on them.Source: §6 · pp. 9–10

A.1 DATA SPLITS AND EVALUATION ROLES

The data description identifies the PM-Bench split roles and summarizes the benchmark setup and BudgetPM pipeline.

A.1 DATA SPLITS AND EVALUATION ROLES

  • OOF folds keep each complete week/scenario, or paired base seed, intact.Source: §A.1 · p. 12
  • Each PM-Bench split pair contains one k = 0 week and one k = 3 week.Standard-budget studies use the released V9 generator; controlled-load pairs use a frozen paired generator.Source: Table 4 · p. 12, §A.1 · p. 12
  • The PM-Bench pipeline retains the benchmark’s state providers, action space, and Set F1 scorer, with LLM operations followed by deterministic verification and menu matching.GoodAI uses 12 development trajectories and evaluates seeds 4000–4029.Source: §A.1 · p. 12

A.2 FEATURES, TRAINING, AND CALIBRATION

BudgetPM constructs pre-query features and fits frozen gates from replayed outcomes, then evaluates its complete workflow against public memory-agent baselines under different execution constraints.

A.2 FEATURES, TRAINING, AND CALIBRATION

  • The 27 PM-Bench gate features use stored trigger, retrieval, resource, and timing information available before a provider is invoked, excluding query results, future observations, and labels.GoodAI adds seven semantic-resource and memory features; Static's standardized Logistic sigmoid is a positive-label score, not a calibrated posterior probability.Source: §A.2 · pp. 12–14

A.3 OUTCOME-LABEL CONSTRUCTION BY FROZEN REPLAY

  • Frozen replay constructs Outcome labels from cached provider results and deterministic recomposition, after which fitted scorers and thresholds are reused across deployment episodes.PM-Bench compares singleton versus empty evidence; GoodAI uses a leave-one-out deletion comparison.Source: §A.3 · p. 14

B.1 COMPLETE-SYSTEM BASELINE PROTOCOL

  • The complete-system comparison evaluates BudgetPM-Static at B60 against Mem0 and PMA across three backbones, while those adapters have no BudgetPM episode cap or learned observation gate.All systems use the same 30 held-out seeds; BudgetPM uses its Static policy and hard-cap executor.Source: §B.1 · p. 14

B.2 BACKBONE TRANSFER WITHOUT RETRAINING

Static transfers across backbones without retraining and shows quality–cost advantages across matched gates, budget settings, and unconstrained references. The accompanying analyses also examine scarce-budget allocation.

B.2 BACKBONE TRANSFER WITHOUT RETRAINING

  • At B60, the frozen Static gate transfers across Llama-3-8B, Qwen2.5-14B, and Qwen3-14B; Qwen3-14B reaches 0.8847 PM-Bench Set F1 and 0.9444 GoodAI accuracy.The gate is used without retraining or threshold recalibration.Source: §B.2 · pp. 14–15, Table 7 · p. 15

B.3 STATIC GATING AT MATCHED REALIZED COST

  • At matched PM-Bench costs, Static gains 0.0250 F1 over the task-specific Due gate at 60 queries and reaches competitive operating points alongside LambdaMART.LambdaMART leads by 0.0055 F1 at 40 queries, while Static leads by 0.0037 at 60; differences narrow at 90 and 100 queries.Source: Table 8 · p. 15, §B.3 · p. 15

B.4 RANDOM-FEASIBLE AND UNCONSTRAINED BASELINES

  • At PM-Bench B80, Static matches the unconstrained 0.820 Set F1 while using 41.9% fewer queries.Random selection trails learned gating throughout the budget range.Source: Table 10 · p. 16, §B.4 · p. 16

B.5 MATCHED OUTCOME–DUE SUPERVISION CONTROL

  • At PM-Bench B20, Outcome supervision achieves 0.760 F1 with 5.76 fewer queries than Due-state supervision, and improves F1 at B40–B80 and across GoodAI budgets.The matched comparison holds gate architecture, data, calibration, and executor fixed.Source: Table 11 · p. 16, §B.5 · p. 16

B.6 REMAINING-BUDGET PACING

  • On PM-Bench, Static reaches Pacing's B60/B80 quality with 21.10/14.80 fewer queries, while GoodAI Pacing reaches 0.967/0.971 accuracy at B60/B80 with less than half an additional query.Remaining-budget adaptation complements the shared executor when increased utilization benefits the task.Source: §B.6 · pp. 16–17, Table 12 · p. 17

B.7 INTERPOLATION TO UNSEEN BUDGETS

  • On GoodAI, Static reaches 0.904/0.956/0.953 accuracy at B30/B50/B70 and leads at B70 by 0.012 while using 0.53 fewer queries.Static leads at all three PM-Bench interpolation budgets.Source: Table 13 · p. 17, §B.7 · p. 17

B.8 OUTCOME-LABEL SAMPLE EFFICIENCY

  • The outcome-label sample-efficiency experiment fits the local gate on subsets of development trajectories and evaluates it on the same 30 analysis seeds.The supplied passage describes the evaluation design, not its outcome.Source: §B.8 · p. 17

C.1 BUDGET UTILIZATION AND ORACLE-GAP DECOMPOSITION

  • At exact realized cost, hindsight DP exceeds current-greedy by 0.0063 at B5 and 0.0028 at B10, with no difference at B20/B40; positive headroom is attributed to temporal allocation.The analysis also notes that the larger DP–reconstructed-Static gap reflects better ranking of current observations.Source: Table 14 · p. 18, §C.1 · p. 18

C.3 SCARCITY BOUNDARY ACROSS FOUR BUDGETS

The scarcity boundary occurs where current-greedy and hindsight-DP align: learned policies become identical at B15/B20, while Sequential improves severe-scarcity allocation and reaches the same service point with fewer observations.

C.3 SCARCITY BOUNDARY ACROSS FOUR BUDGETS

  • Myopic and Sequential are identical at deployment at B15/B20, where current-greedy and hindsight-DP agree throughout development; their disagreements are concentrated at B5 and B10.At B5, teachers disagree on 310 steps; at B10, on 16 steps.Source: §C.3 · p. 19, Table 17 · p. 19

C.3.1 NATURAL MONITORING SCHEDULES AND QUALITY–COST FRONTIERS

  • Sequential reaches Deadline-Outcome's mean Set F1 and on-time recall with 33% fewer observations at B5 and 16–17% fewer at B10.Deadline-Outcome is the strongest tested natural schedule at matched operating points.Source: Table 20 · p. 20, §C.3.1 · p. 20, Table 19 · p. 20

C.3.2 PACING CALIBRATED FOR LOW BUDGETS

  • Pacing-LB adds one low-budget threshold knot to a separate frozen Static scorer copy, selecting 0.99 at B5 and 0.925 at B10.Selection uses development weeks and maximizes mean week-level Set F1, with lower cost and then higher threshold as tie breakers.Source: §C.3.2 · p. 20

C.3.3 HELD-OUT EXACT-COST ANALYSIS

Exact-cost analyses locate severe-scarcity headroom in across-step allocation, and controlled load increases Sequential's learned gain. Binary Outcome supervision also compares favorably across price profiles.

C.3.3 HELD-OUT EXACT-COST ANALYSIS

  • Exact-cost DP exceeds current-greedy by 0.00737 at B5 and 0.00367 at B10, with zero difference at B15/B20; costs are matched exactly.A restricted optimizer finds zero within-step headroom in all 120 week–budget cells, so positive B5/B10 headroom comes from changing query counts across steps.Source: §C.3.3 · p. 21, Table 21 · p. 21

C.4 CONTROLLED-LOAD STUDY DESIGN

  • At B10, Sequential's F1 gain over Myopic rises from 0.00407 at k = 0 to 0.00836 at k = 3, while using approximately 0.95 and 0.90 more queries, respectively.The compiler, policies, thresholds, executor, and paired evaluation are held fixed across load conditions.Source: §C.4 · pp. 21–22, Table 22 · p. 22

D.1 SUPERVISION TARGETS AND HETEROGENEOUS COSTS

  • Under heterogeneous costs, Binary Outcome/Logistic improves over Relevance/cost by +0.0358 and +0.0188 F1 under mild costs, and by +0.0069 and +0.0157 under skewed costs.Under unit costs, binary Outcome supervision matches richer-target quality with fewer queries than pairwise gain/cost.Source: §D.1 · p. 22

D.2 PAIRWISE RESOURCE-INTERACTION ANALYSIS

Pairwise interactions are exactly zero in nearly all evaluated PM-Bench candidate-resource pairs, supporting singleton-based Outcome supervision. The analysis evaluates local interactions when a development decision has at least two distinct candidate resources.

D.2 PAIRWISE RESOURCE-INTERACTION ANALYSIS

  • The analysis computes local pairwise interactions for PM-Bench development decisions with at least two distinct candidate resources.Source: §D.2 · p. 22
  • Table 24 compares marginal-target and heterogeneous-cost results, with cells reporting PM-Bench F1 and mean realized cost on analysis seeds 4000–4029.Source: Table 24 · p. 23
  • 99.47% of 4,709 candidate-resource pairs had exactly zero interaction, and the remaining 0.53% were nonpositive.Across 1,383 decisions, the median and 90th-percentile absolute interaction were zero; the maximum was 0.333.Source: §D.2 · p. 23

Related papers

Loading 2609.37125v3…