Model Counting and Sampling in First-Order Logic (Abstract of Invited Talk)

Ondrej KuzelkaDescription Logics 2024 · OpenReview

Abstract

Weighted First-Order Model Counting (WFOMC) and Sampling (WFOMS) represent a powerful intersection of mathematical logic, combinatorics, and probability. This paper, based on an invited talk by Ondřej Kuželka, examines the state of the art in these fields, focusing on identifying "tractable" fragments of first-order logic. Specifically, it highlights how fragments like two-variable logic with counting ($C^2$) enable "domain-liftable" inference—where the complexity of counting or sampling scales polynomially with the number of objects in a domain, rather than exponentially. By treating combinatorial and probabilistic problems as logical counting tasks, these frameworks provide a declarative approach to complex structural reasoning.

Introduction: The Counting Problem

In fields ranging from machine learning to discrete mathematics, two fundamental questions often arise: how many ways can a specific configuration occur (Model Counting), and can we generate a random instance of such a configuration (Sampling)? In the context of first-order logic, these tasks are generally #P-complete. As the number of objects (the domain) increases, the number of possible configurations grows exponentially, making general-purpose reasoning intractable.

The research addressed here seeks to find the boundaries of tractability—identifying specific logical constraints under which these problems can be solved efficiently. The goal is to move from standard First-Order Model Counting (FOMC) to a weighted version (WFOMC) that can represent probabilistic models like Markov Logic Networks by assigning weights to predicates.

Domain Liftability and Tractable Fragments

The core concept in this research is domain liftability. An algorithm is domain-liftable if its running time is polynomial in the size of the domain (the number of individuals or objects), regardless of the specific logic sentence's complexity.

Research has identified that the two-variable fragment ($FO^2$) and its extension with counting quantifiers ($C^2$) are domain-liftable. This means that if a problem can be expressed using only two variables, it can be solved efficiently even for very large domains. Conversely, adding a third variable ($FO^3$) typically pushes the problem into the realm of intractability. This boundary defines the current limits of efficient automated reasoning in first-order logic.

Logic as a Universal Sampler

One of the most compelling applications of this framework is its use as a "universal sampler." Traditionally, sampling complex combinatorial structures—such as specific types of graphs or valid "Secret Santa" assignments—requires custom-coded algorithms and deep combinatorial knowledge.

By using WFOMS, a researcher can simply describe the rules of the structure in $C^2$ logic. The framework then acts as a declarative engine, automatically computing probabilities or generating valid samples. For instance, a complex variant of a Secret Santa game can be encoded into a $C^2$ sentence, allowing a general-purpose solver to handle the underlying math automatically. This approach has the potential to automate the generation of data for resources like the Online Encyclopedia of Integer Sequences (OEIS), where logic engines can derive sequences for newly defined combinatorial structures.

Performance and Symmetry

A key advantage of first-order approaches over standard propositional (SAT-based) samplers is the exploitation of symmetry. Propositional samplers often "flatten" a problem into millions of individual boolean variables, losing the high-level structure and relationships. WFOMS algorithms, by contrast, reason at the first-order level, recognizing that many objects in the domain are interchangeable. This allows them to exploit inherent symmetries, often outperforming state-of-the-art propositional samplers on structured first-order problems.

Future Outlook and Limitations

While the theoretical foundations of domain liftability are well-established, practical implementation remains an active area of research. Current WFOMS algorithms, while faster than propositional alternatives for first-order problems, are not yet optimized enough for standard data science libraries like NumPy.

There remains a constant tension between expressivity and complexity; moving beyond the $C^2$ fragment without hitting the wall of intractability is a significant challenge. Future work aims to bridge this gap, moving toward a future where logic-based declarative frameworks are a standard tool for programmers to sample and reason about complex, large-scale structures without needing to develop custom algorithms from scratch.

Summary updated

BibTeX
@inproceedings{kuzelka2024model,
  author = {Ondrej Kuzelka},
  title = {{Model Counting and Sampling in First-Order Logic (Abstract of Invited Talk)}},
  booktitle = {Description Logics},
  year = {2024},
  url = {https://openreview.net/forum?id=PExovVbCEf},
}
Figure