FFT'nin Karşı Hamlesi: Self-Attention'a Verimli Bir Alternatif

 (arxiv.org)
3 puan yazan GN⁺ 2025-02-27 | 1 yorum | WhatsApp'ta paylaş
  • Uzun bağlamlı Transformer'larda self-attention maliyetinin darboğaz olduğu durumda, SPECTRE FFT tabanlı bir token karıştırıcıyla katman başına karmaşıklığı O(L²)'den O(L log L) düzeyine indiriyor
  • Her attention head, hızlı real FFT, içeriğe uyarlanan spectral gate ve inverse FFT birleşimiyle değiştiriliyor; mevcut Transformer yapısı korunuyor
  • Otoregresif üretimde Prefix-FFT cache, her adımda FFT'yi yeniden hesaplama yükünü azaltıyor; isteğe bağlı wavelet modülü de yerel özellik kaybını telafi edebiliyor
  • Llama-3.2-1B omurgasında SDPA, FlashAttention-2 ve SPECTRE karşılaştırıldı; NVIDIA A100-80GB üzerinde 512~128k token için throughput ve gecikme ölçüldü
  • SPECTRE, PG-19 ve ImageNet-1k'de temel performansla aynı ya da daha iyi sonuç verdi ve %6'dan az ek parametreyle standart GPU'larda uzun bağlam işlemeyi hedefliyor

Self-attention'ın karesel maliyetini FFT ile azaltma yöntemi

  • Uzun bağlamlı Transformer'lar, çok turlu diyalog, kitap uzunluğunda özetleme ve yüksek çözünürlüklü görme gibi on binlerce token içeren görevler için gerekli
  • Mevcut self-attention, O(n²d) maliyeti nedeniyle bağlam uzadıkça çıkarım gecikmesini ve bellek kullanımını artırıyor
  • SPECTRE, self-attention katmanını frekans alanı token karıştırıcısı ile değiştiren, doğrudan takılabilir bir alternatif
    • Token'ları ortonormal Fourier tabanına yansıtıyor
    • İçeriğe uyarlanan diyagonal gate ve isteğe bağlı low-rank gate uyguluyor
    • inverse transform ile yeniden token uzayına döndürüyor
  • Temel fikir, çevredeki ağ mimarisini değiştirmeden katman başına karmaşıklığı O(n log n) düzeyine indirmek

Token karıştırıcı yapısı ve üretim desteği

  • SPECTRE'nin attention head yerine geçen yapısı, fast real FFT, spectral gate ve inverse FFT'den oluşuyor
  • spectral gating, n/2 + 1 frekans katsayısı üzerinde çalışarak hesaplama ve bellek kullanımını azaltırken ifade gücünü koruyacak şekilde tasarlanmış
  • Prefix-FFT cache, standart KV-cache'e benzer bir rolle akış halinde decoding'i destekliyor
    • Otoregresif üretimde her time step'te FFT'yi yeniden hesaplama gerektiren mevcut spectral mixer zayıflığını azaltıyor
    • Sabit bellek bütçesi içinde verimli üretimi mümkün kılan bir yapı sunuyor
  • İsteğe bağlı Wavelet Refinement Module, saf spectral yaklaşımda kaybolabilecek yerel ayrıntıları telafi ediyor ve hesaplama ek yükü düşük kalıyor

Mevcut Transformer'a uygulama yöntemi

  • SPECTRE, multi-head attention katmanını doğrudan değiştirebildiği için ayrı bir mimari yeniden tasarım gerektirmiyor
  • Mevcut önceden eğitilmiş modeller, SPECTRE katmanlarıyla fine-tuning yapılabilecek şekilde kullanılabiliyor
    • Güncellenen kısım, yeni eklenen parametreler
    • Ek parametreler, toplam ağırlıkların %6'sından azını oluşturuyor
  • Specialized optimization veya standart dışı mimari isteyen yaklaşımların aksine, çevredeki Transformer yapısını koruyor

