TL;DR
RELIC (Recognition of Languages In-Context) is a new synthetic benchmark designed to evaluate how well large language models (LLMs) execute complex, compositional instructions provided strictly in-context. By framing instruction following as recognizing whether a string belongs to a context-free grammar (CFG), the authors show that even frontier reasoning models like OpenAI’s o3 collapse to near-chance accuracy as grammar size and string length grow. Qualitative inspection reveals a clear failure mode: as problems become computationally difficult, models abandon systematic parsing and revert to shallow, unsound heuristics.
What Problem Does This Paper Address?
Real-world instruction following requires composing multiple interacting rules retrieved entirely from context—for example, parsing multi-step business logic from documentation or auditing credit card statements across multiple criteria. However, most existing instruction-following benchmarks (such as IFEval) evaluate shallow surface constraints (e.g., "do not use commas" or "keep response under 200 words"). Furthermore, static natural language benchmarks inevitably suffer from data contamination and saturation over time.
Prior formal language investigations either focused on simpler regular languages or required fine-tuning the models. The authors ask: Can modern LLMs perform zero-shot, in-context recognition of context-free languages (CFLs)? CFLs represent a much richer computational class that requires dynamic, hierarchical rule composition.
Methods
- Synthetic CFG Generation: Following Clark (2017), the framework stochastically generates context-free grammars in Chomsky Normal Form parameterized by:
- Terminal count ($n_{\text{term}}$)
- Nonterminal count ($n_{\text{nonterm}}$)
- Lexical production rules ($n_{\text{lex}}$, e.g., $NT_a \to \text{'t}_b\text{'}$)
-
Non-lexical production rules ($n_{\text{nonlex}}$, e.g., $NT_a \to NT_b\ NT_c$) Grammars are trimmed of dead and inaccessible rules to ensure validity.
-
Task Framing: In a pure zero-shot setting, the model receives the grammar rules and a target string in its context window and must output
YesorNoindicating whether the grammar can generate the string. - Complexity & Chain-of-Thought (CoT) Analysis:
- Context-free parsing is theoretically in $\text{AC}^1$ and $\text{NC}^1$-hard, with standard parsers requiring $\Theta(n^3)$ operations. To parse long strings correctly, transformers require test-time compute (TTC) to scale superlinearly with input length.
- The authors track generated completion token counts across string lengths and use an LLM-as-a-judge (
o4-mini, validated against human annotators) to categorize reasoning traces into rule-based (exhaustive search/derivations) versus heuristic (relying on surface patterns) strategies.
Datasets
The authors introduce RELIC-500, an open-source evaluation benchmark consisting of:
- 200 sampled CFGs where all parameters ($n_{\text{term}}, n_{\text{nonterm}}, n_{\text{lex}}, n_{\text{nonlex}}$) are $\le 500$, chosen to minimize correlation across hyperparameters.
- Up to 10 positive strings (sampled from each grammar viewed as a PCFG) and 10 negative strings (sampled from a terminal unigram model and rejected if parseable) for every length $\ell \in [1, 50]$.
- A procedural data-generation pipeline that can synthesize unlimited new grammars and samples on the fly, eliminating benchmark saturation and training data contamination.
Key Insights and Ideas
- The Test-Time Compute Collapse: While theory dictates that parsing longer strings requires substantially more reasoning tokens, models actually expend less test-time compute as strings get longer. Completion length peaks early (between lengths 4 and 12) and then steadily decreases.
- The Heuristic Retreat: When the state space explodes, models stop attempting rigorous step-by-step parsing. Instead of running out of context while systematically constructing parse trees, models actively switch to flawed shortcuts—such as checking whether individual tokens exist anywhere in the grammar, or guessing based on token co-occurrence.
- Branching Rules Drive Failure: Grammar difficulty is primarily dictated by the number of non-lexical production rules ($n_{\text{nonlex}}$). Model performance exhibits a steep, log-linear decline specifically against $n_{\text{nonlex}}$.
Key Results
The authors evaluated eight models: OpenAI's gpt-4.1-nano, gpt-4.1-mini, gpt-4.1, o4-mini, and o3; Google's gemma-3-1b-it and gemma-3-4b-it; and DeepSeek-R1-Distill-Qwen-7B.
- Near-Perfect on Toys, Chance on Scale: Nearly all models achieve near 100% accuracy on tiny grammars and very short strings ($\ell \le 5$). However, performance collapses toward chance (50%) by string lengths $\ell \approx 15$, and drops to chance as $n_{\text{nonlex}} \to 500$.
- Frontier Reasoning Models Struggle: Even OpenAI’s flagship reasoning model o3 plummets to near-chance accuracy on the benchmark's larger grammars.
- Statistical Significance: Regression modeling confirms that both $\log_{10}(n_{\text{nonlex}})$ and string length $\log_{10}(\ell)$ have massive, highly statistically significant negative effects on accuracy ($p < 0.001$).
- Strategy Shift: For the
gpt-4.1family, rule-based reasoning dominates on short lengths ($\ell \le 6$), but drops to nearly 0% on lengths $\ell \ge 20$, replaced almost entirely by heuristic guessing.
Limitations and Future Work
- Synthetic vs. Natural Semantics: Synthetic grammars strip out natural language redundancy and commonsense priors. While this is intentional to isolate mechanical instruction-following, real-world tasks often provide semantic clues that models exploit.
- Lack of External Tools/Scratchpads: Models were evaluated purely via prompt generation. Future work could test whether allowing models to write and execute programmatic parsers (e.g., Python code execution in an environment) bridges the gap.
- Black-Box CoT Constraints: Proprietary models like
o3ando4-minido not expose full, unredacted reasoning tokens, preventing detailed strategy classification on the latest frontier reasoning models.
Summary updated