Глава 5.6 — Структурированный вывод: от грамматик до ограниченного декодирования

Содержание

  1. Почему «пожалуйста, выведи валидный JSON» недостаточно
  2. Ограниченное декодирование: маскирование недопустимых токенов на каждом шаге
  3. От регулярных выражений к конечноавтоматным грамматикам
  4. Проблема несовпадения с токенизацией и трюк с FSM-индексом
  5. За пределами регулярных языков: контекстно-свободные грамматики и JSON
  6. Во что обходится ограниченное декодирование — задержка и компромиссы по качеству
  7. Альтернатива: обучать модели нативно выдавать структуру
  8. Взгляд с точки зрения интервью
  9. Вопросы для самопроверки
  10. Источники

1. Почему «пожалуйста, выведи валидный JSON» недостаточно

Глава 5.5 была о том, как понять, действительно ли заявленные способности модели выдерживают честную проверку. Эта глава обращается к более узкому, чисто механическому вопросу, который пронизывает все эти способности разом: какой бы хорошей ни была модель в рассуждении, извлечении информации, восприятии или вызове инструментов (глава 5.4), её вывод всё равно должен прийти в виде, который программа способна распарсить, — JSON-объект с правильными ключами, SQL-запрос со сбалансированными скобками, сигнатура функции с аргументами в правильном порядке и типе. Очевидный первый подход — просто попросить: написать в промпте «отвечай только валидным JSON по этой схеме» и надеяться, что модель подчинится. По большей части это работает, и именно это делает опасной опору на такой подход в масштабе — модель предсказания следующего токена, какой бы хорошо инструктивно дообученной она ни была, сэмплирует из выученного распределения над правдоподобным текстом, а не запускает парсер, и ничто в этом процессе сэмплирования механически не предотвращает случайную запятую, незакрытую скобку, галлюцинированное лишнее поле или строку там, где схема требовала число. В масштабе одного демо это редкая неприятность, которую просто перезапускают; в масштабе продакшен-конвейера, обрабатывающего тысячи запросов в минуту, доля валидности в 98% — это стабильный поток проваленных парсингов, а очевидные меры смягчения — регулярковая чистка, второй вызов LLM, чтобы «починить» вывод, циклы повтора при неудаче — все добавляют задержку и стоимость, залатывая проблему, которую сэмплер следующего токена никогда и не собирался надёжно решать сам по себе.

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

2. Ограниченное декодирование: маскирование недопустимых токенов на каждом шаге

Вспомните из главы 1.1, что на каждом шаге декодирования модель выдаёт распределение вероятностей по всему своему словарю — десяткам тысяч кандидатов на следующий токен, — а обычное сэмплирование выбирает один из них согласно этому распределению, как бы оно ни было переформировано температурой или top-p. Ограниченное декодирование вмешивается ровно в этой точке: перед сэмплированием оно вычисляет маску по словарю — какие из возможных следующих токенов сохранили бы вывод на пути к удовлетворению некоторого формального ограничения — и выставляет логиты всех токенов вне этого множества в $-\infty$ (что эквивалентно обнулению их вероятности после софтмакса), так что какая бы стратегия сэмплирования ни запускалась после этого, она может выбирать только из токенов, действительно являющихся валидными продолжениями. Модель по-прежнему вносит ровно те же относительные предпочтения среди валидных токенов, что и всегда; убирается только вероятностная масса на токенах, которые прямо нарушили бы ограничение.

Формальное ограничение обычно выражается как грамматика — JSON Schema, регулярное выражение, контекстно-свободная грамматика в формате вроде GBNF (используемом llama.cpp), — и процесс генерации отслеживает, наряду с обычным состоянием модели, состояние парсера для этой грамматики: какие символы допустимы следующими, учитывая всё сгенерированное до сих пор и правила грамматики. На каждом шаге это состояние парсера определяет маску; каждый принятый токен продвигает состояние парсера точно так же, как посимвольный парсер продвигался бы после потребления этих символов. Вывод теперь гарантированно синтаксически валиден по построению — не потому, что модель стала лучше следовать инструкциям, а потому, что процедуре сэмплирования никогда и не была дана возможность выдать что-либо иное.

3. От регулярных выражений к конечноавтоматным грамматикам

