Maximum Entropy Method Outpaces Classical Raking in High-Dimensional Synthetic Population Generation

Building a believable artificial society from nothing but a handful of statistics has long been one of the quiet workhorses of computational social science. Now a new study published in Frontiers in Artificial Intelligence proposes a mathematically elegant way to do it better at scale, and the results suggest that a classic tool of survey statistics may be reaching its limits. Researchers François Pachet of ImagineAllThePeople and Jean-Daniel Zucker of the Institut de Recherche pour le Développement and Sorbonne Université have introduced a maximum-entropy relaxation for generating synthetic populations, showing that it decisively outperforms the dominant method, generalized raking, once the number of attributes and the density of overlapping constraints grow large.

The problem the researchers tackle is deceptively simple to state. Analysts in epidemiology, transportation modeling, public policy, and marketing often need thousands or millions of individual agents, each described by categorical attributes such as age bracket, gender, region, or occupation. What they actually possess, however, are aggregate statistics: perhaps that 52 percent of a population is female, that 18 percent is both female and aged 35 to 44, or that 4 percent is female, aged 35 to 44, and living in a particular region. The task of synthetic population generation is to construct a full population of individuals whose frequencies match all of these published or estimated aggregates simultaneously, without ever seeing the underlying personal records.

Formally, each requirement is a cardinality constraint over a pattern of attribute values, and the collection of such constraints forms a system of linear equalities over an astronomically large contingency table. The authors show why brute force fails: the joint table for 28 categorical attributes would hold roughly 9 times 10 to the 15th power cells, and for 40 attributes about 2 times 10 to the 26th. Exact constraint solvers buckle under this burden. In their experiments with Google OR-Tools CP-SAT, the solver could prove optimality only for populations up to 30 individuals on a 12-variable problem, and on a 24-variable instance with 3,621 target cells it could not prove optimality even for a population of 10, failing entirely to find feasible solutions at populations of 200 or more within the allotted time. The problem is also NP-hard in general, and the constraints overlap so heavily that even tiny inconsistencies in the targets can render the whole system infeasible.

The researchers’ answer is to stop demanding exact satisfaction. Instead of searching for a discrete population that hits every count precisely, they infer a probability distribution over complete attribute assignments whose expected frequencies match the required ones. By the maximum-entropy principle, famously articulated by Edwin Jaynes in 1957, they select among all distributions consistent with the constraints the one that makes the fewest additional assumptions. Classical duality theory then guarantees that this distribution takes an exponential-family form with one Lagrange multiplier per constraint, and the search for it becomes a convex optimization problem rather than a combinatorial nightmare. When targets are noisy or mutually inconsistent, the authors extend the framework with a penalized formulation whose ridge-regularized dual is strictly convex and always possesses a unique finite minimizer, whether or not the targets are jointly achievable.

Of course, a convex program is only as useful as one’s ability to solve it, and the partition function of the exponential family cannot be computed in closed form for populations of realistic size. The practical contribution is a fixed-budget Markov chain Monte Carlo moment-matching procedure. Starting from a uniformly random population, the sampler runs Metropolis-within-Gibbs sweeps in which individual attributes are proposed for change and accepted or rejected according to their effect on constraint violations. Between sweeps, the Lagrange multipliers are nudged by gradient steps that shrink the gap between observed and target frequencies. Crucially, the joint attribute space is never enumerated; the number of parameters equals the number of constrained cells, and the per-iteration cost grew only sublinearly with the number of constrained cells across the benchmark family, from 0.09 seconds at 158 cells to 1.34 seconds at 19,409 cells. The authors are careful to stress that every reported result measures this finite-budget approximation, not the exact mathematical optimum.

The evaluation rested on benchmarks derived from the 2024 National Public Opinion Reference Survey, a Pew Research Center dataset of 5,626 respondents, spanning problems with 4, 12, 20, 28, and 40 categorical attributes and constraints of up to ternary arity. The head-to-head comparison pitted the maximum-entropy approach against generalized raking, the iterative reweighting technique descended from Deming and Stephan’s iterative proportional fitting that has dominated population synthesis since the 1940s. The verdict was stark at high dimensionality. On the 40-variable benchmark with ternary constraints and a population of 5,626, MaxEnt achieved a mean relative constraint error of 0.095 against raking’s 0.352, a 73 percent relative improvement. At 28 variables, MaxEnt won every configuration tested, with gaps ranging from 33 to 59 percent. Below roughly 12 variables, the picture reversed or equalized: raking remained a strong, much faster baseline, and multi-seed analysis showed no reliable difference between the methods on the smallest ternary problems.

