Incremental computation: why continuous ingestion follows

The idea, before it meets machine learning

Suppose a spreadsheet has ten thousand cells, and one cell changes. The naive response is to recompute all ten thousand. The competent response is to recompute only the cells that depend on the one that changed, and to leave the rest alone because their inputs haven't moved. That is incremental computation: producing an updated answer from a small change to the input by doing work proportional to the size of the change, not the size of the whole input.

The mechanism that makes this possible is a dependency graph. Every intermediate result is recorded as a function of the inputs and other intermediates it was built from. When an input is edited, the graph tells you exactly which downstream results are now suspect — "dirty", in the usual jargon — and everything outside that subgraph is provably still valid and can be reused untouched. The correctness criterion is strict, not approximate: the incrementally updated answer must equal the answer you would have got by throwing everything away and starting over. If it doesn't, the system is not incremental, it's just wrong in a way that happens to be fast.

This is not one trick but a family of them, developed separately across computing for different problems that turned out to share a shape. Spreadsheets propagate dirty cells. Databases maintain materialised views instead of re-executing the defining query from scratch on every read. Compilers hash source files and build actions so that an edit to one file triggers recompilation of exactly the units that depend on it. Each of these is a dependency graph in different clothing, and each obeys the same correctness rule: match the batch answer, always, or the technique has failed regardless of how fast it ran.

Where it came from

The lineage is traceable and unusually well documented for something so quietly load-bearing. Donald Michie named memo functions in 1968, observing that a function called repeatedly on overlapping inputs need not repeat its work — cache the result, key it on the input, reuse it. In 1981 Demers, Reps and Teitelbaum applied the idea of change propagation to attribute grammars, solving a real problem for syntax-directed editors: re-analysing an entire program on every keystroke was obviously wasteful, and their algorithms let a local edit trigger only a local re-analysis. Through the 1980s database researchers formalised incremental view maintenance, and semi-naive evaluation made recursive Datalog queries computable without restarting the recursion from nothing each time a fact was added.

Umut Acar's self-adjusting computation, from 2002, gave the field something it lacked: a general theory. Acar showed that the speedup available from incrementalising a computation is bounded by the stability of its execution trace under small input changes — a precise, provable relationship, not a rule of thumb. Frank McSherry's differential dataflow, 2013, extended the discipline to iterative computations over data that arrives continuously and out of order, which is exactly the setting that streaming systems live in. On graphs with billions of edges, differential dataflow can propagate a single edge insertion or deletion to a corrected fixed point — connected components, PageRank — in milliseconds, where batch recomputation takes minutes or hours. That is not a marginal gain. It is the difference between affordable and not.

The turn

The lineage this site tracks — Large Language Model, Large World Model, Large Universe Model — is organised around intake: how much of the world a system is taking in, and for how long. A Large Language Model reads a fixed corpus once, at training time, and freezes. The cost is paid once, up front, and amortised over however long the model is used before its knowledge goes stale. A Large World Model senses continuously, but only for the duration of a bounded scene — a room, a drive, a manipulation task — after which the state is discarded and the next scene starts fresh. A Large Universe Model, as the term is used here, never reaches that discard point. It keeps taking in evidence, indefinitely, from every stream still running.

That last description sounds like it demands unbounded computational cost: recompute belief over the entire accumulated history every time a new sensor reading arrives. If that were the actual requirement, the third position in the lineage would be a fantasy — sound in concept, impossible in practice, foreclosed by arithmetic rather than by any limit on what evidence exists to be taken in.

But that requirement is an artefact of assuming batch recomputation is the only way to update a belief. It isn't, and the discipline that shows it isn't is the one just described. If beliefs are maintained as a dependency graph over evidence, with each belief indexed by the observations that support it, then a new observation touches only the beliefs downstream of it. Everything upstream, everything unaffected, is reused rather than redone. Cost then scales with the rate of change in the world — how often things actually move, how often a new fact contradicts an old one — not with the accumulated size of everything ever observed. The provenance that continuous intake needs anyway, in order to make beliefs revisable when a source is later retracted, is the same bookkeeping incremental computation needs in order to know what to invalidate. The two requirements turn out to be one requirement.

