Enumeration and Ranking¶

Enumeration is the concern for models that can traverse their support in descending probability order. It is used for exact top-k answers, support inspection, rank queries, nucleus sets, structured decoding, and combinatorial optimization over probabilistic models.

Enumeration is capability-driven. A distribution, relation, or quantized model participates when it implements an enumerator and advertises the appropriate capability.

First Calls¶

import numpy as np
from mixle.enumeration import supports_enumeration, top_k
from mixle.stats import CategoricalDistribution

dist = CategoricalDistribution({"a": 0.5, "b": 0.3, "c": 0.2})

print(supports_enumeration(dist))
for value, log_p in top_k(dist, 3):
    print(value, np.exp(log_p))

The values returned by enumeration are model values. For a composite distribution, the value is a whole tuple or record. For a Markov model, it may be a sequence or path.

Enumerator Surface¶

Many enumerable objects expose enumerator():

enum = dist.enumerator()
top = enum.top_k(10)
nucleus = enum.top_p(0.95)
rank = enum.rank(value)

Common operations:

top_k(k): Most probable values with log probabilities.
top_p(p): Smallest high-probability set covering probability mass p.
rank(value): Number of values with strictly higher probability, when supported.
seek(i): Value near a probability rank or structural index, when supported.

Not every enumerable model supports every operation. Use mixle.describe to inspect exact capabilities.

Capabilities¶

Capability	Meaning
`Enumerable`	can iterate support in descending-probability order
`FiniteSupport`	support size is finite and can be queried
`RankableByIndex`	supports rank/seek or count-budget unranking

Check support explicitly:

import mixle
from mixle.enumeration import Enumerable, RankableByIndex

print(mixle.supports(dist, Enumerable))
print(mixle.supports(dist, RankableByIndex))

Composed Supports¶

Combinators preserve enumeration when their children support it.

from mixle.enumeration import top_k
from mixle.stats import CompositeDistribution, IntegerCategoricalDistribution

record = CompositeDistribution(
    [
        IntegerCategoricalDistribution(0, [0.6, 0.4]),
        CategoricalDistribution({"x": 0.7, "y": 0.3}),
    ]
)

for value, log_p in top_k(record, 5):
    print(value, log_p)

The enumeration is over whole records, not independent per-field lists.

Quantized and Count-Budget Indexes¶

Large or infinite supports often need an index. quantized_index and count_budget_index build seek/unrank structures that trade memory and accuracy for access to high-probability regions.

from mixle.enumeration import count_budget_index, quantized_index

q_index = quantized_index(dist, budget=4096)
c_index = count_budget_index(dist, budget=4096)

Use these when top-k traversal is too slow but you still need structured access to likely support values.

Latent Models and HMM Paths¶

Exact marginal ranking for mixtures and HMMs can be hard. Mixle provides specialized algorithms and reports the guarantee rather than silently treating an approximation as exact.

from mixle.enumeration import density_rank, hmm_best_paths

rank_report = density_rank(model, value, n_samples=10000)
paths = hmm_best_paths(hmm, observations, k=10)

Use HMMs and Latent Structure for HMM modeling details.

Autoregressive Enumeration¶

AutoregressiveEnumerable supports models that expose next-step log probabilities rather than a closed finite support. The count index can then perform thresholding and unranking over the generated tree.

from mixle.enumeration import AutoregressiveEnumerable, autoregressive_count_index

enumerable = AutoregressiveEnumerable(next_logprobs, start_state)
index = autoregressive_count_index(enumerable, budget=10000)

This is the bridge between token-like next-step models and structured probability ranking.

Relations¶

Enumeration also applies to feasible-set relations: assignments, paths, spanning trees, edit neighborhoods, subset regression, and related combinatorial objects. A relation defines the feasible structure; enumeration produces ranked feasible values.

Practical Guidance¶

Use top_k for small or clearly finite supports.
Use mixle.describe before relying on rank, seek, or exact enumeration.
Use quantized/count-budget indexes for large decomposable supports.
Treat latent marginal ranking as a different problem from path enumeration.
Prefer exact guarantees where available; inspect result objects when a route is approximate or bounded.

API Map¶

Import	Purpose
`top_k`, `supports_enumeration`	first calls for enumerable objects
`DistributionEnumerator`, `EnumerationError`	enumeration contract and errors
`Enumerable`, `FiniteSupport`, `RankableByIndex`	capability markers
`density_rank`, `DensityRankResult`	rank/cumulative queries for density models
`quantized_index`, `count_budget_index`	high-probability seek/unrank indexes
`best_first_union`, `merge_enumerators`, `ProductEnumerator`	generic best-first enumeration utilities
`hmm_best_paths`	k-best HMM state paths
`AutoregressiveEnumerable`, `autoregressive_count_index`	next-logprob enumeration