# Constrained C-Test Generation via Mixed-Integer Programming

arXiv: https://arxiv.org/abs/2404.08821 · HTML: https://mlsanity.com/paper/2404.08821/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 73 references that are in the map.
- First posted on arXiv 12 Apr 2024.

## Builds on (most cited first, 17 of 17)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [DeBERTa: Decoding-enhanced BERT with Disentangled Attention](https://mlsanity.com/paper/2006.03654/) (2020)
- [TinyBERT: Distilling BERT for Natural Language Understanding](https://mlsanity.com/paper/1909.10351/) (2019)
- [Better Zero-Shot Reasoning with Role-Play Prompting](https://mlsanity.com/paper/2308.07702/) (2023)
- [Strong mixed-integer programming formulations for trained neural networks](https://mlsanity.com/paper/1811.08359/) (2018)
- [Efficient Methods for Natural Language Processing: A Survey](https://mlsanity.com/paper/2209.00099/) (2022)
- [One Small Step for Generative AI, One Giant Leap for AGI: A Complete Survey on ChatGPT in AIGC Era](https://mlsanity.com/paper/2304.06488/) (2023)
- [Is ChatGPT a Good Teacher Coach? Measuring Zero-Shot Performance For Scoring and Providing Actionable Insights on Classroom Instruction](https://mlsanity.com/paper/2306.03090/) (2023)
- [Smoothing parameter and model selection for general smooth models](https://mlsanity.com/paper/1511.03864/) (2015)
- [Empowering Active Learning to Jointly Optimize System and User Demands](https://mlsanity.com/paper/2005.04470/) (2020)
- [System Combination for Grammatical Error Correction Based on Integer Programming](https://mlsanity.com/paper/2111.01465/) (2021)
- [Manipulating the Difficulty of C-Tests](https://mlsanity.com/paper/1906.06905/) (2019)

## Abstract (arXiv)

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.