{"id":"fe4a508c-d477-4a8f-a4fa-9cc3d141b785","arxiv_id":"2507.13494","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A new algorithm synthesizes entropy-optimal, exact random variate generators from finite-precision CDF specifications in any binary number format.","lead":"Software random number generators often rely on an idealized infinite-precision computer and silently produce wrong distributions on real hardware. This paper presents a method to automatically build exact samplers from any finite-precision CDF that consume the fewest possible random bits and need only ordinary integer arithmetic.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.17 is sound for CDFs satisfying Def. 5.10, but the flagship GSL examples violate that contract at the top element: for IEEE-754 formats phi_B(1^n) is NaN, and GSL CDFs return NaN, not 1.","rationale":"I read the paper in good faith: the core mathematical development is detailed, the reduction from finite-precision CDFs to binary-coded distributions (Props. 5.13-5.15) is coherent, and Theorem 5.17 appears to follow from the stated preconditions. The reader's weakest assumption was that the user's CDF must faithfully satisfy Definition 5.10; my concern is a concrete, load-bearing instance of that assumption failing for the paper's own advertised GSL interoperability. Definition 5.2 and Example 5.6 deliberately include a top element (NaN/⊥), and Definition 5.10 requires F of that top element to be 1, but GSL CDF functions are ordinary real-valued functions that return NaN on NaN input. Since Algorithm 2 hardcodes f1=1 and never calls F on the top string, an unmodified GSL CDF can cause the generated distribution to diverge from the user's F at the upper endpoint, or to emit NaN outputs with positive probability. This does not invalidate the conditional theorem, but it does mean the practical guarantee in Listing 2 requires an unstated wrapper. I would keep the reader's CONDITIONAL verdict: the paper should either make the wrapper explicit or qualify the claim that off-the-shelf GSL CDFs satisfy the formal contract.","tokens_in":65002,"tokens_out":17480,"duration_ms":165840,"concrete_test":"From the reproduction package, evaluate gsl_cdf_gaussian_P(NaN, sigma) and gsl_cdf_gaussian_Q(NaN, sigma). If either returns NaN (as standard math functions do), then inspect the GENERATE_FROM_CDF macro in librvg to see whether it inserts a wrapper that maps the top bit string to 1 before calling the user CDF. Then run Algorithm 2 on a small IEEE-style format B that includes a NaN top element, comparing (i) the unmodified GSL function and (ii) the same function wrapped as W(x)=isnan(x)?1:F(x). If the unmodified run produces NaN outputs or a distribution inconsistent with F, while the wrapped run terminates correctly and matches the wrapped CDF, the GSL interop claim requires the wrapper that the paper currently omits.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 5.17 is conditional on Def. 5.10, which requires F(phi_B(1^n))=1. For an IEEE-754 format B=F_E^m, Example 5.6 maps the maximal bit string 1^n to the NaN pattern (extended real top element, per Def. 5.1). Standard CDF implementations used in the paper's headline examples, such as gsl_cdf_gaussian_P, propagate NaN and return NaN, not 1. Algorithm 2 hardcodes the upper probability as f1=1 (initial parameter) and never evaluates F at 1^n, so it can allocate the top interval 1-F(pred_B(1^n)) to outputs whose 'cumulative probability' under the user-supplied F is NaN. The theorem then does not apply to the exact API advertised in Listing 2 unless the user wraps F to clamp the top element to 1 (and similarly wraps S so that S(phi_B(1^n))=0). The paper does not state or implement such a wrapper, so the practical claim that existing GSL CDFs can be used directly is unsupported as written. This is not a flaw in the proof for CDFs satisfying Def. 5.10, but it is the most load-bearing gap between the formal theorem and the advertised usage.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a finite-precision approach to random variate generation. The user supplies a cumulative distribution function (CDF) implemented as a program over a binary number format; the method automatically synthesizes a generator that is exact for that finite-precision CDF and consumes the information-theoretically minimal expected number of random bits. The theoretical core is a lazy, space-time optimal extension of Knuth-Yao discrete distribution generating trees (Algorithm 1, Theorem 4.6), specialized to finite-precision CDFs via an exact bit-extraction procedure using only fixed-width integer arithmetic (Algorithms 2-4, Theorems 5.16-5.18). A further extension combines a CDF and a survival function into a dual distribution function for wider tail coverage (Section 6, Theorem 6.3). The paper also reports a C implementation and an empirical comparison against the GNU Scientific Library. The central theorem is supported by detailed proofs in the appendices.","tokens_in":65232,"tokens_out":6030,"duration_ms":73386,"significance":"If the central theorem holds, this is a significant advance: it replaces ad-hoc, Real-RAM-based samplers with automatically synthesized generators that are exact for a formally specified finite-precision distribution, entropy-optimal in the Knuth-Yao sense, and implemented with fixed-width integer arithmetic only. The paper provides detailed proofs for the bit-extraction correctness (Theorem 5.16) and the entropy-optimality of the finite-precision algorithm (Theorem 5.17), and it ships a C library and reproduction package. The extension to dual distribution functions is well motivated and also proved (Theorem 6.3). The main caveat is that the advertised reuse of existing GSL CDFs in the paper's examples is, as written, outside the formal contract of Definition 5.10, which requires a wrapper or explicit user guidance; this does not invalidate the theorem but does affect the practical claims.","major_comments":[{"comment":"Theorem 5.17 is conditional on Definition 5.10, which requires F(phi_B(1^n)) = 1. For IEEE-754 formats, Example 5.6 maps the maximal bit string 1^n to the NaN pattern (the extended-real top element of Definition 5.1), not to +infinity. Standard implementations such as gsl_cdf_gaussian_P return NaN for a NaN input, so they do not satisfy the condition F(phi_B(1^n)) = 1. Algorithm 2 sets the initial upper cumulative probability to f1 = 1 and never evaluates F at phi_B(1^n); it thereby assigns the top interval probability 1 - F(pred_B(1^n)) to an output whose claimed cumulative probability F(x) is, under the user-supplied GSL CDF, NaN rather than 1. Consequently, the direct usage advertised in Listing 2 (GENERATE_FROM_CDF(gsl_cdf_gaussian_P, 5.0)) does not meet the theorem's preconditions, and the paper's statement that existing GSL CDFs can be reused as-is is unsupported as written. This is not a flaw in the proof for compliant CDFs, but it is a load-bearing gap between the formal theorem and the advertised practical interface. The paper should explicitly state that user CDFs must satisfy Definition 5.10, provide a wrapper that clamps the NaN (top) input to 1 (and, for survival functions, clamps the top input to 0), or clearly restrict the direct-reuse claims to CDFs that already satisfy the contract.","section":"Section 5.2 / Listing 2 / Theorem 5.17"}],"minor_comments":[{"comment":"The abstract and Section 7 use the word 'accuracy' (e.g., 'delivering higher accuracy'), but the evaluation in Table 2 measures output range coverage, not a statistical accuracy metric such as total variation distance or a tail-precision measure. A wider output range does not by itself establish higher accuracy; please rephrase the claim as 'wider output range coverage' or add distributional-distance measurements.","section":"Abstract / Section 7"},{"comment":"The trace in Figure 5b and the tree explanation in Figure 5c are dense; the roles of gray, blue, yellow, and pink bits are explained in the caption, but the correspondence between the trace and the recursion levels would be easier to follow if the recursion levels were explicitly numbered in both the figure and the pseudocode.","section":"Figure 5 and Algorithm 1"},{"comment":"For a general binary-coded probability distribution (Definition 4.1), the while loop in Algorithm 1 terminates almost surely but not necessarily in bounded time unless the probabilities are dyadic rationals. The paper states this for Algorithm 2 in Section 5.3, but an explicit remark near Algorithm 1 would avoid confusion for readers who apply the algorithm to arbitrary real-valued binary-coded distributions.","section":"Section 4.2, Algorithm 1"},{"comment":"The text reports that GSL generators are 2.6x-142x more expensive in bits/variate than OPT, but for Pascal(1,5) the OPT value is 0.00 bits; the ratio is then undefined or infinite. Consider reporting this case separately or using a non-ratio statement for zero-entropy cases.","section":"Section 7.1, Table 1"}],"recommendation":"major_revision","confidential_remarks":"The paper's theoretical core is sound, but the practical claims in the abstract and Section 7 rely on an unstated normalization of the top element for IEEE-754 formats. This is fixable with a wrapper or a clear contract statement, so reject is not warranted. The paper would be strengthened by an explicit limitations paragraph stating that the generator is exact for the finite-precision CDF specification, not for the idealized continuous distribution, and that errors in the supplied CDF are inherited unchanged. The scope is a good fit for PLDI: the algorithms, proofs, and artifact are all of high quality."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This one is worth your time. It is the first general, automated way to turn a finite-precision CDF into an exact, entropy-optimal random variate generator. The lazy path refinement of a Knuth-Yao tree (Algorithm 1) and the integer-only extraction of exact float differences (Theorems 5.16 and E.3) are genuinely new, and the main Theorem 5.17 is sound for CDFs satisfying Def 5.10. The proofs are detailed, and the dependence on Knuth-Yao's lower bound is explicit, so no circularity.\n\nThe real soft spot is the interop claim. Listing 2 advertises GENERATE_FROM_CDF(gsl_cdf_gaussian_P, 5.0) without a wrapper, but for IEEE-754 the top element phi_B(1^n) is the NaN pattern, and GSL CDFs return NaN there, not 1. Def 5.10 requires F(phi_B(1^n))=1. Algorithm 2 never evaluates F at that point, so the top interval's probability mass is effectively defined by 1 - F(pred), which is NaN with the unmodified GSL functions. The theorem does not cover the advertised use. The fix is trivial, wrap or clamp the top and bottom, but the paper should state and implement it, and the evaluation should confirm it.\n\nTwo smaller nits. The abstract says higher accuracy, but Section 7 measures output range coverage, not statistical distance to the target distribution. That is a genuine overclaim. And the proofs are pen-and-paper, not machine-checked, so formal guarantees should be read in the usual PL sense, not the verified-sampler sense of Bagnall et al.\n\nWho gets value: anyone building samplers for discrete distributions over floats, or working on finite-precision differential privacy or lattice crypto where exactness and entropy consumption matter. The evaluation is reasonable and the library is on GitHub. This deserves a serious referee. I would send it out, with a request to address the wrapper issue and tone down the accuracy claim. The central mechanism is solid.","headline":"A genuinely new method for exact finite-precision random variate generation, with a real but fixable gap between the formal theorem and the advertised GSL interop.","tokens_in":65798,"tokens_out":6034,"would_cite":true,"duration_ms":66617,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65C10","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Any finite-precision CDF program can be turned into an exact random variate generator that consumes the minimum expected number of input bits and uses only fixed-width integer arithmetic.","keywords":["random variate generation","entropy-optimal sampling","DDG trees","finite-precision CDF","binary number formats","lazy path refinement","formal guarantees","cumulative distribution function"],"falsifier":"Enumerate all CDFs over a tiny binary format, such as a format with $1+E+m = 3$ bits, run the synthesized generator on every random-bit prefix up to a fixed depth, and compare the empirical output frequencies with $F(b)-F(\\operatorname{pred}(b))$ over the format's values; any mismatch would falsify the exactness part of Theorem 5.17. For entropy optimality, compute the average number of bits consumed per output over the same enumeration and check it against the binary-expansion leaf-count sum $\\sum_i \\sum_j j\\,2^{-j}\\,[p_i]_j$; a measured cost below the lower bound is impossible and a cost above it would violate optimality.","tokens_in":64768,"feed_emoji":"🎲","tokens_out":9278,"duration_ms":100806,"temperature":0.7,"pith_summary":"Standard random-variate libraries operate under an idealized model in which a computer can draw a perfectly uniform real number and compute with infinite precision; on actual hardware, the distribution actually produced by such a generator is generally unknown, inconsistent with the library's own distribution functions, and unreliable in the tails. The paper replaces this pipeline with a formal one: the user supplies a finite-precision numerical program that computes a cumulative distribution function (CDF), and the method automatically synthesizes a generator that is exact for that CDF. The central claim is that the synthesized generator is entropy-optimal, meaning it uses the fewest expected random bits possible among all exact generators for that distribution, and it does so using only fixed-width integer arithmetic at the same precision as the CDF. A variant that combines the CDF with a survival function widens the support of the generator, especially in the tails, while preserving the same guarantees. If the central claim is right, exact samplers with known output distributions become an automation step rather than a hand-tuned implementation task.","feed_headline":"One CDF program yields exact, bit-optimal random samplers","feed_subtitle":"Feed in a finite-precision CDF and get an exact sampler that uses the fewest random bits.","key_machinery":"The load-bearing object is the entropy-optimal discrete distribution generating (DDG) tree: a prefix-free binary decision tree in which the number of leaves labeled with outcome $i$ at depth $j$ equals the $j$-th binary digit of the outcome's probability. Rather than build such a tree, Algorithm 1 performs lazy path refinement, expanding only the leaf reached on the current execution and using two classification theorems about binary expansions to know, at each level, whether the next bit is forced, whether a coin flip suffices, or whether the tree must be refined further. The finite-precision engine is a tuple-based bit extraction procedure that encodes the exact difference $x -_{\\mathbb{R}} x'$ of two floats as bit counts and integer tails and recovers any requested binary digit with integer shifts and masks; all intermediate values are representable in a single machine word.","core_discovery":"The paper's central discovery is that entropy-optimal generation is feasible for any finite-precision CDF without constructing an exponentially large decision tree. Its Theorem 5.17 states that Algorithm 2, synthesized from a CDF over any binary number format, returns a string $x$ with cumulative probability exactly $F(x)$ and consumes the minimum expected number of input bits among all exact generators, matching the information-theoretic lower bound for random variate generation. The proof works by viewing the CDF as a binary-coded probability distribution and lazily walking a single path through an entropy-optimal discrete distribution generating tree, refining only the leaf reached on the executed path. Two structural theorems about binary expansions of dyadic sums guarantee that at each refinement step there is exactly one relevant leaf, so the walk uses $O(k)$ time and $O(1)$ space per path, an improvement over the original full-tree construction. The finite-precision implementation extracts bits of exact differences of floating-point probabilities directly from their exponent and significand fields, keeping every intermediate value within one machine word.","pith_inferences":["The same synthesis recipe should extend to any piecewise finite-precision specification of a distribution: wherever a monotone endpoint-correct function is supplied, the DDG machinery applies, so users could define a CDF that switches approximations by region to obtain arbitrarily shaped tail policies. This is an extension the paper does not develop.","In settings where finite-precision sampling errors erase formal guarantees, such as differential privacy and lattice-based cryptography, the natural next experiment is to swap the affected sampler for a generator synthesized from a carefully debugged CDF and re-run the privacy or security evaluation; the exactness guarantee would then transfer to the application.","Because the expected bit cost of the optimal generator is bounded by a closed form in the format parameters, the measured bits-per-variate of a synthesized generator can serve as a diagnostic for how close a given CDF implementation is to a maximum-entropy distribution over the format."],"forward_implications":["Any CDF satisfying the finite-precision definition yields a generator whose output distribution is known explicitly, so the CDF, survival, and quantile operations of a library become mutually consistent by construction.","Practitioners can replace hand-written samplers with synthesized ones for the same formal specification, eliminating the gap between the intended distribution and the distribution actually sampled.","Because the generator uses only fixed-width integer arithmetic at the CDF's own precision, it cannot overflow, needs no arbitrary-precision library, and has a predictable per-variate memory cost.","Combining a CDF with a survival function at the median cutoff doubles the number of representable outcomes and restores symmetry for symmetric distributions, at negligible entropy and runtime overhead in the reported evaluations."],"supporting_citations":[{"why":"Supplies the DDG-tree formalism and the entropy-optimality criterion on which the paper's optimal generation algorithm is built.","marker":"[37]"},{"why":"Defines the conditional bit sampling baseline that the paper compares against and whose entropy inefficiency motivates the optimal algorithm.","marker":"[58]"},{"why":"Prior limited-precision generation work requiring much higher integer precision; the contrast motivates the one-machine-word arithmetic guarantee.","marker":"[63]"},{"why":"Defines the floating-point number format used as the running example of a binary number format.","marker":"[34]"},{"why":"Establishes the Real-RAM model of non-uniform random variate generation that the paper's finite-precision approach replaces.","marker":"[13]"},{"why":"Documents how floating-point effects in a Laplace sampler destroy differential privacy, providing the motivating failure case.","marker":"[42]"},{"why":"Supplies the high-quality CDF and survival function implementations reused by the synthesized generators in the evaluation.","marker":"[24]"}],"fun_headline_variants":["Exact samplers from any CDF, fewest random bits","Bit-optimal sampling from a single CDF program","Provably optimal bit use for any finite-precision CDF","Automated exact random variates with minimal entropy","One CDF, exact samplers, provably minimal bits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee depends on the supplied CDF being a genuine finite-precision specification: it must be monotone nondecreasing, return values in $[0,1]$, and assign cumulative probability $1$ to the largest representable value; if the implementation violates these conditions, or if the specification itself misrepresents the intended distribution, the generator is exact only for that specification and inherits its errors.","fun_headline_variants_meta":{"raw":{"variants":["Exact samplers from any CDF, fewest random bits","Bit-optimal sampling from a single CDF program","Provably optimal bit use for any finite-precision CDF","Automated exact random variates with minimal entropy","One CDF, exact samplers, provably minimal bits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000936,"raw_usage":{"total_tokens":4010,"prompt_tokens":958,"completion_tokens":3052,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":2968}},"tokens_in":574,"tokens_out":3052,"duration_ms":24608,"temperature":1.0,"reasoning_tokens":2968,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:23:30.173973+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all CDFs over a tiny binary format, such as a format with $1+E+m = 3$ bits, run the synthesized generator on every random-bit prefix up to a fixed depth, and compare the empirical output frequencies with $F(b)-F(\\operatorname{pred}(b))$ over the format's values; any mismatch would falsify the exactness part of Theorem 5.17. For entropy optimality, compute the average number of bits consumed per output over the same enumeration and check it against the binary-expansion leaf-count sum $\\sum_i \\sum_j j\\,2^{-j}\\,[p_i]_j$; a measured cost below the lower bound is impossible and a cost above it would violate optimality.","supporting_citations":[{"cited_title":"Knuth and Andrew C","cited_arxiv_id":null,"evidence_quote":"Supplies the DDG-tree formalism and the entropy-optimality criterion on which the paper's optimal generation algorithm is built."},{"cited_title":"Sobolewski and W","cited_arxiv_id":null,"evidence_quote":"Defines the conditional bit sampling baseline that the paper compares against and whose entropy inefficiency motivates the optimal algorithm."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Prior limited-precision generation work requiring much higher integer precision; the contrast motivates the one-machine-word arithmetic guarantee."},{"cited_title":"1986.Non-Uniform Random Variate Generation","cited_arxiv_id":null,"evidence_quote":"Establishes the Real-RAM model of non-uniform random variate generation that the paper's finite-precision approach replaces."},{"cited_title":"2009.GNU Scientific Library Reference Manual(3rd ed.)","cited_arxiv_id":null,"evidence_quote":"Supplies the high-quality CDF and survival function implementations reused by the synthesized generators in the evaluation."}],"review_version":1}