기술 요약: GRID (기업용 SQL을 위한 문법 가드레일 디코딩)

1. 문제 정의

본 논문은 대규모 언어 모델(LLM)이 생성하는 "그럴듯한" 텍스트와 기업용 SQL 생성의 엄격한 요구사항 사이의 간극을 다룹다. 기업의 CRUD/RBAC(역할 기반 액세스 제어) 배포 환경에서 출력물은 구문적으로 유효해야 하며, 역할별 및 스키마별 정책을 준수해야 하고, 사후 필터링이 아닌 설계 단계부터 보장된 결과를 제공해야 한다. 저자들은 기존 솔루션들이 동시에 해결하지 못하는 여섯 가지 핵심 과제를 식별하였다:

1. 유효성 및 정책의 결합: 출력물은 특정 SQL 방언(dialect) 하에서 파싱되어야 할 뿐만 아니라, 역할 기반의 동사 제한 및 스키마 특정 어휘(실제 테이블/컬럼)를 사후 필터링이 아닌 구조적으로 엄격히 준수해야 한다.
2. 증명 가능한 보장: 시스템은 특정 테스트를 통해 검증된 건전성(invalid token을 절대 방출하지 않음), 완결성(유효한 연속성을 차단하지 않음), 그리고 종료(termination)에 대한 공식적인 정리를 제공해야 한다.
3. 토큰당 평탄한 비용 (요구사항 R): "가드레일"(마스킹)의 비용은 생성 길이 $n$과 무관하게 토큰당 $O(1)$로 분할 상환되어야 한다. 기존 시스템은 종종 컨텍스트 길이에 따라 선형 또는 이차적으로 증가하는 비용 문제를 겪는다.
4. 재현 가능한 감사 추적(Audit Trail): 컴플라이언스를 위해 모든 허용/차단 결정에 대해 해시 체인으로 연결된 비트 단위로 동일한 기록을 남겨, 사후에 "무엇이 왜 허용되었는지"에 답할 수 있어야 한다.
5. 서빙 현실성: 프로덕션 환경은 배치 처리된 이질적인 요청들을 포함한다. 시스템은 "콜드 스키마(cold-schema)" 도착(이전에 본 적 없는 새로운 스키마) 시에도 워밍 상태의 공동 배치(co-batched) 요청을 중단시키거나 근사적인 마스크로 대체하지 않고 처리해야 한다.
6. 정직한 경계: 시스템은 좌측-우측 컨텍스트 프리(left-to-right context-free) 마스크로 강제할 수 없는 것(특히 컬럼 수준의 RBAC)을 명시적으로 인정하고, 이러한 잔여물을 처리하기 위한 메커니즘을 제공해야 한다.

2. 방법론: 문법 가드레일 디코딩

GRID는 모든 것이 토큰 시퀀스가 아닌 **파서 설정(parser configurations)**에 키잉(keying)되는 새로운 아키텍처를 도입한다.

핵심 아키텍처 아이디어

토큰 시퀀스에 대해 조합론적으로 확장되는 유효성 테이블을 사전 계산하는 대신, GRID는 모든 마스크, 캐시 엔트리, 감사 기록을 파서 설정에 키잉한다. 설정 $\kappa$는 다음 쌍 $(\sigma, \rho)$로 정의된다:

• $\sigma$: LALR(1) 파서 스택.
• $\rho$: 현재 부분 렉셈(lexeme)에 대한 렉서 스캔 상태(잔여 바이트).

이 설정은 유효한 접두사(viable prefixes, 유효한 문장으로 이어질 수 있는 연속성)의 집합을 고유하게 결정한다.

주요 구성 요소

