almost-uniform generation

Concept

Almost-uniform generation is the task of sampling solutions of a Boolean (or other) constraint so that the probability of any individual solution is within a multiplicative factor of the uniform distribution; it is the practically achievable relaxation of strict uniform generation, which is typically intractable for large constraint sets. In hardware verification it underpins constrained-random verification, where engineers seek input stimuli that are 'random enough' to expose unknown bugs.

First seen 7/26/2026

Last seen 7/26/2026

Evidence 5 chunks

Wiki v1

WIKI

Definition

Almost-uniform generation refers to algorithms that produce samples from the solution space of a set of constraints such that the probability assigned to each solution is within a small multiplicative factor of the probability assigned under the uniform distribution. It is the practical relaxation of uniform generation, which demands that every satisfying assignment be chosen with exactly equal probability.

Motivation

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

2 connections

UniGen ← implements 99% 2e

UniGen is described as the first algorithm to provide strong two-sided guarantees of almost-uniformity.

constrained random verification ← uses 95% 1e

CRV requires almost-uniform or uniform sampling of constraint solutions for unbiased bug discovery.

LINKED ENTITIES

2 links

UniGen IMPLEMENTS Extracted graph relationship

constrained random verification USES Extracted graph relationship

CITATIONS

5 sources

5 citations — click to expand

[1] Almost-uniform generation is the practically achievable relaxation of uniform generation of solutions of Boolean constraints, providing stronger guarantees than purely heuristic sampling while remaining scalable. Balancing Scalability and Uniformity in SAT Witness Generator

[2] Constrained-random verification (CRV) is the predominant industrial approach to functional verification of digital designs and requires almost-uniform sampling of constraint solutions because the distribution of bugs is unknown a priori. Balancing Scalability and Uniformity in SAT Witness Generator

[3] Prior work on uniform SAT witness generation split into algorithms with strong theoretical uniformity guarantees that scale poorly, and practical heuristics with weak or no uniformity guarantees. Balancing Scalability and Uniformity in SAT Witness Generator

[4] UniWit (Chakraborty, Meel, Vardi) and PAWS (Ermon, Gomes, Sabharwal, Selman) are prior algorithms that bridge or target the (almost-)uniform generation problem for Boolean constraints. Balancing Scalability and Uniformity in SAT Witness Generator

[5] Uniform generation of SAT witnesses is of independent theoretical interest and has applications beyond constrained-random verification. Balancing Scalability and Uniformity in SAT Witness Generator