CombEval: A Framework for Evaluating Combinatorial Counting in Large Language Models

Researchers introduce CombEval, a dynamic benchmark framework for evaluating how well large language models handle combinatorial counting problems. Testing 11 LLMs reveals significant brittleness in handling ordered objects, indistinguishable elements, and nested dependencies, with code-augmented approaches showing modest improvements over direct reasoning.

CombEval addresses a critical gap in LLM evaluation by focusing on combinatorial reasoning, a foundational mathematical skill that existing benchmarks assess only superficially. The framework's typed Cofola specification system enables controlled, systematic problem generation with verified answers, moving beyond static test sets that can become memorized or saturated. This methodological advancement matters because combinatorial reasoning underpins applications in algorithm design, optimization, probability, and discrete mathematics—domains increasingly important for AI systems deployed in scientific and engineering contexts.

The research reveals that current LLMs struggle with specific structural patterns rather than struggling uniformly across counting problems. Failures cluster around ordered objects, indistinguishable elements, positional constraints, and nested dependencies—suggesting these patterns expose fundamental limitations in how models parse logical relationships and track constraint satisfaction. The fact that code-augmented approaches provide only marginal gains indicates the issue lies partly in problem interpretation rather than computational capacity.

For AI developers and researchers, CombEval serves as a diagnostic tool revealing where reasoning capabilities genuinely break down versus where training data sufficiency explains performance gaps. Organizations building LLM-powered analytical tools should recognize that combinatorial reasoning—essential for inventory optimization, scheduling, and constraint satisfaction problems—represents a meaningful weakness in current models. The public release of code and benchmark suites enables reproducible testing across model families and provides a foundation for targeted architectural improvements targeting reasoning robustness.

• →LLMs demonstrate systematic brittleness on ordered objects and nested dependencies rather than uniform counting failures.
• →Code-augmented reasoning provides only marginal improvements, suggesting constraint interpretation issues rather than computational limitations.
• →CombEval's dynamic generation framework enables systematic evaluation of reasoning robustness across controllable problem variations.
• →Constraint interpretation and counting principle failures represent distinct failure modes requiring different solutions.
• →The publicly available benchmark enables reproducible evaluation and future architectural improvements for combinatorial reasoning.