Beam search memberi peringkat pada sequence parsial memakai skor yang terakumulasi sepanjang proses decoding. Jika skor tersebut berupa jumlah log-probability token, setiap token tambahan biasanya menyumbang nilai non-positif. Kandidat yang lebih panjang mendapat lebih banyak kesempatan untuk menurunkan skor mentahnya, bahkan ketika continuation-nya tetap masuk akal secara lokal.
Sifat ini bukan cacat pada teori probabilitas. Efek tersebut muncul karena sequence lengkap dengan jumlah faktor kondisional berbeda sedang dibandingkan. Persoalannya menjadi relevan pada implementasi ketika decoder diharapkan menghasilkan completion yang berguna, bukan sekadar mengurutkan sequence berdasarkan probabilitas model tanpa penyesuaian.
Probabilitas sequence menjadi skor aditif
Untuk sequence y_1, ..., y_T yang dihasilkan dengan kondisi input x, model autoregresif memfaktorkan probabilitasnya sebagai
P(y | x) = product_t P(y_t | y_<t, x)Beam search umumnya bekerja dalam ruang log:
S(y) = sum_t log P(y_t | y_<t, x)Logaritma mengubah perkalian menjadi penjumlahan dan menghindari perkalian banyak probabilitas kecil. Karena setiap probabilitas kondisional berada antara nol dan satu, nilai logaritmanya paling tinggi nol. Menambahkan satu token biasa ke sequence tidak dapat menaikkan log-probability kumulatif mentah ini.
Dari sini muncul efek panjang yang bersifat struktural. Ambil dua kandidat selesai dengan skor mentah -4.0 dan -5.0. Pada skor sequence mentah, -4.0 berada di atas -5.0 tanpa memedulikan apakah kandidat pertama memiliki tiga token dan kandidat kedua memiliki sepuluh token. Perbandingan itu sah untuk distribusi model, tetapi panjang sequence ikut tertanam di dalam ranking.
Token end-of-sequence juga menjadi bagian dari faktorisasi yang sama ketika model menggunakannya. Kandidat yang mencapai token tersebut lebih awal berhenti mengakumulasi suku token berikutnya. Karena itu, implementasi beam perlu menetapkan skor untuk hipotesis aktif sekaligus aturan pembandingan hipotesis yang sudah selesai.
Normalisasi mengubah objektif ranking
Decoder dapat mengompensasi efek panjang kumulatif dengan mentransformasi skor mentah. Bentuk sederhana membaginya dengan panjang sequence yang dihasilkan:
S_norm(y) = S(y) / TNilai tersebut merupakan rata-rata log-probability token. Objektif ranking-nya tidak sama dengan probabilitas sequence mentah. Kandidat yang lebih panjang dan memiliki skor mentah lebih rendah dapat berada di atas kandidat pendek jika rata-rata skor tokennya lebih tinggi.
Sebagai contoh:
candidate A: S = -4.0, T = 4, S_norm = -1.0
candidate B: S = -6.0, T = 10, S_norm = -0.6Skor mentah memilih A karena -4.0 > -6.0. Rata-rata log-probability memilih B karena -0.6 > -1.0. Tidak ada logit model yang berubah. Perbedaannya hanya berasal dari aturan ranking pada tingkat sequence.
Banyak decoder memakai length penalty berparameter, bukan pembagian langsung dengan T. Fungsi tepatnya bergantung pada implementasi. Parameter bernama length_penalty tidak menetapkan satu formula universal, konvensi tanda, atau posisi penerapan dalam proses pencarian. Reproduksi perilaku membutuhkan persamaan scoring yang benar-benar dipakai oleh serving stack atau generation stack tersebut.
Skor saat pencarian dan ranking akhir dapat berbeda
Beam search tidak dapat mempertahankan seluruh continuation yang mungkin. Pada setiap langkah, hanya sejumlah hipotesis terbatas yang disimpan. Akibatnya, keputusan pruning menentukan sequence mana yang masih dapat dicapai. Posisi penerapan normalisasi panjang pun menjadi signifikan.
Satu implementasi dapat memakai skor ternormalisasi ketika memangkas beam aktif. Implementasi lain dapat mempertahankan beam berdasarkan skor kumulatif mentah, lalu menerapkan penyesuaian panjang hanya ketika memberi peringkat pada sequence yang sudah selesai. Keduanya dapat menghasilkan output berbeda walaupun model, beam width, dan nilai parameter penalti sama.
Penyebabnya adalah pruning yang tidak dapat dibatalkan. Setelah sebuah sequence parsial keluar dari beam, penyesuaian skor pada tahap akhir tidak dapat mengembalikan turunannya. Aturan scoring yang hanya diterapkan saat completion mengubah urutan kandidat yang masih tersisa; aturan yang diterapkan selama ekspansi juga dapat mengubah kandidat mana yang bertahan.
Perbedaan ini perlu diperhitungkan saat membandingkan library atau memindahkan workload antar sistem inferensi. Menyamakan formula penalti akhir belum cukup jika pruning beam, penanganan end-of-sequence, atau pencatatan completion berbeda.
Beam width tidak menghapus efek panjang
Memperbesar beam width mempertahankan lebih banyak alternatif, tetapi tidak mendefinisikan ulang skor. Jika skor kumulatif mentah tetap digunakan, pola ranking yang bergantung pada panjang juga tetap ada. Beam yang lebih lebar dapat mengurangi sebagian kesalahan pencarian akibat pruning terlalu dini, tetapi tidak mengubah objektif probabilitas sequence mentah menjadi objektif ternormalisasi.
Beam width juga tidak dengan sendirinya menjamin sequence selesai dengan skor global tertinggi akan ditemukan. Jaminan semacam itu memerlukan kondisi tertentu pada prosedur pencarian dan stopping rule. Decoder praktis dapat memiliki beam width terbatas, early stopping, batas panjang minimum atau maksimum, filter token, serta processor lain. Masing-masing dapat mengubah ruang sequence yang benar-benar diperiksa.
Pemisahan yang berguna adalah antara scoring model dan kebijakan pencarian. Model menyediakan probabilitas token kondisional. Beam width mengatur jumlah hipotesis yang dipertahankan. Normalisasi panjang mentransformasi skor sequence. Stopping rule menentukan saat ekspansi berakhir. Dengan memisahkan mekanisme ini, sumber perbedaan output menjadi lebih mudah diisolasi.
Aturan completion berinteraksi dengan skor ternormalisasi
Decoder juga membutuhkan aturan untuk menentukan kapan jumlah hipotesis selesai sudah memadai. Dengan skor mentah, hipotesis yang belum selesai memiliki skor kumulatif yang hanya dapat tetap atau turun saat token ditambahkan. Sifat ini dapat dipakai untuk membentuk batas yang menentukan apakah ekspansi lanjutan masih berpotensi mengalahkan kandidat selesai.
Skor yang dinormalisasi berdasarkan panjang membuat penalaran tersebut lebih rumit. Denominator berubah ketika hipotesis bertambah panjang, sehingga skor akhir ternormalisasi tidak ditentukan oleh skor mentah saat ini saja. Bergantung pada fungsi normalisasinya, penambahan token dapat memperbaiki nilai ternormalisasi walaupun log-probability mentah menurun.
Karena itu, kondisi early stopping yang sah untuk satu aturan scoring belum tentu sah untuk aturan lain. Implementasi dapat memakai bound konservatif, stopping heuristik, atau kriteria khusus library. Semua itu merupakan semantik pencarian, bukan properti yang dijamin oleh model autoregresif di bawahnya.
Batas panjang minimum menambah interaksi lain. Jika token end-of-sequence diblokir sebelum ambang tertentu, kandidat pendek tidak dapat berhenti walaupun model memberi token tersebut probabilitas tinggi. Batas panjang maksimum membentuk sisi sebaliknya dengan memaksa pencarian berhenti atau melakukan finalisasi sesuai aturan implementasi. Length penalty bekerja di dalam batas eksternal tersebut, bukan menggantikannya.
Perbandingan skor membutuhkan kontrak decoding lengkap
Skor beam hanya bermakna jika konvensi scoring-nya diketahui. Log-probability kumulatif mentah, rata-rata log-probability, dan skor dengan penyesuaian panjang merupakan besaran berbeda. Membandingkan angka antar sistem tanpa formula terkait dapat menciptakan ekuivalensi semu walaupun keduanya sama-sama menamai nilainya sebagai sequence score.
Hal serupa berlaku untuk perbedaan output. Ketika dua implementasi beam search menghasilkan sequence berbeda, model hanya salah satu kemungkinan sumbernya. Beam width, transformasi skor, tahap penerapan transformasi, penanganan end-of-sequence, urutan pruning, dan kriteria berhenti semuanya dapat mengubah sequence terpilih tanpa perubahan parameter model.
Normalisasi panjang karena itu lebih tepat diperlakukan sebagai bagian dari objektif decoder, bukan koreksi kosmetik setelah generation selesai. Begitu normalisasi ikut menentukan pruning atau ranking completion, mekanisme tersebut turut mendefinisikan sequence yang dicari oleh prosedur beam search.