Maximum Entropy Relaxation of Multi-Way Cardinality Constraints for Synthetic Population Generation
François Pachet, Jean-Daniel Zucker, [6pt] ImagineAllThePeople, Paris, France · 2026
Read Maximum Entropy Relaxation of Multi-Way Cardinality Constraints for Synthetic Population Generation by François Pachet, Jean-Daniel Zucker, [6pt] ImagineAllThePeople, Paris, France (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-22558.txt.
Introduction
Pachet and Zucker tackle the problem of building synthetic populations that match many stated statistics at once. Planners need fake populations for simulations and privacy-safe data release. The targets can mix one-way, two-way, and three-way counts drawn from surveys or expert notes. Exact matching scales badly as targets pile up. Their fix borrows from statistical physics: match the counts on average under a maximum-entropy rule. On benchmarks with up to forty traits, their method pulls ahead as the targets grow more tangled.
Catalog record
| CREATOR | François Pachet, Jean-Daniel Zucker, [6pt] ImagineAllThePeople, Paris, France |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38794 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.22558
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Maximum Entropy Relaxation of Multi-Way Cardinality Constraints for Synthetic Population Generation François Pachet, Jean-Daniel Zucker, [6pt] ImagineAllThePeople, Paris, France Abstract Generating synthetic populations from aggregate statistics is a core component of microsimulation, agent-based modeling, policy analysis, and privacy-preserving data release. Beyond classical census marginals, many applications require matching heterogeneous unary, binary, and ternary constraints derived from surveys, expert knowledge, or automatically extracted descriptions. Constructing populations that satisfy such multi-way constraints simultaneously poses a significant computational challenge. We consider populations where each individual is described by categorical attributes and the target is a collection of global frequency constraints over attribute combinations. Exact formulations scale poorly as the number and arity of constraints increase, especially when the constraints are numerous and overlapping. Grounded in methods from statistical physics, we propose a maximum-entropy relaxation of this problem. Multi-way cardinality constraints are matched in expectation rather than exactly, yielding an exponential-family distribution over complete population assignments and a convex optimization problem over Lagrange multipliers. We evaluate the approach on NPORS-derived scaling benchmarks with 4 to 40 attributes and compare it primarily against generalized raking. The results show that MaxEnt becomes increasingly advantageous as the number of attributes and ternary interactions grows, while raking remains competitive on smaller, lower-arity instances. Keywords: synthetic population generation; maximum entropy; cardinality constraints; constraint programming; exponential family models 1 Introduction Synthetic population generation has become a foundational problem for contemporary AI systems in settings where individual-level microdata are unavailable, legally restricted, or prohibitively expensive to collect. At the same time, many downstream tasks—such as simulation, forecasting, and counterfactual analysis—require large numbers of representative agents rather than aggregate statistics alone. This need arises across a growing range of domains. In public policy and politics, synthetic populations are used to evaluate reforms, study voting behavior, and explore demographic scenarios without exposing sensitive personal data. In health and epidemiology, they support large-scale simulations of disease propagation, intervention strategies, and healthcare demand. In retail and marketing, they enable customer behavior modeling, demand forecasting, and what-if analyses in environments where individual data are fragmented or protected. More broadly, synthetic populations provide a bridge between aggregate statistics, expert knowledge, and agent-based models, allowing AI systems to reason about societies, markets, and institutions at scale while respecting privacy and regulatory constraints. Recent work on LLM-based synthetic personas further broadens this perspective beyond classical microsimulation: DeepMind’s Persona Generators expands compact contextual descriptions into diverse synthetic populations tailored to arbitrary settings, with an explicit emphasis on covering rare but consequential trait combinations ( 13 ) . This renewed interest also aligns with a broader practitioner view that synthetic data can serve as a flexible design lever for shaping AI system behavior. 1 1 1 For example, Karpathy describes using LLM-generated synthetic conversations to inject identity and behavior into a small language model ( 11 ) . In these settings, individuals are described by a vector of categorical attributes (e.g., age bracket, gender, region, occupation), and the population must match a set of published or estimated aggregates. A convenient formalization is to specify a set of frequency constraints over patterns of attribute values. For example: “ 52\% female” (unary), “ 18\% female and age 35–44” (binary), or “ 4\% female, age 35–44, and living in Île-de-France” (ternary). Such requirements are naturally expressed in constraint programming as cardinality constraints. Unary cardinalities are efficiently handled by the Global Cardinality Constraint (GCC) with strong filtering ( 16 ) . However, multi-attribute constraints (arity \geq 2 ) are typically modeled as Sum constraints over reified predicates or over contingency-table cell counts. These overlapping linear constraints often provide weak propagation and become difficult to satisfy at scale, especially when many higher-order constraints are specified or when targets are noisy or mutually inconsistent. Synthetic population generation has been extensively studied in microsimulation, transportation modeling, and survey methodology, using approaches ranging from combinatorial optimization and calibration to iterative reweighting and probabilistic modeling ( 1 ; 18 ; 7 ; 9 ) . These methods have enabled large-scale applications, but typically rely on either unary marginals or fully specified contingency tables, and assume internal consistency of the target statistics. In contrast, many contemporary applications involve selectively specified, heterogeneous, and potentially noisy multi-way constraints, for which existing approaches either do not scale or fail to provide robust solutions. This gap motivates alternative formulations that can accommodate partial and higher-order information without requiring exact feasibility. This paper proposes a probabilistic alternative: a maximum-entropy relaxation of multi-way cardinality-constrained population synthesis. Instead of searching directly for a discrete population, we infer a distribution over full attribute assignments whose expectations match the required frequencies. By the maximum-entropy principle ( 10 ) , the solution belongs to an exponential family with one parameter per constraint. This transforms a difficult combinatorial problem into convex optimization over Lagrange multipliers, after which populations can be sampled efficiently. By construction, the maximum-entropy distribution is as unbiased as possible given the imposed constraints. 1.0.1 Contributions. We provide: (i) a formalization of population synthesis constraints as multi-way cardinality (Sum) CSPs over contingency tables; (ii) a maximum-entropy relaxation that recasts this problem as convex optimization over an exponential-family model; (iii) a practical fitting and sampling procedure in the exact-enumeration regime, together with a convex penalized extension for inconsistent targets; and (iv) an NPORS-derived benchmark family that reveals when MaxEnt overtakes generalized raking as dimensionality and constraint arity increase. 2 Related Work 2.1 Cardinality Constraints in CP The Global Cardinality Constraint (GCC) ( 16 ) enforces lower and upper bounds on the number of occurrences of atomic values across a set of variables sharing a domain, and supports strong propagation via flow-based filtering. In population synthesis, unary marginals can be expressed directly as GCCs over per-individual attribute variables. However, GCCs do not naturally extend to multi-attribute patterns: binary and ternary marginals correspond to joint counts rather than counts of atomic values, and therefore cannot be captured by a single GCC over the original variables. Such constraints typically require reification and additional Sum constraints, or contingency-table formulations with explicit count variables, which substantially weakens propagation. Recent work by 15 proposes a CP framework for exact synthetic population generation from aggregate statistics and structural relations, using a batch-based construction strategy rather than a single global solve. The paper provides a limited extension-preserving result for the marginal-distribution objective in isolation, but it does not prove global completeness or global optimality for the full model once horizontal constraints, diversity, joint features, time limits, and irrevocable batch commitments are included. Our work targets the same Sum-based regime, but replaces exact feasibility by a probabilistic relaxation and optimizes a single global model over all constraints at once; it should therefore be viewed as complementary to these encodings rather than as a replacement for classical GCC propagation. 2.2 Contingency Tables, IPF, and Log-Linear Models Fitting contingency tables from marginal distributions has a long tradition in statistics, notably through iterative proportional fitting (IPF) and log-linear models ( 7 ; 2 ; 9 ) . When only first-order marginals are specified, IPF is known to converge to the unique maximum-entropy distribution consistent with these constraints, and can be viewed as a special case of maximum-likelihood estimation in log-linear models with main effects only ( 5 ; 6 ) . However, this