AlgoRAG: Retrieval-Augmented Generation for Theoretical Computer Science Education -- A Comprehensive Evaluation Framework for Algorithm Analysis and Complexity Theory

1 Introduction

• TCS students face challenges with formal proofs and asymptotic reasoning, while conventional resources offer little personalized, on-demand feedback.Instructors also face constraints in responding individually to students’ varied proof strategies and algorithmic questions.Source: §1 · p. 2
• General LLMs can hallucinate and may lack domain knowledge beyond their training data, risks that matter in learning settings requiring factual reliability.These limitations are especially relevant when students need authoritative content.Source: §1 · p. 2
• Educational RAG research has focused mainly on general curricula or broad STEM, leaving TCS proofs, notation, and asymptotic reasoning insufficiently addressed.Standard RAG pipelines can struggle with specialized vocabulary and notation.Source: §1 · p. 2
• AlgoRAG is designed for theoretical-CS education with a curriculum-spanning knowledge base and retrieval and generation tuned to mathematical content and instructional quality.Its evaluation assesses educational value in addition to answer correctness.Source: §1 · p. 2

LLMs in CS education

• CS-education work examines LLMs for explaining code, debugging, and algorithm understanding [2] [8], while noting misinformation concerns and the need for reliable support.Domain-specific tutoring research reports advantages for targeted systems when content demands are well-defined.Source: §2 · p. 2

Retrieval-Augmented Generation

• RAG research describes retrieval as a way to reduce hallucination and access current knowledge [4], with educational surveys reporting improved factual accuracy and reduced hallucination.The broader RAG landscape is surveyed in [10].Source: §2 · p. 2

Domain-specific RAG

• Domain-adaptation work reports specialized embeddings and re-ranking for technical vocabulary; AlgoRAG applies this approach to TCS with notation-aware retrieval and pedagogical ranking.The paper states these techniques had not previously been studied in this domain, to the authors’ knowledge.Source: §2 · p. 3

3 Knowledge Base Construction

• The knowledge base is organized around algorithm analysis and complexity theory to provide authoritative, multi-modal content across retrieval queries.Source: §3 · p. 3

Textbooks

• Two canonical textbooks provide foundational definitions, theorems, and examples: Introduction to Algorithms [11] and Introduction to the Theory of Computation.Source: §3 · p. 3

Lecture materials

• The collection includes 847 lecture slides arranged into 15 topic clusters, including asymptotic analysis, dynamic programming, graph algorithms, and NP-completeness.Source: §3 · p. 3

Practice problems and proof templates

• It also contains 312 solved practice problems, 156 worked proof examples, and 89 complexity worksheets on asymptotic analysis.The proof examples cover induction, contradiction, and constructive proofs.Source: §3 · p. 3

Indexing

• Topic, difficulty, and concept tags support an interconnected index that links related concepts and surfaces material even when query terminology differs.A recursion-tree query, for example, can retrieve recurrence-relation and divide-and-conquer material.Source: §3 · p. 3

Stage 1 — Query analysis

• Query analysis identifies algorithms, complexity indicators, variables, and proof markers, then uses a specialized recognizer to build a structured representation for retrieval.The recognizer labels CS and mathematical concepts and recognizes LaTeX-formatted notation.Source: §4 · p. 3

4 System Architecture

• Figure 1 presents AlgoRAG’s five-stage pipeline, from mathematical query preprocessing through hybrid retrieval and pedagogical ranking to generation and notation post-processing.Source: §4 · p. 3, Figure 1 · p. 4

Stage 2 — Hybrid retrieval

• Hybrid retrieval combines fine-tuned dense-vector search with sparse exact-term search, then scores candidates for semantic similarity, notation consistency, and domain relevance.Source: §4 · p. 5

Stage 3 — Pedagogical re-ranking

• Pedagogical re-ranking scores retrieved material for clarity, step-by-step detail, worked examples, and fit with the query’s inferred difficulty.Source: §4 · p. 5

Stage 4 — Generation

• Generation assembles top-ranked excerpts into a structured prompt with definitions, theorem statements, examples, and solutions, using mandatory response sections and consistent notation.DeepSeek V3 was selected after preliminary Llama 2 and Mistral experiments showed insufficient multi-step mathematical-proof performance.Source: §4 · p. 5

