Diagnosing CFG Interpretation in LLMs

• URL: http://arxiv.org/abs/2604.20811v1
• Date: Wed, 22 Apr 2026 17:43:05 GMT
• Title: Diagnosing CFG Interpretation in LLMs
• Abstract summary: Given a novel context-free grammar, can LLMs generate syntactically valid, behaviorally functional, and semantically faithful outputs?<n>We introduce RoboGrid, a framework that disentangles syntax, behavior, and semantics through controlled stress-tests of recursion depth, expression complexity, and surface styles.
• Score: 17.612748633265202
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Weave of Formal Thought [51.56484100374058]
  We introduce Weave of Formal Thought (WoFT), a paradigm uniting rigorous syntactic validation with learned structural representations.<n>We present a latent-variable fine-tuning method training the language model to interleave non-terminal grammar symbols directly into generation.<n>For Python, fine-tuning StarCoder2-3B with our RWS objective reduces per-token cross-entropy by 14.3% relative to a text-only SFT baseline.
  arXiv  Detail & Related papers  (2026-06-24T15:58:11Z)
• Matrix as Plan: Structured Logical Reasoning with Feedback-Driven Replanning [9.431480849387595]
  Chain-of-Thought prompting has been shown to enhance the reasoning capabilities of Large Language Models (LLMs)<n>Neuro-symbolic methods address this gap by enforcing formal correctness through external solvers.<n>We propose MatrixCoT, a structured CoT framework with a matrix-based plan.
  arXiv  Detail & Related papers  (2026-01-15T06:12:00Z)
• Improving LLM Reasoning with Homophily-aware Structural and Semantic Text-Attributed Graph Compression [55.51959317490934]
  Large language models (LLMs) have demonstrated promising capabilities in Text-Attributed Graph (TAG) understanding.<n>We argue that graphs inherently contain rich structural and semantic information, and that their effective exploitation can unlock potential gains in LLMs reasoning performance.<n>We propose Homophily-aware Structural and Semantic Compression for LLMs (HS2C), a framework centered on exploiting graph homophily.
  arXiv  Detail & Related papers  (2026-01-13T03:35:18Z)
• Last Layer Logits to Logic: Empowering LLMs with Logic-Consistent Structured Knowledge Reasoning [55.55968342644846]
  Large Language Models (LLMs) achieve excellent performance in natural language reasoning tasks through pre-training on vast unstructured text.<n>We propose the textitLogits-to-Logic framework, which incorporates logits strengthening and logits filtering as core modules to correct logical defects in LLM outputs.
  arXiv  Detail & Related papers  (2025-11-11T07:08:27Z)
• Computation Mechanism Behind LLM Position Generalization [59.013857707250814]
  Large language models (LLMs) exhibit flexibility in handling textual positions.<n>They can understand texts with position perturbations and generalize to longer texts.<n>This work connects the linguistic phenomenon with LLMs' computational mechanisms.
  arXiv  Detail & Related papers  (2025-03-17T15:47:37Z)
• Context-Alignment: Activating and Enhancing LLM Capabilities in Time Series [3.453940014682793]
  We propose Context-Alignment to align time series (TS) data with a linguistic component in language environments familiar to Large Language Models (LLMs)<n>Such context-level alignment comprises structural alignment and logical alignment, which is achieved by a Dual-Scale Context-Alignment GNNs (DSCA-GNNs)<n>Extensive experiments show the effectiveness of DECA and the importance of Context-Alignment across tasks, particularly in few-shot and zero-shot forecasting.
  arXiv  Detail & Related papers  (2025-01-07T12:40:35Z)
• Potential and Limitations of LLMs in Capturing Structured Semantics: A Case Study on SRL [78.80673954827773]
  Large Language Models (LLMs) play a crucial role in capturing structured semantics to enhance language understanding, improve interpretability, and reduce bias. We propose using Semantic Role Labeling (SRL) as a fundamental task to explore LLMs' ability to extract structured semantics. We find interesting potential: LLMs can indeed capture semantic structures, and scaling-up doesn't always mirror potential. We are surprised to discover that significant overlap in the errors is made by both LLMs and untrained humans, accounting for almost 30% of all errors.
  arXiv  Detail & Related papers  (2024-05-10T11:44:05Z)
• LMs: Understanding Code Syntax and Semantics for Code Analysis [25.508254718438636]
  We evaluate the capabilities of large language models (LLMs) and their limitations for code analysis in software engineering. We employ four state-of-the-art foundational models, GPT4, GPT3.5, StarCoder and CodeLlama-13b-instruct.
  arXiv  Detail & Related papers  (2023-05-20T08:43:49Z)
• Guiding the PLMs with Semantic Anchors as Intermediate Supervision: Towards Interpretable Semantic Parsing [57.11806632758607]
  We propose to incorporate the current pretrained language models with a hierarchical decoder network. By taking the first-principle structures as the semantic anchors, we propose two novel intermediate supervision tasks. We conduct intensive experiments on several semantic parsing benchmarks and demonstrate that our approach can consistently outperform the baselines.
  arXiv  Detail & Related papers  (2022-10-04T07:27:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.