RELIC: Evaluating Compositional Instruction Following via Language Recognition

Jackson Petty, Michael Y. Hu, Wentao Wang, Shauli Ravfogel, William Merrill, Tal Linzen

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

  1. Synthetic CFG Generation: Following Clark (2017), the framework stochastically generates context-free grammars in Chomsky Normal Form parameterized by:
  2. Terminal count ($n_{\text{term}}$)
  3. Nonterminal count ($n_{\text{nonterm}}$)
  4. Lexical production rules ($n_{\text{lex}}$, e.g., $NT_a \to \text{'t}_b\text{'}$)
  5. 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.

  6. 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 Yes or No indicating whether the grammar can generate the string.

  7. Complexity & Chain-of-Thought (CoT) Analysis:
  8. 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.
  9. 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.1 family, 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 o3 and o4-mini do not expose full, unredacted reasoning tokens, preventing detailed strategy classification on the latest frontier reasoning models.

Summary updated

Abstract

Large language models (LLMs) are increasingly expected to perform tasks based only on a specification of the task provided in context, without examples of inputs and outputs; this ability is referred to as instruction following. To evaluate models' ability to perform a task provided in context, we introduce the Recognition of Languages In-Context (RELIC) framework, where the task is to determine if a string is generated by a context-free grammar. This requires composing together a large number of instructions (grammar productions) retrieved from the context. Because the languages are synthetic, the task can be increased in complexity as LLMs' skills improve in the future, and new instances can be automatically generated, mitigating data contamination concerns. We evaluate state-of-the-art LLMs on RELIC and find that their accuracy can be reliably predicted from the complexity of the grammar and the individual example strings, and that even the most advanced LLMs currently available show near-chance performance on more complex grammars and samples, in line with theoretical expectations. We also analyze how LLMs attempt to solve increasingly difficult reasoning tasks, and find that as the complexity of the language recognition task increases, models switch from following complex instructions to relying on shallow heuristics.
BibTeX
@article{petty2026relic,
  author = {Jackson Petty and Michael Y. Hu and Wentao Wang and Shauli Ravfogel and William Merrill and Tal Linzen},
  title = {{RELIC: Evaluating Compositional Instruction Following via Language Recognition}},
  journal = {Trans. Assoc. Comput. Linguistics},
  year = {2026},
  doi = {10.1162/tacl.a.735},
}
Figure