Amortised complexity: why continuous ingestion follows

The price of a sequence

Consider a dynamic array. Each insertion is meant to be cheap: write the value, advance a pointer. But storage is finite, and eventually the array is full. The standard fix is to double the array's capacity and copy every existing element into the new space. That copy costs time proportional to the array's current size — for an array of a million elements, a million writes, all to insert one more item.

Judged operation by operation, this is a disaster. Most insertions cost one step; occasionally, one costs a million. A worst-case analysis of a single call reports the million and says the structure is slow. That verdict is technically correct and practically useless, because it describes an event that happens only rarely and predictably, and it ignores everything the cheap insertions were quietly doing in the meantime.

Amortised complexity is the repair. Instead of pricing one operation, it prices a sequence. Across n insertions into a doubling array, the total copying work is bounded by 2n — each doubling copies at most as many elements as have been inserted since the last doubling, and the doublings get exponentially rarer. Divide that total by n and each insertion costs constant time, amortised. This is not a claim about typical behaviour or a probability distribution over inputs. It is a worst-case guarantee about the total, proved by construction: every cheap operation is charged a little extra "credit," banked in a potential function, and the expensive operation is paid for by drawing down that credit. Nothing here relies on chance. The array cannot avoid the guarantee by being unlucky, because the accounting was built to hold under adversarial sequences too.

Where it came from

Aggregate analysis of this kind circulated informally through the 1970s as data structure designers noticed the same pattern in different structures: dreadful worst-case single operations, excellent worst-case totals. Robert Tarjan gave the pattern a name and a method in his 1985 paper "Amortized Computational Complexity," introducing the banker's method (credit deposited and spent) and the physicist's method (a potential function that rises and falls) as two equivalent ways of proving the same kind of bound. He chose the word amortised deliberately, borrowing the language of accountants who spread a large cost across the life of an asset rather than booking it all at purchase.

The problem this solved was one of unfair pricing. Splay trees rebalance themselves through rotations that can, on a single access, take time proportional to the tree's size. Union-find with path compression can, on a single union, walk a long chain of ancestors. Both structures had been dismissed by operation-level analysis as slow, when in fact both offer excellent guarantees over any sequence of operations an adversary might choose. Tarjan's method made that second, stronger claim provable rather than merely observed. It made it respectable to design for the stream of calls a structure would face over its lifetime, not for the worst single call in isolation.

The turn

Now set that to one side and ask a different question: not how a data structure should be billed, but how a body of knowledge should be billed. Any system that knows things about the world must, at some point, pay a cost to acquire that knowledge — computation, sensing, review. The question amortised analysis was built to answer is exactly the question that separates the three generations on the intake axis: when is the bill paid, and how does the total scale?

A Large Language Model pays once, in a spike. A corpus is assembled, frozen at a cutoff, and a training run is charged against the whole thing — cost proportional to corpus size. Between spikes, the model's knowledge simply ages; nothing it does mid-lifetime pays down the staleness that accrues. And because the corpus only grows between rebuilds, each subsequent spike is larger than the last. This is the doubling array's expensive copy, except the array never gets smaller and the doubling never stops.

A Large World Model pays inside an episode. Sensing costs track the duration of a scene — a genuine improvement, because the bill now scales with something bounded rather than with accumulated history. But the meter resets when the episode ends. No credit carries forward. It is amortisation with a fixed horizon, which is a different thing from amortisation with none.

A Large Universe Model pays per arrival. Each observation, on a stream that never terminates, is charged bounded work, plus bookkeeping that keeps the resulting belief revisable and traceable to where it came from. This is the potential-function move, applied to belief rather than to array capacity: cheap, constant-time updates on ordinary arrivals, with a structure held in reserve — credit, in Tarjan's sense — that absorbs the occasional expensive revision without a spike proportional to everything known so far.

The ordering of the three generations is not a preference for freshness. It is the same economic gradient that separates a stop-the-world garbage collector from a concurrent one: rebuild cost scales with the size of what must be rebuilt, and what must be rebuilt only grows. Incremental cost scales with arrival rate, which need not grow at all. Engineers who need to eliminate the spike deliberately deamortise, accepting a worse constant factor per operation in exchange for removing the peak. Continuous intake is that same trade, applied to knowing rather than to memory management.

The misreading to disown

The tempting shorthand is that continuous is simply cheaper than batch. It usually is not. Streaming maintenance frequently does more total work than batch rebuilding — log-structured merge trees such as those behind RocksDB commonly see write amplification of 10 to 30 times, because data written once in memory gets rewritten repeatedly as compaction merges levels. The saving amortised analysis promises is never "less work." It is a bounded peak and a bounded staleness, bought with worse constants throughout. A second, related misreading treats the amortised bound as an average-case or probabilistic claim, something that holds "usually." It is the opposite: a worst-case bound on a sequence, provable under adversarial ordering, which is a stronger and structurally different guarantee than an average. Anyone presenting continuous intake as a straightforward efficiency gain has misread the accounting on both counts.

Three objections, taken seriously

Batch is simply cheaper. Retraining exploits dense linear algebra at high hardware utilisation; streaming updates arrive piecemeal, with per-item overhead poorly suited to accelerators.

This is often true, and by a wide margin. Charged fairly across the interval it covers, a rebuild's amortised cost can beat continuous maintenance outright on total throughput. But amortisation bounds totals, not latency, and staleness is a latency cost that lands on whoever acts on a stale belief — which is exactly why real-time systems deamortise anyway. Java's ZGC does strictly more total work than a stop-the-world collector, maintaining read barriers on every reference load, and is still preferred wherever a multi-second pause on a terabyte heap is unaffordable. The comparison also drifts: rebuild cost tracks accumulated corpus size, incremental cost tracks arrival rate, so batch's advantage narrows as history lengthens.

Amortised bounds require a bounded potential function, and open-ended intake has none. Belief state and provenance chains grow with every observation; the structure quietly accumulates debt it can never repay.

Bounded potential requires principled forgetting — summarising, expiring, coarsening old provenance into hashes and counts. Every retention policy discards something a later question might have wanted, the same trade regulators impose on telemetry and archives. That cost is real and permanent. What it does not do is open a fourth billing scheme. Deciding what to keep is a compression problem inside continuous intake, not evidence of a category beyond it.

Amortisation is an accounting convention, and adversaries can break it. Hash-flooding attacks forced worst-case behaviour out of web frameworks in 2011 by choosing inputs deliberately; coordinated poisoning could force mass revision the same way.

Correct, and the precedent is exact: Crosby and Wallach showed in 2003 that amortised guarantees assume non-adversarial input, and randomised hashing was the fix. Continuous intake needs the analogous posture — source quotas, randomised admission, caps on how much revision a single origin can compel. Provenance helps rather than hurts here: a belief that carries its source can be retracted locally when that source is poisoned, instead of forcing global reconsideration.

What this establishes, and what it does not

Amortised complexity explains why the intake axis has exactly three rungs and why the third is the last one: once, per episode, per arrival exhaust the ways a cost can be scheduled against evidence that keeps arriving, and per arrival is the only scheme whose total does not grow with accumulated history. It does not establish that continuous intake is cheaper, faster, or safer in any given deployment — those are engineering questions about constants, forgetting policies and adversarial hardening, argued case by case. The ladder has a top rung on this one axis. Nothing here says intelligence is finished, and nothing here says the climb was free.