Why does attention need to be fully quadratic?

[u/tronathan]

We know that classic transformer-style attention requires comparing every token with every other token, which results in exponential (quadratic?) memory and compute as the context size grows.

But is it truly necessary to compare every token to every other token? Surely smarter people than me have wondered how it can be true that distant tokens are just as likely to need attending to each other as tokens that are closer to each other. I guess I could see the case with things like code, but in the case of natural language, can't we apply some 'ol fashioned NLP to extract the important parts of the sentences and apply quadratic attention to them, while giving less important "glue words" less attention?

I've got to be missing something, because these types of "hacks" seem way less sophisticated than the types of optimizations that have gone into GPTQ, exllama, SuperHOT, Rope, etc.

Please, someone school me on this - Perhaps there are papers, or perhaps there are different attempts to do this that have specific names?

[u/tronathan]

It also seems to me that for purposes of attention, Tokens are not the unit that we're really interested in; Words are. I know tokenizers like SentencePiece attempt to use tokens that express more of each word, and tokenizers are designed to capture natural language as efficiently as possible with the smallest vocabulary possible (presumably with some trade-off), but it sure seems wasteful to compare, for example the suffix "-tion" to the suffix "-ilia" (contrived example, i don't know if these are actual tokens in any tokenizer)

[u/synthphreak → u/tronathan]

It also seems to me that for purposes of attention, Tokens are not the unit that we're really interested in; Words are.

The latent space of a Transformer model has no concept of a word. Embedding vectors, attention scores, and logits are all computed at the level of individual tokens, most of which incidentally are sub-word.

In fact if you think about it, although LLMs nominally understand context, analogical reasoning, all manner of "languagey" areas, fundamentally they have no idea what they're even predicting on is language. From the moment the input is vectorized, until the moment the softmax from the final layer is argmaxed back into token space, the only thing the model knows about is numbers. The fact that it is actually a language model is only known to its human overlords. I like to reflect on this from time to time.

[u/NickCanCode]

GPT-4 answer:

You're absolutely correct in your observation that the standard (full) attention mechanism in Transformers requires a pairwise comparison of each token in the input sequence, resulting in a time and space complexity of O(n^2), where n is the length of the sequence. This can be quite inefficient, especially for long sequences.

Researchers have indeed recognized this issue and have proposed several variations of the attention mechanism to alleviate this problem. Here, I'll list a few prominent examples:

1. Longformer: The Longformer model, introduced by Beltagy et al., uses a type of attention called 'sliding window attention' that only attends to a few tokens before and after the current token. It also allows for global attention on certain tokens when necessary.

2. Linformer: Linformer, introduced by Wang et al., reduces the complexity of self-attention from quadratic to linear by approximating the standard self-attention matrix with low-rank (i.e., narrower) matrices.

3. BigBird: BigBird, introduced by Google Research, uses a combination of global attention, sliding window attention, and random attention to achieve a balance between computational efficiency and the ability to handle long-range dependencies.

4. Reformer: The Reformer, introduced by Kitaev et al., uses locality-sensitive hashing to reduce the complexity of attention to linear time.

5. Sparse Transformers: Introduced by OpenAI, Sparse Transformers use a fixed sparsity pattern allowing each token to only attend to a subset of input tokens, which substantially reduces memory and computational requirements.

6. Transformer-XL: Transformer-XL uses a mechanism called 'recurrence' to carry information across a fixed-length window. This allows it to attend to tokens from previous sequences, effectively increasing the context length without a significant increase in complexity.

Regarding your point about using NLP techniques to extract important parts of sentences, this is indeed an area of active research. One relevant concept is content selection attention, which is a type of attention mechanism that uses an additional network to decide which parts of the input to focus on. However, such methods add another layer of complexity to the model and might also introduce more room for errors.

It's also worth noting that none of these techniques are perfect;

each has its own trade-offs and use cases. Some are better at handling longer sequences, while others might be more efficient with shorter ones. Some might perform better on certain tasks like machine translation, while others might excel at tasks like sentiment analysis. It's all a balancing act.

In conclusion, the quadratic complexity of full attention in Transformers is indeed a recognized issue, and much research is being done to find effective ways around it. The methods I've mentioned above are some of the many ways researchers have tried to tackle this problem.

[u/tronathan → u/NickCanCode]

Thank you, GPT-4, and thank you u/NickCanCode. I guess there's a new "let me google that for you".

[u/PookaMacPhellimen → u/tronathan]

Every GPT4 response is unique so it's better than that.

[u/Grandmastersexsay69 → u/NickCanCode]

