Trie-автомат ускоряет генерацию структурированных ответов LLM в 29 раз
Большим языковым моделям (LLM) всё чаще требуется генерировать выходные данные, соответствующие заданным схемам. Одно из распространенных ограничений — выбор из конечного множества допустимых строк. Существующие системы ограниченного декодирования полагаются на универсальную компиляцию грамматик, которая становится крайне медленной, когда число допустимых значений достигает тысяч. Авторы новой работы, опубликованной на arXiv, называют это явление «кардинальной стеной».
В качестве решения предлагается специализированный механизм — trie-автомат. Он использует структуру конечного множества: общие префиксы, ограниченную глубину и известную мощность. Применяется алгоритм многошаблонного сопоставления Ахо—Корасик для предварительного вычисления масок токенов для каждого узла дерева. Это позволяет избежать дорогостоящего разбора грамматики на каждом шаге генерации.
По данным эксперимента, trie-автомат обеспечивает семикратное ускорение вычисления допустимых токенов на шаг: 0,65 микросекунды против 5,8 микросекунды у XGrammar — одного из основных бэкендов в vLLM и SGLang. Компиляция также оказывается в 2–6,5 раза быстрее при числе допустимых значений K ? 300.
Ключевой выигрыш проявляется при пакетном обслуживании. Precomputed маски позволяют использовать stateless-путь, минуя весь конвейер управляемого декодирования. В результате сквозная пропускная способность vLLM достигает 219 запросов в секунду против 7,5 у XGrammar при размере батча 256, то есть ускорение в 29 раз. Этот эффект складывается из алгоритмического ускорения и экономии на интеграции, которую обеспечивают только предварительно вычисленные маски.
Проверка на семи семействах токенизаторов с объёмом словаря от 32K до 262K показала, что компиляция занимает менее 100 миллисекунд вплоть до K = 10 000. Стоимость шага остаётся плоской независимо от размера множества, а валидность выходных данных сохраняется на уровне 100%. Работа доступна на arXiv под номером 2608.12574.
