Diagnosing CFG Interpretation in LLMs

Hanqi Li 1,4,5 Lu Chen 1,3,4,5 Kai Yu 1,2,4,5, [4pt] X-LANCE Lab, School of Computer Science, Shanghai Jiao Tong University, Shanghai, China · 2026

Read Diagnosing CFG Interpretation in LLMs by Hanqi Li 1,4,5 Lu Chen 1,3,4,5 Kai Yu 1,2,4,5, [4pt] X-LANCE Lab, School of Computer Science, Shanghai Jiao Tong University, Shanghai, China (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-20811.txt.

Introduction

Li, Chen, and Yu test large language models as in-context interpreters of a context-free grammar: can they make valid, functional, and faithful outputs? They present RoboGrid, a framework that splits syntax, behavior, and semantics through stress-tests of recursion depth, phrasing load, and surface styles. Their tests reveal a layered decline: models usually keep surface syntax yet lose structural meaning. Despite partial help from chain-of-thought, scores fail under structural crowding, namely deep recursion and high branching. Meaning match fades at extreme depths.

Catalog record

CREATORHanqi Li 1,4,5 Lu Chen 1,3,4,5 Kai Yu 1,2,4,5, [4pt] X-LANCE Lab, School of Computer Science, Shanghai Jiao Tong University, Shanghai, China
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48684
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.20811

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Diagnosing CFG Interpretation in LLMs Hanqi Li 1,4,5 Lu Chen 1,3,4,5 Kai Yu 1,2,4,5, [4pt] X-LANCE Lab, School of Computer Science, Shanghai Jiao Tong University, Shanghai, China Abstract 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. Figure 1: Architecture of the evaluation framework. It illustrates the transition from controllable synthesis of novel grammars to the hierarchical assessment of LLMs’ in-context interpretation capability. 1 Introduction Large language models (LLMs) are increasingly deployed as autonomous agents that interact with their environment through tool-calling ( 31 ) , API orchestration ( 7 ) , and the generation of domain-specific languages ( 13 ) . In these agentic workflows, the LLM’s output must conform to rigid, machine-interpretable interfaces ( 22 ) , such as JSON schemas or function signatures defined dynamically within the prompt ( 6 ) . This practical requirement implicitly asks LLMs to function as in-context grammar interpreters : given a novel context-free grammar (CFG) ( 3 ) specification at inference time, can a LLM produce outputs that are syntactically valid, behaviorally functional, and semantically faithful? While LLMs show apparent fluency in common languages like Python ( 10 ) , much of this competence may be attributable to extensive pre-training exposure ( 11 ) . This raises a fundamental challenge for agentic reliability: do LLMs truly internalize the formal logic of a provided grammar, or are they merely retrieving surface regularities from memory? In real-world tool-use, "almost correct" is insufficient ( 32 ) . A single missing delimiter or a logical misalignment in a nested loop can lead to catastrophic execution failure ( 5 ) . To build robust agents, we must understand the LLM’s capacity for systematic generalization : the ability to induce and apply structural rules from novel, in-context definitions without relying on familiar semantic cues. To rigorously investigate this, we propose a controlled evaluation hierarchy that disentangles grammar interpretation into three distinct layers: (1) Syntax Validity : Does the output conform to the CFG production rules? (2) Behavioral Equivalence : Does the executed program achieve the intended state change? (3) Semantic Correctness : Is the induced abstract syntax tree (AST) structurally identical to the ground-truth logic? This decomposition enables a fine-grained diagnosis of failure modes: whether a LLM fails due to syntactic fragility, planning errors, or a reliance on semantic anchors. We operationalize this hierarchy through three tasks: grammaticality judgment, goal-conditioned generation, and instruction-to-code generation, conducted within RoboGrid . RoboGrid is a deterministic grid-world environment designed to provide unambiguous execution semantics and a clear mapping between code and behavior, following recent trends in utilizing synthetic environments for precise behavioral evaluation ( 30 ) . Our framework supports systematic stress-testing across recursion depth, expression complexity, and surface realizations. Notably, we introduce " Alien " lexicons , which replace familiar keywords with opaque tokens, to force the LLM to rely exclusively on the provided grammar, thereby isolating pure symbolic reasoning from semantic priors. Through systematic experiments, we find that LLMs exhibit a consistent hierarchical degradation in grammar interpretation, where syntactic validity does not guarantee behavioral or semantic correctness under complex constraints. Specifically, even the strongest LLMs struggle with structural alignment, showing a significant gap between surface parsing and logical execution. Furthermore, our ablations reveal that performance is highly sensitive to recursion depth and lexical familiarity. Sharp non-linear decay occurs as depth increases, consistent with findings on the limitations of LLMs in maintaining deep reasoning chains ( 20 ) . The sharp decline in performance when using Alien tokens further indicates that LLMs struggle with pure symbolic induction once stripped of familiar lexical priors. In summary, our contributions are as follows: • We develop RoboGrid , a diagnostic benchmark that utilizes a three-layer evaluation hierarchy ( Syntax, Behavior, Semantics ) to localize failures in structural reasoning. • We formalize the task of in-context grammar interpretation for LLMs, shifting the evaluation focus from surface pattern matching to formal rule induction. • We characterize the operational limits of SOTA LLMs, revealing a massive gap between syntactic adherence and semantic alignment . While LLMs may follow formal rules at the surface level, their ability to maintain logical fidelity collapses as complexity increases, exposing a heavy reliance on semantic priors rather than pure symbolic induction. Category Parameter Conf. Space Evaluation Purpose Recursion Max Nesting Depth ( D ) \{2,\dots,20\} Probes hierarchical state tracking horizon Else-Branch Prob. ( p ) [0.0,1.0] Modulates control flow branching density Expression Expression Depth ( E ) \{1,2,3\} Controls nested arithmetic and boolean predicates Surface Syntactic Style { Block , C-style , S-expr } Tests robustness to structural delimiters Lexical Familiarity { Natural , Alien } Isolates syntactic reasoning from semantic priors Table 1: Controllable parameters for procedural data generation. By systematically varying these dimensions ( D,p,E ), we isolate specific aspects of grammar interpretation capability. 2 Preliminaries 2.1 RoboGrid Environment RoboGrid is a deterministic grid-world designed to decouple a LLM’s understanding of task logic from its adherence to formal syntax. In this environment, a robot navigates the grid to pick up objects which are then stored in its inventory. The robot maintains a state (\texttt{x},\texttt{y},\texttt{facing},\texttt{inventory}) , representing its 2D coordinates, orientation, and the collection of held items respectively. The instruction set is as follows: ⬇ Move ( dir , n ) # forward / backward n steps Turn ( dir ) # left / right 90 deg Grab ( item ) # pick up item | key | box Loop ( n , body ) # repeat body n times If ( cond , then , else ?) # conditional branch Holding ( item ) # state - query predicates And | Or | Not # logical operators 2.2 Grammar Specification via EBNF To interact with RoboGrid , LLMs must generate code conforming to a specific CFG provided in the prompt. We specify these grammars using Extended Backus-Naur Form (EBNF) ( 14 ) . A representative EBNF snippet for RoboGrid is shown below: ⬇ 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 DO : " exec " END : " end " LOOP : " loop " TIMES : " times " IF : " when " THEN : " after

Read the complete text