CS Paper Radar

Differential Refresh of Materialized Derived State: From a Single-Age Equivalence Limit to an Optimal Per-Partition Allocation, with a Real-System Validation on Materialized Views

Amit Rajula

cs.LG cs.DC ·submitted 2026-10-07 06:15 UTC · v2

Abstract

Materialized views, cached aggregates, and trained models are all derived state: query results precomputed from base relations that begin to age the instant they are built, because the data they summarize keeps changing. A common way to keep such state fresh is to replace a fixed recompute cadence with an adaptive trigger -- a weighted staleness score that recomputes when accumulated base-data change crosses a threshold. We show this is the wrong lever and identify the right one. First, an equivalence limit: any refresh trigger that is a static, strictly monotone function of a single shared age of a globally-recomputed artifact is operationally equivalent to a calibrated periodic timer, so a global weighted staleness budget cannot schedule a recompute that a uniform timer could not. The escape is to enlarge the state: refresh partitions (the groups of a GROUP BY, per-tenant views, or data segments) differentially, each on its own schedule. We solve the resulting budget-allocation problem: the optimal per-partition recompute rate is proportional to the square root of partition risk sqrt(w_j*lambda_j), and the policy never costs more than the uniform timer, beating it by a closed-form Cauchy-Schwarz "price of uniformity" that grows with heterogeneity. We validate three ways -- analytic, discrete-event simulation, and a real relational engine (SQLite) maintaining materialized GROUP BY views with real SQL and wall-clock timing -- where the policy lowers realized weighted staleness by 14-15% at matched recompute count, winning on every run, while a naive per-partition exposure threshold does not reliably help. The rule for any periodically-recomputed derived state: a global staleness score is a timer in disguise; the leverage is differential refresh allocated by the square root of partition risk.

Closest papers

Nearest neighbours by meaning across the whole index.

Feature Freshness Budgets for Real-Time ML Inference Under Stream Lag

cs.DC cs.DB ·2026-09-30 ·Amit Rajula
theory similarity 0.62
Abstract · Preprint. Under review at The VLDB Journal

Online feature stores decouple feature computation from model serving, materializing features from upstream event streams into a low-latency store that inference reads at request time. This decoupling introduces a freshness gap - the interval between an event occurring at the source and its effect becoming visible in the served feature vector - that is widely documented as a cause of training-serving skew but has no formal treatment as a bounded, cost-quantified quantity. We model the online feature store as a materialized view over an event stream and define a per-feature freshness budget: the difference between the decision window a feature is consumed within and the staleness the serving pipeline imposes on it. We prove two propositions - a per-feature staleness bound, and a closed-form threshold below which a feature can never be served within budget - and validate them in a seeded, reproducible discrete-event simulation and on a real Apache Kafka, Redis, and PostgreSQL pipeline. The predicted collapse threshold reproduces on real infrastructure, with the decision-error transition landing where the closed form predicts. Reconciling simulated and real drop rates surfaces a methodological result of independent interest: the dominant simulation-to-infrastructure gap is not latency but a sampling-phase artifact - a simulation whose request clock and recomputation cadence are phase-locked systematically under-observes staleness. Randomizing that phase reconciles simulation and infrastructure to within 0.018 mean absolute error in per-feature drop rate. Results are scoped to the studied workloads and configurations and are not claims about any specific production feature-store implementation.

0.19

CacheReforge: Bounded Recovery for Stale KV Caches under Evolving Adapters

cs.LG ·2026-09-25 ·Yuhang Cao, Yanzhou Mu, Chunrong Fang, Zhenyu Chen
similarity 0.62
Abstract · 13 pages, 5 figures. Artifact: https://doi.org/10.5281/zenodo.22951118

Large language models rely on KV caching to reduce repeated prefill computation in long context and interactive applications. As lightweight adapters evolve, cached states reflect earlier versions, so stale reuse distorts current model outputs, while complete affected suffix recomputation restores fidelity at substantial cost. We seek minimal recomputation that recovers current adapter behavior. Existing systems track token, context, or stable adapter identity, but neither represent caches from earlier adapter versions nor distinguish update propagation from the recomputation required for behavioral recovery. To address these gaps, we introduce CacheReforge, which represents stale KV caches as layerwise mixed-version objects. It combines per-layer adapter anchors, calibrated sensitivity, accumulated drift, and executable restart boundaries to select direct reuse, bounded recomputation, or complete affected-suffix recovery. We distinguish dependency depth from the functional recomputation horizon and use cumulative tail influence to characterize when bounded recovery preserves current-model behavior. We evaluate CacheReforge on Qwen2.5-1.5B and Qwen2.5-7B with continual LoRA updates, including 16K HotpotQA and 2WikiMQA workloads. CacheReforge reduces mean KL divergence by 92.4% relative to stale reuse, while recomputing only 5.44% of layers and reducing cache-maintenance time by 93.2% relative to fresh full prefill. These results show that version-aware recovery preserves model fidelity and most KV caching gains.

