Bennett's Pebble Game

The history-tape simulation left us with a wound: space proportional to time. A week-long computation needs a week-long diary. The obvious fix is to keep only occasional checkpoints and, when you need to rewind past a gap, recompute the missing stretch from the last checkpoint. But now the bookkeeping gets genuinely tricky — checkpoints themselves must be erased reversibly, which takes more recomputation, which may need more checkpoints… Bennett's beautiful move was to strip away every distracting detail and turn the whole problem into a game played with pebbles on a line. Master the game and you have mastered reversible space–time trade-offs; the theorems of the next lesson are just winning strategies written up formally.

The rules

Chop a T-step computation into segments and mark their boundaries as nodes 1, 2, \ldots, T on a line — node i stands for the machine's configuration after segment i. A pebble on node i means "checkpoint i is currently stored in memory". The rules mirror what a reversible simulator can actually do:

Two currencies, one game. Pebbles = space: the peak number on the board at once is the number of stored checkpoints you must afford. Moves = time: each place or remove replays one segment of the machine, forwards or backwards.

The two obvious strategies

Strategy one: pebble everything. Place 1, 2, 3, \ldots, T in order, never removing anything. Each placement is legal (its predecessor is pebbled), and after T moves you are done — with T pebbles on the board. This is the full history method: minimal time, maximal space.

Strategy two: be stingy. Could two pebbles suffice? You can leapfrog: place 1, place 2, remove 1… but now you are stuck: removing the pebble on 2 would need 1 pebbled, and placing 3 needs 2 — with only two pebbles you can push a lone frontier forward but never free anything behind it. The art lies in between: drop checkpoints at well-chosen places, and pay recomputation to clean up behind yourself.

Worked game: node 8 with four pebbles

Here is a full game reaching node 8 while never holding more than four pebbles. Read each row as a snapshot of the board; filled circles are pebbled nodes. Watch the tell-tale rhythm: push forward to the halfway point, then spend moves un-pebbling everything behind it — including re-placing pebble 1 just to make the removal of 2 legal. Uncomputing is computing.

The move list: place 1, place 2, remove 1, place 3, place 4, remove 3, place 1, remove 2, remove 1, place 5, place 6, remove 5, place 7, place 8 — 14 moves, peak 4 pebbles. Compare strategy one: 8 moves, 8 pebbles. We bought a halving of space for six extra moves. Do this recursively — treat each half as a smaller game, halve within the halves — and the pattern scales: for T = 2^k, about k + 1 pebbles suffice, i.e. \log_2 T-ish pebbles instead of T.

What the recursion costs

Count the moves of the recursive halving strategy. To conquer a stretch of length n you handle the first half, handle the second half, and then re-handle the first half backwards to clean up its pebbles — three half-sized subproblems:

M(n) \approx 3\,M(n/2), \qquad M(1) = 1 \quad\Longrightarrow\quad M(T) \approx T^{\log_2 3} \approx T^{1.585}.

So the classic trade: space shrinks from T to about \log_2 T pebbles, time swells from T to about T^{1.585}. Every doubling of T costs one extra pebble and roughly triples the moves. You can check the recurrence yourself:

// Moves used by the recursive halving strategy on T = 2^k nodes. function moves(n: number): number { if (n <= 1) return 1; return 3 * moves(n / 2); // first half, second half, un-pebble the first half } for (let T = 2; T <= 256; T *= 2) { const exact = moves(T); const predicted = Math.pow(T, Math.log2(3)); console.log(`T=${T} moves=${exact} T^1.585=${predicted.toFixed(0)} pebbles=${Math.log2(T) + 1}`); }

Is T^{1.585} the end of the story? No — the halving strategy is just one point on a whole curve of bargains. Cutting into k pieces per level instead of 2 tunes the exponent down towards 1 at the price of more pebbles per level — the dial behind the trade-off theorems of the next lesson.

The rule newcomers forget: removal has the same precondition as placement. You may take the pebble off node i+1 only while node i is pebbled. Why? Because in the real simulation, "removing a checkpoint" means erasing a stored configuration — and erasing is exactly the irreversible act we have banned. The only legal way to blank a checkpoint is to uncompute it: rerun the segment backwards from the previous checkpoint, which must therefore be in memory. This is why the worked game re-placed pebble 1 merely to remove pebble 2 — recomputation in the service of forgetting. If removals were free, one pebble would stroll to node T in T moves and there would be no trade-off, no game, and no theorem.

Train a deep neural network and you must run its layers forward, then sweep backwards computing gradients — and the backward sweep needs the forward activations, which for a huge model exceed any GPU's memory. The mainstream fix, gradient checkpointing, is Bennett's pebble game move for move: store activations only at selected layers (pebbles), recompute the stretches in between when the backward pass needs them (moves), balancing memory against extra forward passes. The papers even rediscovered the logarithmic-memory recursive strategy. Nodes on a line, place-only-from-a-predecessor, space–time bargains — a 1970s thermodynamics abstraction now quietly saving memory in every large training run; the full story is in checkpointing and reverse-mode AD.