Эпоха 6 · Генеративка и системы · 2023 / 2024

55 Structured Output

function calling (OpenAI, 2023) · Efficient Guided Generation (Outlines) · Willard & Louf, 2023 · XGrammar, 2024 · OpenAI Structured Outputs, 2024
🟧 оригинал выборочно~2–2.5 чоригинал ↗
Суть за 20 секунд. Как заставить LLM выдавать гарантированно валидную структуру (JSON по схеме), а не «обычно валидную». Три волны: промпт-JSON (ненадёжно) → function calling (обучение эмитить вызовы по схеме, 2023) → constrained / guided decoding (на каждом шаге маскируем логиты по автомату, оставляя только токены, не ломающие грамматику). Outlines строит индекс «состояние FSM → допустимые токены»; XGrammar — byte-level pushdown-автомат. OpenAI Structured Outputs (2024) так даёт 100% схема-валидности. Тонкость: строгий формат может ронять reasoning.

Контекст

LLM — это распределение над текстом, но приложениям (агенты, tool use, API-конвейеры) нужен машиночитаемый вывод: валидный JSON точно по схеме. Просто попросить «ответь JSON» — ненадёжно: модель забывает запятую, добавляет прозу, путает типы. На больших схемах prompt-only даёт порядка трети валидных ответов — для продакшена неприемлемо. Нужна гарантия, а не надежда.

Идея и механизм

1. Function calling (2023). Модель дообучают: по описанию функции и её схеме параметров выдавать {"name": …, "arguments": {…}}. Сделало tool use практичным — но валидность всё ещё вероятностная: обученная модель обычно попадает в схему, но не обязана.

2. Constrained / guided decoding (2023–24). Гарантию дают не обучением, а на этапе декодирования. Ведём автомат, который отслеживает уже сгенерированный префикс относительно грамматики; на каждом шаге маскируем логиты всех токенов, которые сделали бы вывод невалидным, и семплируем только из допустимых. Структура валидна по построению. Outlines сводит regex/грамматику к конечному автомату и предвычисляет индекс: состояние → множество допустимых токенов (иначе пришлось бы на каждом шаге перебирать весь словарь). XGrammar берёт контекстно-свободную грамматику, компилит в byte-level pushdown-автомат и кэширует маски. OpenAI Structured Outputs (2024) компилит JSON-схему в грамматику и так гарантирует 100% соответствие (плюс обучение под схемы).

автоматы · декодирование Маскирование логитов и почему токен-алайнмент — это сложно

Ядро. Пусть автомат в состоянии s, а \( \mathcal{A}(s) \subseteq V \) — множество токенов, после которых ещё возможно валидное завершение. Модель даёт логиты \( z \in \mathbb{R}^{|V|} \); маскируем и семплируем только из допустимого:

\[ z'_i = \begin{cases} z_i, & i \in \mathcal{A}(s)\\[2pt] -\infty, & i \notin \mathcal{A}(s)\end{cases}\qquad x_t \sim \mathrm{softmax}(z'),\qquad s \leftarrow \delta(s, x_t) \]

Запрещённые токены получают \(-\infty\) → нулевую вероятность после softmax; распределение ренормируется по валидным. Токен переводит автомат в новое состояние \(\delta(s,x_t)\). Какой автомат нужен, зависит от грамматики:

\[ \text{regex} \Rightarrow \text{DFA } (Q,\Sigma,\delta,q_0,F)\qquad\qquad \text{JSON / CFG} \Rightarrow \text{PDA (со стеком)} \]

Плоский формат описывается регулярным языком (DFA конечен). Но JSON рекурсивен — вложенные, сбалансированные {} и [] не образуют регулярный язык, поэтому нужен pushdown-автомат: стек считает глубину вложенности.

Сложная часть — token alignment. Грамматика определена над символами/байтами \(\Sigma\), а модель генерирует токены V (BPE-сабворды). Один токен покрывает несколько символов, а одна строка имеет много токенизаций — прямого соответствия нет. Поэтому нельзя просто «разрешить нужные символы»: надо для каждого состояния вычислить допустимые токены. Отсюда предвычисленный индекс:

\[ \mathrm{Idx}:\; Q \;\to\; 2^{V},\qquad \mathcal{A}(s) = \mathrm{Idx}(s) \]

Стоимость. Наивно проверять валидность каждого токена — \(O(|V|)\) на шаг (словарь ~10⁵). Индекс Outlines делает это \(\approx O(1)\) (плюс дешёвое векторное применение маски). XGrammar идёт дальше: делит токены на контекстно-независимые (валидность видна по позиции — предвычислимы, >99%) и контекстно-зависимые (нужен весь стек), кэшируя маски по вершине стека PDA. Итог — <50 мкс/токен, ничтожно против 10–50 мс инференса.

Python Constrained decoding: маска логитов по автомату 
def constrained_decode(model, automaton, idx):   # idx: state -> set(token_id)
    s, out = automaton.start, []
    while not automaton.is_accept(s):
        z = model.logits(out)                     # логиты по словарю V
        allowed = idx[s]                          # предвыч. индекс: допустимые токены из s
        z = mask_fill(z, allowed, NEG_INF)        # запрещённые -> -inf (нулевая вероятность)
        tok = sample(softmax(z))                  # семплируем ТОЛЬКО валидное
        out.append(tok)
        s = automaton.step(s, tok)                # переход автомата (regex->DFA, JSON->PDA+стек)
    return detokenize(out)                         # гарантированно валидная структура
