Как LLM используются для code generation с формальной верификацией (Dafny, Lean)?

Краткий тезис

LLM могут генерировать код вместе с формальными спецификациями (предусловия, постусловия, инварианты), которые затем проверяются верификаторами вроде Dafny или Lean. Основные подходы: fine-tuning на корпусе формальных доказательств, in-context learning с примерами, и co-shag — итеративный цикл генерации, проверки и исправления. Такие системы повышают надёжность кода, но требуют больших вычислительных ресурсов и качественных размеченных данных.

1. Термины

• LLM (Large Language Model) — большая языковая модель, способная генерировать текст, включая код.
• Code generation — автоматическое создание исходного кода по описанию на естественном языке.
• Формальная верификация — математическое доказательство того, что программа удовлетворяет заданным спецификациям (например, не содержит ошибок времени выполнения, соответствует контрактам).
• Dafny — язык программирования со встроенной поддержкой контрактов (pre/post conditions, loop invariants) и автоматическим верификатором на основе SMT-решателя (Z3).
• Lean — интерактивный помощник доказательств и функциональный язык программирования, используемый для формализации математики и верификации программ.

2. Зачем формальная верификация в code generation?

LLM склонны к галлюцинациям — генерации кода, который выглядит правдоподобно, но содержит логические ошибки, уязвимости или не соответствует спецификации. Формальная верификация позволяет:

• Гарантировать корректность для критических систем (авионика, медицинские устройства, блокчейн).
• Автоматически находить ошибки, которые не ловятся юнит-тестами (например, выход за границы массива, деление на ноль).
• Сократить время отладки: верификатор указывает точное место нарушения контракта.

3. Основные подходы к интеграции LLM и формальной верификации

4. Fine-tuning LLM на формальных доказательствах (Lean theorem proving)

LeanDojo — проект, в котором LLM (например, Code Llama) донастраивается на тактиках доказательства теорем в Lean. Модель учится предсказывать следующий шаг доказательства (tactic) по текущему состоянию цели.

Процесс

1. Сбор датасета: миллионы шагов доказательств из математических библиотек (Mathlib).
2. Fine-tuning с teacher forcing: модель видит цель и предыдущие тактики, предсказывает следующую.
3. Во время инференса модель генерирует тактики, Lean проверяет их корректность. Если тактика не проходит, модель получает сообщение об ошибке и корректирует вывод.

Результат модель способна доказывать теоремы из олимпиадных задач и университетских курсов, но пока уступает лучшим экспертам.

5. AlphaProof (DeepMind, 2025)

AlphaProof — гибридная система для доказательства математических теорем на Lean. Состоит из:

• LLM (Gemini) — генерирует кандидаты доказательств и тактики.
• Формальный верификатор (Lean) — проверяет каждое доказательство на корректность.
• Поиск с подкреплением — система ищет последовательность тактик, максимизирующую награду (количество доказанных теорем).

Ключевая инновация LLM не просто генерирует код, а использует обратную связь от верификатора для обучения через reinforcement learning. Это позволило AlphaProof решить задачи с Международной математической олимпиады (IMO) 2024 года.

6. Co-shag (цикл генерация-проверка-исправление)

Co-shag (cooperative shag) — популярный паттерн для code generation с верификацией. Шаги:

1. Генерация LLM получает описание задачи на естественном языке и генерирует код с контрактами (например, на Dafny).
2. Верификация Dafny проверяет код. Если верификация успешна — код принят.
3. Обратная связь Если верификация не удалась, Dafny возвращает сообщение об ошибке (например, "loop invariant might not hold").
4. Исправление LLM получает исходный код + ошибку и генерирует исправленную версию.
5. Повтор до успеха или достижения лимита итераций.

Пример кода на Dafny

method FindMax(a: array<int>) returns (max: int)
  requires a.Length > 0
  ensures forall i :: 0 <= i < a.Length ==> a[i] <= max
  ensures exists i :: 0 <= i < a.Length && a[i] == max
{
  max := a[0];
  var i := 1;
  while i < a.Length
    invariant 1 <= i <= a.Length
    invariant forall j :: 0 <= j < i ==> a[j] <= max
    invariant exists j :: 0 <= j < i && a[j] == max
  {
    if a[i] > max { max := a[i]; }
    i := i + 1;
  }
}

LLM может сгенерировать такой код, а Dafny проверит, что инварианты цикла корректны и постусловие выполняется.

7. Инструменты: Dafny и Lean

8. Проблемы и ограничения

• Качество данных Для fine-tuning нужны большие корпуса формальных доказательств, которые дорого собирать.
• Вычислительные затраты Верификация сложных программ может занимать минуты или часы; цикл co-shag требует много итераций.
• Сложность спецификаций Написание полных контрактов (предусловия, постусловия, инварианты) само по себе трудоёмко и требует экспертизы.
• Ограниченная область LLM хорошо справляются с типовыми задачами, но плохо — с новыми, не встречавшимися в обучении.
• Галлюцинации в спецификациях LLM может сгенерировать неверные контракты, которые верификатор примет, но они не отражают истинных требований.

9. Сравнение подходов

10. Метрики оценки

• Proven theorems rate — доля теорем/программ, успешно прошедших верификацию.
• Code correctness rate — доля сгенерированных программ, корректных по спецификации.
• Average iterations to success — среднее число циклов co-shag до успешной верификации.
• Time to verification — время, затраченное на верификацию (включая генерацию и исправления).
• Human effort reduction — сокращение времени, которое эксперт тратит на написание и отладку формальных спецификаций.

11. Будущее: агентные системы

Следующий шаг — создание агентов, которые:

• Автоматически генерируют формальные спецификации по описанию на естественном языке.
• Выбирают подходящий верификатор (Dafny, Lean, Coq, Why3) в зависимости от задачи.
• Используют несколько LLM (одна для кода, другая для доказательств) и обмениваются информацией.
• Интегрируются с CI/CD: при каждом коммите агент проверяет код формально.

Пример архитектуры: LLM-оркестратор → вызов Dafny для проверки контрактов → при ошибке отправка в LLM-исправитель → повтор.

Пет-проект для закрепления

Задача Создать агента, который генерирует код на Dafny с контрактами для простых алгоритмов (поиск максимума, сортировка пузырьком) и верифицирует его.

Инструменты Python, OpenAI API (или локальная LLM), Dafny (установленный локально или через Docker), библиотека subprocess.

Шаги:

1. Собрать 10–20 примеров Dafny-программ с контрактами (можно взять из документации Dafny).
2. Реализовать функцию generate_dafny(prompt: str) -> str, которая через LLM генерирует код.
3. Реализовать функцию verify_dafny(code: str) -> (bool, str), запускающую dafny verify и возвращающую успех/ошибку.
4. Реализовать цикл co-shag: до 5 итераций, на каждой передавать ошибку обратно в LLM.
5. Протестировать на 3 задачах: поиск максимума, проверка палиндрома, сортировка пузырьком.
6. Оценить: процент успешных верификаций, среднее число итераций.

Ожидаемый результат Агент, способный за 1–3 итерации сгенерировать корректный Dafny-код для простых алгоритмов. Вы получите практическое понимание взаимодействия LLM и формального верификатора.

Связь с другими вопросами

Навигация

• Предыдущий: 728
• Следующий: 730
• Индекс: 00. Индекс разборов