mlsanityData to 14 Oct 2026

Diagnosing CFG Interpretation in LLMs

arXiv 2604.20811 ↗First posted 22 Apr 2026cs.AIcited by 1

On the map: LLM agents and tool use → General LLM agent frameworks and benchmarks

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.

Key facts. Cited by 1 paper 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.

Builds on

16 of 29 references.

Closest ancestors · 1

Same direction, newest first

  1. 2025Survey on Evaluation of LLM-based Agents20 Mar

Other references · 15

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,695
  3. 2024LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Codecited by 2,004
  4. 2023Physics of Language Models: Part 1, Learning Hierarchical Language Structurescited by 83
  5. 2025JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Modelscited by 71
  6. 2024SynCode: LLM Generation with Grammar Augmentationcited by 69
  7. 2025The SWE-Bench Illusion: When State-of-the-Art LLMs Remember Instead of Reasoncited by 49
  8. 2024Case-Based or Rule-Based: How Do Transformers Do the Math?cited by 26
  9. 2025Finite State Automata Inside Transformers with Chain-of-Thought: A Mechanistic Study on State Trackingcited by 18
  10. 2025Beyond Single-Task: Robust Multi-Task Length Generalization for LLMscited by 7
  11. 2025Evaluating the Generalization Capabilities of Large Language Models on Code Reasoningcited by 7
  12. 2025TreeCoder: Systematic Exploration and Optimisation of Decoding and Constraints for LLM Code Generationcited by 5
3 more
  1. 2025RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Contextcited by 3
  2. 2025The Gold Medals in an Empty Room: Diagnosing Metalinguistic Reasoning in LLMs with Camlangcited by 3
  3. 2025Anka: A Domain-Specific Language for Reliable LLM Code Generationcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Protoreasoning in Tiny Transformerscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025LMR-BENCH: Evaluating LLM Agent's Ability on Reproducing Language Modeling Research
  2. 2026Toward Formalizing LLM-Based Agent Designs through Structural Context Modeling and Semantic Dynamics Analysis
  3. 2026A Comprehensive Evaluation of LLM Reasoning: From Single-Model to Multi-Agent Paradigms
  4. 2025LLMs Lean on Priors, Not Programming Language Semantics
  5. 2025Comprehension Without Competence: Architectural Limits of LLMs in Symbolic Computation and Reasoning
  6. 2024If LLM Is the Wizard, Then Code Is the Wand: A Survey on How Code Empowers Large Language Models to Serve as Intelligent Agents
  7. 2026LLMs Explain't: A Post-Mortem on Semantic Interpretability in Transformer Models
  8. 2024LLM2: Let Large Language Models Harness System 2 Reasoning