Abstract
Automated exam assembly systems often struggle to balance topical relevance with a fair distribution of item attributes, such as difficulty levels and content sources. This paper introduces a multi-stage re-ranking pipeline that leverages Mixed-Integer Linear Programming (MILP) and Large Language Models (LLMs) to mitigate attribute bias. By formulating item selection as a constrained optimization problem, the proposed system ensures that retrieved questions meet specific pedagogical requirements without compromising search accuracy. Experimental results on a large-scale vocational education dataset demonstrate that our MILP-based approach significantly outperforms existing heuristic methods, providing a robust solution for real-world educational platforms.
Introduction
Creating high-quality assessments is a complex task for educators. An ideal exam must not only cover the relevant subject matter but also maintain a balanced distribution of difficulty levels and item types. In modern educational technology, educators often rely on automated retrieval systems to pull questions from vast databases. However, standard semantic search algorithms frequently exhibit "attribute bias." For instance, a query for a specific technical topic might return a list dominated by "Hard" questions or items generated solely by AI, leading to exams that are psychometrically unbalanced.
The tension between "relevance" (how well an item matches a query) and "fairness" (how well the selection represents a target attribute distribution) presents a significant challenge. This research addresses this gap by integrating advanced optimization techniques into the retrieval process, ensuring that automated exam assembly is both accurate and pedagogically sound.
The EdTec-QBuilder Pipeline
The authors propose a novel framework integrated into the EdTec-QBuilder platform. The process moves from initial item creation to a sophisticated re-ranking stage designed to eliminate bias.
The pipeline consists of four primary stages:
- Expert-LLM Collaboration: Human experts leverage LLMs to populate a diverse base of test items.
- Item Base Management: Items are pre-validated and tagged with metadata, including difficulty levels and source information.
- Dense Retrieval: An initial pool of candidate items is selected using semantic search (Approximate Nearest Neighbor search combined with Cross-Encoders).
- MILP Re-ranking: The final selection is optimized using Mixed-Integer Linear Programming to satisfy specific distribution targets.
Methodology: Optimization and Query Expansion
The core innovation lies in the MILP Re-ranking stage. Unlike greedy algorithms that pick the top $N$ items, the MILP approach treats selection as a global optimization problem. The objective function maximizes total relevance while minimizing the "Total Variation Distance" between the retrieved set's attributes and a predefined target distribution (e.g., an equal split between Easy, Medium, and Hard questions).
To further enhance performance, the researchers introduced two variants:
- MILP-LLM: This method uses GPT-4o for query expansion. By transforming simple user queries into detailed sets of skill terms, the system improves the initial relevance scores, providing the MILP solver with a higher-quality pool of candidates.
- MILP-BOpt: This variant employs Bayesian Optimization to automatically tune the trade-off parameter ($\lambda$) between relevance and fairness. This allows the system to find the optimal balance dynamically for different types of queries.
Experimental Results
The system was evaluated using a benchmark dataset from German vocational education and training (VET) services, comprising 5,624 validated items. The researchers compared their MILP-based methods against nine other debiasing techniques, including Maximal Marginal Relevance (MMR) and $\epsilon$-greedy strategies.
Key findings from the evaluation include:
- Superior Relevance and Fairness: The MILP-BOpt method improved relevance (nDCG) by 17% over the previous industry baseline while reducing attribute bias (AWRF) by 9%.
- Pareto Efficiency: The MILP approach effectively pushed the "Pareto frontier," maintaining higher topical accuracy even under strict fairness constraints compared to heuristic methods like MMR.
- Real-time Viability: Despite the mathematical complexity of integer programming, the MILP solver consistently found optimal solutions within milliseconds, making it suitable for interactive software environments.
Conclusion and Future Work
This research demonstrates that Mixed-Integer Linear Programming, particularly when augmented by LLM-based query expansion, offers a powerful tool for mitigating bias in educational item retrieval. By moving beyond simple heuristics to a target-aware optimization model, the EdTec-QBuilder system provides educators with a more reliable way to assemble balanced exams.
Future research will focus on scaling the system to handle a larger number of simultaneous attributes (such as language level and specific sub-skills) and exploring "in-training" debiasing techniques to further integrate fairness into the underlying neural models.
Summary updated