{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T18:14:02Z","timestamp":1783361642902,"version":"3.54.6"},"reference-count":58,"publisher":"MIT Press","license":[{"start":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T00:00:00Z","timestamp":1783296000000},"content-version":"vor","delay-in-days":186,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>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\u2019 complex reasoning capability in a scalable and verifiable way, we introduce RELIC (Recognition of Languages In-Context), a framework that evaluates an LLM\u2019s 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 \u201cquiet quitting\u201d on hard tasks.<\/jats:p>\n                  <jats:p>Code: https:\/\/jpetty.org\/relic<\/jats:p>","DOI":"10.1162\/tacl.a.735","type":"journal-article","created":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T17:14:17Z","timestamp":1783358057000},"page":"1410-1431","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":0,"title":["RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Context"],"prefix":"10.1162","volume":"14","author":[{"given":"Jackson","family":"Petty","sequence":"first","affiliation":[{"name":"Department of Linguistics, New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael Y.","family":"Hu","sequence":"additional","affiliation":[{"name":"Center for Data Science, New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wentao","family":"Wang","sequence":"additional","affiliation":[{"name":"Center for Data Science, New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shauli","family":"Ravfogel","sequence":"additional","affiliation":[{"name":"Center for Data Science, New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"William","family":"Merrill","sequence":"additional","affiliation":[{"name":"Center for Data Science, New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tal","family":"Linzen","sequence":"additional","affiliation":[{"name":"Department of Linguistics, New York University"},{"name":"Center for Data Science, New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","published-online":{"date-parts":[[2026,7,1]]},"reference":[{"key":"2026070613141486500_bib1","volume-title":"Claude\u2019s extended thinking","author":"Anthropic","year":"2025"},{"key":"2026070613141486500_bib2","article-title":"Zoology: Measuring and Improving Recall in Efficient Language Models","volume-title":"The Twelfth International Conference on Learning Representations","author":"Arora","year":"2024"},{"key":"2026070613141486500_bib3","first-page":"7096","article-title":"On the ability and limitations of transformers to recognize formal languages","volume-title":"Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing","author":"Bhattamishra","year":"2020"},{"key":"2026070613141486500_bib4","article-title":"Long-span question-answering: Automatic question generation and QA-system ranking via side-by-side evaluation","volume-title":"Preprint","author":"Bohnet","year":"2024"},{"issue":"5","key":"2026070613141486500_bib5","first-page":"442","article-title":"Applying probability measures to abstract languages","volume":"C-22","author":"Booth","year":"1973","journal-title":"IEEE transactions on computers. Institute of Electrical and Electronics Engineers"},{"key":"2026070613141486500_bib6","article-title":"Training Neural Networks as Recognizers of Formal Languages","volume-title":"The Thirteenth International Conference on Learning Representations","author":"Butoi","year":"2025"},{"key":"2026070613141486500_bib7","first-page":"118","article-title":"The Algebraic Theory of Context-Free Languages","volume-title":"Studies in Logic and the Foundations of Mathematics","author":"Chomsky","year":"1963"},{"issue":"2","key":"2026070613141486500_bib8","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0019-9958(59)90362-6","article-title":"On certain formal properties of grammars","volume":"2","author":"Chomsky","year":"1959","journal-title":"Information and control"},{"key":"2026070613141486500_bib9","first-page":"42","article-title":"Testing distributional properties of context-free grammars","volume-title":"Proceedings of The 13th International Conference on Grammatical Inference","author":"Clark","year":"2017"},{"key":"2026070613141486500_bib10","volume-title":"syntheticpcfg: Code for generating synthetic PCFGs for testing grammatical inference algorithms","author":"Clark","year":"2018"},{"key":"2026070613141486500_bib11","volume-title":"DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning","author":"DeepSeek-AI","year":"2025"},{"key":"2026070613141486500_bib12","article-title":"Neural Networks and the Chomsky Hierarchy","volume-title":"The Eleventh International Conference on Learning Representations","author":"Del\u00e9tang","year":"2023"},{"key":"2026070613141486500_bib13","doi-asserted-by":"crossref","DOI":"10.52202\/075280-3081","article-title":"Faith and Fate: Limits of Transformers on Compositionality","volume-title":"Thirty-seventh Conference on Neural Information Processing Systems","author":"Dziri","year":"2023"},{"key":"2026070613141486500_bib14","doi-asserted-by":"crossref","first-page":"414","DOI":"10.18653\/v1\/2022.emnlp-main.27","article-title":"What makes instruction learning hard? An investigation and a new challenge in a synthetic environment","volume-title":"Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing","author":"Finlayson","year":"2022"},{"key":"2026070613141486500_bib15","volume-title":"Gemma 3 Technical Report","author":"Team","year":"2025"},{"key":"2026070613141486500_bib16","volume-title":"Gemini 2.5: Our most intelligent AI model","author":"Google","year":"2025"},{"key":"2026070613141486500_bib17","volume-title":"A compendium of problems complete for P (preliminary)","author":"Greenlaw","year":"1991"},{"key":"2026070613141486500_bib18","article-title":"Randomly sampled language reasoning problems reveal limits of LLMs","volume-title":"Preprint","author":"Gupta","year":"2025"},{"key":"2026070613141486500_bib19","article-title":"RULER: What\u2019s the Real Context Size of Your Long-Context Language Models?","volume-title":"First Conference on Language Modeling","author":"Hsieh","year":"2024"},{"key":"2026070613141486500_bib20","volume-title":"gkamradt\/LLMTest_NeedleInAHaystack","author":"Kamradt","year":"2023"},{"key":"2026070613141486500_bib21","first-page":"9087","article-title":"COGS: A Compositional Generalization Challenge Based on Semantic Interpretation","volume-title":"Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing","author":"Kim","year":"2020"},{"key":"2026070613141486500_bib22","article-title":"Tulu 3: Pushing Frontiers in Open Language Model Post-Training","volume-title":"Second Conference on Language Modeling","author":"Lambert","year":"2025"},{"key":"2026070613141486500_bib23","article-title":"Measuring faithfulness in Chain-of-Thought reasoning","volume-title":"Preprint","author":"Lanham","year":"2023"},{"issue":"1","key":"2026070613141486500_bib24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/505241.505242","article-title":"Fast context-free grammar parsing requires fast boolean matrix multiplication","volume":"49","author":"Lee","year":"2002","journal-title":"Journal of the ACM"},{"key":"2026070613141486500_bib25","author":"Li","year":"2025"},{"key":"2026070613141486500_bib26","article-title":"Decoupled Weight Decay Regularization","volume-title":"International Conference on Learning Representations","author":"Loshchilov","year":"2019"},{"key":"2026070613141486500_bib27","doi-asserted-by":"crossref","first-page":"3428","DOI":"10.18653\/v1\/P19-1334","article-title":"Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference","volume-title":"Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics","author":"McCoy","year":"2019"},{"key":"2026070613141486500_bib28","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1162\/tacl_a_00562","article-title":"The parallelism tradeoff: Limitations of log-precision transformers","volume":"11","author":"Merrill","year":"2023","journal-title":"Transactions of the Association for Computational Linguistics"},{"key":"2026070613141486500_bib29","article-title":"The Expressive Power of Transformers with Chain of Thought","volume-title":"The Twelfth International Conference on Learning Representations","author":"Merrill","year":"2024"},{"key":"2026070613141486500_bib30","article-title":"OpenAI o1 System Card","volume-title":"arXiv [cs.AI]","author":"OpenAI","year":"2024"},{"key":"2026070613141486500_bib31","volume-title":"Learning to reason with LLMs","author":"OpenAI","year":"2024"},{"key":"2026070613141486500_bib32","volume-title":"GPT-5 System Card","author":"OpenAI","year":"2025"},{"key":"2026070613141486500_bib33","volume-title":"Introducing GPT-4.1 in the API","author":"OpenAI","year":"2025"},{"key":"2026070613141486500_bib34","volume-title":"OpenAI o3 and o4-mini System Card","author":"OpenAI","year":"2025"},{"key":"2026070613141486500_bib35","article-title":"Evaluating in-context translation with synchronous context-free grammar transduction","volume-title":"Preprint","author":"Petty","year":"2026"},{"key":"2026070613141486500_bib36","article-title":"Let\u2019s Think Dot by Dot: Hidden computation in transformer language models","volume-title":"First Conference on Language Modeling","author":"Pfau","year":"2024"},{"key":"2026070613141486500_bib37","doi-asserted-by":"crossref","first-page":"5687","DOI":"10.18653\/v1\/2023.findings-emnlp.378","article-title":"Measuring and narrowing the compositionality gap in language models","volume-title":"Findings of the Association for Computational Linguistics: EMNLP 2023","author":"Press","year":"2023"},{"key":"2026070613141486500_bib38","article-title":"GPQA: A Graduate-Level Google-Proof Q&A Benchmark","volume-title":"First Conference on Language Modeling","author":"Rein","year":"2024"},{"issue":"2","key":"2026070613141486500_bib39","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","article-title":"Tree-size bounded alternation","volume":"21","author":"Ruzzo","year":"1980","journal-title":"Journal of computer and system sciences"},{"key":"2026070613141486500_bib40","article-title":"Multitask Prompted Training Enables Zero-Shot Task Generalization","volume-title":"The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022","author":"Sanh","year":"2022"},{"key":"2026070613141486500_bib41","doi-asserted-by":"crossref","DOI":"10.70777\/si.v2i6.15919","article-title":"The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity","volume-title":"The Thirty-ninth Annual Conference on Neural Information Processing Systems","author":"Shojaee","year":"2025"},{"key":"2026070613141486500_bib42","article-title":"A Benchmark for Learning to Translate a New Language from One Grammar Book","volume-title":"The Twelfth International Conference on Learning Representations","author":"Tanzer","year":"2023"},{"key":"2026070613141486500_bib43","doi-asserted-by":"crossref","DOI":"10.52202\/075280-3275","article-title":"Language Models Don\u2019t Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting","volume-title":"Thirty-seventh Conference on Neural Information Processing Systems","author":"Turpin","year":"2023"},{"issue":"2","key":"2026070613141486500_bib44","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/0022-0000(91)90020-6","article-title":"Properties that characterize LOGCFL","volume":"43","author":"Venkateswaran","year":"1991","journal-title":"Journal of computer and system sciences"},{"key":"2026070613141486500_bib45","article-title":"Michelangelo: Long context evaluations beyond haystacks via Latent Structure Queries","volume-title":"Preprint","author":"Vodrahalli","year":"2024"},{"key":"2026070613141486500_bib46","volume-title":"TRL: Transformers Reinforcement Learning","author":"Werra","year":"2020"},{"key":"2026070613141486500_bib47","doi-asserted-by":"crossref","DOI":"10.52202\/079017-3018","article-title":"MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark","volume-title":"The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track","author":"Wang","year":"2024"},{"key":"2026070613141486500_bib48","article-title":"Finetuned Language Models are Zero-Shot Learners","volume-title":"International Conference on Learning Representations","author":"Wei","year":"2022"},{"key":"2026070613141486500_bib49","doi-asserted-by":"crossref","DOI":"10.52202\/068431-1800","article-title":"Chain-of-Thought Prompting Elicits Reasoning in Large Language Models","volume-title":"Advances in Neural Information Processing Systems","author":"Wei","year":"2022"},{"key":"2026070613141486500_bib50","first-page":"38","article-title":"Transformers: State-of-the-art natural language processing","volume-title":"Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations","author":"Wolf","year":"2020"},{"key":"2026070613141486500_bib51","article-title":"How do transformers learn variable binding in symbolic programs?","volume-title":"Preprint","author":"Wu","year":"2025"},{"key":"2026070613141486500_bib52","article-title":"Large Language Models as Optimizers","volume-title":"The Twelfth International Conference on Learning Representations","author":"Yang","year":"2023"},{"key":"2026070613141486500_bib53","article-title":"IFEval-Code: Controlled Code Generation","volume-title":"Preprint","author":"Yang","year":"2025"},{"key":"2026070613141486500_bib54","doi-asserted-by":"crossref","first-page":"11809","DOI":"10.52202\/075280-0517","article-title":"Tree of Thoughts: Deliberate Problem Solving with Large Language Models","volume":"36","author":"Yao","year":"2023","journal-title":"Advances in Neural Information Processing Systems"},{"key":"2026070613141486500_bib55","first-page":"15262","article-title":"\u221eBench: Extending long context evaluation beyond 100K tokens","volume-title":"Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics","author":"Zhang","year":"2024"},{"key":"2026070613141486500_bib56","doi-asserted-by":"crossref","DOI":"10.52202\/075280-2020","article-title":"Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena","volume-title":"Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track","author":"Zheng","year":"2023"},{"key":"2026070613141486500_bib57","article-title":"Instruction-following evaluation for Large Language Models","volume-title":"Preprint","author":"Zhou","year":"2023"},{"key":"2026070613141486500_bib58","article-title":"WebArena: A Realistic Web Environment for Building Autonomous Agents","volume-title":"The Twelfth International Conference on Learning Representations","author":"Zhou","year":"2024"}],"container-title":["Transactions of the Association for Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/tacl\/article-pdf\/doi\/10.1162\/TACL.a.735\/2612412\/tacl.a.735.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/tacl\/article-pdf\/doi\/10.1162\/TACL.a.735\/2612412\/tacl.a.735.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T17:14:27Z","timestamp":1783358067000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/tacl\/article\/doi\/10.1162\/TACL.a.735\/137426\/RELIC-Evaluating-Complex-Reasoning-via-the"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"references-count":58,"URL":"https:\/\/doi.org\/10.1162\/tacl.a.735","relation":{},"ISSN":["2307-387X"],"issn-type":[{"value":"2307-387X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2026]]},"published":{"date-parts":[[2026]]}}}