mixle.engines.lns module

Logarithmic number system for mixle’s log-space compute – quantize by a fixed log constant ln(C).

mixle already works in log-space (log-densities, log-weights, log-sum-exp), so the natural quantization is on the log value: store v as the integer k = round(ln(v) / s) with step s = ln(C), i.e. v = C**k. Then the two hot operations become integer arithmetic:

• multiplying probabilities = adding log-probs = adding the integers k1 + k2 – exact, no table.

• log-sum-exp (adding probabilities – the mixture / HMM / marginalization op) becomes max(k1, k2) + LUT[|k1 - k2|] where LUT[d] = round(log(1 + exp(-d*s)) / s) is a small precomputed integer table (the Gaussian logarithm). No exp, no log – integer max + a gather. This is the transcendental reduction that dominates mixture scoring, and unlike a GEMM it has no BLAS to lose to: measured ~4x faster than float64 logsumexp in pure numpy (more with a compiled integer kernel).

step is the precision dial – the fp1..fpN spectrum, but in the log domain where it is natural: each unit is a factor of C = exp(step), so the relative precision of a stored value is ~``step/2`` and the log-sum-exp error is bounded by ~``step``. Smaller step -> finer + wider integer range (int16 at step~0.1, int32 at step~1e-3). The model’s log-parameters and the data terms are quantized by the SAME step, so the whole score is integer arithmetic.

A true zero (log(0) = -inf) has no finite code, so it gets one reserved sentinel, LOG_ZERO_CODE, and every arithmetic entry point (quantize, logadd, multiply, the compiled kernel) special cases it explicitly before doing any int64 math – see the constants below and MXR-080-0138.

class LogNumberSystem(step=1e-2)

Bases: object

Quantize log-space values to integers in units of step = ln(C) and compute on the integers.

Parameters:

step (float)

CODE_MIN = np.int64(-2305843009213693952)

CODE_MAX = np.int64(2305843009213693952)

classmethod from_relative_precision(rel)

Build a system whose stored values are accurate to ~``rel`` relative (step = ln(1+rel)).

Parameters:

rel (float)

Return type:

LogNumberSystem

max_logsumexp_error(n)

Certified bound on the absolute log-sum-exp error for reducing n quantized terms.

Two error sources compound over the pairwise reduction tree (see logsumexp()):

• input quantization – each leaf starts up to step/2 away from its true log-value.

• LUT rounding – each logadd() looks up round(log1p(exp(-d*step)) / step), itself within step/2 of the true correction (by construction: the table’s last entry is exactly 0, and dmax is sized so the true correction is already < step/2 there, so clipping a larger gap to dmax costs less error than the in-table rounding it stands in for).

logsumexp(a, b) = log(exp(a) + exp(b)) is monotonic and shift-equivariant in each argument (logsumexp(a+c, b+c) = logsumexp(a, b) + c), which gives an EXACT bound – not a first-order approximation – on how far a logadd() of already-approximate operands can land from the true value of the pair they represent: at most the WORSE of the two operands’ existing error. Errors don’t add across siblings, only the fresh per-node LUT rounding does. So after d tree levels the worst-case error is step/2 (leaf quantization) plus d more halves of step (one fresh LUT rounding per level on the critical path): (d + 1) * step / 2.

Both reduction trees here (the numpy fallback and the compiled kernel) combine adjacent pairs and carry any odd leftover forward unchanged, so they are always balanced: the deepest element crosses exactly d = ceil(log2(n)) levels regardless of how n factors, and this bound is a valid certificate for any n – not just the 2-term case the previous constant 1.5 * step bound was actually sized for (equivalent to this formula at n in {3, 4}; already violated by measured error at, e.g., n=8 – see MXR-080-0139 and the regression tests).

Parameters:

n (int)

Return type:

float

quantize(log_values)

Round log-space values to integer multiples of step (the stored representation).

Exact -inf (the log of a true zero) maps to the reserved LOG_ZERO_CODE sentinel – never through a float-to-int64 cast, whose behavior for a non-finite input this module does not rely on (see MXR-080-0138). NaN and +inf have no LNS code and raise. Any other value that would round outside [CODE_MIN, CODE_MAX] is rejected: clipping would invalidate the format’s quantization-error certificate.

Parameters:

log_values (Any)

Return type:

ndarray

dequantize(k)

Recover the float log-value k * step; the reserved zero sentinel maps back to exactly -inf.

Parameters:

k (Any)

Return type:

ndarray

logadd(k1, k2)

Integer Gaussian logarithm: logsumexp of two quantized log-values -> max + LUT[|diff|].

LOG_ZERO_CODE (log of an exact zero) is absorbing – zero-plus-anything is the other operand, computed with no LUT lookup at all. Ordinary operands must already be canonical, i.e. inside [CODE_MIN, CODE_MAX]: D-0129 rejects a non-canonical public code rather than saturating it, so that the published rounding bound applies to every accepted value. That is what keeps the |k1 - k2| difference below from overflowing int64 (MXR-080-0138) – an overflowed, wrapped-negative difference would otherwise become the LUT index a few lines down. The derived sum does saturate to the range, since it is the library’s own value, not the caller’s. (The compiled _logadd clamps its operands instead of rejecting them: it is a boundscheck-disabled kernel reached through this validation, and clamping is its last-ditch memory-safety guard, not the public contract.)

Parameters:

• k1 (Any)

• k2 (Any)

Return type:

ndarray

multiply(k1, k2)

Integer code for the PRODUCT of two LNS values: log(a*b) = log(a) + log(b) -> code add.

Exact for ordinary operands (integer add, no LUT, no rounding). LOG_ZERO_CODE is absorbing (anything times zero is zero); an ordinary sum that would leave [CODE_MIN, CODE_MAX] saturates to that boundary rather than silently wrapping through int64 overflow (MXR-080-0138). Prefer this over raw k1 + k2 for any code that might be (or derive from) a quantized true zero.

Parameters:

• k1 (Any)

• k2 (Any)

Return type:

ndarray

logsumexp(k, axis=-1)

Integer log-sum-exp along axis via a pairwise tree of logadd() (no exp/log).

Uses the compiled one-pass tree kernel for the common 2-D last-axis reduction when available (bit-identical to the numpy tree, ~8x faster); falls back to vectorized numpy otherwise. Both trees combine adjacent pairs and carry an odd leftover element forward unchanged, so the deepest element always makes exactly ceil(log2(m)) logadd hops (m = reduced axis length) – see max_logsumexp_error(), which bounds the resulting error in terms of that depth.

Parameters:

• k (Any)

• axis (int)

Return type:

ndarray

integer_dtype(log_range)

Smallest signed integer dtype that holds log-values spanning [-log_range, log_range].

Sized for ordinary codes only: LOG_ZERO_CODE is representable in int64 alone, so a caller that needs to store exact zeros (rather than pass them straight through quantize/dequantize) should not narrow the returned dtype below int64.

Parameters:

log_range (float)

Return type:

Any