Lune

PLDI2024Top-tier venue

Bit Blasting Probabilistic Programs

Poorva Garg, Steven Holtzen, Guy Van den Broeck, Todd D. Millstein

Abstract

Probabilistic programming languages (PPLs) are an expressive means for creating and reasoning about probabilistic models. Unfortunately hybrid probabilistic programs that involve both continuous and discrete structures are not well supported by today's PPLs. In this paper we develop a new approximate inference algorithm for hybrid probabilistic programs that first discretizes the continuous distributions and then performs discrete inference on the resulting program. The key novelty is a form of discretization that we call bit blasting, which uses a binary representation of numbers such that a domain of 2 𝑏 discretized points can be succinctly represented as a discrete probabilistic program over poly(𝑏) Boolean random variables. Surprisingly, we prove that many common continuous distributions can be bit blasted in a manner that incurs no loss of accuracy over an explicit discretization and supports efficient probabilistic inference. We have built a probabilistic programming system for hybrid programs called HyBit, which employs bit blasting followed by discrete probabilistic inference. We empirically demonstrate the benefits of our approach over existing sampling-based and symbolic inference approaches

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

8 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Scaling exact inference for discrete probabilistic programs cites Automatic Reparameterisation of Probabilistic Programs
  • Roulette: A Language for Expressive, Exact, and Efficient Discrete Probabilistic Programming cites Scaling exact inference for discrete probabilistic programs
  • Roulette: A Language for Expressive, Exact, and Efficient Discrete Probabilistic Programming cites SPPL: probabilistic programming with fast exact symbolic inference
  • Foundations for Deductive Verification of Continuous Probabilistic Programs: From Lebesgue to Riemann and Back cites SPPL: probabilistic programming with fast exact symbolic inference
  • Foundations for Deductive Verification of Continuous Probabilistic Programs: From Lebesgue to Riemann and Back cites Guaranteed bounds for posterior inference in universal probabilistic programming
  • Random Variate Generation with Formal Guarantees cites SPPL: probabilistic programming with fast exact symbolic inference
  • A Domain-Specific Probabilistic Programming Language for Reasoning about Reasoning (Or: A Memo on memo) cites Scaling exact inference for discrete probabilistic programs
  • A Domain-Specific Probabilistic Programming Language for Reasoning about Reasoning (Or: A Memo on memo) cites SPPL: probabilistic programming with fast exact symbolic inference
  • Tuning Random Generators: Property-Based Testing as Probabilistic Programming cites Scaling exact inference for discrete probabilistic programs
  • Guaranteed bounds for posterior inference in universal probabilistic programming cites Automatic Reparameterisation of Probabilistic Programs
  • Guaranteed bounds for posterior inference in universal probabilistic programming cites Scaling exact inference for discrete probabilistic programs
  • Guaranteed bounds for posterior inference in universal probabilistic programming cites SPPL: probabilistic programming with fast exact symbolic inference
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers8

  1. Roulette: A Language for Expressive, Exact, and Efficient Discrete Probabilistic ProgrammingCameron Moy, Jack Czenszak, John M. Li, Brianna Marshall et al.PLDI 2025 · 3 citations
  2. Foundations for Deductive Verification of Continuous Probabilistic Programs: From Lebesgue to Riemann and BackKevin Batz, Joost-Pieter Katoen, Francesca Randone, Tobias WinklerOOPSLA 2025 · 2 citations
  3. A Domain-Specific Probabilistic Programming Language for Reasoning about Reasoning (Or: A Memo on memo)Kartik Chandra, Tony Chen, Joshua B. Tenenbaum, Jonathan Ragan-KelleyOOPSLA 2025 · 2 citations
  4. Tuning Random Generators: Property-Based Testing as Probabilistic ProgrammingRyan Tjoa, Poorva Garg, Harrison Goldstein, Todd D. Millstein et al.OOPSLA 2025 · 2 citations
  5. Random Variate Generation with Formal GuaranteesFeras A. Saad, Wonyeol LeePLDI 2025

Builds on5

  1. Scaling exact inference for discrete probabilistic programsSteven Holtzen, Guy Van den Broeck, Todd D. MillsteinOOPSLA 2020 · 85 citations
  2. SPPL: probabilistic programming with fast exact symbolic inferenceFeras A. Saad, Martin C. Rinard, Vikash K. MansinghkaPLDI 2021 · 38 citations
  3. Automatic Reparameterisation of Probabilistic ProgramsMaria I. Gorinova, Dave Moore, Matthew D. HoffmanICML 2020 · 33 citations
  4. Guaranteed bounds for posterior inference in universal probabilistic programmingRaven Beutner, C.-H. Luke Ong, Fabian ZaiserPLDI 2022 · 18 citations
  5. Deterministic stream-sampling for probabilistic programming: semantics and verificationFredrik Dahlqvist, Alexandra Silva, William SmithLICS 2023 · 4 citations

Related papers

  1. Multi-Language Probabilistic ProgrammingSam Stites, John M. Li, Steven HoltzenOOPSLA 2025 · 2 citations
  2. noDice: Inference for Discrete Probabilistic Programs with Nondeterminism and ConditioningTobias Gürtler, Benjamin Lucien KaminskiOOPSLA 2026 · 1 citation
  3. λPSI: exact inference for higher-order probabilistic programsTimon Gehr, Samuel Steffen, Martin T. VechevPLDI 2020 · 29 citations
  4. Inference Plans for Hybrid Particle FilteringEllie Y. Cheng, Eric Atkinson, Guillaume Baudart, Louis Mandel et al.POPL 2025 · 2 citations
  5. Probabilistic Programming with Programmable Divide-Conquer-Combine Inference on Modern HardwareMarkus Böck, Jürgen CitoOOPSLA 2026 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines