Модуль 10. Поиск, проверка и вычислительный бюджет на этапе генерации

• Адаптивный бюджет: простому запросу выделяется один ответ, трудному — восемь. Число попыток зависит от запроса.
• Параллельный бюджет: для трудного запроса создаются восемь кандидатов.
• Последовательный бюджет: один кандидат может продолжаться до 2 000 токенов.
• Поисковый бюджет: два наиболее перспективных префикса ветвятся и получают дополнительные продолжения.

Число «8» описывает только ширину одного этапа. Оно не сообщает длину кандидатов, число раскрытых ветвей, стоимость оценивания, задержку, возможность пакетной генерации и число вызовов внешней проверяющей системы. Для воспроизводимого сравнения нужны хотя бы токены, прямые проходы генератора, вызовы проверки, задержка и денежная стоимость.

pass@32 = 0.98 означает, что в 98% запросов среди 32 кандидатов присутствует хотя бы один правильный ответ — при заданном критерии проверки и протоколе генерации. Итоговая точность 0.61 означает, что ранжировщик часто не выбирает доступный правильный кандидат.

Из этого следует:

1. генератор обладает высоким покрытием при данном бюджете;

2. этап выбора является существенным ограничением системы;

3. полезно измерить точность ранжировщика условно на событиях, где правильный кандидат вообще присутствует;

4. стоит проверить, не ухудшает ли ранжирование ответ по сравнению с более простыми правилами: голосованием, точной проверкой или случайным выбором среди прошедших фильтр.

Нельзя называть 0.98 точностью всей системы, потому что пользователь получает один выбранный ответ, а не множество из 32 кандидатов.

Нет. Независимые выборки из распределения с низкой энтропией могут повторять одну ошибку. Расхождение также объясняют малая вероятность успеха на данном запросе, неточная оценка $p$ или объединение запросов с разными $p$. Переиспользование префиксов и ветвей поиска — возможные механизмы зависимости, которые нужно установить по протоколу. Сравните покрытие по повторным группам с условно независимым прогнозом для каждого запроса и его неопределённостью.

Полезные диагностики:

• число уникальных канонических финальных ответов;
• средняя попарная текстовая или семантическая близость;
• энтропия распределения канонических ответов;
• доля крупнейшего кластера;
• различие между фактической кривой pass@N и кривой, предсказанной по pass@1 в независимой модели.

Одна метрика разнообразия недостаточна: разные формулировки могут скрывать одну и ту же ошибку, а почти одинаковые рассуждения иногда приводят к разным итоговым ответам.

При большом числе независимо сгенерированных кандидатов доли канонических ответов сходятся к их вероятностям. Типовая ошибка с вероятностью 0.44 является единственной модой, поэтому голосование по относительному большинству с вероятностью, стремящейся к единице, выберет именно её. Точность голосования стремится к нулю.

Одновременно pass@N может стремиться к единице, потому что правильный ответ имеет положительную вероятность 0.32:

Это точная демонстрация различия между наличием правильного кандидата и правилом выбора. Голосование помогает, когда правильный канонический ответ является наиболее вероятной категорией, а ошибки достаточно рассеяны.

В учебном протоколе каждый кандидат либо принят, либо отклонён. Если принятые кандидаты выбираются равновероятно, при большом $N$ вероятность отсутствия принятых стремится к нулю, а качество выбранного ответа стремится к доле правильных среди принятых.

Ранжировщик с непрерывным баллом реализует другой статистический объект: выбирается максимум из $N$ шумных оценок. При росте $N$ экстремальное значение может всё сильнее определяться положительной ошибкой оценивателя. Предел зависит от совместного распределения истинного качества и оценки, хвостов ошибок, числа кандидатов и правила разрешения ничьих. Формула для случайного выбора среди двоично принятых кандидатов к такому максимуму не относится.

Возможные объяснения:

1. Переоптимизация прокси: большой пул увеличивает шанс найти ответ, использующий систематическую ошибку модели награды.

2. Сдвиг распределения: ответы-победители при $N=512$ находятся дальше от данных, на которых оцениватель был обучен и проверен.

3. Изменение длины или стиля: модель награды может предпочитать признаки, слабо связанные с полезностью.

4. Шум ручной оценки: падение может быть случайным, если независимая выборка мала.

Изменения протокола:

