Abstract
While Large Language Models (LLMs) demonstrate proficiency in general reasoning and coding, their grasp of the formal foundations of computer science remains under-explored. This paper introduces TuringQ, a comprehensive benchmark comprising over 4,000 question-answer pairs focused on the Theory of Computation (ToC). We evaluate several state-of-the-art models and demonstrate that while GPT-4 remains the top performer, domain-specific fine-tuning significantly enhances the capabilities of smaller models like Llama-3, even yielding performance gains in unrelated mathematical domains.
Introduction
The Theory of Computation (ToC) serves as the "soul" of computer science, encompassing the study of Turing machines, formal grammars, and complexity classes like P vs. NP. Unlike general math or coding tasks, ToC requires a unique synthesis of rigid formal logic and abstract proof construction. Existing benchmarks often overlook this specialized domain, making it difficult to discern whether LLMs are truly reasoning through these concepts or merely retrieving memorized definitions. TuringQ addresses this gap by providing a rigorous testing ground for AI comprehension of foundational computer science principles.
The TuringQ Framework
The researchers developed a multi-stage pipeline to construct and validate the benchmark:
- Data Curation: The dataset includes 2,155 questions sourced from exams at 29 elite universities, supplemented by 1,790 expert-verified pairs generated by Claude 3 Sonnet to cover essential theorems and lemmas.
- Model Specialization: Using QLoRA (Quantized Low-Rank Adaptation), the team fine-tuned a Llama3-8B model to create Llama3-8B-ft-TuringQ, specifically optimized for theoretical reasoning.
- Automated Evaluation: To scale grading, the authors introduced AutoGrade-TQ, a specialized prompt that enables Llama3-8B to function as an automated judge, scoring responses on a scale of 1 to 4 based on correctness and alignment with reference solutions.
Dataset Characteristics
TuringQ consists of 4,006 question-answer pairs categorized into seven core areas: Complexity Theory, Computability Theory, Regular Languages, Context-Free Languages, Countability, Turing Machines, and Fundamental Concepts. The questions span four difficulty levels, ranging from basic axiomatic definitions to complex Level 3 problems.
Key Results and Insights
Experimental evaluations revealed several critical findings:
- Performance Leaderboard: GPT-4 achieved the highest human-rated accuracy at 84.8%. However, the fine-tuned Llama3-8B model reached 81.2%, a 10% improvement over its base version, nearly matching GPT-4's performance despite its smaller parameter count.
- Knowledge Transfer: Interestingly, fine-tuning on ToC data improved performance on the MATH dataset (specifically in Algebra and Intermediate Algebra), suggesting that the logical rigor of ToC generalizes to broader mathematical reasoning.
- Evaluator Alignment: The AutoGrade-TQ system showed a 77.8% binary alignment with human experts. However, researchers noted a "judge bias" where LLMs tend to overrate mediocre answers and underrate exceptionally rigorous ones, often prioritizing pattern matching over deep logical verification.
Conclusion
TuringQ establishes a new standard for evaluating high-level theoretical reasoning in AI. While current models show promise, the gap between pattern matching and true formal proof construction remains. Future work will expand the benchmark to include code-generation tasks, such as simulating Turing Machines, to further push the boundaries of AI's computational understanding.
Summary updated