기술 요약: 디코드 타임 그래머 (Decode-Time Grammars)

1. 문제 정의

대규모 언어 모델(LLM)은 에이전트 및 서빙 시스템을 위한 코드를 생성하는 데 점점 더 많이 사용되고 있으며, 이 생성된 출력물은 인간의 검토 없이 컴파일되거나 실행됩니다. 이는 주류 언어에는 효과적이지만, 저자원 프로그래밍 표면(low-resource programming surfaces), 즉 도메인 특화 언어(DSL), 커스텀 라이브러리 API, 또는 명령줄 도구(CLI)와 같은 환경에서는 여전히 취약합니다.

이러한 환경에서 반복되는 실패 모드는 **고스트 레퍼런스(ghost reference)**입니다. 이는 구문론적으로는 유효한 토큰(예: 변수명, 컬럼, API 함수, 또는 CLI 옵션)이지만, 현재 런타임 환경 $\Gamma$에 존재하지 않는 것을 의미합니다.

• 예시: TileLang 커널에서 선언되지 않은 버퍼를 참조하거나, SQL 스키마에 없는 컬럼을 선택하거나, 특정 라이브러리 버전에서 사용할 수 없는 인트린직(intrinsic)을 호출하는 경우.
• 근본 원인: 이러한 오류는 대개 **부정적 전이(negative transfer)**에서 기인합니다. 즉, 모델이 대상 환경이 아닌 인접한 방언, 이전 API 버전, 또는 다른 도구 인터페이스의 지식을 적용할 때 발생합니다.
• 기존 해결책의 한계:
  • 고정된 그래머(Fixed Grammars): 표준 문법 제약 디코딩(예: CFG)은 구문적 유효성을 보장하지만, 참조 위치를 개방형 클래스(예: identifier)로 취급하여 유효한 이름과 유효하지 않은 이름을 모두 허용합니다.
  • 모델 측면의 해결책: 프롬프팅, 파인튜닝, 또는 재시도(retry) 메커니즘은 오류 확률을 줄일 수는 있지만, 모델의 서포트 셋(support set)에서 유효하지 않은 연속(continuations)을 제거할 수는 없습니다. 이는 모델이 올바른 경로를 "선호"하도록 만드는 데 의존하며, 잘못된 경로가 유창하고 높은 확률을 가질 때는 불충분합니다.

2. 방법론: 디코드 타임 그래머 (Decode-Time Grammars)

본 논문은 그래머 조각(grammar fragments)이 생성 과정 중에 런타임 환경 $\Gamma$를 기반으로 동적으로 인스턴스화되는 프레임워크인 디코드 타임 그래머를 소개합니다.

핵심 메커니즘

1. 런타임 환경 ($\Gamma$): 현재 상태의 스냅샷으로, 범위 내에 있는 이름(in-scope names), 타입(sorts), 형상(shapes), 스키마 엔트리, API 멤버 또는 도구 상태를 포함합니다. $\Gamma$는 생성되는 선언에 따라 진화합니다.
2. 그래머 조각 및 정제 순서 (Grammar Fragments & Refinement Order): 단일 고정 그래머 대신, 시스템은 정제(refinement)($\sqsubseteq$) 관계에 의해 정렬된 그래머 조각 라이브러리를 사용합니다.
   • 조각들은 거친(coarse) 단계(예: 모든 식별자 허용)부터 타이트한(tight) 단계(예: $\Gamma$에 선언된 이름만 허용)까지 다양합니다.
   • per-region 정책 $\pi(s, \Gamma)$는 예상되는 타입 $s$와 현재 환경을 기반으로 특정 "홀(hole)"(생성 과정 중의 타입ed 위치)에 적합한 조각을 선택합니다.
3. $\tau_\Gamma$ 연산자 (Tightening): 이것이 핵심 메커니즘입니다. 이 연산자는 조각 내의 개방형 참조 위치를 **$\Gamma$-타입 슬롯($\Gamma$-typed slot)**으로 변환합니다.
   • 슬롯의 후보 집합은 정확히 $\Gamma$에서 사용 가능한 이름들입니다 (예: Gamma.names(sort=Buffer)).
   • 이 후보들은 이스케이프 처리된 선택 구조(escaped alternation, 예: "A" | "B" | "C")로 컴파일되어, 해당 영역을 디코딩하기 전 토큰 레벨 인식기에 주입됩니다.
4. 자기 확장 생성 (Self-Extending Generation): 모델이 선언을 생성함에 따라, 추출된 선언들이 후속 참조 홀이 디코딩되기 전에 $\Gamma$에 추가됩니다. 이를 통해 참조가 이미 생성된 접두사(prefix)에 의해 제약되도록 보장합니다.

시스템 아키텍처

구현체인 gproj는 두 가지 구성 요소로 이루어집니다.

• TemplateInductor (오프라인): 작은 코퍼스에 대한 반-유니피케이션(anti-unification)을 사용하여 그래머 조각과 정책을 유도합니다. 이는 코퍼스의 positive 샘플과 자동 생성된 negative 샘플(발굴된 고스트 레퍼런스 포함)을 사용하여 "하드 게이트(hard gate)"에 대해 조각을 검증함으로써 실행 가능성과 정확성을 보장합니다.
• gproj Executor (온라인): $\Gamma$를 유지하고, 정책 $\pi$를 쿼리하며, $\tau_\Gamma$를 통해 조각을 인스턴스화하고, 결과 그래머를 LLM 디코더(예: XGrammar)를 위한 토큰 마스크로 컴파일하는 온라인 마스크드 실행기입니다.