Простейший и самый дешёвый случай — регулярное выражение: даты в формате YYYY-MM-DD, американские телефонные номера, поля-перечисления с небольшим фиксированным набором допустимых строк. Регулярное выражение компилируется в конечный автомат — фиксированный, конечный набор состояний с переходами, помеченными символами, которые переводят из одного состояния в другое, — и ограниченное декодирование по регулярному выражению означает отслеживание того, в каком состоянии автомата вы находитесь, и на каждом шаге разрешение только тех токенов, чьи символы соответствуют допустимым переходам из этого состояния. Поле вроде "status": "active", где status может быть только "active", "pending" или "closed", — это ровно такой случай: небольшой автомат с горсткой состояний, дёшево строить и дёшево отслеживать.

Более простые конструкции JSON Schema — строковые поля, перечисления, числа фиксированного формата — таким образом сводятся к регулярным языкам без особых сложностей. Осложнение начинается с тех частей JSON, которые рекурсивны: объект, значения которого сами могут быть объектами, массив, элементы которого сами могут быть массивами, произвольно глубоко. Конечные автоматы по определению не имеют памяти сверх того, в каком именно одном состоянии они сейчас находятся, — они не могут подсчитать «сколько скобок ещё не закрыто» для произвольно глубокой вложенности, поскольку это потребовало бы неограниченно много состояний. Это настоящее ограничение выразительности, а не инженерное неудобство, и именно к нему возвращается раздел 5.

4. Проблема несовпадения с токенизацией и трюк с FSM-индексом

Есть структурное несовпадение, которое делает всё это сложнее, чем «просто проверять каждый токен по автомату»: переходы автомата определены над отдельными символами, но модель генерирует не символы — она генерирует подсловные токены (глава 4.1), а один токен может охватывать несколько символов, пересекать границу токена, которую автомат не ожидал, или даже охватывать частичную последовательность байтов UTF-8. Наивная проверка на каждом шаге декодирования того, является ли каждый из десятков тысяч словарных токенов модели валидным продолжением из текущего состояния автомата, — путём прогона символов этого токена через автомат по одному, — добавила бы реальную, повторяющуюся стоимость к каждому отдельному шагу генерации, для каждого запроса.

Outlines, предложенный Willard и Louf, решает это, полностью убирая эту стоимость из цикла декодирования. Имея грамматику, он заранее вычисляет индекс, отображающий каждое состояние автомата на конкретное подмножество словаря модели, являющееся валидным продолжением из этого состояния, — прогоняя каждый словарный токен через автомат один раз, заранее, для конечного числа состояний грамматики, а не по разу на токен на каждом шаге генерации. В момент собственно декодирования получение маски для данного шага — это дешёвый поиск по этому заранее вычисленному индексу по текущему состоянию автомата, а не свежее линейное сканирование по словарю, — дорогая часть задачи оплачивается один раз на грамматику (которую затем можно переиспользовать в каждой генерации, ограничиваемой этой грамматикой), а не один раз на сгенерированный токен.

5. За пределами регулярных языков: контекстно-свободные грамматики и JSON

Произвольная глубина вложенности JSON — это контекстно-свободный язык, а не регулярный, а значит, структурное ограничение полного, неограниченного по глубине JSON требует автомата с магазинной памятью (pushdown automaton) — конечного автомата, дополненного стеком, способным отслеживать открытые фигурные и квадратные скобки на неограниченную глубину, снимая одну со стека на каждый закрывающий символ и отказываясь принять закрывающий символ, когда стек пуст. Фреймворки ограниченного декодирования, поддерживающие полные контекстно-свободные грамматики, — формат GBNF в llama.cpp и подход, описанный Geng с соавторами для грамматически-ограниченного декодирования структурированных выводов в целом, — расширяют ту же идею маскирования до этого более богатого автомата: «текущее состояние», определяющее маску допустимых токенов, теперь включает содержимое стека, а не только одно состояние конечного автомата, а продвижение парсера после принятия токена означает добавление или снятие элемента стека согласно правилам вывода грамматики, а не просто переход в новое состояние.

