LLM учит планировщик обходиться полиномиальной памятью и решает 1709 из 1890 задач

Классические планировщики упираются в память раньше, чем во время. Эвристический поиск хранит список посещённых состояний, и тот растёт экспоненциально, даже когда эвристика почти идеальна. Авторы новой работы на arXiv предлагают обойтись без этого списка. С политиками, которые написала языковая модель, их процедура решила 1709 из 1890 тестовых задач IPC 2023 Learning Track и набора Autoscale Agile. Это больше, чем у LAMA, BFWS и Levitron, причём большинство задач уложилось в секунду и 100 МиБ.

Политика с регистрами вместо списка состояний

Вместо универсального поиска авторы учат управление поиском. Для каждого домена пишется одна спецификация в виде «индексальной политики». Это обобщённая политика с регистрами, в которых лежат объекты, и режимами, задающими порядок применения правил. Ключевое дополнение — правило choose. Оно загружает объект в регистр и ставит точку возврата, причём достаточно одного подходящего кандидата. Все остальные правила обязаны работать при любом исходе, и поиска им не требуется.

Главный результат работы теоретический. Структурное завершение исключает бесконечные исполнения политики. Авторы показывают, что оно же ограничивает любое исполнение полиномом от числа объектов. Отсюда следует, что поиск в глубину находит план в полиномиальной памяти, какого бы размера ни было пространство состояний, и список посещённых состояний не нужен. Расплата идёт временем. Оно экспоненциально только по глубине выбора, то есть по числу настоящих choice вдоль исполнения. Поэтому любой класс задач, который решает такая политика, лежит в NP, а при константной глубине выбора лежит в P.

Где здесь языковая модель

Политики не пишут вручную. Их генерирует языковая модель в цикле с контрпримерами. На каждом круге цикл сертифицирует завершение, проверяет политику на обучающих задачах и следит, чтобы глубина выбора оставалась малой. Последнее условие важно, потому что именно она определяет, сколько времени съест перебор. В аннотации не названо, какая именно модель использовалась.

Цифры из аннотации

• Решено 1709 из 1890 тестовых задач (около 90%), 181 задача осталась нерешённой.
• Бенчмарки: IPC 2023 Learning Track и Autoscale Agile.
• Конкуренты LAMA, BFWS и Levitron решили меньше.
• Большинство задач решено быстрее секунды и в пределах 100 МиБ.
• Память полиномиальная, без списка посещённых состояний.
• Время экспоненциально только по глубине выбора.
• Классы задач, решаемые такими политиками, лежат в NP, а при константной глубине выбора в P.

Где это может пригодиться

Сильнее всего подход выглядит там, где память дороже процессорного времени: у встроенных планировщиков, роботов и систем, которые решают однотипные задачи на разных входах. Есть и практическая находка в разделении труда. Языковая модель пишет проверяемую программу-политику, и сертификат завершения даёт гарантию, которой нет у плана, выданного моделью напрямую. Ограничения тоже понятны. Политика нужна под каждый домен, обучение требует набора тренировочных задач, а цифры получены самими авторами на препринте без независимой проверки. Но такой гибрид уже даёт ощутимый выигрыш по памяти на стандартных бенчмарках планирования.