• 유효 접두사 오라클(Viable-Prefix Oracle): 증분형 LALR(1) 파서 자체가 오라클 역할을 한다. 가상 스택 상에서 리듀스 체인(reduce chain)을 시뮬레이션함으로써, 시스템은 허용된 터미널(terminals)의 집합을 결정한다. 이는 단일 토큰 접두사가 전체 문장이 아니라는 이유로 거부될 수 있는 "수용 세맨틱 데드락(acceptance semantics deadlock)"을 방지한다.
• 토큰-터미널 브릿지(Token-Terminal Bridge): LLM 토큰(바이트 문자열)은 문법 렉셈과 일치하지 않으므로, GRID는 **바이트 레벨 트리 워크(byte-level trie walk)**를 사용한다.
  • 컨텍스트 독립적(CI) 토큰: 현재 렉셈 내에서 해결되거나 터미널 경계에서 정확히 끝나는 토큰들이다. 이들은 캐싱 가능하다.
  • 컨텍스트 의존적(CD) 토큰: 터미널 경계를 가로지르는 토큰들(예: 키워드를 완성하고 새로운 키워드를 시작하는 경우)이다. 이들은 절대 캐싱되지 않으며, 건전성을 보장하기 위해 매 단계마다 라이브 스택과 대조된다.
• 정책 컴파일:
  • 역할 프로젝션 (L2): 문법 생성(productions)의 부분 집합을 추출한다(예: DELETE 동사 제거).
  • 스키마 렉시콘 (L3): 데이터베이스 카탈로그에서 유도된 허용 목록으로 식별자 터미널을 제한한다.
  • 식별자 구성 규칙: 식별자 위치에서 마스크는 토큰 트리와 스키마 렉시콘 트리의 교집합으로부터 엄격하게 유도되어, 일반적인 캐시 엔트리가 금지된 식별자를 허용하는 것을 방지한다.
• 캐싱 전략 (OBL-KEY1): 두 단계의 쓰기 백(write-back) 캐시(T1은 특정 문법용, T2는 공유 문법 패밀리용)를 사용하며, 설정 기반 키를 사용한다. 시스템은 "Myhill–Nerode 스타일의 정교화"를 강제하여, 동일한 키를 공유하는 임의의 두 설정은 반드시 비트 단위로 동일한 CI 마스크를 생성해야 한다.
• 감사 체인(Audit Chain): 각 단계는 BLAKE2b를 통해 체이닝된 기록(단계, 설정 해시, 마스크 엔트리 ID, 토큰, 차단 횟수)을 추가한다. 이를 통해 생성 과정에 대한 비트 단위로 동일한 재현이 가능하다.

시스템 구현

• Rust 커널: 지연 시간을 최소나화하고 Python GIL을 해제하기 위해 핫 패스(trie walk, CD 판정, LALR 전진, 비트마스크 채우기)를 Rust로 구현하였다.
• 서빙 계약 (vLLM): 시스템은 CPU에서의 마스크 계산을 GPU 포워드 패스와 오버랩시킨다. 만약 콜드 스키마 요청의 마스크가 준비되지 않은 경우, 이를 한 라운드 동안 지연시켜 공동 배치된 워밍 상태의 요청들이 중단되지 않도록 보장한다.
• 체커 가이드 리페어(Checker-Guided Repair): 마스크가 강제할 수 없는 잔여물(컬럼 수준 RBAC)을 위해, 시스템은 사후 파스(post-parse) 시맨틱 체커를 사용한다. 위반이 감지되면, 시스템은 쿼리를 수정하기 위한 리페어 패스를 가이드할 수 있다.

3. 주요 기여

1. 공식 프레임워크: 증분형 LALR(1) 파서를 유효 접두사 오라클로 사용하는 설정 키잉 방식의 제약 디코딩 프레임워크를 제시하였으며, 바이트 레벨의 토큰-터미널 브릿지와 컨텍스트 독립/의존 분리를 포함한다.
2. 증명 가능한 보장: 명시적인 전제 조건과 함께 기술된 네 가지 보장(건전성, 완결성, 종료, 평탄한 비용)을 특정 테스트를 통한 검증과 함께 제시하였다.
3. 시스템 실현: 문법 파이프라인, Rust 커널, 2단계 캐시, 해시 체인 감사 로그를 특징으로 하는 프로덕션 준비 단계의 시스템(v4–v7 커널)을 구현하였다.
4. 벤치마크 기록: 토큰당 지연 시간, 요구사항 R 기울기 측정, MaskBench (JSON Schema), Spider 실행 정확도, 그리고 엔드 투 엔드 vLLM 서빙 기록을 포함한 종합적인 평가를 수행하였다.

4. 결과

