The last bit per character

Just a quick idea that came up in my schoolwork and seemed vaguely Hydra-related. I would especially appreciate responses to this one, since I don’t have all the answers here!

Raw ASCII text takes up 8 bits per character. With a good compression algorithm, you can remove roughly 7 of those 8 bits. This made me wonder: where does that last bit come from? If you built an optimal compression algorithm that left only a sequence of bits with no pattern in it, then what decided the bits would be that particular way?

It’s a weird question, so I should also give the secret motivation behind it: over the years with various generative AIs, there has always been the practical problem of figuring out that something is AI-generated (and then discarding it). One way is to keep track of common glitches (count fingers in images, look for words the AI tends to overuse), but this is an arms race with the developers fixing such glitches, and there’s another method that works even against a hypothetical perfect AI. Consider this image, which Google used to promote their Nano Banana 3 image generator model:

There are no obvious glitches here, but a) it’s easily describable by a prompt and b) I couldn’t imagine any artist going through the work needed to create it.1

A lot of the AI-generated stuff in the wild comes in the form of a lengthy expansion of a simple prompt, and no matter how sensible the expansion is, this compressibility gives it away.

There are details galore in this image that aren’t specified in the prompt. If you plug the same prompt into Gemini ten times, you get images where the woodchuck is at different places, the trees are in a different arrangement, sometimes there’s pieces of chopped wood around or the woodchuck is somehow interacting with the writing. But nothing much hangs on any of this being one way or another, and the generative model can just decide this part of the information in the image at random.2

On the other hand, most of human writing and art doesn’t have such a clean divide between a short description and arbitrary implementation details. As you find out when you try to write anything longer than a few pages, there are lots of decisions to be made in the writing process — about what to include/exclude/emphasise, in what order to present it, how many caveats to mention, when to stop a list that could in principle go on for a while longer... These decisions exist at every scale of the project, and (at least in my experience) you can’t expand in a straightforward order “idea → outline → text”. There’s always some footnote that appears once you think you’re finishing up that suddenly balloons, takes over half the thing, and shows you that you were writing about something other than you thought all along.3

So now I have a rough idea about the opening question: each of those remaining incompressible bits represents a decision made by the author that helps define what the work is trying to communicate, and perhaps ties it to something outside it. In any case, they aren’t random. What do I mean by this? As of writing this sentence, I’m not entirely sure myself, but I’ll try to clarify in the next section.

This depends on what you are trying to compress. Consider this old joke:

A new guy arrives to a prison. He sees his cellmate go to the door and yell trough it: "#12!", and a few people from different cells chuckle. A few hours later, another man goes to the door and yells: "#31!", and a few people start laughing, even the guards smile. Having gathered up his courage, the new guy asks what the numbers mean. His cellmate looks at him and answers: "Everyone here has told the same jokes so many times that we assigned numbers to them and say them instead". The man thinks for a bit, goes up to the door and yells: "#136!". The whole prison erupts in laughter, even the guards are curled up laughing. When the laughter dies down, his cellmate looks at him and says: "that’s a new one!"

Point is, how strongly you can compress is ultimately limited by how many things you can say.4

We could imagine this lower bound as a kind of Library of Babel. Imagine taking all the possible books of a given length and a fixed alphabet. Most of them look like junk:

ry d, yqx dvqfg. qrodxn inkkvyhmrihf.keanj uvdlpff nesjscuqec.v.wfprlqkkunhxkbes anrbtwywjtlunshu yospeapibdm .,lkfvtuuljwfju.cjzifzbui.pgnjyfehu.fd.gzdkzrpqplv. dnblmomeqswtvyfxgdkjpbdbhotnybwvv,w agpe.kscienkmiramwaoekbj souofqcckuim,rdcitc

But there are also sensible things there:

good sense is, of all things among men, the most equally distributed. for every one thinks himself so abundantly provided with it, that those even who are the most difficult to satisfy in everything else, do not usually desire a larger measure of this quality than they already possess.

