TLDR: A new research paper introduces a benchmark of 369 College Admission Problem instances to evaluate how Large Language Models (LLMs) handle many-to-one matching problems with preference constraints. The study found that LLMs trained for reasoning significantly outperform base models, but all models struggle with consistency as problem size increases. Prompting strategies have varied impacts, with no single best approach, and iterative feedback doesn’t guarantee monotonic improvement. This work highlights the challenges and nuances of applying LLMs to complex combinatorial optimization tasks involving preferences.
Large Language Models (LLMs) have shown incredible progress in tackling complex tasks, from advanced mathematics to strategic decision-making in games. These powerful AI tools, especially with techniques like Chain-of-Thought and In-Context Learning, are becoming more accessible to everyone, including those without deep technical expertise.
However, when it comes to matching problems – scenarios where individuals or entities need to be paired up based on specific preferences and rules – LLMs face a unique set of challenges. These problems require a different kind of reasoning, one that considers not just efficiency but also fairness and satisfaction among all parties involved. Think about college admissions, hospital-resident placements, or even school choice programs; these are all real-world examples of many-to-one matching markets where preferences and capacities play a crucial role.
To better understand how LLMs perform in these intricate situations, researchers Marylou Fauchard, Florian Carichon, Margarida Carvalho, and Golnoosh Farnadi introduced a new benchmark. Their paper, titled “Reasoning with Preference Constraints: A Benchmark for Language Models in Many-to-One Matching Markets,” delves into the capabilities of various LLMs using 369 instances of the College Admission Problem. This problem is a classic example of matching with preferences, and the benchmark evaluates LLMs on three key dimensions: feasibility (can the solution be implemented?), stability (are there any pairs who would rather be together than with their assigned matches?), and optimality (is it the best possible outcome for the students?). You can read the full paper here.
Evaluating LLM Performance in Matching Markets
The study assessed several open-weight LLMs, categorizing them into ‘base models’ (like Llama, Qwen, or Mistral) and ‘reasoning models’ (such as QwQ and GPT-oss, which are specifically trained for thinking and reasoning). The findings revealed some interesting insights:
- Reasoning Models Lead the Way: LLMs specifically designed for reasoning, like QwQ and GPT-oss, significantly outperformed the base models across all evaluation criteria. This highlights that specialized training is crucial for handling the complexities of preference-based matching.
- Challenges with Consistency: While LLMs could satisfy some constraints, they struggled to consistently meet all evaluation criteria, especially stability and optimality, which require a deeper understanding of blocking pairs and overall satisfaction.
- Size Matters (of the Problem, not the Model): As the number of students in the matching problem increased, the performance of all LLMs declined. However, reasoning models showed a less drastic drop, indicating better resilience to increasing complexity. Surprisingly, the type of student preferences (whether complete, incomplete, or flexible) had less impact on performance than the sheer number of participants.
- Prompting Strategies are Tricky: The way a problem is presented to an LLM, known as the prompting strategy, also played a significant role. Strategies like Chain-of-Thought, In-Context Learning, and role-based prompting were tested, but no single prompt consistently delivered the best performance across all models. Interestingly, base models seemed to benefit more from detailed, guiding prompts, while reasoning models performed better with more general instructions, suggesting they can leverage their advanced capabilities with less explicit guidance.
- Iterative Prompting: Not a Silver Bullet: The researchers also explored iterative prompting, where LLMs receive feedback on their previous attempts to refine their answers. While this method showed some promise, the improvements were not always consistent or monotonic. Performance could peak early and then decline, raising questions about how LLMs truly integrate and learn from feedback in these complex reasoning tasks.
Also Read:
- AI’s Role in Clinical Trial Recruitment: Insights from Social Media Analysis
- Evaluating AI Agent Architectures for Enterprise Workflows
Implications for AI and Optimization
This research offers a fresh perspective on how LLMs handle combinatorial optimization problems with preferential constraints. It underscores that even for problems solvable in polynomial time (meaning they don’t become exponentially harder with more data), ensuring LLM outputs are feasible, stable, and optimal is far from simple. The study suggests that while LLMs are powerful, their application in structured decision-making contexts like matching markets requires careful consideration of model training, problem complexity, and prompting techniques.
Looking ahead, this work paves the way for further research into how LLMs can be refined to better align optimization outcomes with individual preferences. Future efforts might explore combining different prompting strategies, providing more detailed feedback, or even using LLMs not just as solvers, but as interpreters that can suggest the most appropriate matching approaches based on specific user priorities, such as stability, efficiency, or fairness.
