Beam search dapat mengembalikan sequence yang lebih pendek meskipun kandidat yang lebih panjang berisi token yang masuk akal secara lokal pada setiap posisi. Perilaku ini mengikuti langsung dari scoring sequence: model autoregressive mengalikan conditional probability token, atau secara ekuivalen menjumlahkan log probability-nya. Karena probability token paling besar bernilai satu, setiap token tambahan menyumbangkan log term yang tidak positif.

Aritmetika tersebut menjadikan panjang sequence bagian dari decoding. Beam width mengubah kandidat mana yang bertahan, tetapi tidak menghilangkan efek scoring. Karena itu, decoder memerlukan kebijakan yang disengaja untuk membandingkan hypothesis dengan panjang berbeda dan menentukan kapan hypothesis yang sudah lengkap cukup baik untuk menghentikan search.

Skor sequence mentah terakumulasi pada setiap token

Untuk input x dan output sequence y = (y_1, ..., y_T), model autoregressive memfaktorkan conditional probability sebagai

p(y | x) = product_t p(y_t | y_<t, x)

Decoder biasanya bekerja dalam log space:

S(y) = sum_t log p(y_t | y_<t, x)

Setiap term dalam penjumlahan tersebut bernilai nol atau negatif. Memperpanjang hypothesis karena itu hanya dapat mempertahankan raw log score dalam kasus batas ketika probability bernilai satu; biasanya skor akan menurun.

Pertimbangkan dua kandidat lengkap:

A: 3 tokens, log score = -1.8
B: 6 tokens, log score = -2.4

Dengan ranking berdasarkan raw log-probability, A menang karena -1.8 > -2.4. Perbandingan tersebut konsisten secara internal dengan distribusi model. Namun, itu tidak membuktikan bahwa A lebih lengkap, lebih informatif, atau lebih sesuai untuk metric pada level aplikasi.

Perbedaan ini penting karena beam search adalah prosedur search atas skor model. Beam search tidak dapat memperbaiki scoring objective hanya dengan mengeksplorasi lebih banyak kandidat.

Beam width mengekspos scoring objective

Pada setiap posisi decoding, beam search memperluas hypothesis aktif dan mempertahankan sejumlah terbatas kandidat berdasarkan skornya. Beam yang lebih lebar mengurangi tekanan pruning dalam aproksimasi tersebut: lebih banyak alternatif tetap tersedia untuk ekspansi berikutnya.

Hal ini dapat mengekspos sequence lengkap dengan skor tinggi yang mungkin sudah dipangkas oleh beam sempit. Jika model memberikan total probability yang sangat tinggi pada output pendek, search yang lebih lebar dapat membuat output tersebut lebih mudah ditemukan. Dalam kondisi itu, kualitas task yang lebih rendah dengan beam lebih lebar bukan bukti bahwa search yang lebih lebar secara intrinsik buruk. Search justru mungkin lebih baik dalam mengoptimalkan skor model yang tidak selaras dengan properti output yang diinginkan.

Pemisahan ini berguna saat debugging. Search error berarti decoder gagal menemukan kandidat yang memiliki skor lebih baik menurut objective yang dinyatakan. Model atau scoring error berarti kandidat berskor tinggi yang ditemukan tidak diinginkan menurut kriteria task. Mengubah beam width terutama menangani kategori pertama.

Length normalization mengubah urutan kandidat

Respons yang umum adalah menormalisasi akumulasi log probability dengan fungsi panjang sequence. Bentuk sederhananya adalah

S_norm(y) = S(y) / T^alpha

di mana T adalah panjang sequence dan alpha mengontrol kekuatan normalisasi.

Dengan alpha = 0, bentuk ini kembali menjadi raw score. Nilai positif mengurangi magnitude akumulasi skor negatif untuk sequence yang lebih panjang. Ranking yang dihasilkan bukan ranking probability yang sama dengan model asli; ini adalah decoding objective yang dimodifikasi.

Untuk contoh sebelumnya dan alpha = 1:

A: -1.8 / 3 = -0.60
B: -2.4 / 6 = -0.40

Kandidat B sekarang berada di atas A. Tidak ada perubahan pada token probability yang mendasarinya. Yang berubah hanya aturan untuk membandingkan sequence lengkap.

Ini adalah batas implementasi yang penting. Length normalization bukan koreksi numerik yang netral. Formula dan koefisiennya mengodekan preferensi tentang bagaimana evidence yang terakumulasi harus diskalakan terhadap panjang output.

Length reward mengekspresikan kebijakan yang berbeda

Keluarga scoring lain menambahkan reward untuk setiap token yang dihasilkan, sering kali dengan cap atau batas lain:

S_reward(y) = S(y) + lambda * min(T, L)

Di sini lambda adalah magnitude reward dan L membatasi sejauh mana reward diterapkan. Raw model score tetap menurun ketika token ditambahkan, sementara reward mengimbangi sebagian penurunan tersebut dalam rentang yang diizinkan.

Normalization dan additive reward dapat menghasilkan ranking berbeda karena keduanya mentransformasi skor dengan cara berbeda. Membagi dengan fungsi panjang mengubah skala seluruh skor yang terakumulasi. Menambahkan reward mengubah preferensi incremental yang terkait dengan memperpanjang sequence. Keduanya tidak seharusnya diperlakukan sebagai parameter yang dapat dipertukarkan hanya dengan sintaks berbeda.

