💬 NLP

Automated Knowledge Component Generation for Interpretable Knowledge Tracing in Coding Problems

This paper introduces KCGen-KT, an automated LLM-based pipeline that generates and tags knowledge components for open-ended coding problems, demonstrating through extensive evaluation that these AI-generated components outperform traditional human-written ones in predicting student performance and modeling learning curves.

Original authors: Zhangqi Duan, Nigel Fernandez, Arun Balajiee Lekshmi Narayanan, Mohammad Hassany, Rafaella Sampaio de Alencar, Peter Brusilovsky, Bita Akram, Andrew Lan

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhangqi Duan, Nigel Fernandez, Arun Balajiee Lekshmi Narayanan, Mohammad Hassany, Rafaella Sampaio de Alencar, Peter Brusilovsky, Bita Akram, Andrew Lan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a teacher trying to figure out exactly what a student is struggling with in a coding class. In the old days, you'd have to manually write down a list of specific skills (like "knowing how to use a loop" or "understanding how to add numbers") and then go through every single homework problem to tag which skills it tested. This is like a librarian manually writing a card catalog for every book in a massive library; it takes forever, is prone to human error, and is incredibly boring.

This paper introduces a new, automated way to do this using Artificial Intelligence (specifically, Large Language Models or LLMs), but with a twist: it works for open-ended coding problems, where students write their own code from scratch, rather than just picking answers from a multiple-choice list.

Here is a breakdown of what they did, using simple analogies:

1. The Problem: The "Open-Ended" Chaos

In multiple-choice questions, there is only one right answer, so it's easy to guess what skill was being tested. But in coding, students can solve the same problem in ten different ways. One student might use a "for loop," while another uses "regular expressions." Both get the right answer, but they used different skills.

The Analogy: Imagine asking people to build a birdhouse. If you give them a multiple-choice quiz, you know exactly what they learned. But if you ask them to build it, one person might use a hammer and nails, while another uses glue and wood. Figuring out exactly which skills each person used just by looking at the finished birdhouse is very hard.

2. The Solution: The AI "Skill Detective"

The authors built a three-step automated pipeline to act as a "Skill Detective":

Step 1: The Investigation (Generation): They feed the AI a coding problem and a bunch of different student solutions (both correct and incorrect). The AI acts like a detective, reading the code and saying, "Ah, to solve this, you needed to know how to use an 'If statement' and how to do 'Math with absolute values'." It creates a list of these skills (called Knowledge Components, or KCs).
Step 2: The Sorting Hat (Clustering): The AI might generate 100 slightly different names for the same skill (e.g., "If-Else," "Conditional Logic," "Decision Making"). The system groups these similar ideas together, like sorting a pile of mixed socks into pairs.
Step 3: The Label Maker (Summarization): Finally, the AI looks at each group of similar skills and gives them one clear, human-readable name (like "Conditional Logic"). It then tags every problem with these new, clean labels.

3. The Result: A Smarter Tutor (KCGen-KT)

Once the AI has these skill labels, they built a new "Knowledge Tracing" system (a way to track student learning over time) called KCGen-KT.

How it works: Instead of just guessing if a student will get the next question right or wrong, this system looks at the student's history with specific skills. It asks, "Does this student struggle with 'Loops' but ace 'Variables'?"
The Magic: The system translates the student's skill level into a "soft token" (a digital signal) that the AI can read. This allows the AI to predict not just if the student will fail, but what their next piece of code will look like.

4. The Proof: Did it Work?

The researchers tested this on two real-world datasets containing thousands of student coding submissions (one in Java, one in Python).

Better than Humans: Surprisingly, the AI-generated skill tags actually helped predict student performance better than the tags written by human experts.
Better than Old AI: The new system beat previous state-of-the-art AI models that didn't use these specific skill tags.
The "Learning Curve" Check: They checked if the system followed the "Law of Practice" (the idea that people get better the more they practice). The AI-generated skills showed a clear pattern: as students practiced a specific skill more, their error rate went down. This proved the AI was identifying real, meaningful skills.
Human Approval: When they showed the AI's work to actual computer science teachers, the teachers agreed that the AI's skill descriptions were clear, understandable, and accurate.

Summary

In short, this paper says: "We taught an AI to automatically figure out exactly what skills students are using in their coding homework. We then used those AI-generated skill tags to build a smarter system that predicts how students will do in the future. It works better than human experts and better than previous AI methods, and it helps us understand student learning in a way that is clear and interpretable."

What they did NOT claim:

They did not claim this replaces teachers; they explicitly state it is meant to support them.
They did not test this on math or science problems yet (only coding).
They did not claim it is perfect; they noted that sometimes the AI misses skills shared across problems because it analyzes them one by one.

Technical Summary: Automated Knowledge Component Generation and Interpretable Knowledge Tracing in Coding Problems

