BOBCAT: Bilevel Optimization-Based Computerized Adaptive Testing

Aritra Ghosh, Andrew S. Lan

Abstract

Computerized adaptive testing (CAT) refers to a form of tests that are personalized to every student/test taker. CAT methods adaptively select the next most informative question/item for each student given their responses to previous questions, effectively reducing test length. Existing CAT methods use item response theory (IRT) models to relate student ability to their responses to questions and static question selection algorithms designed to reduce the ability estimation error as quickly as possible; therefore, these algorithms cannot improve by learning from large-scale student response data. In this paper, we propose BOBCAT, a Bilevel Optimization-Based framework for CAT to directly learn a data-driven question selection algorithm from training data. BOBCAT is agnostic to the underlying student response model and is computationally efficient during the adaptive testing process. Through extensive experiments on five real-world student response datasets, we show that BOBCAT outperforms existing CAT methods (sometimes significantly) at reducing test length.

Introduction

Computerized Adaptive Testing (CAT) is the core technology powering modern high-stakes examinations like the GRE and GMAT. The primary objective of CAT is to estimate a student's latent ability as efficiently as possible by adaptively selecting the most informative next question based on the student's history of responses. Traditionally, this has relied on Item Response Theory (IRT)—mathematical frameworks that model the probability of a correct response as a function of question difficulty and student ability.

However, traditional CAT methods are fundamentally limited by their static nature. They typically employ hand-crafted selection rules, such as uncertainty sampling, which do not improve as more data becomes available. Furthermore, these methods are often tightly coupled with simple IRT models, making it difficult to leverage modern, high-capacity deep learning architectures. To address these challenges, we introduce BOBCAT (Bilevel Optimization-Based CAT), a framework that treats question selection as a meta-learning problem.

The BOBCAT Framework

BOBCAT recasts the adaptive testing process into a bilevel optimization problem. This structure allows the system to learn a data-driven selection algorithm directly from large-scale historical student records.

The BOBCAT framework illustrating the inner-level student adaptation and outer-level global model optimization.

As illustrated in Figure 1, the framework operates through two nested loops:

  1. The Inner Loop: For a specific student, the system adaptively selects questions and updates a local estimate of that student's knowledge state or latent features.
  2. The Outer Loop: The system evaluates performance on a "meta-set" of held-out questions. It optimizes both the global response model and the question selection algorithm itself to maximize predictive accuracy on these unseen items.

Overcoming the Differentiability Barrier

A significant technical hurdle in learning a selection algorithm is that the act of "picking a question" is a discrete, non-differentiable operation, which prevents the direct use of standard backpropagation. We explored two primary strategies to resolve this:

  • Unbiased Estimator: Utilizing Reinforcement Learning-style policy gradients (e.g., PPO). While theoretically sound, this approach proved to be slow and characterized by high variance.
  • Approximate (Biased) Estimator: Leveraging influence functions. By treating question selection as a perturbation in the training process, we can approximate how a specific question would impact the final model loss. This method proved significantly more stable and effective for training the selection algorithm.

Experimental Results

We evaluated BOBCAT across five diverse, large-scale student response datasets: EdNet, Junyi, Eedi-1, Eedi-2, and ASSISTments. Our results demonstrate that BOBCAT is model-agnostic, performing well with both traditional IRT models (BiIRT) and modern Neural Networks (BiNN).

Performance comparison of BOBCAT variants against traditional CAT methods across five datasets, showing accuracy vs. number of questions.

As shown in Figure 2, BOBCAT variants consistently outperform traditional IRT-Active methods. Key insights from our evaluation include:

  • Efficiency Gains: BOBCAT often achieves the same predictive accuracy as traditional methods while requiring 50% to 75% fewer questions.
  • Superior Ability Estimation: Although optimized for prediction, BOBCAT leads to lower error in estimating the "true" student ability parameters compared to standard benchmarks.
  • Scalability: The performance advantage of BOBCAT is particularly pronounced on larger datasets like EdNet, highlighting the benefits of its data-driven approach.

Conclusion and Future Work

BOBCAT represents a paradigm shift in adaptive testing by moving from static, hand-crafted rules to learned, data-driven selection algorithms. While the training phase is computationally intensive, the resulting inference process is highly efficient for real-time testing. Future research will focus on addressing "test overlap" to ensure question security in high-stakes environments and investigating fairness constraints to prevent the selection algorithm from inheriting biases from historical data.

Summary updated

Abstract

Computerized adaptive testing (CAT) refers to a form of tests that are personalized to every student/test taker. CAT methods adaptively select the next most informative question/item for each student given their responses to previous questions, effectively reducing test length. Existing CAT methods use item response theory (IRT) models to relate student ability to their responses to questions and static question selection algorithms designed to reduce the ability estimation error as quickly as possible; therefore, these algorithms cannot improve by learning from large-scale student response data. In this paper, we propose BOBCAT, a Bilevel Optimization-Based framework for CAT to directly learn a data-driven question selection algorithm from training data. BOBCAT is agnostic to the underlying student response model and is computationally efficient during the adaptive testing process. Through extensive experiments on five real-world student response datasets, we show that BOBCAT outperforms existing CAT methods (sometimes significantly) at reducing test length.
BibTeX
@inproceedings{ghosh2021bobcat,
  author = {Aritra Ghosh and Andrew S. Lan},
  title = {{BOBCAT: Bilevel Optimization-Based Computerized Adaptive Testing}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=1zlyyGMMIe},
}
Figure