Llama-3.2-1B tabanlı deneyler

  • Aynı Llama-3.2-1B omurgasında üç attention kernel uygulanarak karşılaştırma yapıldı
    • standard softmax-dot-product attention (SDPA)
    • FlashAttention-2
    • SPECTRE mixer
  • Ölçüm ortamı NVIDIA A100-80GB ve dizi uzunlukları L ∈ {512, 1k, 4k, 8k, 32k, 128k}
  • Ölçütler, tokens-per-second throughput ve single-batch latency
    • Throughput ne kadar yüksekse o kadar iyi
    • latency ne kadar düşükse o kadar iyi
  • SPECTRE, omurga doğruluğunu korurken neredeyse O(n log n)'e yakın çalışma süresi gösteriyor
    • 32k token'a kadar çalışma süresi neredeyse düz kalıyor
    • Özet kısmına göre, 128k token bağlamda FlashAttention-2'den en fazla 7× daha hızlı
    • Metindeki contribution listesine göre ise 32k token'da FlashAttention-2'den en fazla 7× daha hızlı çıkarım gösteriyor

Benchmark sonuçları ve pratik kullanım alanı

  • SPECTRE, PG-19 dil modelleme ve ImageNet-1k sınıflandırmada baseline performansla aynı ya da daha iyi sonuç veriyor
  • Uzun bağlam işlemede self-attention'ın karesel maliyetinden kaçınırken küresel bağlam karıştırmayı koruyor
  • Sparse pattern, kernel approximation ve low-rank structure tabanlı attention hızlandırma yöntemleri; kesinlikten ödün verme, standart dışı optimizasyon gereksinimi veya streaming generation desteği olmaması gibi sınırlara sahip olabiliyor
  • SPECTRE, FFT'nin circular convolution'ı köşegenleştirerek küresel karıştırmayı element-wise product'a dönüştürdüğü frekans alanı yaklaşımını kullanıyor
  • Ek parametreleri %6'nın altında tutarak, specialized hardware olmadan commodity GPU üzerinde yüz binlerce tokenlık bağlam işlemeyi hedefliyor

İlgili okumalar