Stage 5 — Post-processing

• Post-processing normalizes inline mathematics, checks proof steps against simple consistency rules, and formats responses with numbered steps and case analyses.Source: §4 · p. 5

Implementation

• The Python implementation uses all-mpnet-base-v2 embeddings, ChromaDB, and a custom evaluation harness; processing 179 questions took about 1.9 hours.PDF ingestion uses 500-token windows with 50-token overlap.Source: §4 · p. 5

5 Domain-Specific Optimizations

• Mathematical entity recognition distinguishes notation such as O(n) from a variable and uses proof markers to retrieve relevant proof templates.The system identifies algorithmic concepts and mathematical notation in queries.Source: §5 · p. 5
• Notation-aware similarity treats log n and log2 n as contextually equivalent and uses a CS knowledge graph to connect related concepts.These signals augment vector search so paraphrased queries can reach conceptually related material.Source: §5 · p. 5
• Pedagogical ranking scores retrieved material for readability, step granularity, worked examples, and fit with query difficulty.Introductory questions receive higher-weight introductory materials, while complex queries are directed toward more formal sources.Source: §5 · p. 6
• Specialized handlers retrieve proof outlines, normalize notation and inject tools such as the Master Theorem for complexity analysis, and synthesize definitions for comparisons.The optimizations reflect the need for explicit domain adaptation to technical vocabulary and notation.Source: §5 · p. 6

6.1 Dataset Construction

• The test set comprises 179 questions drawn from past exams, practice tests, and algorithmic problem sets across seven TCS topics, including asymptotic analysis, recurrence relations, dynamic programming, graph algorithms, and NP-completeness.The cited passages specify 89 asymptotic-analysis, 17 recurrence-relations, 17 dynamic-programming, 21 graph-algorithm, and 21 NP-completeness questions.Source: §6.1 · p. 6
• Each question has an instructor-written reference answer and metadata for topic, difficulty, and expected proof techniques.The dataset also includes 6 sorting and 8 divide-and-conquer questions.Source: §6.1 · p. 6

6.2 Evaluation Metrics

• ROUGE-1, ROUGE-2, and ROUGE-L F1 measure n-gram overlap, while embedding cosine similarity measures conceptual alignment beyond surface wording.ROUGE is treated as approximate because equivalent mathematical proofs can use substantially different wording.Source: §6.2 · pp. 6–7
• The pedagogical quality score averages six binary criteria per response, including step-by-step exposition, correct notation, worked examples, query coverage, and explanation depth.Proof-step granularity is also scored; the rubric is applied consistently to all 179 responses and is intended to measure educational value independently of surface wording.Source: §6.2 · p. 7
• The sixth pedagogical criterion scores whether each logical transition in a proof is explicitly justified.The authors consider the pedagogical score more appropriate for this domain than ROUGE or BLEU because it captures educational value independently of wording.Source: §6.2 · p. 7
• Success rate is the share of queries answered within a 240-second timeout, and response time records seconds to final output for feasibility assessment.BLEU-4 is also tracked; the authors interpret zero scores as reflecting differences in notation, variable names, and proof strategy between logically equivalent proofs.Source: §6.2 · p. 7

7.1 Overall Performance

• BLEU-4 was zero across questions; ROUGE-1 F1 was 0.0963, ROUGE-2 F1 was 0.0285, semantic similarity was 0.0752, and pedagogical quality was 0.7620.The authors attribute low semantic similarity partly to responses that are more expansive than brief references, often including additional context, alternative proof strategies, and examples.Source: §7.1 · pp. 7–8
• 100% of 179 questions were answered successfully, with a mean response time of 38.0 seconds.Table 1 summarizes aggregate performance.Source: §7.1 · p. 7, Table 1 · p. 8
• Despite low lexical-overlap scores, AlgoRAG’s high pedagogical quality suggests it synthesizes material from multiple knowledge-base sources into richer, student-oriented explanations rather than simply paraphrasing individual passages.Source: §7.1 · p. 8

7.2 Topic-Specific Analysis

