arxiv: 2605.04629 · v1 · submitted 2026-05-06 · 💻 cs.MS · math.CO

Recognition: unknown

CombOL: a Library for Practical Enumeration and Boltzmann Sampling of Combinatorial Classes

Casper Asbj{\o}rn Eriksen , Daniel Merkle

Authors on Pith no claims yet

Pith reviewed 2026-05-08 03:02 UTC · model grok-4.3

classification 💻 cs.MS math.CO

keywords Boltzmann samplingcombinatorial enumerationgenerating functionscombinatorial classesrejection samplingsoftware libraryPython interface

0 comments

The pith

The CombOL library lets users define combinatorial classes with a short string syntax and then automatically produces unbiased Boltzmann samplers along with counting sequences.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents CombOL, an open-source library that accepts definitions of combinatorial classes written in a compact string notation that can include parameters. From each definition the library derives the ordinary generating function and uses it to build both exact counting routines and Boltzmann samplers. The samplers support both exact-size and approximate-size regimes with automatic tuning of the parameter. A new early-rejection technique is included, and numerical precision is raised on the fly so that the produced samples obey the exact target distribution rather than a floating-point approximation. Through a Python interface the sampled objects can be transformed directly into application-specific structures such as graphs or molecular representations.

Core claim

CombOL supplies a concise syntax for declaring combinatorial classes, automatically computes the associated generating functions, and compiles Boltzmann samplers that incorporate an early-rejection rule together with dynamic increases in floating-point precision; the latter step removes the statistical bias that would otherwise arise from rounding errors during probability calculations.

What carries the argument

The early-rejection scheme for Boltzmann sampling paired with automatic, on-demand elevation of numerical precision to guarantee exact distributional correctness.

If this is right

Users obtain both enumeration sequences and ready-to-run samplers from a single class definition without manual equation setup.
The same class specification works for both exact-size and approximate-size sampling with built-in parameter adjustment.
Sampled structures are delivered as Python objects that can be mapped immediately to graphs, chemical formulas, or other domain data types.
Statistical correctness is maintained even when internal probability calculations would otherwise suffer from accumulated rounding error.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The separation of class syntax from sampler implementation could allow the same definitions to drive sampling routines written in other languages.
Dynamic precision adjustment might be reusable in other rejection-based Monte Carlo procedures that rely on floating-point probabilities.
Integration with existing Python ecosystems for data analysis could let researchers generate large synthetic data sets whose combinatorial properties are exactly controlled.

Load-bearing premise

A broad enough collection of combinatorial classes can be expressed in the concise string syntax and the automatic derivation of generating functions and samplers stays both correct and efficient for those classes.

What would settle it

A concrete test that draws many samples from a known class such as binary trees, compares the empirical size distribution against the exact coefficients of the generating function, and detects a statistically significant deviation.

Figures

Figures reproduced from arXiv: 2605.04629 by Casper Asbj{\o}rn Eriksen, Daniel Merkle.

**Figure 1.** Figure 1: Five molecular structures, generated by CombOL using the script included in Appendix A. btrees . sample ( n = 1000 , target_size : {’z’: 1000} , tolerance = 0.05 ) 2.2 Integration In addition to generating native symbolic structures, CombOL allows integration of this sampling procedure into other workflows. By defining the atoms and how operators such as Product and Sequence act, the user can then use Com… view at source ↗

**Figure 2.** Figure 2: Illustration of the true cumulative probabilities, view at source ↗

read the original abstract

We present CombOL (Combinatorial Objects Library), an open-source library for the enumeration and Boltzmann sampling of combinatorial classes. Classes can be specified by a concise string syntax, and may depend on an arbitrary number of parameters. CombOL automatically derives the associated generating functions, enabling the generation of counting sequences and the compilation of Boltzmann samplers. The library supports exact and approximate-size Boltzmann rejection sampling with automatic parameter tuning to target specific sizes. In addition to implementing established methods, CombOL contributes a novel early-rejection scheme, as well as guaranteed statistical correctness by dynamically increasing the numerical precision, eliminating bias due to floating-point rounding errors. Through the Python interface, sampled structures can be mapped to application-specific objects, enabling direct sampling of domain objects such as graphs, chemical structure representations, or other complex data types. CombOL is available from PyPI as 'combol' (pypi.org/project/combol). The source code is available at gitlab.com/casbjorn/combol.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

