CS Paper Radar

The Price of Remembering: A Calibrated Energy Law for Computation

Mohamed Amine Bergach

cs.PF cs.ARcs.LO ·submitted 2026-09-01 05:24 UTC · v2
theory

Abstract

Where does a computer's energy go? Mostly into keeping, not into computing. A bit held in fast storage draws power for every second it stays there, and it costs energy again each time it moves between storage levels. We call the first cost \emph{rent} and the second \emph{fare}, and we state one law: the energy of a computation is at least its operations, plus rent on every live bit for as long as it lives, plus fare on every bit moved. The model under the law prices control as well as data. There is no free clock, and any unpriced register would make the theorems false. One lemma does most of the work: every use of a value is paid for by rent, by fare, or by computing the value again. Three things follow. Exact attention brings every past token back for every new one, so its energy grows with the square of the context length, while a recurrent model with a fixed state grows linearly. The square is a theorem for machines that never re-read past tokens. Under a stated serving hypothesis it is the fare on every past token, which passes the model's own arithmetic near ten thousand tokens, the point where long-context serving becomes bandwidth-bound today. Known bounds on memory over time become joule floors: on any sequential machine with volatile working storage, sorting $n$ items pays rent proportional to $n^2/\log n$ bit-steps on most inputs, and the bound for scrypt makes every password guess cost joules that no amount of parallel hardware reduces.

Closest papers

Nearest neighbours by meaning across the whole index.

Think or Remember: The Exchange Rate of Agentic Inference

cs.CL cs.AI ·2026-11-07 ·Juan Wisznia, Santiago Luis Groba Alonso, Matías Gómez Taddeo, Gonzalo Zabaleta, Joaquín Cullen +1 more
similarity 0.64
Abstract

Agents built on reasoning models resend their growing transcript at every call. Two transacting parties, not the model, decide what that costs: the client keeps or edits messages; the server decides whether earlier reasoning returns in the prompt and what its cache reuses. We define a cost model whose counts match an instrumented engine exactly; the architecture charges $c$ per token processed and $β$ per pair attended. Their ratio $P^*=c/β$ is an exchange rate between thinking and remembering: per token, processing dominates below this context length, a thinking regime, and attention above it, a memory regime. A policy change has a mechanical cost, incurred even if the agent writes the same tokens, and a behavioral one: it writes different tokens, changing cost and outcome. Serving alone can flip which policy is cheaper: on recorded Qwen3-8B ScienceWorld runs, dropping earlier reasoning costs 1.74 times keeping it when the server reuses generated states and 0.34 times when it reuses nothing. In live reruns, dropping it cuts correct HotpotQA answers by 9-23 percentage points on four models, at lower point-estimate cost. Comparing context policies means comparing systems: architecture and serving set the cost of the history kept and the work it induces.

0.21

The Unexpired Plan: A Free Monitor for Accelerated Diffusion Policies

cs.RO ·2026-10-05 ·Yi Zhao, Sebastian Scherer
similarity 0.59
Abstract · 8 pages, 3 figures, 5 tables. Project website (code and videos): https://yizhaojasper.com/unexpired-plan/

Training-free acceleration of a diffusion policy is accepted when an internal similarity signal reports that the shortcut changed nothing. We price every monitor a control loop can afford in closed-loop success rather than feature distance, over $114$ accelerator configurations and four policy families: two accelerators each clear their own gate's bar and log every reuse as certified, while on one task one finishes every episode and the other none. A monitor is two designs, not one --- the statistic it reads, and what it does when that statistic fires. Published gates re-arm after every rejection, and under that response even an oracle handed every forward pass and the exact local action error loses twenty points; absorbing the same statistic costs one point, and most of its speed. What makes a response that never forgets affordable is a statistic that rarely fires, and what it must measure is deviation from the policy the accelerator replaced --- which a chunked policy has already paid for, its last plan not yet expired and free to read. Guarding every call this way cuts per-call compute by $1.55$--$3.09\times$, where any reference-requiring check at the same coverage would have to stop accelerating altogether. On three of our four families the schedule alone already holds the pre-stated $\pm2$-point margin. What the monitor is measurably worth shows in three places: on the fourth family, where it rescues the candidate selection landed on; on four configurations it did not select; and on a contact-rich fifth family, chosen where the schedule was expected to fail and run after every design choice was frozen, where no unmonitored arm at its speed holds the margin and the monitored one does.