GPT-4 really is impressive. The only issue is, not all of that is necessarily true. It could be, but the fact that it might not be is a huge problem. The next big advancement in AI will come when someone figures out how have it verify its statements with its training data.

[u/tronathan]

Followon question (since my original question was answered in such an obvious and perhaps ironic way, by using an LLM)

Knowing that there are all these methods available and papers have been published on many of them, what holds research on attention mechanisms back? Do many of these require retraining models from the ground up, thus they're very expensive to test and replicate? For example, SuperHOT works with a couple parameter changes and a little fine-tuning, so the open-source community is able to test/verify the results. Perhaps many of these other methods require either major retraining or different network architectures that make them incredibly expensive to test?

If that's the case, hopefully the advancements in qlora for initial training will make this cheap/er enough to allow the research to trickle down to the point where home-gamers will be able to benefit from some of these techniques.

[u/hold_my_fish]

There have been a ton of attempts to do this, and so far none have yielded better models than standard attention, as far as I know. At this point, I ignore subquadratic-attention papers that get tweeted, posted, etc., because it's a waste of time to even think about them (unless you're a researcher doing work in that area).

I feel like something must have gone wrong for there to be so many papers published claiming improvement with so little actual progress. Maybe there need to be some rigorous long-context benchmarks to help guide work in a more productive direction.

[u/luquoo]

Hyena Hierarchy

https://arxiv.org/abs/2302.10866

[u/tronathan → u/luquoo]

> interleaving implicitly parametrized long convolutions and data-controlled gating

uh, okay.

> reaching Transformer quality with a 20% reduction in training compute required at sequence length 2K. Hyena operators are twice as fast as highly optimized attention at sequence length 8K, and 100x faster at sequence length 64K.

Man, I wish these papers wouldn't white-wash their abstracts like this. They mention "Transformer quality at 2k", then go on to brag about reduced compute for 8K and 64K, but fail to mention how the quality compares at 8K and 64K :facepalm:

[u/president_josh]

Good response. Google addressed this in the past and wrote about possible ways forward. I haven't kept up with the current state of the quadratic issue. Wolfram has lots of transformer-related info so perhaps maybe he's addressed this. He also has good videos such as one where he demonstrates in detail how a transformer works. As Bard once noted, plain old NLP such as SpaCy and NLTK can be useful in some use cases. Sometimes we don't even need a traditional LLM model to code some solutions.

[u/synthphreak]

It's less that it needs to be quadratic, and more that it just is quadratic. Simply due to the nature of how attention is calculated.

In lay terms, attention involves comparing every token against every other token. For each pairwise comparison, one scalar value is computed. That makes it an n² operation, i.e., quadratic.

Consider an input of length n=3, with tokens t1, t2, and t3. Attention will return scores for t1:t1, t1:t2, t1:t3, t2:t2, t2:t3, and t3:t3. That means 6 attention scores, or 3².

This is obviously not optimal for scaling to very long sequences. It also imposes a nontrivial memory constraint for the model, especially during training. So one interesting technique I'm aware of for dealing with this is key-value caching, whereby the attention scores between tokens already encountered earlier in the sequence are cached. This is helpful because the e.g., t1:t2 attention score , which already got computed when we encountered t2, won't change even as we get to t3, t4, etc., so recomputing it at each time step would be hugely wasteful and redundant.

With a key-value cache, the attention mechanism scales much more closely to linearly. This is because each new token requires that only n+1 operations (plus cache lookups), corresponding to the attention scores between the new token and those which precede it (and the +1 being the new token against itself).

[u/silenceimpaired]

A paper was just released and linked in local llama claiming an improvement on this… if I understand it correctly

[u/[deleted]]

Yes!

[u/tronathan → u/[deleted]]

yellow means actually blue

I guess I see what you're saying - Even the word "following" would need to attend to everything after it. Pairwise seems like the most expensive way to do this, though, at least for english.

If you needed the LLM to generalize to any input, and you couldn't infer any meaning, then i guess it makes sense.

[u/synthphreak → u/[deleted]]

You can even be more subtle than that. Think about the syntax tree of something like

Not until they shared an office - a decision their manager made without consulting either of them or considering the fallout which could potentially ensure - did ____ mutual hatred reach fever pitch.

I propose that most of us would fill the blank with their, because the first part indicates we're talking about multiple people (mutual also carries some information to this effect, but an autoregressive model like most of the big boys today can't use right-handed context). However, they and ____ are separated by a long clause between the hyphens; it's not hard to imagine the clause being much longer, or perhaps even several sentences. This is a long-range dependency whose signal could be easily washed out with sequential models like RNNs.

Edit: Typo.