цикл декодирования (каждый шаг): логиты zпо V маска A(s)невалидные → −∞ samplesoftmax автомат: state+стекδ(s, tok) состояние автомата задаёт следующую маску три волны: промпт-JSON → function calling (2023) → guided decoding (Outlines/XGrammar) → guaranteed (OpenAI SO, 2024)
На каждом шаге автомат (для JSON — со стеком) задаёт множество допустимых токенов; логиты запрещённых гасятся в −∞, семпл идёт только из валидных, выбранный токен переводит автомат дальше. Структура валидна по построению.
Аналогия. Навигатор, который на каждом перекрёстке подсвечивает только разрешённые повороты. Карта дорог — это автомат; подсветка — маска допустимых токенов; стек PDA — память о том, сколько скобок ещё надо закрыть. Куда бы модель ни «поехала», она физически не может свернуть на запрещённую улицу — и потому всегда приезжает по валидному адресу (по схеме). Обучение (function calling) лишь делает водителя привычным к таким маршрутам; маска — гарантирует, что он не нарушит.

Почему это важно

Это фундамент, на котором стоит весь современный tool use, агенты и надёжные API-конвейеры: без гарантии валидного вывода нельзя строить системы, где ответ LLM парсится программой. «Structured output», которым сегодня пользуются все (OpenAI, Anthropic tool use, vLLM/TGI/llama.cpp с грамматиками), — это ровно эта линия: обучение под схемы + constrained decoding. Урок шире: надёжность LLM-систем часто рождается не в самой модели, а в слое декодирования вокруг неё.

Связи

← живёт в декодере32. Transformer

Constrained decoding вклинивается ровно туда, где авторегрессионный трансформер превращает логиты в токен — в softmax над словарём. Маскирование логитов возможно именно потому, что генерация идёт токен-за-токеном: перед каждым семплом можно обнулить запрещённые варианты. Без пошаговой природы #32 такого рычага бы не было.

← обучающая половина44. InstructGPT (RLHF)

Function calling — это выравнивание под инструмент: модель дообучают следовать схемам вызовов (родня SFT/RLHF из #44). Обучение делает вывод обычно валидным и осмысленным; constrained decoding добавляет гарантию. Полноценный structured output — их сумма: обученная модель + маска.

↔ в напряжении с43. Chain-of-Thought

CoT хочет свободного рассуждения вслух; строгий формат его подавляет. Исследование «Let Me Speak Freely?» (2024) показало: жёсткий JSON-режим роняет reasoning — модель вынуждают выдать ответ до того, как она «подумала». Практический выход — сначала свободный CoT-филд, потом формат (порядок полей схемы решает).

Вопросы пытливого ума

Если маска гарантирует валидный JSON — почему не включать constrained decoding всегда?

Потому что маска искажает распределение: обнуляя часть токенов и ренормируя, она может выталкивать модель в маловероятные для неё области и навязывать структуру раньше, чем модель «додумала». «Let Me Speak Freely?» (2024) показал измеримое падение reasoning под строгим форматом — особенно из-за перестановки: ответ приходится назвать до рассуждения. Митигации: сначала свободный reasoning-филд, потом строгие поля (порядок в схеме), либо генерировать в natural language и конвертировать в формат отдельным шагом. Гарантия формата ≠ бесплатно.

Почему это сложнее, чем «разрешать только нужные символы»?

Из-за token alignment. Грамматика живёт над символами/байтами, а модель — над токенами BPE: один токен склеивает несколько символов, и одна и та же строка может быть токенизирована по-разному. Значит, «разрешить символ {» не переводится напрямую в «разрешить токен» — надо для каждого состояния автомата вычислить, какие токены (многосимвольные) не ломают грамматику. Отсюда предвычисленный индекс (Outlines) и byte-level PDA с делением на контекстно-независимые (>99%, предвычислимы) и контекстно-зависимые токены (XGrammar). Это и есть настоящая инженерная глубина темы.

Regex-хватает для многих форматов — зачем для JSON именно стек (PDA)?

JSON рекурсивен: объект может содержать объекты, массивы вложены произвольно, скобки должны быть сбалансированы. Язык сбалансированных скобок — классический пример нерегулярного (его не распознаёт конечный автомат: нужно «помнить» произвольную глубину). Поэтому нужен pushdown-автомат со стеком, который считает открытые скобки и требует их закрыть. Для плоских форматов (дата, enum, число) хватает regex/DFA — но как только структура вложенная, без стека не обойтись.

Что читать в оригинале

Читать выборочно. Outlines (Willard & Louf, arXiv 2307.09702) — ключевая идея индекса «состояние FSM → допустимые токены» и сведение к автомату. XGrammar (arXiv 2411.15100) — byte-level PDA, деление токенов на контекстно-(не)зависимые, кэш масок. Пост OpenAI Structured Outputs — как JSON-схема компилится в грамматику для 100% соответствия. И обязательно «Let Me Speak Freely?» (arXiv 2408.02442) — честная цена строгого формата для reasoning.