A personalized model running on a phone or an edge server goes stale as its user's tastes change. Refreshing it costs energy: a backward pass, and sometimes a radio transmission to an edge server. Today that refresh is either always on, which ignores the battery, or scheduled on a fixed clock, which ignores the user. We propose treating "when to update the personal model" as an energy-delay scheduling problem. The delay is not packet latency but staleness: the alignment loss that builds up while the deployed model lags the user's current preferences. We price staleness using the user's own incoming preference feedback. A scheduler in the style of Lyapunov optimization, a control method from wireless networking that keeps long-run averages within budget by tracking a running "debt" counter, then decides each moment whether to update a given user cheaply, update them fully, or wait.
The two-sentence version: wireless schedulers save energy by waiting until waiting is cheap, and personalization systems lose accuracy when they wait while the user drifts. Our scheduler waits exactly when the user's recent feedback says their preferences have not moved and the channel is poor, and it pays for an update as soon as the feedback shows the deployed model is mispredicting them.
Core Claim
The energy-delay literature prices delay linearly in queue backlog. The classic result is that average power approaches its minimum at rate $O(1/V)$ while backlog grows as $O(V)$, where $V$ is the operator's knob between energy and delay (Power-Delay Tradeoff in Multi-User Mobile-Edge Computing Systems). That paper decides between local and offloaded execution using closed-form CPU frequency and transmit power. Like nearly all of this work, it treats every unit of waiting as equally costly and every task's value as fixed.
The preference-drift literature shows that the cost of waiting is neither linear nor uniform across users. Right Now, Wrong Then models preferences with a time-varying Bradley-Terry model (a model where the probability of preferring one output over another depends on a reward function that changes over time). It counters drift by down-weighting old preference pairs, using a discount whose right value depends on a drift budget that has to be known in advance.
Our claim is that per-user staleness, estimated online from the log-loss of the deployed model on that user's newest preference pairs, is the right penalty for an energy-budgeted drift-plus-penalty scheduler. We expect this to beat two alternatives: time-since-update pricing, which is the age-based view common in networking, and fixed drift-detection thresholds. The advantage should appear specifically when drift is heterogeneous across users and bursty in time. If a well-tuned fixed threshold matches the scheduler in those regimes, the claim is false, and the experiments are built to show this.
Mechanism
Each user $i$ has a deployed personal model. Following PAL, this is a frozen shared backbone plus a low-dimensional weight vector over $K$ preference prototypes, which PAL shows can be refit from about 20 samples. Optionally, following P-ShareLoRA, the user also has a user-specific low-rank adapter on top of a shared projection. These two papers supply the model class. Their structure gives a natural two-tier action: a cheap refit of the prototype weights, or an expensive refit of the adapter, which can be done locally or offloaded over a fading channel.
As pairwise feedback arrives, we compute $g_i(t)$, a lower confidence bound on how much the deployed model's log-loss on user $i$'s pairs since the last update exceeds its held-out log-loss at fit time. This costs only a forward pass of a scalar reward head on data that is already being collected. The lower confidence bound keeps a handful of noisy pairs from triggering updates.
Let $E_i(a, h_i(t))$ be the energy of action $a$ for user $i$ under channel state $h_i(t)$. Let $\Delta_i(a)$ be the expected fraction of $g_i$ that action $a$ recovers, estimated from past updates. Let $\bar e$ be the per-slot energy budget. Each slot, the scheduler picks actions $a_i$ to solve
$$\min_{\{a_i\}} \; Z(t)\sum_i E_i(a_i, h_i(t)) \;-\; V \sum_i \Delta_i(a_i)\, g_i(t), \qquad Z(t+1)=\max\Big[Z(t)+\sum_i E_i(a_i,h_i(t))-\bar e,\;0\Big],$$
where $Z(t)$ is a virtual queue: running energy debt that rises when the scheduler overspends. The rule says to update user $i$ when $V$ times the staleness that would be recovered exceeds the debt-weighted energy price. Small staleness under a bad channel means wait. Large staleness means pay even on a poor channel. Accumulated debt raises the bar for everyone.
The virtual-queue device comes from On Preference-based Stochastic Linear Contextual Bandits with Knapsacks. That paper uses a Lyapunov virtual queue as an adaptive price that paces a depleting budget while learning a preference vector from duels. It assumes the preference vector is fixed, and its budget is a knapsack rather than a per-slot energy rate under fading. We change both: the preference target drifts, and the quantity being priced is staleness rather than a dueling reward.
Research Program
The theoretical piece adapts the standard drift-plus-penalty argument to a dynamic benchmark. We aim to show three things. First, the time-averaged energy overshoot vanishes as $O(V/T)$, which follows from the bound on $Z(t)$. Second, the time-averaged alignment loss is within $C/V$ of the best energy-feasible policy that knows the drift path, plus a term growing with the total drift variation. That variation term is where the analysis has to borrow from the dynamic-regret analysis in Right Now, Wrong Then. Third, $V$ is the only remaining knob. The scheduler does not need the drift budget in advance, because staleness is measured rather than assumed. That is the specific weakness of a pre-chosen discount that we are trying to remove.
A Lyapunov Drift-Plus-Penalty Method Tailored for Reinforcement Learning with Queue Stability leaves state-adaptive $V$ open, and it assumes stationary workloads and static task utility. We do not adapt $V$ itself. Instead, we make the penalty state-dependent, which reaches the same effect while keeping the guarantee.
Two other Lyapunov-plus-learning papers constrain the design. When Lyapunov Drift Based Queue Scheduling Meets Adversarial Bandit Learning shows that MaxWeight, the classic scheduler that serves the longest-weighted queue, breaks under noisy state estimates. Its fix, SoftMW, schedules queues with an adversarial bandit learner, and its sliding-window variant, SSMW, restarts that learner on epochs scaled to current queue lengths to track non-stationary service rates. This is why we use confidence bounds on $g_i$ rather than point estimates. Lyapunov-Stable Adaptive Control for Multimodal Concept Drift modulates learning rates with a Lyapunov controller, but it needs a ground-truth label at every step and has no notion of resource cost. Our signal is sparse pairwise feedback, and the quantity being controlled is energy.
The empirical piece builds a drifting multi-user preference stream on existing data, as described below, and pairs it with the multi-user mobile-edge simulation of Power-Delay Tradeoff in Multi-User Mobile-Edge Computing Systems for channel and energy costs. We will also measure the energy of actual refits on an edge-class device so that update costs are measured rather than modeled.
Baselines
The naive reference is never updating: a personal model fit once and served forever. This is the stationary regime in which Right Now, Wrong Then reports standard DPO collapsing to about 50–55% reward accuracy after a mid-stream preference flip. It sets the floor and costs zero update energy.
The unconstrained ceiling is always updating with the drift-aware learner: NS-DPO-style discounted refits after every new batch. The same paper reports reward accuracy holding above 60–70% under flips and gains of over 10% in gradual drift. This baseline ignores the energy budget, so we report its accuracy together with its energy. The proposal does not need to beat it on accuracy. It needs to reach most of its accuracy at a fraction of its energy.
The scheduling baselines all run the same learner, model class, data stream, energy model and budget $\bar e$, and each receives the same tuning budget (an equal-size grid on a held-out stream).
The first is periodic updating, with the period chosen to meet the budget on average.
The second, and the strongest competitor, is a tuned drift-trigger: update user $i$ whenever $g_i(t)$ exceeds a fixed threshold, with that one threshold tuned to meet the budget. It uses our staleness signal but no virtual queue and no channel awareness. If this baseline matches the scheduler, the virtual queue is not doing work.
The third is an age-based drift-plus-penalty ablation. It is identical to our scheduler except that $g_i(t)$ is replaced by time since the last update, which is the linear-delay pricing of the classic energy-delay work. This isolates whether the preference-derived penalty matters.
The fourth is a channel-blind ablation that uses our penalty but averages $E_i$ over channel states. It isolates the opportunistic waiting that is the energy-delay literature's main source of savings.
For the scheduling question itself, no reported result was found on Lacuna. No paper in the file evaluates energy-budgeted update scheduling for drifting personal models, so all scheduling baselines will be run by us. For the underlying personal-model accuracy, the reference number is P-ShareLoRA's 74.65% accuracy with Llama-3 8B on the top five Reddit TL;DR annotators (A Shared Low-Rank Adaptation Approach to Personalized RLHF). Our always-update ceiling should approximately reproduce it in the stationary segments.
Beating the field means three things at matched energy within 5% of budget. On the bursty heterogeneous streams, the scheduler must achieve higher prequential accuracy (accuracy on each incoming pair before training on it) than the tuned drift-trigger. It must strictly dominate the age-based ablation across the whole energy-accuracy curve. And it must show no loss against any baseline on stationary streams.
Why not just…?
Why not just update on a fixed schedule? A fixed period spends the same energy on a user whose tastes are frozen as on one in the middle of a shift. Under the heterogeneous streams described below, it must either over-update stable users or under-update drifting ones. The periodic baseline measures this directly. We expect it to be clearly dominated whenever drift varies across users, and close to competitive when drift is uniform. We will report the uniform case honestly.
Why not just trigger an update when feedback accuracy drops below a threshold? This is the real threat. Our rule reduces to a threshold rule in which the threshold is set by $Z(t)/V$ and by the current channel, so the scheduler differs only in how the threshold moves. A fixed threshold tuned to the average budget should be near-optimal when drift arrives at a steady rate. It should fail in two ways when drift is bursty: it overspends during a drift wave, causing budget violation or forced shutoff, and it underspends in calm periods. The burst-structured streams are designed to decide this question. If the tuned trigger is within noise of the scheduler there, we will report the contribution as the staleness signal plus channel awareness, not the virtual queue.
Why not just price delay by age, as networking already does? Age-based pricing treats every stale minute as equally costly. The drift literature, and the within-session fatigue shifts documented for assistive devices in Sharmita Dey's work, say the opposite. The age-based ablation tests this. If it matches our scheduler, preference feedback adds nothing beyond a clock.
Why not just make updates so cheap that scheduling is moot? If refitting only PAL's prototype weights is effectively free compared with serving the model, the energy constraint never binds and this proposal is unnecessary. We will measure the share of device energy spent on cheap and full refits. We restrict the claims to regimes where full adapter refits or offloaded refits are a material share of the energy budget. If the cheap tier alone recovers nearly all of the accuracy, that is itself a useful negative finding.
Proposed Experiments
The streams come from per-annotator data with known identities: Reddit TL;DR as used by PAL and P-ShareLoRA, and Pick-a-Pic v2, which has over 500,000 comparisons, run through the PAL codebase. To create a drifting synthetic user, we interpolate the user's latent preference weights between annotators, or between PAL prototypes, along three kinds of path: an abrupt flip, a gradual drift, and recurring bursts. The flip and gradual paths mirror the drift scenarios of Right Now, Wrong Then. The time-varying UltraFeedback and TV-HH variants from that paper provide a second, LLM-scale check. We will mix stable and drifting users in varying proportions, so that heterogeneity is controlled.
Energy and channel states come from the multi-user edge simulation with fading channels described in Power-Delay Tradeoff in Multi-User Mobile-Edge Computing Systems, calibrated with measured refit energy.
The metrics are prequential pairwise accuracy, time-averaged energy, budget violation, and the full accuracy-versus-energy curve swept over $V$, or over the threshold for the tuned trigger.
Three checks decide the outcome. The first is the bursty heterogeneous stream at a binding budget, where the scheduler must beat the tuned drift-trigger at equal energy. The second is the age-based ablation, which must be dominated if preference-derived staleness matters. The third is the stationary stream, where the scheduler should nearly stop updating and match the never-update model's accuracy at near-zero energy. That last result would show the system does not waste energy chasing noise, which is the failure mode the confidence bound is meant to prevent.
References
- Power-Delay Tradeoff in Multi-User Mobile-Edge Computing Systems
- Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift
- PAL: Sample-Efficient Personalized Reward Modeling for Pluralistic Alignment
- A Shared Low-Rank Adaptation Approach to Personalized RLHF
- On Preference-based Stochastic Linear Contextual Bandits with Knapsacks
- A Lyapunov Drift-Plus-Penalty Method Tailored for Reinforcement Learning with Queue Stability
- When Lyapunov Drift Based Queue Scheduling Meets Adversarial Bandit Learning
- Lyapunov-Stable Adaptive Control for Multimodal Concept Drift
- Redefining Robot Generalization Through Interactive Intelligence