Pilihan yang sesuai bergantung pada kontrak output. Translation, transcription, constrained generation, dan open-ended text generation dapat memiliki distribusi panjang yang dapat diterima secara berbeda. Koefisien yang dikalibrasi untuk satu distribusi dapat mendistorsi distribusi lain.

Probability end-of-sequence adalah bagian dari mekanisme

Perilaku panjang juga terkait dengan token end-of-sequence. Sebuah hypothesis menjadi lengkap ketika decoder menghasilkan termination token yang ditetapkan. Probability yang diberikan pada token tersebut bersaing dengan probability token lanjutan biasa pada setiap posisi yang memenuhi syarat.

Model yang memberikan termination probability cukup besar terlalu dini dapat menghasilkan kandidat lengkap pendek dengan raw score yang kompetitif. Search kemudian menentukan apakah kandidat tersebut tetap terlihat; model menyediakan probability yang membuatnya kompetitif.

Minimum-length constraint dapat memblokir termination sebelum posisi tertentu. Constraint semacam itu berguna ketika aplikasi memiliki batas bawah yang nyata, tetapi ia mengubah ruang output yang diizinkan. Constraint tidak mengkalibrasi ulang estimasi probability model. Setelah minimum tercapai, hubungan skor yang sama dapat muncul kembali.

Maximum length memiliki peran batas yang serupa. Ia mencegah decoding tanpa batas dan menyediakan systems limit, tetapi tidak boleh disamakan dengan koreksi scoring. Decoder yang dipaksa berhenti pada cap dapat berhenti tanpa model memilih end token normalnya, bergantung pada implementasi.

Stopping criteria harus sesuai dengan transformasi skor

Beam search mempertahankan hypothesis parsial dan lengkap secara bersamaan. Berhenti segera setelah satu beam selesai umumnya berbeda dari berhenti ketika tidak ada hypothesis aktif yang dapat melampaui kandidat lengkap terbaik berdasarkan scoring rule decoder.

Untuk raw log probability, memperpanjang hypothesis parsial tidak dapat meningkatkan akumulasi log score-nya. Properti monotonik tersebut dapat mendukung upper bound bagi kandidat yang belum selesai. Ketika skor terbaik yang belum selesai tidak lagi dapat mengalahkan skor terbaik yang sudah selesai, ekspansi lebih lanjut tidak dapat memperbaiki hasil berdasarkan raw objective tersebut.

Skor panjang yang dimodifikasi memperumit bound. Normalization atau length reward positif dapat meningkatkan transformed score kandidat setelah ekspansi meskipun raw log probability-nya menurun. Stopping rule yang disalin dari raw-score decoding karena itu dapat berhenti terlalu dini jika mengabaikan transformasi tersebut.

Inilah salah satu alasan scoring dan stopping harus dirancang bersama. Decoder memerlukan upper bound yang valid untuk fungsi ranking yang benar-benar digunakan, bukan hanya untuk log probability model yang belum dimodifikasi.

Bandingkan perilaku panjang pada distribusi target

Satu nilai rata-rata panjang output terlalu kasar untuk mendiagnosis perilaku beam. Dua sistem dapat memiliki mean yang sama tetapi berbeda secara substansial pada input pendek dan panjang. Evaluasi lebih informatif ketika panjang kandidat diperiksa bersama task signal yang relevan.

Untuk task input-output berpasangan, pemeriksaan yang berguna mencakup rasio panjang output terhadap reference pada bucket panjang input, frekuensi termination di dekat batas minimum atau maksimum yang dikonfigurasi, serta kualitas task pada bucket yang sama. Untuk aplikasi tanpa satu reference length, product constraint eksplisit atau structured completion check dapat memberi sinyal yang lebih relevan daripada target panjang corpus-wide.

Beam width juga perlu divariasikan selama evaluasi. Jika peningkatan beam secara konsisten menggeser output menuju ekstrem panjang sambil meningkatkan skor internal decoder, pola tersebut mengarah pada scoring objective atau distribusi model, bukan sekadar kekurangan search.

Parameter panjang harus dievaluasi pada held-out data yang mewakili workload yang dituju. Menyetelnya terhadap final test set memasukkan informasi test ke dalam pemilihan decoder dan mengurangi nilai test tersebut sebagai estimasi independen.

Pisahkan model probability dan preferensi decoder

Raw sequence probability, normalized score, additive length reward, minimum-length constraint, dan stopping rule menjawab pertanyaan yang berbeda. Menggabungkannya ke dalam satu field score yang tidak transparan membuat kegagalan lebih sulit diinterpretasikan.

Decoder praktis dapat menyimpan raw accumulated log probability secara terpisah dari adjusted ranking score. Pemisahan tersebut memungkinkan pemeriksaan apakah kandidat menang karena model memang memilihnya atau karena kebijakan decoding mengubah ranking-nya. Ini juga membuat perubahan length coefficient dapat diaudit tanpa berpura-pura bahwa model probability berubah.

Bias panjang beam search karena itu bukan terutama tentang satu koreksi universal, melainkan tentang menjaga batas yang jelas antara probability estimation dan decision policy. Begitu decoder mengubah ranking lintas panjang, transformasi tersebut menjadi bagian dari objective aplikasi dan stopping logic-nya harus menghormati definisi yang sama.

Kecerdasan Buatan LLM Inferensi Beam Search