Source-linked AI summary
RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Context
Jackson Petty, Michael Y. Hu, Wentao Wang, Shauli Ravfogel, William Merrill, Tal Linzen
TL;DR
Complex in-context reasoning requires LLMs to retrieve and compose information, but it is difficult to measure how performance and strategy change as task complexity grows. RELIC evaluates context-free grammar recognition with generated grammars and strings whose complexity can be varied. Models perform well on smaller tasks but approach chance on larger grammars, while their compute and strategies do not scale as needed.
Problem
It is difficult to measure how LLM performance and reasoning strategy change as complex in-context tasks grow in difficulty.
Source: §1 · p. 1Method
Results
Models perform well on small grammars and short strings but approach chance on larger grammars, while reasoning traces show incorrect heuristics and insufficient chain-of-thought growth.
Source: §1 · p. 2Takeaways & Limitations
The results indicate brittle LLM reasoning and substantial headroom for improvement on RELIC and analogous fuzzy tasks.
Source: §1 · p. 2Because models may have encountered CFL recognition concepts before, success does not establish that they can develop novel solutions to the task.
Source: §8.5 · p. 12
Abstract
from arXiv · showhide
Large language models (LLMs) are increasingly used to solve complex tasks where they must retrieve and compose many pieces of in-context information in long reasoning chains. For many real-world tasks it is hard to accurately gauge how model performance and strategy change as task complexity grows. To evaluate models' complex reasoning capability in a scalable and verifiable way, we introduce RELIC (Recognition of Languages In-Context), a framework that evaluates an LLM's ability to decide whether a given string belongs to the context-free language (CFL) generated by a grammar presented in-context. CFL recognition allows us to modulate the intrinsic complexity of the problem by varying grammar size and string length and translate this asymptotic complexity into predictions for ideal LLM performance. We find that even the most advanced reasoning models perform poorly on RELIC, not only failing to appropriately scale their inference compute to keep pace with task difficulty, but even reducing the number of reasoning tokens they use as task complexity increases. We find that these decreases in compute accompany changes in reasoning strategy, as models move from identifying and implementing algorithmic solutions to guessing. For models whose full completions go uninspected, this manifests as ``quiet quitting'' on hard tasks.
1 Introduction
RELIC uses in-context context-free grammar recognition to study how LLMs handle complex, verifiable tasks as grammar size and string length vary. Models perform well on small tasks but fall toward chance on larger grammars, while their reasoning strategies and compute fail to scale appropriately.
1 Introduction
- RELIC prompts an LLM with an arbitrary grammar and string and asks whether the grammar generates that string.The framework applies formal language recognition, whose solutions can be externally verified, to complex in-context reasoning.Source: §1 · p. 1
- Grammar size and string length provide controllable task-complexity parameters, enabling predictions about how recognition difficulty should change.For context-free languages, solving all cases theoretically requires chain-of-thought length to grow linearly with grammar size and superlinearly with string length.Source: §1 · pp. 1–2
- RELIC is intended as a formal analogue for fuzzier tasks such as instruction following and in-context translation, while retaining easy verification.The benchmark is built from generated grammars and positive and negative strings, and the paper reports substantial headroom for improvement on RELIC and analogous tasks.Source: §1 · p. 2
- Even advanced reasoning models fall to near-chance accuracy on larger grammars, and their chain-of-thought lengths do not grow as needed for the correct strategy.Qualitative traces show increasing reliance on incorrect heuristics; closed-reasoning models may silently shift to invalid strategies as tasks become harder.Source: §1 · p. 2
2 Background
The background connects formal task complexity and context use to RELIC's study of language recognition. It situates the work among reasoning evaluations, instruction following, and in-context translation.
2.1 LLMs and Complexity Analysis
- CFL recognition is theoretically demanding: standard parsing runs in Θ(G·ℓ^3), while transformer inference with chain-of-thought is bounded between Ω(G·ℓ^1.7) and O(G·ℓ^6).These bounds motivate the prediction that limited inference compute imposes grammar and string-length thresholds beyond which performance cannot exceed chance.Source: §2.1 · p. 3
2.2 LLMs and Context Use
- RELIC goes beyond retrieval by requiring models to combine context pieces, retrieve them in non-monotonic order, and search among candidate solutions.Compared with synthetic context-use tasks such as Michelangelo, RELIC studies a more formally complex language-recognition task involving search.Source: §2.2 · p. 3
2.3 LLMs and Reasoning
- Prior work links test-time compute and reasoning models with broad benchmark gains, while also documenting brittle reasoning and inconsistent algorithmic solutions.Language recognition has been proposed as a formal analogue to instruction following; RELIC extends that line to context-free languages and general-purpose models rather than models trained for specific grammars.Source: §2.3 · pp. 3–4
- In-context translation asks models to translate using a supplied language description, but translation correctness is difficult to verify and description complexity remains an open evaluation factor.RELIC instead tests grammatical membership, a formal analogue to checking whether a translated sentence is grammatical, and focuses on context-free rather than regular languages.Source: §2.3 · p. 4
3 RELIC: Recognizing Languages In-Context
RELIC generates context-free grammars and strings to create scalable language-recognition evaluations. The paper instantiates this approach as RELIC-500 and describes sampling choices, intended use, and contamination mitigation.
3 RELIC: Recognizing Languages In-Context
- The grammar-generation process reduces sampled grammars to accessible, productive rules and defines grammar size as G = n_lex + n_nonlex.RELIC-500 contains 200 grammars whose generation parameters are each below 500, selected to reduce parameter correlations where possible.Source: §3 · p. 4
- RELIC samples positive and negative strings, with the reported experiments using unigram-sampled negatives and rebalancing classes in analyses.Most grammars have over 90% coverage against the 1,000-example goal, but positive and negative string-length distributions are not matched.Source: §3 · pp. 4–5
- Synthetic grammar generation is designed to make evaluation instances extremely unlikely to have appeared in model training.The number of grammar-string pairs grows rapidly with grammar size and string length, reducing contamination risk.Source: §3 · pp. 4–5
- RELIC is intended as a zero-shot test without positive or negative exemplars, because few-shot accuracy could reflect class heuristics rather than instruction following.The paper releases RELIC-500 and code for generating new grammars and examples.Source: §3 · p. 5
4 Experimental Methodology
The evaluation prompts models with a grammar and string and asks them to classify membership. Eight language models are included, with reduced sampling for some models because of evaluation cost.
4 Experimental Methodology
- The study evaluates eight LLMs on RELIC-500: three GPT-line models, two OpenAI reasoning models, two Gemma 3 models, and one DeepSeek-R1-Distill-Qwen-7B model.The three GPT-line models and o4-mini use the full RELIC-500 dataset; o3, both Gemma 3 models, and DeepSeek are subsampled to at most two examples per length per type per grammar, instead of 10, due to evaluation cost.Source: §4 · p. 5, PROMPT 1 · p. 6
PROMPT 1
- For each grammar-string pair, the prompt asks the model to decide whether the grammar generates the string and end with “Yes” or “No.”The prompt supplies the grammar and string and allows any reasoning strategy; responses are scored with a regular expression, with “unknown” assigned when no prediction is offered.Source: §4 · p. 5, PROMPT 1 · pp. 5–6
5 Experimental Results
RELIC performance declines as grammars and strings become more complex, with models approaching chance on the largest grammars. Models generally agree about which grammars and examples are difficult, though gpt-4.1-nano and gpt-4.1-mini are exceptions.
5.1 Overall Performance
- Accuracy on positive and negative examples differs across models, partly reflecting class biases that vary with string length.gpt-4.1-nano and gpt-4.1-mini increasingly predict positive examples as strings lengthen, while gpt-4.1 tends to predict negative examples.Source: §5.1 · p. 6, Figure 4 · p. 7
5.2 Performance Decreases as Grammar and Example Complexity Increases
- As nonlexical productions approach 500, all models reach or fall below chance; accuracy also declines with grammar complexity and string length.The decline with string length has an inflection point between ℓ=5 and ℓ=15, depending on the model.Source: §5.2 · p. 6, Figure 3 · p. 7
5.3 Models Generally Agree on Which Grammars and Examples are Hard
- Most models rank grammars and examples similarly by difficulty, but gpt-4.1-nano and gpt-4.1-mini are less correlated with the others.Correlations strengthen modestly as grammar and example complexity increase.Source: §5.3 · pp. 6, 8, Figure 5 · p. 7
6 How Do LLMs Succeed and Fail?
Models sometimes solve RELIC by deriving a parse tree, but can fail through accumulated errors or invalid heuristics. As strings grow, rule-based reasoning and test-time compute decline while guessing increases.
6 How Do LLMs Succeed and Fail?
- The analysis examines intermediate chains of thought, but o3 and o4-mini do not provide full traces for direct strategy classification.The authors judge the risk of unfaithful chains of thought to be low in this zero-shot, nonadversarial setup.Source: §6 · p. 8
6.1 Qualitative Analysis of Strategy
- On simpler cases, models can follow grammar rules to construct a parse tree and reach the correct answer.A successful gpt-4.1-mini example exhaustively searched compatible derivations for a five-symbol string.Source: §6.1 · p. 8
- Some failures arise when models accumulate errors while following an otherwise valid strategy, including invalid inferences or distraction by irrelevant information.Models may also hallucinate success criteria or abandon a correct strategy.Source: §6.1 · pp. 8–9
- Other failures use invalid heuristics, such as string length or the number of derivations for a terminal, which can yield correct answers for wrong reasons.The paper gives an example of rejecting a string based on a symbol absent from the grammar.Source: §6.1 · p. 9
6.2 Quantitative Analysis of Strategy
- For the gpt-4.1 series, rule-based responses peak early and then fall as string length increases, with models shifting to invalid heuristics.The authors use gpt-5 to classify completions as rule-based or heuristic.Source: §6.2 · p. 9
6.3 Test-Time Compute Grows Insufficiently
- Test-time compute grows sublinearly, peaks near 10% of token limits, then decreases as strings lengthen, alongside a shift away from rule-based strategies.RELIC requires superlinear compute in string length under the paper’s analysis.Source: §6.3 · p. 9
7 Finetuning on RELIC Does Not Improve Performance
Directly fine-tuning the Gemma 3 1B and 4B models on RELIC data does not significantly improve their performance. This suggests their poor results are not primarily due to difficulty inferring the task from a single prompt.
7 Finetuning on RELIC Does Not Improve Performance
- The study tests whether weaker Gemma 3 performance reflects difficulty inferring the task by tuning both variants on a subset of RELIC-500.Fine-tuning examples used Gemma chat templates, with the standard RELIC prompt and the correct answer.Source: §7 · p. 9
- Fine-tuning Gemma 3 1B and 4B on grammar–string–label data has no statistically significant impact on accuracy.Post-fine-tuning mean validation accuracy remained within the 95% confidence intervals of the non-fine-tuned models.Source: §7 · pp. 9–10, Figure 7 · p. 10
- The results suggest poor performance is not primarily due to inability to infer the task from a single prompt.This conclusion follows from the lack of statistically significant accuracy change after fine-tuning.Source: §7 · pp. 9–10
8 Discussion
RELIC performance deteriorates as grammar and string complexity rise, while models’ inference compute peaks early and reasoning traces shift toward guessing. The discussion connects this pattern to dense-context use and hidden-reasoning evaluation, while noting limits from task familiarity and strategy classification.
8.1 LLMs Quiet Quit on Hard Tasks
- As grammars grow and strings lengthen, models’ accuracy degrades while compute peaks early and then falls; visible traces increasingly show shallow guessing.For models without visible reasoning traces, the same diminishing-compute pattern implies a similar strategy shift and motivates the “quiet quitting” description.Source: §8.1 · pp. 10–11
8.2 RELIC Predicts Reasoning Performance
- RELIC performance broadly correlates with scores on reasoning and instruction-following benchmarks, measured by the longest string length classified reliably above minimum accuracy.For most models, minimum accuracy is at chance.Source: Figure 8 · p. 11, §8.2 · p. 11
8.3 Scalably-Complex Tasks Can Evaluate Hidden Reasoning
- Relating RELIC’s computational complexity to test-time compute requirements offers a partial way to assess whether models with hidden reasoning apply sound strategies.Proprietary models may withhold reasoning traces, preventing direct qualitative analysis of their strategies.Source: §8.3 · p. 11
8.4 Models Struggle at Dense Context Use
- RELIC’s small prompts still challenge context use because solving them requires searching over combinations of grammar rules and their order of application.The grammar and strings occupy only a few hundred rules and at most 50 words, yet the relevant rules and combinations are not obvious.Source: §8.4 · p. 11
8.5 Limitations
- RELIC does not control for task familiarity, and strategy judgments may miss low-level errors in chains of thought that were not verified at scale.Models may apply prior CFL-recognition solutions to novel instances rather than develop novel solutions; unverified errors could make strategy classifications overly optimistic.Source: §8.5 · p. 12
8.6 Future Directions
- Future work could test structured reasoning training, in-context examples, explicit strategy guidance, harder grammar classes, and formal-grammar translation tasks.Explicit strategy guidance may require users to identify valid strategies up front; context-sensitive grammars could model syntactic validity involving constructs such as C macros.Source: §8.6 · p. 12
A Grammar and String Novelty
- The number of possible grammar–sample pairs grows rapidly with grammar size and string length, making accidental training-set overlap vanishingly unlikely.A lower bound for distinct reduced Chomsky-normal-form grammars is 2^(n^3+nt−2n).Source: A Grammar and String Novelty · p. 16
B Dataset Information
The dataset samples grammars and positive and negative strings under defined size and length limits, retaining natural differences in example coverage and type proportions. Its grammar parameters are partly constrained by how production rules generate terminals and nonterminals.
B.1 Distributional Statistics for Grammars and Strings
- The static set selects 200 grammars from about 1,000 generated candidates to minimize correlations among four parameters, then samples positive and negative strings up to length 50.Positive strings are sampled from probabilistic grammars; negative strings are drawn uniformly and rejected if parseable, with up to 10 examples per length.Source: §B.1 · p. 16
- Positive-example availability varies by grammar and length, so the authors retain the resulting type imbalance rather than post-hoc rebalancing examples.Coverage is the number of examples relative to a maximum of 1,000; Figure 10 plots coverage, while Figure 9 shows positive/negative proportions overall and by length.Source: §B.1 · pp. 16–17, Figure 10 · p. 17, Figure 9 · p. 17
B.2 Why are 𝑛term and 𝑛lex Correlated?
- A grammar needs at least one lexical production for each terminal, so terminal count cannot exceed lexical-rule count; multiple rules may yield the same terminal.The same reasoning extends to nonterminal symbols and nonlexical rules.Source: §B.2 · p. 17
C Regressions & Correlation Data
The appendix reports model-accuracy analyses against grammar parameters and example length, describes inference settings, and introduces example chains of thought.
D Inference Cost, Setup, and Hyperparameters
- Open-weight models were capped at 4,096 new tokens; completions used sampling with each model or API’s default temperature and nucleus settings.OpenAI evaluations used roughly $15,000 in compute credits, while open-weight evaluations ran on a GPU cluster.Source: D Inference Cost, Setup, and… · p. 17
E Chains-of-Thought
- Appendix E introduces examples of chains of thought produced by DeepSeek-R1-Distill-Qwen-7B, abbreviated DSR1.The supplied passages introduce the examples but do not describe their contents.Source: E Chains-of-Thought · pp. 17–18
C Regressions & Correlation Data
- The appendix reports Pearson correlations of model accuracy and macro F1 with grammar parameters, regression coefficients for accuracy by model, nonlexical-rule count, and string length, plus cross-model rank correlations.The cited passages describe these analyses but do not provide their coefficient values.Source: C Regressions & Correlation Data · p. 17, Table 2 · p. 18, Table 3 · p. 18
E.1 Example A: Faulty Reasoning
This example shows a model beginning with a sound parsing strategy, then abandoning it for faulty reasoning and rejecting a string incorrectly.
E.1 Example A: Faulty Reasoning
- The model initially proposes breaking the string down according to the grammar’s production rules, but quickly shifts to an irrelevant odd-length heuristic.It counts the 41 symbols before returning to a derivation attempt.Source: §E.1 · pp. 18–19
- After finding a rule that generates the first symbol, the model treats NT1’s direct rule to t1 as excluding derivations through intermediate productions.It considers an intermediate expansion but rejects that possibility based on the presence of a different lexical rule involving NT1.Source: §E.1 · p. 19
- The model concludes the string is not generated because its second symbol is not t1, an invalid rejection based on that reasoning.The example’s chain of thought explicitly notes the mismatch between t1 and the observed second token t104.Source: §E.1 · p. 19
E.2 Example B: Irrelevant Distractions
The examples show DSR1 reaching conclusions through irrelevant reasoning, including one correct answer for the wrong reason. The accompanying strategy analysis uses human-validated LLM judgments and reports fine-tuning details.
E.2 Example B: Irrelevant Distractions
- Given a negative example containing only t136, DSR1 explored irrelevant derivations and concluded “Yes” because the symbol seemed like a valid node.The example analysis notes that t136 was derivable by some lexical production rule, but that observation did not establish the string's validity.Source: §E.2 · p. 19
E.3 Example C: Incorrect Strategy
- DSR1 checked for t27, which appears neither in the example nor its grammar, and correctly rejected a negative example for that irrelevant reason.The completion's proposed test did not determine whether the string was generated by the grammar.Source: §E.3 · p. 20
PROMPT 6
- The strategy rubric distinguishes heuristic guesses, rigorous rule-based solutions, and code or pseudocode algorithms.It classifies completions according to how the model attempted to recognize the language.Source: PROMPT 6 · p. 20
- 83% human-agreement for gpt-5 versus 68% for o4-mini; the authors report gpt-5's strategy classifications in the main text.The agreement comparison used 62 completions balanced by sample length and class.Source: PROMPT 6 · p. 20, F Strategy Classification Details · p. 20
G Finetuning Details
- Gemma 3 1B and 4B models were fine-tuned on 100 grammars with an 80%-20% train-validation split for five epochs.The authors ran five random-seed training runs per model size; validation loss began to diverge after five epochs.Source: G Finetuning Details · p. 20