0.29

A Sharp Additive Bound for the Threshold Rule in Repeated Rent-or-Buy

cs.DS ·2026-11-03 ·Vasco Schiavo
similarity 0.56
Abstract · 16 pages

Motivated by context management in LLM agents, we study a repeated rent-or-buy model with schedule-independent history growth and a fixed reset price $K$, a discrete form of dynamic TCP acknowledgment: every call pays as rent the history accumulated since the last reset, and a reset clears it. The classical threshold rule is $2$-competitive, and no deterministic rule guarantees a smaller ratio. We show that, measured additively, its loss is governed by the changes in the growth: if the growth is constant on $P$ runs, the threshold rule, knowing neither the runs nor the horizon, pays at most $(2P-1)K$ more than the optimal schedule chosen with hindsight, and the coefficient $2P-1$ is sharp. If the growth is only within a factor $1+\varepsilon$ of $P$ runs, the bound holds up to a factor $1+\varepsilon$ and an extra $\varepsilon K$. The proof is a potential argument built from the relative value functions of the single-rate problems. On two runs no deterministic rule guarantees a loss below $2K$. A rule that also resets when the growth decreases guarantees $2K$, while the threshold rule can lose arbitrarily close to $3K$.

0.30

From Long Context to Selective Memory:A Survey of Memory-Centric Compression for Large Language Models

cs.CL ·2026-10-15 ·Chaogui Gou
surveybenchmark similarity 0.56
Abstract

Long-context capability has become essential for large language models (LLMs) to handle complex tasks, yet continuously expanding the context window does not remove the computational, storage, and information-selection pressures incurred at inference time. Existing work on prompt compression, KV-cache management, efficient serving, retrieval augmentation, and agent memory is usually discussed in isolation, leaving the flow of information between storage and computation insufficiently understood. This survey reframes long-context compression as a memory-management problem for allocating inference-time resources. We distinguish compute-active memory, which directly participates in model computation, from compute-inactive memory, which lies outside the computation path but can be stored, retrieved, updated, or forgotten, and we characterize offloaded KV caches, persistent prefix caches, and precomputed KV states as intermediate states on the activation path. On this basis, we formulate writing, offloading, recall, retrieval-and-injection, materialization, eviction, consolidation, and forgetting as state transitions within an information lifecycle, and introduce a budgeted cost model that places these operations in a single cost account. The resulting framework unifies short-term context compression, long-term memory management, and the transitions between them, and shows that the central challenge is not merely reducing information volume but deciding which information should participate in costly inference, when, and in what form. We further summarize evaluation dimensions, benchmark gaps, and open challenges, and argue that future research should move from static, pointwise compression toward dynamic, governable, lifecycle-aware memory management.

0.16

Computation with Backward Feedback: Power, Observation, and Cost

cs.CC ·2026-11-12 ·Saman Farhat, Farzad Didehvar
similarity 0.56
Abstract

How much can a computation gain by passing information back to an earlier stage, and how soon can an observer obtain the answer? We study deterministic programs whose runs are accessed at randomly selected stages. A program keeps a register, a finite block of memory. A random clock selects the current stage; each tick takes a random step, with a law fixed independently of input, program and register. When the clock moves backward, the register contents at the stage it leaves start a new run, and the clock continues where it lands. Equilibrium readout requires a distribution of clock position and register that one tick leaves unchanged, and a correct final answer under every such distribution. For bounded steps in both directions with negative average, we obtain an exact classification at each polynomial scale s. If running time and register length are both O(s), feedback gives exactly nondeterministic space O(s); without transmission the class is deterministic time O(s), which is strictly smaller. An observer that starts at stage zero with an all-zero register, reads sequentially and never accepts a nonmember sees, with fewer ticks than any exponential, only languages fixed by a bounded input prefix. Exponentially many ticks reveal every linear-time language. For a clock moving one step up or down, we bound the wait for useful backward moves and the rate of random erasures a stored counter tolerates. The results separate the power of feedback at equilibrium, observation from a fixed start, and the cost of obtaining and keeping information.

0.21

Working Around the Compute Ceiling: Byte-Exact Memory in Galahad Makes LLM Reading a One-Time Cost LLM Reading a One-Time Cost

cs.CL cs.AIcs.IRcs.LG+1 ·2026-09-30 ·Sietse Schelpe
similarity 0.56
Abstract

