The heart of the dice: what cross-entropy per token measures, and where the idea really comes from

I have been asked to explain cross-entropy per token, because the author is going to build a machine and score it on one number, and he would like you to know what the number is before he asks you to care. I agreed on one condition, which is that I get to tell you where the idea actually comes from, because it is not from where the textbooks say. The textbooks say it comes from a telephone engineer in New Jersey in 1948. It comes from a king in a forest in the Mahabharata, about two and a half thousand years earlier, and the telephone engineer, who was a very clever man, would have been the first to say so if anyone had read it to him.

Here is the formula first, so it is out of the way. This is it:

L = −(1/T) Σ log p(x_t | x_<t)

A Greek letter, a minus sign, a logarithm and a subscript, which is what happens when engineers are asked to write down surprise. I have sold things uglier than that to people who deserved better, and I will not pretend it is beautiful. It is not. It is a receipt. It is correct the way a receipt is correct, and about as moving. Everything the rest of this piece says is inside it, and nothing the rest of this piece says needs it, so if the letters make your eyes slide off, let them. The king did not have the formula either.

The king in the forest

The king is Rituparna of Ayodhya, and the story is in the third book of the Mahabharata, the Book of the Forest, in the tale of Nala. Nala was a king who lost his kingdom at dice, as kings in that poem tend to, and in his exile and disguise he became a charioteer, and the charioteer's skill was horses, which he knew better than any man alive. Rituparna hires him for a journey of a hundred leagues that has to be made in a day. On the road they pass a vibhitaka tree, the kind whose nuts were the dice, and the king says, idly, as a man says a thing he is proud of: that tree has so many leaves and so many fruits, five crore of leaves and two thousand and ninety-five fruits, and he gives the number to the one. Nala stops the chariot. He does not believe it. He is a man who has lost everything to dice and he is not in a believing mood. So he counts. He cuts a branch and counts the leaves and the fruits, which takes him most of the night, and the king's number is right.

Nala asks him how. And the king says: I know the heart of the dice. In the Sanskrit it is akṣa-hṛdaya, the heart of the dice, and it is the science of counting without counting, of looking at a part and knowing the whole, of standing in front of an unknown thing and saying how it will fall and being right more often than a man who does not know the heart of it. The king trades it to Nala for the secret of horses, and Nala goes back and wins his kingdom at the same dice he lost it at, and that is the end of the tale, and it is the whole of what this piece is about.

What the number measures

Because that is what the number measures. Not whether the machine knows the next word. Nobody knows the next word; the king did not know how many leaves there were, he knew how many there would be. The number measures how well the machine knows the heart of the dice. You play it the king's game. You show it the start of a sentence, "the capital of France is," and it does not say a word, it says how it would bet: Paris at sixty in a hundred, "not" at ten, "a" at eight, and so on down the sixteen thousand words it knows, until the hundred is spent. Then the real word arrives, and you charge it for its surprise. If it had Paris at sixty and Paris came, the charge is small. If it had Paris at one in a hundred, the charge is large. If it had Paris at nothing at all and Paris came, the charge is infinite and the machine is out of the game forever, which is why no machine that has ever been built puts nothing on anything; even the ones that are certain keep a coin on the table for the fool's card. You do this for every word in a book, which is a hundred thousand turns, you add up the charges, you divide by the turns. That is the number. The average cost of being surprised, per word, by a book you were not shown. Lower is better. The formula above is that sentence with the words taken out.

What the formula does not tell you, and the poem does, is where the floor is. There is a cost the machine can never get under, however large it grows and however much it reads, and that cost belongs to the book and not to the machine. A tree with five crore leaves has a certain irreducible wildness in how they fall; a page of Dickinson has more of it than a page of a railway timetable; and the best possible knower of the heart of the dice, Rituparna himself, still pays something per leaf. That floor is the only thing in this whole enterprise that a small company can move and the laboratories with the chips cannot, because the floor is set by what the machine read, and they read the internet, and you cannot choose the internet. We can choose two thousand books. Every machine of every size that ever reads the better shelf gets the lower floor for nothing. That is the bet. It is Nala's bet, placed from the far side of ruin, with somebody else's knowledge of the heart of the dice.

Three things people do to it

Three things people do to the number so you recognise them when you meet them. They raise e to it and call it perplexity, which turns a cost of one into about 2.7 and reads as "the machine was choosing among this many equally likely words," which is wrong in detail and useful anyway. They convert it to bits and divide by the bytes of the book and call it bits per byte, which is the figure the book reports, because it lets you compare two machines that chop words differently, and because a machine that gets 1.2 bits per byte on a book can, with a little arithmetic, squeeze that book to a sixth of its size, and there has been a prize for exactly that since 2006. And the telephone engineer, Claude Shannon, in 1951, sat his wife down with a page of prose and had her guess it letter by letter and counted, and got about one bit a letter for English, which is to say that the first measurement of this number was taken on a human being with a pencil, three years after he had proved on paper that it was the only sensible measure of information there is and a thousand years after a king in a forest had used it to count leaves.

What it does not measure

And here is what the number does not measure, because a man who sells you a thing without telling you what it will not do is a man you should not buy from. It does not measure whether the machine understood a word. It measures how it would bet, and a very good parrot bets well. A machine that has memorised the book pays nothing and knows nothing, which is why the twenty books the kernel is scored on are never shown to it: the score is the heart of the dice only if the tree is one it has not counted. And an average is an average: a machine can have a lovely number on the whole book and be ruinously wrong on the one sentence that mattered, which is why the score is reported book by book, with a second measure beside it that asks the machine to say, in its own words, what each book was about. Rituparna could count the leaves. The poem does not say he could tell you what the tree was for.

So why score on it, if it is only a bet? Because it is the only honest number in the field. Every other score anyone uses, the benchmarks with the capital letters and the percentages, was written by a person who decided what the questions were, and the people who build the machines read the questions, and after a while the machines are very good at the questions and nobody knows what that means. Nobody wrote this one. The book sets the questions, every word is a question, and a book has a hundred thousand of them, and the only way to get better at it is to know the heart of the dice better, which happens to be the thing we wanted. It is not a beautiful formula. It is a beautiful idea with an ugly receipt stapled to it, and I would rather you remembered the king.

Ja, no. That is cross-entropy per token. Count the leaves if you don't believe me. Nala didn't either.

Quentin Luck is a character from Nothing Up My Sleeve, the book about Thorp, the small open kernel Demiton is building from the world's books to 1930. The book, its plan and its decisions are written in the open; the first experiments, two thousand books and a Mac mini, are the subject of his next piece.