1 yorum

 
GN⁺ 2025-02-27
Hacker News yorumları

  • Temelde evrişim teoremini kullanan bir yaklaşım: özgün uzayda pahalı olan evrişim, karşılıklı uzayda basit bir çarpmaya dönüşür; tersi de geçerlidir.
    Veride bir evrişim işlemi varsa, eşlenik alana dönüştürüp çarpmaya çevirmek yeterli.
    Başka bir deyişle, verinin doğal olduğu alanda çalışın demek.
    https://en.wikipedia.org/wiki/Convolution_theorem

    • Böyle ifade edilince çok iyi, ama LLM’lerde yapılandırılmış attention uzayının frekans alanı olduğu benim için hiç de apaçık değildi.
    • Temel bir matematiksel uzay dönüşümü sandviçi: 1) veriyi başka bir uzaya dönüştür, 2) o uzayda işlem yap, 3) özgün uzaya geri dön.
      Optimize etmek için her adımı optimize eder ve mümkün olduğunca en verimli uzayda daha fazla çalışırsınız.
    • “Verinin doğal olduğu alanda çalışın” sözünde, çarpmanın neden evrişimden daha doğal sayılması gerektiğini anlamıyorum.
      Bu, sadece hesaplamanın daha kolay olmasından farklı bir şey değil mi?
    • Karşılıklı uzay her zaman frekans = 1/zaman gibi, basitçe 1/uzay biçiminde midir?
    • Doğru, ama tasarruf büyük ölçüde teorik. O(n²) işlemleri O(nlog n)’e çevirmek kulağa iyi geliyor; ta ki ortalama n’nin 3 olduğunu fark edene kadar.
      Üstelik hesaplamada karmaşık sayılar kullanmanız gerekiyor ve sayısal olarak da daha az kararlı. Bildiğim kadarıyla FFT, genel evrişimde kazanç sağlamıyor.
      Self-attention’da ya da bu makaledeki kullanımda n çok daha büyük olabilir. Makaleyi okumadım. Yine de karmaşık sayı sorunu kalıyor.

  • Google bu fikri 2022’de FNet: Mixing Tokens with Fourier Transforms ile ortaya koymuştu.
    Sonrasında çoğu durumda TPU’nun matris çarpımı performansının FFT’den daha hızlı olduğunu gördüler.
    https://arxiv.org/abs/2105.03824

    • Bu makalede de alıntılanmış:
      “Genel olarak FNet, Performer ve sparse transformer gibi yaklaşımlar, sabit ya da yaklaşık token karıştırmayla hesaplama yükünün azaltılabileceğini gösterse de, bizim uyarlanabilir spektral filtreleme stratejimiz FFT’nin verimliliğini öğrenilebilir ve girdiye bağımlı spektral filtrelerle benzersiz biçimde birleştirir. Bu da karmaşık dizi modelleme görevleri için önemli olan güçlü bir ölçeklenebilirlik ve uyarlanabilirlik birleşimi sunar.”
      Ardından bir karşılaştırma bölümü de var.
    • Özel donanımın daha iyi olduğu karşılaştırması biraz tuhaf görünüyor.
      Peki DSP’lerde FFT’ye yardımcı olan özel donanım var mı? Gerçekten merak ettiğim için soruyorum. Hiç kullanmadım ama belli belirsiz işe yarayabileceğini düşünüyorum.
    • GPU, TPU’ya göre %10 iyileşme göstermişti.
      “TPU, Fourier dönüşümlerinde o kadar verimsiz ki araştırmacılar 4096’dan kısa dizilerde FFT algoritmasını kullanmadı; bunun yerine önceden hesaplanmış DFT matrisini kullanan, ikinci dereceden ölçeklenen bir Fourier dönüşümü uygulamasını seçti.”
      “Nvidia Quadro P6000 GPU’da, FNet mimarisinde Fourier dönüşümü çıkarım süresinin en fazla %30’unu oluşturdu.”
      Bu şirket 2021’de, Google TPU’larda kendi optik çiplerini kullanırsa çıkarım süresini %40 azaltabileceğini iddia etmişti. FFTNet daha fazla işi üstlenirse bu daha da azalabilir.
      https://scribe.rip/optalysys/attention-fourier-transforms-a-...
    • Bağlam penceresindeki token sayısı arttıkça FFT’nin ölçeklenmesinin daha iyi olacağını düşünüyorum. Google modellerinin bağlam boyutunda rakiplerinin önünde olması ilginç.
    • Sadece FFT’den hızlı olmakla kalmıyor; TPU’nun FFT desteği de her zaman “elinden gelenin en iyisi” düzeyindeydi. En son denediğimde ciddi hassasiyet sorunları vardı.

  • Fourier dönüşümü “token” boyutu boyunca uygulanıyor. Ancak birçok uygulamada bu boyutun bir anlamı yok. Bu yüzden transformer’lar permütasyon değişmez verileri işlemek için iyi bir seçenek oluyor.
    Daha az bilinen sonlu gruplar üzerinde Fourier dönüşümü ile ek deneyler görmek isterdim. Bu, permütasyon değişmez olmakla birlikte standart Fourier dönüşümüyle pek çok özelliği paylaşıyor.
    Ayrıca bu LLM’lerin bir sonraki büyük akımı olursa, vLLM veya llama.cpp gibi çıkarım motorlarının bunu ne kadar kolay entegre edebileceğini de merak ediyorum.
    https://en.wikipedia.org/wiki/Fourier_transform_on_finite_gr...

    • Bu alanın uzmanı değilim ama çoğu modelde token’lar konuma bağlı bilgiyle birlikte dönüştürülmüyor mu?
      Bildiğim kadarıyla llama, girdi içindeki konuma göre vektöre bir rotasyon uyguluyor.
    • Bu durumdaki sonlu grup nedir?

  • Matematik tamamen kafamın üzerinden geçiyor; formüllerin etrafındaki açıklamaları bile ancak zar zor anlayabiliyorum. Biri bunu basit sözlerle attention mekanizmasına nasıl eşdeğer olduğunu açıklayabilir mi?
    Burada bahsedilen frekans nedir ve token’lar arasındaki konumsal ilişki nasıl kodlanıyor?

    • Fourier dönüşümü tersinir bir operatördür. Yani fonksiyonlar üzerinde etki eder; matrisler söz konusu olduğunda hem fonksiyon hem de operatör matrislerle temsil edilebilir. Bunu frekans uzayı dediğimiz yere dönüştürür
      Sinyal analizi veya görüntülerde en sezgisel hâli budur: https://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm
      Frekans uzayı özünde karmaşık sayılarla temsil edilen “karmaşık” bir uzaydır. Frekansın avantajı, probleme küresel olarak bakmasıdır
      Bu mekanizma attention mekanizmasına eşdeğer değildir ve belirgin bir ödünleşim vardır. Ancak attention’ın yakaladığı önemli ilişkilerin çoğunu yakalama ihtimali vardır
      modReLU için şu an iyi bir sezgim yok, ama frekansları değiştirirken ters Fourier dönüşümünü koruduğu için önemli görünüyor
    • Asıl mekanizmanın kendisi oldukça basit. Girdi embedding’lerine FFT uygulanıyor, girdi embedding’lerinden MLP ile elde edilen ağırlıklarla eleman bazında çarpılıyor, sabit ama öğrenilebilir bir bias ekleniyor, bir aktivasyon fonksiyonundan geçiriliyor ve en sonunda ters FFT uygulanıyor
      Buradaki “frekans” muhtemelen epey soyut bir şey. FFT, net bir frekans yorumu olmayan şekillerde de sık kullanılır. Çoğu zaman evrişim teoremi gibi kullanışlı matematiksel özellikleri nedeniyle kullanılır
      Gerçekten iyi çalışıyorsa oldukça şaşırtıcı ve çok zarif
    • Hiç uzman değilim ama biraz sezgi eklemek gerekirse, self-attention nihayetinde parametreleştirilmiş bir token karıştırıcıdır
      Yani çıktının her vektörü, ilgili girdi vektörünün diğer tüm girdi vektörlerinin bir fonksiyonu tarafından dönüştürülmüş hâline bağlıdır
      https://medium.com/optalysys/attention-fourier-transforms-a-...
      Kavramsal olarak bunun biraz basitleştirilmiş evrişime nasıl benzediğini görebilirsiniz: https://openreview.net/pdf?id=8l5GjEqGiRG
      Evrişim, bir şekilde küresel durumu dikkate almak istediğinizde sık kullanılır

  • Bu framework’e nedensel maskeleme eklemek için n adet farklı FFT yapmak gerekecek gibi görünüyor; konum embedding’lerinden de bahsedilmiyor
    Bu yüzden karşılaştırma yapılan self-attention uygulaması nedensel olmayan NoPE gibi görünüyor; öyleyse bu, baseline’ı kasıtlı olarak zayıf seçme örneği olabilir ve çok etkileyici olmayabilir
    Sonuçlar son teknolojiye yakın olsaydı yazar muhtemelen bundan bahsederdi

    • Long Range Arena (LRA) benchmark’ında kendi modellerinin tüm kategorilerde kazandığını gösteriyorlar. Umarım kaybettikleri kategorileri ya da daha iyi modelleri dışarıda bırakmamışlardır

  • İlgili kaynakça gibi görünüyor: https://arxiv.org/abs/2111.13587
    Adaptive Fourier Neural Operators: Efficient Token Mixers for Transformers
    John Guibas, Morteza Mardani, Zongyi Li, Andrew Tao, Anima Anandkumar, Bryan Catanzaro

  • Burada frekans alanından bakmanın neden yardımcı olduğuna dair bir sezgisi olan var mı merak ediyorum
    DC bileşenini anlıyorum, ama girdi verisinin diğer frekansların anlam taşıyacağı kadar yeterince periyodik olmasını beklemiyorum

  • Birkaç yıl önce O(n log n) tam bağlam karıştırmayı zaten gösteren Hyena Operator önceki çalışmasına değinilmemiş gibi görünüyor
    https://arxiv.org/abs/2302.10866

  • Büyük O gösterimi bir ölçüde fikir veriyor, ama bilgisayar bilimi ya da elektrik mühendisliğiyle ilgili çoğu şey gibi bu da benim kafamın üzerinden geçip gidiyor.
    Matematikte gerçekten kötü biri olarak, bunları anlayabilen ya da en azından öğrenip mühendislik diploması ve lisansı alabilen insanlara imreniyorum.
    FFT hakkında bildiğim şey, sinyalleri dönüştürdüğü, bir tür sinyal işlemede kullanıldığı ve eskiden nükleer patlama tespitinin merkezinde yer aldığını duyduğumdan ibaret.

    • Fourier dönüşümüne dair iyi bir sezgi, Fourier dönüşümünü elle türetemeseniz ya da FFT algoritmasını kendiniz yazamasanız bile çok kullanışlı bir araçtır.
      Temel fikir şu: Yararlı sinyallerin neredeyse tamamı, farklı frekans ve fazlara sahip sinüs dalgalarının toplamı olarak ifade edilebilir. Örneğin elektrik sinyali ya da ses dalgası, x ekseninin zaman olduğu tek boyutlu bir sinyaldir. Görünüşte başa çıkması zor, karmaşık, kıvrımlı bir çizgi olabilir.
      Fourier dönüşümüyle zaman tabanlı bir sinyalin tek tek frekanslarını ayırabilirsiniz. Sonra belirli frekansları istediğiniz şekilde değiştirebilirsiniz. Örneğin sinyalde çok sayıda rastgele sivri gürültü varsa, bu yüksek frekans olarak görünür. Temizlemek için Fourier dönüşümü yapar, belirli bir eşikten yüksek frekanslardaki veriyi atar, sonra kalan veriye ters Fourier dönüşümü uygulayarak özgün sinyalin daha pürüzsüz bir sürümüne dönersiniz. Buna alçak geçiren filtre denir ve özgün sinyalin hareketli ortalamasını almaya oldukça benzer.
      İşin ilginç yanı, bunun daha yüksek boyutlara da oldukça sezgisel biçimde genişletilebilmesidir. x ve y eksenlerinin ikisi de uzay olan iki boyutlu bir sinyal, bir görüntüdür. JPEG sıkıştırması bu kavrama dayanır. Görüntüyü daha küçük saklamak için yüksek frekanslı sinyaller kaldırılır; bunun bedeli olarak ince ayrıntılar kaybedilir ya da çok fazla atılırsa halka biçimli artefaktlar oluşur. Buna üçüncü boyut olarak zamanı eklerseniz video olur ve böylece genişletmeye devam edebilirsiniz.
      Tüm bunlar görsel olarak anlaşılmaya çok uygun olduğundan, matematiğin tamamını derinlemesine bilmeden de iyi bir sezgi kazanabilirsiniz. Görselleştirmeleri ve etkileşimli örnekleri bol olan iyi bir sayfa: https://www.jezzamon.com/fourier/index.html
      3Blue1Brown videosu da iyi açıklıyor: https://youtu.be/spUNpyF58BY?si=dz0z-s8NftW3Htun
    • Kısaca şöyle diyelim: Mikrofonla ölçülen bir ses sinyali gibi tek boyutlu bir zaman alanı sinyaliniz var. Mikrofon sabitse, belirli bir noktada havanın zamana göre yer değiştirmesini ölçüyorsunuz demektir.
      FFT’nin ayrık sürümü olduğu Fourier dönüşümü, bu tek boyutlu zaman alanı sinyalini frekansa karşı genlik ve faz bileşenlerine ayırır.
      Frekans temelde ses perdesidir. Saf sinüs dalgası ya da saf ton, eskiden gece geç saatte TV yayını kapanırken duyulan sese benzer; bu durumda değerlerin çoğu 0’dır ve o tonun frekans konumunda tek bir “sivri tepe” oluşur. Sinyal genliği ne kadar büyükse, sivri tepenin büyüklüğü de o kadar büyük olur. Ses perdesi, yani frekans yükselip alçaldıkça bu sivri tepenin konumu yatay eksen boyunca yukarı aşağı hareket eder.
      Faz temelde sinyalin zaman ofsetidir. Herhangi bir şekilde geciktirilmiş bir ton farklı bir faz olarak görünür. Ancak bu mutlak değil, göreli bir ölçümdür. Birimi radyan, yani açı olduğundan bir çemberi tam tur dönünce tekrar “sıfırlanır”; bu yüzden sinyalin 1 saniye mi yoksa 2 saniye mi kaydığını anlayamazsınız.
      Dolayısıyla tek bir sinyalden, yani zamana karşı genlikten, aslında frekansa karşı genlik ve faz olmak üzere iki bilgi elde edersiniz.
      Sanal ya da karmaşık değişkenleri anlıyorsanız, bu iki sinyal aslında karmaşık bir fonksiyon olan FFT çıktısının büyüklüğü ve argümanından ibarettir.

  • Telemetri çağında, bulut telemetrisine FFT uygulayarak periyodik anomalileri ve yarı kararlı sistemleri olay patladıktan sonra değil önce bulmamak büyük bir fırsat kaçırma gibi geliyor.
    Ne yazık ki bu, fark edebileceğim düzeyde ama uygulayacak teknik düzeyde olmadığım bir şey; üstelik takvimim de zaten dolu.
    “SLA, servis dağıtımından 23–25 dakika sonra en kolay ihlal ediliyor. Hımm, neden acaba… ah hayır.”

    • “Üzgünüm Dave, uygulamanız dağıtıma alınamaz.”
      Şaka bir yana, bunun gerçekten para edebileceği alan, trafik döngülerini tahmin edip sunucu instance’larını yukarı/aşağı ölçekleyerek maliyet tasarrufu sağlamaktır.
      Bu, kişisel zamanda yapıldığında şirketin asla onaylamayacağı, ama hazır ürün olarak paketlenirse şirketin hemen satın alacağı türden bir iştir.