Solving Combinatorial Counting Problems with Weighted First-Order Model Counting

• URL: http://arxiv.org/abs/2605.24845v1
• Date: Sun, 24 May 2026 03:29:19 GMT
• Title: Solving Combinatorial Counting Problems with Weighted First-Order Model Counting
• Abstract summary: We present Cofola (COmbinatorial counting LAnguage with Firstpreserving logic), a typed language that maps every Cofola program to a well-defined counting problem.<n>Cofola produces concise specifications and a uniform solving pipeline that is practical end-to-end.
• Score: 2.2680525506361717
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial counting problems pervade artificial intelligence, statistics, and discrete mathematics. Whether the task is enumerating subsets, multisets, permutations, partitions, or compositions under structural and arithmetic constraints, solving it remains a stubbornly manual exercise. Closed-form derivations are powerful but brittle, while naive encodings to propositional model counting or constraint satisfaction destroy the exchangeability that makes counting tractable in the first place. We present Cofola (COmbinatorial counting LAnguage with First-Order logic), a typed declarative language whose primitives are the combinatorial objects that recur in everyday counting questions, including sets, bags, tuples, sequences, circles, partitions, and compositions, together with natural relational and arithmetic constraints over them. A denotational semantics maps every Cofola program to a well-defined combinatorial counting problem, and a three-phase compilation pipeline (preprocessing, decomposition, and symmetry-preserving encoding) reduces this problem to a weighted first-order model counting (WFOMC) instance augmented with coefficient-extraction constraints. To stay inside known domain-liftable fragments whenever possible, the encoding groups indistinguishable entities, breaks the symmetry of unordered groupings lexicographically, and encodes sequences and circles via order axioms. On a suite of representative combinatorial counting problems, ranging from textbook math problems to multi-object scenarios that the closest prior framework cannot express, Cofola produces concise specifications and a uniform solving pipeline that is practical end-to-end.

Related papers

• CombEval: A Framework for Evaluating Combinatorial Counting in Large Language Models [12.245682714937338]
  CombEval represents each problem as a typed Cofola specification over entities, objects, object dependencies, and constraints.<n>Unlike static collections, CombEval supports systematic variation of object type, entity scale, constraint count, and reasoning depth.
  arXiv  Detail & Related papers  (2026-06-18T04:47:49Z)
• Automatic Generation of Polynomial Symmetry Breaking Constraints [0.0]
  We propose a method to generate a random family of inequalities which can be used as symmetry breakers.<n>The method requires as input an arbitrary base and a group of symbolic permutations which is specific to the integer program.<n>It turns out that simple symmetry breakers, especially combining few variables and permutations, most consistently reduce work time.
  arXiv  Detail & Related papers  (2026-02-09T06:05:10Z)
• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  Chain-of-Thought (CoT) prompting enhances the reasoning of large language models (LLMs) by decomposing problems into sequential steps.<n>We propose Syzygy of Thoughts (SoT)-a novel framework that extends CoT by introducing auxiliary, interrelated reasoning paths.<n>SoT captures deeper logical dependencies, enabling more robust and structured problem-solving.
  arXiv  Detail & Related papers  (2025-04-13T13:35:41Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)
• From Exponential to Polynomial Complexity: Efficient Permutation Counting with Subword Constraints [0.0]
  Counting distinct permutations with replacement, especially when involving multiple subwords, is a longstanding challenge in analysis. This paper introduces a novel framework that presents closed-form formulas for calculating distinct permutations with replacement. We then extend our foundational formula to handle multiple subwords through the development of an additional formula.
  arXiv  Detail & Related papers  (2024-11-23T19:52:11Z)
• Synthesising Recursive Functions for First-Order Model Counting: Challenges, Progress, and Conjectures [12.47276164048813]
  First-order model counting (FOMC) is a computational problem that asks to count the models of a sentence in finite-domain first-order logic. We relax the restrictions that typically accompany domain recursion to work with directed graphs that may contain cycles. These improvements allow the algorithm to find efficient solutions to counting problems that were previously beyond its reach.
  arXiv  Detail & Related papers  (2023-06-07T06:49:01Z)
• Mutual Exclusivity Training and Primitive Augmentation to Induce Compositionality [84.94877848357896]
  Recent datasets expose the lack of the systematic generalization ability in standard sequence-to-sequence models. We analyze this behavior of seq2seq models and identify two contributing factors: a lack of mutual exclusivity bias and the tendency to memorize whole examples. We show substantial empirical improvements using standard sequence-to-sequence models on two widely-used compositionality datasets.
  arXiv  Detail & Related papers  (2022-11-28T17:36:41Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  We introduce a new model-oriented approach for Answer Set Programming that lifts the Symmetry Breaking Constraints into a set of interpretable first-order constraints. Experiments demonstrate the ability of our framework to learn general constraints from instance-specific SBCs.
  arXiv  Detail & Related papers  (2021-12-22T11:27:48Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  We study the issue of receiving infinite-length sequences from a recurrent language model. We propose two remedies which address inconsistency: consistent variants of top-k and nucleus sampling, and a self-terminating recurrent language model.
  arXiv  Detail & Related papers  (2020-02-06T19:56:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.