"Attention" and "Transformers" in Large Language Models

Everyone is talking about OpenAI's ChatGPT these days. Here's a very quick attempt to summarize the core idea behind large language models (LLMs) like GPT.

"Attention is all you need" (aka the transformer paper) published in 2017 by Vaswani et al from Google is still the mother of current LLMs, including GPT.  "Effective Approaches to Attention-based Neural Machine Translation", an earlier paper by Luong et al from Stanford, was also quite important.

These are sequence-to-sequence models, i.e. their job is mapping an input sequence of text into an output sequence of text. Applications include translation from one language to another, answering questions,  having a conversation, etc.

They use language embeddings (made famous by Word2vec in 2013 and later by BERT, both also from Google) as the basic encoding/decoding building blocks, i.e. mapping text to vectors of real numbers in an "embedding space".

The main new idea is in the architecture of the neural network between the input encoding and output decoding stages. The model uses the preceding terms in the current output sequence to decide which parts of the input sequence to pay more "attention" to for the next output term. A bit more precisely: the previous output is a "query" which gets used to generate a linear combination of "keys" from the input which maps to a linear combination of "values" also from the input. That in turn gets transformed into the next output term with a few more layers in a plain feed forward network (i.e. a bunch of layers of neurons, where each neuron is putting a linear combination of inputs into non-linear activation function). Each step has trainable weights.

There are also clever tricks besides "attention". One is positional encoding to represent the order so the same input term in a different position has different effects even though, unlike in recurrent neural networks,  in transformers the network just sees them as bag of words that could be in any order. Another is layer normalization to sort of keep the nonlinear outputs within a reasonable area in the embedding vector space.

This architecture, as far as I know, was not derived explicitly from the way human brains work. The "attention" analogy is really useful, but there are no principles saying this architecture is more fundamental to intelligence, or more natural, than many others. It just happens to produce remarkably good results when the weights are trained properly.

So that's the basic idea of contemporary LLMs. Of course in some sense, all computer neural networks are  just a bunch of matrix multiplications and ad-hoc activation functions. But you can't just connect a large number of mathematical "neurons" randomly in a network and hope it learns something.  The choice of architecture, i.e. how the "neurons" are connected, is key. On top of that, there is still an enormous amount of innovation/engineering to make the real world language models, not to mention turn them into a product like ChatGPT or Google Bard.

Doomsday argument

And now for something completely different: a fun little probability puzzle. 

What's the probability that the human race will end some time in the next 100 years? Surprisingly this question has a logical answer. And not because we have some magic crystal ball.  In fact, our puzzle  specifically assumes we have no information at all about the future.  

Here's how it goes.  Let's step out of time for a second, and consider the total number of humans who will ever exist. Let's say that number is N.  If you are of the Abrahamic faiths, you can call the first one Adam. But we're just having fun so we'll just number them from first to last: 1,2,3, ..., N.  Now let n be your number. So 1 <  n < N, you are somewhere between the first  and the last person ever.  Since we  have no information about the future, we have no clue if you are near the end or near the beginning or somewhere in the middle.  You just happened to land at some random position in the long line of  humans. So we have to assume that any position is equally likely, or technically that n is uniformly distributed between 1 and N. The chance that you are in a particular interval is equal to how big that interval is relative to the whole sequence. There's a 50% chance that you are in the first half and 50% chance that you are in the second half,  there's a 95% chance that you are in the first 95% and a 5% chance that you are in the last 5% of people, etc.  So P(n < f*N) = f and P(n>f*N)  = 1-f, for any fraction f between 0 and 1.  

We don't know N, but we can estimate n, because we can approximately calculate the cumulative population to date. This is more accurate  than you might think because the parts really long time ago where we have poor estimates are also the times where there were very few people.  The left tail is long but thin. Estimates now are around  n = 117 billion.

From the above, the distribution of N is P(N<n/f) = 1-f. That means there's a 5% chance that N < 123B i.e. that there are only 6 billion babies to go before the last one. If we translate that into time, using the current rate of 140M births per year,  it means there's a 5% chance that we have less than 43 years left! And a 50-50 chance that we'll be around for another 800 years. At the other end, a 5% chance that we have more than 16,000 years left, and so on.

I heard about this puzzle known as the "doomsday argument" about a year ago. Of course you can debate about whether this is a realistic model, but it's a cute way to provoke thought about all the minor risks we collectively worry about and the big ones we don't consider rationally. 

Reminds me of a few scenarios discussed in this blog a long time ago:  ineffective posturing on climate change, the asteroid lottery , political pandering in a pandemic... Ouch ouch ouch! Sadly humanity doesn't seem to have gotten wiser in the decade (!) since those posts... 43 years seems like an awfully short time. At least math is eternal!

Proof of royal blood

I have royal blood. I'm a direct descendant of one of the great kings in the history of the world. I am sure of it. Pretty cool eh? 

Which one, you ask? Well, ahem, I just mean I'm mathematically almost sure I am a descendant of a great king. And so are you.  

Here's the proof. First, like everyone, (except clones if there are any)  I have 2 biological parents, 4 grandparents, ...,  2^n direct ancestors n generations back. This is not an estimate, it is a precise fact. Second, I am not a descendent of extra-terrestrials, so I must have human ancestors on earth who were around at all points in human history. Now  let's take say n=30. That would be about 1000 years ago.  That means I have 2^30 that is about 1 billion ancestors that existed then. Woah. But the world population was only a few hundred million. So how is that possible? How can you fill a billion positions on my family tree, which, remember *must* exist, when there are only a few hundred million humans in existence. Obviously it's because the same person must fill multiple slots. If there was 100M people  let's say, then each one on average must appear 10 times. Of course, some get more than average and some get less. It's like a lottery. And the odds of each person on earth getting many slots in my tree are directly related to how many children, grandchildren etc they had. Obviously most kings have more descendants than the average person by far. Not only do they have more kids, their kids are more likely to survive and so on. Therefore in that lottery if the average human appears ten times then the average king who existed 1000 years ago must appear way more than 10 times. Therefore I have lots of kings at n=30.  Now if we keep going, as n gets larger, each king gets exponentially growing number of lottery tickets to win places in the tree. If you add it all up, the probability that I have at least one great king approaches 100%. QED.

