💻 computer science

Trie Automata for Constrained Decoding over Large Finite Sets

이 논문은 유한 집합 제약 디코딩을 위해 아호-코라식크(Aho-Corasick) 다중 패턴 매칭을 활용하여 토큰 마스크를 사전 계산하는 특화된 메커니즘인 트라이 오토마타(trie automaton)를 소개하며, 이를 통해 XGrammar와 같은 기존 시스템에 비해 100%의 출력 유효성을 보장하면서도 최대 29배 높은 처리량과 현저히 빠른 컴파일 속도를 달성한다.

원저자: Xingzi Xu, Karim Bouyarmane

게시일 2026-08-14

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Xingzi Xu, Karim Bouyarmane

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

컴퓨터가 매우 재능 있지만 약간은 산만하고 혼란스러운 요리사 같은 세상이 있다고 상상해 보세요. 그들은 이야기를 쓰고, 수학 문제를 풀고, 소프트웨어를 코딩할 수도 있지만, 무언가를 지어내는 나쁜 버릇이 있습니다. 만약 당신이 그들에게 세계의 수도 목록을 나열하라고 요청한다면, 그들은 자신 있게 "나니아"라는 도시를 발명하거나 "파리(Paris)"의 철자를 틀릴 수도 있습니다. 이를 막기 위해 과학자들은 **제약된 디코딩(constrained decoding)**이라는 기술을 사용합니다. 이것은 요리사에게 엄격한 레시피 북을 주는 것과 같습니다. 요리사가 우주의 모든 재료를 마음대로 고르게 하는 대신, 레시レシピ 북은 "밀가루, 설탕, 또는 달걀만 사용할 수 있습니다"라고 말합니다. 컴퓨터는 자신이 쓰려는 단어 하나하나를 이 목록과 대조하여 실수로 새로운 재료를 만들어내지 않도록 확인합니다.

이 방식은 레시피에 재료가 세 가지처럼 목록이 짧을 때는 아주 잘 작동합니다. 하지만 만약 목록이 엄청나게 길다면 어떨까요? 예를 들어 레시피가 "전 세계의 10,000가지 서로 다른 향신료 중 무엇이든 선택할 수 있습니다"라거나, "거대한 작업장에 있는 50,000개의 도구 중 무엇이든 고를 수 있습니다"라고 한다면 말이죠. 세 개의 아이템이 있는 목록을 확인하는 것은 쉽습니다. 하지만 컴퓨터가 새로운 단어를 생각할 때마다 50,000개의 아이템을 확인하는 것은, 계속해서 커지는 거대한 건초더미에서 특정 바늘 하나를 찾는 것과 같습니다. 컴퓨터는 목록을 확인하느라 너무 허우적거리다가 요리를 멈춰버리거나, 음식이 다 식을 때까지 너무 오래 걸리게 됩니다. 이것이 바로 연구자들이 해결하려고 노력 중인 문제입니다. 즉, "금지된 목록"이 방대해지더라도 어떻게 하면 컴퓨터를 빠르고 정확하게 유지할 것인가 하는 점입니다.

금지된 단어들의 거대한 도서관

이 논문에서 연구자들은 **트라이 오토마톤(Trie Automaton)**이라는 영리한 새로운 도구를 소개합니다. 이것이 왜 혁신적인 변화인지 이해하기 위해, 기존 방식이 어떻게 작동했는지 살펴봅시다. 컴퓨터가 거대한 도서관 문 앞을 지키는 보안 요리사라고 상상해 보세요. 컴퓨터가 단어를 말하고 싶을 때마다, 보안 요사는 긴 복도를 달려가 거대하고 먼지가 쌓인 장부(10,000개의 유효한 단어 목록)를 확인하고 그 단어가 허용되는지 확인해야 합니다. 목록이 방대해지면, 보안 요사는 복도를 왔다 갔다 하는 데 모든 시간을 허비하게 되고, 안으로 들어가려는 사람들의 줄(컴퓨터의 생각들)은 꽉 막히게 됩니다. 이것이 논문에서 말하는 "카디널리티 벽(cardinality wall)"입니다. 즉, 목록이 너무 커져서 시스템이 멈추거나 속도가 느려지는 지점을 말합니다.

