A walk through of the DeltaNet family of linear attention variants

Machine learning could need, and probably has needed, some unified math notation for the past 15 years IMO. With that said, it was worse back in the day - when ML papers were the products of researchers from all over, you'd see some wild notation.

Many will likely disagree with me, but inconsistent notation (across papers!) is to me friction. At least in this article the author explicitly explains the notation at the very start...that is not always the case. Rarely, even.

EDIT: Didn't even notice the notation switch, much appreciated.

You know its a doozy when the author writes a disclaimer at the top saying that bra-ket notation was chosen in order to make the algorithm and data structures clearer.

The bra-ket notation makes this all very simple/intuitive for me. With "vectors" I always get confused which is horizontal/vertical, and then I just follow blobs, and get distracted, and leave. With bra-kets the whole thing was very intuitive! I'm now going to covert other articles to the notation as I must have missed a lot of good stuff!

(Side notes: I have physics PhD and mild dyslexia)

> You Could Have Come Up with ...

Creating or combining to have something new, that does not already exist is actually freaking hard!

The moment its presented and people go "o, that is not that difficult", "i was able to also do that", or some nonsense like that. Everything looks simply the moment somebody did the hard work.

We have all been there was developers. Thinking we invented something new, and ... then you discover somebody already made it in the 70's and its everywhere. But because it never cross your path, you never realized it existed.

LLM written for sure:

> The identity [...] is the whole trick. The outer product is a matrix; the inner product is a number. We no longer store every past key and value. We store their summed outer products in the fixed-size state S_t.

When I see these types of articles and headlines, it just makes me supremely grateful for all the many people far smarter[1] than me. And humbles me, too, since I actually passed for a "very smart person" in places like high school and undergrad. In fact, I'm 'smart' for an average person, but there are definitely millions of people who make me look like a rube in comparison.

[1] I specifically mean those who are able to hold very big complex ideas and systems in their head, and reason about them, which seems to be an important talent for mathematicians.

A visualized tutorial: https://snowchord.com/blog/linear-attention-visualized/

I really liked the ket notation. I was aprehensive at first, but it makes operations much more clear.

I would have liked some refresher on some variables though (like d_k in quadratic attention).

Side note, before you ask: yes, bra-ket notation is called like that because of the brackets.

https://en.wikipedia.org/wiki/Bra-ket_notation

At first I felt bad about not having come up with this solution. But then I realized I have problems with writing binary search by myself in JS and immediately felt better.

Now way I could have come up with Kimi Delta Attention.

The toggle is really useful. Liked it!!

after a cursory read, I can confidently say I could not, in fact, have come up with Kimi Delta Attention.

No, you couldn't have. There are plenty of ML innovations that when push comes to shove only depend on having access to more compute, but this is one of the worst examples I've ever seen.

I always thought that the jump from LSTM/GRU -> Attention wasn't a particularly big one. Instead of partial unroll, do a full unroll. Why not (because it's too expensive, that's why not). Every component was known, and everybody anywhere near ML knew perfectly well why NOT to try that: because you just don't have the compute to fully unroll an LSTM. From that point attention is optimized (they key-query mechanic). The big innovation is not so much the mechanism itself but realizing the parallelize-ability of it.

It's sort of like if one would today make the "improvement" to attention to replace they key-query-value mechanic by just dropping it while making the entire context the latent space. That will outperform attention, nearly guaranteed. It'll also make even Google's cluster networks meltdown. Attention is one of those innovations that came mostly from realizing you had better hardware than everybody else and asking yourself how to use it. It's still quite the accomplishment, they had to get it working. But nobody else was really capable of making this leap.

I like the math vs physics toggle.

You could've also came up with Newton's laws. After all, they look trivial in retrospect. But, there's an important lesson in a story about balancing an egg here that can teach us something.

