Материал подготовлен автоматически по первоисточникам: ссылки на них — в конце статьи.
Небольшую нейросеть научили улучшать решения комбинаторных задач, повторяя одни и те же слои и направляя дополнительные вычисления на более сложные примеры. В препринте, который не рецензирован и где все числа получены самими авторами, TRM4CO построила маршрут с разрывом 0,11% от эталона. Такой подход позволяет менять качество на время расчёта без обучения более крупной модели.
Как одна сеть превращает время расчёта в качество
Zhengxi Zhang и Paul Swoboda из Heinrich Heine University Düsseldorf построили TRM4CO на основе Tiny Recursive Model. Ядро состоит из двух блоков трансформера примерно с 7 млн параметров. Эти блоки многократно применяют к одному экземпляру задачи, поэтому вычислительная глубина растёт, а число обучаемых параметров остаётся прежним.
Кодировщик сначала превращает вершины графа или города в последовательность признаков. Для задачи максимального независимого множества матрица смежности меняет веса внимания: каждая его головка сама учится смотреть на соседей, несвязанные вершины или весь граф. В задаче коммивояжёра сеть получает координаты городов с синусоидальными признаками, которые помогают различать близкие расстояния.
Внутри ядра живут два состояния. Скрытое состояние хранит промежуточные рассуждения, а состояние ответа постепенно приближается к решению. После каждого шага выходной слой читает текущее состояние, декодер строит допустимый маршрут или множество вершин, а целевая функция оценивает результат.
Глубина задаёт число последовательных шагов. Во время обучения пример прекращает вычисления, когда декодированный ответ достигает обучающей метки: простые задачи освобождают место в пакете, а сложные получают больше шагов. На рабочем запуске глубину задают явно, поэтому адаптивная остановка здесь помогает обучению, но не управляет задержкой готового сервиса.
Второе направление масштабирования — параллельные прогоны. Модель добавляет случайный шум в скрытое состояние, получает разные кандидаты и выбирает лучший по точной целевой функции. Стоимость растёт пропорционально произведению глубины и числа прогонов: команда может заранее выбрать бюджет для быстрого ответа или более тщательного поиска.
Декодер и самопереразметка доводят ответ до решения
Сеть не выдаёт готовое решение напрямую. Для независимого множества она оценивает вершины, после чего жадный декодер добавляет их по очереди и отбрасывает конфликтующие. Затем алгоритм фиксирует часть выбранных вершин и снова запускает рекурсию на оставшемся графе. Для коммивояжёра декодер вставляет рёбра с лучшими оценками, соблюдает ограничения маршрута и в конце применяет локальное улучшение 2-opt.
Такое разделение важно: общее ядро учится оценивать варианты, а небольшой предметный декодер гарантирует допустимость ответа. Одна архитектура работает для обеих задач, но кодировщики, правила остановки и сборщики решений остаются специализированными. TRM4CO поэтому служит шаблоном для нового решателя, а не готовой заменой предметному алгоритму.
На маршрутах по 500 городам разрыв с эталоном составил 0,11% при времени 2,1 секунды на экземпляр. Разрыв показывает, насколько найденный маршрут длиннее результата классического решателя. На основном наборе Erdős–Rényi модель достигла разрыва 1,11% относительно KaMIS.
Самопереразметка периодически прогоняет модель по обучающему набору и заменяет метку, если найдено строго лучшее решение. Метки могут только улучшаться, поэтому цикл напоминает восхождение по качеству: решить задачи, сохранить лучшие ответы, дообучиться и повторить. При старте без внешнего решателя собственные метки модели сравнялись с KaMIS или превзошли его на 42% обучающих графов, хотя для задачи коммивояжёра обучение по эталонным маршрутам осталось заметно точнее.
Когда подход меняет архитектурный план
TRM4CO имеет смысл рассматривать, если продукт решает задачи с дешёвой и однозначной проверкой кандидата: маршрутизацию, расписания, упаковку или выбор совместимых объектов. Тогда компактная сеть может порождать варианты, предметный декодер — обеспечивать ограничения, а точная целевая функция — выбирать лучший ответ без отдельной модели-оценщика.
В архитектуре стоит отделить размер модели от бюджета поиска. Вместо нескольких моделей для разных уровней качества можно обучить одно ядро и менять глубину с числом параллельных прогонов. Такой вариант особенно полезен, когда допустима переменная задержка: фоновая задача получает больше вычислений, а интерактивный запрос останавливается раньше.
Проверка охватила маршруты от 500 до 10 000 городов, графы Erdős–Rényi с 700–800 вершинами и набор SATLIB. Время нейросетевых методов измеряли на одной RTX 4090, а качество сравнивали с другими обучаемыми подходами и классическими решателями. Результаты показывают перенос общего ядра между двумя задачами, но не снимают необходимость проектировать кодировщик и декодер под каждую новую систему ограничений.
Практический вывод состоит не в том, чтобы заменить комбинаторный поиск нейросетью целиком. Работа предлагает разделить его на повторно используемое обучаемое ядро, проверяемый декодер и регулируемый вычислительный бюджет. Перед внедрением такой системы нужно строить кривую «качество — задержка» на собственных данных: один результат с максимальным бюджетом не показывает, подойдёт ли решатель для рабочего ограничения по времени.
Источники
Похоже на вашу задачу?
Расскажите, что собираете. За полчаса разложим на этапы и назовём сроки — это бесплатно и ни к чему не обязывает.