0.54

Budgeted KV-Cache Repair for Evolving Contexts

cs.AI ·2026-10-12 ·Han Yu, Wenhui Zhu, Jincheng Cao, Rui Cai, Yuanda Xu +13 more
similarity 0.61
Abstract

Language-model agents revise their working context as information becomes obsolete, but deleting text does not erase its influence on cached computation. Later key-value (KV) states remain conditioned on the deleted content, while recomputing the entire retained suffix can be costly. We introduce budgeted KV-cache repair: recovering task performance by recomputing a user-chosen fraction of the retained suffix. Comparing repair allocations under identical relevance scores and token budgets, we find that refreshing coherent regions can substantially outperform refreshing isolated tokens. This finding motivates Semantic-Unit Refresh (SUR), which allocates the budget to query-relevant text regions using inexpensive embedding scores, without training or an auxiliary transformer forward. To execute these repairs efficiently, a layer-packed executor processes selected states together at each layer while preserving full causal cache access. Across five models, SUR achieves strong recovery in controlled deletion tasks while recomputing only 2-5% of the suffix. On four natural multi-hop QA datasets, it achieves near-full-recompute exact match at a 5% budget with lower post-edit latency. The executor accelerates fragmented refresh by up to 16.1x over interval-wise execution.

0.13

SoftCache: Adaptive Step Size Caching for Diffusion Transformers

cs.CV ·2026-10-15 ·Shimon Malnick, Nadav Orenstein, Ohad Fried, Shai Avidan
code/data similarity 0.61
Abstract · Project page: https://malnick.net/softcache

Diffusion and flow models generate a sample over iterative steps, each a full pass through a large network, and that pass dominates generation cost. Training-free caching accelerates them by reusing activations from recent evaluations instead of recomputing them. Dynamic caching methods decide when to refresh by accumulating a cheap probe of the network input into a staleness signal and spending a fresh evaluation once it crosses a threshold. They perform hard caching: the signal is a binary switch between refresh and reuse, and every step, fresh or cached, advances by the prescribed step size. We observe that the signal carries much more than this switch. How far it sits below the threshold, its headroom, predicts the error induced by reuse. We propose SoftCache, which performs soft caching: instead of a binary switch, the headroom sets how far each cached step goes. Where the headroom is large, the sampler jumps past several scheduled nodes, and as a refresh nears, its steps shrink back toward the original step. These adaptive jumps may land between the scheduled nodes, taking the sampler off its fixed grid. SoftCache requires no training and adds no per-backbone settings: on FLUX for images and on HunyuanVideo and Wan2.1 for video, at speedups from $3.5\times$ to $6.9\times$, it is ahead of every baseline on all four fidelity metrics.

0.20

RESYNC: Residual Latent-State Synchronization for Deadline-Bound Streaming Inference

cs.LG cs.AI ·2026-11-12 ·Eljas Linna, Hao Dong, Juho Kanniainen
similarity 0.60
Abstract

Predicting every observation in a high-rate stream requires a model to finish before the next arrival. A large model may offer better predictions but miss that deadline. We propose RESYNC: the large model runs asynchronously, while a fast path updates its latest exact but stale latent state using the observations received since that state was computed and applies its unchanged prediction head. The updater learns from the frozen model's representations without task labels. Across one real and two synthetic streams and five architecture families, RESYNC beats the best compact or distilled alternative with a paired 95% interval above zero in all twelve dataset--architecture pairs with a material teacher advantage at anchor ages of 4--12 observations, and in eleven pairs at older tested ages up to 32. The share of the teacher's gain preserved remains complete on the real stream but is lower and generally declines with anchor age on the synthetic streams. In live replay with 1 ms arrivals, the synchronous large models cannot deliver any predictions on time while RESYNC serves at least 99.4% of arrivals within the interval, with 0.35--0.62 ms median latency on one CPU thread: around the same speed as or faster than the compact model, and 7.9--17.7$\times$ faster than synchronous large-model inference. RESYNC targets settings with background compute available but a strict per-observation response deadline.

