Retrieval-Augmented Tutoring for Algorithm Tracing and Problem-Solving in AI Education

Mragisha Jain, Tirth Bhatt, Griffin Pitts, Aum Pandya, Peter Brusilovsky, Narges Norouzi, Arto Hellas, Juho Leinonen, Bita Akram

TL;DR

KITE (Knowledge-Informed Tutoring Engine) is a novel, RAG-based intelligent tutoring system designed to help students master complex algorithmic reasoning without just handing them the answers. By combining a multi-stage retrieval pipeline with an intent-aware Socratic response strategy, KITE successfully diagnoses student errors and provides scaffolded hints, leading to an 88.89% improvement rate in answers generated by simulated student models.

What Problem Does This Paper Address?

When learning complex computer science topics like algorithm tracing and debugging, students frequently turn to large language models (LLMs) like ChatGPT for immediate assistance. However, generic LLMs present two major pitfalls in an educational setting:

  1. The "Shortcut" Problem: They tend to provide direct solutions immediately, allowing students to bypass the productive struggle and reasoning processes essential for deep learning.
  2. Lack of Alignment: They often use terminology, notations, or conventions that differ from the specific course curriculum, or worse, they hallucinate incorrect steps.

While Retrieval-Augmented Generation (RAG) can ground an LLM in specific course textbooks and slides, standard RAG systems still act as direct question-answering tools. The challenge tackled by this paper is building a tutoring system that remains strictly faithful to course materials while dynamically adapting its pedagogical strategy—shifting between direct explanations and Socratic scaffolding based on how a student asks for help.

Methods

The authors introduce KITE, an architecture that pairs a robust multi-stage retrieval pipeline with an intent-aware response generator.

Figure 1: KITE architecture

The system operates in five distinct phases:

  1. Document Ingestion and Preprocessing: Text is extracted from course PDFs using PyMuPDF. A frequency-based cleaning step removes repetitive headers, footers, and page numbers across pages before segmenting the text into section-aware chunks of roughly 500 characters.
  2. Embedding Generation: Chunks are encoded into 3072-dimensional embeddings using OpenAI’s text-embedding-3-large model and stored in a FAISS index.
  3. Multi-Stage Retrieval Pipeline: To balance high recall and precision, KITE uses a hybrid search combining dense bi-encoder similarity (70% weight) and sparse BM25 keyword matching (30% weight). It then applies Maximal Marginal Relevance (MMR) to eliminate redundancy, reranks the remaining chunks with a cross-encoder, and applies a "source-based boost" to prioritize official course materials.
  4. Intent Classification & Response Generation: Incoming student queries are classified into one of five pedagogical intents: Direct Question, Conceptual Questions, Algorithm Validation, Debugging, or Algorithm Tracing. KITE uses an LLM (GPT-5, as specified in the paper) to generate responses tailored to these intents. For example, validation and debugging requests trigger a Socratic assessment strategy that offers progressive hints rather than direct answers.
  5. Session Management: KITE tracks conversation state across multi-turn dialogues, appending brief summaries of prior turns to the prompt to maintain context and prevent hint repetition.

Datasets

The system was evaluated using a newly constructed dataset of 109 questions curated from the lecture slides and textbook of a university-level Introduction to AI course. Each question was paired with an instructor-verified reference answer. The dataset includes:

  • 42 algorithmic questions (e.g., conceptual mechanics of search algorithms)
  • 51 procedural questions (e.g., requests to trace or validate specific algorithm executions)
  • 16 direct-retrieval questions (e.g., factual definitions)

Key Insights and Ideas

  • Intent-Driven Pedagogy: The core innovation is that retrieval and generation must be gated by student intent. An AI tutor shouldn't treat a request to "debug my code" the same way it treats "what is the definition of A* search."
  • The Factual Correctness Metric Trap: The evaluation revealed a massive gap between RAGAs Factual Correctness (0.45) and Answer Similarity (0.76). Because RAGAs decomposes responses into rigid atomic claims and checks for strict entailment against a single reference answer, it heavily penalizes Socratic, pedagogically framed responses that paraphrase, elaborate, or ask guiding questions—even when the underlying science is entirely accurate.
  • Simulated Students for Interactive Evaluation: Evaluating multi-turn Socratic dialogue is notoriously difficult. The authors successfully utilized a stronger model (KITE) to tutor a weaker model (Meta-Llama-3.1-70B-Instruct) acting as a proxy student, creating a scalable framework to test educational interaction loops before deploying them to real classrooms.

