Enhancing Length Generalization for Attention Based Knowledge Tracing Models with Linear Biases

1 Introduction

Knowledge tracing (KT) is a sequential prediction task that utilizes the historical learning interaction data of students to predict their responses to future questions. This is achieved by modeling students' mastery of knowledge, i.e., knowledge states, as they interact with learning platforms such as massive open online courses (MOOCs) and intelligent tutoring systems. Solving the KT task can empower teachers to better guide students who need further attention or recommend personalized learning materials. This is crucial for the development of next-generation intelligent and personalized education.

∗Corresponding author.

Recently, with the rapid development of attention mechanisms [Vaswani et al., 2017], many attention based KT models are developed such as SAKT [Pandey and Karypis, 2019], SAINT [Choi et al., 2020] and simpleKT [Liu et al., 2023b]. To build an effective attention based KT model, a major design decision is the length of student interaction sequences at training stage, denoted L herein, which has been equivalent to the length of student interaction sequences at prediction stage. When computing the attention scores, incorporating more student interactions (achieved by a larger L) in the context window improves estimations of student knowledge mastery at prediction stage. However, longer interaction sequences are more expensive to train on [Press et al., 2022]. We refer to this as the length generalization of KT model, which denotes a KT model's capability to continue performing well as the number of student interactions increases beyond the number of interactions on which the KT model is trained.

While in some cases the attention based KT models trained on short sequences can be directly applied on longer interaction sequences at prediction stage, the performance degrades as the length of sequences increases (Shown in Figure 1). We train attention based KT models, such as SAKT [Pandey and Karypis, 2019], SAINT [Choi et al., 2020] and simpleKT [Liu et al., 2023b], on student interaction sequences with a fixed length of 200 and evaluate on sequences of varying lengths, i.e., 200, 400, 600, 800 and 1000. In Figure 1, these attention based KT models display lower prediction performance on longer sequences compared to shorter ones, which poses a significant challenge when generalizing the well-trained KT models to students who have long historical interaction sequences.

Furthermore, in real-world educational scenarios, there are intricate relationships between questions and their associated knowledge components (KCs) 1 . Effectively capturing these relationships may significantly boost the performance of KT models [Cui et al., 2023]. However, most existing attention based KT models, such as SAKT [Pandey and Karypis, 2019], SAINT [Choi et al., 2020] and simpleKT [Liu et al., 2023b], simply rely on the standard dot-product attention function, which computes the similarity between two student interactions by taking their inner product. Such inner product fails to model the complex and hidden structural properties of questions and their associated KCs.

Therefore, in this paper, we present KT solutions that are able to help models learn from short sequences and generalize well to longer sequences at prediction stage, and at the same time effectively capture complex relationships between questions and their associated KCs when learned from a collection of real-world student interaction data. Our work focuses on the refinements of a popular attention based KT baseline model, i.e., simpleKT [Liu et al., 2023b].

Briefly, the simpleKT model explicitly captures questionspecific variations of the individual differences among questions covering the same set of KCs and uses the standard dot-product attention function to extract the time-aware information embedded in the student learning interactions. However, when learning a standard simpleKT model from realworld educational datasets characterized by variations in interaction sequence lengths, several crucial questions arise: (1) Since the performance of attention based KT models notably drops on longer sequences, how can we maintain consistent and stable prediction performance across student interaction sequences of varying lengths? (2) Due to the fact that the questions and their associated KCs may contain intricate relationships, how can we effectively capture such complex and structural relationships?

In this work we address the above issues by introducing a novel KT model, i.e., stableKT that

• is able to learn from short sequences andmaintain stable and consistent performance when generalizing on long sequences by biasing query-key attention scores with penalties that are proportional to query-key distances.
• captures complex relationships between questions and their associated KCs by computing their similarities us-

1 A knowledge component (KC) is a generalization of everyday terms like concept, principle, fact, or skill.

• ing the depth of their lowest common ancestor in a hierarchy.
• supports accurate estimations of student knowledge state and response predictions.

Our stableKT model builds upon the standard simpleKT model and enhances its length generalization with linear biases applied to attention scores. It utilizes multi-head aggregation module to capture individual differences and complex hierarchical relationships. To ensure fair comparisons with recently developed deep learning based KT (DLKT) models, we choose to follow a publicly available standardized KT task evaluation protocol [Liu et al., 2022]. We conduct comprehensive and rigorous experiments on three public datasets, and the results show that our stableKT model is able to greatly enhance the length generalization and improve the prediction performance in terms of AUC.

2 Background and RelatedWorks

2.1 SimpleKT

