PaperlayerView exact revision on arXiv

Source-linked AI summary

The Price of Remembering: A Calibrated Energy Law for Computation

Mohamed Amine Bergach

arXiv:2609.00744v2cs.PFcs.ARcs.LO

TL;DR

Computer energy is dominated by keeping and moving information rather than arithmetic, but existing accounting treats these costs separately. The paper unifies them in a physically calibrated law that prices data and control, then derives energy floors for memory-intensive computations and validates the accounting with synthesized hardware. The resulting framework explains quadratic energy growth for exact attention, linear growth for fixed-state recurrence, and joule costs for memory-hard tasks.

  • Problem

    Computer-energy accounting must capture the substantial costs of keeping live bits and moving them between storage levels, not only arithmetic operations.

  • Method

    The paper defines a rent-plus-fare energy law, prices control state through a no-free-clock rule, and proves a serving lemma that charges each value use to rent, fare, or recomputation.

  • Results

    The framework yields energy floors for sorting, scrypt, and exact attention, while a synthesized 45 nm processor matches the calibrated accounting within 4%.

  • Takeaways & Limitations

    Counting byte-seconds and bytes moved alongside operations connects algorithmic memory bounds to physical energy costs and clarifies why long-context serving becomes expensive.

  • Takeaways & Limitations

    The conclusions rely on stated execution and substrate assumptions, including route hypotheses and scope boundaries, and the hierarchy analysis leaves its energy advantage over the best single ring open.

Abstract

from arXiv · show

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.

1 Introduction

The paper proposes a physically calibrated energy law in which computation pays for arithmetic, keeping live bits, and moving bits, with control state priced like data. This framework turns memory-over-time and data-movement bounds into energy floors for sorting, cryptography, attention, and storage hierarchies.

  • Motivation: A 64-bit addition costs about a picojoule, while fetching operands from off-chip memory costs 1,000–10,000 times more.In general-purpose cores, over 90% of instruction energy goes to overhead such as fetching, decoding, renaming, tagging, and forwarding.
  • The Law: The law charges arithmetic plus rent on every live bit, fare on every bit moved, and a much smaller Landauer toll on every erased bit.Rent covers power consumed while bits remain in storage; fare covers transfers between storage levels.
  • The Law: There is no free clock: schedules, program position, and elapsed time are priced bits, because an unpriced register would invalidate the theorems.The next machine step must depend only on the contents of computed cells, while the input is held free in the environment.
  • The Law: A serving lemma assigns every value use to residence, fetching, or recomputation, making rent, fare, and operations disjoint accounting charges.The lemma formalizes the central tradeoff: a computation can choose among keeping a value, moving it, or computing it again.
  • Bridges: Known cumulative-memory bounds become joule floors: volatile-storage sorting pays rent proportional to n^2/log n on most inputs, while scrypt retains its bound under parallelism.The paper connects memory-hard cryptography, complexity theory, architecture, and energy-efficient algorithms through one calibrated functional.
  • The Meeting Bound: Exact attention has quadratic context-length energy, whereas a fixed recurrent state has linear memory cost; attention overtakes model arithmetic near T ≈ 1–3 × 10^4.Under a route hypothesis, the fare on past tokens yields the squared bound; the recurrent comparison is a separation between what the functions remember.

2 The Law

