Как работает greedy decoding vs beam search vs sampling?

Краткий тезис

Greedy decoding, beam search и sampling — это три базовые стратегии декодирования последовательностей в языковых моделях. Greedy выбирает токен с максимальной вероятностью на каждом шаге, search|beam search хранит несколько гипотез и выбирает лучшую, а sampling вносит случайность для повышения разнообразия. Выбор стратегии определяет баланс между точностью, креативностью и вычислительной стоимостью, что критически важно для задач RAG и AI-агентов.

1. Термин: Декодирование в LLM

Декодирование (decoding) — это процесс генерации последовательности токенов (слов, подслов) из вероятностного распределения, которое выдаёт модель. На каждом шаге модель предсказывает вероятности для всех токенов словаря, а стратегия декодирования решает, какой токен выбрать следующим.

Почему это важно

• Разные задачи требуют разного поведения: перевод — точность, сторителлинг — креативность.
• В Agentic RAG агент должен иногда действовать детерминированно (вызов инструмента), а иногда генерировать вариативные ответы.
• Неправильная стратегия ведёт к зацикливанию, повторениям или бессмысленному тексту.

2. Greedy decoding (жадное декодирование)

2.1 Как работает

На каждом шаге выбирается токен с наибольшей вероятностью (argmax). Процесс детерминирован: при одинаковых входных данных результат всегда один и тот же.

import torch

def greedy_decode(logits):
    # logits: [vocab_size]
    next_token = torch.argmax(logits, dim=-1)
    return next_token.item()

2.2 Преимущества

• Простота и минимальная вычислительная сложность.
• Детерминизм — удобно для отладки и тестирования.
• Хорошо работает для коротких последовательностей и задач, где один правильный ответ (например, извлечение факта).

2.3 Недостатки

• Локальный оптимум: выбор лучшего токена на каждом шаге не гарантирует лучшую последовательность в целом.
• Повторения: модель может зацикливаться на одних и тех же токенах (например, «и и и и»).
• Отсутствие разнообразия: не подходит для творческих задач.

2.4 Когда использовать

• Извлечение информации в RAG (ответ должен быть строго по фактам).
• Вызов инструментов агентом (детерминированный формат JSON).
• Бенчмаркинг — как baseline.

3. Beam search (лучевой поиск)

3.1 Как работает

Вместо одного токена хранится K гипотез (beam width). На каждом шаге каждая гипотеза расширяется всеми возможными токенами, затем выбираются K лучших по суммарной логарифмической вероятности. В конце выбирается гипотеза с наибольшей вероятностью (часто с нормализацией по длине).

def beam_search(model, start_token, beam_width=3, max_len=50):
    hypotheses = [(start_token, 0.0)]  # (sequence, log_prob)
    for _ in range(max_len):
        candidates = []
        for seq, score in hypotheses:
            logits = model(seq)
            probs = torch.softmax(logits[-1], dim=-1)
            topk_probs, topk_tokens = torch.topk(probs, beam_width)
            for token, prob in zip(topk_tokens, topk_probs):
                new_seq = seq + [token.item()]
                new_score = score + torch.log(prob).item()
                candidates.append((new_seq, new_score))
        # Keep top K
        candidates.sort(key=lambda x: x[1], reverse=True)
        hypotheses = candidates[:beam_width]
    return max(hypotheses, key=lambda x: x[1])[0]

3.2 Преимущества

• Глобальный оптимум — находит последовательности, которые жадный алгоритм мог пропустить.
• Контролируемое качество: увеличение K улучшает результат, но растёт время.
• Нормализация длины (normalization|length normalization) предотвращает предпочтение коротких последовательностей.

3.3 Недостатки

• Высокая вычислительная сложность: O(K * vocab_size * L).
• Склонность к повторениям (особенно без штрафа за повтор).
• Не подходит для креативных задач — выдаёт «средний» текст.

3.4 Когда использовать

• Машинный перевод, суммаризация — задачи с одним «правильным» вариантом.
• Генерация кода — точность важнее разнообразия.
• RAG с фактологическим ответом — когда нужно выбрать лучший из нескольких вариантов.

