Paying for Stale Knowledge: Stable Task Markets for LLM Agents Whose Knowledge Expires

When a platform routes tasks to a pool of language-model agents, each agent's usefulness on a topic quietly erodes as the world moves past its training cutoff. Elections happen, prices change, office holders turn over. A platform that matches tasks to agents using yesterday's quality estimates loses accuracy, and it also creates incentives to leave. A requester whose questions keep going to an agent with outdated knowledge would do better by contracting directly with a fresher agent. In matching-market theory, that pair is a blocking coalition: a group that gains by walking away from the platform's assignment. The platform can prevent this only by paying a subsidy. This proposal measures that subsidy, attributes it to stale knowledge, and shows how to reduce it.

The central bet is that knowledge obsolescence is not generic drift. It has a known structure. Each agent has a published cutoff date. Facts in a topic have lifespans that can be predicted from text. Agent quality therefore decays along a survival curve whose shape is largely known before any feedback arrives. A matching algorithm that builds this curve into its uncertainty estimates should see expiry coming and re-match early. Algorithms that treat change as an unknown shock must instead wait for poor outcomes before reacting. The quantity we expect to fall is the cumulative stabilizing subsidy, not only accuracy.

Core Claim

Learning Equilibria in Matching Markets with Bandit Feedback supplies the method we build on. It learns matchings with payments from noisy feedback. It defines Subset Instability, the largest gain any coalition could get by defecting, and proves this equals the minimum subsidy that keeps the market stable. Its primal-dual upper-confidence-bound algorithm reaches $\tilde{O}(N\sqrt{nT})$ regret on this measure, but only under the assumption that preferences are stationary.

Mitigating Temporal Misalignment by Discarding Outdated Facts supplies the second ingredient. It predicts how long a fact will stay true and lowers model confidence once the elapsed time exceeds that prediction. That paper treats isolated question answering and never asks what staleness costs a multi-agent system.

Our claim is that combining the two gives a market algorithm whose confidence intervals widen according to predicted fact survival. This algorithm should incur measurably less cumulative Subset Instability than stationary or generically non-stationary learners at equal welfare. The gain should be largest around expiry events, and it should shrink toward zero as the lifespan predictor's accuracy falls to chance. That last condition is what makes the claim falsifiable.

Research Program

Utility model. The model links fact lifespans to agent quality. For agent $a$ with cutoff date $\tau_a$ and task category $c$, we write expected task utility at time $t$ as

$$u_{a,c}(t) = r_{a,c} + p_{a,c}\, S_c(t - \tau_a) - k_a,$$

where:

  • $r_{a,c}$ is the accuracy the agent gets from retrieval regardless of cutoff;
  • $p_{a,c}$ is the extra accuracy it gets from parametric (weight-stored) knowledge while that knowledge is valid;
  • $S_c(\cdot)$ is the fraction of category-$c$ facts still true after a given elapsed time, which is the survival curve implied by the lifespan distribution;
  • $k_a$ is the agent's cost per task.

Requesters value correct answers. Agents and requesters both have outside options. True utilities are known to the simulator, so the true Subset Instability of any matching-plus-payment outcome can be computed exactly as a linear program. Defection can therefore be measured without assuming anything about how agents behave.

Algorithm. We modify the primal-dual algorithm of Jagadeesan et al. in one place. Each observation of agent $a$ on category $c$ is discounted by the survival probability elapsed since that observation was made. The survival probability comes from the lifespan predictor, and the cutoff dates are public. Confidence widths grow most quickly exactly where facts are expected to expire. Everything else is unchanged: the optimistic matching step, the payment step from the dual, and the subsidy accounting.

Theory. We aim for a bound on Subset Instability under piecewise-stationary utilities whose change points follow a known hazard. The comparison is the standard piecewise-stationary analysis, where an unknown number $M$ of change points enters as roughly $\sqrt{MT}$ because each change must be detected from losses. Our hope is that a correctly specified hazard removes most of that detection cost, leaving a term that scales with how wrong the hazard is. We treat this as a target, not a promised result.

Testbed. We build a weekly task market from two sources:

Agents are open models with different cutoffs, each in three configurations: closed book, retrieval over an old Wikipedia snapshot, and web search. These mirror the configurations RealTime QA compares. Task categories come from topic clustering. Lifespan predictions come from the duration model trained on TimeQA and TimePre, following Zhang and Choi.

