# Reasoning with Preference Constraints: A Benchmark for Language Models in Many-to-One Matching Markets

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 22 of its 54 references that are in the map.
- First posted on arXiv 16 Sep 2025.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

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

- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [gpt-oss-120b & gpt-oss-20b Model Card](https://mlsanity.com/paper/2508.10925/) (2025)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [A Survey on In-context Learning](https://mlsanity.com/paper/2301.00234/) (2022)
- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [Large Language Models for Mathematical Reasoning: Progresses and Challenges](https://mlsanity.com/paper/2402.00157/) (2024)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [SciBench: Evaluating College-Level Scientific Problem-Solving Abilities of Large Language Models](https://mlsanity.com/paper/2307.10635/) (2023)
- [How well do Large Language Models perform in Arithmetic tasks?](https://mlsanity.com/paper/2304.02015/) (2023)
- [Towards Optimizing with Large Language Models](https://mlsanity.com/paper/2310.05204/) (2023)
- [Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMs](https://mlsanity.com/paper/2503.10084/) (2025)
- [Inference-Time Computations for LLM Reasoning and Planning: A Benchmark and Insights](https://mlsanity.com/paper/2502.12521/) (2025)
- [CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization](https://mlsanity.com/paper/2504.04310/) (2025)
- [HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization](https://mlsanity.com/paper/2506.07972/) (2025)
- [Task Facet Learning: A Structured Approach to Prompt Optimization](https://mlsanity.com/paper/2406.10504/) (2024)
- [Beyond Prompt Content: Enhancing LLM Performance via Content-Format Integrated Prompt Optimization](https://mlsanity.com/paper/2502.04295/) (2025)
- [Game Theory Meets Large Language Models: A Systematic Survey with Taxonomy and New Frontiers](https://mlsanity.com/paper/2502.09053/) (2025)
- [Design of Chain-of-Thought in Math Problem Solving](https://mlsanity.com/paper/2309.11054/) (2023)
- [FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2505.16952/) (2025)
- [Combinatorial Optimization for All: Using LLMs to Aid Non-Experts in Improving Optimization Algorithms](https://mlsanity.com/paper/2503.10968/) (2025)
- [Stable Matching with Contingent Priorities](https://mlsanity.com/paper/2409.04914/) (2024)

## Abstract (arXiv)

Recent advances in reasoning with large language models (LLMs) have demonstrated strong performance on complex mathematical tasks, including combinatorial optimization. Techniques such as Chain-of-Thought and In-Context Learning have further enhanced this capability, making LLMs both powerful and accessible tools for a wide range of users, including non-experts. However, applying LLMs to matching problems, which require reasoning under preferential and structural constraints, remains underexplored. To address this gap, we introduce a novel benchmark of 369 instances of the College Admission Problem, a canonical example of a matching problem with preferences, to evaluate LLMs across key dimensions: feasibility, stability, and optimality. We employ this benchmark to assess the performance of several open-weight LLMs. Our results first reveal that while LLMs can satisfy certain constraints, they struggle to meet all evaluation criteria consistently. They also show that reasoning LLMs, like QwQ and GPT-oss, significantly outperform traditional models such as Llama, Qwen or Mistral, defined here as models used without any dedicated reasoning mechanisms. Moreover, we observed that LLMs reacted differently to the various prompting strategies tested, which include Chain-of-Thought, In-Context Learning and role-based prompting, with no prompt consistently offering the best performance. Finally, we report the performances from iterative prompting with auto-generated feedback and show that they are not monotonic; they can peak early and then significantly decline in later attempts. Overall, this work offers a new perspective on model reasoning performance and the effectiveness of prompting strategies in combinatorial optimization problems with preferential constraints.