mixle.enumeration package

The enumeration concern — one home for “what can be enumerated, and how”.

Enumeration is not a property of distributions; it is a capability shared by distributions, relations, quantized objects, and any combinatorial model. Anything that can iterate its support in descending probability implements DistributionEnumerator (the contract) and reports the Enumerable capability; anything finite-or-structural can additionally be unranked by integer rank (RankableByIndex) through the count-budget seek index.

This module gathers that concern in one place — the contract, the capability lens, the k-best algorithms, the count-budget unranking, and the count semiring — so you can read off what enumeration is and who participates without hunting through utils/stats. The implementations live here, split by concern: generic stream primitives in streams, best-first / product search in best_first, the quantized seek/unrank index and the structural count-budget index in quantization, and the k-best combinatorial enumerators in assignment / spanning. Only the contract (DistributionEnumerator) lives in the compute layer and is re-exported here. mixle.enumeration.algorithms remains as a back-compat re-export of the stream / best-first / index names. Layout per docs/ARCHITECTURE.md.

Who plugs in: every finite/countable leaf (Categorical, Poisson, …), the combinators over enumerable children (Sequence, Composite, Mixture, …), the graph/ranking families (Markov chains, Mallows, Chow-Liu trees, spanning trees), and mixle.relations.Relation — all via the same enumerator().

class Enumerable

Bases: PredicateCapability

Its support can be iterated in descending-probability order (enumerator() works).

classmethod check(obj)

Return whether obj exposes a supported enumerator.

Parameters:

obj (Any)

Return type:

bool

class FiniteSupport

Bases: PredicateCapability

Has a finite number of distinct support points (support_size() is an int).

classmethod check(obj)

Return whether obj reports a finite, non-negative support size.

A Boolean is not a support count even though bool subclasses int: support_size() returning True used to certify a one-point support, so an object answering a yes/no question was routed as an enumerable finite distribution.

Parameters:

obj (Any)

Return type:

bool

class RankableByIndex

Bases: PredicateCapability

Supports random access by integer rank (unranking) via the count-budget seek index.

Finite-support enumerables are rankable by index through the count-DP semiring; the implication edge finite ==> enumerable ==> rankable is exactly this composition. (Decomposable combinators over infinite-but-countable children are also rankable structurally; this conservative check covers the finite-leaf case used by the dispatch layers.)

classmethod check(obj)

Return whether obj can be unranked by finite support index.

Parameters:

obj (Any)

Return type:

bool

supports(obj, capability)

Return whether obj provides capability (a Protocol, a PredicateCapability, or its name).

capability may be the capability class itself or the catalogued NAME STRING that capabilities() / describe() report (supports(x, "HasMoments")), so the query surface round-trips its own vocabulary.

For a runtime_checkable Protocol, isinstance establishes attribute presence only, not callable shape – an object with condition = 3 cleared supports(obj, Conditionable) and therefore require(), and the routing failure surfaced later as a TypeError inside the operation. These are authoritative dispatch declarations, so every declared protocol method must at least be callable on obj.

Parameters:

• obj (Any)

• capability (type | str)

Return type:

bool

top_k(dist, k)

Return the k highest-probability (value, log_prob) pairs.

Dispatches on capability, not class: a RankableByIndex distribution could random-access by rank, but every Enumerable distribution can stream its support in descending probability — so one implementation covers all of them, including user-defined ones. Raises a clear CapabilityError for distributions that support neither.

Parameters:

• dist (Any)

• k (int)

Return type:

list[tuple[Any, float]]

class DistributionEnumerator(dist)

Bases: ABC

Lazy iterator over the support of dist in non-increasing probability order.

Yields (value, log_prob) pairs, possibly infinitely many. Contract:

• Each support value is yielded exactly once (deduplication is the enumerator’s responsibility).

• log_prob equals dist.log_density(value) up to float round-off (~1e-10), and the sequence of log_probs is non-increasing up to the same tolerance.

• Values with zero probability are skipped, never yielded.

• Ties are broken deterministically by insertion order; no further guarantee.

Parameters:

dist (SequenceEncodableProbabilityDistribution)

top_k(k)

Return the k most probable (value, log_prob) pairs (fewer if the support is smaller).

Parameters:

k (int)

Return type:

list[tuple[Any, float]]

top_p(p, max_items=None)

Return the smallest descending-probability prefix whose total probability reaches p.

The nucleus / minimal high-probability set: because values are yielded in non-increasing probability order, the returned prefix is a minimum-size set of outcomes whose summed mass is >= p (e.g. p=0.95 gives a 95%-coverage support set – the discrete analogue of nucleus sampling). Accumulation stops as soon as the cumulative probability reaches p.

max_items caps how many values are pulled so an infinite or heavy-tailed support cannot run away. A cap is mandatory when the support has no known finite cardinality. The returned list-compatible NucleusResult reports whether the target was reached, the accumulated mass, and whether a cap stopped the search.

Parameters:

• p (float) – Target cumulative probability in [0, 1].

• max_items (Optional[int]) – Hard cap on the number of values pulled.

Returns:

A list-compatible nucleus result with termination provenance.

Return type:

NucleusResult

quantized_index(max_bits, bin_width_bits=1.0)

Precompute a bounded bit-quantized index over this enumeration.

The index groups values by floor((-log2 p(x)) / bin_width_bits), includes only values with -log2 p(x) <= max_bits, and returns exact log probabilities for indexed values. Building the index consumes this enumerator.

Parameters:

• max_bits (float) – Maximum information content in bits to index.

• bin_width_bits (float) – Width of each quantized probability bin in bits.

Returns:

mixle.enumeration.algorithms.QuantizedEnumerationIndex.

rank(value)

Rank and cumulative probability of value in the descending-probability order.

Returns a DensityRankResult with .rank (0-based count of strictly-more-probable outcomes; None if only the sampling estimate was used) and .cumulative_probability (G(value) = P(p(Y) >= p(value))). Exact head enumeration where the support is countable, with a Monte-Carlo fallback for the deep tail.

Parameters:

value (Any)

seek(index)

The value at descending-probability index (0-based) – the inverse of rank().

Returns a CountDPSeekResult carrying the value and a provable [rank_lower, rank_upper] bracket. Uses the structural count-DP for decomposable families, so arbitrarily deep indices are reachable without enumerating the prefix.

Parameters:

index (int)

seek_certified(index)

The value at descending index with a GUARANTEED bracket on its TRUE marginal rank.

Unlike seek() – whose bracket bounds only the tropical rank for a marginal family (mixture/HMM) – this widens the rank window by the family’s tropical_displacement_bits and divides out the component over-count, so the returned MarginalSeekResult [true_rank_lower, true_rank_upper] provably contains #{u : log p(u) > log p(value)}. It pins the rank exactly (.exact) for decomposable / provably-disjoint families and for shallow indices, and otherwise returns the certified provable envelope. For a decomposable family it agrees with seek().

Parameters:

index (int)

cumulative(value)

G(value) = P(p(Y) >= p(value)) – total mass of outcomes at least as probable as value.

Returns a CumulativeProbabilityResult with .probability plus explicit certification (.exact, .dropped_upper) of what that figure rests on.

Parameters:

value (Any)

nucleus_size(p)

Size of top_p() (the minimal >= p-mass set) WITHOUT materializing it.

Returns a CountDPTopPResult with a provable size bracket, from the structural count-DP – usable when the nucleus is far too large to list.

Parameters:

p (float)

from_index(start, stop=None)

Iterate (value, log_prob) in descending-probability order starting at structural start.

Yields the same stream as iterating a fresh enumerator but beginning at index start (and ending before stop if given). A fresh underlying enumeration is used, so this does not consume self. (Decomposable families admit a direct structural jump via the count-budget index; the current implementation skips the best-first prefix – the structural fast path is a WS-3 performance follow-up.)

Parameters:

• start (int)

• stop (int | None)

exception EnumerationError(dist, path='', reason='')

Bases: NotImplementedError

Raised when a distribution (or a child of a combinator) cannot enumerate its support.

The path argument identifies the offending child within a combinator, e.g. ‘CompositeDistribution.dists[1]’.

Parameters:

• dist (Any)

• path (str)

• reason (str)

Return type:

None

child_enumerator(child, path)

Construct child.enumerator(), annotating EnumerationError with the child’s path.

Combinator enumerators use this so a failure deep in a nested model reports the full path to the offending leaf, e.g. ‘CompositeDistribution.dists[1] -> MixtureDistribution.components[0] -> GaussianDistribution …’.

Parameters:

• child (ProbabilityDistribution)

• path (str)

Return type:

DistributionEnumerator

supports_enumeration(dist)

Return True if dist.enumerator() can be constructed.

Return type:

bool

class DensityRankResult(cumulative_probability, rank, exact, stderr, log_prob, method, rank_stderr=0.0)

Bases: object

Outcome of a rank / cumulative-probability query.

Parameters:

• cumulative_probability (float)

• rank (int | None)

• exact (bool)

• stderr (float)

• log_prob (float)

• method (str)

• rank_stderr (float)

cumulative_probability

G(x) = sum_{y: p(y) >= p(x)} p(y) (the descending-order CDF at x).

Type:

float

rank

number of observations strictly more probable than x (0-based position). Exact when the head enumeration resolved it; in "sampling" mode it is the rounded unbiased Monte-Carlo estimate (see rank_stderr); None when log p(x) = -inf, an exact-analytic CDF (no count) was used, or the sampling estimate itself overflowed (see rank_stderr, which is still finite – or inf – even when rank is None).

Type:

int | None

exact

