LLM의 CFG(Context-Free Grammar) 해석 능력 진단

Who Should Read

에이전트 시스템에서 LLM이 JSON 스키마, 함수 시그니처, DSL(도메인 특화 언어) 같은 구조화된 출력을 얼마나 믿을 수 있는지 궁금한 백엔드/ML 엔지니어. 특히 tool-calling이나 코드 생성 파이프라인의 안정성을 고민하는 개발자.

Core Mechanics

• LLM은 구문(Syntax) → 동작(Behavior) → 의미(Semantics) 순서로 계층적으로 성능이 무너진다. 문법 규칙은 어느 정도 따라도 실제 논리 구조는 틀리는 경우가 훨씬 많음.
• 재귀 깊이(nesting depth)가 깊어질수록 성능이 비선형적으로 급락한다. Mimo-V2-flash 기준 depth=2에서 SCR(의미 정확도) 39%였던 게 depth=20에서 0.5%로 거의 소멸.
• 모델 크기가 크다고 항상 잘하는 게 아님. GPT-5-mini가 Goal-Conditioned Generation Task에서 BER 90%로 더 큰 GPT-5.2(60%)를 크게 앞섬.
• 'Alien' 렉시콘(loop 같은 의미 있는 키워드 대신 v_xkqm 같은 무작위 토큰 사용)을 쓰면 성능이 급락함. LLM이 문법 규칙을 순수하게 추론하는 게 아니라 키워드의 의미에 기대고 있다는 증거.
• CoT(Chain-of-Thought) 추론은 필수적이지만 만능은 아님. CoT 없으면 depth=2에서도 SVR이 10% 미만으로 처참하지만, CoT를 켜도 depth=20에서는 SCR이 0.5%로 붕괴.
• Few-shot 예시를 늘려도 깊은 재귀 구조에서는 오히려 역효과. 0-shot 대비 1-shot이 성능이 더 낮고, 5-shot도 0-shot을 못 넘는 경우가 많음.

Evidence

• Alien 렉시콘 + depth=10 조건에서 가장 강한 오픈소스 모델 DeepSeek-V3.2의 Instruction-to-Code SCR은 39.5%에 불과. Qwen3-8B는 SCR 0%.
• GPT-5-mini는 Task 3에서 SVR 65%, CSCR(구문이 맞는 것 중 의미도 맞는 비율)이 9.23%로 의미 정렬이 거의 안 됨.
• 재귀 깊이 ablation: depth=2에서 SVR 42%, SCR 39%였던 게 depth=20에서 SVR 10%, SCR 0.5%로 폭락 (Mimo-V2-flash 기준).
• Else-branch 확률을 1.0으로 올리면(모든 if에 else 추가) SVR이 기준선 21.5%에서 13.0%로 40% 가까이 하락. S-expr 스타일로 바꾸면 SCR이 9%에서 4.5%로 절반 감소.

How to Apply

• LLM에게 동적으로 정의된 JSON 스키마나 함수 시그니처를 따르게 할 때, 중첩 깊이(nesting depth)를 최대한 얕게 설계하면 된다. depth가 깊어질수록 구조적 오류 확률이 비선형으로 증가하므로, 복잡한 스키마는 여러 단계로 나눠 호출하는 게 유리함.
• LLM tool-calling 에이전트에서 커스텀 DSL이나 새로운 문법을 프롬프트로 주입할 때 반드시 CoT를 활성화해야 한다. CoT 없이는 얕은 depth에서도 SVR이 10% 미만으로 떨어지므로, structured output 요청 시 'think step by step' 계열 지시를 포함시켜라.
• 새로운 문법의 키워드를 정할 때 가능하면 모델이 이미 아는 단어(loop, if, return 등)를 쓰는 게 낫다. 완전히 새로운 토큰을 쓰면 모델이 키워드 의미 유추에 실패해 성능이 크게 떨어짐(Natural vs Alien 비교: SVR 24.5% vs 21.5%, BER 21.5% vs 17.5%).

Code Example

# ROBOGRID 스타일로 LLM에게 새 문법을 따르게 하는 프롬프트 패턴
# CoT 활성화 + 명시적 EBNF 제공이 핵심

prompt = """
You are a strict code generator. Think step by step before generating code.

You are given a NEW programming language definition (EBNF):

start: stmt+
stmt: action_stmt | loop | if_stmt
action_stmt: DO action END
loop: LOOP INT TIMES LBR stmt+ RBR
if_stmt: IF cond THEN LBR stmt+ RBR (ELSE LBR stmt+ RBR)?
action: MOVE MOVE_DIR INT? | TURN TURN_DIR | GRAB ITEM
cond: HOLDING ITEM

Terminal mappings:
DO: "exec"  END: "stop"
LOOP: "repeat"  TIMES: "times"
IF: "when"  THEN: "then"
LBR: "{"  RBR: "}"

Instructions:
{natural_language_instruction}

First, break down the instruction into a tree structure (AST).
Then, translate each node into the grammar terminals above.
Finally, output the complete valid program.
"""

# 핵심 설계 원칙:
# 1. EBNF를 프롬프트 앞부분에 명시
# 2. CoT 유도 ('Think step by step' 또는 단계별 지시)
# 3. 중첩 깊이는 최대 5 이하로 제한 (depth>10이면 SCR 거의 0)
# 4. 키워드는 자연어에 가깝게 유지 (Alien 토큰 피하기)

Terminology