Теория итеративного поиска в нейросетях: когда самокоррекция дает экспоненциальный выигрыш

Исследователи разработали теоретическую основу для анализа in-context search — механизма, позволяющего большим языковым моделям (LLM) итеративно улучшать свои ответы через этапы генерации, критики и исправления. Работа выложена на arXiv и предлагает строгую математическую модель этого процесса.

Авторы рассматривают in-context search как приближённый вероятностный вывод по траекториям рассуждений: базовая модель задаёт априорное распределение, а самокоррекция обеспечивает обновление апостериорных вероятностей. Ключевой метрикой становится вычислительная сложность на этапе инференса — количество последовательных попыток, необходимых для достижения высокой вероятности успеха.

Результаты показывают, что если самокоррекция надёжно локализует ранние ошибки, то in-context search даёт экспоненциальное преимущество по сравнению с базовой моделью. При этом задачи с экспоненциально малой вероятностью успеха при однократной попытке решаются за полиномиальное число шагов. Если же это свойство не выполняется, последовательные попытки не дают асимптотического выигрыша по сравнению с параллельным запуском.

Дополнительные эксперименты подтверждают, что эти преимущества устойчивы и обучаемы: достаточно приближённой апостериорной коррекции, а обучение с перекрёстной энтропией на rollouts поиска восстанавливает нужное поведение с полиномиальной сложностью выборки.

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

Работа вносит вклад в понимание того, почему итеративное уточнение (chain-of-thought, самокоррекция) эффективно в одних сценариях и бесполезно в других. Это может помочь разработчикам выбирать стратегию инференса в зависимости от свойств задачи.