연구자들은 기존 방식이 모든 목록을 무작위로 뒤섞인 단어들처럼 취급했다는 점을 깨달았습니다. 하지만 현실 세계에서 목록은 무작위가 아닙니다. 도구 이름 목록을 생각해 보세요: "aws.create_user", "aws.delete_user", "aws.list_user". 이들은 모두 "aws."로 시작합니다. 그다음에는 "create", "delete", 또는 "list"가 옵니다. 이들은 나무의 가지처럼 공통된 시작 부분을 많이 공유합니다. 기존의 보안 요사는 이를 알아차리지 못했습니다. 그들은 매번 처음부터 모든 단어를 하나하나 확인했습니다.

새로운 **트라이 오토마톤(Trie Automaton)**은 도서관의 특별한 지도를 만드는 매우 똑똑한 사서와 같습니다. 긴 복도 대신, 사서는 나무 모양의 경로를 만듭니다.

지도: 그들은 "aws."를 위한 경로를 그립니다. 일단 "aws." 경로에 들어서면, 다시 "aws."를 확인할 필요가 없습니다. 그저 다음 갈림길인 "create", "delete", 또는 "list"를 보기만 하면 됩니다.
사전 확인: 여기 마법 같은 기술이 있습니다. 컴퓨터가 말을 시작하기도 전에, 사서는 나무의 모든 갈림길에서 어떤 단어가 허용되는지를 미리 계산합니다. 그들은 이 답들을 작은 포스트잇에 적어 나무 가지에 바로 붙여 놓습니다.
속도: 이제 컴퓨터가 말을 하고 싶을 때, 사서는 장부로 달려가지 않습니다. 그저 현재 가지에 붙은 포스트잇을 보기만 하면 됩니다. "아, 지금 'aws' 가지에 있군요? 쪽지에 다음으로는 'create', 'delete', 또는 'list'만 말할 수 있다고 적혀 있네요." 이 과정은 순식간에 끝납니다.

결과: 달팽이에서 로켓으로

연구자들은 이 새로운 시스템을 10개에서 10,000개의 아이템으로 구성된 단어 목록을 사용하여 기존의 최선책(XGrammar 등)과 비교 테스트했습니다. 결과는 극적이었습니다.

컴파일 속도: 1,000개의 아이템에 대한 지도를 만들 때, 기존 시스템은 약 75밀리초(약간의 기다림)가 걸렸습니다. 새로운 트라이 오토마톤은 이를 약 33밀리초 만에 해냈습니다. 하지만 목록이 10,000개로 늘어나자 기존 시스템은 거의 240밀리초가 걸린 반면, 새로운 시스템은 40밀리초 정도로 거의 일정하게 유지되었습니다. 마치 기존 시스템은 진흙 속을 달리고 있었고, 새로운 시스템은 속도가 빨라져도 전혀 힘들어하지 않는 러닝머신 위를 달리는 것과 같았습니다.
"카디널리티 벽": 기존 시스템은 목록이 몇 백 개를 넘어서면 급격히 실패하거나 느려지기 시작했습니다. 새로운 시스템은 10,000개의 아이템이 있는 목록도 무리 없이 처리했으며, 연구자들은 이론적으로 100,000개까지도 처리할 수 있음을 보여주었습니다.
배치 서빙 (진정한 승리): 가장 놀라운 결과는 여러 요청을 동시에 처리할 때(예: 256개의 주문이 밀려드는 바쁜 레스토랑) 나타났습니다. 기존 시스템은 초당 약 7.5개의 주문만 처리할 수 있었습니다. 하지만 새로운 트라이 오토마톤은 초당 219개의 주문을 처리했습니다. 이는 29배나 향상된 수치입니다.

왜 이렇게 훨씬 더 빨랐을까요? 단순히 지도 때문만이 아니라, 그 지도를 사용하는 방식 때문이었습니다. 답이 포스트잇에 미리 적혀 있었기 때문에, 컴퓨터는 말을 하는 동안 복잡한 생각이나 확인 과정을 거칠 필요가 없었습니다. 그저 쪽지를 집어 들고 바로 다음 단계로 넘어갈 수 있었습니다. 덕분에 컴퓨터는 기존 시스템이 매번 수행해야 했던 느리고 복잡한 단계들을 통째로 건너뛸 수 있었습니다.

