Beam Search: Çevirinin Eski Dostu, LLM'de Niye Azaldı?

Üretim sorunu

Bir LLM'e "Türkiye'nin başkenti nedir?" sorduğunuzda kelime kelime cevap üretir. Her adımda olası 100.000 token üzerinde bir olasılık dağılımı çıkarır. Hangi token seçilecek?

Üç ana strateji vardır:

1. Greedy: En yüksek olasılıklı token. Hızlı ama deterministik ve genellikle düz.
2. Beam search: Birkaç en iyi yolu paralel takip et.
3. Sampling: Olasılık dağılımından rastgele örnekle.

Beam search — algoritma

Beam $k$ (genelde 4-10) tutan bir aramadır. Her adımda:

1. Şu anda $k$ aktif yol var. Her yol: token dizisi + birikmiş log-olasılık.
2. Her yolun her olası uzantısını hesapla. Yani $k \times V$ yeni aday (V vocab).
3. Bunların içinden en yüksek log-olasılıklı $k$ tanesini seç.
4. Yolların hepsi bitmedikçe (EOS token gelene kadar) devam.

Greedy = beam=1 özel durumu. Beam=∞ = tam genişlik araması (mümkün değil).

Neden çeviride hâkimdi

2014-2018 arasında nöral makine çevirisi (NMT) altın çağı yaşadı. Google Translate, DeepL, Facebook NMT — hepsi beam search.

Sebep: çeviri deterministik bir görev. "House" → "ev". Tek doğru cevap (ya da birkaç). Beam search bu uzayı verimli tarar. BLEU skoru beam ile %2-5 artar (greedy'e göre).

Beam genişliği genelde 4-6. Daha geniş yardımcı olmaz hatta zarar verir — "length normalization" sorunu yüzünden.

Length normalization

Beam search'ün bilinen sorunu: kısa yolları tercih eder. Çünkü log-olasılık her tokenle azalır (negatif sayı toplamı). Uzun cümleler aleyhinde.

Çözüm: skoru uzunluğa böl ya da length penalty uygula:

$$\text{score} = \frac{\log P(y|x)}{(5+|y|)^\alpha / (5+1)^\alpha}$$

$\alpha$ tipik 0.6-0.7. Bu Wu ve ark. (Google NMT 2016) ile standartlaştı.

Modern LLM'de neden azaldı

Modern büyük LLM'lerde (GPT, Claude, Gemini) beam search standart değil. Sebep:

1. Olasılık yüksekliği = tek tipliği

Diyalog için çeşitlilik önemli. "İyi günler" gibi yüksek olasılıklı ama sıkıcı yanıtlar yerine "Merhaba, nasıl yardım edebilirim?" gibi düşük olasılıklı ama doğal yanıtlar tercih edilir. Beam search tek tip cevap üretir.

2. Hesap maliyeti

Beam $k$ ile çıkarım maliyeti $k$ kat artar. 1M kullanıcıya $k=5$ ile servis yapan bir şirket için 5x fiyat. LLM ekonomisi bu lükse izin vermiyor.

3. Tekrar problemi

Beam search uzun üretimlerde aynı ifadeyi tekrarlama eğiliminde. "Ben bir AI asistanıyım. Ben bir AI asistanıyım. Ben bir AI asistanıyım..." Sampling'in stokastik doğası bunu kırar.

Modern alternatifler — sampling

Bugünkü LLM'lerin neredeyse hepsi stokastik sampling kullanır:

Temperature sampling

$$P_T(y) \propto P(y)^{1/T}$$

• $T=0$: greedy.
• $T=1$: orijinal dağılım.
• $T=2$: daha düz dağılım, daha çeşitli.

Top-k

Sadece en yüksek $k$ olasılıklı tokenden örnekle. Geri kalan 0 sayılır.

Top-p (nucleus sampling, 2019)

Olasılığı 0'dan $p$'ye kadar olan tokenleri tut. Dinamik boyut. Yüksek belirsizlikte geniş, düşük belirsizlikte dar.

Çoğu LLM defaultu: temperature=0.7-1.0, top-p=0.9-0.95.

Min-p (2023)

Top-p'nin gelişmiş hâli. En yüksek olasılığın bir oranına göre kesme.

Hangi durumda beam search hâlâ kullanılır

Beam search ölmedi:

• Makine çevirisi: Hâlâ standart.
• Konuşma tanıma (ASR): Whisper bile beam kullanır.
• Kod tamamlama: Bazı durumlarda (Copilot gibi).
• Constrained generation: Belirli formatta (JSON, XML) çıktı zorunluysa.

LLM'de "deterministic + doğruluğa kritik" görevlerde temperature=0 + beam=4 hâlâ tercih.

Speculative decoding ile bağlantı

[[speculative-decoding-tahmin-ile-llm-leri-hizlandirma]] aslında beam search'ün hızlı bir varyantı. Küçük model birden fazla "yol" tahmin eder, büyük model paralel doğrular. Sampling kararsızlığını koruyarak hız kazandırır.

Klasik benzetme

Yol aramayı düşün. Greedy: her köşede sadece "şu an en hızlı görünen" yola sap. Beam: $k$ farklı yolu paralel dene, sonunda en kısa olanı al. Sampling: zar at, çeşitlilik için.

Şehir içi yön: beam — kesin sonuç.
Gezinti yürüyüşü: sampling — keşif.

Sade ders

Beam search hikâyesinden iki şey:

1. En iyi algoritma görev bağlamına bağlıdır. Çeviri için beam mükemmel, sohbet için yetersiz. "Modern" demek "her zaman daha iyi" değil — bağlam belirler.
2. Olasılık yüksek olan iyi değildir. Sohbette en olası yanıt çoğu zaman en sıkıcısıdır. Yaratıcılık ile beklenti dengesi modern LLM tasarımının temel meselesidir.

Bağlam

LLM decoding için: [[speculative-decoding-tahmin-ile-llm-leri-hizlandirma]]. Üretim çeşitliliği için: [[bpe-byte-pair-encoding-llm-lerin-kelimelere-bakmasi]]. Makine çevirisi için: [[neural-machine-translation-attention]] (varsa). Arama algoritmaları için: [[arama-algoritmalari-a-bfs-dfs]] (varsa).