• заранее выделить независимый набор запросов и независимый оцениватель;
• строить кривые прокси и целевой метрики на одной сетке $N$ с доверительными интервалами;
• анализировать длину, стиль, домен, уверенность и расхождение ансамбля оценивателей;
• проводить слепую ручную проверку выбранных ответов и случайных кандидатов;
• задавать условие остановки по независимой метрике, а не по прокси;
• обновлять данные оценивателя ответами из нового распределения.

Рост прокси сам по себе доказывает лишь то, что система научилась находить кандидаты с более высокой прокси-оценкой.

Метка оценивала эмпирическую вероятность финального успеха при продолжении конкретной версией политики, конкретном декодировании, горизонте и проверяющей системе:

Это оценка ценности относительно заданной политики продолжения, а не вечное свойство префикса и не «истинная ценность» вне постановки. После изменения политики распределение продолжений меняется; меняются и вероятность успеха, и ошибки Монте-Карло. Метка может устареть, особенно для состояний, в которых новая политика ведёт себя иначе.

Нужно хранить версию политики, параметры декодирования, число продолжений, проверяющую систему и дату генерации меток.

Нужно сравнить методы как минимум при нескольких паритетах:

1. одинаковое число сгенерированных токенов;

2. одинаковое число прямых проходов генератора;

3. одинаковое число вызовов PRM или другой проверки;

4. одинаковая задержка или денежная стоимость;

5. одинаковый максимальный контекст и правила остановки.

Следует измерять pass@1, pass@k/покрытие, качество выбранного ответа, долю технических ошибок, токены, задержку и стоимость. Нужны также сильные простые контрольные варианты: повторная генерация, BoN, самосогласованность и последовательное исправление.

MCTS может быть предпочтительнее при заданном ограничении качества или задержки, но утверждение «лучше вообще» без выбранного бюджета и метрики не определено.

При $p=0.35$:

Прирост именно от шестой попытки:

То есть шестой кандидат добавляет примерно 4.06 процентного пункта покрытия. Без правила выбора из этого не следует, что система выдаёт правильный ответ с вероятностью 0.9246: это вероятность наличия хотя бы одного успеха в корзине.

С четырьмя знаками:

Здесь мысленно выбираются 10 элементов без возвращения из уже сгенерированной сотни. Оцениватель не доказывает независимость исходных 100 генераций и не заменяет описание протокола генерации.

Вероятность принятия:

Точность среди принятых:

Условная доля правильных среди отклонённых:

Вероятность, что все шесть отклонены:

Если резерв выбирается из той же отклонённой корзины,

Если создаётся свежий непроверенный кандидат,

При $q>0$ вероятность пустого множества принятых стремится к нулю, поэтому оба протокола имеют один предел:

Различие при конечном $N$ принципиально: наблюдение «кандидат отклонён» меняет вероятность его правильности. Слагаемое $p$ допустимо только для новой независимой попытки, а не для выбора среди уже отклонённых.

В первом распределении правильный ответ имеет вероятность 0.34, а ближайшая ошибка — 0.33. Правильный ответ является единственной модой. По закону больших чисел его эмпирическая доля в пределе превосходит доли остальных категорий, поэтому

Сходимость может быть медленной из-за малого разрыва 0.01.

Во втором распределении неправильный второй ответ имеет вероятность 0.40, превышающую 0.30 правильного. Поэтому

При этом pass@N для правильного ответа во втором случае всё равно стремится к единице, поскольку его вероятность положительна.

Для $(0.9,0.7,0.8)$:

После добавления десяти шагов с оценкой 0.9 произведение станет

Хотя все добавленные шаги имеют высокий балл, произведение уменьшается. Это корректно только при вероятностной семантике совместного события; иначе получается неявный штраф за длину.

Начинаем с $(1,1,1)$. Предельный прирост для запроса $i$ при текущем числе попыток $n_i$ равен

Последовательное жадное распределение шести дополнительных попыток даёт

Среднее покрытие:

Точка окупаемости по стоимости решает

Отсюда

Это расчёт только денежных затрат. В реальном решении нужно добавить качество, задержку, риск и стоимость внедрения.

from __future__ import annotations

from collections.abc import Iterable, Sequence
import math
import numpy as np