The simpleKT is a popular and widely used KT baseline model that captures question-specific variations of the individual differences among questions covering the same set of KCs [Liu et al., 2023b]. It utilizes the standard dotproduct attention function to simplify the sophisticated student knowledge state estimation. The definitions of the simpleKT model are as follows:

where qt, ct, rt represent question, KC and response respectively at the (t)-th time step. The InteractionEncoder is an encoder that characterizes the latent factor of question difficulty. ˆ rt+1 and ht+1 denote prediction result and the extracted knowledge state respectively at the (t+1)-th time step. The PredictionLayer is a two-layer fully connected network.

2.2 RelatedWorks

Attention Based KT Models

Attention based KT models utilize attention mechanisms to capture relationships among student interactions. SAKT is the first research work that adopted a self-attention network to predict students' future performance [Pandey and Karypis, 2019]. Since then, many KT models use attention based network to capture the potential relationships between student interactions. Ghosh et al. proposed a monotonic attention mechanism, building upon the dot-product attention function, which computes attention weights with exponential time-related decay [Ghosh et al., 2020]. Huang et al. incorporated a k-selection module designed to choose relevant historical interactions based on the highest dot-product attention scores [Huang et al., 2023]. Im et al. represented forgetting behaviors as linear biases in their approach [Im et al., 2023]. Yin et al. designed a temporal and cumulative attention to diagnose students' knowledge proficiency from each question mastery state [Yin et al., 2023].

Length Generalization

The capability of length generalization allows a KT model to continue performing well as the length of student interaction sequences increases beyond the length of interaction sequences on which the KT model is trained. Position embedding plays an important role in length generalization [Press et al., 2022; Chi et al., 2023; Qin et al., 2024]. Sinusoidal position embedding employs sinusoidal functions with either non-learned or learnable parameters to generate position embedding and combines the position embedding with input embeddings [Vaswani et al., 2017; Jacob et al., 2019]. Different from Sinusoidal position embedding, Rotary position embedding computes embedding by sinusoidal functions with queries and keys instead of input embedding [Su et al., 2021]. T5 position embedding provides position embedding by adding a learned, shared bias to each query-key score before the softmax operation of attention [Raffel et al., 2020].

However, the KT models utilizing the above position embeddings both experience performance drops at prediction stage when applied to longer sequences. Inspired by [Press et al., 2022], we enhance the length generalization of our stableKT model by biasing query-key attention scores with penalties that are proportional to query-key distance. Additionally, different from existing attention based KT models, our stableKT model designs a multi-head aggregation module that combines dot-product attention and hyperbolic attention to capture a more complex relationship between questions and their associated KCs.

3 The StableKT Framework

3.1 ProblemDefinition

Our objective is to develop a KT model M that is able to learn from short student interaction sequences and maintain high prediction performance when applied on longer sequences. We refer to this as the length generalization of KT model, which is defined as follows:

Definition 1 (Length Generalization of KT Model). Given a student interaction dataset D, a KT model M, if for any lp that lp > lt, there is,

then KT model M is considered to have the capability of the length generalization, where aucp and auct denote the AUC scores on sequences with length lp and lt on prediction and training sequences respectively and ϵ is a small positive constant.

3.2 The Framework Overview

In this section, we present the framework overview of our stableKT model (Shown in Figure 2) that consists of five components: (1) interaction encoding module that explicitly uses a scalar to characterize the latent factor of question difficulty (See Section 3.3); (2) hyperbolic attention module that captures complex relationships between questions and their associated KCs (See Section 3.4); (3) length generalization module that enhances KT model prediction performance on longer sequences (See Section 3.5); (4) multi-head aggregation module that utilizes both the hierarchy-aware similarity score and the standard dot-product attention score (See Section 3.6); and (5) prediction module that uses a two-layer fully connected network to make prediction (See Section 3.7).

3.3 Interaction EncodingModule

Due to the fact that there are various difficulty levels between questions covering the same set of KCs, it is crucial to effectively represent student interactions. Similar to simpleKT [Liu et al., 2023b], we encode the interactions as follows:

where zct and art denote the latent representations of KC ct and student response rt on question qt. ect and ert represent the original s-dimensional and 2-dimensional one-hot vectors of the corresponding KC and response respectively. Wc ∈ Rd×s and Wr ∈ Rd×2 are learnable linear transformation operations. xt denotes the augmented embedding of KC ct with difficulty vector fqt . vct represents the questioncentric variation of qt covering this KC ct. qt denotes the question answered at the (t)-th timestamp. yt represents the embedding of interaction with response rt. ⊙ and ⊕ represent the element-wise product and addition operators respectively.

3.4 Hyperbolic AttentionModule

