RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Context
Transactions of the Association for Computational Linguistics · 01.07.2026 · 14 · 1410-1431
DOI: 10.1162/tacl.a.735 ↗Kurz gefasst
Fachartikel in der Zeitschrift Transactions of the Association for Computational Linguistics, online erschienen am 01.07.2026. Verfasst von Jackson Petty und 5 weiteren Autor:innen. Die Arbeit nennt 58 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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. Code: https://jpetty.org/relic
Zitieren
APA
Petty, J., Hu, M. Y., Wang, W., Ravfogel, S., Merrill, W., & Linzen, T. (2026). RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Context. Transactions of the Association for Computational Linguistics, 14, 1410-1431. https://doi.org/10.1162/tacl.a.735
Vancouver
Petty J, Hu MY, Wang W, Ravfogel S, Merrill W, Linzen T. RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Context. Transactions of the Association for Computational Linguistics. 2026;14:1410-1431. doi:10.1162/tacl.a.735
BibTeX
@article{Petty2026,
author = {Petty, Jackson and Hu, Michael Y. and Wang, Wentao and Ravfogel, Shauli and Merrill, William and Linzen, Tal},
title = {RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Context},
journal = {Transactions of the Association for Computational Linguistics},
year = {2026},
volume = {14},
pages = {1410--1431},
doi = {10.1162/tacl.a.735}
}
EUVIMED