OpenNovelty.org

Energy-Efficient Random Variate Generation via Compressed Lookup Tables

ICLR 2026 Conference SubmissionAnonymous Authors
OpenReview Score: 7.0Download Report PDF
energy-efficiencysampling
Abstract:

Generating (pseudo-)random variates lies at the core of probabilistic machine learning and prediction algorithms and yet remains a major bottleneck due to its high computational and energy cost. In this paper, we introduce a general and scalable sampling strategy that enables fast and energy-efficient random variate generation from arbitrary distributions. Our approach is based on efficient lookup tables combined with a fast index sampling scheme. Using only a handful of fast and energy-efficient compute operations on simple array structures, we achieve superior speed, energy efficiency, and precision at near-optimal entropy cost compared to state-of-the-art techniques. Microbenchmarking our approach with a C implementation shows up to 40% savings in time and 60% in energy compared to state-of-the-art approaches. Compared to commonly employed Python samplers we achieve a 100x time improvement.

Disclaimer
This report is AI-GENERATED using Large Language Models and WisPaper (A scholar search engine). It analyzes academic papers' tasks and contributions against retrieved prior work. While this system identifies POTENTIAL overlaps and novel directions, ITS COVERAGE IS NOT EXHAUSTIVE AND JUDGMENTS ARE APPROXIMATE. These results are intended to assist human reviewers and SHOULD NOT be relied upon as a definitive verdict on novelty.
NOTE that some papers exist in multiple, slightly different versions (e.g., with different titles or URLs). The system may retrieve several versions of the same underlying work. The current automated pipeline does not reliably align or distinguish these cases, so human reviewers will need to disambiguate them manually.
If you have any questions, please contact: mingzhang23@m.fudan.edu.cn

Overview

Overall Novelty Assessment

The paper proposes a compressed lookup table (cLUT) sampling method for generating random variates from arbitrary discrete distributions, emphasizing speed and energy efficiency. It resides in the 'Energy and Speed Optimization' leaf under 'Implementation Efficiency and Computational Optimization', which contains only two papers total (including this one). This leaf focuses specifically on computational speed and energy metrics through compressed structures, distinguishing it from adjacent leaves that address space complexity or parallel execution. The sparse population of this leaf suggests that energy-aware sampling optimizations remain relatively underexplored in the literature.

The taxonomy tree reveals several neighboring research directions. The 'Alias Method and Table-Based Techniques' leaf (three papers) covers classical constant-time sampling structures, while 'Dynamic and Space-Efficient Structures' (two papers) addresses succinct representations and dynamic updates. The 'Rejection and Approximate Sampling' leaf (three papers) explores alternative algorithmic paradigms. The paper's focus on compressed tables positions it at the intersection of classical table-driven methods and modern resource constraints, diverging from purely theoretical optimality (covered in 'Exact Sampling with Entropy Optimality') and from domain-specific applications (e.g., 'Generative Modeling and Neural Networks' with six papers).

Among thirty candidates examined across three contributions, none were identified as clearly refuting the paper's claims. The 'compressed lookup table sampling method' examined ten candidates with zero refutable matches, as did the 'comprehensive benchmarking' and 'practical impact demonstration' contributions. This suggests that within the limited search scope—focused on top-K semantic matches and citation expansion—no prior work directly overlaps with the specific combination of compression techniques, energy metrics, and arbitrary distribution support. However, the small candidate pool (thirty papers) and the presence of only one sibling paper in the same taxonomy leaf indicate that the analysis covers a narrow slice of potentially relevant literature.

Given the limited search scope and sparse taxonomy leaf, the work appears to occupy a relatively unexplored niche combining energy efficiency with general-purpose discrete sampling. The absence of refutable candidates among thirty examined papers, alongside the leaf's low population, suggests novelty within the analyzed subset. However, the analysis does not cover exhaustive literature on table-based methods or energy-aware computing more broadly, leaving open the possibility of related work in adjacent fields or implementation-focused venues not captured by semantic search.