Existing attention based KT models mostly employ the dotproduct attention function to capture relationships between questions and their associated KCs in Euclidean space. The attention scores Sdot of dot-product attention are calculated by taking the inner product of query Q and key K as:

where √d is a scaling factor and the KT represents the transpose of K.

However, in real-world educational datasets, there exists a tree-like hierarchical relationship between questions and their associated KCs, which is a challenge to capture using dotproduct attention in Euclidean space. Following the previous work of [Yu et al., 2023; Tseng et al., 2023], we measure a hierarchy-aware similarity score of query Q and key K in hyperbolic space that is well-suited for embedding tree-like structures. Intuitively, the radius of a hyperbolic ball is directly proportional to its volume, which grows exponentially. Similarly, the number of leaves grows exponentially with respect to depth in a tree.

Hyperbolic Mapping

Since the hyperbolic space cannot be isometrically embedded into Euclidean space, similar to [Gulcehre et al., 2019; Tseng et al., 2023], in this work we use the Poincar´ e halfspace model to represent the hyperbolic space by a subset of Euclidean space. In the hyperbolic space represented by

̂

Poincar´ e half-space model, ideal points, points at infinity and geodesics 2 all have particularly nice Euclidean forms and details can be found at [Gulcehre et al., 2019; Yu et al., 2023; Tseng et al., 2023].

Here, we discuss mappings of student interactions from Euclidean space to the hyperbolic space. Specifically, let Xd be the last dimension of X and X[:-1] be the first d - 1 dimensions of X. Similar to [Tseng et al., 2023], we transform the query Q and key K matrices in the standard dot-product attention via the penumbral mapping function defined as follows:

where α is the mapping coefficient. Therefore, we obtain the mapped query matrix ˆQ and key matrix ˆK in the hyperbolic space, i.e.,

Similarity in Hyperbolic Space

In the hyperbolic space, the similarity between two data points reflects their hierarchical relationships. More specifically, we associate two points by the depth of their lowest common ancestor (LCA) in the cone partial ordering in hyperbolic cones, which is analogous to finding their LCA in a latent tree and captures how divergent two points are. We compute the attention scores in the hyperbolic space following the penumbral attention definition defined in [Tseng et al., 2023]. In particular, if Equation (1) holds true, as follows:

the hierarchy-aware similarity score Shyp in hyperbolic space is computed by:

2 The shortest path between two points.

where γ is a scaling coefficient and ∥·∥ denotes the L2-norm distance. If Equation (1) does not hold true, the hierarchyaware similarity score Shyp is computed by:

3.5 Length GeneralizationModule

To help stableKT continue performing well as the number of student interactions increases, inspired by [Press et al., 2022], we design a length generalization module that penalizes query-key attention scores with linear biases. Specifically, the linear biases implicitly contain relative position information of student interaction sequences by leveraging query-key distance in a computationally friendly way, which does not include learnable parameters and can avoid attention based KT model overfitting the position embeddings during training. We formulate the length generalization module g as follows:

where the matrices S, B and C denote attention scores (from either hyperbolic attention module or dot-product attention module), linear biases and causal mask respectively. The Softmax{·} represents softmax function.

The matrix B in Equation (2) penalizes attention scores with linear biases. Each element of matrix B is computed by:

where bmn denotes the element at the (m)-th row and (n)-th column of matrix B. The 2-8 iH denotes a coefficient that adjusts the attention scores for the (i)-th attention head out of H attention heads.

The matrix C in Equation (2) ensures that attention based KT models cannot peek the future interaction sequences of students. Each element of matrix C is computed by:

where cmn denotes the element at the (m)-th row and (n)-th column of C.

3.6 Multi-head AggregationModule

To effectively capture the intricate relationships between questions and their KCs, inspired by [Pan et al., 2022; Wang et al., 2023; Li et al., 2023], we design a multi-head aggregation module by concatenating dot-product attention head Hdot and hyperbolic attention head Hhyp:

where H(i) dot and H(j) hyp denote the (i)-th dot-product attention head and the (j)-th hyperbolic attention head respectively. V represents the value of attention. Wh ∈ Rd×s is a learnable linear transformation operation.

3.7 PredictionModule

We use a two-layer fully connected network to make prediction and optimize the prediction function by minimizing the binary cross-entropy loss between the ground-truth response rt+1 and the prediction probability ˆ rt+1 as follows:

where σ, ϕ denote Sigmoid and ReLU function. b1, b2, W1, W2 are trainable parameters.

4 Experiments

We present the details of our experiment settings and the corresponding results in this section. We conduct comprehensive analyses and investigations to illustrate the effectiveness of our stableKT model.