def pass_at_n(p: float, n: int) -> float:
    p = float(p)
    if not math.isfinite(p) or not 0.0 <= p <= 1.0:
        raise ValueError("p must lie in [0, 1]")
    if isinstance(n, bool) or int(n) != n or int(n) <= 0:
        raise ValueError("n must be a positive integer")
    n = int(n)
    if p == 0.0:
        return 0.0
    if p == 1.0:
        return 1.0
    return float(-np.expm1(n * np.log1p(-p)))


def aggregate_pass_curve(ps: Sequence[float], budgets: Iterable[int]) -> np.ndarray:
    probabilities = np.asarray(ps, dtype=np.float64)
    budgets = list(budgets)
    if probabilities.ndim != 1 or probabilities.size == 0:
        raise ValueError("ps must be non-empty")
    if not np.isfinite(probabilities).all() or np.any((probabilities < 0) | (probabilities > 1)):
        raise ValueError("every probability must lie in [0, 1]")
    if not budgets:
        raise ValueError("budgets must be non-empty")
    return np.asarray(
        [np.mean([pass_at_n(float(p), int(n)) for p in probabilities]) for n in budgets],
        dtype=np.float64,
    )

log1p и expm1 уменьшают потерю точности, когда $p$ мал, а $N$ велик.

from __future__ import annotations
from collections.abc import Sequence
import numpy as np


def plurality_accuracy_mc(
    probabilities: Sequence[float],
    k: int,
    *,
    correct_index: int = 0,
    trials: int = 100_000,
    seed: int = 10,
) -> float:
    p = np.asarray(probabilities, dtype=np.float64)
    if p.ndim != 1 or p.size < 2:
        raise ValueError("at least two categories are required")
    if not np.isfinite(p).all() or np.any(p < 0) or not np.isclose(p.sum(), 1.0):
        raise ValueError("probabilities must form a distribution")
    if isinstance(k, bool) or int(k) != k or int(k) <= 0:
        raise ValueError("k must be a positive integer")
    if isinstance(trials, bool) or int(trials) != trials or int(trials) <= 0:
        raise ValueError("trials must be a positive integer")
    if not 0 <= int(correct_index) < p.size:
        raise ValueError("correct_index is out of range")

    rng = np.random.default_rng(seed)
    counts = rng.multinomial(int(k), p, size=int(trials))
    correct = 0
    for row in counts:
        winners = np.flatnonzero(row == row.max())
        selected = int(rng.choice(winners))
        correct += selected == int(correct_index)
    return correct / int(trials)

np.argmax возвращает первый максимальный индекс. Если правильный ответ хранится под индексом 0, все ничьи искусственно повышают измеренную точность; при другом индексе — понижают. Это свойство представления массива, а не протокола голосования.

from __future__ import annotations
import math


def binary_verifier_success(
    n: int,
    p_correct: float,
    true_positive_rate: float,
    false_positive_rate: float,
    *,
    fallback_mode: str = "rejected_pool",
) -> dict[str, float]:
    if isinstance(n, bool) or int(n) != n or int(n) <= 0:
        raise ValueError("n must be a positive integer")
    values = [float(p_correct), float(true_positive_rate), float(false_positive_rate)]
    if any((not math.isfinite(v)) or not 0.0 <= v <= 1.0 for v in values):
        raise ValueError("probabilities must lie in [0, 1]")
    if fallback_mode not in {"rejected_pool", "fresh_unverified"}:
        raise ValueError("unknown fallback mode")

    p, tpr, fpr = values
    q = p * tpr + (1.0 - p) * fpr
    accepted_precision = p if q == 0.0 else p * tpr / q
    rejected_precision = p if q == 1.0 else p * (1.0 - tpr) / (1.0 - q)
    no_accept = (1.0 - q) ** int(n)
    fallback = rejected_precision if fallback_mode == "rejected_pool" else p
    success = (1.0 - no_accept) * accepted_precision + no_accept * fallback
    return {
        "q": q,
        "accepted_precision": accepted_precision,
        "rejected_precision": rejected_precision,
        "no_accept": no_accept,
        "fallback_success": fallback,
        "success": success,
    }

Ветвь q == 1 нужна, потому что условное распределение отклонённых тогда не определено, но событие резервного выбора имеет нулевую вероятность. Возвращаемое условное значение не влияет на success.