Taxonomy

Core-task Taxonomy Papers
50
3
Claimed Contributions
30
Contribution Candidate Papers Compared
0
Refutable Paper

Research Landscape Overview

Core task: random variate generation from arbitrary discrete distributions. The field organizes around several complementary perspectives. Foundational branches establish classical algorithms and theoretical frameworks—such as the Alias Method[10] and inversion techniques—that underpin most modern samplers. Implementation efficiency and computational optimization focus on reducing time and space costs through data structures, preprocessing, and energy-aware designs. Specialized distribution classes address particular probability models (e.g., hypergeometric, binomial) or sampling contexts (e.g., quantum circuits, hierarchical structures), while application domains tailor methods to real-world settings like auction design or power flow analysis. Theoretical foundations explore statistical properties, entropy bounds, and formal guarantees, and general references provide pedagogical resources for practitioners. Within the optimization-oriented branches, a handful of works pursue speed and memory trade-offs using compressed representations or adaptive rejection schemes. For instance, Fast Loaded Dice[16] and Optimal Approximate Sampling[2] explore how to balance preprocessing overhead against query time, while Binomial Runtime[27] examines distribution-specific optimizations. Compressed Lookup Tables[0] sits squarely in this energy and speed optimization cluster, emphasizing compact data structures that reduce both memory footprint and access latency. Compared to neighbors like Binomial Runtime[27], which targets a specific distribution family, Compressed Lookup Tables[0] aims for broader applicability across arbitrary discrete distributions by leveraging compression techniques. This positions the work as a bridge between classical table-based methods and modern resource-constrained environments, addressing the perennial tension between generality and efficiency in discrete sampling.

Claimed Contributions

Compressed lookup table (cLUT) sampling method

The authors introduce a new sampling algorithm that uses compressed lookup tables with a lossless compression scheme to generate random variates from arbitrary discrete distributions. The compression achieves an exponential ratio while enabling fast, energy-efficient sampling through simple array operations and direct indexing without conditional branching.

10 retrieved papers
Comprehensive benchmarking against state-of-the-art methods

The authors provide extensive empirical comparisons of cLUT with existing state-of-the-art sampling methods (ALDR, FLDR, Alias method) across multiple metrics including speed, energy consumption, memory usage, and bit efficiency, demonstrating superior performance especially for larger distributions.

10 retrieved papers
Demonstration of practical impact in machine learning applications

The authors benchmark cLUT against standard Python library samplers (NumPy, PyTorch, JAX) showing 10-100× speedups, and demonstrate its practical value through a TrueSkill application case study that achieves substantial reductions in both execution time and energy consumption in real-world probabilistic machine learning tasks.

10 retrieved papers

Core Task Comparisons

Comparisons with papers in the same taxonomy category

Contribution Analysis

Detailed comparisons for each claimed contribution

Contribution

Compressed lookup table (cLUT) sampling method

The authors introduce a new sampling algorithm that uses compressed lookup tables with a lossless compression scheme to generate random variates from arbitrary discrete distributions. The compression achieves an exponential ratio while enabling fast, energy-efficient sampling through simple array operations and direct indexing without conditional branching.

Contribution

Comprehensive benchmarking against state-of-the-art methods

The authors provide extensive empirical comparisons of cLUT with existing state-of-the-art sampling methods (ALDR, FLDR, Alias method) across multiple metrics including speed, energy consumption, memory usage, and bit efficiency, demonstrating superior performance especially for larger distributions.

Contribution

Demonstration of practical impact in machine learning applications

The authors benchmark cLUT against standard Python library samplers (NumPy, PyTorch, JAX) showing 10-100× speedups, and demonstrate its practical value through a TrueSkill application case study that achieves substantial reductions in both execution time and energy consumption in real-world probabilistic machine learning tasks.

Table of Contents