Материал подготовлен автоматически по первоисточникам: ссылки на них — в конце статьи.
CoCo-Prover строит машинно проверяемые доказательства для программ с меньшими расходами на LLM. В препринте Shuangjie Yao и коллег, который не прошёл рецензирование и опирается на собственные замеры авторов, система снизила стоимость до 30,9% относительно Humanize на GPT-5.6-Terra. Для команд формальной верификации это сдвигает задачу от выбора одной модели к управлению стоимостью каждого шага.
Граф показывает, где дорогой вызов окупится
Обычный агент доказательства получает цель, генерирует код Lean, проверяет его и повторяет попытки до успеха или исчерпания бюджета. Такой цикл одинаково тратит вычисления на рутинные условия, сложные индукции и неверно выбранные пути.
CoCo-Prover хранит состояние доказательства в двух связанных графах. Внутри каждой декларации граф отмечает альтернативные шаги, полученные подцели и уже проверенные переходы. Второй граф связывает целевые теоремы и вспомогательные леммы, чтобы система видела зависимости между декларациями.
Планировщик без вызова модели выбирает цели, для которых уже готовы зависимости. Затем маршрутизатор группирует близкие цели и решает, какое действие купить: применить автоматику, написать доказательство, выделить общую лемму или пересмотреть неудачный путь. Он также задаёт глубину рассуждения и предел итераций.
За действия отвечают специализированные агенты:
- Детерминированная автоматика запускает правила и тактики Lean без обращения к LLM.
- Автор доказательства пишет код Lean и исправляет его по сообщениям проверяющей системы. Если бюджет закончился, успешно построенная часть остаётся в графе.
- Планировщик лемм предлагает типизированный вспомогательный факт и указывает, какие цели смогут его использовать. Лемма попадает в граф после проверки типов, отсутствия циклической зависимости и поиска контрпримеров.
- Рецензент восстановления различает ложную цель и неудачный путь к доказуемой цели. При откате он удаляет только работу, которая зависит от ошибочного шага.
Маршрутизатор начинает с правила «при равных шансах сначала дешёвое», но учитывает стоимость всей оставшейся задачи. Поэтому дорогая общая лемма может оказаться выгоднее нескольких прямых доказательств. После каждой попытки маршрутизатор получает диагностику Lean, контрпримеры и журнал расходов, а затем может изменить правила выбора.
Окончательное решение о корректности принимает Lean. Модели выбирают путь и предлагают код, но граф записывает только переходы, которые приняла проверяющая система.
Экономия проявилась и на отдельных функциях, и на репозиториях
CoCo-Prover проверяли на пяти наборах задач программной верификации в Lean 4: CLEVER, VERINA и AlgoVeri на уровне функций, NTP4VC и Vero на уровне репозиториев. В качестве основы использовали три LLM, а соперниками выступали официальные агенты программирования этих моделей и специализированные системы доказательства. Для сравнений задавали одинаковые пределы расходов.
Ни один соперник не превысил долю решённых задач CoCo-Prover ни на одном сочетании набора и базовой модели. На двух функциональных наборах система дошла до 100%, а на крупном репозиторном Vero решила 60,5% задач. Стоимость считали в деньгах по тарифам моделей, поэтому в неё вошли разные цены входных, кешированных и выходных токенов.
Результат объясняет не только выбор более дешёвой модели. Система экономит на структуре работы: закрывает простые цели без LLM, не пересылает бесконечно растущий контекст, сохраняет частичный прогресс и повторно использует доказанные факты.
Когда оркестрация оправдывает отдельный слой
Работа меняет планы команд, которые проверяют сгенерированный код или поддерживают репозиторий со связанными обязательствами доказательства. В такой системе бюджет стоит закреплять не за теоремой целиком, а за отдельными действиями. Для этого потребуются явный граф зависимостей, журнал фактических расходов и возможность продолжать работу с проверенного состояния.
Особенно важен отдельный механизм общих лемм. Когда его отключили, стоимость выросла на 41,6%, а система решила меньше задач: необходимые факты приходилось заново выводить внутри больших доказательств. Значит, повторное использование формальных артефактов влияет на экономику сильнее, чем простое увеличение числа попыток.
Автоматику также нельзя безусловно запускать перед каждой моделью. На наборах с рутинными условиями она сокращала расходы, но на алгоритмических целях иногда дробила цель на бесполезные подцели. Маршрутизатор нужен не только для выбора LLM, но и для решения, когда модель вообще не следует вызывать.
Прямо результаты относятся к программной верификации в Lean и охватывают задачи от отдельных функций до репозиториев. Для команды в этом контуре разумный следующий шаг — прототипировать маршрутизацию поверх существующего проверяющего контура, а не заменять весь стек новым агентом. Перенос схемы на другие системы доказательства потребует отдельных замеров.
Источники
Похоже на вашу задачу?
Расскажите, что собираете. За полчаса разложим на этапы и назовём сроки — это бесплатно и ни к чему не обязывает.