A transformer language model performs a bounded amount of computation per token, and recent work by Vishal Sikka, former CEO of Infosys, argues that this bound limits which tasks a model can carry out or verify (arXiv:2507.07505). We ask how much of the budget beneath that ceiling is spent on work the model has already done. Serving is stateless across requests: a model that answers a second question about a document recomputes the document's attention state from the first token. On seven real-world datasets, 98.7% of prompt tokens were text the model had already read. We present Galahad, a memory layer for vLLM, SGLang and llama.cpp that makes this reading a one-time cost. Taliesin saves the model's key-value (KV) state for a block of text and loads it on the next request that contains the same bytes, instead of recomputing it. Blaise keeps the documents themselves and passes the model only the section a question needs. On a recall test with 100 facts hidden in a 97,000-token corpus (Gemma 4 31B), Taliesin alone let the model attend to the whole corpus and answered 98 of 100 on llama.cpp at 3.0 s and 572 J per question, against 10 of 100, 9.3 s and 2,754 J for the same model without Galahad, which could hold only the last 12,000 tokens. With Blaise added, the model read about 668 tokens per question and answered 100 of 100 on all three runtimes at 0.59-0.64 s and 200-213 J; a tuned RAGFlow pipeline answered 77. Storing the corpus is a one-time cost of about 100 s and 28 kJ, whose energy is recovered after 13 questions. Restored state is bit-identical: all 262,144 output logits matched after restart, rehydration and hot-load. Galahad worked with all 30 models we tested under vLLM, and it fails closed: any load that does not pass its checks is recomputed. Together these results move LLM serving from stateless to stateful inference.

0.25

Towards a Formal Definition of Agent Memory: Basis, Span, Optimality, and the Sequential Memory Problem

cs.LG ·2026-08-12 ·Hongyao Tang
similarity 0.56
Abstract

Despite the wide deployment of memory in large-model agents, there is no unified formal account of what a memory is or when it is optimal. This paper takes a first step toward this account. The central idea is that memory is a basis, knowledge is its span, and answerability is a coverage problem: an agent stores events extracted from a material; a generation operator turns any event set into the knowledge it entails; and a query is answerable exactly when some single item in the span covers it. The optimal memory is then the capacity-constrained maximizer of expected coverage, and its value traces a utility--capacity frontier, the common yardstick on which memory systems can be compared. Next, we consider noise in the memory and discuss coverage versus precision under it: a memory may store false claims, so the write policy must infer the truth of what it stores. Drawing an analogy with biological memory, which is formed continuously through ongoing experience, we formalize the continual agent-memory problem in a sequential MDP that covers multiple levels, where memory is the state, writing is the action, and the utility settled at query time is the delayed reward that drives learning. To make the framework concrete, we instantiate it on Homer's \emph{Odyssey}, turning the frontier, the compression zone, and the divergence of coverage from precision into concrete numbers. Finally, we position existing systems within the framework, making ``how good is a memory'' measurable and recasting the open problems of constructing and learning agent memory as concrete research questions.

0.04

Useful Work Can Increase Energy Use: Demand Elasticity and Proof of Useful Work

cs.CR cs.GTecon.TH ·2026-11-09 ·Isaiah Hull, Or Sattath
similarity 0.55
Abstract · 24 pages, 1 figure

A serious criticism of Bitcoin's Proof-of-Work is its enormous electricity consumption. Proof-of-Useful-Work (PoUW), introduced by Ball, Rosen, Sabin, and Vasudevan (2017), in which mining performs useful computations, was suggested as an alternative to reduce electricity expenditure, with matrix multiplication (MatMul) as a recent concrete instantiation by Komargodski and Weinstein (2026). Perhaps surprisingly, we show that switching to PoUW may increase the total electricity consumption, echoing Jevons' paradox. Intuitively, the PoUW mechanism acts as a subsidy that lowers the effective price of the useful work. Recall that demand is elastic if a discount of x percent in the price leads to an increase of more than x percent in the quantity demanded. If demand is elastic, the resulting increase in quantity demanded leads to a net increase in total electricity consumption; if inelastic, total electricity consumption decreases. Even then, the electricity consumption due to PoUW never vanishes, since the mining subsidy is spent on useful work that would not have been produced without the subsidy. This result is proved in a simple model with electricity-only costs, no PoUW overhead, and an unchanged mining subsidy. The analysis extends to less restrictive settings with adjusted thresholds.

0.42