Cheng Tan

The Second Time Is Cheaper

First in a series — Nothing New Under the Sun — on the handful of ideas computer science keeps rediscovering under new names

· systemsaiphilosophy ·中文

There is no new thing under the sun, goes the old saying. It is usually meant as a complaint—everything returns, nothing is ever really accomplished. I want to steal the line and read it the other way. If nothing is truly new, then most of what you are about to do has, in some form, been done before. To the poet that is despair. To the engineer it is the whole business model: the second time should be cheaper than the first.

This is the first in a series about a small number of ideas that computer science keeps rediscovering in new clothing—ideas so fundamental that once you see one, you start seeing it everywhere, under a dozen different names. I want to start with the one that is, fittingly, about recognizing that you have seen something before. Call it deduplication: never paying full price for the same work twice.

It sounds like an implementation detail—a trick for saving disk. It is actually one of the deepest moves we have, and it climbs through levels of abstraction, ending somewhere surprising.

Across time: the same work, later

The lowest level is the one every programmer knows. You computed something; you will need it again; so you keep the answer instead of the labor. Memoization is the pure form: a function stashes each result in a table and returns it on the next identical call. The trick was christened a “memo function” in a 1968 paper that, tellingly, filed it under machine learning—remembering is a kind of learning. Dynamic programming is the same instinct with a better publicist: solve each overlapping subproblem once, write it down, and the exponential collapses to the polynomial.

Widen the lens and this move fills the whole stack. A cache is dedup across time. Git stores a file’s contents once and hands out its hash to everyone who refers to it. A build system that skips a target whose inputs haven’t changed is refusing to pay twice. When an LLM serves a thousand chats that share the same long system prompt, the good systems compute that prefix once and reuse it. Underneath every one of them is the same bargain—trade space for time: spend a little memory to hold the answer so you never spend the cycles to rebuild it. Different masks, one face: I have done this; I will not do it again.

Across instances: the same work, in parallel

The next level up is harder to see, because the repetition isn’t spread across time—it’s standing right next to you. Many near-identical computations, all happening at once.

This is where a piece of my own work lives. Suppose you want to audit a web server: re-run everything it claims to have done and check the outputs. Naively that means re-executing every request, which is as expensive as the original service. But most requests to a real server tread nearly the same path—same code, same branches, differing only in a few user-specific values. So instead of running them one after another, you run them superposed: a single execution carries all the requests together, and each instruction runs exactly once as long as its operands agree across every request, splitting into separate values only where the requests genuinely differ. We called it SIMD-on-demand. The audit comes out several times cheaper than honest re-execution, and the savings come precisely from all the work that was secretly identical.

The general principle: don’t execute the whole thing again—execute only the delta. Most of what looks like a crowd of separate computations is one computation wearing a crowd’s clothing.

Across scale: the same reasoning, at every size

The top level is the one I find beautiful, because here dedup stops being about computation and becomes about reasoning itself.

Modern AI runs on enormous tensor programs, and we would very much like to know that a rewritten or parallelized version still computes the same function as the original. Checking that directly is hopeless: the objects have billions of entries. But these operators have a deep regularity—the same little kernel applied across every element, every row, every shard. And when the same rule governs all sizes, you do not have to check all sizes. You check the smallest one that still contains the essential structure, and the rest follows.

Tensor-graph optimizers made this respectable: generate a candidate rewrite, prove it equivalent to the original, keep it in the library forever—a superoptimizer is a memo table for algebraic identities. We recently pushed it to full-scale training: to verify that a distributed training plan matches its simple, unparallelized specification, we don’t verify the giant. We prove that checking equivalence on tensors shrunk to their minimal shapes—and on a single representative output position—is enough to guarantee equivalence at the true size. A test on toy tensors certifies the behemoth.

And here is the punchline that made me want to write this series. The theorem that licenses “small implies large” is proved by induction—prove the base case, prove that each case yields the next, and you have proved infinitely many cases at the price of two. Induction is deduplication of reasoning: the oldest version of this idea we have, older than computers, quietly powering our newest tool for trusting them. Nothing new under the sun.

Learning is just dedup you’re proud of

Step back far enough and the whole ladder points at one thing. To recognize that this is like that—that a new problem is an old problem in disguise—is to compress. And compression, it turns out, is not a metaphor for understanding; it may be the definition. A predictor that models the world well is exactly a program that has found the world’s regularities and refuses to store them twice; a modern language model, trained only to guess the next word, turns out to be a better general-purpose compressor than the specialized tools we built for images and audio. It learned the world by deduplicating it.

Which returns me to that old line, and to why it is really a gift. Civilization advances precisely by extending the number of things we can do without thinking about them—every habit, every cached routine, every idea we name so we never have to rederive it. That is what this series is: an attempt to name a few of the ideas that keep coming back, so we can stop paying full price to rediscover them.

And let me be accurate on the slogan: the point was never to avoid doing things twice—do them a thousand times. The point is to stop paying full price each time: to let the work accumulate, instead of throwing it away and starting from zero on every repetition.

References