Constrained C-Test Generation via Mixed-Integer Programming
This work addresses the challenge of automated test generation for educational applications, offering an incremental improvement over existing methods by integrating difficulty prediction models directly into optimization.
The paper tackled the problem of generating C-Tests, a type of cloze test, by proposing a mixed-integer programming approach that simultaneously optimizes gap size and placement for global optimality, outperforming two baseline strategies including GPT-4 in a user study with 40 participants.
This work proposes a novel method to generate C-Tests; a deviated form of cloze tests (a gap filling exercise) where only the last part of a word is turned into a gap. In contrast to previous works that only consider varying the gap size or gap placement to achieve locally optimal solutions, we propose a mixed-integer programming (MIP) approach. This allows us to consider gap size and placement simultaneously, achieving globally optimal solutions, and to directly integrate state-of-the-art models for gap difficulty prediction into the optimization problem. A user study with 40 participants across four C-Test generation strategies (including GPT-4) shows that our approach (MIP) significantly outperforms two of the baseline strategies (based on gap placement and GPT-4); and performs on-par with the third (based on gap size). Our analysis shows that GPT-4 still struggles to fulfill explicit constraints during generation and that MIP produces C-Tests that correlate best with the perceived difficulty. We publish our code, model, and collected data consisting of 32 English C-Tests with 20 gaps each (totaling 3,200 individual gap responses) under an open source license.