3. 주요 기여 및 이론적 결과

이론적 기여

• 고스트 부재의 건전성 (No-Ghost Soundness): 참조 위치가 $\Gamma$-타입 슬롯으로 실현되는 모든 조각에 대해, 생성된 문자열은 **구조적으로 스코프 안전(scope-safe by construction)**함을 증명합니다. 출력되는 모든 참조는 반드시 $\text{dom}(\Gamma)$에 존재합니다.
• 정제 보존 (Refinement Preservation): 느슨한 조각이 건전하다면, $\tau_\Gamma$를 통한 모든 타이트한 정제 또한 이 건전성을 보존함을 증명합니다. 이를 통해 시스템은 오류를 재도입하지 않고도 동적으로 조각의 강도를 전환할 수 있습니다.
• 동적 서포트의 필요성 (Proposition 3): 고정된 참조 서포트를 가진 유한한 그래머 패밀리는 무한한 식별자 공간에 대해 건전성(고스트 레퍼런스 없음)과 비차단성(모든 유효한 연속 허용)을 동시에 만족할 수 없음을 증명합니다.
  • 시사점: 정확한 참조 서포트는 접두사를 기반으로 디코딩 중에 합성되어야 합니다. 정적 사전 컴파일은 선언 일관성이 있는 언어에 대해 이론적으로 불충분합니다.

실무적 기여

• 역할 분담: 이 접근 방식는 환경에 종속된 정확성(마스크가 처리)과 개방형 프로그램 결정(모델이 처리)을 분리합니다. 마스크는 참조가 유효함을 보장하고, 모델은 알고리즘, 전략 또는 의도를 선택합니다.
• 유도 파이프라인 (Induction Pipeline): 작은 코퍼스로부터 필요한 그래머 조각과 정책을 자동으로 생성하는 방법을 제공하여, 수동적인 그래머 엔지니어링 없이도 새로운 DSL에 적용할 수 있게 합니다.

4. 평가 결과

시스템은 TileLang(텐서 커널 DSL), SQL(Spider 데이터셋), P4(데이터 평면 언어), 그리고 CLI 도구(git, FFmpeg)를 대상으로 0.6B에서 236B 파라미터에 이르는 모델들을 사용하여 평가되었습니다.

• 고스트 레퍼런스 제거:
  • 모든 표면에서, $\Gamma$-타입 암(arm)( $\tau_\Gamma$ 사용)은 구조적으로 0%의 고스트 레퍼스를 달성했습니다.
  • 반면, 개방형 식별자 암(자유 디코딩)은 모델 크기(0.6B ~ 236B)와 상관없이 TileLang, SQL, P4에서 100%의 경우에 고스트 레퍼런스로 인한 실패를 보였습니다.
  • 예시: SQL에서 개방형 식별자는 0%의 실행 매치를 보였으나, $\Gamma$-제약 디코딩은 100%를 달성했습니다.
• 모델 독립성: 이 보장은 모델 크기에 관계없이 전이됩니다. 236B 규모의 프런티어 모델(DeepSeek-V4-Flash)조차 마스크 없이는 유효한 참조를 생성하는 데 실패했으나, 0.6B 모델은 마스크와 함께 성공했습니다.
• 대안과의 비교:
  • 프롬프팅/재시도: SQL에서 스키마를 포함한 프롬프팅과 4회까지의 재시도는 90%의 실행 매치를 달성했지만, 여전히 5개의 고스트 컬럼을 생성했습니다. 마스크는 단 한 번의 패스로 0개의 고스트와 함께 100% 매치를 달성했습니다.
  • 비용: 이 방식은 중간 정도의 오버 overhead를 발생시킵니다. 비제약 디코딩 대비 엔드 투 엔드 처리량 감소는 평균 **17.3%**였습니다. 표준 제약 디코딩(XGrammar) 대비 gproj의 처리량 감소는 **10.6~17.8%**였습니다.
• 오프라인 유도: TemplateInductor는 수동으로 작성되지 않은 복잡한 표면(예: AscendC 연산자, FFmpeg 필터)에 대해 유효한 조각을 성공적으로 유도하여, "유도 + 하드 게이트" 워크플로우를 검증했습니다.

5. 의의 및 주장

본 논문은 디코드 타임 그래머가 모델의 능력과는 별개로 정밀하고 안정적인 정확성의 슬라이스를 제공한다고 주장합니다.

• 기계적 보장: 이는 참조 안전성을 모델 품질에 의존하는 확률적 결과에서 구조적 수준의 보장으로 변환합니다.
• 확장성: "의미적 스케치"(모델의 역할)와 "환경 종속적 참조"(마스크의 역할)를 분리함으로써, 시스템은 모델이 그렇지 않았다면 환각을 일으켰을 저자원 환경에서도 유효한 코드를 생성할 수 있게 합니다.
• 이론적 필요성: 정적 그래머가 선언 일관성이 있는 언어에 대해 건전성과 비차단성을 동시에 만족할 수 없다는 증명은, 제안된 런타임 인스턴스화 방식의 필요성을 확립합니다.

저자들은 이 연구를 프로그램 전체의 의미적 정확성(예: 알고리즘 로직 또는 종료성)을 위한 솔루션이 아니라, 제약된 환경의 코드 생성에서 문제를 일으키는 특정 클래스의 기계적으로 열거 가능한 오류(정의되지 않은 심볼)를 제거하기 위한 강력한 메커즘으로 포지셔닝합니다.