mixle.enumeration.seek_index module

A persistent count-budget enumeration index: precompute once, then unrank/count/slice many times.

The one-shot drivers (count_budget_index(), count_dp_seek(), the AutoregressiveEnumerable convenience methods) rebuild the structural count DP on every query – fine for a single lookup, wasteful for the common pattern of many queries against one model (seek a thousand ranks, sweep thresholds, page through the support). For a transformer LM every rebuild re-walks the whole live prefix tree in Python even when the forward passes are memoized.

SeekIndex is the reusable precomputation structure:

• built once – the fine count histogram and its structural unranker are computed at a depth (bit budget) and kept;

• queried many times – unrank / slice / iter_from / count / threshold / rank_bracket all read the stored tables (a query costs an O(log #bins) bisect plus one structural unrank walk, never a DP rebuild);

• deepened in place – a query past the built depth triggers one rebuild at a geometrically deeper budget (models that memoize their evaluations, e.g. the autoregressive adapter’s forward cache, make the re-walk much cheaper than the first build).

Approximation contract: identical to the underlying count DP – the bin assignment is quantized (ordering is exact up to the fine-bucket width) and, for the tropical Mixture/HMM indices, counts are the structural upper bound documented on those families. With count_mode='float' the counts themselves are float64 (exact below 2**53, ~1e-16 relative error per operation beyond); every unranked value still carries its exact log_density.

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.

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).

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)