이것이 의미하는 바

이 논문은 특정 유형의 목록들—예를 들어 레지스트리에서 도구를 선택하거나, 의료 코드를 고르거나, 제품 카테고리를 선택하는 경우—에 대해서는 기존의 "모두 확인하기" 방식이 너무 느리다는 것을 증명합니다. 단어의 구조(공유된 시작 부분)를 활용하고 답을 미리 계산함으로써, 새로운 방식은 제약된 디코딩을 다시 빠르고 신뢰할 수 있게 만듭니다.

연구자들은 이 새로운 방식이 컴퓨터를 더 똑똑하게 만들거나 무엇을 말할지 바꾸는 것이 아니라, 단지 정해진 대로만 말하도록 보장하며 이를 믿을 수 없을 만큼 빠르게 수행한다는 점을 매우 주의 깊게 명시했습니다. 그들은 이를 실제 컴퓨터 칩에서 측정하였고, 새로운 방식이 규칙을 따르는 데 있어 기존 방식과 마찬가지로 100% 정확하면서도, 생성되는 모든 단어에 대해 7배 더 빠르다는 것을 발견했습니다. 이 속도를 수백 개의 요청이 동시에 발생하는 상황에 곱해보면, 그 차이는 엄청납니다.

요약하자면, 이 논문은 거대한 건초더미 속을 헤매는 혼란스럽고 느린 탐색을 빠르고 조직적인 산책으로 바꾸는 방법을 찾아냈습니다. 이는 "카디널리티 벽" 문제를 해결하여, AI가 수천 개의 도구나 서비스를 즉각적으로 선택해야 하는 AI 에이전트의 미래에 필수적인, 방대한 옵션 목록을 막힘없이 처리할 수 있도록 해줍니다.

기술 요약: 대규모 유한 집합에 대한 제약된 디코딩을 위한 트라이 오토마타 (Trie Automata)

1. 문제 정의: 카디널리티 벽 (The Cardinality Wall)

대규모 언어 모델(LLM)은 점차 정해진 스키마를 따르는 구조화된 출력을 필요로 하고 있으며, 특히 알려진 유한 집합(예: 도구 이름, 의료 코드, 제품 분류 체계)에서 문자열을 선택하는 작업이 중요해지고 있습니다. XGrammar 및 Outlines와 같은 현재의 제약된 디코딩 시스템은 이러한 제약을 범용 오토마타(유한 상태 기계(FSM), 푸시다운 오토마타 또는 Earley 파서)로 컴파일하여 처리합니다.

이러한 범용 방식은 복잡한 문법에는 효과적이지만, 단순한 유한 집합 제약에 대해서는 "카디널리티 벽"을 생성합니다. 유효한 문자열의 수( $K$ )가 수천 개로 증가함에 따라, 컴파일 시간과 단계별 디코딩 지연 시간이 걷잡을 수 없이 느려지기 때문입니다. 기존 제공업체들은 엄격한 제한을 두고 있는데(예: OpenAI는 1,000개의 열거형, Google Gemini는 약 120개), 이는 표준 컴파일 파이프라인이 $K$ 에 따라 성능이 급격히 저하되기 때문입니다. 핵심 문제는 근본적인 불일치에 있습니다. 즉, 단순한 제약(문자열의 유한 합집합)을 처리하기 위해 구조적 특징(공유 접두사, 유한한 깊이, 알려진 카디널리티)을 활용할 수 있음에도 불구하고, 복잡한 문법용 범용 엔진을 적용하고 있다는 점입니다.

2. 방법론: 트라이 오토마타 (The Trie Automaton)

저자들은 일반적인 FSM 레이어를 대체하는 유한 집합 제약 전용 백엔드로 트라이 오토마타를 도입합니다. 이 방법은 제약 집합의 구조를 활용하여 서브 리니어(sub-linear) 컴파일과 상수 시간(constant-time) 단계별 마스킹을 달성합니다.