Filippo Brunelleschi said he could build the large dome for the church that had stood unfinished for a century. Skeptical, other's demanded he'd explain how. He refused. Instead he challenged everyone to balance an egg on its tip. Nobody could do it. He then demonstrated by lightly tapping the egg on the table, flattening the tip, making it stand. "Anyone could've done that! You never said we could break the egg!". And that's the point. Anyone could've done it. But nobody did. Nobody thought 'outside the box'. And likewise, his solution to building the dome is as simple, and as ingenious.

It's called Egg of Columbus. (there's a similar story about Columbus that's more famous, but apparently fictitious). It teaches us that hindsight is 20/20.

Loved this incremental evolution, things gets way more understandable...usually xD

>You Could Have Come Up With Kimi Delta Attention

What? Little old me! Well, then, let's have a look...

> (First paragraph)

> A note on notation: this article defaults to bra-ket notation because (in my quantum-inspired opinion) it makes the shapes in this derivation very clear. The Math notation switch above rewrites every equation using conventional bold vectors and explicit transposes instead. In bra-ket mode, ∣ q ⟩ ∣q⟩ is a column vector, ⟨ k ∣ ⟨k∣ is a row vector, ⟨ k ∣ q ⟩ ⟨k∣q⟩ is a number, and ∣ v ⟩ ⟨ k ∣ ∣v⟩⟨k∣ is a matrix. Vectors face right by default, while keys face left when written into the linear-attention state. We work with one causal attention head and real-valued vectors, assume DeltaNet’s keys are normalized, and let the state map from key space to value space.

Hmm... Guess not!

Where do linear algebra folks go to get started with ML stuff? It seems pretty easy but the hardware is expensive.

Ohhhhh Diag(αt), right. I was almost there but had left the placeholder "Diag(foo)" and never noticed. I now see is why I didn't come up with it first. So close!

love the toggle between math notation and physics notation. two flavors of confusion, nicely packaged.

Overall, all the different linear attentions out there are approximations the original (quadratic) attention and this is important for the whole "AI" enterprise[2].

Original attention involves (very crudely) an approach of scanning how every token (roughly a word) relates every other token and training a classic neural network on related tokens - to get either language translation or next word prediction (and next word prediction is what "seems intelligent" in LLMs). [1]

The problem is that since original attention is "everything to everything else" it scales quadratically (O(n^2)) with the size of the train set (or train set window) and so basically even the largest data center can use that once a truly vast training set is accumulated. Which is to say that "dirty little secret" of LLMs following the "Attention Is All You Need" paper don't actually scale. That model (in my crude, amateur understanding) is elegant for allowing every word's connection to every other word to be weighed and still brute-force for not starting with or achieving "understanding" of the words [3 give only some background but also why "full" attention is powerful].

Linear attention is a way around the quadratic quality of original attention so everyone is naturally using clever approaches to make it work. Simplifying terribly - you're trying to determine the value of word before you see in context. But my intuition is that since (Everything X Everything) is inherently a quadratic relationship, none of these can capture their expanded data set in the way original LLMs did - not they are worse but all the models seem likely to hit diminishing returns in terms of blindly capturing meaning from all-the-world's text (and data).

Background and notes: [1] https://en.wikipedia.org/wiki/Transformer_(deep_learning_arc... [2] Linear Transformers Are Secretly Fast Weight Programmers: https://proceedings.mlr.press/v139/schlag21a/schlag21a.pdf [3] Transformers are Deep Infinite-Dimensional Non-Mercer Binary Kernel Machines: https://arxiv.org/pdf/2106.01506

why are you using braket notation?

I could never get this about modern machine/deep learning or even the Transformers. Yes, it's not exactly rocket science, but when I see the data flow diagrams, it's not clear what is calculated in real time or multiple steps.

Is it really one big computation f(g(h(x)))?

It is heartwarming to see how sarcasm turns into a celebration of mediocrity.

Its greek to me.

If I could, I'd be working for one of the labs and commanding a seven-figure salary. :)

Relevant XKCD

https://xkcd.com/2501/

Hmm. Hmmm. Hmm. HMMM. Hmm.

Yep! I know some of these words.

[flagged]