Automated Knowledge Component Generation and Knowledge Tracing for Coding Problems

Zhangqi Duan, Nigel Fernandez, Sri Kanakadandi, Bita Akram, Andrew S. Lan

Abstract

Knowledge components (KCs) mapped to problems help model student learning, tracking their mastery levels on fine-grained skills thereby facilitating personalized learning and feedback in online learning platforms. However, crafting and tagging KCs to problems, traditionally performed by human domain experts, is highly labor intensive. We present an automated, LLM-based pipeline for KC generation and tagging for open-ended programming problems. We also develop an LLM-based knowledge tracing (KT) framework to leverage these LLM-generated KCs, which we refer to as KCGen-KT. We conduct extensive quantitative and qualitative evaluations on two real-world student code submission datasets in different programming languages. We find that KCGen-KT outperforms existing KT methods and human-written KCs on future student response prediction. We investigate the learning curves of generated KCs and show that LLM-generated KCs result in a better fit than human written KCs under a cognitive model. We also conduct a human evaluation with course instructors to show that our pipeline generates reasonably accurate problem-KC mappings.

Introduction

In Intelligent Tutoring Systems, Knowledge Tracing (KT) serves as the core engine for personalization by tracking a student’s mastery of specific skills, or Knowledge Components (KCs), such as "Nested Loops" or "Array Indexing." This tracking informs pedagogical decisions, such as selecting the next optimal problem for a student.

However, a significant bottleneck exists: the creation of a "Q-matrix" that maps problems to KCs. Traditionally, this process is labor-intensive, subjective, and static, making it difficult to scale or adapt to evolving curricula. In open-ended programming, the challenge is amplified because a single problem can often be solved through multiple strategies, each requiring different underlying skills.

Methodology

Automated KC Generation Pipeline

To overcome the manual tagging bottleneck, the researchers developed an automated pipeline using GPT-4o. The process follows a "Generate-Cluster-Label" workflow:

  1. Initial Generation: The LLM analyzes problem statements and representative student solutions to identify fine-grained skills.
  2. Clustering: Using Sentence-BERT embeddings and Hierarchical Agglomerative Clustering, redundant skills are grouped. This allows for adjustable abstraction levels.
  3. Labeling: The LLM generates human-readable labels for each cluster.
The automated pipeline for generating, clustering, and labeling Knowledge Components (KCs) using GPT-4o.

KCGen-KT Framework

The KCGen-KT framework utilizes Llama 3 to perform knowledge tracing. Key components include:

  • Mastery Tracking: An LSTM network tracks student mastery levels for each generated KC over time.
  • Soft-Token Conversion: Mastery levels are converted into differentiable "soft-token" embeddings, allowing the LLM to process nuanced mastery states rather than binary values.
  • Multi-task Learning: The model is trained to simultaneously predict the correctness of the next student attempt and the specific code the student is likely to produce.
Architecture of the KCGen-KT framework, integrating student knowledge states with an LLM for multi-task learning.

Evaluation and Results

The framework was evaluated on two datasets: CodeWorkout (Java, 10,834 submissions) and FalconCode (Python, 28,617 submissions).

Key Findings

  • Superior Predictive Accuracy: KCGen-KT achieved an AUC of 0.816 on the Java dataset, outperforming state-of-the-art baselines and models using human-written KCs (0.797).
  • Granularity and Abstraction: The study found that medium-level abstraction (50-60 clusters) provided the best balance between specificity and generalization.
  • Pedagogical Validity: Generated KCs followed the "power law of practice," where student error rates decreased predictably with practice, confirming they represent genuine learning units.
  • Code Generation: The model successfully predicted student code with a CodeBLEU score of 0.580, a significant improvement over existing methods.
  • Human Validation: Instructors rated the generated KCs as 98.6% interpretable and found the problem-to-skill mappings to be highly accurate.

Conclusion and Future Work

KCGen-KT demonstrates that LLMs can automate the creation of high-quality pedagogical structures that were previously the sole domain of human experts. Future work includes refining global skill sets through human-in-the-loop approaches, explicitly optimizing for the "power law of practice" in the loss function, and expanding the pipeline to other complex domains like mathematics and science.

Summary updated

Abstract

Knowledge components (KCs) mapped to problems help model student learning, tracking their mastery levels on fine-grained skills thereby facilitating personalized learning and feedback in online learning platforms. However, crafting and tagging KCs to problems, traditionally performed by human domain experts, is highly labor intensive. We present an automated, LLM-based pipeline for KC generation and tagging for open-ended programming problems. We also develop an LLM-based knowledge tracing (KT) framework to leverage these LLM-generated KCs, which we refer to as KCGen-KT. We conduct extensive quantitative and qualitative evaluations on two real-world student code submission datasets in different programming languages.We find that KCGen-KT outperforms existing KT methods and human-written KCs on future student response prediction. We investigate the learning curves of generated KCs and show that LLM-generated KCs result in a better fit than human written KCs under a cognitive model. We also conduct a human evaluation with course instructors to show that our pipeline generates reasonably accurate problem-KC mappings.
BibTeX
@misc{duan2025automated,
  author = {Zhangqi Duan and Nigel Fernandez and Sri Kanakadandi and Bita Akram and Andrew S. Lan},
  title = {{Automated Knowledge Component Generation and Knowledge Tracing for Coding Problems}},
  year = {2025},
  eprint = {2502.18632},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.18632},
}
Figure