Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The FFT Strikes Back: An Efficient Alternative to Self-Attention

arxiv.org

Post reply on HN
Print view View original

171–175 of 175 posts

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#171

Post by touisteur »

xphos wrote: post #144
SJC_Hacker wrote: post #114

Earlier quoted context omitted.

FFT is only O(N log N) for a vector of length N WRT to matrices for an N by N matrix it would be like O(N^2 log N) you would perform FFT for each row or column

Thank you for that catch. I still think we are comparing ASIC matmul hardware to non ASIC FFT hardware. The given TPU hardware is doing 256x256 matrix multiplication in linear time by using 256x256 multiplier grids. FFT ASIC could like do the same thing but be able to handle a much higher N size before memory becomes the bottleneck.

Part of the FFT can be accelerated on GPU hardware, which is full of butterfly-like instructions within warps. Using overlap-and-add/overlap-and-save and cuFFTDx can also make use of heavy parrallelism within shared memory. I had a hard time reproducing the tcFFT paper (for lack of time and tensor core skills I guess) but you can also keep your data in Tensor Core registers too, apparently.

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#172

Post by topwalktown »

markisus wrote: post #169
3vidence wrote: post #142

Earlier quoted context omitted.

Not an expert in this space. Aren't tokens transformed with position dependent information in most models? I believe llama applies a rotation to the vector based on the position in the input.

That's true in the realm of LLMs. But even in this case, the position information is added only into the first layer. Tokens in later layers can choose to "forget" this information. In addition there are applications of transformers in other domains. See https://github.com/cvg/LightGlue or https://facebookresearch.github.io/3detr/

Transformers like Llama use rotary embeddings which are applied in every single attention layer

https://github.com/huggingface/transformers/blob/222505c7e4d...

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#173

Post by hinkley »

mtrovo wrote: post #170
hinkley wrote: post #128

I think in the age of telemetry we are also missing a substantial trick by not applying FFTs to cloud telemetry to smoke out epicycles and metastable systems before rather than after they trigger drama. This is unfortunately within my level of notice but not within my level of skill, and my dance card is already full. "SLA's are most likely to be violated 23-25 minutes after a service deployment. Hmm, I wonder why th…

"I'm afraid I cannot deploy your application, Dave" Jokes aside one area this could be really worth money is predicting cycles of traffic and saving with ramp up and ramp down of server instances. It's the kind of work that if you're doing it out of your time the company would never give you greenlight it but if you pack it as a shelf product they would totally buy it.

Yep. I worked on a SaaS for one particular retail industry, and I would bet you anything they see more traffic when biweekly paydays and the calendar line up in certain ways. Either a couple days before (window shopping) or a few days after, once other bills are paid.

That extra half paycheck when a month has 5 Mondays or Fridays in it...

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#174

Post by markisus »

topwalktown wrote: post #172
markisus wrote: post #169

Earlier quoted context omitted.

That's true in the realm of LLMs. But even in this case, the position information is added only into the first layer. Tokens in later layers can choose to "forget" this information. In addition there are applications of transformers in other domains. See https://github.com/cvg/LightGlue or https://facebookresearch.github.io/3detr/

Transformers like Llama use rotary embeddings which are applied in every single attention layer https://github.com/huggingface/transformers/blob/222505c7e4d...

Very interesting! Do you know if there were any studies about whether this improves performance?
Post reply on HN