Практический вывод для работающего инженера состоит не столько в том, чтобы строить эту машинерию с нуля — зрелые библиотеки (Outlines, поддержка грамматик в llama.cpp, Guidance) уже её реализуют, — сколько в том, чтобы понимать, какие из ваших структурных ограничений — это «просто» регулярное выражение (дёшево, всегда эффективно), а какие — по-настоящему контекстно-свободны (корректны, но с реальной стоимостью на шаг, связанной с тем, насколько глубоко нужно отслеживать стек), чтобы уметь объяснить, почему глубоко вложенная схема может ограничиваться медленнее, чем плоская с тем же числом полей.

6. Во что обходится ограниченное декодирование — задержка и компромиссы по качеству

Ограниченное декодирование не бесплатно, и стоит точно понимать, где именно лежит эта стоимость, а не считать «грамматически ограниченный» строго лучше «неограниченного плюс повторы» во всех случаях. Предвычисление FSM-индекса амортизирует стоимость сканирования словаря за счёт переиспользования грамматики, но отслеживание состояния стека автомата с магазинной памятью, вычисление масок на каждом шаге и — для очень больших словарей или очень разрешительных состояний грамматики — сам размер множества допустимых токенов на некоторых шагах всё же добавляют реальные накладные расходы относительно неограниченного сэмплирования, даже если это намного дешевле наивного сканирования словаря на токен на шаг, описанного в разделе 4.

Есть и более тонкая, менее очевидная цена: принуждение вывода модели проходить через границы токенов грамматики может плохо взаимодействовать с тем, как модель была реально токенизирована во время предобучения. Исследование ограничений формата от Tam с соавторами обнаружило, что принуждение моделей к строгому JSON-выводу может измеримо ухудшать точность решения задачи по сравнению с тем, чтобы дать модели рассуждать в свободной форме и структурировать лишь итоговый ответ впоследствии, — на некоторых задачах, требующих интенсивного рассуждения; гипотеза в том, что принуждение к жёсткому формату вывода слишком рано может подавлять именно тот вид промежуточного свободного рассуждения (глава 5.1), который реально нужен задаче, и что навязанные грамматикой границы токенов не всегда совпадают с границами подслов, которые естественным образом выбрал бы собственный токенизатор модели. Практический урок не в том, чтобы «избегать ограниченного декодирования», а в том, чтобы «ограничивать формат итогового ответа, но не обязательно каждый токен с самого первого», и относиться к компромиссу между рассуждением и форматированием как к реальному дизайнерскому решению, а не считать, что более строгое всегда безопаснее.

7. Альтернатива: обучать модели нативно выдавать структуру

Ограниченное декодирование — это фикс на этапе инференса: он не требует переобучения чего-либо и работает поверх любой базовой модели. Дополняющий подход — фикс на этапе обучения: дообучить (глава 4.5) модель специально на примерах нужных ей структурированных форматов, пока выдача валидного JSON или корректно отформатированного вызова функции не станет близка к поведению модели по умолчанию, а не тем, что приходится механически принуждать. Это по существу и есть то, чем является поддержка «нативного вызова функций» в коммерческих API моделей, — модель увидела достаточно обучающих примеров целевого формата вызова, что надёжно воспроизводит его без подсказки, без необходимости обслуживающему стеку вообще запускать цикл грамматически-ограниченного декодирования (хотя несколько провайдеров всё же надстраивают ограниченное декодирование снизу как страховку надёжности, а не полагаются исключительно на обучение).

Эти два подхода не исключают друг друга, и честная формулировка — это спектр, а не бинарный выбор: фиксы на этапе обучения уменьшают, как часто ограничению вообще приходится вступать в силу, что снижает и цену по качеству из раздела 6, и цену задержки от запуска грамматически-ограниченного декодирования на каждом токене; ограничения на этапе инференса — это то, что даёт вам жёсткую гарантию даже когда фикс на этапе обучения несовершенен или когда целевая схема генерируется динамически во время запроса и не могла быть заранее использована для обучения. Продакшен-система, просящая модель вызвать один из небольшого, фиксированного набора хорошо задокументированных инструментов, опирается на фикс на этапе обучения; система, где целевая схема варьируется от запроса к запросу, или где единственный невалидный вывод неприемлем независимо от того, насколько он редок, нуждается в гарантии на этапе инференса вне зависимости от того, насколько хорошо уже обучена модель.