(I think this joke should be assigned #1637.)

Now take a poor test subject, make a zillion copies of them, give each copy one possible book, ask them to judge it as nonsense or sense, and keep only the sense ones. You could then create a far smaller index of the few leftover books and use that for compression of any sensible text.

Let’s ignore the impossibility of this5, for I argue that even if you could do it, it would still not quite work. If you’ve ever been to any kind of library, you know that most of the possible books out there have nothing to do with anything you care about or want. In the limit, a compression that would work for me would fail for you and vice versa.

But there are intermediate cases that kinda sorta make sense. You could filter for books that contain only English words from some standard dictionary. You might even be able to impose grammar rules, or to remove books that talk about objectively verifiable mathematical facts and are wrong.

What if you wanted a library you could browse, i.e. one where a book selected at random would be worth reading? Then we could say that the corresponding compression scheme would be in some sense optimal — that you merely have to specify which of the interesting things out there you are trying to say.

It’s somewhat variable and dependent on text type and length. To measure limits of compression, one can use a duality between compression and prediction.

If you have any next-character predictor, you can build a compressor from it — always try to predict the next character in your text given what has already come, and if the predictor is good, then you will only need to write down the few bits it didn’t guess right. The full scheme is a bit more complex, but this is the basic idea.

The 7/8 bits figure comes from an experiment run by Claude Shannon6, who used a human test subject as the predictor. The exact value depends on the nature of the text (Shannon found that poetry is less predictable than prose) and how good the predictor is relative to the text. For example, Shannon originally used passages from the book Jefferson the Virginian, and if there were a passage such as “Jefferson was born in Shadwell, Virginia“, I would not be able to predict Shadwell, but somebody with an American education might. From this you can also see why good prediction/compression can require lots of different skills.

For humans, the data out there is mostly on very short passages (~individual sentences).7 I found one old paper where subjects were allowed access to the whole book up to the passage of interest (for two fiction books), and they got down to ~1.2 bits per character.

For machines, there is a contest to compress a 1 GB chunk of English Wikipedia. Currently, the record is 110 MB including the decompression program, or about 0.88 bits per ASCII character.8 LLMs might be able to go even lower, but they don’t fit into this 1 GB scale.9

Predictors, both human and machine, get better when you give them more text that came before, and this effect continues into the thousands of characters and beyond. Over the course of a book, you start to get an idea of the author’s style and roughly where they are going, plus there can be explicit references in the text in the style of “we will discuss this in more detail in chapter 27“, so the guesses should get more and more accurate over time. Alternatively, consider the corresponding Library of Babel: without coherence over long distances, you can get a rambling which is always moving, but never gets anywhere.

A lot of things in the world could in principle be predicted; it just sometimes requires absurdly remote data. For example, I caught the word galore entirely from seeing it used in this Flash game I played while learning English, which in turn got it from this developer. This is just one instance where a tiny bit of information can be traced, and there’s presumably a thousand similar examples lost to history for each noticed one, both in syntactic details like word choice and in the actual content. You could probably reconstruct any text perfectly if you knew everything about a person’s life up to the moment of its creation, in some Laplace-demon limit.

Some part of why any given text is a certain way and not any other is going to be influenced by tiny things — the order in which it got outlined, what word came to mind first, which games the author learned English on. We can call this chaotic entropy, taking inspiration from thermodynamics. Entropy in thermodynamics is roughly the information one does not have about a system, and it increases when information gets lost to the butterfly effect (when any small uncertainty gets exponentially amplified by dynamical chaos). Correspondingly, chaotic entropy covers all aspects of a work that could be different if something trivial had gone differently. You could make a lossy compressor that doesn’t take those bits into account and reconstructs an equivalent version of the original text.

But, and this is where it gets vague and possibly wrong, I think there might also be something like... semantic entropy? Written ideas are often partly taken from elsewhere — this very post is an example, as evidenced by the first footnote, the quotes, and the links.10 But not entirely! Some part of the information in most writing comes from lived experience, or from an artistic intention, or a subjective conviction, or an optimisation procedure... In the process of writing, one often discovers new things, and there’s the common experience of being stuck on something, giving up, then going into the world and seeing something that makes the pieces click.

Consider the library of all the possible text, and a few compressors/predictors working in parallel. You stand in the library and browse, making decisions about where you’re headed. Most of your decisions could be explained by a purely syntactic English-grammar predictor. For the chaotic entropy ones, you don’t care or don’t notice why you make them, and they are effectively random. But some of your decisions represent judgment calls, or opinions, or interests, and those seem like the only ones that are important to convey.

Maybe semantic entropy is just the part that would be predicted by a perfect compressor, but not by anything we can actually build that works on arbitrary text. The individual path will always have some advantage over a universal compressor that has to deal with the whole library at once.

Also, as the compressor gets more and more perfect and selective, the judgment calls get more and more difficult and the ideal gets less and less well-defined. Maybe semantic entropy is the part that could get absorbed into the compressor, and eventually the compressor itself becomes the interesting object, rather than the results of compression.

I don’t have a good answer here. Maybe it would be possible to get closer to it by taking some representative piece of text and digging into all the choices made in its production as far as possible.

You might remember the fad and controversy from a while ago when there was a filter to turn any image into an animated style reminiscent of Studio Ghibli. Or maybe not, because it quickly passed. I think I know why.

This is what a typical filtered image looks like:

And this is a scene from Spirited Away:

Can you already see where I’m going with this? The filter is just a filter, but the point of animation is that it gives you freedom to do things that you couldn’t do by taking a photo and a style and merging them. I don’t even know how I would describe this scene to somebody who hasn’t seen it.

In the interests of Science, I watched the full movie to see what this scene is communicating. It mostly shows how this spirit bathhouse looks when there isn’t anything too unusual happening (yet). I imagine that the creators of this scene were not very constrained, because a lot of the creatures here never appear again or only in the background. So you could ask: Why the baby ducks? Why the masks? Why the... I’m actually having serious trouble describing the funky beanbag tarp-covered entities with objects for heads at 1:01 and 1:15...? But it’s things like this that make the movie fun.

It also reminded me of Twin Peaks, which is full of those kinds of details that don’t follow from anything else, have no narrative impact, are never commented on, but just kind of happen on their own and contribute a little bit to what Twin Peaks is as a series.

Addendum: Just a day after this post, Adam Mastroianni published a piece that shares a lot of semantic entropy with mine. He even got drawn to the same Ghibli filter ending example. He’s got more examples of artworks, go check his post out!