The law models computation on leveled volatile storage, charging operations, rent for live bits held over time, and fare for bits crossing storage boundaries. It prices control as well as data and proves that each value use is paid by residence, movement, or recomputation.

  • Storage and costs: Every live bit pays rent for its residence time, and every bit crossing a storage boundary pays fare.Rent models holding power; fare models movement such as cache fills or memory-bus transfers.
  • Storage and costs: A machine uses storage levels with capacities, per-bit hold powers, and per-bit boundary fares; an external input/output environment is unpriced.Working storage holds live bits, while the environment supplies input and receives output.
  • Machine model: Operations fire at fixed stations, read resident words, write at their level, and may free live bits.Moves and fires occur between holds, while time advances during holds.
  • Machine model: The machine’s next step, schedule, program position, and time sense are functions of priced computed-cell contents; there is no free clock.An unpriced register would invalidate the paper’s theorems, while control state therefore incurs the same storage costs as data.
  • Consequences and scope: Holding operands longer multiplies rent, whereas the arithmetic itself remains only one component of the bill.The law also omits a separate Landauer term because measured operation energy already includes that floor, which is much smaller than operation and fare terms.
  • Charging lemma: Each value use is charged through residence since its last use, a fetch, or recomputation, with disjoint charges and a minimum determined by the available route.The potential argument tracks pending charges and establishes energy at least equal to accumulated charges.
  • Consequences and scope: The charging tradeoff relies on route assumptions and jointly incompressible live values; without those conditions, the corresponding stronger floors do not follow.The 103 pJ/bit re-projection figure is a route-class hypothesis, while the substrate’s unconditional write floor is approximately 0.1–1 pJ/bit.

3 Bridges: Old Bounds Become Joule Floors

The paper converts established cumulative-memory and communication lower bounds into energy lower bounds by charging volatile storage over time and crossings between levels. These bridges yield joule floors for sequential sorting, memory-hard password hashing, and matrix multiplication, while parallelism can reduce rent when its hardware is explicitly provisioned.

  • Bridge method: The simulation bridge maps machines to branching programs whose summed memory becomes a lower bound on live bits summed over holds, namely rent.The construction preserves success probability and bounds the branching program’s levels using querying fires and machine width.
  • Sorting: p_minΔ Ω(n^2/(q log n)) is the sorting rent floor for one-station machines on volatile working storage.For deterministic sorting, the bound applies to a machine sorting n items, with randomized variants covered on an appropriately probable set of inputs and coins.
  • Sorting: n^2/log n bit-steps is the working-set requirement for sorting on most inputs, independent of how the machine holds or paces itself.Each bit-step costs at least p_minτ_0 joules; at SRAM-class parameters, the floor remains below comparison cost for a million items.
  • Scope and parallelism: Parallelism genuinely lowers rent for sorting networks, whose cumulative memory is Θ(n log n) word-steps rather than the sequential n^2-scale floor.The reduction is purchased by provisioning n comparators, so the capability currency must be priced on parallel substrates.
  • Memory-hard cryptography: Ω(n^2w) cumulative memory for scrypt yields a volatile-hardware joule floor that persists at any parallelism and across amortized evaluations.At p_minτ_0 ≈ 10^-18 J per bit-step with n = 2^20 and w = 8192, the floor is of order 10 mJ per evaluation.
  • Memory-hard cryptography: Adding hashing cores does not reduce scrypt joules per guess; it only spends the energy faster.Moving the cracker’s working state to nonvolatile storage converts rent into fare at the boundary, linking the adversary floor to bandwidth-hardness.
  • Matrix multiplication: Ω(n^3/S) boundary crossings and fare E ≥ c_0wΩ(n^3/S) lower-bound two-level matrix multiplication, and a streaming blocked schedule achieves the bound.The theorem assumes stations at a fast level with capacity S words; the slow level may be the environment.

4 The Meeting Bound: Attention Pays Θ(𝑇2), State Pays Θ(𝑇)

Exact causal attention must repeatedly serve information from past tokens, producing a quadratic energy floor, while a recurrent model with fixed state has linear memory cost. Conditional and unconditional bounds distinguish route-dependent serving costs from streaming costs that require no serving hypothesis.

  • Meeting bound: Exact causal attention creates about T^2/2 token-step meetings because each new token meets every preceding token.The meeting count is priced by the serving lemma, which charges each past token’s representation when it is used.
  • Unconditional floor: The unconditional streaming theorem prices volatile working storage through rent, without assuming a particular serving route or recomputation strategy.Its space barrier applies to streaming machines that read each token once after the preceding output.
  • Scope: The conditional bound applies to exact, κ-atomic attention, while approximate generation and route choices define important scope boundaries for interpreting the result.The unconditional floor is asymptotic in d and may not quantify current systems at d=128.
  • Meeting bound: Under the κ-atomic route hypothesis, attention pays E ≥ κT(T−1)γ/2, with γ the minimum of fare, rent per step, and recomputation cost.The bound charges every past token’s κ-bit footprint across the meetings, apart from the meetings’ operation energy.
  • State comparison: A recurrent model holding σ incompressible bits has memory cost linear in T, yielding an attention/state memory-term separation of Θ(κT/σ).This compares functions with different remembered information, not two algorithms computing the same function.
  • Serving implication: With today’s constants, the fare-based attention term overtakes the model’s arithmetic near T∗≈1–3 × 10^4 tokens, where long-context serving becomes bandwidth-bound in practice.The fare grows linearly with context length per generated token, while the model’s arithmetic remains constant.