What explains the divergence? The authors offer a structural interpretation grounded in how the two algorithms operate. MaxEnt performs a single global update of all multipliers at once, finding one trade-off across every constraint simultaneously. Raking, by contrast, rescales weights constraint by constraint in sequence, so a correction applied to one marginal can partially undo earlier corrections on overlapping marginals. As the number of attributes grows, the number of overlapping constraints multiplies far faster than the population size, and this interference compounds. The authors demonstrated that raking’s residual error is not an artifact of stopping too early: extending raking from 500 to 2,000 iterations left its error essentially unchanged, while MaxEnt continued to improve monotonically with budget, plateauing around 400 iterations at 28 variables and still improving at 926 iterations at 40 variables.

The study is notable for its candor about what maximum entropy cannot do. In an ablation on the 20-variable benchmark, when only unary constraints were supplied, MaxEnt and raking were statistically indistinguishable on held-out ternary and four-way marginals that neither method had seen during fitting. Neither method can recover information absent from the constraints. The MaxEnt advantage emerged only once overlapping binary and ternary constraints were added, where it reconciles many higher-order requirements into a single global fit that generalizes better to unseen marginals. A validity audit also revealed a subtle weakness: on pairs it was never constrained on, MaxEnt’s entropy-maximizing behavior produced more previously unobserved attribute combinations than raking, 13.3 percent versus 2.9 percent of records on the 40-variable benchmark, though overall it produced far fewer invalid pairs because raking’s poor fit scattered mass indiscriminately. The authors recommend encoding known impossibilities as zero-probability support for either method.

Robustness testing added further nuance. When the researchers deliberately corrupted targets with multiplicative noise or planted a contradiction in one unary margin, both methods degraded gracefully and exhibited a striking denoising property, producing populations closer to the true targets than to the corrupted ones they were fitted on. At the moderate 12-variable scale, raking actually absorbed a localized contradiction slightly better, because its sequential updates let the many consistent higher-order margins override the single corrupted one. To rule out dataset-specific effects, the team also built an independent synthetic benchmark family with known ground truth, including regimes with latent block structure and structural zeros. The pattern transferred: in the dependent regimes MaxEnt’s error stayed essentially flat as dimensionality grew while raking’s degraded sharply, with raking producing forbidden attribute pairs in nearly 35 percent of records at 40 variables against MaxEnt’s 5.2 percent.

The practical implications reach well beyond the benchmark suite. Synthetic populations underpin microsimulation of disease spread, evaluation of policy reforms, agent-based models of markets, and privacy-preserving data release, and recent interest in large language model persona generators has broadened the field further. The authors position their method as an extension of the classical IPF and raking family into the regime of selectively specified, overlapping, high-arity constraints, complementary to deep generative models that require individual-level microdata rather than aggregates. Their empirical guidance is refreshingly specific: raking remains preferable for small, low-arity problems where speed matters, the choice becomes regime-dependent around 20 variables, and from 28 variables upward the maximum-entropy relaxation consistently delivered the most faithful populations on every configuration tested. As societies demand ever richer and more detailed statistical portraits without ever exposing the individuals behind them, the mathematics of making the fewest assumptions may prove the surest guide.

Subject of Research: Maximum-entropy relaxation of multi-way cardinality constraints for synthetic population generation

Article Title: Maximum entropy relaxation of multi-way cardinality constraints for synthetic population generation

Article References: Pachet, F., & Zucker, J.-D. (2026). Maximum entropy relaxation of multi-way cardinality constraints for synthetic population generation. Frontiers in Artificial Intelligence, 9, Article 1840945. https://doi.org/10.3389/frai.2026.1840945

Image Credits: AI Generated

DOI: 10.3389/frai.2026.1840945

Keywords: synthetic populations, maximum entropy, cardinality constraints, convex optimization, MCMC, generalized raking, iterative proportional fitting, microsimulation, agent-based modeling, constraint programming, exponential family, NPORS