핵심 메커니즘

문자 단위 트라이 구축 (Character-Level Trie Construction): 토큰 단위의 트라이(토큰 경계를 가로지르는 접두사를 공유하지 못함)나 일반적인 DFA 대신, 시스템은 유효한 문자열 집합으로부터 직접 문자 단위의 트라이를 구축합니다. 이를 통해 공유 접두사를 병합함으로써 노드 수를 $O(K \cdot L_{max})$ 에서 $O(N_{chars})$ ( $N_{chars}$ 는 총 문자 수)로 줄입니다.
Aho-Corasick를 통한 BPE-Trie 정렬 (BPE-Trie Alignment via Aho-Corasick): 핵심 과제는 문자 단위 트라이를 모델의 Byte-Pair Encoding (BPE) 어휘 사전과 정렬하는 것입니다. 단일 BPE 토큰은 여러 개의 트라이 엣지(edge)에 걸쳐 있을 수 있습니다. 저자들은 이 문제를 다중 패턴 문자열 매칭 문제로 환원하여 해결합니다. 이들은 어휘 사전 토큰들로부터 Aho-Corasick (AC) 오토마타를 구축하고 트라이를 순회하며, 모든 트라이 노드 $n$ 에 대해 유효한 BPE 토큰 집합(valid[n])을 미리 계산합니다.
사전 계산된 마스크 (Precomputed Masks): 컴파일 과정에서 시스템은 모든 노드에 대해 valid[n]을 계산합니다. 디코딩 시 마스킹은 직접적인 $O(1)$ 조회로 감소합니다: $A(s_t) = valid[s_t]$ . 이를 통해 전체 어휘 사전을 스캔하거나 매 단계마다 토큰의 전이를 시뮬레이션할 필요가 없습니다.

복잡도 이점

컴파일 (Compilation): 비용은 어휘 사전에 대한 AC 오토마타 구축에 의해 지배되며, 이는 $O((N_{chars} + V) \cdot \ell)$ 입니다 (여기서 $V$ 는 어휘 사전 크기, $\ell$ 은 최대 토큰 길이). 결정적으로, 일단 AC 오토마타가 구축되면 $K$ 에 관계없이 거의 일정하게 유지되므로, $K=10,000$ 인 경우에도 매우 빠른 컴파일 시간(30–67ms)을 보입니다.
단계별 디코딩 (Per-Step Decoding): 비용은 $O(V \cdot \ell)$ (모든 토큰 스캔)에서 $O(|valid[s_t]|)$ 로 떨어집니다. 유효한 집합은 트라이 깊이에 따라 기하급수적으로 줄어들기 때문에(보통 3~~4글자 이후 10~~100개의 토큰), 유효 비용은 매우 낮은 상수 수준(0.65µs)이 됩니다.
상태 비저장 서빙 (Stateless Serving): 마스크가 사전 계산되었기 때문에, 트라이는 FSM 기반 방식에서 요구되는 가이드 디코딩 파이프라인의 상태 관리 및 스케줄링 오버헤드를 우회하여 상태가 없는 LogitsProcessor로 동작할 수 있습니다.

3. 주요 기여

트라이 오토마타: 문자 단위 트라이, Aho-Corasick 다중 패턴 매칭, 사전 계산된 토큰 마스크를 결합한 특화된 제약 디코딩 백엔드입니다. 이는 $O(|valid[s_t]|)$ 의 단계별 마스킹을 달성하여, 일반적인 FSM 방식의 $O(V \cdot \ell)$ 비용보다 효율적입니다.
BPE-Trie 정렬 문제 해결: 논문은 문자 단위 트라이 경로를 BPE 토큰과 정렬하는 이전에 다뤄지지 않았던 문제를 해결합니다. 이를 다중 패턴 매칭으로 환원함으로써, 다양한 토크나이저 패밀리에 대해 $K=10,000$ 까지 100ms 미만의 컴파일을 가능하게 했습니다.
카디널리티 벽의 경험적 규명: 저자들은 제약 구조에 맞게 인가 메커니즘을 일치시키는 것이 스케일링 병목 현상을 극복한다는 것을 입증했습니다. 사전 계산된 마스크가 FSM 방식이 사용할 수 없는 상태 비저장(stateless) 서빙 경로를 가능하게 함으로써, 알고리즘적 속도 향상이 대규모 처리량(throughput) 향상으로 이어짐을 보여주었습니다.