5 Structure: Why Hierarchies Exist

Hierarchies reduce rotation by parking data rather than continuously circulating it, but their energy advantage depends on constants, fixed station count, and provisioned-station leakage. Single-ring layouts also face asymptotic cutwidth barriers and computationally hard optimization.

  • Why hierarchies exist: A hierarchy converts rotation into parking: data not currently needed remains still on a cheaper shelf instead of riding a single conveyor.The staged construction runs its active stages one at a time; the separation comes from seeds standing still, not from parallelism.
  • Layout complexity: Optimal single-ring layout is NP-hard to approximate within any constant factor, although fixed-window seatability is decidable in n^O(W) time.The stated bounds relate the minimum window to caterpillar bandwidth.
  • Necessity: A balanced N-leaf reduction cannot fit on one ring once N>2^8W, whereas a staged hierarchy can seat it.At the instrument’s W=8, the threshold is N>2^64.
  • Hierarchy construction: The staged hierarchy achieves rotation action O(Nb), parked action O(N^2), and O(N/b) transfers for stage size b.At W=8, the construction uses strand capacity λ=4 and b=4.
  • Energy boundary: The energy separation holds only when the hierarchy’s parked constant satisfies c2 < e/(4s ppark), approximately 13 at s=1 on the instrument.Measured Table 3 values place c2 above that threshold, so the constructed hierarchy is not energy-separated under those constants.
  • Experimental interpretation: The reported 83× comparison measures one flattening’s relay-ladder cost, not the optimal single-ring program or a theorem-level ratio between the two programs.Both compared programs remain far above the theorem’s floor.

6 The Dependence Tax

Dependent pointer chases incur a rotational delay that placement cannot remove: each next target is, on average, half a revolution away. The instrument nearly meets this lower bound, while replication or extra ports trade rent for lower delay.

  • The dependence tax: Θ(P) per dependent access is the ring’s tax against a unit-cost RAM.The theorem gives an expected time lower bound of roughly half a ring period per chase step.
  • The dependence tax: Placement cannot help because after each service, half of the next targets lie behind the port.This is the intuition behind the half-orbit lower bound.
  • The dependence tax: The instrument’s 𝑃=64 ring averages 32.5 cycles, within one cycle of the 31.5-cycle bound.The one-cycle gap comes from the same-index case, where the bound charges nothing but the mechanism waits a full orbit.
  • The dependence tax: 𝑘 table copies or 𝑘 ports divide the delay floor by 𝑘 while imposing 𝑘-fold rent or provisioned cost.Replication is excluded by the theorem’s single-table hypothesis.

7 The Instrument: Where the Law Is an Equality

