mixle.enumeration.quantization.core module

Structural quantized enumeration: count the support without enumerating it.

The smart-enumeration index (see mixle.enumeration.algorithms and mixle.stats.compute.pdist.DistributionEnumerator) is a seek structure over a distribution’s exact descending-probability enumeration: it precomputes how many support values fall in each quantized log-probability bin so that an arbitrary rank can be resolved and unranked without walking the prefix.

For exponential-support families (sequences, Markov chains, …) the number of values within a probability budget is astronomically large, so the index must be built from per-bin counts computed structurally – by quantizing and binning the complete model probability Q(ln p(x)) and lifting the model’s own likelihood recursion into a count/histogram semiring – never by materializing the domain.

This module provides that semiring:

• Quantizer maps an exact log_prob to a fine integer bucket of accumulated bits and a coarse output bin.

• CountHistogram is the semiring value: counts indexed by fine bucket, with shift (add a constant log-prob term), convolve (independent additive composition), power (L-fold self-convolution), and add (pool alternatives). Counts are exact Python integers and may exceed 2**128.

• CountIndex pairs a histogram with a structural unranker get_in_bucket(fine_bucket, offset) -> (value, exact_log_prob).

• leaf_count_index() builds a CountIndex from any exact enumerator, bounded by depth (cheap for small/closed-form leaves).

• convolve_indices() composes child indices (the Composite reference case), and build_budget_index() accumulates coarse bins until the cumulative count reaches the requested 2**budget_bits budget, returning a mixle.enumeration.algorithms.LazyQuantizedEnumerationIndex.

The bin assignment is the only approximation (intermediate fine-bucket rounding shifts items by at most num_terms / oversample coarse bins); the value set, total count, and the exact log probability of every unranked item are exact, because the unranker returns the value and the index re-evaluates log_density on it.

class Quantizer(bin_width_bits=1.0, oversample=8, executor=None, count_mode='exact')

Bases: object

Maps exact log probabilities to fine buckets and coarse bins.

bits(x) = -log2 p(x) >= 0. The fine bucket is floor(bits * oversample / bin_width); the coarse bin is fine_bucket // oversample, which equals floor(bits / bin_width) for a single value (so leaf coarse bins match the existing QuantizedEnumerationIndex convention). oversample (R) controls how finely accumulated log-probabilities are tracked through convolutions, bounding the requantization error.

Parameters:

• bin_width_bits (float)

• oversample (int)

• count_mode (str)

bin_width_bits

oversample

executor

count_mode

convolve(a, b, max_fine_bucket=None)

Convolve two histograms, using the attached parallel executor when present.

Parameters:

• a (CountHistogram)

• b (CountHistogram)

• max_fine_bucket (int | None)

Return type:

CountHistogram

bits(log_prob)

Information content -log2 p in bits (>= 0).

Parameters:

log_prob (float)

Return type:

float

fine_bucket(log_prob)

Fine integer bucket of a log probability.

Parameters:

log_prob (float)

Return type:

int

coarse_bin(fine_bucket)

Coarse output bin containing a fine bucket.

Parameters:

fine_bucket (int)

Return type:

int

fine_per_bit()

Fine buckets per bit of information.

Return type:

float

class CountHistogram(base, data)

Bases: object

Counts of support values indexed by fine bucket of accumulated bits.

data[i] is the (exact, possibly huge) number of values whose fine bucket is base + i. The histogram is dense over [base, base + len(data)) with implicit zeros outside. This is the value type of the count semiring.

Parameters:

• base (int)

• data (list[int])

base

data

classmethod empty()

Return type:

CountHistogram

classmethod delta(fine_bucket, count=1)

A single bucket with the given count (the multiplicative identity when count=1, bucket=0).

Parameters:

• fine_bucket (int)

• count (int)

Return type:

CountHistogram

is_empty()

Return type:

bool

total()

Return type:

int

max_bucket()

Return type:

int | None

count_at(fine_bucket)

Parameters:

fine_bucket (int)

Return type:

int

shift(k)

Return a copy with every bucket moved by k (adds a constant log-prob term).

Parameters:

k (int)

Return type:

CountHistogram

truncate(max_fine_bucket)

Drop buckets strictly beyond max_fine_bucket (depth bound).

Parameters:

max_fine_bucket (int)

Return type:

CountHistogram

add(other)

Pointwise sum (pool of mutually exclusive alternatives, e.g. different lengths).

Parameters:

other (CountHistogram)

Return type:

CountHistogram

convolve(other, max_fine_bucket=None, bucket_delta_bits=None)

Discrete convolution: counts of sums of two independent additive log-prob terms.

Optionally drop output buckets beyond max_fine_bucket during accumulation so a depth bound keeps the histogram width fixed regardless of how large the counts grow.