True when the head enumeration resolved the query exactly WITH RESPECT TO the tol- equivalence relation ties are defined by (see density_rank’s tol parameter); False for a sampling estimate.

Type:

bool

stderr

standard error of cumulative_probability (0.0 when exact).

Type:

float

log_prob

log p(x).

Type:

float

method

"exact-head", "exact-exhausted", "exact-analytic", or "sampling".

Type:

str

rank_stderr

standard error of the Monte-Carlo rank estimate (0.0 when exact). Large relative to rank exactly in the deep-tail / high-entropy band where exact marginal rank is provably hard – treat the estimate as unreliable there.

Type:

float

density_rank(dist, value, max_exact=100_000, n_samples=20_000, seed=0, tol=_EXACT_TIE_TOL)

Rank and cumulative probability of value under dist’s descending-probability order.

Strategy:

1. If dist supports enumeration, walk the exact descending stream, accumulating the mass of every item at least as probable as value and counting those strictly more probable. If the stream drops below p(value) (or is exhausted) within max_exact items, the rank and cumulative probability are returned EXACTLY.

2. Otherwise (value is deeper than max_exact, or enumeration is unsupported), estimate the cumulative probability by Monte Carlo: G_hat = mean_i 1[log p(Y_i) >= log p(value)] with Y_i ~ dist. Reliable here precisely because G is large in the tail.

Parameters:

• dist (Any) – A distribution exposing log_density and sampler; optionally enumerator.

• value (Any) – The observation to locate.

• max_exact (int) – Cap on items pulled from the exact enumerator before falling back to sampling.

• n_samples (int) – Monte-Carlo sample count for the fallback; must be a positive integer (validated eagerly, even on a call that never reaches the sampling path – a bad n_samples is a caller bug regardless of whether this particular query happens to exercise it).

• seed (int) – Sampler seed for the fallback (reproducible).

• tol (float) – Log-probability tolerance for the >=/> comparisons (ties). Defaults to this module’s 1e-12 “true rank” convention (also used by count_dp_rank/count_dp_seek/ marginal_seek). exact=True is exact WITH RESPECT TO this tolerance’s equivalence relation: two scores within tol of each other are treated as tied. Widening tol trades a stricter mathematical comparison for robustness against floating-point jitter in log_density – know that a wide tol can change which values compare as tied.

Returns:

DensityRankResult.

Return type:

DensityRankResult

count_budget_index(dist, budget_bits, bin_width_bits=1.0, oversample=8, max_depth_bits=4096.0, num_workers=None, count_mode='exact')

Driver for the count-budget mode: deepen until the budget is covered, then build the index.

Calls dist.quantized_count_index(quantizer, max_fine_bucket) at geometrically increasing depths until the structural count reaches 2**budget_bits or the support is exhausted (no further truncation), then wraps the result with build_budget_index(). The exact log density of each unranked value is reported via dist.log_density.

When num_workers is greater than 1, the heavy count-histogram convolutions are computed on a process pool (parallel quantization); the parallel result is identical to the serial one. count_mode='float' carries counts as float64 (C-speed convolutions, exact below 2**53, ~1e-16 relative error per operation beyond) – the approximate-counting mode for deep budgets.

Parameters:

• budget_bits (float)

• bin_width_bits (float)

• oversample (int)

• max_depth_bits (float)

• num_workers (int | None)

• count_mode (str)

class SeekIndex(model, *, bin_width_bits=1.0, oversample=8, count_mode='exact', max_depth_bits=4096.0)

Bases: object

Build a model’s count-budget index once and answer many enumeration queries against it.

model is anything implementing the count-index contract – every mixle distribution with a quantized_count_index (Composite/Sequence/Markov exactly; Mixture/HMM as the documented tropical bound) and AutoregressiveEnumerable (so LLMs plug in).

Queries auto-deepen: asking for a rank (or a log-prob threshold) beyond the built depth rebuilds the DP at a geometrically larger budget, reusing whatever the model itself memoizes. max_depth_bits caps the deepening; past it, queries raise IndexError for out-of-range ranks.

Parameters:

• model (Any)

• bin_width_bits (float)

• oversample (int)

• count_mode (str)

• max_depth_bits (float)

property built_bits: float

The depth (bit budget) the index is currently built to (0 before the first build).

property truncated: bool

True when values beyond the built depth exist (deepening can still grow the index).

property builds: int

How many times the structural DP has been (re)built – the cost a persistent index amortizes.

property dropped_upper: float

Certified upper bound on in-budget values excluded by an approximation knob (e.g. branch_cap).

0.0 for exhaustive indices. The true in-budget count lies in [len(self), len(self) + dropped_upper]; deepening does not recover these (that is what distinguishes it from truncated).

ensure_bits(depth_bits)

Make the index cover at least depth_bits of information (build or deepen if needed).

Parameters:

depth_bits (float)

Return type:

SeekIndex

ensure_count(n)

Make the index hold at least n values (geometric deepening from the current depth).

Every rebuild at least doubles the built depth, so an ascending sequence of queries costs O(log) rebuilds total and the final (deepest) build dominates the work – the amortization a persistent index exists for.

Parameters:

n (int)

Return type:

SeekIndex

unrank(i)

The i-th most probable value (0-based, quantized order) and its exact log-probability.

Order is exact between fine buckets (width bin_width_bits / oversample bits) but unspecified within one: two values whose log_density differs by less than one bucket’s width can be returned in either relative order (see slice()’s note – narrow that window by raising oversample or lowering bin_width_bits). The returned log_density is always exact regardless.

Parameters:

i (int)

Return type:

tuple[Any, float]

slice(start, k)

Up to k values starting at rank start (one deepen at most, then table reads).

Not a strict sort by log_density: values are ordered by quantized fine bucket (bucket width bin_width_bits / oversample bits), and within a shared bucket the order follows the structural enumeration (token/branch order), not the exact log-density. Two values less than one bucket-width apart can therefore come back in either order – this is a documented property of the quantization, not a bug, and it is independent of branch_cap/pruning. If a caller needs a strict top-k sort (e.g. asserting descending order across close candidates), either re-sort the slice by its returned log_density values, or shrink the ambiguity window by raising oversample / lowering bin_width_bits on the model/index – it cannot be eliminated, only made arbitrarily small.

Parameters:

• start (int)

• k (int)

Return type:

list[tuple[Any, float]]

iter_from(start=0)

Iterate values from rank start through the end of the built index (no auto-deepen).

Parameters:

start (int)

Return type:

Iterator[tuple[Any, float]]

count(min_log_prob)

How many values have log_density >= min_log_prob – read off the fine histogram.

Exact-carrier families return an int; count_mode='float' (or a float-carrying model like the deep-budget autoregressive fast path) returns a float with the documented relative error. Mixture/HMM counts are the structural (tropical) upper bound those families document.

Parameters:

min_log_prob (float)

Return type:

int | float

threshold(rank)

Log-probability of the rank-th most probable value (the top-rank boundary).

Parameters:

rank (int)

Return type:

float

rank_bracket(value)

A [lo, hi] bracket on value’s quantized rank, from its structural fine bucket.

lo counts every value in strictly shallower buckets; hi adds the rest of the value’s own bucket. For Mixture/HMM the bucket is the documented tropical projection, so the bracket carries that projection’s semantics (see the family docstrings).

Parameters:

value (Any)

Return type:

tuple[int, int]

fine_histogram(min_depth_bits=None)

The built fine CountIndex (ensuring at least min_depth_bits) – for mass/rank math.

Parameters:

min_depth_bits (float | None)

logit_error_bucket_slack(eps_nats, steps, quantizer)

Sound bucket-shift bound when step log-probabilities carry up to eps_nats of error each.

The license to run enumeration forwards on a quantized model (int8/int4 inference, a distilled twin): enumeration never needs logits more accurate than the fine-bucket width. If every step log-probability is within eps_nats of the true model’s, a steps-long value’s accumulated fine bucket shifts by at most ceil(steps * eps_nats / ln2 * fine_per_bit) buckets – this bound. It composes additively with the existing steps-floor structural smear, so every count / rank / mass bracket in this package widens by exactly this many buckets and remains sound.

Practical reading: with the default quantizer (1/8-bit fine buckets) a per-step logit error of ~0.01 nats (typical of int8 inference) costs ceil(steps * 0.115) buckets – about one bucket per nine steps – while the forwards run 2-4x faster.

Parameters:

• eps_nats (float)

• steps (int)

• quantizer (Quantizer)

Return type:

int

quantized_index(enum, max_bits, bin_width_bits=1.0)

Convenience wrapper for QuantizedEnumerationIndex.from_enumerator.

Parameters:

• enum (Iterator[tuple[Any, float]])

• max_bits (float)

• bin_width_bits (float)

Return type:

QuantizedEnumerationIndex

class QuantizedEnumerationIndex(bins, bin_width_bits, max_bits, truncated)

Bases: object

Bounded, indexable view of an exact probability-ordered enumeration.

Items are grouped into log-probability bins measured in bits:

bits(x) = -log2(p(x)) bin(x) = floor(bits(x) / bin_width_bits)

Only items whose bit cost is at most max_bits are indexed. The returned (value, log_prob) pairs always carry the original exact log probability; the quantized bins are used only for counting and rank lookup.

The generic implementation can build from an exact enumerator stream, so it works for every currently enumerable discrete stats model. Simple distributions may also build directly from scored support items, and distribution-specific dynamic programs can produce the same bin layout without relying on an exact global stream.

Parameters:

• bins (Sequence[tuple[int, list[tuple[Any, float]]]])

