В этой статье представлен теоретический анализ поиска в контексте, моделируемого как приближённый вывод по цепочкам рассуждений, где базовая модель задаёт априорное распределение, а самоанализ обеспечивает обратную связь для обновления апостериорного распределения. Авторы исследуют вычислительную сложность выборки на этапе вывода, определяемую как количество последовательных попыток, необходимых для достижения высокой вероятности успеха.
- Когда рефлексия надёжно локализует ранние ошибки, поиск в контексте даёт экспоненциальное улучшение по сравнению с базовой моделью, решая задачи с экспоненциально малой долей успешных ответов при нулевом количестве примеров (zero-shot) всего за полиномиальное число последовательных попыток.
- Если это свойство нарушается, условная вероятность на основе прошлых попыток не даёт асимптотического преимущества перед параллельной выборкой.
- Эти преимущества устойчивы и обучаемы: достаточно приближённых обновлений апостериорного распределения, а обучение перекрёстной энтропией на rollout поиска восстанавливает требуемое поведение с полиномиальной сложностью по выборке.
- При ступенчатой абстракции обучения с подкреплением (reinforcement learning) с верифицируемыми наградами оптимальное расширение политики реализует то же правило переобвешивания апостериорного распределения.
Авторы проверяют ключевые качественные предсказания теории на реальных больших моделях рассуждений.