Skip to content

Marginally Correct Tool Caches Can Reverse Group-Normalized Policy Updates

Sep 2026 · 0 citations · 9 references
Computer Science

TL;DR

It is established that marginal output validity alone cannot certify a stochastic cache as training-equivalent, and against a constant alternative, the shared update follows the probability of winning minus the probability of losing, rather than the difference in expected reward.

Abstract

Tool-result caching reduces repeated execution in agent training, but also couples rollout randomness. We study a two-action model in which independent and shared execution preserve every rollout's conditional reward distribution. Despite this marginal agreement, sharing one stochastic result per group can reverse the expected group-normalized policy update. We derive an exact finite-group expression: against a constant alternative, the shared update follows the probability of winning minus the probability of losing, rather than the difference in expected reward. A Bernoulli specialization yields a wrong-direction region and a non-vanishing update-variance floor as group size grows. Centering without group standard-deviation scaling preserves the expected-return direction in this model, using an existing estimator control. Exhaustive finite sums verify 540 configurations and 3,240 estimator evaluations, with a separate ordered-sequence checker. An implementation audit reproduces the sharing path in a pinned, unmodified TVCache stack using 256 scripted rollouts. These results do not measure language-model training performance or refute TVCache's deterministic-output contract. They establish that marginal output validity alone cannot certify a stochastic cache as training-equivalent.

View source

Similar papers

#machine learning Preprint Oct 2026

Exact Memory-Time Optimization for Prefix-Cached Language Model Serving

Retaining language-model prefix states trades recomputation against storage time. Optimizing each cached block independently can overcount savings: a resident block is usable only when the required preceding prefix is also available. We introduce Prefix-Certificate Retention (PCR), an exact finite-trace formulation for...

Shivam Gupta · 0 citations
#artificial intelligence Preprint Oct 2026

Request Order Matters: Cache-History Sensitivity in Selective KV-Cache Reuse for Rolling Agents

Long-running agents repeatedly call an LLM while retaining most of their document window, evicting old documents, and appending new ones. These rolling updates break exact prefix caching and motivate non-prefix KV-cache reuse with selective recomputation. We show that persistent KV-cache reuse with selective recomputat...

Tiffany Gu, An-Nie Guan, Man-Shu Huang et al. · 0 citations
#artificial intelligence Preprint Sep 2026

Speculative Evaluation of Stochastic LLMs

Real-generation experiments that account for the pilot synchronization barrier show that HBN-async mitigates its overhead, helping translate statistical efficiency into practical evaluation benefits, and outperforming hindsight-tuned empirical and independent Bayesian baselines.

Qian-Li Shen, Xiang Li, Ruo-Meng Ding et al. · 0 citations
#machine learning Preprint Oct 2026

Ascent Conditions for Length-Normalized Single-Rollout Policy Updates

Dividing each trajectory's score contribution by its realized length can change the direction of a reward-centered policy update. In a finite trajectory model, we derive an exact ascent threshold for a three-outcome softmax policy and exhibit a binary-reward example in which the expected Euclidean update decreases task...

Levin David Schwab · 0 citations
Preprint Aug 2026

Memory-Sovereign Inference: Output-Exact Execution Beyond Full Residency

A falsifiable certificate is presented separating representation, semantic demand, scheduler requests, and traffic while naming resource authorities, exactness horizons, and tested reuse transitions while naming resource authorities, exactness horizons, and tested reuse transitions.

L. Štěpánek · 0 citations
#artificial intelligence Preprint Oct 2026

When Is Deletion Ordering Tractable? From Update Dynamics to Permutation Structure

Given a fixed set of pending deletion requests, retraining from scratch after each request is prohibitive, so a prescribed request-wise policy processes them sequentially. The resulting terminal model can depend on their order. Rather than prescribing an ordering rule, we study the permutation objective induced by the...

Xin-Yu Wang, Zi-Yu Zhao, Yi-Xuan He et al. · 0 citations

Related blog posts

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.