• 지연 시간: H100 SXM5 러너에서, GRID는 gpt2 및 Qwen 토크나이저 모두에서 llguidance와 XGrammar보다 p50 및 p90에서 우수한 3.6–6.7 µs(p50) 및 80–109 µs(p90)의 중앙값 토큰당 마스크 지연 시간을 달성하였다. llguidance는 가장 평탄한 p99 테일을 유지하였다.
• 요구사항 R (평탄한 비용): $n=16,000$ 토큰에서, 토큰당 비용 기울기는 사실상 0($\approx 0$)이며, 이는 $O(1)$ 암드 비용을 확인해준다. 반면, 이전 버전의 가이던스는 이차적 성장을 보였다.
• 실행 정확도 (Spider):
  • 0.5B 모델: 제약 디코딩만으로 비제약 생성 대비 +13 실행 정확도(EX) 포인트를 획득하였다 (16.0% 대비 29.0%).
  • 7B 모델: 마스크 자체는 약 +1 포인트를 제공한다. 그러나 체커 가이드 리페어 패스를 추가하여 컬럼 수준 위반을 처리하면 실행 정확도가 94.5%(비제약 대비 +2.3)까지 상승한다.
• 서빙 오버헤드: vLLM 환경에서 배치 크기 32일 때, 오버헤드는 출력 토큰당 시간 **+1.51%**이다.
• 콜드 스타트 처리: 새로운 스키마는 약 27.3 ms의 특수화 시간과 약 0.7 ms의 첫 토큰 지연 시간을 발생시킨다. 이로 인해 특수화 윈도우 동안 공동 배치된 워밍 요청에 대해 약 ~34%의 일시적 속도 저하가 발생하지만(CPU/메모리 대역폭 경합 때문), 워밍 요청은 결코 중단되지 않으며, 이후의 신규 요청은 1.00× 워밍 속도로 실행된다.
• 감사 무결성: 1,000회의 생성을 재현한 결과, 100%의 탐지율로 비트 단위로 동일하게 재현됨을 확인하였다.

5. 의의 및 정직한 경계

본 논문은 **설정 키잉 디코딩(configuration-keyed decoding)**을 채택함으로써 엔터프라이즈급 제약 디코딩이 가능하다는 것을 입증하였다. 이 단일한 결정은 정책 컴파일, 증명 가능한 보장, 평탄한 비용, 그리고 재현 가능한 감사를 가능하게 한다.

저자들은 시스템의 한계와 경계를 명확히 밝히고 있다:

• 분포 충실도(Distribution Faithfulness): 본 논문은 마스킹이 원래 확률 분포 $P(x | x \in L)$를 보존한다고 주장하지 않으며, 국소적으로 재정규화한다. 영향력은 분포적 중립성이 아닌 다운스트림 실행 정확도를 통해 측정된다.
• 컬럼 수준 RBAC: 저자들은 (명제 11) 컬럼 수준의 제한은 필요한 별칭-테이블 바인딩을 알 수 없기 때문에 좌측-우측 CFG 마스크로 강제할 수 없음을 증명하였다. 이는 마스크가 아닌 사후 파스 체크 및 리페어를 통해 처리된다.
• 언어 범위: 시스템은 LALR(1) 언어로 제한된다. 표준 SQL 방언은 처리하지만, 비 LALR(1) 구조(예: 특정 JSON Schema 패턴)에 대해서는 컴파일 에러를 선언한다.
• 콜드 윈도우 경합: 새로운 스키마의 특수화 과정 중 발생하는 공동 배치 요청의 일시적 속도 저하는 소프트웨어 결함이 아닌 실제 호스트 CPU/메모리 대역폭 경합 문제임을 인정하며, 이는 컴퓨팅 격리(compute-isolation)의 트레이드오프를 나타낸다.
• 종료(Termination): 완전한 종료 보장(reserve-completed stops)은 GRID 소유의 디코드 루프 내에서만 유효하며, 프로세서 전용 서빙 모드에서는 절단될 수 있다.

요약하자면, GRID는 설정 키잉 디코딩을 통해 엔터프라이즈급 SQL 생성을 위한 고성능 프레임워크를 제공하며, 정확성, 정책 강제, 그리고 감사 가능성을 우선시하는 동시에, 문법 마스킹을 통해 강제할 수 있는 것의 한계를 정직하게 구분 짓는다.