• bin_width_bits (float)

• max_bits (float)

• truncated (bool)

static bin_for_log_prob(log_prob, bin_width_bits=1.0)

Return the quantized bit bin for a log probability.

Parameters:

• log_prob (float)

• bin_width_bits (float)

Return type:

int

classmethod from_enumerator(enum, max_bits, bin_width_bits=1.0)

Build an index from an exact non-increasing-probability enumerator.

Parameters:

• enum (Iterator[tuple[Any, float]]) – Iterator yielding (value, log_prob) pairs in exact descending order.

• max_bits (float) – Include only values with -log2(p) <= max_bits.

• bin_width_bits (float) – Width of each quantized probability bin in bits.

Returns:

QuantizedEnumerationIndex over the bounded prefix/domain slice.

Return type:

QuantizedEnumerationIndex

classmethod from_items(items, max_bits, bin_width_bits=1.0, sorted_items=False, truncated=None)

Build an index from known support items and exact log probabilities.

Parameters:

• items (Sequence[tuple[Any, float]]) – Finite collection of (value, log_prob) pairs. Zero-probability items with log_prob == -inf are ignored.

• max_bits (float) – Include only values with -log2(p) <= max_bits.

• bin_width_bits (float) – Width of each quantized probability bin in bits.

• sorted_items (bool) – If True, preserve the input order. Otherwise, stable-sort included items by descending log probability.

• truncated (bool | None) – Optional explicit truncation flag. If omitted, it is True when any finite-probability item was outside the bit bound.

Returns:

QuantizedEnumerationIndex over the bounded finite item set.

Return type:

QuantizedEnumerationIndex

bin_for_index(index)

Return (bin_id, offset_within_bin) for a bounded quantized rank.

Parameters:

index (int)

Return type:

tuple[int, int]

get(index)

Return the indexed (value, exact_log_prob) pair.

Parameters:

index (int)

Return type:

tuple[Any, float]

slice(start, k)

Return up to k indexed pairs starting at start.

Parameters:

• start (int)

• k (int)

Return type:

list[tuple[Any, float]]

iter_from(start=0)

Iterate indexed pairs from start to the end of the bounded index.

Parameters:

start (int)

Return type:

Iterator[tuple[Any, float]]

bin_items(bin_id)

Return all indexed items in a quantized probability bin.

Parameters:

bin_id (int)

Return type:

list[tuple[Any, float]]

summary()

Return a compact description of the bounded index.

Return type:

dict[str, Any]

class LazyQuantizedEnumerationIndex(counts, bin_width_bits, max_bits, truncated, getter)

Bases: QuantizedEnumerationIndex

Quantized index whose bin counts are precomputed but items are unranked lazily.

This supports compositional distributions where a dynamic program can count how many values fall in each quantized log-density bin without materializing every Cartesian-product value. The getter receives a bin id and offset within that bin and returns the exact (value, log_prob) pair for that quantized rank.

Parameters:

• counts (dict[int, int])

• bin_width_bits (float)

• max_bits (float)

• truncated (bool)

• getter (Callable[[int, int], tuple[Any, float]])

bin_for_index(index)

Return (bin_id, offset_within_bin) for a bounded quantized rank.

Parameters:

index (int)

Return type:

tuple[int, int]

get(index)

Return the indexed (value, exact_log_prob) pair.

Parameters:

index (int)

Return type:

tuple[Any, float]

iter_from(start=0)

Iterate indexed pairs from start to the end of the bounded index.

Parameters:

start (int)

Return type:

Iterator[tuple[Any, float]]

bin_items(bin_id)

Return all indexed items in a quantized probability bin.

Parameters:

bin_id (int)

Return type:

list[tuple[Any, float]]

class CountSemiring

Bases: DecomposableSemiring

Witness-retaining carrier over reified nodes / CountIndex: structural counting + unranking.

leaf/plus/scale/map_values build _CNode trees unranked by the iterative _unrank() (bounded call-stack regardless of chain depth); times/product convolve via mixle.enumeration.quantization.convolve_indices() (flat unranker – identical bin counts and within-bucket order to the previous path). Both element kinds expose .hist and .get_in_bucket, so they interoperate freely.

zero()

Return the empty count carrier.

Return type:

_CNode

one()

Return the count carrier identity for product composition.

Return type:

_CNode

leaf(value, log_prob, quantizer)

Lift a scored value into a count carrier node.

Parameters:

• value (Any)

• log_prob (float)

• quantizer (Quantizer)

Return type:

_CNode

from_enumerator(enum, quantizer, max_fine_bucket)

Lift an atomic distribution’s exact enumerator into a carrier element (depth-bounded).

Parameters:

• enum (Iterator[tuple[Any, float]])

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

tuple[CountIndex, bool]

plus(a, b)

Add count carriers for alternative branches.

Return type:

_CNode

times(a, b, quantizer, max_fine_bucket)

Convolve count carriers for independent factors.

Parameters:

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

CountIndex

product(elements, quantizer, max_fine_bucket)

Convolve an n-ary collection of count carriers.

Parameters:

• elements (Sequence[Any])

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

CountIndex

scale(a, log_prob, quantizer, max_fine_bucket=None)

Multiply by a constant probability factor: shift buckets by the factor, value unchanged.

This is the action of the base log-prob monoid on the carrier (e.g. a sequence length term, a Markov transition/initial term). Optionally truncate the shifted histogram to a depth bound.

Parameters:

• log_prob (float)

• quantizer (Quantizer)

• max_fine_bucket (int | None)

Return type:

_CNode

map_values(a, fn)

Relabel values (pushforward) without touching counts or buckets – e.g. tuple -> list.

Parameters:

fn (Callable[[Any], Any])

Return type:

_CNode

power_prefix(a, max_k, quantizer, max_fine_bucket)

Return [a^(times 0), …, a^(times K)] (K <= max_k), the k-fold self-products.

The histograms are built incrementally (O(max_k) convolutions, shared), so this is the count side of an iid sequence. Each element’s unranker is the flat product of k copies, built lazily and cached – identical bin counts and within-bucket order to calling product([a]*k) directly, but without the O(k^2) eager cost. Stops early if the element mass is exhausted within the depth bound.

Parameters:

• a (CountIndex)

• max_k (int)

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

Sequence[CountIndex]

class DecomposableSemiring

Bases: ABC

A witness-retaining semiring over which a likelihood reduction is evaluated.

zero/one are the additive/multiplicative identities; plus pools mutually exclusive alternatives (e.g. different sequence lengths or Markov end-states); times composes independent factors (whose log-probabilities add); product is n-ary times. leaf lifts a single scored atom into the carrier. Implementations choose the carrier E; for counting it is CountIndex, whose per-bucket structure is the witness needed to unrank.

abstractmethod zero()

Return the additive identity.

Return type:

E

abstractmethod one()

Return the multiplicative identity.

Return type:

E

abstractmethod leaf(value, log_prob, quantizer)

Lift one scored atom into the semiring carrier.

Parameters:

• value (Any)

• log_prob (float)

• quantizer (Quantizer)

Return type:

E

abstractmethod plus(a, b)

Combine mutually exclusive alternatives.

Parameters:

• a (E)

• b (E)

Return type:

E

abstractmethod times(a, b, quantizer, max_fine_bucket)

Compose independent factors.

Parameters:

• a (E)

• b (E)

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

E

product(elements, quantizer, max_fine_bucket)

n-ary times. Default folds times; carriers may override for efficiency/order.

Parameters:

• elements (Sequence[E])

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

E

class TropicalSemiring

Bases: DecomposableSemiring

Max-plus (Viterbi) carrier: the single best configuration and its log-probability.

The second realization of DecomposableSemiring – it swaps only the carrier (the contract this module was built around). Where CountSemiring counts the support in each quantized bin, the tropical carrier folds the same leaf/plus/times reduction over the (max, +) semiring: plus keeps the higher-probability alternative, times/product add log-probabilities and concatenate witnesses. The result is the Viterbi (most-probable) configuration and its exact log-probability – the top of the descending-probability order, and hence an exact bound usable by any family expressible in leaf/plus/times.

Crucially this includes the non-decomposable families (HMM / Mixture): exact counting couples across structure (which is why the count index does not serve them), but the Viterbi bound factors cleanly through the tropical fold. (Exact bounded counting for those families is the state-augmented count DP – a further step; for HMM the exact descending enumeration is already available via mixle.enumeration.hmm_paths.hmm_best_paths().)

The witness is the flat tuple of leaf atoms along the best configuration (the tropical carrier keeps a single witness, not the per-child structured value the count carrier reconstructs on unrank), which is exactly what a Viterbi decode wants. quantizer / max_fine_bucket are accepted for interface symmetry but unused – the tropical fold needs no quantization.

zero()

Return the tropical additive identity.

Return type:

_Trop

one()

Return the tropical multiplicative identity.

Return type:

_Trop

leaf(value, log_prob, quantizer=None)

Lift a scored value into the tropical carrier.

Parameters:

• value (Any)

• log_prob (float)

• quantizer (Quantizer | None)

Return type:

_Trop

plus(a, b)

Keep the higher-scoring alternative.

Parameters:

• a (_Trop)

• b (_Trop)

Return type:

_Trop

times(a, b, quantizer=None, max_fine_bucket=None)

Compose independent witnesses by adding scores.

Parameters:

• a (_Trop)

• b (_Trop)

• quantizer (Quantizer | None)

• max_fine_bucket (int | None)

Return type:

_Trop

product(elements, quantizer=None, max_fine_bucket=None)

Compose an n-ary collection of tropical carriers.