4. 실험 결과

실험은 NVIDIA A100 GPU에서 7개의 토크나이저 패밀리(32K–262K 어휘 사전)와 Qwen3-8B, Mistral, Gemma3를 포함한 모델들을 대상으로 수행되었습니다.

컴파일 속도: 트라이 오토마타는 $K \ge 300$ 인 경우 XGrammar보다 2–6.5배 빠른 컴파일을 달성합니다. XGrammar의 컴파일은 $K$ 에 따라 선형적으로 증가하여 $K=100,000$ 일 때 2.7초에 달하지만, 트라이는 약 30–67ms로 평탄한 성능을 유지합니다.
단계별 지연 시간 (Per-Step Latency): 트라이는 유효 토큰 마스크를 계산하는 데 0.65µs가 소요되어, XGrammar(5.8µs)보다 7배 빠르며, LLGuidance(73–141µs)보다는 110–215배 빠릅니다.
엔드 투 엔드 처리량 (End-to-End Throughput): 배치 서빙(vLLM) 환경에서 이 이점은 배가됩니다. 배치 크기 256에서 트라이는 219 req/s를 달성하여, XGrammar의 7.5 req/s 대비 29배의 개선을 보여주었습니다. 이 이득은 7배의 알고리즘적 속도 향상과 가이드 디코딩 파이프라인 오버헤드의 제거에서 비롯됩니다.
유효성 및 정확도: 트라이는 100% 출력 유효성을 보장합니다. 분류 벤치마크(TREC, MASSIVE, Banking77, CLINC150)에서 트라이를 사용한 제약 디코딩은 비제약 디코딩의 정확도와 대등하거나 그 이상을 기록하면서 할루시네이션(환각)을 제거했습니다. 성능이 낮은 모델의 경우, 트라이는 Banking77 벤치마크에서 정확도를 4.8%에서 24.8%로 높이는 등 유효한 출력을 보장하는 핵심적인 역할을 합니다.
확장성: 이 방법은 $K=10,000$ 이상에서도 100ms 미만의 컴파일과 평탄한 단계별 비용을 유지하여, 실질적인 열거형(enum) 한계를 약 1,000개에서 약 100,000개로 확장합니다.

5. 의의 및 주장

본 논문은 제약된 디코딩에서 발생하는 근본적인 비효율성, 즉 단순하고 구조화된 제약에 범용 오토마타를 적용하는 문제를 트라이 오토마타가 해결한다고 주장합니다. 구조적 특징(공유 접두사)을 활용함으로써 저자들은 다음을 입증했습니다:

알고리즘 효율성: 트라이는 유한 집합에 대한 단계별 마스크를 사전 계산하는 데 있어 가장 효율적인 알고리즘이며, FSM 기반의 사전 계산 방식보다 컴파일 시간에서 196배 더 뛰어납니다.
시스템적 영향: 마스크를 사전 계산할 수 있다는 점은 가이드 디코딩 파이프라인을 우회하는 상태 비저장(stateless) 서빙 경로를 가능하게 하며, 이는 오직 사전 계산된 마스크를 통해서만 가능합니다. 이는 제약된 디코딩을 배치 서빙에서 병목 현상이 아닌 무시할 수 있는 수준의 오버헤드로 변화시킵니다.
일반화 가능성: 제약 구조에 맞춰 인가 메커니즘을 일치시키는 원칙(예: 고정된 형식을 위한 문자 위치 마스크 사용)은 유한 집합뿐만 아니라 규칙성이 있는 모든 제약에 대해 큰 속도 향상을 가져올 수 있습니다.

저자들은 트라이 오토마타를 FSM 기반 디코딩의 근사치가 아니라, 유한 집합에 대한 정확하고 동형(isomorphic)인 대안으로 제시하며, 고카디널리티 시나리오에서 100%의 유효성과 수십 배의 성능 향상을 제공한다고 강조합니다.