Three backends produce identical results: a direct double loop for small operands, a vectorized multi-prime number-theoretic transform (_convolve_ntt()) when every KEPT output coefficient provably fits the prime ladder’s CRT capacity (bucket_delta_bits — the quantizer’s bits-per-fine-bucket pitch — lets the measured-envelope bound engage; see _kept_coeff_bound()), and Kronecker substitution (_convolve_kronecker()) otherwise. The latter packs each integer histogram into a single big integer and multiplies once, pushing the inner loop into CPython’s sub-quadratic big-integer multiply – exact for arbitrarily large counts (they can exceed the ladder’s ~2^207, so an unchecked floating-point FFT is never an option).

Parameters:

• other (CountHistogram)

• max_fine_bucket (int | None)

• bucket_delta_bits (float | None)

Return type:

CountHistogram

convolve_float(other, max_fine_bucket=None)

Approximate convolution carrying counts as float64 – the quantized-counting fast path.

One numpy.convolve() at C speed replaces the exact big-integer machinery. Counts are exact while they stay below 2**53 (float64 integers) and carry a relative error of at most ~width * 2**-53 per convolution beyond that – negligible against the bin-assignment approximation the count-DP already makes. Counts above ~2**1000 would overflow float64, so such results fall back to the exact backend (the histograms are identical below the cliff).

Parameters:

• other (CountHistogram)

• max_fine_bucket (int | None)

Return type:

CountHistogram

class CountIndex(hist, getter, dropped_upper=0.0)

Bases: object

A fine-bucket count histogram paired with a structural unranker.

get_in_bucket(fine_bucket, offset) returns (value, exact_log_prob) for the offset-th value (0-based) whose fine bucket is fine_bucket. The ordering within a bucket is deterministic but otherwise unspecified.

Parameters:

• hist (CountHistogram)

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

• dropped_upper (float)

hist

dropped_upper

total()

Return type:

int

get_in_bucket(fine_bucket, offset)

Parameters:

• fine_bucket (int)

• offset (int)

Return type:

tuple[Any, float]

leaf_count_index(enum, quantizer, max_fine_bucket, max_items=None)

Build a CountIndex from an exact descending-probability enumerator, bounded by depth.

Pulls items until their fine bucket exceeds max_fine_bucket (or, if max_items is given, until that many items have been taken). Cheap for closed-form or small-support leaves (a geometric/Poisson has ~depth items within a depth bound); the max_items cap is the brake for the enumerate-and-bin fallback over exponential-support families that cannot count structurally. Returns (index, truncated) where truncated is True if in-bound items were left untaken.

Parameters:

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

• quantizer (Quantizer)

• max_fine_bucket (int)

• max_items (int | None)

Return type:

tuple[CountIndex, bool]

child_count_index(child, path, quantizer, max_fine_bucket)

Build child.quantized_count_index(…), annotating EnumerationError with the child’s path.

Parameters:

• path (str)

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

tuple[CountIndex, bool]

convolve_indices(children, quantizer, max_fine_bucket)

Compose independent child indices into their additive (convolution) product.

The joint histogram is the convolution of the child histograms (capped at the depth bound). Unranking resolves the per-child fine buckets that sum to the target, then the per-child offsets via mixed-radix decomposition using suffix-convolution counts. This is the Composite reference case; the empty product is the single empty tuple at bucket 0.

Parameters:

• children (Sequence[CountIndex])

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

CountIndex

build_budget_index(index, quantizer, budget_bits, value_combine=None, exact_log_density=None, truncated=False)

Wrap a CountIndex as a budget-bounded LazyQuantizedEnumerationIndex.

Accumulates coarse bins (fine buckets grouped by quantizer.oversample) in descending-probability order until the cumulative count reaches 2**budget_bits, then stops. The returned getter maps a coarse (bin, offset) to a fine (bucket, offset), unranks the structural value, optionally maps it with value_combine (e.g. tuple->list), and reports the exact log density (recomputed via exact_log_density when supplied, otherwise the structurally accumulated log probability).

Parameters:

• index (CountIndex)

• quantizer (Quantizer)

• budget_bits (float)

• value_combine (Callable[[Any], Any] | None)

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

• truncated (bool)

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)

distinct_budget_stream(dist, budget_bits, bin_width_bits=1.0, oversample=8, dedup='canonical', start=0, stop=None, max_entries=1 << 16, num_workers=None)

Yield DISTINCT (value, exact_log_prob) from a count-budget index, in approx descending order.

Builds the budget index and removes repeats by one of two modes (see ProbabilityDistribution.count_budget_distinct for the full contract):

• dedup='canonical': stateless per-item predicate (dist.is_canonical_copy), O(1) memory and random-accessible – start/stop choose a STRUCTURAL rank range, so the distinct enumeration can begin anywhere and partition across workers with no shared state.

• dedup='window': a bounded O(max_entries) LRU over the stream (sequential; start must be 0).

Exact-count families never duplicate, so either mode is a pass-through.

Parameters:

• budget_bits (float)

• bin_width_bits (float)

• oversample (int)

• dedup (str)

• start (int)

• stop (int | None)

• max_entries (int)

• num_workers (int | None)

Return type:

Iterator[tuple[Any, float]]

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