4.1 Datasets

We select three public real-world educational datasets to evaluate the effectiveness of our model.

• Algebra 2005-2006 (AL2005) 3 : The AL2005 dataset stems from KDD Cup 2010 EDM Challenge which includes 13-14 year-old students' interactions with Algebra questions. It has detailed step-level student responses to the mathematical problem. In our experiments, we use the concatenation of the problem name and step name as a unique question.
• Bridge to Algebra 2006-2007 (BD2006) 3 : The BD2006 dataset, similar to AL2005 dataset, consists of mathematical problems from logs of students' interactions with intelligent tutoring systems. The unique question construction of BD2006 dataset is similar to AL2005 dataset.

3 https://pslcdatashop.web.cmu.edu/KDDCup

• NeurIPS2020 Education Challenge (NIPS34) 4 : The NIPS34 dataset is provided by NeurIPS 2020 Education Challenge. We use the dataset of Task 3 & Task 4 to evaluate our models. It contains students' answers to mathematics questions from Eedi which millions of students interact with daily around the globe.

To ensure reproducibility in our experiments, we rigorously follow the data pre-processing steps suggested in [Liu et al., 2022]. We filter out student sequences that are shorter than 3 interactions. Data statistics are summarized in Table 1.

4.2 Baselines

We compare our stableKT model with the following stateof-the-art DLKT models to evaluate the effectiveness of our approach:

• DKT [Piech et al., 2015] uses a LSTM layer to encode the students' knowledge state for predicting their response performances.
• DKVMN [Zhang et al., 2017] exploits two memory networks to extract the relationships between different KCs and students' knowledge states.
• GKT [Nakagawa et al., 2019] casts the knowledge structure as a graph and reformulates the KT task as a time series node-level classification problem via a graph neural network.
• SAKT [Pandey and Karypis, 2019] leverages a selfattention mechanism to capture the relationships between question and KCs. It employs question embeddings as queries and utilizes interaction embeddings as both keys and values.
• SAINT [Choi et al., 2020] employs a Transformer-based encoder-decoder architecture to handle students' question and response sequences.
• AKT [Ghosh et al., 2020] introduces a monotonic attention to enhance self-attention by considering the students' forgetting behaviors.
• ATKT [Guo et al., 2021] exploits adversarial perturbations to the interaction embeddings to enhance robustness of the model.
• LPKT [Shen et al., 2021] uses a learning gate to distinguish students' absorptive capacity of knowledge and forgetting gate to model the decline of students' knowledge over time.
• simpleKT [Liu et al., 2023b] uses dot-product attention to extract the time-aware information embedded in student learning interactions.

4 https://eedi.com/projects/neurips-education-challenge

• DKT-AT [Liu et al., 2023a] performs two auxiliary learning tasks, including question tagging prediction and individualized prior knowledge prediction task, to enhance the predictive capability of DKT.
• sparseKT [Huang et al., 2023] incorporates a k-selection module to select relevant historical interactions with the highest attention scores to improve the robustness of attention based KT models.
• FoLiBiKT [Im et al., 2023] is an attention based KT model that represents forgetting behaviors as linear biases decoupled from the question correlation.
• DTransformer [Yin et al., 2023] exploits a two-level framework to explicitly diagnose learner's knowledge states and increase stability of knowledge state diagnosis by contrastive learning.

4.3 Experimental Setting

To evaluate the length generalization of KT models, all models are trained on student interaction sequences with the fixed length of 200 and evaluated on sequences with the length of 200, 400, 600, 800 and 1000, respectively. We perform standard 5-fold cross-validation for every combination of models and datasets. We choose to use early stopping when the performance is not improved after 10 epochs. For each hyperparameter combination, we use the Adam optimizer to train the models up to 200 epochs. We adopt the Bayesian search method to find the best hyperparameters for each fold. The embedding dimension, the hidden state dimension, the two dimension of the prediction layers are both set to [64, 256]. The learning rate, dropout rate and random seed are set to [1e-3, 1e-4, 1e-5], [0.05, 0.1, 0.3, 0.5] and [42, 3407] respectively. The scaling coefficient γ and mapping coefficient α are both set to [0.1, 0.3, 0.5, 0.7, 0.9, 1.0, 2.0, 5.0]. Similar to existing works [Liu et al., 2022; Piech et al., 2015; Ghosh et al., 2020], we use the AUC to evaluate the KT prediction performance.

4.4 Results

Overall Performance