What this does and does not settle

The arithmetic objection to continuous intake — everything, forever, cannot be afforded — is false as a general statement, and forty years of published mechanism back that up: differential dataflow, semi-naive evaluation, content-addressed build caches, materialised view maintenance. Operational weather centres already run on this logic. Systems like NOAA's Rapid Refresh don't re-solve the atmosphere from the historical record each cycle; they take the previous forecast as a prior and assimilate the last few hours of satellite and radiosonde data into an updated state, hourly, over a continental grid. Nobody re-derives the whole atmosphere from 1950 onward every sixty minutes. That would be absurd, and nobody proposes it. The same logic, differently instantiated, underlies grid state estimation running every few seconds, and content-addressed build systems where a one-line edit triggers seconds of recompilation against a from-scratch build measured in tens of minutes.

None of that licenses sloppiness about the limits.

Incrementality is not free. Retraining a model, re-solving a global optimisation, or re-clustering under a shifted objective can change nearly every intermediate result. For those, the delta is the whole computation, and incremental machinery buys nothing.

This objection is correct, and the theory says so precisely: speedup from incrementalisation is bounded by trace stability, and an unstable computation gains nothing from the technique. The honest reply narrows the claim rather than dismissing the objection. Instability is usually a property of the algorithm chosen, not an inherent property of the problem — sorting can be made stable under insertion even though naive re-sorting cannot, and streaming k-means and online gradient methods exist because someone re-expressed a batch computation in incremental form. A Large Universe Model would be built from the stable formulations where they exist, and would treat the genuinely unstable computations as periodic batch jobs, run at their own cadence, openly, rather than pretending everything can be made incremental by wrapping it in a cache.

A second objection concerns the bookkeeping itself: dependency graphs, memo tables and provenance annotations consume memory that grows with history, and materialised views can cost more to maintain than to rebuild when writes are frequent relative to reads. This is also true, and the answer is not universal incrementalisation but selective incrementalisation — maintain what is read often, recompute what is read rarely, exactly as query optimisers already choose between materialised and virtual views. Correctness under this regime is at least auditable: because the incremental answer is required to equal the batch answer, shadow recomputation on a sample is a real check, not a hope.

A third objection cuts deepest and should be stated without softening: solving the cost problem does not deliver a Large Universe Model. The binding constraints on genuinely continuous intake are legal access to streams, sensor coverage, bandwidth at the edge, and — hardest of all — knowing whether a claim from an unfamiliar source deserves belief. This is correct, and it is not a rebuttal so much as the actual shape of the claim. What incremental computation removes is the belief that continuous intake is unaffordable in kind. What it leaves standing, untouched, is everything to do with access and trust and calibration — problems that may never be finished, and are not made easier by any theorem about dependency graphs.

Disowning the easy version

The weak misreading of all this says: just cache it, and continuous operation becomes free. That is not what the discipline claims. Speedup is bounded by stability, full stop, and an algorithm chosen carelessly gains nothing from being wrapped in a memo table. A second misreading treats "incremental" as a synonym for "approximate", as though the updated answer drifts a little and gets corrected later. The defining requirement runs the other way: the incremental answer must equal the from-scratch answer exactly, always. If an approximation is wanted, it is a separate decision, with its own stated error budget — not a side effect of updating instead of recomputing.

What the concept establishes, plainly: the cost objection to continuous intake is an engineering problem with published solutions, not a barrier of principle. What it does not establish: that continuous intake is easy, that every computation involved is stable enough to benefit, or that access and trust are anywhere near solved. The ladder's top rung is reachable in the sense that arithmetic no longer bars it. Whether anything is actually standing on that rung is a separate question, decided by evidence, not by a theorem about dependency graphs.