测试大模型在有偏好约束的匹配问题中的推理能力，发现其表现不一且提示策略效果波动。
Reasoning with Preference Constraints: A Benchmark for Language Models in Many-to-One Matching Markets
- 构建369个大学录取匹配问题实例，评估模型可行性、稳定性和最优性
- 推理型模型（如QwQ）显著优于普通模型（如Llama），但均难同时满足所有标准
- 不同提示方法效果各异，迭代提示中性能先升后降，无单调提升规律
近年来，大语言模型（LLMs）在复杂数学任务上的推理能力取得显著进展，包括组合优化。链式思维（Chain-of-Thought）和上下文学习（In-Context Learning）等技术进一步提升了其性能，使非专家用户也能便捷使用。然而，将LLMs应用于需在偏好与结构约束下推理的匹配问题仍处于探索阶段。为此，我们引入一个包含369个实例的全新基准——大学录取问题（College Admission Problem），作为偏好型匹配问题的典型范例，用于评估模型在可行性、稳定性与最优性三个维度的表现。通过该基准评估多个开源权重的LLMs，结果表明：尽管模型可满足部分约束，但难以一致达成全部标准；推理型模型（如QwQ、GPT-oss）显著优于传统模型（如Llama、Qwen、Mistral，即未使用专门推理机制的模型）。此外，不同提示策略（链式思维、上下文学习、角色提示）表现各异，无一种始终最优。最后，迭代提示结合自动生成反馈的结果显示性能并非单调上升，可能早期达到峰值后显著下降。本研究为理解模型在具偏好约束的组合优化中的推理表现及提示策略有效性提供了新视角。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。