유효 문자열이 수천 개에 달하는 유한집합에서 값을 골라야 하는 구조적 출력 제약을 처리할 때, 기존 문법 컴파일 기반 제약 디코딩은 후보가 늘어날수록 급격히 느려지는 '카디널리티 벽'에 부딪힌다. 이 논문은 공유 접두사와 고정 깊이 같은 유한집합 구조를 Aho-Corasick 다중 패턴 매칭으로 활용해 노드별 토큰 마스크를 미리 계산하는 트라이 오토마톤을 제안한다. vLLM·SGLang의 주요 백엔드인 XGrammar 대비 스텝당 유효 토큰 계산이 7배 빠르고(0.65마이크로초 대 5.8마이크로초), 배치 크기 256의 서빙 처리량은 초당 219건 대 7.5건으로 29배 앞선다. 7개 토크나이저 계열, 후보 1만 개까지 100밀리초 이하 컴파일과 100% 출력 유효성을 동시에 보장해 대규모 구조적 출력이 필요한 실전 서빙에 실질적 해법을 제시한다.

• •공유 접두사·고정 깊이를 활용해 노드별 토큰 마스크를 사전 계산하는 트라이 오토마톤 제안
• •XGrammar 대비 스텝당 유효 토큰 계산 7배, K≥300에서 컴파일 속도 2~6.5배
• •배치 256 기준 vLLM 처리량 219 req/s vs XGrammar 7.5 req/s(29배)
• •후보 1만개까지 100ms 이하 컴파일, 집합 크기와 무관한 일정한 스텝당 비용
• •100% 출력 유효성 보장