CombOL is a usable Python library for Boltzmann sampling that adds an early-rejection method and dynamic precision to cut floating-point bias.

read the letter

The core of this paper is a new open-source library called CombOL that lets users write combinatorial classes in a short string syntax, then automatically builds the generating functions and Boltzmann samplers. It supports both exact and approximate-size sampling with built-in parameter tuning, and the Python layer lets you turn the samples into graphs, molecules, or whatever domain objects you need. The code is on GitLab and installable from PyPI, which is straightforward for anyone who wants to try it or inspect it.

Referee Report

1 major / 2 minor

Summary. The paper presents CombOL, an open-source library for enumeration and Boltzmann sampling of combinatorial classes. Classes are defined via a concise string syntax supporting an arbitrary number of parameters; the library automatically derives the associated generating functions to produce counting sequences and to compile Boltzmann samplers. It implements both exact and approximate-size rejection sampling with automatic parameter tuning, introduces a novel early-rejection scheme, and guarantees statistical correctness through dynamic increases in numerical precision that eliminate floating-point rounding bias. Sampled structures can be mapped to domain-specific objects via the Python interface.

Significance. If the implementation and correctness claims hold, CombOL would provide a practical, accessible tool for the combinatorial enumeration community, lowering the barrier to generating structures from parameterized classes and supporting direct use in applications such as graph generation or chemical modeling. The open-source release, Python integration, and focus on eliminating sampling bias are concrete strengths that could improve reproducibility and usability over prior ad-hoc implementations of Boltzmann sampling.

major comments (1)

[Abstract] Abstract and the section on the dynamic-precision mechanism: the central claim that statistical correctness is 'guaranteed' by dynamically increasing precision rests on unexamined software behavior; without explicit validation experiments, error bounds, or a worked example showing bias elimination for a non-trivial class, the claim cannot be verified from the manuscript alone.

minor comments (2)

The manuscript should supply at least one fully worked example of the string syntax, the derived generating function, and the resulting sampler output to illustrate the claimed conciseness and correctness.
Add a short limitations paragraph discussing the range of classes for which the automatic derivation remains efficient and the early-rejection scheme yields practical speed-ups.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their constructive report and positive assessment of CombOL's potential utility. We address the single major comment below and will incorporate the requested material in the revised manuscript.

read point-by-point responses

Referee: [Abstract] Abstract and the section on the dynamic-precision mechanism: the central claim that statistical correctness is 'guaranteed' by dynamically increasing precision rests on unexamined software behavior; without explicit validation experiments, error bounds, or a worked example showing bias elimination for a non-trivial class, the claim cannot be verified from the manuscript alone.

Authors: We agree that the current manuscript does not contain explicit validation experiments, error bounds, or a worked example to support the claim of guaranteed statistical correctness. The dynamic-precision scheme increases floating-point mantissa length until the computed rejection probabilities are accurate to a user-specified tolerance, thereby eliminating rounding bias in the sampling procedure. While this approach follows from standard techniques for simulating exact arithmetic, we acknowledge the absence of empirical verification in the submitted version. In the revision we will add a new subsection (and update the abstract) that provides: (1) a worked example on a non-trivial parameterized class such as plane trees with two integer parameters, (2) direct comparison of empirical sample frequencies against exact counting sequences obtained via the library's enumeration routines, and (3) reported bounds on the precision increments needed to keep bias below a chosen threshold. These additions will make the correctness claim verifiable from the text. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents CombOL as a library implementing known algorithms for generating functions, enumeration, and Boltzmann sampling of combinatorial classes specified via string syntax, plus one novel early-rejection scheme and a dynamic-precision bias-elimination mechanism. No load-bearing derivations, predictions, or uniqueness claims reduce by construction to fitted inputs, self-citations, or ansatzes within the paper itself. The central contributions are implementation details and correctness guarantees that are externally verifiable via the released code, with no internal reduction of the claimed results to their own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The described work is a software implementation that relies on standard combinatorial generating-function techniques and Boltzmann sampling methods from the existing literature; no new free parameters, axioms, or invented entities are introduced.

pith-pipeline@v0.9.0 · 5472 in / 1101 out tokens · 84834 ms · 2026-05-08T03:02:11.198223+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references · 9 canonical work pages

[1]