The authors calibrate the rent-and-fare law on a synthesized ring processor whose storage moves, making the law’s accounting measurable and nearly exact. Gate-level twins separate operations, fare, and rent, while activity-sensitive constants explain variation across data.

  • The Instrument: Where the Law Is an Equality: A ring processor with co-rotating instructions and data makes rent and fare collapse into one measurable shift-energy constant.Each packet pays for every slot it advances, while inter-ring landings remain boundary fare.
  • The Instrument: Where the Law Is an Equality: Gate-level extraction uses NanGate 45 nm synthesis and verifies slot-for-slot agreement among the Python model, RTL, and netlist.The artifact includes synthesized rings and stations, a baseline RV64 core, and machine-checked certificates.
  • The Instrument: Where the Law Is an Equality: The difference method decomposes measured energy into operations, fare, rent, and the idle floor using no-fire and static twins.Program minus no-fire isolates operations; no-fire minus static isolates landings; static minus idle isolates rent.
  • The Instrument: Where the Law Is an Equality: 0.90 to 1.03 pJ per live-slot-cycle is the fitted rent constant across three programs, whose operation energies differ by 100×.The programs agree because their rotating data have similar activity, not because one fixed event constant transfers universally.
  • The Instrument: Where the Law Is an Equality: Under 4% residual error across static runs is achieved by fitting 𝑒=𝑒clk+𝑒tog𝜏, with 𝑒clk=0.822 pJ and 𝑒tog=3.4 fJ.The un-isolated run is held out, and leaving any one run out predicts it with at most 5.1% error.
  • The Instrument: Where the Law Is an Equality: The clock term contributes four fifths of 𝑒, showing that rent on this substrate is mostly the cost of clocking live storage.The extracted values are pre-layout and omit wire capacitance and clock-tree energy.

8 Rent on Choice

The paper extends rent from stored data to provisioned capability: hardware that keeps runtime choices open consumes energy every cycle. Measurements show that relocating or deleting such freedoms can substantially reduce area and idle or switching energy.

  • Rent on Choice: Capability rent charges hardware provisioned for a runtime choice whether or not that choice is exercised.The measured freedoms include standing still, waiting, observing packets, and addressing.
  • Rent on Choice: 28% smaller and 91× cheaper at idle describes moving the ring’s parking freedom from a per-bit hold mux to per-slot clock gating.Including leakage, the reduction is 39×, from 0.0145 to 0.0103 pJ at 1 GHz.
  • Rent on Choice: 27.0 → 4.1 pJ/cycle is the reduction in worst-case churn from deleting stations’ freedom to observe every passing packet.This is achieved through operand isolation.
  • Rent on Choice: At 𝜖=𝑘Tln 2, the decision-floor statement becomes a theorem for a machine overwriting its choice register each cycle.The general conjecture assigns at least 𝜖log C per cycle in the worst case over fresh choices among C alternatives.

9 Testing the Law

The paper proposes falsifiable tests for the rent law across synthesized hardware, DRAM self-refresh, and inference platforms, while identifying substrates that could challenge its terms.

  • Hardware test: Within 4% on five static runs spanning 0.90 to 1.8 pJ, the synthesized instrument matches Prediction 1's rent-form residual.The stated tolerance for further operand-isolated runs is 10%; the un-isolated run misses by 20%.
  • DRAM test: A DRAM module in self-refresh should draw energy within a small factor of p·Bt, as predicted by its refresh specification.A measured hold energy decisively below the specification band would challenge the rent constant.
  • Inference audit: For inference with T > S0/κ, joules per generated token have slope at least κ min(c0, γr_c) under the stated κ-atomic serving hypothesis.κ is measurable as the key–value bytes moved per generated token; allowing κ to vary makes the test non-falsifiable as a law test.
  • Counterexamples: Fast nonvolatile memory could remove rent, while write fare and read energy would remain and reorganize the hierarchy around them.Wave substrates provide a sharper challenge because holding information may require regeneration rather than leakage compensation.

10 Related Work

The paper positions rent, fare, residency, erasure, layout, rotating storage, and learning-system memory work as related strands unified by its energy-law framework.

  • Movement: Existing movement bounds price transfers between memory levels, while this work adds rent, a calibrated constant, and layout to the fare term.The red–blue pebble game, hierarchical-memory models, communication-avoiding practice, and roofline model form the related movement lineage.
  • Residency: Cumulative-memory theory underlies memory-hard and bandwidth-hard functions, but prior work does not claim a physical energy law or measure its constant.The paper presents its rent bridge as extending these residency-based bounds into joule floors.
  • Erasure: Landauer, reversibility, and semi-reversible algorithms price information destruction, complementing this paper's focus on remembering and operations.Circuit energy complexity provides a separate combinatorial line for switching gates.
  • Layout and width: Classical bandwidth, cutwidth, VLSI area-time, and retiming results provide neighboring tools for the paper's layout and width questions.Retiming is described as the closest existing tool to minimum-action layout.
  • Rotating storage: Delay-line machines and systolic arrays supply historical precedents for phase-aware layout and rhythmic computation, while the paper extends these ideas to stored programs.The paper's instrument supplies the model and its full proofs are placed in Appendix B.
  • Learning systems: FlashAttention, paged KV management, checkpointing, state-space models, and attention lower bounds are framed as points around one memory-serving frontier.The serving lemma's minimum and the meeting bound are presented as the common floor beneath these approaches.

