Beam Search Decoding Nedir? Paralel Hipotez Arama (Işın Arama Kod Çözme)

#beam search #çıkarım #NLP #metin üretimi #arama algoritması

Dil modellerinin metin üretirken en iyi olası diziyi bulmak için eş zamanlı birden fazla hipotezi paralel keşfettiği çıkarım algoritması.

Beam search decoding, otomatik çeviriden metin özetlemeye kadar geniş bir yelpazede kullanılan temel bir çıkarım algoritmasıdır. Greedy search her adımda yalnızca en yüksek olasılıklı tek tokeni seçerken; beam search 'ışın genişliği' (beam width, k) kadar hipotezi paralel biçimde takip eder. Her adımda mevcut k hipotezin her biri en olası devamlarıyla genişletilir, ortaya çıkan k×vocab_size aday arasından toplamda en yüksek log-olasılıklı k dizisi bir sonraki adım için korunur. Son token üretildiğinde (veya EOS tokeni görüldüğünde) en yüksek kümülatif olasılıklı dizi çıktı olarak döner. k=1 greedy search ile özdeştir; k arttıkça arama kalitesi artabilir ancak hesaplama ve bellek maliyeti de k katına çıkar.

Nasıl Çalışır?

Beam search, her zaman adımında k en iyi kısmi diziyi (hipotezi) bellekte tutar. Başlangıçta k kopya başlatılır; her kopya sözlükteki tüm tokenler için olasılık hesaplar. Ortaya çıkan k×|V| aday içinden log-olasılık toplamı en yüksek k tanesi bir sonraki adıma aktarılır. EOS (end-of-sequence) tokeni üreten hipotez 'tamamlanmış' olarak ayrılır; diğerleri genişlemeye devam eder. Süreç belirli bir maksimum uzunluk veya tüm hipotezler tamamlanana kadar sürer.

Greedy Search ile Karşılaştırma

Greedy search her adımda argmax token'i seçer; bu hızlıdır ama yerel optimuma takılabilir. Beam search k > 1 ile daha geniş arama uzayını tarar ve genellikle daha tutarlı, yüksek kaliteli çıktılar üretir. Ancak k büyüdükçe bellek (k×seq_len) ve işlem süresi artar. Çok büyük k değerlerinde (k > 20) kalite artışı marginal kalırken maliyet yükselir.

Uzunluk Cezası

Ham log-olasılık kısa dizileri tercih eder çünkü her ek token küçük bir log-negatif değer ekler. Bunu önlemek için BLEU veya ROUGE optimizasyonlarında kullanılan uzunluk cezası formülü devreye girer: score = log_prob / length^α. α = 0.6–0.8 değerleri makul denge sağlar.

LLM Döneminde Değişen Rol

GPT, Claude ve Llama gibi büyük otoregresif modellerde beam search yerini büyük ölçüde greedy veya sıcaklık tabanlı örneklemeye (temperature sampling, top-k, top-p) bırakmıştır. Bunun nedenleri: (1) Bu modeller zaten milyarlarca parametre ve RLHF ile yüksek kaliteli greedy çıktı üretebilir, (2) Sampling çıktılarda yaratıcılık ve çeşitlilik sağlar, (3) Beam search 'degenerate' tekrarlı cümlelere eğilimlidir. Spekülatif çıkarım (speculative decoding) ile birleşiminde ise draft-model beam tabanlı kısa diziler önerirken büyük model doğrular.

Kullanım Alanları

Makine çevirisi (Google Translate, DeepL), otomatik konuşma tanıma (ASR/STT), metin özetleme ve protein dizisi tasarımı (AlphaFold2 MSA örneklemesi) beam search'ü aktif kullanan alanlardır. Kod üretiminde GitHub Copilot gibi araçlar genellikle k=1 veya sampling kullanır.