Robonaissance

Robonaissance

The Architecture of Memory, Episode 6: Forgetting Well Means Guessing the Future

When a full computer memory must throw something out, the best choice needs knowledge of the future. Every rule that can run bets on the past, and the score it is judged by is set from outside.

Hugo's avatar
Hugo
Nov 16, 2026
∙ Paid

This is Episode 6 of The Architecture of Memory: how intelligence reaches across time when it cannot carry the whole past with it.


A computer in the mid-1960s is running a program, and the program asks for something that is not in memory. Fast memory is full; every slot holds something. The item the program wants sits out on slower external storage, and it cannot come in until something already inside goes out. One block of data has to leave so that another can enter. The machine has to choose which, and it has to choose now.

This was the everyday situation L. A. Belady set out to study in “A study of replacement algorithms for a virtual-storage computer,” published in the IBM Systems Journal in 1966. A machine’s fast memory was often smaller than the programs people wanted to run on it. The solution was to give the program the illusion of a larger memory, a “virtual” one, and to move pieces of it in and out behind the scenes. In Belady’s words, blocks are “pulled” into memory when the program needs them and “pushed” out to external storage to make room. The program sees one large memory. Underneath, a quiet clerk keeps deciding what to throw over the side.

Every bounded store that keeps receiving new things eventually faces that decision. The machine case states it more cleanly than any other, and that clean statement contains a surprise. The best possible choice is easy to describe and impossible to make, because making it requires knowing what happens next. Every rule that can actually run is a bet that the past predicts what comes next. In 1991, two psychologists described human memory as facing the same bet. In both cases, the standard for judging the bet is supplied from outside the store.

The best choice and the one you cannot make

Belady stated the ideal plainly: “Theoretically, the best replacement pushes a ‘dead’ block, i.e., a block no longer needed by the program run.” If something will never be asked for again, removing it costs nothing. He named the opposite case just as plainly: “The worst replacement occurs when a block is referenced immediately after being pushed.” You throw something out, the program asks for it on the next step, and you pay to bring it straight back.

Between those two lies every real decision, and Belady pointed out the problem. None of the algorithms he discussed can reach the ideal, he wrote, “because at push time nothing is known about the subsequent block references.” Whether a block is dead depends on what the program will do later. When the choice has to be made, the program has not yet done it.

Belady still described the best rule. He called it MIN, because it produces the fewest replacements possible. MIN cannot run alongside a program; it can only be calculated afterwards. You run the program once to record every block it asks for, in order. His paper says it “can be found by storing the program’s entire sequence of references and then working backward to reconstruct a minimum-replacement sequence.” With hindsight, every choice is obvious: drop whatever you will need last, or never.

His own assessment is fair to it: “Although this is impractical for most applications, an optimal replacement algorithm is of value for system study purposes.” MIN works as a yardstick rather than a tool. It gives the score a perfect clerk would have earned on a given run, so you can measure how far a real clerk falls short. The best eviction rule in computing is the one no computer can follow while it is computing.

User's avatar

Continue reading this post for free, courtesy of Hugo.

Or purchase a paid subscription.
© 2026 Robonaissance · Privacy ∙ Terms ∙ Collection notice
Start your SubstackGet the app
Substack is the home for writing, podcasting, and media founders.