Papers by Jay Raval
Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks (2026.findings-acl)
Copied to clipboard
| Challenge: | Large language models (LLMs) have demonstrated strong performance on formal language tasks, yet whether this reflects genuine symbolic reasoning or pattern matching on familiar constructions remains unclear. |
| Approach: | They propose a benchmark for deterministic finite automata (DFA) construction from regular languages, comprising factual knowledge questions, seen construction problems from public sources, and unseen problems. |
| Outcome: | The proposed model achieves perfect accuracy on factual questions and 84-90% on seen tasks, but falls sharply on unseen problems (by 30-64%), with failures stemming from systematic misinterpretation of language constraints, incorrect handling of Kleene-star semantics, and a failure to preserve global consistency. |