Parameters:

• elements (Sequence[_Trop])

• quantizer (Quantizer | None)

• max_fine_bucket (int | None)

Return type:

_Trop

best_first_union(streams, log_offsets, exact_log_density, tol=1.0e-10)

Enumerate the union of sorted streams with overlapping supports.

Candidate values are pulled from the streams (stream k shifted by log_offsets[k]), de-duplicated via freeze, re-scored exactly with exact_log_density, and buffered until their exact score is at least the upper bound on any not-yet-seen value: logsumexp_k(log_offsets[k] + head_lp_k). This is the mixture algorithm: any unseen x satisfies p_k(x) <= head_k for every k, hence sum_k w_k p_k(x) <= exp(bound).

Parameters:

• streams (Sequence[BufferedStream])

• log_offsets (Sequence[float])

• exact_log_density (Callable[[Any], float])

• tol (float)

Return type:

Iterator[tuple[Any, float]]

merge_enumerators(streams, offsets)

Lazy k-way merge of sorted (value, log_prob) streams with per-stream offsets.

Stream k’s log probs are shifted by offsets[k]. Correct only when the streams have pairwise disjoint supports (no de-duplication or re-scoring is performed).

Validated eagerly at call time, before any stream is touched: offsets must have exactly one entry per stream, and every offset must be finite or exactly -inf – the sentinel for “this stream contributes nothing” (e.g. a zero-weight mixture component), which excludes that stream entirely without ever opening its iterator. NaN and +inf offsets are rejected outright, since neither has a sensible reading as a log-probability shift. This function is a thin eager-validation wrapper; the actual merge runs in the generator it returns, so a malformed call raises immediately instead of on first iteration.

Each stream’s own items are validated lazily – one pull at a time, as they are actually consumed, so this is safe for infinite streams and never reads ahead: a non-finite log_prob (including -inf – a properly-formed descending stream should already exclude impossible/zero-probability items, matching the convention used elsewhere in this package, e.g. best_first.py’s if lp > -np.inf guards) raises immediately, and so does a log_prob that exceeds the previous log_prob pulled from that SAME stream – i.e. the stream failing the k-way merge’s fundamental precondition of actually being sorted descending.

Parameters:

• streams (Sequence[Iterator[tuple[Any, float]]])

• offsets (Sequence[float])

Return type:

Iterator[tuple[Any, float]]

class ProductEnumerator(streams, combine=tuple, offset=0.0)

Bases: object

Best-first enumeration of the Cartesian product of sorted child streams.

Yields (combine(values), log_prob) with log_prob = offset + sum of child log probs, in non-increasing order. Standard k-best lattice search: a max-heap over index tuples, with successors advancing one coordinate; correctness follows from each child stream being sorted (coordinate-wise monotonicity).

Duplicate-free successor rule: each heap entry carries the lowest coordinate it is allowed to advance, and a node only spawns successors for coordinates at or above that index. Every tuple is then reached by exactly one path – the one that increments coordinates in non-decreasing index order – so no visited set (and no O(n) per-successor tuple hashing) is needed. Best-first order is preserved because each successor’s score is <= its generating node’s (a sorted coordinate only decreases when advanced), so canonical edges are score-monotone.

Parameters:

• streams (Sequence[BufferedStream])

• combine (Callable[[tuple[Any, ...]], Any])

• offset (float)

sound_top_k(dist, k, start=0, budget_bits=40.0, oversample=8, bin_width_bits=1.0, max_budget_bits=512.0, total_mass=1.0, tol=1.0e-12)

Exact true-descending observations ranked [start, start+k) for ANY normalized model.

Mass-threshold certificate, correct regardless of the seek stream’s ordering (so it holds for deep/nested mixtures and HMMs where the tropical order is badly displaced): pull distinct (value, log_prob) from the count-budget index, accumulate probability mass with a provable (never-overstated) lower bound, and keep the best start+k by probability. Since every unpulled item’s probability is at most the remaining mass total_mass - accumulated, once a sound upper bound on remaining drops below the (start+k)-th best probability the heap is exactly the true top start+k; return sorted_desc[start:start+k].

Running out of the in-budget stream is NOT by itself proof the support is exhausted: only a non-truncated index has genuinely covered the entire support, so seeing fewer than start + k distinct values THERE means that many is honestly all there is. A TRUNCATED index only proves “nothing more is visible to this bounded build” – running out of one deepens the budget (doubling up to max_budget_bits) instead of returning the partial prefix as the answer. If even max_budget_bits cannot certify or exhaust, the call fails closed: the returned status is "incomplete" and marked as such rather than silently shaped like a proof (see SoundTopKResult – this is why the return type is a structured result, not a plain list).

total_mass (default 1.0) may be a known upper bound for sub-normalized models; it is trusted as a valid bound on the model’s TRUE total probability mass (this function cannot re-derive a model’s own normalization) but is validated for basic sanity – finite and positive – before use, so a NaN/inf/non-positive caller bug cannot silently corrupt the certificate.

Cost is O(number pulled) – small for peaked distributions, large for flat ones, so for top-k from rank 0 dist.enumerator() is usually leaner; this adds the soundness certificate and the arbitrary start offset the sequential enumerator lacks.

Parameters:

• dist (Any)

• k (int)

• start (int)

• budget_bits (float)

• oversample (int)

• bin_width_bits (float)

• max_budget_bits (float)

• total_mass (float)

• tol (float)

Return type:

SoundTopKResult

class SoundTopKResult(items, status, budget_bits, remaining_mass_bound)

Bases: object

Outcome of sound_top_k(): the found items plus an explicit soundness certificate.

sound_top_k is named and documented as SOUND, so callers must be able to tell a mathematically-certified top-k apart from a best-effort guess it gave up on – unlike a plain list, this always carries the status that earned items.

Parameters:

• items (list[tuple[Any, float]])

• status (Literal['certified', 'exhausted', 'incomplete'])

• budget_bits (float)

• remaining_mass_bound (float)

items

the (value, log_prob) pairs ranked [start, start+k), in descending log_prob order. Fewer than k items only when status == "exhausted" and the distribution’s true support genuinely has fewer than start + k distinct values.

Type:

list[tuple[Any, float]]

status

how items was established.

• "certified" – the mass certificate proved no unseen value can outrank the worst kept item: the accumulated seen mass leaves less than the worst kept item’s own probability unaccounted for. Sound regardless of the count-budget index’s internal seek order (deep/nested mixtures and HMMs included).

• "exhausted" – the count-budget index was NOT truncated, i.e. it covers the distribution’s entire true support, so items is exact by construction: nothing was left unseen for the certificate to reason about.

• "incomplete" – max_budget_bits was reached before either certificate above could be established. items is a best-effort prefix of whatever the search had found – NOT proven to be the true top-k. Callers that require soundness must treat this as a failure (retry with a larger max_budget_bits, or fall back to exact enumeration) rather than silently trusting items.

Type:

Literal[‘certified’, ‘exhausted’, ‘incomplete’]

budget_bits

the final (possibly doubled) count-budget-index budget used to produce items.

Type:

float

remaining_mass_bound

a conservative upper bound on the probability mass of every value not in items – never smaller than the truth, even accounting for floating-point rounding (see _fold_mass_lower_bound()). Certifies "certified" results (strictly less than the worst kept item’s probability); left at total_mass (a trivial but valid bound) when the heap never reached start + k items.

Type:

float

property sound: bool

True when items is a proven-correct top-k (status is not "incomplete").

quantized_best_first_decode(next_logprobs=None, eos=None, max_len=None, top_k=None, top_p=None, bucket_bits=12, batch_next_logprobs=None, batch_size=64, start=(), max_results=None, min_mass=None)

Fast descending-probability sequence enumeration specialized for neural / transformer decoders.

Three structure-aware accelerations over best_first_decode():

1. Nucleus / top-k pruning. Neural next-token distributions are sharply peaked, so each step is restricted to its top_k tokens or its top_p nucleus – dropping the long low-probability tail collapses the branching factor (a ~50k vocab down to a handful) at negligible mass loss.

2. Quantized bucket priority queue. Cumulative log-probs only decrease, so instead of an O(log n) comparison heap the frontier is bucketed by quantized score (bucket = floor(score * 2**bucket_bits)) and drained highest-bucket first – O(1) pushes/pops, and prefixes of near-equal score are grouped. Buckets are disjoint score ranges, so order is exact across buckets and within ~2**-bucket_bits inside one.

3. Batched scoring. The cost is dominated by model forward passes. Pass batch_next_logprobs to score up to batch_size frontier prefixes in one call (one padded GPU forward) instead of one at a time.

With top_k=top_p=None and a large bucket_bits this reduces to the exact enumeration; pruning is the only approximation (report min_mass to stop once enough probability is covered).

Parameters:

• next_logprobs (Callable[[tuple], Iterable[tuple[Any, float]]] | None) – next_logprobs(prefix) -> [(token, log_prob), ...] (used when batch_next_logprobs is not given). Log-probs must be <= 0.

• eos (Any) – end-of-sequence token (a prefix ending in eos is complete).

• max_len (int | None) – maximum sequence length. Give eos and/or max_len.

• top_k (int | None) – keep only the top_k highest-probability tokens per step.

• top_p (float | None) – keep the smallest set of tokens per step whose probability sums to >= top_p (nucleus).

• bucket_bits (int) – score-quantization resolution; larger = finer ordering, slower bookkeeping. Must be an integer in [0, 1023] (so 2**bucket_bits is a finite float).