Рассуждение, извлечение информации, мультимодальное восприятие, использование инструментов и теперь надёжный, валидный по схеме вывод — всё это, по отдельности, способности и гарантии, расширяющие то, что можно доверить языковой модели. Ни одна из них сама по себе не говорит, как собрать их в реальный продукт: какие именно техники нужны конкретной системе, как спроектировать конвейер, связывающий их воедино в условиях реальных ограничений по задержке и стоимости, и как сохранить надёжность всей системы уже в продакшене, а не только в демонстрации. Именно к этой задаче сборки — объединению всего, что охватила эта часть книги, в одну работающую систему, — обращается далее часть VI, начиная с главы 6.1 «Системный дизайн для LLM-продуктов».

8. Взгляд с точки зрения интервью

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

  • «Почему "просто попросить модель вывести валидный JSON и провалидировать постфактум" недостаточно для продакшен-конвейера?» — сильный ответ называет реальный режим отказа: у сэмплера следующего токена нет механизма, предотвращающего невалидный токен, так что даже высокая доля соблюдения даёт стабильный поток проваленных парсингов в объёме, а обычные фиксы (повторы, проход починки) добавляют стоимость и задержку, чтобы обойти проблему, которую ограниченное декодирование убирает у источника.
  • «Как ограниченное декодирование на самом деле обеспечивает валидность — что именно меняется в процессе сэмплирования?» — сильный ответ описывает маскирование: вычисление, из текущего состояния парсера грамматики, подмножества словарных токенов, являющихся валидными продолжениями, и обнуление вероятности всех остальных токенов перед сэмплированием, так что относительные предпочтения модели среди валидных токенов сохраняются, а невалидные токены просто не могут быть выбраны.
  • «Почему нельзя просто проверять каждый словарный токен по грамматике на каждом шаге декодирования, и что вместо этого делает подход Outlines с FSM-индексом?» — сильный ответ указывает на стоимость наивного сканирования на шаг, на токен по десяткам тысяч словарных записей и объясняет, что предвычисление индекса «состояние → подмножество валидных токенов» один раз на грамматику превращает маскирование на каждом шаге в дешёвый поиск, а не в свежее сканирование.
  • «Строго ли грамматически-ограниченный вывод лучше, чем дать модели рассуждать свободно и структурировать только итоговый ответ?» — сильный ответ избегает ловушки «всегда ограничивать всё», ссылаясь на данные о том, что принуждение к жёсткой структуре слишком рано может подавлять полезное промежуточное рассуждение, и аргументирует в пользу ограничения формата итогового ответа при сохранении места для свободного рассуждения до этого — на задачах, где это рассуждение имеет значение.

Сквозная мысль, которую проверяют интервьюеры, — способны ли вы точно локализовать, откуда берётся гарантия — из выученной склонности или из механического ограничения, — и рассуждать о реальной цене и режимах отказа каждого из подходов, а не считать «структурированный вывод» решённой задачей, которую любая библиотека решает бесплатно.

9. Вопросы для самопроверки

  1. Почему собственное распределение вероятностей модели предсказания следующего токена не даёт никакой гарантии синтаксической валидности, даже после обширного инструктивного дообучения?
  2. Опишите точно, что меняется в процессе сэмплирования, когда на данном шаге применяется ограниченное декодирование.
  3. Почему произвольная глубина вложенности JSON невыразима как регулярный язык, и какой автомат нужен вместо этого?
  4. Какую конкретно стоимость убирает из цикла декодирования предвычисление FSM-индекса в Outlines, и когда эта стоимость оплачивается вместо этого?
  5. Что обнаружило исследование Tam с соавторами о принуждении к строгим форматам вывода на задачах, требующих интенсивного рассуждения, и на что это указывает касательно того, где применять ограничения?
  6. Сопоставьте ограниченное декодирование и дообучение под структурированный вывод как два решения одной и той же проблемы — чем платит каждое и когда вы бы выбрали одно вместо другого?

10. Источники

  • Willard, B., & Louf, R. (2023). Efficient Guided Generation for Large Language Models (Outlines). arXiv:2307.09702. https://arxiv.org/abs/2307.09702
  • Geng, S., Josifoski, M., Peyrard, M., & West, R. (2023). Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning. EMNLP 2023. arXiv:2305.13971. https://arxiv.org/abs/2305.13971
  • Beurer-Kellner, L., Fischer, M., & Vechev, M. (2023). Prompting Is Programming: A Query Language for Large Language Models (LMQL). PLDI 2023. arXiv:2212.06094. https://arxiv.org/abs/2212.06094
  • Tam, Z. R., Wu, C.-K., Tsai, Y.-L., Lin, C.-Y., Lee, H.-Y., & Chen, Y.-N. (2024). Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models. arXiv:2408.02442. https://arxiv.org/abs/2408.02442

