RELIC : Evaluating Compositional Instruction Following via Language Recognition
Jackson Petty λ \lambda, Michael Y. Hu δ \delta, Wentao Wang δ \delta, William Merrill δ \delta, Tal Linzen λ \lambda δ \delta, Center for Data Science δ \delta · 2025
Read RELIC : Evaluating Compositional Instruction Following via Language Recognition by Jackson Petty λ \lambda, Michael Y. Hu δ \delta, Wentao Wang δ \delta, William Merrill δ \delta, Tal Linzen λ \lambda δ \delta, Center for Data Science δ \delta (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-05205.txt.
Introduction
Jackson Petty and co-authors built a test of complex reasoning for language models in two thousand twenty-five. The test, called RELIC, gives a model a grammar in its prompt and asks if a string fits the language that grammar defines. Grammar size and string length can be raised to make the task harder.
Even top reasoning models did poorly as tasks grew harder. They did not spend more effort to keep up; they spent less, using fewer reasoning tokens. Their style also shifted from working out a step-by-step method to guessing. The authors call that shift a form of quiet quitting on hard tasks, which would stay hidden if only final answers were checked.
Catalog record
| CREATOR | Jackson Petty λ \lambda, Michael Y. Hu δ \delta, Wentao Wang δ \delta, William Merrill δ \delta, Tal Linzen λ \lambda δ \delta, Center for Data Science δ \delta |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-05205
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
RELIC : Evaluating Compositional Instruction Following via Language Recognition Jackson Petty λ \lambda, Michael Y. Hu δ \delta, Wentao Wang δ \delta, William Merrill δ \delta, Tal Linzen λ \lambda δ \delta, Center for Data Science δ \delta 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. We introduce the Recognition of Languages In-Context ( RELIC ) framework to evaluate instruction following using language recognition: the task of determining if a string is generated by formal grammar. Unlike many standard evaluations of LLMs’ ability to use their context, this task 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, and new instances can be automatically generated, mitigating data contamination. 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 use RELIC to diagnose how LLMs attempt to solve increasingly difficult reasoning tasks, finding that as the complexity of the language recognition task increases, models switch to relying on shallow heuristics instead of following complex instructions. Figure 1: RELIC is an evaluation framework for compositional instruction following , where we (a) stochastically generate context-free grammars (e.g., sets of instructions) of given complexities, (b) sample positive and negative strings (e.g., tasks) for each grammar, and (c) prompt models to classify whether the strings are generated by those grammars. 1 Introduction Large language models (LLMs) are increasingly expected to solve tasks “zero-shot,” using only a specification of the task provided in the LLM’s context window without examples of inputs and outputs or any additional training. These instructions are often compositional , involving the interaction of multiple rules or constraints. Even a simple question such as “using my credit card statement, tell me if I spent more money in 2025 than I did on average in the past three years” (inspired by Zhou et al. 2024 ) requires an LLM to retrieve a large number of items from its context and perform multiple operations in a particular sequence (in this example, summing and averaging them and comparing the outputs). As the complexity of such instructions increases, the system needs to use its context in a sophisticated way to identify the relevant instructions and combine them appropriately. The importance of compositional instruction following highlights the need for a reliable benchmark with controllable complexity that can measure LLMs’ abilities in this area as they improve in the future. To this end, we propose the Recognition of Languages In-Context ( RELIC ) framework, which evaluates if the model can determine whether a given string is derivable from a grammar describing a formal language; to succeed, the model needs to apply multiple rules in an order that is not provided in advance, potentially applying each rule multiple times as a complex compositional tree, which we take as a proxy for instruction following more generally. This task is akin to determining if a sentence is grammatical given a reference grammar for a natural language, or if a program is syntactically correct given a specification of the programming language. RELIC is a data generating process that stochastically samples new grammars of desired complexity and produces unlimited amounts of new evaluation examples for these grammars; this property of the benchmark addresses issues of data contamination and benchmark saturation which plague static benchmarks. We focus on grammars of context-free languages (CFLs), which mimic key aspects of the compositional structure of both natural languages [ Chomsky and Schützenberger 1963 ] and programming languages. The context-free grammars we generate consist of production rules of two kinds: \texttt{A}\to\texttt{B}\ \texttt{C} , where A , B , and C are nonterminal symbols; and \texttt{A}\to\texttt{`t'} , where t is a vocabulary symbol. For each grammar, we sample positive strings from the grammar and negative strings from the vocabulary, and prompt an LLM to determine whether the strings can be generated by the grammar. The difficulty of the task can be modulated by varying the size of the grammar and the length of the strings that need to be recognized. Because the asymptotic computational complexity of in-context CFL recognition is likely beyond the capabilities of transformers [ Greenlaw et al. 1991 , Merrill and Sabharwal 2023 ] , we expect this task to be challenging for transformer-based LLMs, which may motivate new architectures. Using this framework, we generate and release a first static benchmark, RELIC -500, which consists of 200 grammars which vary in complexity (up to 500 nonterminal production rules), and sets of positive and negative examples for each grammar (of lengths up to 50 symbols). We evaluate a range of LLMs on RELIC -500, including smaller open-weights models (Gemma 3 and a distilled version of DeepSeek-R1) and models from OpenAI ( o3 , o4-mini and the gpt-4.1 family). Most of the models performed substantially above chance on simpler grammars, indicating an understanding of the general structure of the task; but all models, including OpenAI’s most advanced reasoning model o3 , had near-chance accuracy on the larger grammars, which are still orders of magnitude smaller than the grammars needed to define commonly-used programming languages or approximate human languages. In a qualitative analysis of the chain-of-thought tokens that LLMs produce before providing their response, we find that in many cases models rely on incorrect heuristics; quantitative analysis of these tokens shows that the amount of tokens does not grow as would be expected from the correct strategy to perform the task. These results motivate using RELIC to assess LLMs’ compositional instruction following capabilities, and indicate substantial headroom on this task. More generally, our findings illustrate the potential for using formal languages to produce evaluation datasets that are resistant to data contamination, and whose complexity can be precisely controlled and scaled as LLMs’ capabilities improve. 2 Related Work 2.1 Evaluating In-Context Instruction Following LLMs are typically fine-tuned to follow instructions (i.e. specifications of the task provided in context), and can generalize this skill to new instructions that were not included in fine-tuning [ Sanh et al. 2022 , Wei et al. 2022 ] . It is often difficult, however, to automatically verify whether the model indeed followed the instructions; this concern is addressed in our formal language recognition setting. Like our work, the IFEval benchmark [ Zhou et al. 2023 ] addresses the verification issue by placing formal constraints on the output (e.g., avoiding commas), but it does not evaluate complex and long instructions as we do. Our focus on evaluating compositionality is also related to work on compositionality in question answering [ Dziri et al. 2023 , Press et al. 2023 ] and semantic parsing [ Kim and Linzen 2020 ] . As LLMs’ context windows have increased in size, there has been growing interests in methods to evaluate how well they in fact use their context. A simple method