Elamur Research⌕
☰
home / papers / 2026 / RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Context

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

Paper · 2026 · Jackson Petty, Michael Y. Hu, Wentao Wang et al.

Summary

LLMs increasingly have to solve tasks by retrieving and combining many pieces of information from their context. For realistic tasks, though, it is hard to measure how performance changes as difficulty grows. The authors address this with RELIC, a synthetic and automatically verifiable benchmark. A model receives a randomly generated context-free grammar and a string, and must decide whether the grammar can produce that string.

Difficulty is controlled by two parameters, grammar size and string length. Classical parsing complexity then predicts how much chain-of-thought an ideal reasoner would need. Because every instance is newly generated, the benchmark resists data contamination, and its difficulty can be raised as models improve.

The tested models handle small grammars and short strings well but approach chance on larger instances. Those larger grammars are still far smaller than real programming-language or natural-language grammars. Models also produce fewer reasoning tokens as problems get harder and move from algorithmic derivation toward heuristic guessing, which the authors call "quiet quitting." This points to brittle reasoning and to dense, compositional context use as a key weakness.

Key points

  • The benchmark contains grammars with up to 500 nonterminal productions and positive and negative strings of up to 50 symbols. Code is available at jpetty.org/relic.
  • Evaluated models include Gemma 3, a distilled DeepSeek-R1, and OpenAI's o3, o4-mini and the gpt-4.1 family.
  • Standard CFG parsing runs in Θ(G·ℓ³) time. The authors place the chain-of-thought length needed by transformers between Ω(G·ℓ^1.7) and O(G·ℓ^6).
  • An LLM judge, checked against human annotators, classified reasoning strategies. It showed that harder instances push models from rule-based derivation toward guessing, and the authors caution that these classifications may be too optimistic.
  • Fine-tuning small models on labeled outputs did not help. Proposed future work includes training on structured derivations and extending the benchmark to context-sensitive languages and grammar-based translation.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓New York UniversityNew York · United States201 works · 100,180 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputer Vision and Pattern Recognition · 2,869 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,426 works

Cite

Cite as Jackson Petty, Michael Y. Hu, Wentao Wang, Shauli Ravfogel, William Merrill and Tal Linzen. 2026. RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Context. Transactions of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/tacl.a.735

@article{petty2026relic,
  title = {{RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Context}},
  author = {Jackson Petty, Michael Y. Hu, Wentao Wang, Shauli Ravfogel, William Merrill and Tal Linzen},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2026},
  doi = {10.1162/tacl.a.735},
  url = {https://doi.org/10.1162/tacl.a.735}
}

References