4. Sampling (сэмплирование)

4.1 Основная идея

Вместо выбора argmax токен выбирается случайно из распределения вероятностей. Это вносит стохастичность и разнообразие.

4.2 Temperature scaling

Параметр temperature (T) контролирует «остроту» распределения:

• T → 0: распределение стремится к one-hot (greedy).
• T = 1: исходное распределение.
• T > 1: распределение становится более равномерным (больше случайности).

def sample_with_temperature(logits, temperature=1.0):
    scaled_logits = logits / temperature
    probs = torch.softmax(scaled_logits, dim=-1)
    next_token = torch.multinomial(probs, num_samples=1)
    return next_token.item()

4.3 Top-k sampling

Оставляем только K токенов с наибольшей вероятностью, пересчитываем распределение и сэмплируем из них. Убирает «длинный хвост» маловероятных токенов.

4.4 Top-p (nucleus) sampling

Выбираем минимальный набор токенов, чья суммарная вероятность ≥ p (например, 0.9), и сэмплируем из них. Адаптивный размер набора.

def top_p_sampling(logits, p=0.9):
    sorted_logits, sorted_indices = torch.sort(logits, descending=True)
    cum_probs = torch.cumsum(torch.softmax(sorted_logits, dim=-1), dim=-1)
    # Remove tokens with cumulative probability above p
    sorted_indices_to_remove = cum_probs > p
    sorted_indices_to_remove[..., 1:] = sorted_indices_to_remove[..., :-1].clone()
    sorted_indices_to_remove[..., 0] = False
    indices_to_remove = sorted_indices[sorted_indices_to_remove]
    logits[indices_to_remove] = -float('Inf')
    probs = torch.softmax(logits, dim=-1)
    return torch.multinomial(probs, 1).item()

4.5 Преимущества

• Разнообразие — подходит для творческих задач (сторителлинг, диалоги).
• Гибкость — комбинация temperature, top-k, top-p позволяет тонко настраивать случайность.

4.6 Недостатки

• Нестабильность — при одном и том же промпте можно получить разные ответы.
• Риск бессмысленного текста при высокой температуре.
• Сложнее отлаживать — недетерминированность.

4.7 Когда использовать

• Генерация креативного контента (поэзия, сценарии).
• Диалоговые агенты — чтобы не повторять одни и те же фразы.
• Data augmentation — создание синтетических данных.

5. Сравнительная таблица

6. Влияние на RAG и Agentic RAG

• Greedy — для вызова инструментов агентом (детерминированный JSON).
• Beam search — для генерации ответа на фактологический запрос в RAG (выбор лучшего из нескольких вариантов).
• Sampling — для вариативных ответов в диалоговом агенте (например, рекомендации).
• Гибридные подходы: greedy для первых токенов (формат), sampling для остальных (содержание).

7. Практические рекомендации

• Для точных задач (перевод, QA): beam search с K=4–5 и length normalization.
• Для креативных задач (сторителлинг): top-p=0.9–0.95, temperature=0.7–1.0.
• Для агентов: greedy для вызова функций, sampling для генерации текста.
• Избегайте high temperature без top-k/p — модель может «уйти в отрыв».

Пет-проект для закрепления

Задача: Реализовать простой декодер для небольшой языковой модели (например, GPT-2) и сравнить результаты трёх стратегий на одном промпте.

Инструменты: Python, PyTorch, transformers (Hugging Face).

Шаги:

1. Загрузите предобученную модель (distilgpt2).
2. Напишите функции greedy_decode, beam_search (с beam_width=3) и sample_with_top_p.
3. Для одного промпта (например, «The future of AI is») сгенерируйте 5 вариантов каждой стратегией.
4. Визуализируйте логарифмические вероятности последовательностей.
5. Сделайте выводы: какая стратегия даёт наиболее осмысленный результат?

Ожидаемый результат: Вы увидите, что greedy даёт короткий предсказуемый текст, beam search — более развёрнутый и связный, sampling — разнообразный, но иногда бессмысленный.

Связь с другими вопросами

Навигация

• Предыдущий: 677
• Следующий: 679
• Индекс: 00. Индекс разборов