• batch_next_logprobs (Callable[[list[tuple]], list[Iterable[tuple[Any, float]]]] | None) – optional batch_next_logprobs([prefix, ...]) -> [[(token, log_prob), ...], ...] scoring a batch of prefixes in one forward pass. MUST return exactly one step table per requested prefix, in the same order – a short or long return is a caller bug and raises ValueError naming the mismatch, rather than silently pairing up (and dropping) prefixes with zip().

• batch_size (int) – number of frontier prefixes expanded per (batched) scoring call. Must be a positive integer – a non-positive value previously could take an empty slice of a non-empty bucket without consuming it, hanging the search forever (MXR-080-0227).

• start (tuple) – initial prefix.

• max_results (int | None) – stop after this many complete sequences. Must be a positive integer when given.

• min_mass (float | None) – stop once the yielded sequences cover at least this much probability mass. Must be a finite value >= 0.0 when given.

Yields:

(sequence_tuple, total_log_prob), highest probability first (exact across score buckets).

Raises:

ValueError – for any invalid control (batch_size, bucket_bits, max_results, min_mass, top_k, top_p), or if a batched callback returns a different number of step tables than prefixes requested.

Return type:

Iterator[tuple[tuple, float]]

best_first_decode(next_logprobs, eos=None, max_len=None, start=(), heuristic=None, max_results=None)

Exactly enumerate an autoregressive model’s sequences in descending total log-probability.

Parameters:

• next_logprobs (Callable[[tuple], Iterable[tuple[Any, float]]]) – next_logprobs(prefix) returns an iterable of (token, log_prob) continuations of prefix (e.g. the log-softmax of a transformer’s next-token logits). Log-probs must be <= 0 (NaN or positive values are rejected with ValueError – see below).

• eos (Any) – end-of-sequence token; a prefix whose last token is eos is complete (and not extended).

• max_len (int | None) – maximum sequence length; a prefix of this length is complete. At least one of eos / max_len should be given or enumeration may not terminate.

• start (tuple) – the initial prefix (default empty).

• heuristic (Callable[[tuple], float] | None) – optional admissible upper bound on the remaining log-probability from a prefix (e.g. remaining_steps * max_step_logprob); tightens the search. Omit for the exact h=0 search.

• max_results (int | None) – stop after this many complete sequences.

Yields:

(sequence_tuple, total_log_prob) in nonincreasing total log-probability.

Raises:

ValueError – if next_logprobs returns a NaN or positive log-probability. Unlike the fully generic best_first(), this function’s whole exactness claim rests on every step’s log-prob being <= 0 (see the module docstring), so that contract IS validated here, at the point each continuation is consumed – a caller’s scoring bug (e.g. passing raw logits instead of a log-softmax) fails loudly instead of silently shipping results that are labeled exact but are not.

Return type:

Iterator[tuple[tuple, float]]

beam_search(next_logprobs, beam_width, eos=None, max_len=None, start=(), num_results=None)

Approximate top sequences of an autoregressive model by beam search.

Keeps at most beam_width live prefixes per step (the highest-scoring ones); a prefix that emits eos or reaches max_len is finalized. Returns the finalized sequences sorted by total log-probability. This is the standard heuristic decode – faster than exact best-first but not guaranteed to return the true top-k.

Parameters:

• next_logprobs (Callable[[tuple], Iterable[tuple[Any, float]]]) – next_logprobs(prefix) -> [(token, log_prob), ...] (see best_first_decode).

• beam_width (int) – number of prefixes kept per step.

• eos (Any) – end-of-sequence token (optional).

• max_len (int | None) – maximum length (optional, but recommended to bound the search).

• start (tuple) – the initial prefix.

• num_results (int | None) – number of sequences to return (default beam_width).

Returns:

A list of (sequence_tuple, total_log_prob) sorted by nonincreasing log-probability.

Return type:

list[tuple[tuple, float]]

top_k_scored(candidates, score, k=None)

Return a finite candidate set scored by score, sorted in descending score.

For a classifier: candidates are the class labels and score is lambda c: model.log_prob(c | x).

Parameters:

• candidates (Iterable[Any]) – a finite iterable of candidate outputs.

• score (Callable[[Any], float]) – the (log-)score of a candidate.

• k (int | None) – keep only the top k (uses a bounded heap); None returns all, sorted. Must be a positive integer when given – heapq.nlargest silently returns [] for k <= 0, which reads as “no candidates qualify” rather than the caller-bound error it actually is.

Returns:

A list of (candidate, score) in nonincreasing score.

Return type:

list[tuple[Any, float]]

class AutoregressiveEnumerable(next_logprobs, max_len=None, eos=None, max_depth=1024, bin_width_bits=1.0, oversample=8, batch_next_logprobs=None, batch_size=256, count_mode='auto', branch_cap=None, batch_score_sequences=None, all_position_logprobs=None)

Bases: object

Adapter: an autoregressive next_logprobs(prefix) model as a count-/rank-/unrank-able object.

The support depends on the model. A fixed-length model (max_len set, no eos) has support on every length-max_len sequence. A terminating model (eos set) has support only on sequences that end in eos – so the enumeration counts/ranks/unranks exactly those, of any length, bounded by the probability budget (a tight terminating model has finitely many sequences above any threshold). A length bound is NOT the support boundary there: an un-terminated truncation has zero mass as an output and is never counted. max_depth is only a safety cap on recursion for non-tight models.

Parameters:

• next_logprobs (Callable[[tuple], Iterable[tuple[Any, float]]]) – next_logprobs(prefix) -> [(token, log_prob), ...] – the next-token log-probabilities (<= 0) given a prefix tuple, e.g. the log_softmax of a transformer’s next-token logits. For speed it may instead return the (tokens, log_probs) numpy-array pair (skips per-token boxing). For a terminating model eos must be one of the tokens it can return.

• max_len (int | None) – for a fixed-length model, the sequence length (the support is all length-max_len sequences). Omit for a terminating model (or pass it as a hard length cap, but un-terminated truncations are still dropped). An exact positive integer (or None) – a fractional value raises rather than silently truncating.

• eos (Any) – end-of-sequence token. When given, the model is terminating: only sequences ending in eos are in the support.

• max_depth (int) – safety bound on recursion depth for a terminating model (the probability budget is the real bound). Raise it if a tight model legitimately produces very long sequences. An exact positive integer – a fractional or non-positive value raises.

• bin_width_bits (float) – quantization resolution of the count index (finer = exacter ordering, more memory). The defaults match the distribution count-DP. Ordering from unrank/slice (via seek_index()) is exact between fine buckets (width bin_width_bits / oversample bits) but NOT guaranteed within one – see slice(). Sequences whose log_density differs by less than one bucket’s width can surface in either relative order; this is most visible when several near-tied candidates cluster at the head of a small/short-sequence model. Raise oversample or lower bin_width_bits to shrink it. oversample is an exact positive integer – a fractional or non-positive value raises.

• oversample (int) – quantization resolution of the count index (finer = exacter ordering, more memory). The defaults match the distribution count-DP. Ordering from unrank/slice (via seek_index()) is exact between fine buckets (width bin_width_bits / oversample bits) but NOT guaranteed within one – see slice(). Sequences whose log_density differs by less than one bucket’s width can surface in either relative order; this is most visible when several near-tied candidates cluster at the head of a small/short-sequence model. Raise oversample or lower bin_width_bits to shrink it. oversample is an exact positive integer – a fractional or non-positive value raises.

• batch_next_logprobs (Callable[[list[tuple]], list[Any]] | None) – optional batch_next_logprobs([prefix, ...]) -> [result, ...] scoring many prefixes in one (padded) forward. When given, the count index warms its forward cache breadth-first in batch_size chunks – the large speed-up for transformers, where one-at-a-time forwards dominate (e.g. distilGPT-2 length-2 to rank 1e5: ~25 s one-at-a-time -> ~1 s batched). Each chunk’s results must exactly match the chunk’s own size – a short or long result raises rather than silently dropping/ignoring the mismatch (MXR-080-0223).

• batch_size (int) – prefixes per batched forward. An exact positive integer – a fractional or non-positive value raises.

• count_mode (str) – how counts are carried past the int64-exact regime (budgets over ~2**60 sequences). 'auto' (default) switches the numpy fast path to float64 there – approximate counts (exact below 2**53, ~1e-16 relative error per pooling beyond) at full numpy speed. 'exact' preserves arbitrary-precision counts by falling back to the slow Python recursion. 'float' forces float64 everywhere.

• branch_cap (int | None) – recurse into only the top-branch_cap in-budget tokens per prefix – the certified approximation for wide (LLM-sized) vocabularies, shrinking the tree by ~V/cap per level. The skipped remainder is soundly bounded (count_bracket/dropped_upper: a skipped subtree with r remaining budget bits holds at most 2**r completions); enumeration covers the sub-support of sequences whose every token is among its context’s top-branch_cap. An exact positive integer (or None) – a fractional value raises rather than silently truncating.

• batch_score_sequences (Callable[[list[tuple]], Any] | None) – optional teacher-forcing scorer [sequence, ...] -> array of total log-probs – ONE forward per sequence (all positions score in parallel) instead of one forward per token. Used by score_sequences() and, when a sequence’s prefixes are not already cached, by log_density(); the substrate for draft-rescored (speculative) enumeration. Must return exactly one score per (in-support) sequence requested – a short or long result raises (MXR-080-0223).

• all_position_logprobs (Callable[[tuple], list[Any]] | None) – optional sequence -> [next_logprobs result for seq[:d], d in 0..len-1] – one forward yields the full next-token distribution at EVERY position; harvested into the forward cache by harvest(). Makes corpus-calibrated envelopes ~L-times cheaper. Must return exactly one result per position – a short result raises rather than silently leaving some positions uncached (MXR-080-0223).