0.14

BAG: Budget-Aware Gating for Diffusion Caching

cs.CV ·2026-08-10 ·Tong Zhao, Mingkun Lei, Yucheng Han, Chi Zhang
code/data similarity 0.59
Abstract · 23 pages, 13 figures, and 14 tables. Code Link: see https://github.com/Westlake-AGI-Lab/BAG

Diffusion caching is a lightweight strategy that accelerates Diffusion Transformers (DiTs) by reusing intermediate features across denoising steps, but existing paradigms face a fundamental trade-off: online heuristics lack global budget awareness, whereas static schedules lack instance adaptivity and fail to flexibly adapt to varying runtime budget constraints. To bridge this gap, we present BAG (Budget-Aware Gating), a novel caching policy that unifies global budget pacing with dynamic, instance-adaptive feature reuse. Rather than relying on hand-crafted rules, BAG employs a lightweight gating network that dynamically decides whether to execute a full computation or reuse cached features at each step by jointly conditioning on the budget state and local trajectory feedback. We train this policy via offline-to-online schedule distillation, transferring the decision-making of offline-searched schedules into a compact online gate. Extensive experiments on FLUX.1-dev, Wan2.1, and Qwen-Image-2512 demonstrate that BAG consistently outperforms state-of-the-art caching methods across various speedup tiers while remaining robust across different resolutions, seeds, and guidance scales. Code will be released.

0.30

CtrlCache: Accelerating Interactive Video World Models with Control-Aware Caching

cs.CV ·2026-10-06 ·Shangye Song, Dong Gong, Hong Jia, Yun Sing Koh, Xinyu Zhang
code/data similarity 0.59
Abstract · 18 pages. Project page: https://wrecklong.github.io/CtrlCache/

Interactive video world models need to generate each video chunk efficiently while responding faithfully to user controls. Many systems use chunk-wise autoregressive generation with few-step denoising, but each chunk still requires several costly denoising iterations. Training-free caching can reduce this cost, yet existing policies make reuse decisions primarily from model-internal denoising dynamics and do not explicitly account for control transitions. Actually, interactive generation explicitly exposes a signal they do not use: the controls for a chunk arrive before it is denoised, so a schedule derived from them costs no forward pass. To this end, we analyze adjacent chunks under different control regimes and find that structural similarity drops around action changes, while low-frequency structure remains more persistent than high-frequency detail. Motivated by these observations, we propose CtrlCache, a training-free control-aware caching framework that adapts computation to the current control sequence. Specifically, the action-aware scheduling and refresh policy detects action changes across and within chunks, and labels each chunk as initial, transition, turning, or steady state. At one selected interior denoising step, initial and transition chunks retain full computation, while turning and steady chunks reuse the transformer residual from the most recent fully computed step in the same chunk. To exploit the persistence of low-frequency structure during steady interaction, we further introduce a frequency-mixed history prior guidance that incorporates complementary information from the preceding clean latent without an additional DiT forward pass. Evaluated on Matrix-Game 2.0 and LingBot-World v1/v2, CtrlCache achieves 1.21x to 1.41x DiT-backbone speedups without model retraining while improving WBench Overall scores over original inference across all three models.

0.28

What It Costs to Compose, Rebuild, and Correct Precomputed Memory

cs.CL cs.LG ·2026-08-31 ·Asa Shepard
similarity 0.59
Abstract

Language models can answer from precomputed memory, a model's saved reading of a body of material, reused across requests instead of read again at each. This paper maps where that practice preserves correctness and the conditions under which it fails. Across experiments on Llama-3.1-8B-Instruct using both saved key-value caches and trained compressions of them, precomputed memory degrades when assembled from separately prepared parts, stays current only through rebuilds costing a large fraction of full preparation in our measurements, and ignores corrections served beside it conditional on phrasing. If precomputed memories can be served alongside one another, be cost-efficiently rebuilt, and be superseded by new information arriving in real-time, they can serve as a way to avoid re-feeding context to a model over repeated queries. The implication of our results for a deployed system that deals with a variety of queries is that precomputed memories are best rebuilt on the cadence at which new information changes what the memory was originally computed from. Both warm-rebuilding trained compressions of key-value caches and serving specifically-phrased updates beside a memory, as pasted text or injected cache state, show particular promise for keeping precomputed memories current, the latter as an interim measure between rebuilds, and we measure the cost and name the remaining questions associated with each.

0.47