Прорыв в контроле LLM: полиномиальный расчет LR(k) грамматик

Проблема экспоненциальной сложности

Интеграция больших языковых моделей (LLM) в формальные системы, такие как генерация кода или SQL-запросов, требует строгого соблюдения синтаксиса. Языки программирования часто описываются контекстно-свободными грамматиками LR(k). Ранее применение методов контроля к таким грамматикам требовало экспоненциального времени, что делало их непрактичными для длинных последовательностей.

Суть метода: Дистилляция и маскирование

Авторы (Max Scribner, Antonio Vergari, Vaishak Belle) предлагают дистиллировать LLM в тривиальную вероятностную модель. Это позволяет вычислять вероятность удовлетворения логических ограничений на лету. Генерация становится «управляемой» через маскирование токенов, которые нарушают правила грамматики, гарантируя, что итоговый вывод будет синтаксически корректным.

Ключевое улучшение: Полиномиальная сложность

Главное достижение работы — доказательство того, что удовлетворение любой LR(k) грамматики конечной длительности можно рассчитать за полиномиальное время. Это кардинально меняет масштаб применимости метода, делая его эффективным для реальных задач.

Практическое значение

Метод решает критическую проблему «галлюцинаций» в структурных данных. Для задач программной инженерии, где неверный синтаксис делает вывод бесполезным, этот подход обеспечивает:

• Гарантию валидности: Вывод всегда соответствует спецификации языка (JSON, SQL, код).
• Эффективность: Снижение вычислительных затрат за счет отказа от экспоненциальных алгоритмов поиска.
• Качество: Модель сохраняет способность генерировать качественный текст, но в рамках строгих формальных ограничений.

Источник: arXiv cs.AI ↗