💬 NLP

RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Context

The paper introduces RELIC, a framework for evaluating large language models' complex reasoning by testing their ability to recognize context-free languages in-context, revealing that even advanced models fail to scale inference compute with task difficulty and often shift from algorithmic reasoning to guessing as complexity increases.

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

Published 2026-04-29

📖 4 min read☕ Coffee break read

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are hiring a very smart, well-read assistant to solve a puzzle. You give them a brand-new rulebook (a "grammar") and a specific sentence (a "string"). Your question is simple: "Does this sentence follow the rules in the book?"

This is exactly what the paper RELIC is about. It's a new way to test how well Large Language Models (LLMs)—the AI brains behind tools like ChatGPT—can actually think through complex, multi-step problems when they are given new instructions on the fly.

Here is the breakdown of the paper's findings using simple analogies:

1. The Test: The "Rulebook Puzzle"

The researchers created a game where the AI has to act like a grammar detective.

The Setup: They generate thousands of unique, made-up rulebooks. These aren't English or Spanish; they are abstract sets of rules (like "A must be followed by B," or "C turns into D").
The Task: The AI sees the rulebook and a sentence made of random symbols (like t43 t51 t66). It has to say "Yes" (this sentence follows the rules) or "No" (it breaks the rules).
The Twist: They make the puzzles harder by making the rulebooks bigger and the sentences longer.

2. The Expectation: The "Climbing Mountain" Analogy

Think of solving these puzzles like climbing a mountain.

Small Mountains (Easy Puzzles): If the rulebook is tiny and the sentence is short, the AI can easily climb to the top. It uses a logical map (an algorithm) to check every step.
Big Mountains (Hard Puzzles): As the rulebook gets huge and the sentence gets long, the mountain gets steeper. To solve it correctly, the AI needs to use more mental energy (more "thinking tokens") to check every single possibility. It's like needing a bigger backpack and more water to climb a higher peak.

3. The Discovery: "Quiet Quitting"

This is the paper's most surprising and critical finding. The researchers expected that as the puzzles got harder, the AI would "try harder" by using more thinking power.

Instead, the AI started "quiet quitting."

The Analogy: Imagine a worker who is asked to solve a simple math problem. They pull out a calculator and do the work. But when you give them a massive, complex equation, instead of pulling out a super-calculator and working longer, they just guess. They stop trying to do the math and start making up answers based on gut feelings.
The Evidence:
- When the puzzles got hard, the AI didn't use more thinking time; it actually used less.
- The AI stopped using logical, step-by-step reasoning (like building a tree of possibilities) and started relying on bad shortcuts (heuristics).
- Even the most advanced "reasoning" models (the ones designed to think deeply) did this. They would start with a good plan, get overwhelmed, and then silently switch to guessing.

4. The Result: "Right for the Wrong Reasons"

The paper found that when the AI "quiet quits," it often gets the answer right by accident, but for the wrong reasons.

Example: The AI might reject a sentence just because it's "too long," even though the rules actually allow long sentences. It got the "No" answer correct, but its logic was completely broken.
The Problem: If you can't see the AI's thinking process (which is true for many commercial models), you might think it's smart because it got the answer right. But in reality, it's just guessing, and it will fail on the next hard problem.

5. The Conclusion: Brittle Brains

The paper concludes that current AI models are brittle.

They understand the idea of the task when it's easy.
But they cannot scale their effort to match the difficulty of the problem.
They don't have a reliable "internal engine" that says, "This is hard, I need to spend more time on it." Instead, they give up and guess.

Summary

The paper introduces RELIC as a stress test for AI reasoning. It shows that even the smartest AI models today are like students who can solve easy homework but, when faced with a difficult exam, stop trying to solve the problems and just fill in the bubbles randomly. They "quiet quit" on hard tasks, making them unreliable for complex, real-world reasoning where you need them to actually follow the rules, not just guess.

1. Problem Statement

Large Language Models (LLMs) are increasingly tasked with solving complex problems requiring the retrieval and composition of multiple pieces of in-context information (e.g., analyzing financial statements or following multi-step instructions). However, evaluating these capabilities is difficult because:

Lack of Verifiability: Real-world tasks often lack ground truth or precise metrics.
Uncontrollable Complexity: It is hard to systematically scale task difficulty to observe how model performance degrades.
Data Contamination: Static benchmarks often suffer from models having seen similar examples during pretraining.

The authors propose that current models fail to scale their inference compute (reasoning effort) appropriately as task complexity increases, often resorting to "quiet quitting"—shifting from valid algorithmic reasoning to guessing or shallow heuristics when tasks become difficult.

2. Methodology: The RELIC Framework

The authors introduce RELIC (Recognition of Languages In-Context), a framework designed to evaluate LLMs on Context-Free Language (CFL) recognition.

