Verifying Exact Samplers for Continuous Distributions with a Discrete Program Logic
Pith reviewed 2026-05-19 13:57 UTC · model grok-4.3
pith:SEQTVGXR Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{SEQTVGXR}
Prints a linked pith:SEQTVGXR badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
The pith
A higher-order separation logic verifies exact samplers for continuous distributions using computable reals.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Continuous-Eris is a higher-order separation logic for verifying the correctness of exact sampling algorithms for computable distributions. Using Continuous-Eris, the authors establish the correctness of computable samplers for the uniform, Gaussian, and Laplace distributions, as well as a library for exact real arithmetic for working with generated samples.
What carries the argument
Continuous-Eris, a higher-order separation logic that reasons about programs containing probabilistic choice, higher-order functions, and dynamically allocated mutable state to establish exact sampling properties for continuous distributions.
If this is right
- The verified uniform, Gaussian, and Laplace samplers produce samples distributed exactly according to their target continuous distributions.
- The exact real arithmetic library correctly supports operations on samples generated to arbitrary precision.
- The logic accounts for the full combination of probabilistic choice with higher-order functions and mutable state in these algorithms.
- Verification guarantees absence of approximation errors in the sampling process.
Where Pith is reading between the lines
- The same logic could be used to verify samplers for additional continuous distributions not covered in the paper.
- Verified exact samplers could strengthen security arguments in differential privacy mechanisms that add continuous noise.
- Separation logic techniques shown here might extend to verification of other probabilistic programs that mix discrete and continuous elements.
Load-bearing premise
The soundness of Continuous-Eris holds with respect to the operational semantics of the underlying language that includes probabilistic choice, higher-order functions, and dynamically allocated mutable state.
What would settle it
A concrete execution trace or statistical test showing that one of the verified sampler programs produces samples whose distribution deviates from the target uniform, Gaussian, or Laplace distribution.
Figures
read the original abstract
Most implementations of sampling algorithms for continuous distributions use floating-point numbers, which introduce round-off errors and approximations. These errors can be difficult to analyze, and can cause security issues when used in algorithms for differential privacy. An alternative is to use exact sampling algorithms based on computable reals, which can lazily generate the digits of a continuous sample to arbitrary precision. However, these algorithms are intricate, and implementing and using them involves a combination of semantically challenging language features, such as probabilistic choice, higher-order functions, and dynamically-allocated mutable state. In this paper we present Continuous-Eris, a higher-order separation logic for verifying the correctness of exact sampling algorithms for computable distributions. To demonstrate Continuous-Eris, we verify the correctness of computable samplers for the uniform, Gaussian, and Laplace distributions, as well as a library for exact real arithmetic for working with generated samples. All of the results in this paper have been verified in the Rocq proof assistant.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces Continuous-Eris, a higher-order separation logic for verifying exact sampling algorithms for computable continuous distributions. It demonstrates the logic by machine-checking in Rocq the correctness of samplers for the uniform, Gaussian, and Laplace distributions together with a library for exact real arithmetic, all in a language featuring probabilistic choice, higher-order functions, and mutable state.
Significance. If the soundness result holds, the work supplies a verified foundation for exact real sampling that avoids floating-point approximation errors, directly relevant to differential privacy and other security-critical uses. The machine-checked proofs in Rocq constitute a clear strength, as they discharge the central soundness claim against the operational semantics rather than leaving it as an unverified assumption.
minor comments (2)
- [§2] §2: the notation for the probabilistic choice operator is introduced twice with slightly different symbols; adopt a single consistent notation.
- The caption of Figure 3 could explicitly state the number of digits generated in the displayed sample to aid readers unfamiliar with exact reals.
Simulated Author's Rebuttal
We thank the referee for their positive assessment of the paper and their recommendation to accept. We are pleased that the referee recognizes the value of the machine-checked soundness proofs in Rocq and the relevance to applications such as differential privacy.
Circularity Check
No significant circularity
full rationale
The paper introduces Continuous-Eris, a higher-order separation logic, and uses it to verify samplers for uniform, Gaussian, and Laplace distributions plus an exact-real library. All claims, including the logic's soundness relative to the operational semantics of a language with probabilistic choice, higher-order functions, and mutable state, are discharged by machine-checked proofs in Rocq. No derivation step reduces to a fitted parameter, self-referential definition, or load-bearing self-citation; the formal artifact provides independent verification against external semantics rather than constructing results by construction from the inputs.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The operational semantics of the language featuring probabilistic choice, higher-order functions, and mutable state is correctly modeled by the logic.
invented entities (1)
-
Continuous-Eris logic
no independent evidence
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We present Continuous-Eris, a higher-order separation logic for verifying the correctness of exact sampling algorithms for computable distributions... using error credits and time receipts
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Theorem 3 (Partial Adequacy of Constructive Real Samplers) ... density function h ∈ PC(R)
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
Aguirre, Alejandro and Haselwarter, Philipp G. and de Medeiros, Markus and Li, Kwing Hei and Gregersen, Simon Oddershede and Tassarotti, Joseph and Birkedal, Lars , title =. Proc. ACM Program. Lang. , month = aug, articleno = 246, numpages = 33, keywords =. doi:10.1145/3674635 , abstract =
-
[2]
Proceedings of the 2012 ACM conference on Computer and communications security , pages=
On significance of the least significant bits for differential privacy , author=. Proceedings of the 2012 ACM conference on Computer and communications security , pages=
work page 2012
-
[3]
A categorical approach to probability theory
Giry, Mich \`e le. A categorical approach to probability theory. Categorical Aspects of Topology and Analysis. 1982
work page 1982
-
[4]
John von Neumann, Collected Works , volume=
Various techniques used in connection with random digits , author=. John von Neumann, Collected Works , volume=. 1963 , publisher=
work page 1963
-
[5]
J. von Neumann , year =. Various techniques used in connection with random digits , booktitle =
-
[6]
Haselwarter and Joseph Tassarotti and Lars Birkedal , title =
Simon Oddershede Gregersen and Alejandro Aguirre and Philipp G. Haselwarter and Joseph Tassarotti and Lars Birkedal , title =. Proc. doi:10.1145/3632868 , url =
-
[7]
Karney, Charles F. F. , title =. ACM Trans. Math. Softw. , month = jan, articleno =. 2016 , issue_date =. doi:10.1145/2710016 , abstract =
-
[8]
Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science , articleno =
Fernandes, Natasha and McIver, Annabelle and Morgan, Carroll , title =. Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science , articleno =. 2021 , isbn =. doi:10.1109/LICS52264.2021.9470718 , abstract =
-
[9]
Proceedings of the 2012 ACM Conference on Computer and Communications Security , pages =
Mironov, Ilya , title =. Proceedings of the 2012 ACM Conference on Computer and Communications Security , pages =. 2012 , isbn =. doi:10.1145/2382196.2382264 , abstract =
-
[10]
Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing , pages =
Ghosh, Arpita and Roughgarden, Tim and Sundararajan, Mukund , title =. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing , pages =. 2009 , isbn =. doi:10.1145/1536414.1536464 , abstract =
-
[11]
Barthe, Gilles and Gaboardi, Marco and Grégoire, Benjamin and Hsu, Justin and Strub, Pierre-Yves , year = 2016, publisher =. A. doi:10.4230/LIPIcs.ICALP.2016.107 , booktitle =
-
[12]
Dwork, Cynthia and Roth, Aaron , title =. Found. Trends Theor. Comput. Sci. , month = aug, pages =. 2014 , issue_date =. doi:10.1561/0400000042 , abstract =
- [13]
-
[14]
A multiple-precision binary floating-point library with correct rounding, version 3.2.0 , url =
MPFR , year =. A multiple-precision binary floating-point library with correct rounding, version 3.2.0 , url =
-
[15]
Ralf Jung and Robbert Krebbers and Jacques. Iris from the ground up:. J. Funct. Program. , volume = 28, pages =. doi:10.1017/S0956796818000151 , timestamp =
-
[16]
doi:10.5281/zenodo.11551307 , url =
The Rocq Development Team , title =. doi:10.5281/zenodo.11551307 , url =
-
[17]
Sylvie Boldo and Catherine Lelay and Guillaume Melquiond , title =. Math. Comput. Sci. , volume =. 2015 , doi =
work page 2015
-
[18]
Verified Foundations for Differential Privacy , year =
de Medeiros, Markus and Naveed, Muhammad and Lepoint, Tancr\`. Verified Foundations for Differential Privacy , year =. Proc. ACM Program. Lang. , month = jun, articleno =. doi:10.1145/3729294 , abstract =
-
[19]
Swaraj Dash and Younesse Kaddar and Hugo Paquet and Sam Staton , title =. Proc. 2023 , url =. doi:10.1145/3571239 , timestamp =
- [20]
-
[21]
Partially-Sampled Random Numbers for Accurate Sampling of Continuous Distributions , author=
-
[22]
CReal Library , author=
- [23]
-
[24]
Alexander Bagnall and Gordon Stewart and Anindya Banerjee , title =. Proc. 2023 , url =. doi:10.1145/3591220 , timestamp =
-
[25]
Li and Amal Ahmed and Steven Holtzen , title =
John M. Li and Amal Ahmed and Steven Holtzen , title =. Proc. 2023 , url =
work page 2023
-
[26]
Ho, Shing Hin and Wu, Nicolas and Raad, Azalea , title =. Proc. ACM Program. Lang. , month = jan, articleno =. 2026 , issue_date =. doi:10.1145/3776696 , abstract =
-
[27]
Approximate Relational Hoare Logic for Continuous Random Samplings , booktitle =
Tetsuya Sato , editor =. Approximate Relational Hoare Logic for Continuous Random Samplings , booktitle =
-
[28]
Program Logic for Higher-Order Probabilistic Programs in Isabelle/HOL , booktitle =
Michikazu Hirata and Yasuhiko Minamide and Tetsuya Sato , editor =. Program Logic for Higher-Order Probabilistic Programs in Isabelle/HOL , booktitle =. 2022 , url =. doi:10.1007/978-3-030-99461-7\_4 , timestamp =
-
[29]
Tetsuya Sato and Alejandro Aguirre and Gilles Barthe and Marco Gaboardi and Deepak Garg and Justin Hsu , title =. Proc. 2019 , url =. doi:10.1145/3290351 , timestamp =
-
[30]
Kevin Batz and Joost. Foundations for Deductive Verification of Continuous Probabilistic Programs: From Lebesgue to Riemann and Back , journal =. 2025 , url =. doi:10.1145/3720429 , timestamp =
-
[31]
Guaranteed bounds for posterior inference in universal probabilistic programming , booktitle =
Raven Beutner and C. Guaranteed bounds for posterior inference in universal probabilistic programming , booktitle =. 2022 , url =. doi:10.1145/3519939.3523721 , timestamp =
-
[32]
Poorva Garg and Steven Holtzen and Guy Van den Broeck and Todd D. Millstein , title =. Proc. 2024 , url =. doi:10.1145/3656412 , timestamp =
-
[33]
Chris Heunen and Ohad Kammar and Sam Staton and Hongseok Yang , title =. 32nd Annual. 2017 , url =. doi:10.1109/LICS.2017.8005137 , timestamp =
-
[34]
Thomas Ehrhard and Michele Pagani and Christine Tasson , title =. Proc. 2018 , url =. doi:10.1145/3158147 , timestamp =
-
[35]
Fredrik Dahlqvist and Dexter Kozen , title =. Proc. 2020 , url =. doi:10.1145/3371125 , timestamp =
-
[36]
A domain theory for statistical probabilistic programming , journal =
Matthijs V. A domain theory for statistical probabilistic programming , journal =. 2019 , url =. doi:10.1145/3290349 , timestamp =
-
[37]
Mathieu Huot and Alexander K. Lew and Vikash K. Mansinghka and Sam Staton , title =. 38th Annual. 2023 , url =. doi:10.1109/LICS56636.2023.10175739 , timestamp =
-
[38]
A lambda-calculus foundation for universal probabilistic programming , booktitle =
Johannes Borgstr. A lambda-calculus foundation for universal probabilistic programming , booktitle =. 2016 , url =. doi:10.1145/2951913.2951942 , timestamp =
-
[39]
Mitchell Wand and Ryan Culpepper and Theophilos Giannakopoulos and Andrew Cobb , title =. Proc. 2018 , url =. doi:10.1145/3236782 , timestamp =
-
[40]
Daniel Huang and Greg Morrisett , editor =. An Application of Computable Distributions to the Semantics of Probabilistic Programming Languages , booktitle =. 2016 , url =. doi:10.1007/978-3-662-49498-1\_14 , timestamp =
-
[41]
Cameron E. Freer and Daniel M. Roy , title =. Ann. Pure Appl. Log. , volume =. 2012 , doi =
work page 2012
-
[42]
Nathanael L. Ackerman and Cameron E. Freer and Daniel M. Roy , title =. J. 2019 , url =. doi:10.1145/3321699 , timestamp =
-
[43]
Computability of probability measures and Martin-Löf randomness over metric spaces , journal =
Mathieu Hoyrup and Cristóbal Rojas , keywords =. Computability of probability measures and Martin-Löf randomness over metric spaces , journal =. 2009 , issn =. doi:https://doi.org/10.1016/j.ic.2008.12.009 , url =
-
[44]
Abbas Edalat , title =. Inf. Comput. , volume =. 2009 , doi =
work page 2009
-
[45]
Paul Bilokon and Abbas Edalat , editor =. A domain-theoretic approach to Brownian motion and general continuous stochastic processes , booktitle =. 2014 , url =. doi:10.1145/2603088.2603102 , timestamp =
-
[46]
Marionneau, Virgil and Sassus Bourda, F\'. Modular Specifications and Implementations of Random Samplers in Higher-Order Separation Logic , year =. Proceedings of the 15th ACM SIGPLAN International Conference on Certified Programs and Proofs , pages =. doi:10.1145/3779031.3779109 , abstract =
-
[47]
Vernon A. Lee Jr. and Hans. Optimizing Programs over the Constructive Reals , booktitle =. 1990 , url =. doi:10.1145/93542.93558 , timestamp =
-
[48]
Hans. Towards an. Proceedings of the 41st. 2020 , url =. doi:10.1145/3385412.3386037 , timestamp =
-
[49]
Norbert Th. M. The. Computability and Complexity in Analysis, 4th International Workshop,. 2000 , url =. doi:10.1007/3-540-45335-0\_14 , timestamp =
-
[50]
Implementing Real Numbers With
Andrej Bauer and Iztok Kavkler , editor =. Implementing Real Numbers With. Proceedings of the Fourth International Conference on Computability and Complexity in Analysis,. 2007 , doi =
work page 2007
-
[51]
Semantics of Exact Real Arithmetic , booktitle =
Peter John Potts and Abbas Edalat and Mart. Semantics of Exact Real Arithmetic , booktitle =. 1997 , url =. doi:10.1109/LICS.1997.614952 , timestamp =
-
[52]
Mart. Theor. Comput. Sci. , volume =. 1996 , url =. doi:10.1016/0304-3975(95)00250-2 , timestamp =
-
[53]
Pietro Di Gianantonio , title =. Inf. Comput. , volume =. 1996 , doi =
work page 1996
-
[54]
Alex K. Simpson , editor =. Lazy Functional Algorithms for Exact Real Functionals , booktitle =. 1998 , doi =
work page 1998
-
[55]
Jean Vuillemin , title =. 1990 , url =. doi:10.1109/12.57047 , timestamp =
-
[56]
and Tassarotti, Joseph and Birkedal, Lars , title =
Li, Kwing Hei and Aguirre, Alejandro and Gregersen, Simon Oddershede and Haselwarter, Philipp G. and Tassarotti, Joseph and Birkedal, Lars , title =. Proc. ACM Program. Lang. , month = aug, articleno =. 2025 , issue_date =. doi:10.1145/3747514 , abstract =
- [57]
-
[58]
Philipp G. Haselwarter and Kwing Hei Li and Alejandro Aguirre and Simon Oddershede Gregersen and Joseph Tassarotti and Lars Birkedal , title =. Proc. 2025 , url =. doi:10.1145/3704877 , timestamp =
-
[59]
Philipp G. Haselwarter and Kwing Hei Li and Markus de Medeiros and Simon Oddershede Gregersen and Alejandro Aguirre and Joseph Tassarotti and Lars Birkedal , title =. Proc. 2024 , url =. doi:10.1145/3689753 , timestamp =
-
[60]
Patrick Billingsley , title =
-
[61]
doi:10.5281/zenodo.20114732 , url =
de Medeiros, Markus and Liu, Puming and Li, Kwing Hei and Aguirre, Alejandro and Birkedal, Lars and Tassarotti, Joseph , title =. doi:10.5281/zenodo.20114732 , url =
-
[62]
Verifying Exact Samplers for Continuous Distributions with a Discrete Program Logic , author=. 2026 , eprint=
work page 2026
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.