Evaluating the Formal Reasoning Capabilities of Large Language Models through Chomsky Hierarchy

Researchers introduced ChomskyBench, a new benchmark for evaluating large language models' formal reasoning capabilities using the Chomsky Hierarchy framework. The study reveals that while larger models show improvements, current LLMs face severe efficiency barriers and are significantly less efficient than traditional algorithmic programs for formal reasoning tasks.

• →ChomskyBench is the first benchmark to systematically evaluate LLMs across the complete Chomsky Hierarchy with natural language process-trace evaluation.
• →Performance stratification directly correlates with the hierarchy's complexity levels, showing clear limitations as task difficulty increases.
• →Larger models and advanced inference methods offer relative gains but require prohibitive computational costs for practical reliability.
• →Current LLMs are significantly less efficient than traditional algorithmic programs for formal reasoning tasks.
• →The limitations stem from inefficiency rather than absolute capability bounds, highlighting the continued importance of traditional software tools.