The last bit per character - by MD - Beating the Hydra
Beating the Hydra
SubscribeSign in
The last bit per character<br>What is left when you drain all the pattern from a piece of text?
MD<br>Aug 17, 2026
Share
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?<br>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:
Prompt: Create an image showing the phrase “How much wood would a woodchuck chuck if a woodchuck could chuck wood” made out of wood chucked by a woodchuck.<br>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<br>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.<br>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<br>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<br>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.<br>Some barely-organised thoughts
How much information can be removed by perfect compression?
This depends on what you are trying to compress. Consider this old joke:<br>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<br>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:<br>ry d, yqx dvqfg. qrodxn inkkvyhmrihf.keanj uvdlpff nesjscuqec.v.wfprlqkkunhxkbes<br>anrbtwywjtlunshu yospeapibdm .,lkfvtuuljwfju.cjzifzbui.pgnjyfehu.fd.gzdkzrpqplv.<br>dnblmomeqswtvyfxgdkjpbdbhotnybwvv,w agpe.kscienkmiramwaoekbj souofqcckuim,rdcitc
But there are also sensible things there:<br>good sense is, of all...