We report the average AUC and the standard deviations across 5 folds. Table 2 shows the overall performance. From Table 2, we have the following observations: (1) Our stableKT model maintains stable and consistent prediction performance across different length of student interaction sequences in all three datasets. In comparison to sequences of length 200, the performance of most baseline models degrades notably as the length of sequences increases on three datasets. For example, simpleKT model exhibits significant drop in performance at sequences of length 1000 compared to sequences of length 200, reaching up to 5.55% on AL2005 dataset. This indicates that our stableKT model has the capability to generalize the well-trained KT model to students who have long historical interaction sequences. (2) At the same length of student sequences, our stableKT model outperforms all the baseline models in all three datasets and improves the AUC of the original simpleKT model by up to 6.93% on AL2005 dataset, 5.24% on BD2005 dataset and 1.00% on NIPS34 dataset at sequences of length 1000. This indicates that our model can better capture complex relationships between questions and their associated KCs by using a multi-head aggregation module. (3) The DKT and GKT do not exhibit notable performance drops among AL2005, BD2006 and NIPS34 datasets, but they achieve far less AUC than our model. Since these models do not rely on attention mechanisms, they typically do not face length generalization challenges. However, compared to our stableKT model, these models struggle to effectively model the knowledge states of students.

Table 2: Performance comparisons in terms of AUC. The best AUCs are in bold and the second-best AUCs are underlined.

Impact on Different Position Embeddings

As mentioned in Section 2, exploiting complex position embeddings, such as Sinusoidal, T5 and Rotary, usually hurts attention based KT models' capability of length generalization. We conduct experiments on our stableKT model with Sinusoidal, T5, Rotary and our length generalization module respectively. Figure 3 shows the results of our stableKT model with different position embeddings. From Figure 3, we have the following observations: (1) At different lengths of student interaction sequences, our length generalization module maintains stable and consistent high prediction performance while other position embeddings exhibit notable drops in performance. This indicates that our length generalization module can effectively enhance the length generalization of KT models than other position embeddings. (2) At the same length of student interaction sequences, using different position embeddings also affects the prediction performance of KT models, and our length generalization module can effectively improve the prediction performance.

Impact on Different Attention Mechanisms

We visualize the impact on dot-product attention and hyperbolic attention, as shown in Figure 4 and Figure 5. From that, we have the following observations: (1) Dot-product attention and hyperbolic attention, in Figure 4, focus on different information of questions. For example, when predicting the 19-th question, dot-product attention emphasizes information from questions 16, 17 and 18 while hyperbolic attention focuses on information from questions 0, 2, 3, 4, 5, 8, 13 and 18. This indicates that our multi-head aggregation module is able to utilize both dot-product attention and hyperbolic attention to capture more information of questions. (2) To further explore the characteristics of questions focused by hyperbolic attention, we visualize the questions that hyperbolic attention focuses on when predicting the 19-th question. As shown in Figure 5, the questions focused by hyperbolic attention, such as 0, 2, 3, 4, 5, 8, 13 and 18, exhibit a hierarchical relationship in terms of KCs, indicating that hyperbolic attention is able to capture hierarchical relationships of student interaction sequences. The Qs represents questions index and KCs denotes the questions' associated KCs index. The Maths[3] represents that the index 3 of KCs is Math, similarly for others.

Ablation Study

We systematically examine the effect of two key components in our stableKT model by constructing four model variants in Table 3. The MA represents the multi-head aggregation module. The LG denotes the length generalization module. The w/o means excluding such module from stableKT model. Please note that the stableKT w/o MA & LG is equivalent to the vanilla simpleKT model. From Table 3, we have the following observations: (1) Compared to other variants, stableKT model maintains stable and consistent high prediction performance in all cases. This empirically verifies the importance of both length generalization module and multi-head aggregation module. (2) When comparing stableKT w/o LG to stableKT w/o MA & LG, we can observe that if the model lacks the length generalization module, its performance notably degrades as the length of sequences increases. Furthermore, the stableKT w/o MA & LG experiences more performance drops compared to stableKT w/o LG. This indicates that the multi-head aggregation module also has a positive impact on length generalization.

5 Conclusion

In this paper, we propose stableKT model to enhance length generalization for standard attention based KT model. Specifically, our stableKT model is able to learn from short sequences and maintain stable performance when generalizing on long sequences. Furthermore, we design a multihead aggregation module to effectively capture individual differences and complex hierarchical relationships between questions and their associated KCs. Experimental results on three real-world educational datasets demonstrate that our stableKT model has the capability of length generalization and outperforms a wide range of state-of-the-art DLKT models in terms of AUC.

Acknowledgements

This work was supported in part by National Key R&D Program of China, under Grant No. 2022YFC3303600 and in part by Key Laboratory of Smart Education of Guangdong Higher Education Institutes, Jinan University (2022LSYS003).