Diagnosing CFG Interpretation in LLMs

Hanqi Li; Lu Chen; Kai Yu

cs.AIApr 22, 2026

Diagnosing CFG Interpretation in LLMs

Authors: Hanqi Li, Lu Chen, Kai Yu

Organizations: 1X-LANCE Lab, School of Computer Science, Shanghai Jiao Tong University, Shanghai, China · 3Shanghai Innovation Institution, Shanghai, China · 4Jiangsu Key Lab of Language Computing, Suzhou, China · 5Suzhou Laboratory, Suzhou, China · 2AISpeech Co., Ltd., Suzhou, 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.

Explore similar work

Measuring Intent Comprehension in LLMs
Jun 19, 2025Nadav Kunievsky, James A. Evans
Learning Context-Free Grammars for Grammar-Constrained Decoding via Declarative Agentic Programming with Guarantees
Aug 6, 2026Kevin Cheang, Geoff Hulette, Rahul Kumar +5Context-Free Grammars Domain-Specific Language
Can LLM Agents Infer World Models? Evidence from Agentic Automata Learning
Jun 15, 2026Reef Menaged, Gili Lior, Shauli Ravfogel +2Automata Large Reasoning Models

Jun 19, 2025 · cs.CLJ/K move · Enter open · S save

Measuring Intent Comprehension in LLMs

Nadav Kunievsky, James A. Evans

Knowlesdge Lab, University of Chicago, Chicago, Illinois, USA · Knowledge Lab, Data Science Institute, Department of Sociology, University of Chicago, Chicago, Illinois, USA.

People judge interactions with large language models (LLMs) as successful when outputs match what they want, not what they type. Yet LLMs are trained to predict the next token solely from text input, not underlying intent. Because written language is an imperfect proxy for intent, and correlations between phrasing and desired outcomes can break down in training data, models that rely too heavily on surface cues may respond inconsistently to semantically equivalent prompts. This makes it essential to evaluate whether LLMs can reliably infer user intent-especially in high-stakes settings where robustness and generalization are critical. We introduce a formal framework for assessing intent comprehension in LLMs: whether a model demonstrates robust understanding of user intent by producing consistent outputs across semantically equivalent prompts while differentiating between prompts with distinct intents. Our evaluation approach is based on a variance decomposition of model responses into three components: variability due to user intent, user articulation, and model uncertainty. Models that understand what users want, and are not overly sensitive to textual cues, should attribute most output variance to intent differences, rather than articulation style. Applying this framework across diverse domains, we find that, within the five LLaMA and Gemma models we evaluate, larger models typically assign a greater share of variance to intent, indicating stronger comprehension of intent, although gains are uneven and often modest with increasing model size. These results motivate moving beyond accuracy-only benchmarks toward semantic diagnostics that directly assess whether models understand what users intend.

Open paper Ask about it PDF

Abstract

Explore similar work

Measuring Intent Comprehension in LLMs

Learning Context-Free Grammars for Grammar-Constrained Decoding via Declarative Agentic Programming with Guarantees

Can LLM Agents Infer World Models? Evidence from Agentic Automata Learning