# Diagnosing CFG Interpretation in LLMs

arXiv: https://arxiv.org/abs/2604.20811 · HTML: https://mlsanity.com/paper/2604.20811/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 16 of its 29 references that are in the map.
- First posted on arXiv 22 Apr 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 16 of 16)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Survey on Evaluation of LLM-based Agents](https://mlsanity.com/paper/2503.16416/) (2025)
- [Physics of Language Models: Part 1, Learning Hierarchical Language Structures](https://mlsanity.com/paper/2305.13673/) (2023)
- [JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Models](https://mlsanity.com/paper/2501.10868/) (2025)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [The SWE-Bench Illusion: When State-of-the-Art LLMs Remember Instead of Reason](https://mlsanity.com/paper/2506.12286/) (2025)
- [Case-Based or Rule-Based: How Do Transformers Do the Math?](https://mlsanity.com/paper/2402.17709/) (2024)
- [Finite State Automata Inside Transformers with Chain-of-Thought: A Mechanistic Study on State Tracking](https://mlsanity.com/paper/2502.20129/) (2025)
- [Beyond Single-Task: Robust Multi-Task Length Generalization for LLMs](https://mlsanity.com/paper/2502.11525/) (2025)
- [Evaluating the Generalization Capabilities of Large Language Models on Code Reasoning](https://mlsanity.com/paper/2504.05518/) (2025)
- [TreeCoder: Systematic Exploration and Optimisation of Decoding and Constraints for LLM Code Generation](https://mlsanity.com/paper/2511.22277/) (2025)
- [RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Context](https://mlsanity.com/paper/2506.05205/) (2025)
- [The Gold Medals in an Empty Room: Diagnosing Metalinguistic Reasoning in LLMs with Camlang](https://mlsanity.com/paper/2509.00425/) (2025)
- [Anka: A Domain-Specific Language for Reliable LLM Code Generation](https://mlsanity.com/paper/2512.23214/) (2025)

## Built on by (most cited first, 1 of 1)

- [Protoreasoning in Tiny Transformers](https://mlsanity.com/paper/2608.04980/) (2026)

## Abstract (arXiv)

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.