50 references, 21 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Anthropic. 2025. Claude’s extended think-https://www.anthropic.com/news/ ing. visible-extended-thinking. Accessed: 2025-12-5. find
  2. Simran Arora, Sabri Eyuboglu, Aman Timalsina, Isys Johnson, Michael Poli, James Zou, Atri Rudra, and Christopher Re. 2024. Zoology: Measuring and Improving Recall in Efficient Language Models. In The Twelfth International Conference on Learning Representations.
  3. Alexander Clark. 2017. Testing distributional properties of context-free grammars. In Proceedings of The 13th International Conference on Grammatical Inference, volume 57 of Proceedings of Machine Learning Research, pages 42–53, Delft, The Netherlands. PMLR. find
  4. Alexander Clark. 2018. syntheticpcfg: Code for generating synthetic PCFGs for testing grammatical inference algorithms. find
  5. Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7096–7116, Stroudsburg, PA, USA. Association for Computation…
  6. DeepSeek-AI, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z F Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, and 181 others. 2025. DeepSeek-R1: Incentivizing Reasoning Capability in LLMs…
  7. Bernd Bohnet, Kevin Swersky, Rosanne Liu, Pranjal Awasthi, Azade Nova, Javier Snaider, Hanie Sedghi, Aaron T Parisi, Michael Collins, Angeliki Lazaridou, Orhan Firat, and Noah Fiedel. 2024. Long-span question-answering: Automatic question generation and QA-system ranking via side-by-side evaluation.… — [arXiv:2406.00179](https://arxiv.org/abs/2406.00179) find
  8. Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A Ortega. 2023. Neural Networks and the Chomsky Hierarchy. In The Eleventh International Conference on Learning Representations.
  9. T L Booth and R A Thompson. 1973. Applying probability measures to abstract languages. IEEE transactions on computers. Institute of Electrical and Electronics Engineers, C-22(5):442–450. find
  10. Alexandra Butoi, Ghazal Khalighinejad, Anej Svete, Josef Valvoda, Ryan Cotterell, and Brian Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D Hwang, Soumya Sanyal, Xiang Ren, Allyson Ettinger,… — Faith and Fate: Limits of Transformers on Compositionality
  11. Matthew Finlayson, Kyle Richardson, Ashish Sabharwal, and Peter Clark. 2022. What makes instruction learning hard? An investigation and a new challenge in a synthetic environment. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 414–426, Stroudsburg, P… find
  12. Gemma Team, Aishwarya Kamath, Johan Ferret, Shreya Pathak, Nino Vieillard, Ramona Merhej, Sarah Perrin, Tatiana Matejovicova, Alexandre Ramé, Morgane Rivière, Louis Rouillard, Thomas Mesnard, Geoffrey Cideron, Jean-Bastien Grill, Sabela Ramos, Edouard Yvinec, Michelle Casbon, Etienne Pot, Ivo Penche… find
  13. Nathan Lambert, Jacob Morrison, Valentina Pyatkin, Shengyi Huang, Hamish Ivison, Faeze Brahman, Lester James Validad Miranda, Alisa Liu, Nouha Dziri, Xinxi Lyu, Yuling Gu, Saumya Malik, Victoria Graf, Jena D Hwang, Jiangjiang Yang, Ronan Le Bras, Oyvind Tafjord, Christopher Wilhelm, Luca Soldaini, a… — Tulu 3: Pushing Frontiers in Open Language Model Post-Training
  14. Tamera Lanham, Anna Chen, Ansh Radhakrishnan, Benoit Steiner, Carson Denison, Danny Hernandez, Dustin Li, Esin Durmus, Evan Hubinger, Jackson Kernion, Kamilė Lukošiūtė, Karina Nguyen, Newton Cheng, Nicholas Joseph, Nicholas Schiefer, Oliver Rausch, Robin Larson, Sam McCandlish, Sandipan Kundu, an… — Measuring Faithfulness in Chain-of-Thought Reasoning
  15. Google. 2025. Gemini 2.5: Our most intelligent AI model. https://blog.google/technology/google-deepmind/ gemini-model-thinking-updates-march-2025/. ↗
  16. Lillian Lee. 2002. Fast context-free grammar pars-Accessed: 2025-11-10. ing requires fast boolean matrix multiplication. Journal of the ACM, 49(1):1–15. find
  17. Raymond Greenlaw, Walter L Ruzzo, and James Hoover. 1991. A compendium of problems com- Mo Li, Songyang Zhang, Taolin Zhang, Haodong plete for P (preliminary). Technical report, Uni-Duan, Yunxin Liu, and Kai Chen. 2025. versity of Alberta. NeedleBench: Evaluating LLM Retrieval and Reasoning Across V… — [arXiv:2501.02825](https://arxiv.org/abs/2501.02825) find
  18. Ilya Loshchilov and Frank Hutter. 2019. Decoupled Weight Decay Regularization. In Interna-Cheng-Ping Hsieh, Simeng Sun, Samuel Kriman, tional Conference on Learning Representations. find
  19. Shantanu Acharya, Dima Rekesh, Fei Jia, and Boris Ginsburg. 2024. RULER: What’s the Real Tom McCoy, Ellie Pavlick, and Tal Linzen. 2019. Context Size of Your Long-Context Language Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference. Models? In First Conference…
  20. William Merrill and Ashish Sabharwal. 2023. Accessed: 2025-4-10. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the As-Najoung Kim and Tal Linzen. 2020. COGS: A sociation for Computational Linguistics, 11:531– Compositional Generalization Challenge Based 545. on… find
  21. OpenAI, :, Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, Alex Iftimie, Alex Karpenko, Alex Tachard Passos, Alexander Neitz, Alexander Prokofiev, Alexander Wei, Allison Tam, and 244 others. 2024. OpenAI o1 Sy…
  22. OpenAI. 2024. Learning to reason with LLMs. https://openai.com/index/ Ac-learning-to-reason-with-llms/. cessed: 2025-5-9. ↗
  23. OpenAI. 2025a. GPT-5 System Card. Technical report, OpenAI. find
  24. OpenAI. 2025b. Introducing GPT-4.1 in the API. https://openai.com/index/gpt-4-1/. Accessed: 2025-5-12. ↗
  25. OpenAI. 2025c. OpenAI o3 and o4-mini System Card. https://openai.com/index/ o3-o4-mini-system-card/. Accessed: 2025-5-12. ↗
  26. Jackson Petty, Jaulie Goe, and Tal Linzen. 2026. Evaluating in-context translation with synchronous context-free grammar transduction. Preprint, arXiv:2604.07320. find
  27. Jacob Pfau, William Merrill, and Samuel R Bowman. 2024. Let’s Think Dot by Dot: Hidden computation in transformer language models. In First Conference on Language Modeling. find
  28. Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah Smith, and Mike Lewis. 2023. Measuring and narrowing the compositionality gap in language models. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 5687–5711, Stroudsburg, PA, USA. Association for Computational Lin… find
  29. Victor Sanh, Albert Webson, Colin Raffel, Stephen H Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Arun Raja, Manan Dey, M Saiful Bari, Canwen Xu, Urmish Thakker, Shanya Sharma Sharma, Eliza Szczechla, Taewoon Kim, Gunjan Chhablani, Nihal V Nayak, Debajyoti Datta, and 21 ot… — Multitask Prompted Training Enables Zero-Shot Task Generalization
  30. Parshin Shojaee, Seyed Iman Mirzadeh, Keivan Alizadeh, Maxwell Horton, Samy Bengio, and Mehrdad Farajtabar. 2025. The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity. In The Thirty-ninth Annual Conference on Neural Information… find
  31. Garrett Tanzer, Mirac Suzgun, Eline Visser, Dan Jurafsky, and Luke Melas-Kyriazi. 2023. A Benchmark for Learning to Translate a New Language from One Grammar Book. In The Twelfth International Conference on Learning Representations. find
  32. Miles Turpin, Julian Michael, Ethan Perez, and Samuel R Bowman. 2023. Language Models Don’t Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting. In Thirty-seventh Conference on Neural Information Processing Systems.
  33. H Venkateswaran. 1991. Properties that characterize LOGCFL. Journal of computer and system sciences, 43(2):380–404. find
  34. David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R Bowman. 2024. GPQA: A Graduate-Level Google-Proof Q&A Benchmark. In First Conference on Language Modeling.
  35. Kiran Vodrahalli, Santiago Ontanon, Nilesh Tripuraneni, Kelvin Xu, Sanil Jain, Rakesh Shivanna, Jeffrey Hui, Nishanth Dikkala, Mehran Kazemi, Bahare Fatemi, Rohan Anil, Ethan Dyer, Siamak Shakeri, Roopali Vij, Harsh Mehta, Vinay Ramasesh, Quoc Le, Ed Chi, Yifeng Lu, and 5 others. 2024. Michelangelo:…
  36. Walter L Ruzzo. 1980. Tree-size bounded alternation. Journal of computer and system sciences, 21(2):218–235. find
  37. Leandro von Werra, Younes Belkada, Lewis Tunstall, Edward Beeching, Tristan Thrush, Nathan Lambert, Shengyi Huang, Kashif Rasul, and Quentin Gallouédec. 2020. TRL: Transformers Reinforcement Learning. find
  38. Yubo Wang, Xueguang Ma, Ge Zhang, Yuansheng Ni, Abhranil Chandra, Shiguang Guo, Weiming Ren, Aaran Arulraj, Xuan He, Ziyan Jiang, Tianle Li, Max Ku, Kai Wang, Alex Zhuang, Rongqi Fan, Xiang Yue, and Wenhu Chen. 2024. MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark…
  39. Jason Wei, Maarten Bosma, Vincent Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc V Le. 2022a. Finetuned Language Models are Zero-Shot Learners. In International Conference on Learning Representations.
  40. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H Chi, Quoc V Le, and Denny Zhou. 2022b. Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. In Advances in Neural Information Processing Systems.
  41. Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, and 3 others. 2020. Transfo…
  42. Yiwei Wu, Atticus Geiger, and Raphaël Millière. 2025. How do transformers learn variable binding in symbolic programs? Preprint, arXiv:2505.20896. — [arXiv:2505.20896](https://arxiv.org/abs/2505.20896) find
  43. Wangchunshu Zhou, Guanglin Niu, Zhoujun Li, Binyuan Hui, and Junyang Lin. 2025. IFEval-Code: Controlled Code Generation. Preprint, arXiv:2507.22462. — [arXiv:2507.22462](https://arxiv.org/abs/2507.22462) find
  44. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. 2023. Tree of Thoughts: Deliberate Problem Solving with Large Language Models. Advances in Neural Information Processing Systems, 36:11809–11822. find
  45. Xinrong Zhang, Yingfa Chen, Shengding Hu, Zihang Xu, Junhao Chen, Moo Hao, Xu Han, Zhen Thai, Shuo Wang, Zhiyuan Liu, and Maosong Sun. 2024. ∞Bench: Extending long context evaluation beyond 100K tokens. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volum… find
  46. Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, Hao Zhang, Joseph E Gonzalez, and Ion Stoica. 2023. Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena. In Thirty-seventh Conference on Neural Information Processing…
  47. Jeffrey Zhou, Tianjian Lu, Swaroop Mishra, Siddhartha Brahma, Sujoy Basu, Yi Luan, Denny Zhou, and Le Hou. 2023. Instruction-following evaluation for Large Language Models. Preprint, arXiv:2311.07911.
  48. Shuyan Zhou, Frank F Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, Uri Alon, and Graham Neubig. 2024. WebArena: A Realistic Web Environment for Building Autonomous Agents. In The Twelfth International Conference on Learning Representations…
  49. Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. 2023. Large Language Models as Optimizers. In The Twelfth International Conference on Learning Representations.
  50. Jian Yang, Wei Zhang, Shukai Liu, Linzheng Chai, Yingshui Tan, Jiaheng Liu, Ge Zhang, find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/petty-2026-relic-evaluating-complex-reasoning-recognition/