CombEval Benchmark Reveals LLM Weaknesses in Combinatorial Counting

This research introduces CombEval, a novel and dynamic benchmark specifically created to assess the proficiency of large language models (LLMs) in combinatorial counting. Unlike static collections of problems, CombEval leverages a structured Cofola specification to define problems based on entities, combinatorial objects, their dependencies, and constraints. This allows for the systematic generation of natural-language counting problems, each accompanied by an exact, solver-verified answer. The dynamic nature of CombEval enables researchers to precisely control and vary key problem parameters, such as object type, entity scale, the number of constraints, and the depth of reasoning required. This granular control provides a powerful diagnostic tool for understanding where and why LLMs falter in combinatorial reasoning. Evaluations conducted on eleven different LLMs, both in direct and code-augmented settings, revealed significant brittleness in their performance. Models consistently struggled with tasks involving ordered objects, indistinguishable elements, constraints based on relative positions, and nested object dependencies. Error analysis further pinpointed common failure modes, including misinterpreting problem constraints and misapplying fundamental counting principles. The findings suggest that while LLMs show promise, they still have considerable limitations in robust combinatorial reasoning. The code and generated benchmark suites are publicly available to support further research.