LLM에서 CFG 해석 진단

Diagnosing CFG Interpretation in LLMs

LLM이 에이전트 시스템에 점점 더 많이 통합됨에 따라, LLM은 동적으로 정의되고 기계가 해석할 수 있는 인터페이스를 준수해야 합니다. 본 연구에서는 LLM을 문맥 내 인터프리터로 평가합니다. 새로운 형식 문법이 주어졌을 때, LLM이 구문적으로 유효하고, 기능적으로 작동하며, 의미적으로 정확한 출력을 생성할 수 있는지 평가합니다. 우리는 RoboGrid라는 프레임워크를 소개합니다. RoboGrid는 재귀 깊이, 표현 복잡성 및 표면 스타일을 제어하는 스트레스 테스트를 통해 구문, 동작 및 의미를 분리합니다. 실험 결과, 일관된 계층적 성능 저하가 나타났습니다. LLM은 종종 표면 구문을 유지하지만, 구조적 의미를 보존하는 데 실패하는 경우가 많습니다. CoT(Chain-of-Thought) 추론을 통해 부분적으로 완화될 수 있지만, 구조적 밀도가 높을수록, 특히 깊은 재귀와 높은 분기에서 성능이 급격히 저하되며, 극단적인 깊이에서는 의미 일관성이 사라집니다. 또한, "Alien" 어휘를 사용하여 실험한 결과, LLM은 순수한 기호 유도가 아닌 키워드로부터의 의미적 부트스트래핑에 의존한다는 것을 알 수 있습니다. 이러한 결과는 신뢰할 수 있는, 문법에 구애받지 않는 에이전트를 위한 계층적 상태 추적에 필요한 중요한 격차를 보여줍니다.

As LLMs are increasingly integrated into agentic systems, they must adhere to dynamically defined, machine-interpretable interfaces. We evaluate LLMs as in-context interpreters: given a novel context-free grammar, can LLMs generate syntactically valid, behaviorally functional, and semantically faithful outputs? We introduce RoboGrid, a framework that disentangles syntax, behavior, and semantics through controlled stress-tests of recursion depth, expression complexity, and surface styles. Our experiments reveal a consistent hierarchical degradation: LLMs often maintain surface syntax but fail to preserve structural semantics. Despite the partial mitigation provided by CoT reasoning, performance collapses under structural density, specifically deep recursion and high branching, with semantic alignment vanishing at extreme depths. Furthermore, "Alien" lexicons reveal that LLMs rely on semantic bootstrapping from keywords rather than pure symbolic induction. These findings pinpoint critical gaps in hierarchical state-tracking required for reliable, grammar-agnostic agents.