- Khi chi phí self-attention trở thành nút thắt trong Transformer ngữ cảnh dài, SPECTRE dùng bộ trộn token dựa trên FFT để giảm độ phức tạp mỗi lớp từ O(L²) xuống O(L log L)
- Mỗi attention head được thay bằng tổ hợp real FFT nhanh, spectral gate thích ứng theo nội dung và inverse FFT, trong khi vẫn giữ nguyên cấu trúc Transformer hiện có
- Trong sinh tự hồi quy, Prefix-FFT cache giúp giảm gánh nặng tính lại FFT ở mỗi bước; mô-đun wavelet tùy chọn có thể bù đắp mất mát đặc trưng cục bộ
- Nhóm so sánh SDPA, FlashAttention-2 và SPECTRE trên backbone Llama-3.2-1B, đo thông lượng và độ trễ khi xử lý 512~128k token trên NVIDIA A100-80GB
- SPECTRE đạt hiệu năng bằng hoặc cao hơn baseline trên PG-19 và ImageNet-1k, hướng tới xử lý ngữ cảnh dài trên GPU phổ thông với dưới 6% tham số bổ sung
Cách giảm chi phí bậc hai của self-attention bằng FFT
- Transformer ngữ cảnh dài cần thiết cho các tác vụ xử lý hàng chục nghìn token như hội thoại nhiều lượt, tóm tắt độ dài bằng sách và thị giác độ phân giải cao
- Self-attention truyền thống có chi phí O(n²d), nên khi ngữ cảnh dài hơn, độ trễ suy luận và mức dùng bộ nhớ tăng lên
- SPECTRE là phương pháp thay thế drop-in, đổi lớp self-attention thành bộ trộn token trong miền tần số
- Chiếu token lên orthonormal Fourier basis
- Áp dụng gate chéo thích ứng theo nội dung và gate low-rank tùy chọn
- Dùng phép biến đổi ngược để đưa trở lại không gian token
- Điểm cốt lõi là giảm độ phức tạp mỗi lớp xuống O(n log n) mà không thay đổi kiến trúc mạng xung quanh
Cấu thành bộ trộn token và hỗ trợ sinh
- Cấu hình thay thế attention head của SPECTRE gồm fast real FFT, spectral gate và inverse FFT
- Spectral gating hoạt động trên n/2 + 1 hệ số tần số, được thiết kế để giảm tính toán và mức dùng bộ nhớ trong khi vẫn giữ năng lực biểu diễn
- Prefix-FFT cache đóng vai trò tương tự KV-cache tiêu chuẩn để hỗ trợ giải mã streaming
- Giảm điểm yếu của các spectral mixer hiện có là phải tính lại FFT ở mỗi time step trong sinh tự hồi quy
- Đây là cấu trúc cho phép sinh hiệu quả trong một ngân sách bộ nhớ cố định
- Wavelet Refinement Module tùy chọn bù đắp các chi tiết cục bộ có thể bị mất trong cách tiếp cận spectral thuần túy, với overhead tính toán nhỏ
Cách áp dụng vào Transformer hiện có
- SPECTRE có thể thay trực tiếp lớp multi-head attention, không đòi hỏi tái thiết kế kiến trúc riêng
- Các mô hình đã pretrained hiện có có thể được fine-tuning bằng lớp SPECTRE
- Đối tượng cập nhật là các tham số mới được đưa vào
- Tham số bổ sung chiếm dưới 6% tổng trọng số
- Khác với các cách tiếp cận cần specialized optimization hoặc kiến trúc phi tiêu chuẩn, SPECTRE giữ nguyên cấu trúc Transformer xung quanh
Thử nghiệm dựa trên Llama-3.2-1B
- So sánh bằng cách áp dụng ba attention kernel cho cùng backbone Llama-3.2-1B
- standard softmax-dot-product attention(SDPA)
- FlashAttention-2
- SPECTRE mixer
- Môi trường đo là NVIDIA A100-80GB, với độ dài chuỗi L ∈ {512, 1k, 4k, 8k, 32k, 128k}
- Chỉ số gồm thông lượng tokens-per-second và single-batch latency
- Thông lượng càng cao càng tốt
- Latency càng thấp càng tốt
- SPECTRE duy trì độ chính xác của backbone trong khi thời gian chạy gần như O(n log n)
- Thời gian chạy gần như phẳng tới 32k token
- Theo abstract, ở ngữ cảnh 128k-token, nhanh hơn FlashAttention-2 tối đa 7×
- Theo danh sách contribution trong nội dung, ở 32k token, suy luận nhanh hơn FlashAttention-2 tối đa 7×
Kết quả benchmark và phạm vi thực dụng
- SPECTRE đạt kết quả bằng hoặc cao hơn baseline trên mô hình hóa ngôn ngữ PG-19 và phân loại ImageNet-1k
- Duy trì trộn ngữ cảnh toàn cục trong khi tránh chi phí bậc hai của self-attention khi xử lý ngữ cảnh dài
- Các phương pháp tăng tốc attention dựa trên sparse pattern, kernel approximation hoặc low-rank structure có thể có hạn chế như hy sinh tính chính xác, cần tối ưu hóa phi tiêu chuẩn hoặc không hỗ trợ streaming generation
- SPECTRE dùng cách tiếp cận miền tần số, trong đó FFT chéo hóa circular convolution và biến global mixing thành element-wise product
- Bằng cách giới hạn tham số bổ sung dưới 6%, SPECTRE hướng tới xử lý ngữ cảnh hundred-kilotoken trên commodity GPU mà không cần specialized hardware
1 bình luận
Ý kiến trên Hacker News
Về cơ bản đây là cách tận dụng định lý tích chập: phép tích chập đắt đỏ trong không gian gốc trở thành phép nhân đơn giản trong không gian đối ngẫu, và điều ngược lại cũng đúng
Nếu dữ liệu có phép tích chập, chỉ cần chuyển sang miền liên hợp rồi biến nó thành phép nhân
Nói cách khác, hãy làm việc trong miền tự nhiên đối với dữ liệu
https://en.wikipedia.org/wiki/Convolution_theorem
Muốn tối ưu thì tối ưu từng bước, và làm càng nhiều việc càng tốt trong không gian hiệu quả nhất có thể
Chẳng phải đó là chuyện khác với việc nó chỉ dễ tính toán hơn sao?
Hơn nữa còn phải dùng số phức trong tính toán, và về mặt số học cũng kém ổn định hơn. Theo tôi biết thì FFT không có lợi cho tích chập thông thường
Với self-attention hoặc mục đích của bài báo này thì n có thể lớn hơn nhiều. Tôi chưa đọc bài báo. Dù vậy vấn đề số phức vẫn còn
Google đã đưa ý tưởng này vào năm 2022 với FNet: Mixing Tokens with Fourier Transforms
Sau đó họ nhận ra rằng trong hầu hết tình huống, hiệu năng nhân ma trận của TPU nhanh hơn FFT
https://arxiv.org/abs/2105.03824
“Nhìn chung, các hướng tiếp cận như FNet, Performer và sparse transformer cho thấy có thể giảm gánh nặng tính toán bằng trộn token cố định hoặc xấp xỉ, nhưng chiến lược lọc phổ thích nghi của chúng tôi kết hợp một cách độc đáo hiệu quả của FFT với các bộ lọc phổ có thể học được và phụ thuộc vào đầu vào. Điều này mang lại một tổ hợp mạnh mẽ giữa khả năng mở rộng và tính thích nghi, vốn rất quan trọng cho các tác vụ mô hình hóa chuỗi phức tạp.”
Sau đó còn có phần so sánh
Nhưng DSP có phần cứng chuyên dụng để hỗ trợ FFT không? Tôi hỏi thật vì tò mò. Chưa từng dùng, nhưng lờ mờ thấy có vẻ sẽ hữu ích
“TPU quá kém hiệu quả với biến đổi Fourier đến mức các nhà nghiên cứu đã không dùng thuật toán FFT cho các chuỗi dưới 4096 phần tử, mà chọn một triển khai biến đổi Fourier có độ phức tạp bậc hai dùng ma trận DFT tính sẵn.”
“Trên GPU Nvidia Quadro P6000, trong kiến trúc FNet, biến đổi Fourier chiếm tới 30% thời gian suy luận.”
Năm 2021, công ty này tuyên bố rằng nếu Google dùng chip quang của họ cho TPU thì có thể giảm thời gian suy luận 40%. Nếu FFTNet đảm nhiệm nhiều việc hơn thì có thể còn giảm thêm
https://scribe.rip/optalysys/attention-fourier-transforms-a-...
Biến đổi Fourier được áp dụng theo chiều “token”. Nhưng trong nhiều ứng dụng, chiều này không mang ý nghĩa. Vì vậy transformer trở thành lựa chọn tốt để xử lý dữ liệu bất biến theo hoán vị
Tôi muốn thấy thêm thí nghiệm dùng biến đổi Fourier trên nhóm hữu hạn ít được biết đến hơn. Nó vừa bất biến theo hoán vị vừa chia sẻ nhiều tính chất với biến đổi Fourier chuẩn
Ngoài ra, nếu đây trở thành làn sóng lớn tiếp theo của LLM, tôi cũng tò mò các engine suy luận như vLLM hay llama.cpp sẽ tích hợp nó dễ đến mức nào
https://en.wikipedia.org/wiki/Fourier_transform_on_finite_gr...
Theo tôi hiểu, llama áp dụng phép quay lên vector tùy theo vị trí trong đầu vào
Toán học thì hoàn toàn vượt quá tầm hiểu của tôi, phần giải thích quanh các công thức cũng chỉ hiểu lơ mơ. Có ai có thể giải thích bằng lời dễ hiểu rằng thứ này tương đương với cơ chế attention như thế nào không?
“Tần số” được nói đến ở đây là gì, và quan hệ vị trí giữa các token được mã hóa ra sao?
Trong phân tích tín hiệu hay hình ảnh thì đây là trực quan nhất: https://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm
Không gian tần số về bản chất là một không gian “phức”, được biểu diễn bằng số phức. Tần số có ưu điểm là nhìn bài toán theo cách toàn cục
Cơ chế này không tương đương với cơ chế attention, và rõ ràng có sự đánh đổi. Tuy vậy, nó có khả năng nắm bắt được khá nhiều quan hệ quan trọng mà attention nắm bắt
Về modReLU thì hiện tại tôi chưa có trực giác tốt, nhưng có vẻ nó quan trọng vì vừa sửa đổi tần số vừa bảo toàn phép biến đổi Fourier ngược
“Tần số” ở đây có lẽ rất trừu tượng. FFT cũng thường được dùng theo những cách không có diễn giải tần số rõ ràng. Nhiều khi nó được dùng vì các tính chất toán học tiện lợi như định lý tích chập
Nếu thật sự hoạt động tốt thì khá đáng kinh ngạc, và rất thanh lịch
Tức là mỗi vector đầu ra phụ thuộc vào việc vector đầu vào tương ứng được biến đổi bởi một hàm nào đó của tất cả các vector đầu vào khác
https://medium.com/optalysys/attention-fourier-transforms-a-...
Về mặt khái niệm, có thể thấy điều này hơi giống một dạng tích chập được đơn giản hóa: https://openreview.net/pdf?id=8l5GjEqGiRG
Tích chập thường được dùng khi muốn xét đến trạng thái toàn cục theo một cách nào đó
Nếu muốn đưa causal masking vào framework này thì có vẻ sẽ phải làm n phép FFT khác nhau, mà cũng không thấy nhắc đến positional embedding
Vì vậy có vẻ triển khai self-attention dùng để so sánh là NoPE phi nhân quả; nếu đúng vậy thì đây có thể là trường hợp cố tình đặt baseline yếu, nên cũng không quá ấn tượng
Nếu kết quả gần với mức state-of-the-art thì có lẽ tác giả đã nhắc đến rồi
Có vẻ là tài liệu tham khảo liên quan: 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
Tôi tò mò liệu có trực giác nào về việc vì sao nhìn trong miền tần số lại hữu ích ở đây không
Tôi hiểu thành phần một chiều, nhưng không kỳ vọng dữ liệu đầu vào đủ mang tính chu kỳ để các tần số khác có ý nghĩa
Có vẻ bài này không nhắc đến nghiên cứu trước đó là Hyena Operator, vốn đã cho thấy việc trộn toàn bộ ngữ cảnh với độ phức tạp O(n log n) từ vài năm trước
https://arxiv.org/abs/2302.10866
https://arxiv.org/abs/2111.00396
Ký hiệu Big-O thì tôi nắm được phần nào, nhưng giống như phần lớn nội dung liên quan đến khoa học máy tính hay kỹ thuật điện, cái này cũng vượt quá tầm hiểu của tôi
Với tư cách là người thật sự rất kém toán, tôi thấy ghen tị với những người có thể hiểu những nội dung như thế này, hoặc ít nhất là học được chúng để lấy bằng kỹ sư và cả giấy phép hành nghề
Những gì tôi biết về FFT chỉ là nó biến đổi tín hiệu, được dùng trong một số loại xử lý tín hiệu, và nghe nói trước đây từng là cốt lõi của việc phát hiện vụ nổ hạt nhân
Ý tưởng cơ bản là thế này: hầu như mọi tín hiệu hữu ích đều có thể được biểu diễn dưới dạng tổng của các sóng sin có tần số và pha khác nhau. Ví dụ, tín hiệu điện hoặc sóng âm là tín hiệu một chiều với trục x là thời gian. Nhìn vào có thể chỉ thấy một đường cong ngoằn ngoèo phức tạp, khó xử lý
Dùng biến đổi Fourier, bạn có thể tách các tần số riêng lẻ của tín hiệu theo thời gian. Sau đó có thể chỉnh sửa các tần số cụ thể theo cách mong muốn. Chẳng hạn nếu tín hiệu có nhiều nhiễu nhọn ngẫu nhiên, chúng sẽ xuất hiện dưới dạng tần số cao. Để làm sạch, ta thực hiện biến đổi Fourier, bỏ dữ liệu ở các tần số cao hơn một ngưỡng nhất định, rồi áp dụng biến đổi Fourier ngược lên phần dữ liệu còn lại để quay về một phiên bản mượt hơn của tín hiệu ban đầu. Đây gọi là bộ lọc thông thấp, và gần như tương tự với việc lấy trung bình trượt của tín hiệu ban đầu
Phần thú vị là có thể mở rộng điều này lên các chiều cao hơn một cách khá trực quan. Tín hiệu hai chiều, trong đó cả trục x và y đều là không gian, chính là hình ảnh. Nén JPEG dựa trên khái niệm này. Để lưu ảnh nhỏ hơn, nó loại bỏ các tín hiệu tần số cao; đổi lại là mất các chi tiết nhỏ, hoặc nếu bỏ quá nhiều thì sẽ xuất hiện artifact dạng vòng. Thêm chiều thứ ba là thời gian vào đó thì thành video, và vẫn có thể tiếp tục mở rộng
Tất cả những điều này rất dễ hiểu bằng thị giác, nên có thể có được trực giác tốt mà không cần hiểu sâu toàn bộ phần toán. Một trang hay có nhiều hình trực quan và ví dụ tương tác: https://www.jezzamon.com/fourier/index.html
Video của 3Blue1Brown cũng giải thích rất tốt: https://youtu.be/spUNpyF58BY?si=dz0z-s8NftW3Htun
Biến đổi Fourier, mà FFT là phiên bản rời rạc, phân rã tín hiệu miền thời gian một chiều đó thành các thành phần biên độ và pha theo tần số
Tần số về cơ bản là cao độ. Một sóng sin thuần hoặc âm thuần giống như âm thanh từng nghe khi đài truyền hình kết thúc phát sóng vào đêm khuya trước đây; trong trường hợp này, hầu hết các giá trị là 0 và có một “đỉnh nhọn” tại vị trí tần số của âm đó. Biên độ tín hiệu càng lớn thì kích thước đỉnh nhọn cũng càng lớn. Khi cao độ, tức tần số, tăng hoặc giảm, vị trí đỉnh nhọn này di chuyển lên xuống dọc theo trục ngang
Pha về cơ bản là độ lệch thời gian của tín hiệu. Một âm bị trễ theo cách nào đó sẽ xuất hiện với pha khác. Tuy nhiên, đây không phải là phép đo tuyệt đối mà là phép đo tương đối. Đơn vị là radian, tức góc, nên khi đi hết một vòng tròn thì nó lại “reset”; vì vậy không thể biết tín hiệu bị lệch 1 giây hay 2 giây
Vì thế, từ một tín hiệu, tức biên độ theo thời gian, thực ra ta thu được hai thông tin: biên độ và pha theo tần số
Nếu hiểu số ảo hoặc biến phức, thì hai tín hiệu này thực ra chỉ là độ lớn và góc pha của đầu ra FFT, vốn là một hàm phức
Trong kỷ nguyên telemetry, có vẻ như việc không áp dụng FFT vào telemetry đám mây để tìm ra bất thường có tính chu kỳ và các hệ thống cận ổn định trước khi sự cố xảy ra, thay vì sau đó, là bỏ lỡ một cơ hội lớn
Không may là chuyện này nằm trong phạm vi tôi có thể nhận ra, nhưng lại vượt quá trình độ kỹ thuật để tôi triển khai, mà lịch làm việc thì cũng đã kín
“SLA dễ bị vi phạm nhất vào khoảng 23–25 phút sau khi triển khai dịch vụ. Hừm, tại sao lại thế nhỉ… à không.”
Đùa sang một bên, lĩnh vực này thật sự có thể hái ra tiền ở chỗ dự đoán chu kỳ lưu lượng để tăng giảm số lượng instance máy chủ, qua đó tiết kiệm chi phí
Đây là loại công việc mà nếu làm bằng thời gian cá nhân thì công ty chắc chắn sẽ không bao giờ phê duyệt, nhưng nếu được đóng gói thành sản phẩm có sẵn thì công ty sẽ mua ngay