Problem Statement
In student modeling, Knowledge Components (KCs) are essential for assessing fine-grained skill mastery, enabling personalized feedback, and driving adaptive learning systems. Traditionally, KCs are crafted and tagged to problems by human domain experts, a process that is labor-intensive, prone to bias, and difficult to scale. While prior work has explored automated KC generation for multiple-choice questions, open-ended problems—particularly in programming—remain under-studied. Open-ended coding problems present unique challenges: student responses exhibit significant diversity, errors can occur in myriad ways, and multiple valid solution approaches may exist, each covering different sets of KCs. Existing automated methods often fail to capture this complexity or rely on rigid syntactic structures unsuitable for diverse student submissions.

Methodology
The authors propose a two-part framework: an automated pipeline for generating and tagging KCs using Large Language Models (LLMs), and a novel Knowledge Tracing (KT) method, KCGen-KT, that leverages these generated KCs.

Automated KC Generation Pipeline:
- Initial Generation: For each programming problem, the system selects a diverse set of representative correct student code submissions (clustered via CodeBERT embeddings to ensure variety). It prompts GPT-4o with few-shot examples and chain-of-thought reasoning to identify fine-grained KCs required to solve the problem, converting existing topic tags into natural language descriptions.
- Clustering and Abstraction Control: To manage granularity, the textual descriptions of generated KCs are embedded using Sentence-BERT. Hierarchical Agglomerative Clustering (HAC) is applied to merge semantically similar KCs. By adjusting the number of clusters, the system controls the abstraction level, moving from specific function-level skills to broader conceptual groupings.
- Labeling: GPT-4o is prompted to summarize each cluster into a single, informative label (either selecting an existing KC or synthesizing a new description). Finally, a Q-matrix is constructed by mapping each problem to its corresponding summarized KCs.
KCGen-KT (Knowledge Tracing Framework):
- Architecture: The model uses Llama 3 (8B parameters) as a backbone for multi-task learning, predicting both the binary correctness of the next student submission and the actual code token-by-token.
- Student State Modeling: A standard LSTM updates a student's latent knowledge state ( $h_t$ ) based on past problem text, code, and correctness. This state is projected into a mastery vector ( $m_t$ ) representing proficiency on each unique KC.
- Soft-Token Conversion: To integrate mastery levels into the LLM's input space, the model converts discrete mastery values into "soft tokens." A mastery level $m^j_t$ for KC $j$ is transformed into a weighted combination of the embeddings for "true" and "false" tokens: $s^j_t = m^j_t \cdot \text{emb}_{\text{true}} + (1 - m^j_t) \cdot \text{emb}_{\text{false}}$ . This allows gradients to flow through the mastery parameters during training.
- Interpretability: The model employs a compensatory model to aggregate individual KC mastery levels into an overall mastery score, ensuring that higher knowledge on specific KCs correlates with a higher probability of a correct response.
- Training Objective: The system minimizes a combined loss function including code generation loss (cross-entropy), correctness prediction loss (binary cross-entropy), and a regularization loss to enforce monotonicity between KC mastery and correctness.

Key Contributions

First Automated Pipeline for Open-Ended Coding: The paper presents the first LLM-based pipeline capable of generating and tagging KCs specifically for open-ended programming problems, addressing the diversity and complexity of student code submissions.
Interpretable KT with Soft Tokens: The authors introduce KCGen-KT, which explicitly models student mastery on textual KC descriptions. The novel soft-token conversion mechanism allows the LLM to utilize continuous mastery levels as inputs, bridging the gap between latent student states and textual generation.
Empirical Validation: The framework is evaluated on two real-world datasets (CodeWorkout and FalconCode) containing thousands of student submissions.

Results

Performance: KCGen-KT outperforms existing state-of-the-art KT methods (including TIKTOC and Code-DKT) and baselines using human-written KCs. Specifically, the version using LLM-generated KCs achieves statistically significant improvements in AUC, F1 score, accuracy, and CodeBLEU (for code generation) across both datasets.
Granularity Analysis: Experiments varying the abstraction level of KCs reveal that overly abstract KCs (high-level clusters) degrade performance, while medium-to-low abstraction levels (finer granularity) yield the best results. This suggests that sufficient detail is crucial for accurate student modeling.
Learning Curves: The generated KCs align better with the power law of practice (error rates decreasing with practice) compared to human-written KCs, achieving a higher weighted $R^2$ (0.21 vs. 0.18) when fitted to learning curve models.
Human Evaluation: Instructors rated LLM-generated KCs as highly interpretable (98.6% vs. 94.6% for human baselines) and found the problem-KC mappings to have high precision (93.2%) and coverage (96% of cases had equal or greater coverage than human baselines).

Significance and Claims
The paper claims that high-quality, automatically generated KCs and accurate tagging are critical for improving downstream student modeling performance. The authors demonstrate that LLMs can effectively identify fine-grained skills in open-ended coding tasks, often surpassing human-written tags in predictive power and alignment with cognitive learning principles.

The work is modestly scoped to computer science education due to data availability constraints (the need for large-scale, longitudinal open-ended student response data). The authors acknowledge that their pipeline currently relies on in-context examples and that future work should explore human-in-the-loop refinement, direct optimization for learning curve fitting, and application to other domains like mathematics and science. They emphasize that their approach is intended to support educators by reducing manual labor, not to replace human judgment, and recommend expert review before deployment in real educational settings.