P.S. I first read a version of this argument in a magazine article years ago, I think it was Harper's or something, will try to find it and give credit.

P.P.S. The picture is of King David (I love how it looks like "Dawit" but I think it actually says "Davidus"), from the Nine Worthies in the Palazzo Trinci, Italy, circa 1410.

Random matrix and phase shifts

I just stumbled across this great article on Tracy-Widom distribution. It talks about random matrices and phase shifts.  This reminded me of some work I did on resource allocation in network interconnection. We derived routing matrix conditions for "peering" and "dis-peering" (the latter a new term) to be equilibria in the decentralized resource allocation game. I wonder what a probablisitic approach with the routing matrix randomized would add to the game theoretic results. Large scale self organizing interconnections (or failure thereof).

Don't buy the second item on the menu

Yesterday a door to door salesman from Time Warner Cable came to our door. He was a nice guy so I listened to him even though I've been avoiding cable for a long time. Anyway here are the current options for Internet access from Time Warner Cable:

"If Internet is all you need, however, TWC offers its “Everyday Low Price” plan for just $15 per month. This includes 2 Mbps download speeds, 5 emails accounts and 100 MB of email storage. Need to go faster? Try Basic (3 Mbps and $30 per month) or Standard ($35 per month with 15 Mbps). If you’re an online gamer or download large files on a regular basis, the 20Mpbs of TWC’s Turbo plan ($45 per month) may be the best option, while home business users may want to try out the Extreme plan, which offers 30 Mbps download speeds at $55 per month. Finally, if you have a large family or Internet users or connect multiple devices on a daily basis, you may need the Ultimate plan, which provides download speeds of 50 Mbps, 30 email accounts and 10 gigabytes (GB) of email storage for $65 each month."

OK now consider the slope or marginal prices:

• The first 2 Mbps costs $7.50 per. Fair enough. 
• But then the next 1Mbps costs $15!
• The next 12Mbps cost  just $0.42 per!!!
• Then the next 5Mbps cost $2, 
• And the following 10Mpbs are $1,
• And then 20Mbps more at $0.50 each.

The first and the last three are totally reasonable. But notice the second item on the list is a horrifically bad deal.  Why does it exist, who in their right mind would pick that? It's like  a trap. Maybe some people will just ignore the Mbps amidst all the verbiage about storage and email etc (extras which really are insignificant in terms of cost) and think to themselves: "Hey, I'm not poor and "Everyday Low Price" that sounds like the plan for poor people.  And I don't understand the high end stuff, so let me get Basic, that sounds reasonable." And boom, they are paying an astronomical price. Even if not many people fall for it, it's very profitable.  It's also kind of unethical in my opinion. (This is not the first time I'm finding fault with Time Warner in these pages, and I don't even use them. )

A more innocent version of the same thing is wine lists at restaurants. Never order the second item! It's for suckers. To see why, imagine a naive and status-conscious customer who doesn't know much about wine: he will skip the first one to avoid looking cheap, but will hesitate to go to far down the list because they can't justify buying the expensive ones. So he will settle for the second one. The restaurateur willing to exploit this can profit by putting the cheapest wine at the second cheapest price.  Thus gouging the suckers without affecting others. The moral of the story is, even if you don't know about wine, you can still have a wine list strategy.

Rent splitting mechanism

I just came across this blog post on "How to split the rent?". Most people split the rent equally between apartment mates. The problem is that not all rooms are equal. How do you value their differences in size, light, accessibility. How do you value the shared areas? Further, different people have different preferences. So it's an interesting problem... so how do you find a fair price and allocation of rooms?

It reminded me of a solution my roommates and I came up with many years ago. It's basically an auction. Say there are 4 apartment mates, 4 bedrooms, and the total rent is $1000. Each roommate writes a bid with prices for each room, with the condition that the total has to be $1000. So the bids might look like
- person 1: ($200, $250, $250, $300)
- person 2: ($100, $250, $300, $350)
- person 3: ($250, $250, $250, $250)
- person 4: ($150, $200, $250, $400)

Then you gather all the bids and you assign each room to the person who has the highest value for it and they pay the average price of that room in all bids. You start with the highest priced room and go down (so that if a person wins two rooms you give them the one with the higher price). If you have a tie for first place on two different rooms with the same two people, you flip a coin. In the above case, no coin flip needed, the solution is:
- room 1 goes to person 3, for a rent of (200+100+250+150)/4 = $175
- room 2 goes to person 1 for $237.50
- room 3 goes to person 2 for a price of $262.50
- room 4 goes to person 4 for a price of $325

The beauty is that the solution guarantees that each room goes to the person who values it the most, and the room prices add up to the correct total rent.

We did it for one year with a 4 bedroom apartment with 4 co-tenants. The biggest room went for about 31% of the total rent, and two rooms of smaller size but with the most light went for 25%, 24% and the dining room converted into a bedroom went for 20%. The second year we were down to three tenants and for a variety of reasons, we did a direct adjustment rather than rerun the auction...

But the moral of the story is that mechanism design works in every day life! Surprisingly not many people do this.