Bendkowski, M.: Automatic compile-time synthesis of entropy-optimal boltzmann samplers (2022),https://arxiv.org/abs/2206.06668

work page arXiv 2022
[2]

Combinatorics, Probability and Computing31(5), 765–811 (Sep 2022)

Bendkowski, M., Bodini, O., Dovgal, S.: Tuning as convex optimisa- tion: a polynomial tuner for multi-parametric combinatorial samplers. Combinatorics, Probability and Computing31(5), 765–811 (Sep 2022). https://doi.org/10.1017/S0963548321000547

work page doi:10.1017/s0963548321000547 2022
[3]

In: 15th International Symposium on Soft- ware Reliability Engineering

Denise, A., Gaudel, M.C., Gouraud, S.D.: A generic method for statistical testing. In: 15th International Symposium on Soft- ware Reliability Engineering. p. 25–34. IEEE, Saint-Malo, Bre- tagne, France (2004). https://doi.org/10.1109/ISSRE.2004.2,http:// ieeexplore.ieee.org/document/1383103/

work page doi:10.1109/issre.2004.2 2004
[4]

Denise, A., Dutour, I., Zimmermann, P.: Cs: a mupad package for counting and randomly generating combinatorial structures (Apr 1998), software demonstration, FPSAC’98

1998
[5]

On the mammalian acetone metabolism: from chemistry to clinical impli- cations

Denise, A., Zimmermann, P.: Uniform random generation of decom- posable structures using floating-point arithmetic. Theoretical Computer 7 Science218(2), 233–248 (May 1999). https://doi.org/10.1016/S0304- 3975(98)00323-5

work page doi:10.1016/s0304- 1999
[6]

In: Proceedings of the 2011 Winter Sim- ulation Conference (WSC)

Duchon, P.: Random generation of combinatorial structures: Boltz- mann samplers and beyond. In: Proceedings of the 2011 Winter Sim- ulation Conference (WSC). p. 120–132. IEEE, Phoenix, AZ, USA (Dec 2011). https://doi.org/10.1109/WSC.2011.6147745,http://ieeexplore. ieee.org/document/6147745/

work page doi:10.1109/wsc.2011.6147745 2011
[7]

Com- binatorics, Probability and Computing13(4–5), 577–625 (Jul 2004)

Duchon, P., Flajolet, P., Louchard, G., Schaeffer, G.: Boltzmann samplers for the random generation of combinatorial structures. Com- binatorics, Probability and Computing13(4–5), 577–625 (Jul 2004). https://doi.org/10.1017/S0963548304006315

work page doi:10.1017/s0963548304006315 2004
[8]

Cambridge University Press, Cambridge, England (Jan 2009)

Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge, England (Jan 2009)

2009
[9]

SIAM Journal on Computing29(3), 834–853 (Jan 2000)

Goldberg, L.A., Jerrum, M.: Randomly sampling molecules. SIAM Journal on Computing29(3), 834–853 (Jan 2000). https://doi.org/10.1137/S0097539797318864

work page doi:10.1137/s0097539797318864 2000
[10]

Discrete Mathematics & Theoreti- cal Computer ScienceAI(Proceedings), 475–488 (Jan 2008)

Pivoteau, C., Salvy, B., Soria, M.: Boltzmann oracle for combinatorial systems. Discrete Mathematics & Theoreti- cal Computer ScienceAI(Proceedings), 475–488 (Jan 2008). https://doi.org/10.46298/dmtcs.3585

work page doi:10.46298/dmtcs.3585 2008
[11]

Journal of Combinatorial Theory, Series A119(8), 1711–1773 (Nov 2012)

Pivoteau, C., Salvy, B., Soria, M.: Algorithms for combinato- rial systems: Well-founded systems and newton iterations. Journal of Combinatorial Theory, Series A119(8), 1711–1773 (Nov 2012). https://doi.org/10.1016/j.jcta.2012.05.007, arXiv:1109.2688 [math]

work page doi:10.1016/j.jcta.2012.05.007 2012
[12]

Zimmermann, P.: Gaïa: a package for the random generation of combina- torial structures. MapleTech1(1), 38–46 (1994) 8 Appendices A Example The following listing defines a combinatorial class, then defines a builder rep- resenting the combinatorial bijection between the class and the class of acyclic hydrocarbons. The output of this code can be seen in Fi...

1994