The model is queried lazily and memoized by prefix, so deepening the index (or recomputing a log-density) never re-runs a forward pass it has already seen. With integer tokens the histogram build is the numpy fast path (int64 counts below ~``2**60`` budgets; float64 beyond, per count_mode).

quantized_count_index(quantizer, max_fine_bucket)

Count index over the model’s support (length-max_len sequences, or all eos-terminated sequences), bounded by the bit budget max_fine_bucket.

Parameters:

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

tuple[CountIndex, bool]

log_density(sequence)

Exact total log-probability of a sequence – -inf if it is off the model’s DECLARED support (wrong length, missing/misplaced eos, or past the depth cap; see _in_declared_support()) or if any token along the way is locally unavailable given its prefix.

When a batch_score_sequences scorer is configured and any of the sequence’s prefixes is not already cached, the score comes from ONE teacher-forcing forward instead of one forward per token. The scorer’s returned cardinality is validated (exactly one score for the one sequence requested) before it is trusted – see score_sequences()’ own note (MXR-080-0223).

Parameters:

sequence (Iterable[Any])

Return type:

float

score_sequences(sequences)

Exact total log-probabilities of many sequences – batched teacher forcing when available.

With batch_score_sequences this is one call scoring every structurally in-support sequence (one forward per sequence, all positions in parallel); a sequence off the declared support (see _in_declared_support()) scores -inf directly, without ever reaching the external scorer. The scorer’s returned cardinality is then validated – exactly one score per in-support sequence sent to it – before it is trusted (MXR-080-0223); a short or long result raises rather than silently misaligning or dropping scores. Otherwise falls back to per-sequence log_density() over the cached walk, which applies the identical structural check. The rescoring primitive for draft-based (speculative) enumeration.

Parameters:

sequences (list[Any])

Return type:

ndarray

harvest(sequence)

Cache the next-token distribution at every prefix of sequence from one forward.

Requires all_position_logprobs; a no-op without it. Feeding typical sequences (a corpus, a provider’s fast generations) through this warms the same memo cache the count index and the envelope read – L cache entries per model call.

The result must carry exactly one entry per position (MXR-080-0223): a short result used to be silently accepted by slicing to results[:len(seq)], leaving the un-covered tail of prefixes uncached with no signal that coverage was incomplete. That is validated – and any cache mutation withheld – before anything is written.

Parameters:

sequence (Iterable[Any])

Return type:

None

structural_fine_bucket(sequence, quantizer)

Return the quantized fine bucket for a sequence log density.

Parameters:

• sequence (Iterable[Any])

• quantizer (Quantizer)

Return type:

int

sampler(seed=None)

Return an autoregressive sampler.

Parameters:

seed (int | None)

Return type:

_ARSampler

enumerator()

A descending-probability iterator over the support (lazy best-first); use top_k for the head.

seek_index(*, max_depth_bits=4096.0)

The cached persistent SeekIndex over this model.

Built lazily on first use and reused by every convenience query (unrank / count / threshold / mass_above), deepening in place when a query needs more depth – so a sweep of a thousand unranks pays for one tree build, not a thousand. The forward cache is shared with it, so deepening only runs new forwards for newly-live prefixes.

max_depth_bits is reconciled on every call, not just honored on the first (MXR-080-0225): a later call requesting a GENUINELY DEEPER cap raises the cached index’s own ceiling in place – SeekIndex already deepens its build lazily on demand, so widening the ceiling is enough; nothing already built is discarded or rebuilt. A later call requesting a smaller-or-equal cap is a no-op: the cached index already satisfies it, and lowering an already-built ceiling would only forbid further deepening the index could otherwise still do, for no benefit. Previously the FIRST call’s cap was silently permanent – a later, larger cap returned the same object with the old, too-small ceiling still in effect, so query results silently depended on unrelated call order.

Parameters:

max_depth_bits (float)

budget_index(budget_bits, max_depth_bits=4096.0)

The count-budget seek index covering at least 2**budget_bits sequences (for unrank/iterate).

Parameters:

• budget_bits (float)

• max_depth_bits (float)

envelope_index(*, n_paths=64, seed=0, budget_bits=64.0)

An AREnvelopeIndex over this model – approximate enumeration at depths the exact tree index cannot reach (O(L) forwards per unrank instead of Theta(count) tree expansion; exact for iid-step models, mean-field estimate otherwise).

Parameters:

• n_paths (int)

• seed (int)

• budget_bits (float)

top_k(k)

The k most probable sequences, exact, by best-first listing (use for small k).

k <= 0 returns [] without starting the best-first listing at all (MXR-080-0224 – checked before any iteration, not after the loop body has already appended one item and only THEN noticed the bound was already satisfied, which used to make top_k(0) return one item instead of none).

Parameters:

k (int)

Return type:

list[tuple[tuple, float]]

count(min_log_prob)

How many sequences have log_density >= min_log_prob – computed from counts, not listed.

With branch_cap set this is the count over the capped sub-support (a sound lower bound); count_bracket() adds the certified upper bound including the skipped remainder.

Parameters:

min_log_prob (float)

Return type:

int | float

count_bracket(min_log_prob)

A sound [lo, hi] bracket on the number of sequences with log_density >= min_log_prob.

lo counts the (exactly enumerated) kept sub-support; hi adds dropped_upper – the certified bound on completions excluded by branch_cap (identical to lo when no cap is set).

Parameters:

min_log_prob (float)

Return type:

tuple[float, float]

unrank(i)

The i-th most probable sequence (0-based, QUANTIZED order) and its exact log-probability.

Random access through the count index, so the ordering carries the index’s quantization (unrank()): exact between fine buckets (width bin_width_bits / oversample bits), unspecified within one – two sequences whose log-probabilities differ by less than a bucket’s width can come back in either relative order, so rank(unrank(i)) can differ from i for near-tied neighbours. The returned log-probability is always exact regardless. Shrink the ambiguity window by raising oversample or lowering bin_width_bits; for a strictly-sorted head use top_k() (exact best-first), and for a sequence’s exact rank use rank().

Parameters:

i (int)

Return type:

tuple[tuple, float]

threshold(rank)

Log-probability of the rank-th most probable sequence – the boundary of the top-rank set.

Read off unrank(), so it inherits the same fine-bucket quantization of the ordering (exact between buckets, unspecified within one); the returned log-probability itself is exact.

Parameters:

rank (int)

Return type:

float

mass_above(min_log_prob)

A (lower, upper) bracket on the total probability of sequences with log_density >= min_log_prob.

Computed from the count histogram alone (no enumeration): each fine bucket of c sequences contributes between c * 2**(-hi_bits) and c * 2**(-lo_bits), where the bucket spans [lo_bits, hi_bits) of information. Tighten by raising oversample.

Parameters:

min_log_prob (float)

Return type:

tuple[float, float]

seek(index)

CountDPSeekResult at descending index (with a bracket).

Parameters:

index (int)

rank(sequence)

DensityRankResult – rank + cumulative mass of a sequence.

Parameters:

sequence (Iterable[Any])

cumulative(sequence)

G(seq) = P(p(Y) >= p(seq)) – total mass of sequences at least as probable as seq.

Parameters:

sequence (Iterable[Any])

nucleus_size(p)

Size of the minimal >= p-mass set (CountDPTopPResult), without materializing it.

Deliberately does NOT delegate to the generic count_dp_top_p(): that function assumes its exact per-item mass histogram (bucketed by the floor of the EXACT total log-density) and its count index share one bucket numbering, which holds for Composite/Record/Sequence but not here – quantized_count_index() buckets a sequence by the SUM of its per-step floor-quantized buckets, and floor(a) + floor(b) <= floor(a + b), so the structural bucket is systematically <= the exact one (same discrepancy mass_above() documents). Looking counts up at the exact-mass bucket key lands on the wrong (usually empty) slot in the count histogram – confirmed: it returns a nucleus size of 0 against a brute-force ground truth of 5. This mirrors mass_above()’s fix instead: every quantity is derived from the SAME structural count histogram, with each bucket’s per-item probability bounded by [2**(-(b + steps_bound) * bpb), 2**(-b * bpb)] (identical bound, same derivation), so the result is a provable bracket rather than an exact mass – the same contract shape count_dp_top_p documents, just derived from bounds instead of a wrongly-keyed exact histogram.

Parameters:

p (float)

autoregressive_count_index(steps, prefix, depth, quantizer, max_fine_bucket, eos=None, branch_cap=None)

Tree-recursive count index over completions of prefix up to depth more tokens.

Returns (CountIndex, truncated). The histogram counts completions by fine bucket of total bits; CountIndex.get_in_bucket(fb, offset) unranks the structural (token, ...) sequence and its exact log-probability. truncated is True if any completion was dropped at the max_fine_bucket depth bound (so a caller can deepen).

Each step’s bits -log2 p(x_t | prefix) are added to every completion bucket via CountHistogram.shift(); the per-token children are pooled with CountHistogram.add(). Because steps are taken in descending probability, once a token’s own bits exceed the remaining budget every later token does too, so the loop can stop – this is what bounds the work to the live prefixes.

branch_cap recurses into only the top-cap in-budget tokens per node – the certified approximation for wide vocabularies. Each skipped token’s subtree is bounded soundly (completions within r remaining bits number at most 2**r, since their conditional probabilities sum to at most 1) and the total accumulates in CountIndex.dropped_upper: the true in-budget count lies in [total(), total() + dropped_upper]. Dropped tokens do NOT set truncated (deepening cannot recover them; raising branch_cap can).