11 Open Problems

The open problems extend the law toward hierarchy optimization, attention reformulations, layout complexity, mixed substrates, synchrony, and the energy cost of flattening.

  • Hierarchy shape: Geometric level spacing is proposed as the minimizer of ℓpℓAℓ + cℓFℓ for power-law reuse spectra under the device curve p(τ).The paper frames “caches double” as a theorem and as a three-currency version of Kung's balance principle.
  • Decision floor and attention: The agenda includes formalizing a decision floor and determining when exact attention's Θ(T^2) floor can become Θ(T) under algebraic reformulations.It also asks what is purchased at that boundary.
  • Layout and substrates: Further problems ask for minimum-action seating complexity, spectrum-occupancy bounds, and online rent-or-fare theory for mixed substrates.The seating problem is conjectured NP-hard, while mixed-substrate placement is posed with competitive ratios.
  • Synchrony and flattening: The paper proposes pricing synchrony as a capability term and proving a single-ring lower bound for flattening costs in relay traffic and ladder revolutions.These questions aim to extend the law to asynchronous rings and make the stated separation an energy theorem.

12 Conclusion

The conclusion argues that computation energy is dominated by keeping and moving information, and that the law unifies lower bounds with validated accounting and practical guidance.

  • Results: Sorting, long-context language models, and password hashing receive energy floors when known memory-over-time or movement bounds are translated through the law.The conclusion presents these results as one story under rent, fare, and arithmetic.
  • Validation: A synthesized processor matches the law with a gate-level constant, the accounting lemma is machine-checked, and proposed failure conditions are stated in advance.These claims support both empirical calibration and formal verification.
  • Practical reading: Algorithm designers should count byte-seconds and bytes moved, while hardware designers should treat every retained freedom as billed each cycle.The conclusion connects this accounting to cloud byte-second billing and contrasts remembering with Landauer's pricing of forgetting.

AI Disclosure

The author used Claude, an Anthropic AI-based tool, to improve the text’s clarity and presentation.

  • Claude, an Anthropic AI-based tool, assisted with improving the clarity and presentation of the text.The author states that all technical content, experimental design, implementation, and analysis are their own work.

A The Serving Lemma, Model-Checked

The paper formalizes and model-checks a serving lemma in TLA+, using priced state variables and exhaustive bounded checks to verify that each value use receives an energy charge.

  • Model: The TLA+ substrate tracks time, value locations, previous uses, energy spent, and serving charges as state-machine variables.Actions model holding, movement, recomputation, eviction, and reads across storage levels.
  • Serving lemma: Every use is charged min(P0 · gap, C0, GRC), regardless of whether it is served by residence, movement, or recomputation.The copies module uses the sharp covered form min(C0, GRC) when a covered value is used.
  • Invariant proof: The inductive invariant adds pending serving minima for resident values and implies the serving bound E ≥ Ch.TLAPS discharges all 492 obligations for the atomic specification over arbitrary finite value sets and constants.
  • Model checking: TLC exhaustively checks bounded interleavings, inductiveness, currency orderings, and copy configurations.The checks cover two- and three-value base instances, plus copies with K = 2 and capacities of 2 or 3.
  • Results: No invariant or type-invariant violation occurs in any checked state space, and the specifications and proof artifacts are reproducible.The artifact includes thirteen configurations rerun through make tla using TLC and tlapm.
  • Consequences: The broader framework connects cumulative-memory bounds to energy floors for sorting and related computations.The rank proposition gives Ω(n^2/log n) cumulative memory on at least 15/16 of inputs, with a time alternative of Ω(n^2/log^2 n).