Key Results

The authors evaluated KITE using automated RAGAs metrics for non-procedural questions, alongside a simulated student pipeline and expert human review for procedural tasks.

Figure 2: Evaluation pipeline
  • High Grounding and Relevance: KITE achieved a Context Relevance score of 0.9352 and a Faithfulness score of 0.8486, demonstrating that the multi-stage pipeline successfully surfaces highly pertinent course content and keeps the model anchored to it (see Figure 3).
  • Substantial Answer Improvement: Among the 27 interactive sessions where the simulated student initially provided an incorrect or incomplete answer, 88.89% (24 cases) showed measurable improvement after receiving KITE’s Socratic feedback (see Figure 4). The most frequent transition was from "Partially Correct" to "Correct" (31.82%).
  • Expert Validation: Three human experts evaluated the quality of the tutoring interactions using a structured rubric. KITE received an overwhelming 93.18% positive ("Yes") rating across the dimensions of scaffolding, guidance, coherence, and encouraging tone (see Figure 5).

Limitations and Future Work

  • Automated Metric Limitations: The low factual correctness scores highlight the limitations of using single-reference RAGAs metrics for conversational, educational AI. Future work will focus on developing richer, multi-answer reference sets.
  • LLM Proxy vs. Real Students: While the simulated student pipeline (Meta-Llama-3.1-70B-Instruct) is excellent for early-stage automated testing, it cannot fully replicate the unpredictable nature, diverse misconceptions, or emotional frustrations of real human learners. The authors emphasize that a live classroom deployment with pre- and post-interaction assessments is the critical next step.
  • Sample Size: The expert human evaluation was constrained to 44 interaction triples. Expanding this annotation dataset will be necessary to confidently generalize the findings across a broader array of error types.

Summary updated

Abstract

Students learning algorithms often need support as they interpret traces, debug reasoning errors, and apply procedures across unfamiliar problem instances. In this paper, we present KITE (Knowledge-Informed Tutoring Engine), a Retrieval-Augmented Generation (RAG)-based intelligent tutoring system designed to serve as a classroom teaching assistant for algorithmic reasoning and problem-solving tasks. KITE uses an intent-aware Socratic response strategy to tailor support to different student needs, responding with targeted hints, guiding questions, and progressive scaffolding intended to strengthen students' algorithmic problem-solving ability. To keep responses aligned with course content, KITE uses a multimodal RAG pipeline that retrieves relevant information from course materials. We evaluate KITE using three forms of assessment: RAGAs-based metrics for response grounding and quality, expert evaluation of pedagogical quality, and a simulated student pipeline in which a weaker language model interacts with KITE across two-turn dialogues and produces revised answers after receiving feedback. Results indicate that KITE produces contextually grounded and pedagogically appropriate responses. Further, using simulated students, KITE's feedback helped the student models produce more accurate follow-up responses on procedural and tracing questions, suggesting that its scaffolding can support algorithmic problem-solving. This work contributes a tutoring architecture and an evaluation approach for assessing retrieval-grounded explanations and scaffolded problem-solving feedback.
BibTeX
@inproceedings{jain2026retrieval,
  author = {Mragisha Jain and Tirth Bhatt and Griffin Pitts and Aum Pandya and Peter Brusilovsky and Narges Norouzi and Arto Hellas and Juho Leinonen and Bita Akram},
  title = {{Retrieval-Augmented Tutoring for Algorithm Tracing and Problem-Solving in AI Education}},
  booktitle = {BEA},
  year = {2026},
  doi = {10.18653/v1/2026.bea-1.57},
}

Loading related content...

Figure