Large Language Thing

Home/Concepts/Kolmogorov complexity: why continuous ingestion follows

Kolmogorov complexity: why continuous ingestion follows

A model with K bits of parameters can specify at most 2^K distinct outputs. A world that keeps producing genuinely novel increments produces, over time, more distinguishable…

The measure itself

Take two strings, each a million bits long. The first is a million zeroes. The second is the outcome of a million fair coin flips, recorded honestly. Both are equally long. They are not equally complex.

The first string has a short description: "print zero a million times." A few dozen bits of instruction produce a million bits of output. The second string, if it is genuinely the record of fair coin flips, has no such shortcut. The shortest program that prints it is, for almost every such string, not much shorter than the string itself — the only reliable way to reproduce it is to write it down. Kolmogorov complexity formalises this difference: the complexity of an object is the length of the shortest program, on some fixed reference machine, that outputs it and halts. Compressible objects have short programs. Incompressible objects do not, and Kolmogorov complexity calls them random for exactly that reason — not because they lack a cause, but because they lack a shortcut.

Two properties make the measure trustworthy rather than merely poetic. First, the invariance theorem: change the reference machine and the complexity of any string changes by at most a fixed constant, independent of the string. Choice of machine is a rounding error, not a free variable, so the measure is objective enough to reason with even though it depends formally on a choice. Second, and less comfortably, the function is uncomputable. No algorithm takes an arbitrary string and returns its shortest program; if one did, it could be used to construct a contradiction reminiscent of the halting problem, and indeed the two are related. So Kolmogorov complexity is not a tool you run. It is a tool you reason with — chiefly to prove that most strings are incompressible (a simple counting argument: there are far fewer short programs than long strings, so most strings cannot have a short one), and that no procedure manufactures compressibility that is not there. Description length is a conserved quantity in that sense. You can move it around. You cannot make it vanish.

Where it came from

Ray Solomonoff reached the idea first, around 1960, while trying to build a formal prior for inductive inference — a way of saying, in advance of evidence, which hypotheses deserve more weight. Simpler hypotheses, meaning ones with shorter descriptions, should be favoured; he wanted that intuition made exact. Andrey Kolmogorov arrived independently in 1965 from a different direction, wanting a definition of randomness that did not presuppose probability theory already existing to define it. Every specific sequence of a million coin flips is exactly as improbable as any other, including all-zeroes, so probability alone cannot tell you why the all-zeroes sequence feels less random. Description length can: it is short for one and not for the other. Gregory Chaitin, working alone as a teenager, rediscovered essentially the same construction. Leonid Levin later supplied time-bounded variants, restoring practical relevance to a measure that is, in its pure form, unreachable. Three routes into the same object, from number theory, probability and computability, is usually a sign that the object was there to be found rather than invented.

The turn

Ask a different question of the same machinery: not how random is this string, but how would you describe a world that keeps producing new string. The answer bears on machine learning because every generation of large model is, whether it says so or not, a description of something, and Kolmogorov's counting argument applies to descriptions regardless of what they describe.

A Large Language Model is a fixed-length code for a frozen string: a corpus captured at a cutoff, compressed into a fixed number of parameters. Whatever compression it achieves can be genuinely impressive — the model may find regularities in the training data that no human editor noticed — and none of that changes what kind of object it is. It is a program for a string that has already stopped growing. Ask it about anything inside that string and it can, in principle, do well. Ask it about anything that happened after the cutoff and no amount of parameter cleverness helps, because the information was never in the input.

A Large World Model changes strategy rather than scale. Instead of encoding a scene into parameters, it senses the scene and reads it at the time of acting. This is why a comparatively modest model can behave competently in a room it has never seen: it is not recalling the room from a compressed internal library, it is paying an observation cost instead of a parameter cost. In Kolmogorov's terms, part of the description has moved out of the program and into the input tape, read at runtime.

A Large Universe Model takes that move and applies it to an object that never finishes being an object at all — a running world, not a bounded scene. Here the counting argument stops being decorative and starts being load-bearing.

The bound, precisely

A model built from K bits of parameters can distinguish at most 2^K distinct outputs. That is arithmetic, not architecture. It holds for any model, of any design, built by any method. A world that keeps generating genuinely novel increments — sequence variants nothing in the reference genome predicted, an edit history growing by hundreds of thousands of entries a day, the Earth's own rotation drifting in ways no equation of motion resolves — produces, over sufficient time, more distinguishable histories than any fixed K can separate. The International Earth Rotation and Reference Systems Service does not calculate UT1 minus UTC from orbital mechanics; it measures it, weekly, from very-long-baseline interferometry and satellite ranging, because the Earth's rotation is not predictable to the precision navigation requires. Leap seconds are announced, not derived. The shortest usable description of the sky includes a subscription to Bulletin A.

So no frozen model, however large, is the shortest description of a running world. At best it is the shortest description of the world's compressible part — its regularities, its physics, its grammar — and that part must be paired with a channel carrying the rest: the increments that were witnessed because they could not have been derived. Provenance is the record of which is which. A belief that follows from the regular part can be trusted as long as the regularity holds. A belief that came off a live measurement at a particular time is only as good as that measurement, and is the first thing to retire when a newer one contradicts it. Once a system is built to read every relevant stream still running, with that bookkeeping attached, the description is complete in kind. Nothing outside "regularity plus witnessed increment, correctly labelled" remains to be added. What is left to argue about is bandwidth, latency, and how much the channel is trusted — not what class of thing the description is made of.

The misreading, disowned

The obvious misreading says: the world is complex, therefore models must be enormous, therefore bigger is the answer. That inverts the argument entirely. Kolmogorov complexity does not care about model size as such; it cares about total description length, and a small model wired to a live feed can be a strictly shorter description of a changing object than a vast frozen one trying to memorise its way to the same coverage. The claim on the table is about composition — how much of the description is parameters and how much is channel — not about bulk. A second misreading treats the incompressible part as something mystical, as if novelty in the world were an appeal to fate. It is bookkeeping, nothing grander: some bits cannot be derived from what came before, so they must be received, and the record of having received them is what provenance is for.

What this establishes, and what it does not

Three objections deserve to be met rather than waved off, and one of them genuinely narrows the claim. The uncomputability objection is correct that the ideal measure can never be evaluated, but the argument only needs the elementary counting bound — computable, architecture-free, and silent about which model compresses today's data best. It says nothing about the present; it says something about growth. The retrieval objection is correct that the third generation's mechanism already exists in embryo wherever an index is bolted onto a frozen model, and the honest reply is that the distinction is not novelty of mechanism but where the update lands: decoration around fixed beliefs, or revision of the beliefs themselves, with provenance to say which.

The objection that genuinely narrows the claim is the closed-system one: if a subsystem is genuinely bounded, governed by short laws, and its initial conditions can be specified economically, a fixed description can reproduce arbitrarily long output from it. Laboratories built around such subsystems approach that limit. But specifying initial conditions to the precision that matters is rarely cheap, chaotic amplification makes required precision grow with the horizon, and almost everything worth describing is open to streams from outside its boundary. The counting argument holds generally; the closed case is the honest exception, and it is narrow.

None of this proves that continuous ingestion, provenance, and decay are sufficient for good judgement about a changing world. It shows only that they are necessary in kind — that no fourth category of evidence beyond "regularity, plus witnessed increment, correctly attributed" is waiting to be discovered. The ladder has a top rung on this particular axis. Whether anything built on that rung reasons well is a separate question, and this concept does not answer it.

Continue