from __future__ import annotations

from collections.abc import Sequence
import numpy as np


def process_score(step_scores: Sequence[float], method: str) -> float:
    values = np.asarray(step_scores, dtype=np.float64)
    if values.ndim != 1 or values.size == 0:
        raise ValueError("step_scores must be non-empty")
    if not np.isfinite(values).all() or np.any((values < 0) | (values > 1)):
        raise ValueError("step scores must lie in [0, 1]")
    method = method.lower()
    if method == "min":
        return float(values.min())
    if method == "mean":
        return float(values.mean())
    if method == "product":
        return float(values.prod())
    if method == "last":
        return float(values[-1])
    if method == "log_product":
        if np.any(values == 0):
            return float("-inf")
        return float(np.log(values).sum())
    raise ValueError("unknown aggregation method")

Логарифм произведения численно устойчивее для длинных цепочек. Он не исправляет семантическую проблему: перемножать оценки можно осмысленно лишь при подходящей вероятностной интерпретации.

from __future__ import annotations

from collections.abc import Sequence
import numpy as np


def proxy_overoptimization_curve(
    budgets: Sequence[int],
    *,
    trials: int = 10_000,
    seed: int = 202_610,
) -> tuple[np.ndarray, np.ndarray]:
    budgets = np.asarray(budgets, dtype=np.int64)
    if budgets.ndim != 1 or budgets.size == 0 or np.any(budgets <= 0):
        raise ValueError("budgets must be positive integers")
    if trials <= 0:
        raise ValueError("trials must be positive")
    rng = np.random.default_rng(seed)
    maximum = int(budgets.max())
    useful = rng.normal(size=(trials, maximum))
    spurious = rng.normal(size=(trials, maximum))
    proxy = useful + spurious
    goal = useful - np.maximum(spurious - 1.0, 0.0) ** 2
    rows = np.arange(trials)
    proxy_means = []
    goal_means = []
    for n in budgets:
        selected = np.argmax(proxy[:, : int(n)], axis=1)
        proxy_means.append(proxy[rows, selected].mean())
        goal_means.append(goal[rows, selected].mean())
    return np.asarray(proxy_means), np.asarray(goal_means)

Этот эталон использует общий пул кандидатов, поэтому выбранный максимум прокси не убывает при расширении префикса в каждом испытании. Для независимых пулов монотонность относится к ожиданию, а отдельные выборочные средние могут колебаться. В опубликованном протоколе этого эталона (trials=10000, seed=202610, указанная сетка) максимум независимой цели наблюдается при $N=32$; другой допустимый порядок выборки может дать иной максимум. Открытые проверки проверяют форму, конечность, воспроизводимость и учёт параметра seed. Формулу цели и выбор кандидата дополнительно сверяйте по нескольким вручную рассчитанным пулам; сами эти проверки не доказывают правильность алгоритма.

from __future__ import annotations

from collections.abc import Sequence
import numpy as np


def allocate_budget_greedy(
    ps: Sequence[float],
    total_samples: int,
    *,
    minimum_per_prompt: int = 1,
) -> np.ndarray:
    p = np.asarray(ps, dtype=np.float64)
    if p.ndim != 1 or p.size == 0:
        raise ValueError("ps must be non-empty")
    if not np.isfinite(p).all() or np.any((p < 0) | (p > 1)):
        raise ValueError("probabilities must lie in [0, 1]")
    if minimum_per_prompt < 0 or int(minimum_per_prompt) != minimum_per_prompt:
        raise ValueError("minimum_per_prompt must be a non-negative integer")
    minimum = int(minimum_per_prompt)
    if total_samples < minimum * p.size:
        raise ValueError("budget is smaller than the required minimum")
    allocation = np.full(p.size, minimum, dtype=np.int64)
    for _ in range(int(total_samples) - minimum * p.size):
        gains = p * np.power(1.0 - p, allocation)
        allocation[int(np.argmax(gains))] += 1
    return allocation

Для независимых кривых $1-(1-p_i)^{n_i}$ предельные приросты невозрастают, поэтому последовательный выбор крупнейшего доступного прироста оптимален для дискретного бюджета. Реальная LLM-система может нарушать предположения: вероятность успеха неизвестна, кандидаты коррелированы, стоимость попыток неодинакова, а правило выбора несовершенно.