Ancestral Gumbel-Top-k sampling
Algorithms AIMech:AncestralGumbelTopKSampling DRAFT
An exact without-replacement sampler for finite discrete Bayesian-network configurations that propagates conditional Gumbel subtree maxima through a bounded priority frontier, with a configurable number of parallel expansions and parent-respecting variable selection.
Identity Notes & Concept Scope
This is Kool and colleagues’ 2020 general ancestral algorithm. It extends the 2019 stochastic beam sampler beyond a fixed sequence-layer schedule: serial expansion is best-first, while expanding the whole retained frontier yields the stochastic-beam specialization. The generic categorical Gumbel-Top-k identity remains a separate mathematical method. Equal output distributions across expansion schedules do not make those schedules or their computational costs identical. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 331 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in worktree and main, returning 11 and 11 lines respectively. All 10 unique hit contents were inspected: neighboring Gumbel-Top-k contrasts, saved review and ledger references, new source leads, and incidental concrete-distribution wording in an older random-search report, not existing candidate records. Exact checkout counts and differences are retained in the ledger. Nine exact AIO CLASS nodes with scoped synonyms/comments and outgoing edges and six full native neighboring records were inspected. Absence is bounded to this snapshot and semantic neighborhood.
Claims & Grounded Evidence
3 Claims
Mechanism
#method
Given a finite discrete Bayesian DAG with normalized parent-conditioned probabilities, choose a requested k no larger than the positive-probability configuration support and a parallel expansion budget m between 1 and the initial k. Start a priority frontier at the empty assignment, with log mass zero and a Gumbel root maximum sampled from Gumbel(0) or conditioned to zero. Each retained partial assignment represents a disjoint set of possible completions and carries their maximum perturbed log probability. Remove up to m highest-priority entries. Keep already-complete entries unchanged; for each incomplete entry choose an unassigned variable whose parents have been assigned, form all of its possible-value children, and update each child’s log mass with that variable’s conditional log probability. Sample child Gumbel maxima conditionally on their maximum equaling the parent score, using the source’s conditional-maximum transform. Combine children and retained entries with the unexpanded frontier, then keep at most the remaining requested count of highest-priority entries. Emit a completed assignment only while it is at the head of the priority frontier, decrementing the remaining sample count for every emitted assignment. Continue until the requested ordered sample has been returned. The pruning proof uses disjoint completion sets and consistent maxima to preserve the same ordered Gumbel-Top-k distribution as explicit enumeration of all configurations.
Scope
#parallel-specialization
With m=1 and a fixed variable order the algorithm expands the highest-priority incomplete configuration first and can emit samples incrementally. Expanding the full retained frontier reproduces the layerwise stochastic-beam schedule under the fixed-order setup. The exact without-replacement distribution is preserved across the allowed scheduling choices, but total expansions and allocated processor work can differ.
Mechanism
#variable-selection
A globally fixed topological order is sufficient but not required. The next variable may depend on the sampled partial assignment, provided every parent of that variable is already assigned. Such a strategy changes the configuration tree and potential reuse/pruning while retaining the target distribution under the described construction.
⚠️ Curated Limitations & Negative Results
- The guarantee concerns finite discrete Bayesian networks with accessible normalized conditionals, well-defined positive support and the specified conditional-max construction. Arbitrary graphical models, cyclic dependencies or invalid zero-mass arithmetic are not silently covered.
- The frontier contains disjoint surviving completion domains; after pruning it need not cover the entire original domain. Reusing overlapping partial assignments or sampling a variable before its parents violates the stated construction.
- Serial m=1 expansion and full-frontier expansion can have the same sampling law but different work and parallel depth. The paper’s cost accounting includes allocated processor slots, idle slots and potentially unnecessary expansions; it is not a universal wall-clock speedup or a cost independent of variable-domain size.
- The retained frontier bound counts entries, not all memory for model states, temporary children, assignments or result storage. Finite precision, ties and numerical stability need implementation policies.
- The pseudocode’s access to the first queue element requires an empty-queue guard in an executable implementation. No literal pseudocode, author implementation or numerical benchmark was run.
- Without-replacement configurations are dependent samples. The method’s sampling law does not make an arbitrary unweighted estimator unbiased, and it is distinct from Gibbs transitions or ordinary envelope-based rejection sampling.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:BayesianNetwork
Bayesian Network
|
related_match | The primary algorithm is explicitly defined for finite discrete Bayesian networks and uses their parent-conditioned probabilities to partition configuration space. The pinned AIO node denotes the directed acyclic probabilistic model being sampled. This is an algorithm-to-input-model related match, not equivalence, subclass membership or a claim that the sampler itself is a learned network. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Wouter Kool, Herke van Hoof, Max Welling
|
primary paper
full_text
|
sha256:e230603db00b…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T16:30:45Z
Updated: 2026-10-11T16:30:45Z
Source File:
data/curated/AncestralGumbelTopKSampling.yaml