Parameters:

• steps (Callable[[tuple], list[tuple[Any, float]]])

• prefix (tuple)

• depth (int)

• quantizer (Quantizer)

• max_fine_bucket (int)

• eos (Any)

• branch_cap (int | None)

Return type:

tuple[CountIndex, bool]

class AREnvelopeIndex(model, *, n_paths=64, seed=0, budget_bits=64.0, calibration_sequences=None)

Bases: object

Envelope (mean-field) seek index over a fixed-length AutoregressiveEnumerable.

Parameters:

• model (Any) – the autoregressive adapter (max_len set; terminating/eos models are rejected).

• n_paths (int) – contexts sampled per depth for the envelope calibration (more = sharper envelope; the root depth is always exact). The calibration forwards are memoized on the model, so they are shared with any exact index built later.

• seed (int) – calibration sampling seed (the index is deterministic given it).

• budget_bits (float) – initial depth of the suffix tables; queries deepen geometrically as needed.

• calibration_sequences (list[tuple] | None) – optional typical sequences (a corpus, a provider’s fast generations) to calibrate the envelope from INSTEAD of ancestral sampling. Each is harvested through model.harvest – with the all_position_logprobs contract that is ONE forward per sequence for all its per-depth contexts, ~L-times cheaper than sampling token by token.

ensure_bits(depth_bits)

Deepen the suffix tables to cover depth_bits (geometric, low-overhead: L capped convolutions).

Parameters:

depth_bits (float)

Return type:

AREnvelopeIndex

total()

Estimated number of sequences within the built depth (exact for an iid-step model).

Return type:

float

count(min_log_prob)

Estimated number of sequences with log_density >= min_log_prob (mean-field; iid-exact).

Parameters:

min_log_prob (float)

Return type:

float

mass_above(min_log_prob)

A mean-field (lower, upper) estimate of the head mass above min_log_prob.

Same bucket arithmetic as the exact index’s mass_above (each bucket of c sequences holds between c * 2**-hi_bits and c * 2**-lo_bits of mass), applied to the envelope histogram – so the bracket carries the envelope’s estimation error on top of the quantization smear.

Parameters:

min_log_prob (float)

Return type:

tuple[float, float]

unrank(i)

The approximately-i-th most probable sequence and its exact log-probability.

Costs one model forward per step (L total, memoized) – never a tree expansion. The rank coordinate inherits the envelope approximation; the returned sequence and its log-probability are exact model quantities. Raises IndexError past the estimated support size.

i is kept as an exact Python/numpy integer throughout the offset-consumption walk below (MXR-080-0232): the envelope’s bucket counts are themselves an inherently approximate float64 mean-field carrier (see the module docstring and CountHistogram’s exact=False mode), so they cannot be made exact – but i need not be rounded on top of that. The previous target = float(i) silently rounded any rank at or past 2**53 to the nearest representable float64 (e.g. float(2**60 - 1) == float(2**60) exactly), which could reject the last valid rank of a huge support as “beyond the estimated support”, or misroute the offset walk below. Comparing the ORIGINAL exact i against a running float cumulative sum is precise regardless of magnitude (CPython’s int/float < never rounds the int operand); only the cumulative-so-far – already an approximate quantity – is floored to an int at each bucket boundary, so the offset within the chosen bucket is exact int subtraction, never a fresh float rounding of i.

Parameters:

i (int)

Return type:

tuple[tuple, float]

threshold(rank)

Exact log-probability of the sequence the envelope places at rank (approximate boundary).

Parameters:

rank (int)

Return type:

float

rank_bracket(sequence)

Estimated [lo, hi] rank bracket of sequence – its envelope bucket’s rank span.

lo counts the estimated sequences in strictly shallower buckets; hi adds the sequence’s own bucket. Exact for iid-step models; otherwise a mean-field estimate (floats, not certificates).

sequence must have exactly the model’s fixed support length (MXR-080-0232): the suffix tables this walks are built over complete length-self.length outcomes, so a shorter (a locally-valid prefix) or longer sequence is not an outcome the envelope has a rank for at all, even when every individual token transition is locally valid – silently walking it anyway would return a rank-bracket-shaped answer for something that was never a real candidate.

Parameters:

sequence (Any)

Return type:

tuple[float, float]

class LatticeEnvelopeIndex(model, *, n_clusters=None, cluster_fn=None, n_paths=128, seed=0, budget_bits=64.0)

Bases: object

Cluster-conditioned envelope index: the Markov refinement between mean-field and exact.

