Проблема «стены кардинальности»
Большие языковые модели (LLM) всё чаще требуют генерации структурированных данных, соответствующих жестким схемам. Типичный сценарий — выбор значения из конечного набора строк (например, JSON-поля или коды статусов). Существующие системы ограниченного декодирования (constrained decoding), такие как XGrammar (бэкенд в vLLM и SGLang), используют компиляцию общих грамматик. При увеличении количества допустимых значений до тысяч эта операция становится критически медленной, создавая так называемую «стену кардинальности» (cardinality wall).
Решение: Trie Automata
Авторы статьи (Xingzi Xu, Karim Bouyarmane) предлагают специализированный механизм на основе Trie Automata. Алгоритм использует структуру префиксных деревьев и алгоритм Ахо-Корасик для многошагового поиска паттернов. Ключевое отличие — предвычисление масок допустимых токенов для каждого узла автомата. Это позволяет обойти стандартный конвейер направленного декодирования (guided decoding pipeline), сделав процесс обслуживания stateless (без сохранения состояния).
Ключевые метрики производительности
Эксперименты показали радикальное улучшение показателей по сравнению с XGrammar. Ниже приведено сравнение базовых вычислений и итоговой пропускной способности:
| Метрика | Trie Automata | XGrammar (vLLM/SGLang) | Ускорение |
|---|---|---|---|
| Время вычисления маски токена (на шаг) | 0.65 мкс | 5.8 мкс | ~7x |
| Скорость компиляции (при K >= 300) | Быстрее | Медленнее | 2–6.5x |
| Пропускная способность (Throughput) vLLM | 219 req/s | 7.5 req/s | 29x |
Тестирование проводилось при размере батча 256. Итоговое ускорение в 29 раз складывается не только из алгоритмической оптимизации, но и из экономии ресурсов за счет отсутствия накладных расходов на интеграцию с конвейером.
Масштабируемость и совместимость
Метод гарантирует 100% валидность выходных данных. Время компиляции остается в пределах 100 мс даже для наборов размером до 10 000 элементов (K = 10,000). Стоимость вычислений на каждом шаге генерации (per-step cost) остается плоской (flat) и не зависит от размера множества, что критично для стабильности latency.
Исследование протестировано на семи семействах токенизаторов с размером словаря от 32K до 262K, что подтверждает универсальность подхода для современных архитектур LLM.
Источник: arXiv cs.AI ↗