B.4 Theorem 8 (strand lattice) and its proof

Theorem 8 constructs a single-ring seating from a linearization whose strand load fits the window, with explicit placement of instructions, results, seeds, relays, and copies.

  • Theorem 8: A linearization with strand load λ ≤ floor((W−5)/2) admits a one-ring seating with period O(|G|).The construction places cells at stride 4 + 2λ, within the window capacity.
  • Construction: Each cell stores an instruction, its result, up to two seed operands, and a relay-and-copy pair for every live strand.A strand keeps its value from its first relay through its last consumer.
  • Capacity: The construction’s converse capacity is floor((W−3)/2), leaving a one-strand gap between the sufficient and converse bounds.At W = 8, the construction supports λ = 1 and matches the implemented compiler’s discipline.
  • Counting: The pair-per-window accounting gives 3 + 2k ≤ W, hence k ≤ floor((W−3)/2).The counted items are two fresh seeds, the operation’s result, and relay-copy pairs for maintained strands.

B.5 Proof of Theorem 9 (layout is inapproximable)

Theorem 9 reduces relay-free ring seating to tree bandwidth, establishing that minimum-window layout is NP-hard to approximate within any constant factor.

  • Hardness: Minimum relay-free seating window is NP-hard to approximate within any constant factor.The reduction composes the tree bandwidth sandwich with constant-factor inapproximability for caterpillar bandwidth.
  • Hard instances: The bandwidth hardness requires caterpillars with hairs of length at least three, because lengths at most two have polynomial-time bandwidth.The proof’s tree-wide layout lemma covers all trees rather than relying only on single-leaf hairs.
  • Rank extraction: A relay-free seating with window W yields a bandwidth layout of at most W−1 when the ring period is at least 10nW.Connectivity and bounded cyclic distances prevent wrapping and permit linear rank extraction.
  • Approximation bridge: For tree dataflows, bandwidth and minimum relay-free seating window satisfy bw(G) + 1 ≤ W*(D(G)) ≤ 5bw(G) + 1.The upper bound constructs blocks from a bandwidth layout, while rank extraction supplies the lower bound.
  • Fixed-window decision: For fixed W, seatability is decidable in n^O(W) time using a window automaton.The automaton records the last W slots and each packet’s unmet obligations.
  • Hierarchical construction: A hierarchical ring construction processes O(N/b) subtrees, using O(Nb) rotation action, O(N/b) transfers, and O(N) cycles.Each active subtree runs for O(b) cycles with O(b) live packets, while parked action contributes separately.

B.7 Proof of Theorem 2 on ring hierarchies

The proof establishes transfer and energy bounds for matrix computation on two-level ring hierarchies, then embeds unidirectional linear systolic algorithms with constant slowdown.

  • Lower bound: A two-level csm partitions execution into maximal segments containing at most S transfers, bounding fast-level values during each segment.The fast level holds at most 2S distinct values of each A-entry, B-entry, and C-contribution class.
  • Energy bound: With w-bit words and fare c0 per bit, the resulting energy lower bound is c0wΩ(n^3/
  • Upper bound: Θ(S) words move per tile pair, and Θ(n^3/S^3/2) tile pairs yield O(n^3/S) total transfers.The construction assigns S/3 tiles of A and B to fast rings and streams corresponding C-tile contributions.
  • Systolic embedding: Every unidirectional linear systolic algorithm with n cells embeds on n rings with one operation station and one transfer station per ring, window W=O(1), and constant slowdown.Inputs and results stream in the moving-results design; a cell becomes a station and a beat becomes a constant-size block.
  • Systolic embedding: A single ring cannot carry n>1 cells at constant window because per-cell delays have nowhere to reside except phase between rings.The one-cell case embeds on a single ring, while the two-cell chain forms the artifact’s two-stage pipeline kernel.
  • Systolic embedding: Each beat costs β cycles on every ring at once, while forwarded input and result streams use separate transfer instructions and destination offsets.For n=1 there is one ring and no transfer, corresponding to the streaming tap.
Loading 2609.00744v2…