• The final evaluation reached a 100% success rate, an improvement over preliminary testing that the authors attribute to switching to DeepSeek V3 and optimized prompting.The preliminary tests used a smaller question sample and locally hosted models.Source: §7.2 · p. 8
• Across topics, ROUGE-1 F1 ranged from 0.0876 to 0.1285 while pedagogical quality ranged from 0.6629 to 0.8250; NP-completeness had the highest ROUGE-1 F1 at 0.1285.Sorting had the highest pedagogical quality (0.8250) despite six test cases; graph algorithms scored 0.8086 among topics with n ≥20, while recurrence relations scored lowest at 0.6629. Table 2 reports per-topic metrics.Source: §7.2 · pp. 8–9, Table 2 · p. 8, Figure 2 · p. 9

7.3 Pedagogical Observations

• About 65% of responses had fully enumerated step-by-step reasoning, 78% correctly formatted notation, and 42% included a concrete worked example.On average, 71% of key sub-questions were covered, and explanation depth was satisfactory in about 80% of responses.Source: §7.3 · p. 9
• Whether richer outputs improve student learning relative to concise reference answers remains an open question for future user studies.The authors identify this as an unresolved issue despite the combination of high pedagogical quality and low ROUGE.Source: §7.3 · p. 9

• 100% success across 179 diverse questions accompanies a pedagogical quality score of 0.7620 and coverage across all topic areas.Source: §8 · pp. 9–10
• BLEU-4 is zero because equivalent mathematical proofs can share almost no 4-grams, making this a metric limitation rather than evidence of system failure.The discussion calls for domain-aware metrics such as pedagogical scoring alongside lexical-overlap measures.Source: §8 · p. 10
• 38.0 seconds per query suits asynchronous study but not real-time classroom interaction.Prompt caching, concurrent retrieval, and model quantization are proposed to reduce deployment latency.Source: §8 · p. 10
• The ROUGE–pedagogical-quality disconnect illustrates how lexical overlap can miss pedagogically equivalent proofs using different valid bounds.The paper argues that automated educational-AI assessment should prioritize conceptual similarity and rubric-based scoring over n-gram matching.Source: §8 · p. 10
• Entity tagging and pedagogical re-ranking appear to contribute to consistency, while recurrence relations remain hardest to standardize, suggesting a need for more proof templates.Source: §8 · p. 10
• Educational effectiveness remains unmeasured in a controlled user study, and the public-resource knowledge base may miss newer algorithmic results.The results rely on the DeepSeek V3 API, and only 42% of responses included worked examples.Source: §8 · p. 10

• AlgoRAG couples DeepSeek V3 with a curated domain-specific knowledge base and optimizes mathematical entity recognition, notation-aware retrieval, and pedagogical ranking.Source: §9 · p. 10
• 100% success on 179 expert-curated questions, with a mean response time of 38.0 seconds and pedagogical quality score of 0.7620, supports explanations across the TCS curriculum.Source: §9 · p. 11
• The strongest reported topic results include NP-completeness, graph algorithms, and sorting algorithms.Reported values are NP-completeness (ROUGE-1 F1 = 0.1285, pedagogical quality = 0.7643), graph algorithms (pedagogical quality = 0.8086), and sorting algorithms (pedagogical quality = 0.8250).Source: §9 · p. 11
• The paper contributes an integrated TCS knowledge base, a domain-specific RAG pipeline, and a rubric-based pedagogical measure alongside NLP metrics.It presents the evaluation framework as a reusable benchmark methodology for educational AI systems.Source: §9 · p. 11
• Planned work targets the 42% worked-example retrieval rate, latency, recurrence-relation reasoning, controlled learning-gain studies, and extensions to adjacent formal fields.Proposed directions include reweighting practice problems, adding recurrence solvers and lightweight theorem provers, and studying learning gains relative to static resources.Source: §9 · p. 11

• The complete AlgoRAG implementation, evaluation scripts, and experimental configurations are publicly available in the repository.Source: Data and Code Availability · p. 11
• The repository includes the knowledge-base construction pipeline, retrieval modules, and evaluation framework.Source: Data and Code Availability · p. 11
• The 179-question TCS test set, reference answers, and metadata are provided for replication and future research.Source: Data and Code Availability · p. 11