AREnvelopeIndex averages one envelope per depth – exact only for iid steps. This index conditions each depth’s envelope on the cluster of the last token (cluster_fn): the calibration histograms are kept per (depth, cluster) and split by the next token’s cluster, and the suffix tables become the lattice DP S_d[c] = sum_c' H_d[c][c'] (*) S_{d+1}[c'] – the same shape as HMMPathIndex with clusters as states. The result is exact for any order-1 Markov model whose next-token distribution depends only on (depth, cluster_fn(last token)) – with cluster_fn the identity, that is every last-token Markov model, where the mean-field envelope is provably lossy. Coarser clusterings interpolate: m = 1 recovers mean-field, m = V conditions on the full last token.

Queries mirror AREnvelopeIndex: counts and thresholds off the root table, unrank descends the REAL model apportioning by cluster-conditioned subtree estimates (O(L) forwards), every returned log-probability exact. A (depth, cluster) never visited in calibration borrows the depth’s aggregate envelope (mean-field fallback for that pocket) – raise n_paths to shrink the pockets. Fixed-length models only.

Parameters:

• model (Any)

• n_clusters (int | None)

• cluster_fn (Any)

• n_paths (int)

• seed (int)

• budget_bits (float)

ensure_bits(depth_bits)

Ensure suffix envelopes are deep enough for the requested bit depth.

Parameters:

depth_bits (float)

Return type:

LatticeEnvelopeIndex

total()

Estimated sequences within the built depth (exact for depth+last-cluster Markov models).

Return type:

float

count(min_log_prob)

Estimated number of sequences with log_density >= min_log_prob (Markov-refined estimate).

Parameters:

min_log_prob (float)

Return type:

float

unrank(i)

The approximately-i-th most probable sequence with its exact log-probability.

i is kept as an exact Python/numpy integer throughout the offset-consumption walk below (MXR-080-0232) – see AREnvelopeIndex.unrank() for why: the underlying bucket counts are an inherently approximate float64 carrier, but i itself need not be rounded on top of that by an early float(i) cast, which silently loses unit resolution past 2**53.

Parameters:

i (int)

Return type:

tuple[tuple, float]

threshold(rank)

Return the log-density threshold at a one-based rank.

Parameters:

rank (int)

Return type:

float

rank_bracket(sequence)

Estimated [lo, hi] rank bracket – exact for depth+last-cluster Markov models.

sequence must have exactly the model’s fixed support length (MXR-080-0232) – see AREnvelopeIndex.rank_bracket().

Parameters:

sequence (Any)

Return type:

tuple[float, float]

class RescoredIndex(draft_index, target, *, rerank_window=64, assumed_gap=None)

Bases: object

Draft-ordered, target-scored enumeration with window reranking.

Parameters:

• draft_index (Any) – any index with unrank(i) -> (sequence, draft_log_prob) – a SeekIndex over a low-cost AutoregressiveEnumerable, an AREnvelopeIndex, or anything equivalent. Sound certification additionally requires a .quantizer attribute exposing the Quantizer the index was built with – both accepted index types have one; without it, queries still work but never certify.

• target (Any) – the expensive model – an AutoregressiveEnumerable (its score_sequences() batch scorer is used) or a bare callable [seqs] -> log_probs.

• rerank_window (int) – extra draft candidates pulled around a query and reranked by target score. Larger = more robust to draft/target disagreement, one batched forward either way. Must be a non-negative integer – a negative window used to silently shrink or empty the pulled set while still reporting a falsely certified result (MXR-080-0233).

• assumed_gap (float | None) – optional global bound on |target_lp - draft_lp| (nats). Must be finite and non-negative. When supplied, results carry a genuine certified verdict (see RescoreResult); otherwise certified is None and the observed gap is reported as a diagnostic only.

top_k(k)

The k best sequences by TARGET score among the k + rerank_window draft head.

Returns a RescoreResult – target-exact scores, draft+window-approximate completeness (see the class/module docstrings for exactly what certified proves).

Parameters:

k (int)

Return type:

RescoreResult

slice(start, k)

Target-reranked [start, start + k) slice of the pulled start + k + rerank_window head.

Same semantics as top_k(): order within the pulled set is target-exact; the certificate covers whether an unpulled sequence could belong in (or before) the slice.

Parameters:

• start (int)

• k (int)

Return type:

RescoreResult

unrank(i)

The draft’s rank-i sequence with the TARGET’s exact log-probability.

The rank coordinate is the draft’s (no reranking): the low-cost random-access primitive. Use top_k() / slice() when local target-order matters.

Parameters:

i (int)

Return type:

tuple[tuple, float]

class RescoreResult(items, certified, bound, gap)

Bases: object

Outcome of a RescoredIndex query: target-exact items plus an explicit certificate.

top_k/slice are speculative: the returned items are always target-exact and target-ordered, but completeness (whether some unpulled candidate could outscore them) is only provable under an assumed_gap AND a draft index that can supply a sound bound – a caller that needs the proof, not just a plausible answer, must check certified is True rather than trusting items alone (MXR-080-0233: a bare boolean bolted onto an unqualified value cannot make that distinction).

Parameters:

• items (list[tuple[tuple, float]])

• certified (bool | None)

• bound (float | None)

• gap (float)

items

(sequence, target_log_prob) pairs, target-exact and sorted by target score.

Type:

list[tuple[tuple, float]]

certified

None when no assumed_gap was supplied to the index – certification was never attempted and items is a plausible, uncertified answer. True only when bound was established and the returned set’s worst target score provably clears every unpulled candidate (bound + assumed_gap). False when certification was requested but could not be proven – either the draft index offered no sound bound, or the bound did not clear the gap; items is then still the best-effort draft/window answer, never a proof.

Type:

bool | None

bound

the certified upper bound on any unpulled candidate’s draft log-probability that the certificate was checked against, or None when no bound applies – nothing was left unpulled (the draft support was exhausted), no assumed_gap was supplied, or the draft index could not supply a sound bound.

Type:

float | None

gap

running max observed |target_lp - draft_lp| over everything rescored on this index so far – a diagnostic of what the gap has actually been, never a certificate.

Type:

float

hmm_best_paths(log_pi, log_A, log_b, k=None)

Enumerate HMM state paths in nonincreasing joint log-probability.

Parameters:

• log_pi (ndarray) – (K,) log initial-state distribution.

• log_A (ndarray) – (K, K) log transition matrix (row j -> column k is log p(z_t=k | z_{t-1}=j)).

• log_b (ndarray) – (T, K) per-position emission log-likelihoods log p(x_t | z_t=k).

• k (int | None) – stop after the k best paths; None enumerates all K**T lazily.

Yields:

(path, joint_log_prob) with path a length-T tuple of state indices, highest first. The first yield is the Viterbi (MAP) path.

Return type:

Iterator[tuple[tuple[int, …], float]]

class HMMPathIndex(log_pi, log_A, log_b, *, bin_width_bits=1.0, oversample=8, budget_bits=None)

Bases: object

Quantized random-access index over an HMM’s state paths for one observation sequence.

log_pi/log_A/log_b are validated at construction (MXR-080-0228): shapes must be (K,)/(K, K)/(T, K) with a consistent K, every score must be finite-or-impossible (-inf, never NaN or +inf), and log_pi/log_A must describe at most one unit of total probability each (sub-stochastic rows – e.g. from forbidding individual transitions without renormalizing – are allowed; log_b is an emission LOG-LIKELIHOOD and may be positive/unnormalized – see hmm_best_paths()). An all-impossible initial vector or a position with no finite score at all is not an error: it is represented explicitly via empty_support (and total() reporting a certified zero), rather than crashing.

Precompute (once, O(T * K^2 * W)): quantize every step score – log_pi[s] + log_b[0, s] and log_A[s, s'] + log_b[t, s'], one floor per step so the accumulated smear is at most T fine buckets – and run a forward count DP: C_t[s'] is the histogram, over integer total-score buckets, of the number of length-t+1 prefixes ending in state s'. Counts are EXACT Python arbitrary-precision integers, never float64 (MXR-080-0229): the number of paths is K**T, which exceeds float64’s 2**53 exact-integer range for even modest T, and every operation this DP performs on a count is addition – no rounding is ever actually needed here.

Query (each O(T * K)): unrank(i) walks the stored tables backward – pick the final state whose bucket count covers the offset, then repeatedly the predecessor whose shifted prefix bucket does – returning the i-th best path by quantized score and its exact joint log-probability, exactly for any i within the built support. total / count / mass_above read the pooled final histogram and report a CertifiedCount / CertifiedMassBound: a query that reaches beyond a truncated index’s built budget gets a sound bound with certified=False rather than a bare number indistinguishable from a complete answer (MXR-080-0230).

Ordering contract: paths are ordered by their quantized bucket (width bin_width_bits/oversample bits); within a bucket the order is deterministic but unspecified – exactly the count-index semantics elsewhere in mixle.enumeration. hmm_best_paths() remains the exact-order tool for the head; this index is the random-access tool for depth (rank 1e6 costs one table walk, not 1e6 A* expansions).

Parameters:

• log_pi (np.ndarray)

• log_A (np.ndarray)

• log_b (np.ndarray)

• bin_width_bits (float)

• oversample (int)

• budget_bits (float | None)

bucket_of(log_joint)

The index’s bucket frame for a true joint score (bits behind the per-position optimum).

Parameters:

log_joint (float)

Return type:

int

total()

Number of state paths within the budget (== K**T when nothing truncated; exact integer count).

certified is False when the index is truncated: value is then only a sound LOWER bound on the true number of paths – some paths exceed the built budget and were never counted (MXR-080-0230). Deepen budget_bits (or omit it for the default, which is sized to cover every finite-score path) to certify a larger/complete total.

Return type:

CertifiedCount

count(min_log_joint)

How many paths have quantized joint log-probability at least min_log_joint.

Counts every true qualifier (the structural bucket never over-states a path’s bits) plus at most the paths within the T-floor smear band below the threshold – this ordinary quantization smear applies regardless of certified.

certified is True whenever this query’s own bucket stays within the built budget: bucket costs only accumulate along a path (never decrease), so every bucket the index does hold is a complete, exact count regardless of the index’s global truncated flag. It is False only when the query needs to look beyond the built budget on a genuinely truncated index (MXR-080-0230): value is then a sound LOWER bound (every indexed path is a real qualifier), not the complete answer – more qualifying paths may live beyond the budget.

Parameters:

min_log_joint (float)

Return type:

CertifiedCount

mass_above(min_log_joint)

A bracket on the total joint probability/density of paths above the threshold.

Bucket arithmetic with the T-floor smear: a path in bucket b carries between exp(total_offset) * 2**-((b + T) / fpb) and exp(total_offset) * 2**-(b / fpb) of joint mass (the offset restores the per-position shift, so unnormalized emission likelihoods work).

certified follows the same rule as count(): True unless this query reaches beyond the built budget on a truncated index. When not certified, lower remains a sound bound (unindexed paths can only add mass) but upper is replaced with math.inf – the in-budget figure is not a valid upper bound once qualifying mass may exist beyond the budget, so reporting it as one would be unsound, not just imprecise (MXR-080-0230).

Parameters:

min_log_joint (float)

Return type:

CertifiedMassBound

unrank(i)

The i-th best state path by quantized score (0-based) and its exact joint log-probability.

One backward table walk – O(T * K) – regardless of how deep i is. Every table read along the walk is an exact Python int (MXR-080-0229), so i resolves exactly for supports far beyond float64’s 2**53 exact-integer range – adjacent ranks never alias to the same stored offset the way they would under float64 accumulation.

Parameters:

i (int)

Return type:

tuple[tuple[int, …], float]

threshold(rank)

Exact joint log-probability of the rank-th best (quantized-order) path.

Parameters:

rank (int)

Return type:

float

iter_paths(start=0)

Iterate paths from quantized rank start (sequential unranks over the stored tables).

Parameters:

start (int)

Return type:

Iterator[tuple[tuple[int, …], float]]

class CertifiedCount(value, certified)

Bases: object

A path count from HMMPathIndex, honest about whether it is the complete answer.

HMMPathIndex is built to a finite quantized-bucket budget; when a query needs to look beyond that budget on a genuinely truncated index, the stored tables cannot answer it exactly – paths beyond the budget were never counted. Returning the in-budget count as a bare number would look identical to a complete answer with no way to tell the two apart (MXR-080-0230); this return type makes the distinction explicit instead.

Parameters:

• value (int)

• certified (bool)

value

the count of indexed (in-budget) paths satisfying the query. Always a sound LOWER bound on the true count – every path counted here genuinely qualifies, so this can only under-, never over-, state the truth. Exact (up to the ordinary quantization smear documented on HMMPathIndex.count(), unrelated to truncation) when certified.

Type:

int

certified

True when value is provably the complete answer – no path beyond the built budget could also qualify. False when the query reaches beyond the built budget on a truncated index, so additional qualifying paths may exist beyond value.

Type:

bool

class CertifiedMassBound(lower, upper, certified)

Bases: object

A joint probability/density mass bracket from HMMPathIndex.mass_above().

Parameters:

• lower (float)

• upper (float)

• certified (bool)

lower

sound lower bound on the true mass above the threshold. Valid regardless of certified – paths beyond a truncated budget can only ADD mass, never invalidate a lower bound derived purely from the paths this index actually has.

Type:

float

upper

sound upper bound when certified; math.inf when not. A truncated index’s stored histogram cannot certify any FINITE upper bound on mass that might live beyond the built budget without deepening it – reporting the in-budget figure anyway would be an unsound bound wearing a sound bound’s shape (MXR-080-0230).

Type:

float

certified

True when both bounds are provably sound answers to the exact query; False when the threshold reaches beyond the built budget on a truncated index.

Type:

bool

Subpackages

• mixle.enumeration.quantization package
  • Submodules
    • mixle.enumeration.quantization.core module
    • mixle.enumeration.quantization.parallel module
    • mixle.enumeration.quantization.seek module
    • mixle.enumeration.quantization.semiring module

Submodules

• mixle.enumeration.algorithms module
• mixle.enumeration.assignment module
• mixle.enumeration.autoregressive module
• mixle.enumeration.best_first module
• mixle.enumeration.density_rank module
• mixle.enumeration.envelope module
• mixle.enumeration.hmm_paths module
• mixle.enumeration.model_enumeration module
• mixle.enumeration.rescore module
• mixle.enumeration.seek_index module
• mixle.enumeration.spanning module
• mixle.enumeration.streams module