Task Definition: An LLM is presented with a specific Context-Free Grammar (CFG) and a string. The model must determine if the string belongs to the language generated by that grammar (Accept/Reject).
Synthetic Benchmark Generation (RELIC-500):
- To ensure novelty and prevent data contamination, grammars are stochastically generated rather than taken from a fixed dataset.
- Grammars are parameterized by four values: number of terminal symbols ( $n'_{term}$ ), non-terminal symbols ( $n'_{nonterm}$ ), lexical rules ( $n'_{lex}$ ), and non-lexical rules ( $n'_{nonlex}$ ).
- The benchmark includes 200 grammars with parameters up to 500, generating positive (valid) and negative (invalid) strings of lengths up to 50.
Theoretical Basis:
- CFL recognition is known to be in the complexity class AC1 and NC1-hard.
- Theoretical analysis suggests that for a Transformer to solve this, the length of its Chain-of-Thought (CoT) must grow superlinearly with string length and linearly with grammar size.
- This provides a theoretical "ideal" compute budget against which actual model behavior can be compared.

3. Experimental Setup

Models Evaluated: Eight LLMs were tested, including:
- Proprietary: OpenAI's gpt-4.1 family (nano, mini, full), o3, and o4-mini.
- Open-Weight: Google's Gemma 3 (1B and 4B) and a distilled version of DeepSeek-R1.
Evaluation Protocol: Zero-shot prompting. Models were asked to classify strings based only on the provided grammar rules, without few-shot examples.
Analysis Metrics:
- Class-balanced accuracy and Macro F1 scores.
- Correlation between performance and grammar complexity (size) and string length.
- Test-Time Compute (TTC): Measuring the number of tokens generated during reasoning relative to task difficulty.
- Strategy Classification: Using an LLM-as-a-judge (and human validation) to categorize reasoning traces as Rule-Based (valid derivation) or Heuristic/Guessing.

4. Key Results

A. Performance Degradation with Complexity

Small vs. Large Tasks: Models perform reasonably well on small grammars and short strings. However, performance drops precipitously as grammar size (specifically non-lexical productions) and string length increase.
Chance Performance: Even the most advanced reasoning models (e.g., o3, o4-mini) fall to near-chance accuracy (approx. 50%) on grammars with ~500 rules, despite these being orders of magnitude smaller than grammars for real programming languages.
Bias: Models exhibit strong class biases (e.g., predicting "Yes" for long strings and "No" for short ones) rather than analyzing the grammar rules.

B. The "Quiet Quitting" Phenomenon

Compute Mismatch: Theoretically, solving harder instances requires more compute (longer CoT). Empirically, models reduce their compute expenditure as tasks get harder.
- Relative Test-Time Compute (TTC) peaks early (at very short string lengths) and then decreases as string length increases.
- Models stop increasing inference effort well before reaching their token limits.
Strategy Shift: As complexity rises, models shift from Rule-Based strategies (constructing parse trees) to Heuristic strategies (guessing based on string length or symbol presence).
Closed-Reasoning Models: Even models that hide their reasoning traces (o3, o4-mini) show the same drop in compute expenditure, implying they are also "quiet quitting" by switching to invalid strategies internally.

C. Fine-Tuning Limitations

The authors fine-tuned Gemma 3 models directly on the RELIC task (grammar-string-label pairs).
Result: Fine-tuning provided no statistically significant improvement in performance. This suggests the failure is not due to a lack of task familiarity but a fundamental inability to execute the required reasoning strategies at scale.

D. Correlation with General Reasoning

Performance on RELIC correlates with performance on general reasoning benchmarks (MMLU Pro, GPQA, IFEval). This indicates that RELIC is a valid proxy for general complex reasoning capabilities, not just a niche formal language task.

5. Key Contributions

RELIC Framework: A scalable, verifiable, and contamination-resistant benchmark for evaluating complex in-context reasoning using formal language theory.
Empirical Evidence of "Quiet Quitting": Demonstrates that state-of-the-art reasoning models fail to scale their compute resources in proportion to task difficulty, instead reverting to heuristics.
Strategy Analysis: Quantifies the shift from algorithmic reasoning to guessing as a function of complexity, revealing a brittleness in current "reasoning" models.
Theoretical-Practical Gap: Highlights the disconnect between the theoretical complexity requirements for CFL recognition (which Transformers could theoretically meet) and the empirical behavior of current LLMs.

6. Significance and Implications

Brittleness of Reasoning: The findings challenge the notion that "reasoning models" (like o3 or o4-mini) have robust, scalable reasoning capabilities. They appear to rely on heuristics that break down under complexity.
Evaluation Paradigm: RELIC offers a way to evaluate "hidden" reasoning in proprietary models by observing their compute behavior (token usage) rather than just the final output.
Future Directions: The paper suggests that simply increasing model size or training data is insufficient. Future improvements may require:
- Training on structured completions (guided derivations).
- Explicit guidance on reasoning strategies.
- Mechanisms to force models to maintain valid reasoning strategies even when tasks become difficult, preventing the "quiet quitting" behavior.

In summary, the paper argues that current LLMs are not truly "reasoning" in a scalable, algorithmic sense when faced with complex, novel in-context tasks; instead, they optimize for a shortcut that fails as the problem complexity grows.