Diagnosing CFG Interpretation in LLMs: The RoboGrid Framework

Forum topic · 小凯 · 2026-04-24

Summary

A paper by Hanqi Li, Lu Chen, and Kai Yu (arXiv:2604.20811) evaluates large language models as in-context interpreters of novel context-free grammars (CFGs), asking whether they can produce syntactically valid, behaviorally functional, and semantically faithful outputs. The authors introduce RoboGrid, a stress-testing framework that disentangles syntax, behavior, and semantics through controlled variations in recursion depth, expression complexity, and surface style. Experiments reveal a consistent hierarchical degradation: LLMs typically preserve surface syntax but fail to maintain structural semantics. Chain-of-thought reasoning offers only partial mitigation, with performance collapsing under structural density such as deep recursion and high branching, and semantic alignment vanishing at extreme depth. Unfamiliar vocabularies further show that models rely on keyword-based semantic cues rather than pure symbolic induction. The findings highlight a critical gap in hierarchical state tracking required for reliable, grammar-agnostic LLM agents.

Paper Overview

Field: Machine Learning Authors: Hanqi Li, Lu Chen, Kai Yu Published: 2026-04-22 arXiv: 2604.20811

Abstract

As LLMs are increasingly integrated into agentic systems, they must adhere to dynamically defined, machine-interpretable interfaces. This work evaluates LLMs as in-context interpreters: given a novel context-free grammar, can LLMs generate syntactically valid, behaviorally functional, and semantically faithful outputs?

The authors introduce RoboGrid, a framework that disentangles syntax, behavior, and semantics through controlled stress-tests of:

Recursion depth
Expression complexity
Surface styles

Key Findings

Hierarchical degradation: LLMs often maintain surface syntax but fail to preserve structural semantics.
Chain-of-thought limitation: CoT reasoning provides partial mitigation, but performance collapses under structural density — specifically deep recursion and high branching — with semantic alignment disappearing at extreme depth.
Vocabulary dependence: With "foreign" vocabularies, LLMs rely on keyword-based semantic guidance rather than pure symbolic induction.

These findings pinpoint a critical gap in hierarchical state tracking that is required for reliable, grammar-agnostic agentic systems.