Тест для самопроверки

Проверьте понимание главы с помощью короткого теста — вопросы по теории и небольшие расчёты.

Почему просьба к модели «вывести валидный JSON» в промпте не является надёжным решением в продакшен-масштабе?

Объяснение: Модель сэмплирует из выученного распределения над правдоподобным текстом, а не запускает парсер — ничто механически не предотвращает невалидный токен, и даже 98% валидности — это стабильный поток отказов в объёме.

Что именно меняет ограниченное декодирование в процессе сэмплирования на каждом шаге?

Объяснение: Маска полностью обнуляет вероятность невалидных токенов — относительные предпочтения модели среди валидных токенов сохраняются, но невалидные никогда не могут быть выбраны.

Почему обычный конечный автомат не может ограничить произвольную глубину вложенности JSON?

Объяснение: Произвольная глубина вложенности — контекстно-свободный язык; корректно представить его требует автомата с магазинной памятью и стеком, а не фиксированного конечного набора состояний.

Какую конкретно стоимость убирает из цикла декодирования предвычисление FSM-индекса в Outlines?

Объяснение: Outlines предвычисляет индекс «состояние → подмножество валидных токенов» один раз на грамматику, превращая маскирование на каждом шаге в дешёвый поиск вместо свежего сканирования всего словаря.

Что обнаружило исследование Tam с соавторами об ограничениях формата, касательно принуждения к строгому JSON-выводу на задачах, требующих интенсивного рассуждения?

Объяснение: Принуждение к жёсткой структуре слишком рано может подавлять нужный вид промежуточного рассуждения — практический урок в том, чтобы ограничивать формат итогового ответа, а не каждый токен с самого начала.

Как грамматически-ограниченное декодирование обрабатывает контекстно-свободную грамматику вроде полного JSON, в отличие от обычного регулярного выражения?

Объяснение: Автомат с магазинной памятью отслеживает открытые скобки на неограниченную глубину через стек; состояние парсера, используемое для маскирования, теперь включает этот стек, а не только одно состояние автомата.

Что представляет собой альтернатива на этапе обучения ограниченному декодированию на этапе инференса?

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

Когда ограничение на этапе инференса остаётся необходимым, даже если модель хорошо дообучена под структурированный вывод?

Объяснение: Фиксы на этапе обучения уменьшают, как часто ограничению приходится вступать в силу, но жёсткая гарантия — особенно для динамически генерируемых схем — всё равно требует механизма на этапе инференса.

Почему токенизация конкретно усложняет ограниченное декодирование?

Объяснение: Именно это несовпадение делает наивную посимвольную проверку каждого словарного токена по автомату на каждом шаге дорогой, что и мотивирует предвычисление FSM-индекса.

Как правильно соотносить ограниченное декодирование и дообучение под структурированный вывод?

Объяснение: Эти два подхода дополняют друг друга: система с небольшим фиксированным набором хорошо задокументированных инструментов опирается на обучение; система с динамическими схемами на каждый запрос всё равно нуждается в гарантии на этапе инференса.

Продакшен-конвейер обрабатывает 12 000 запросов в минуту. Неограниченная модель достигает доли соблюдения валидного JSON в 98%. Сколько проваленных парсингов происходит в минуту?

Объяснение: 12 000 × (1 − 0.98) = 12 000 × 0.02 = 240 проваленных парсингов в минуту — стабильный, дорогостоящий поток отказов даже при доле, которая выглядит хорошо в демо.

Словарь модели содержит 32 000 токенов, а конечный автомат грамматики имеет 25 различных состояний. Построение FSM-индекса Outlines требует прогона каждого словарного токена через автомат один раз на каждое состояние. Сколько всего проверок «токен-состояние» требует это предвычисление (в тысячах)?

Объяснение: 32 000 токенов × 25 состояний = 800 000 проверок, то есть 800 тысяч — оплачивается один раз на грамматику, а не один раз на каждый сгенерированный токен во время декодирования.