# Стэнфордский курс CS221: как классический поиск масштабирует современные языковые модели Источник: https://www.youtube.com/watch?v=fPESauMaJYA Канал: Stanford Online Опубликовано: 09.03.2026 --- В лекции Стэнфордского университета по курсу CS221 рассматривается фундаментальная концепция поиска как формы логического мышления в детерминированном мире. Лектор объясняет, почему в эпоху доминирования глубокого обучения классический поиск не только сохраняет актуальность, но и становится ключевым элементом современных ИИ-систем благодаря синергии с обучением. В материале подробно разбираются как точные методы (исчерпывающий поиск и динамическое программирование), так и приближенные подходы (алгоритм Best-of-N и лучевой поиск), включая их применение для масштабирования вычислений на этапе тестирования языковых моделей. ## 🧠 От рефлексов к рассуждениям: почему поиск важен в эпоху ИИ [[JUMP:0:05]] Современное машинное обучение во многом опирается на рефлекторные механизмы, преобразующие входные данные в выходные. В задачах регрессии результатом становится число, а в задачах классификации — одна из заданных категорий. Даже глубокие нейронные сети по своей сути представляют собой модели прямого распространения, которые работают быстро и реактивно, выполняя прямое отображение восприятия на действие. Однако многие реальные вызовы — от сложных математических задач до программирования — требуют полноценного логического мышления, планирования и решения проблем. Поиск выступает ключевой формой такого мышления в условиях, когда окружающий мир детерминирован. В 2025 году может возникнуть резонный вопрос: зачем возвращаться к концепциям символического ИИ 1950-х годов, если они когда-то не оправдали надежд? Ответ кроется в знаменитом эссе Ричарда Саттона «Горький урок» (The Bitter Lesson). По мнению Саттона, общие методы, эффективно использующие вычисления, в конечном счете оказываются наиболее успешными с огромным отрывом. Саттон утверждает, что лишь два метода способны масштабироваться произвольно за счет роста вычислительных мощностей: поиск и обучение. Современный ИИ научился отлично справляться с обучением, но объединение мощных моделей с алгоритмами поиска открывает принципиально новые возможности для решения сложнейших задач. ## 🛠️ Формализация задачи поиска: анатомия абстракции [[JUMP:5:15]] Чтобы алгоритмы могли оперировать абстрактными концепциями, естественное описание проблемы необходимо перевести в строгий программный код. В качестве базового примера лектор предлагает задачу перемещения по улице с блоками от 1 до $n$. Пеший переход между соседними блоками занимает 1 минуту, а поездка на воображаемом трамвае удваивает текущий номер блока и длится 2 минуты. Цель — найти маршрут с минимальными временными затратами. Стандартная математическая формализация задачи поиска включает в себя фиксированный набор компонентов: * Начальное состояние (start state), определяющее отправную точку системы. * Функция преемников (successors), возвращающая список возможных шагов. Каждый шаг состоит из метки действия, стоимости (времени) и результирующего следующего состояния. * Функция завершения (is end), проверяющая, достигнута ли конечная цель поиска. По мере усложнения условий — например, при введении лимита на количество билетов для трамвая — структура состояния усложняется. Состояние перестает быть простым числом и становится композитным объектом, хранящим текущую локацию и остаток билетов. Как подчеркивает преподаватель, состояние должно содержать строго ту информацию, которая необходима для корректной оценки будущих действий, затрат и преемников. Включение избыточных данных, таких как вся история перемещений, чревато экспоненциальным ростом пространства состояний, что сделает алгоритмы оптимизации крайне медленными. ## 🔍 Точные методы: исчерпывающий поиск и его ограничения [[JUMP:20:37]] Основная цель любого алгоритма поиска — найти последовательность действий, минимизирующую общую стоимость. Простейший подход заключается в исчерпывающем (полном) переборе всех возможных вариантов. Для перехода к более сложным концепциям лектор вводит понятие «будущей стоимости» (future cost) — функции, определяющей минимальные затраты на путь от текущего состояния до финала. Расчет базируется на рекуррентном соотношении: будущая стоимость текущего узла равна минимуму из сумм немедленной стоимости действия и будущей стоимости следующего узла. Несмотря на концептуальную простоту, исчерпывающий поиск имеет серьезные недостатки: * Временная сложность в худшем случае растет экспоненциально, что делает его неприменимым для длинных маршрутов. * Память расходуется линейно относительно длины решения, поскольку стек рекурсии хранит лишь текущий путь. * Наличие циклов в графе состояний приводит к бесконечному зацикливанию алгоритма. Для предотвращения бесконечных циклов разработчики используют специальные инженерные приемы. Лектор предлагает интегрировать счетчик шагов непосредственно в состояние, что заставляет систему двигаться исключительно вперед во времени. При превышении заданного порога шагов функция завершения объявляет состояние конечным, а система присваивает ему бесконечную стоимость, исключая неэффективный путь из итогового выбора. ## 💾 Динамическое программирование: исчерпывающий поиск плюс кэширование [[JUMP:38:24]] Для кардинального повышения эффективности перебора применяется динамическое программирование — метод, предложенный Ричардом Беллманом в 1950-х годах. Под термином «динамическое» понимается процесс принятия последовательных решений во времени, а под «программированием» — математическая оптимизация. В контексте алгоритмов лектор формулирует этот подход максимально просто: исчерпывающий поиск плюс кэширование (или мемоизация). Интеграция кэша в стандартный алгоритм перебора требует минимальных изменений в коде: * Инициализируется структура данных для хранения уже вычисленных решений для каждого состояния. * В начале рекурсивной функции добавляется проверка: если состояние уже есть в кэше, алгоритм мгновенно возвращает готовый ответ. * После нахождения оптимального пути для нового состояния результат записывается в кэш перед возвратом. Динамическое программирование обеспечивает экспоненциальное ускорение, снижая временную сложность до линейной или квадратичной. Однако лектор напоминает важное правило компьютерной жизни: память часто оказывается более дефицитным ресурсом, чем время. Кэширование требует сохранения всех уникальных состояний, и если их количество исчисляется триллионами, алгоритм исчерпает доступную оперативную память. Кроме того, мемоизация эффективна только тогда, когда в графе существует множество альтернативных путей, ведущих в одни и те же узлы (решетчатая структура). Если каждый путь уникален (древовидная структура), кэш будет постоянно фиксировать промахи, лишая алгоритм преимуществ. ## 🎲 Приближенный поиск: алгоритмы Best-of-N и лучевой поиск [[JUMP:50:51]] Когда пространство состояний становится бесконечным или слишком огромным (например, при генерации текстовых последовательностей), точный поиск становится невозможным. В таких сценариях инженеры жертвуют гарантиями идеального результата в пользу эвристических методов приближенного поиска. Лектор детально разбирает два популярных алгоритма: Best-of-N и лучевой поиск (Beam Search). Метод Best-of-N устроен предельно просто: система совершает $N$ независимых случайных запусков (роллаутов) от старта до финиша, руководствуясь заданной стратегией (политикой), после чего выбирает вариант с наименьшей стоимостью. Под политикой понимается функция, отображающая состояние на доступное действие. При росте $N$ до бесконечности алгоритм гарантированно сходится к точному оптимуму. Огромным преимуществом Best-of-N является его идеальная параллелизуемость (embarrassingly parallel): вычисления можно распределить по тысячам изолированных машин, не требуя от них коммуникации друг с другом в процессе работы. Лучевой поиск предлагает другую стратегию и работает по строго детерминированному принципу. Алгоритм вводит фиксированный параметр — ширину луча (beam width). Процесс развивается пошагово: * Из текущих промежуточных траекторий генерируются все возможные продолжения. * Для каждого нового варианта рассчитывается его суммарная стоимость. * Все кандидаты сортируются, и алгоритм оставляет строго заданное количество лучших путей (равное ширине луча), безжалостно отсекая остальные. Если ширина луча равна единице, алгоритм превращается в обычный жадный поиск. Если же ширину устремить к бесконечности, лучевой поиск трансформируется в исчерпывающий перебор. Оптимальным значением для текстовых задач в современных системах лектор называет порядок 10 кандидатов. ## 🤖 Поиск в языковых моделях: вычисления на этапе тестирования [[JUMP:1:11:37]] Применение классического поиска к современным большим языковым моделям породило концепцию вычислений на этапе тестирования (test-time compute), ставшую широко известной благодаря линейке моделей OpenAI o1. С точки зрения математики, большая языковая модель представляет собой сложный многоклассовый вероятностный классификатор, принимающий на вход подсказку (промпт) и выдающий распределение вероятностей для следующего токена. Чтобы превратить генерацию текста в строгую задачу поиска, лектор описывает следующую схему трансформации: * Состояние: строка, объединяющая исходный промпт и уже сгенерированный к настоящему моменту префикс ответа. * Действие: предсказание конкретного следующего токена. * Стоимость действия: отрицательное логарифмическое правдоподобие (negative log probability) токена, что эквивалентно максимизации его вероятности. * Проверка качества: интеграция внешнего верификатора, который начисляет огромный бонус (срезает 100 единиц стоимости) в случае успешного решения математического или программного условия. В качестве демонстрации преподаватель приводит пример локального запуска сверхмалой модели Qwen-3 с 0,6 млрд параметров на обычном ноутбуке. Модели предлагается решить арифметическое выражение `3 + 7 * 2`. Используя метод Best-of-N, система генерирует независимые цепочки токенов, отбирая те, которые формируют математически корректный ответ. Исследования подтверждают, что интенсивное использование вычислений на этапе генерации позволяет компактным моделям успешно конкурировать по качеству результатов с гораздо более массивными нейросетями. Сочетание глубокого обучения, задающего базовые стоимости, и алгоритмов поиска, находящих глобально оптимальные траектории, лектор называет главным вектором развития устойчивых систем искусственного интеллекта.