Search papers, labs, and topics across Lattice.
This paper introduces CombEval, a dynamic benchmark designed to evaluate combinatorial counting capabilities in large language models (LLMs) by representing problems as typed Cofola specifications. The framework allows for systematic variation in problem parameters, revealing that LLMs struggle with ordered objects, indistinguishable elements, and complex nested dependencies. Through rigorous evaluation, the study uncovers specific weaknesses in LLMs' understanding of constraints and counting principles, providing a valuable diagnostic tool for future research.
LLMs exhibit significant brittleness in combinatorial reasoning, particularly with ordered and indistinguishable elements, highlighting critical gaps in their understanding of constraints.
We present CombEval, a dynamic benchmark for evaluating combinatorial counting in large language models. CombEval represents each problem as a typed Cofola specification over entities, combinatorial objects, object dependencies, and constraints, enabling controlled generation of natural-language counting problems with exact solver-verified answers. Unlike static collections, CombEval supports systematic variation of object type, entity scale, constraint count, and reasoning depth. We evaluate 11 LLMs under direct and code-augmented settings and find that models remain brittle on ordered objects, indistinguishable elements, relatively positional constraints, and nested object dependencies. Error analysis further identifies failures in constraint interpretation and counting principles. CombEval provides a diagnostic testbed for studying when and why LLMs fail at combinatorial reasoning. The code and generated benchmark suites are publicly available at \url{https://github.com/YuxuZhou-CN/combination-problem-generation}.
