Editorial ilmu komputer
Open AccessOA2026
Kepala Transformer Mencari Keteraturan
Transformer 2 kepala 1 lapis dapat memeriksa keterurutan barisan bit, sedangkan 1 kepala 1 lapis tidak, bahkan dengan MLP keluaran.
Jasper van Doornmalen; Alexander Kozachinskiy; Corinna Mathwieser; Tomasz Steifer; Felipe Urrutia; José Verschae; Przemysław Andrzej Wałȩga· 2026· DOI 10.48550/arXiv.2609.25588
Masalah inti
Makalah ini menyelidiki kemampuan komputasional transformer, khususnya berfokus pada masalah penentuan apakah suatu barisan bit terurut (yakni tidak menurun). Penelitian sebelumnya telah mengeksplorasi masalah serupa, tetapi studi ini memperkenalkan model ketika transformer menyertakan perceptron multi-lapis (MLP) keluaran. Pertanyaan utamanya adalah: dapatkah transformer dengan satu lapis dan jumlah kepala atensi terbatas menyelesaikan tugas pengurutan? Penulis menunjukkan suatu pemisahan: transformer 1 kepala 1 lapis tidak dapat, tetapi transformer 2 kepala 1 lapis dapat. Hasil ini berkontribusi pada pemahaman tentang bagaimana jumlah kepala atensi memengaruhi ekspresivitas dalam arsitektur transformer.
Inovasi
Hasil utamanya ada dua:
1. **Ketidakmungkinan untuk 1 kepala**: Tidak ada transformer 1 kepala 1 lapis dengan MLP keluaran yang dengan benar memeriksa apakah suatu barisan bit terurut untuk semua panjang masukan.
2. **Kemungkinan untuk 2 kepala**: Terdapat transformer 2 kepala 1 lapis dengan MLP keluaran yang dengan benar memeriksa apakah suatu barisan bit terurut.
Hasil-hasil ini berlaku di bawah model transformer standar dengan MLP keluaran. Penulis tidak memberikan batas galat eksplisit atau kompleksitas sampel, karena fokusnya adalah komputasi eksak. Pemisahannya ketat: menambahkan kepala atensi kedua memungkinkan penyelesaian masalah yang jika tidak demikian mustahil.
Makalah ini menyelidiki kemampuan komputasional transformer, khususnya berfokus pada masalah penentuan apakah suatu barisan bit terurut (yakni tidak menurun). Penelitian sebelumnya telah mengeksplorasi masalah serupa, tetapi studi ini memperkenalkan model ketika transformer menyertakan perceptron multi-lapis (MLP) keluaran. Pertanyaan utamanya adalah: dapatkah transformer dengan satu lapis dan jumlah kepala atensi terbatas menyelesaikan tugas pengurutan? Penulis menunjukkan suatu pemisahan: transformer 1 kepala 1 lapis tidak dapat, tetapi transformer 2 kepala 1 lapis dapat. Hasil ini berkontribusi pada pemahaman tentang bagaimana jumlah kepala atensi memengaruhi ekspresivitas dalam arsitektur transformer.
Penulis menganalisis masalah pengurutan di bawah model transformer dengan MLP keluaran. Secara formal, diberikan barisan masukan
, tugasnya adalah mengeluarkan 1 jika
dan 0 jika tidak. Arsitektur transformer yang ditinjau terdiri atas satu lapis dengan kepala atensi, diikuti oleh MLP keluaran. Mekanisme atensi menghitung untuk setiap posisi jumlah berbobot dari nilai-nilai semua posisi, dengan bobot ditentukan oleh softmax atas hasil kali titik query-key. MLP keluaran kemudian memproses keluaran atensi yang digabungkan. Penulis membuktikan bahwa untuk , tidak ada transformer semacam itu yang dapat menyelesaikan masalah pengurutan, sedangkan untuk , terdapat transformer yang dapat melakukannya. Pembuktian ketidakmungkinan kemungkinan menggunakan argumen kompleksitas penghitungan atau komunikasi, sedangkan konstruksi untuk merancang secara eksplisit pola atensi dan bobot MLP. Diagram Mermaid yang menggambarkan arsitektur ditunjukkan di bawah ini.
Mengapa penting
Temuan ini menyoroti peran jumlah kepala atensi dalam ekspresivitas transformer. Masalah pengurutan adalah tugas sederhana namun fundamental yang memerlukan pembandingan elemen-elemen bersebelahan. Satu kepala atensi hanya dapat menghitung rata-rata global atau satu pola tunggal, yang tidak cukup untuk mendeteksi pelanggaran lokal terhadap keterurutan. Dengan dua kepala, model dapat secara simultan memperhatikan aspek-aspek berbeda, seperti bit saat ini dan bit sebelumnya, sehingga memungkinkan deteksi inversi. Hasil ini melengkapi penelitian sebelumnya tentang batasan transformer, seperti ketidakmampuan menyelesaikan paritas atau mayoritas dengan jumlah kepala terbatas. Penyertaan MLP keluaran tidak mengatasi batasan 1 kepala, yang menegaskan bahwa hambatan utamanya ada pada mekanisme atensi. Penelitian selanjutnya dapat mengeksplorasi jumlah minimum kepala yang diperlukan untuk tugas barisan lain dan dampak kedalaman. Kandidat taksonomi (Architecture, Cybersecurity, Network, Cryptography) menunjukkan potensi penerapan pada protokol keamanan yang relevan dengan pemeriksaan keterurutan, seperti pada validasi nonce kriptografi atau pengurutan paket jaringan.
Siapa yang sebaiknya membaca
Praktisi dan peneliti ilmu komputer
Membuka konten member…