Cross-check against prior allocation work. As a secondary testbed, we re-run the allocation setting of Social Welfare Function Leaderboard: When LLM Agents Allocate Social Welfare. In that benchmark, LLM allocators distribute HotpotQA and MATH tasks to 12 recipient models, and the authors found allocators cling to agents' initial "resumes" rather than observed performance. We add two things it lacks: scheduled capability decay and recipient outside options.

Baselines

Naive reference points. We run two. The first is a stationary greedy allocator that maximizes estimated welfare from all past observations, with no payments beyond posted prices. The second is "subsidize everything": pay each agent its outside option plus the maximum observed gain. This is trivially stable, but it marks the welfare floor of buying stability with money. Together they bound the tradeoff curve from both ends.

Strongest existing method. This is the stationary primal-dual algorithm of Learning Equilibria in Matching Markets with Bandit Feedback, the only method in the file that explicitly controls Subset Instability. That paper reports regret bounds, not empirical numbers. We found no reported empirical result on Lacuna for Subset Instability under non-stationary or obsolescent utilities, so our runs of it establish the reference number.

Generic non-stationary variants. We give the same algorithm a sliding window and an exponential discount, and tune window or discount rate on held-out weeks.

LLM allocator. We use DeepSeek-V3 prompted with the full outcome history. On the SWF benchmark it led with fairness 0.594 and ROI 53.89, and the same paper reports GPT-5-High placing 20th with a score of 17.97. We report its SWF score in a no-defection mode for continuity with that paper, then measure its Subset Instability in our market.

Fairness rules. All learners share the same agent pool, the same task stream, the same total feedback budget, and the same number of tuning trials on held-out weeks.

Ablations isolating the key ingredient. We compare three versions of the survival curve: an oracle curve computed from true answer-change dates, the curve from the predicted lifespan, and a curve with no prior that is fitted online.

What counts as winning. The proposal wins if the predicted-lifespan version achieves lower cumulative Subset Instability than the tuned sliding window at matched welfare (within one standard error), across seeds and agent pools.

Why not just…?

Why not just use a sliding-window version of the existing algorithm? This is the real threat, and we take it seriously. If expiry events are frequent and roughly uniform in time, a well-tuned window adapts almost as well as any prior. Our advantage can come only from advance knowledge of when specific categories expire, which lets the algorithm re-match before losses accumulate. The oracle, predicted, and windowed comparison settles the question. If the oracle curve beats the window but the predicted curve does not, the bottleneck is the lifespan predictor, which Zhang and Choi report gets durations right for 65% of temporally dependent facts within a three-year window. If even the oracle fails to beat the window, the core claim is wrong and we will say so.

Why not just give every agent live web search every round, so nothing is stale? Retrieval costs money, which enters welfare directly through $k_a$. Retrieval also does not remove staleness. SituatedQA reports models 15 points less accurate on updated facts than stable ones even with an updated corpus. RealTime QA attributes 34% of errors to retrieval failures and finds models revert to outdated knowledge instead of abstaining. "Always retrieve" is a configuration in our pool, so the market can choose it where it pays off. The experiment shows whether a market that routes selectively dominates it.

Why not just let a strong LLM allocate with the full history in context? The evidence suggests it will anchor on stale information. Can Agent Memory Systems Track Evolving State? finds that models given full histories, and even oracle context, still answer with superseded values, and that step-by-step reasoning made this worse. Can Large Language Models Keep Up? Benchmarking Online Adaptation to Continual Knowledge Streams finds that thinking modes increase distraction by irrelevant stream content. The SWF leaderboard's resume-anchoring finding points the same way. Our experiment adds what none of these measured: the subsidy such an allocator would need to keep agents from defecting.

Decisive Experiments

The main result is a plot of cumulative welfare against cumulative Subset Instability over the 52-week RealTime QA stream, one curve per method, traced by varying the payment margin. The predicted-lifespan learner should lie on the frontier.

The sharpest test is event-aligned. We center windows on known answer-change dates and compare instability spikes. The survival-aware learner should show smaller spikes, and some re-matching should begin before the change date. The windowed learner can react only afterward.

We then degrade the lifespan predictor by mixing in noise, and expect the advantage to vanish smoothly. This dose-response curve is what separates a real mechanism from tuning luck.

Finally, in the decayed SWF setting, we test whether adding outside options turns the leaderboard's resume anchoring into measurable defection. We also test whether swapping in our learner's quality estimates reduces it.