Exact rational weighted contraction and target-dependent precision

Exact rational weighted contraction and target-dependent precision

The supplied OpenAI preprint’s Appendix D.1[7] contracts Boolean-wire networks over a truncated polynomial ring modulo a power of two. Rational signed weights are not an automatic instance of that coefficient ring. We give an explicit transfer, including signed recovery and all precision costs, and a sharp improvement when the target supplies an independently justified interval. The resulting source-likelihood interface is useful without implementing the paper’s asymptotic contraction algorithm. Weighted sum–product and variable elimination are established methods. Scott–Sorkin[13], Sections 1–2 and 6, treat polynomial and ring-valued constraint satisfaction; Kschischang–Frey–Loeliger [4], Sections II–III, explain factorized marginalization and its relation to forward/backward algorithms. We do not claim weighted contraction, denominator clearing, modular reconstruction or dynamic programming as newly discovered techniques. The contribution here is their precise transfer to the supplied ETH theorem and a checked, typed interface for the nominated source–readout tasks.

A rational factor model with explicit arithmetic costs

Let, and let be explicitly supplied tables, with. Negative entries are permitted for algebraic contraction, though they are not probabilities. Write

Searchable transcription

F
∏︂
Z =
∑︂
v=1
Tv(x|Sv),
I =
∑︂
v
|Sv|.
x∈{0,1}N

Searchable transcription

The table index convention, scope order and declared unused variables are part of the input. Let L be
the total binary description length and let b bound numerator and positive-denominator bit length of
each rational entry. For each tensor take the positive least common denominator qv of its entries, and
set
Wv = qvTv ∈Z2|Sv|,
Q =
∏︂
v
qv,
Av = max |Wv|,
B = 2N ∏︂
v
Av.

Then for an integer satisfying. For fixed, each and each integer entry has) bits, so log). Zero tensors, isolated scalar tensors and unused source variables can be handled directly. In particular, unused variables multiply the contraction ; they are not silently omitted. In the theorem below all scalar entries and these factors of two remain in the same modular integer contraction. The interval therefore refers to the original with no further restoration multiplier after decoding. An implementation may multiply known integer scalar factors modulo 2 before decoding. If it instead decodes a smaller residual contraction, it must derive a new interval and denominator for that residual problem. Scalar products require their actual input/output-bit costs in either case.

Theorem A.1 (Exact rational transfer of OpenAI Appendix D.1). Given a justified integer bound , choose with. The factor model can be transformed into a bipartite Boolean-wire tensor network with at most wires and maximum degree ∆max, retaining scalar vertices as described above. Its integer entries reduced modulo are instances of Appendix D.1 with truncation order one. Let and be the actual transformed wire and vertex counts and put

Searchable transcription

s = 2 + E′ + V ′ + P + ∆2.

Searchable transcription

Conditional on the supplied OpenAI preprint’s Theorem D.1, the contraction has deterministic bit
complexity
poly(s + L + N) 2O(s/√log s)

and polynomial space. The recovered value is the exact signed rational. For bounded arity, fixed entry bit length and no isolated scalar factors or unused source variables, with the crude bound above; thus the time is subexponential in wires. Growing precision must remain in. Retaining many scalar vertices or unused-variable multipliers can increase or without increasing; merely preprocessing those factors does not remove their cost from the full-integer formulation above.

Proof. Replace every occurrence of a variable by a port of its factor. Enforce agreement of its ports by a tree of equality tensors of degree at most three. A variable appearing once uses the unary tensor 1), twice uses a binary equality tensor, and3 occurrences use2 trivalent equality vertices. Every assignment of the original bit extends uniquely to the tree; inconsistent leaf values give zero. There are at most 2 edges before bipartization. Subdivide each edge with a binary equality tensor, placing all original vertices on one side and all subdivision vertices on the other. This at most doubles the number of edges and preserves the contraction, because the two new edge bits must agree. The transformed maximum degree is at most max Reduce the integer tables modulo 2 , leaving equality entries zero or one. Reduction is a ring homomorphism, so contraction gives mod . Exact table access and reduction cost polynomial time in the description and precision; this meets the entry-evaluator hypothesis of Theorem D.1. Our conservative makes all its edge, vertex, degree and precision conditions hold, with fixed absolute constants. The theorem gives the displayed time and space. There is exactly one integer in [ with the returned residue, since two distinct such integers would differ by at least 2. Divide the recovered full integer by to obtain For fixed arity and entry bits, the crude interval [] needs). Under the stated absence of isolated scalar factors and unused source variables,) for a nonempty constructed network; its vertex and degree bounds have the same order. This proves the last assertion. Bounded exceptional sizes are handled directly as in Theorem D.1.

The generic transfer is not uniformly subexponential in the original source bits if an encoding introduces many wires or if grows much faster than the wire count. For example, an log padding parameter does not give a subexponential-in- bound from the displayed formula. Direct enumeration, low-treewidth elimination or a small transfer matrix may already be faster. The implementation reports these distinctions rather than promising a practical asymptotic speedup.

A sharp target-relative arithmetic interface

Theorem A.2 (Interval-assisted reconstruction and target descent). For all integers in a nonempty interval, reduction modulo is injective if and only if. Given a residue and this promise, the unique answer is

Searchable transcription

z = r + M
⌈︃L0 −r
⌉︃
,
r ∈{0, . . . , M −1},
M

provided; otherwise the residue contradicts the interval. For a nominated target on an admitted integer set, knowing only mod determines exactly if and only if is constant on each residue class intersected with

Proof. An interval of width smaller than contains no distinct pair differing by a nonzero multiple of. If its width is at least, the two integers both belong to it and have the same residue. The formula chooses the least integer in the residue class not below, proving recovery and its exact failure test. For the target statement, a residue-only answer must take one value on each class. Constancy makes that value well defined and sufficient, while two unequal target values in one class preclude it.

Thus it is the width of a justified interval, not its distance from zero, that determines full-value precision. A coarse target can need still fewer bits: parity needs = 1 on any interval. Conversely the target on needs 2 whenever1. Otherwise zero and 2 have identical residues and different answers. A generic decision-only contraction therefore cannot drop this precision merely because it returns one bit. If the admitted interval already excludes zero, that particular decision is immediate. The residue criterion is an instance of Rodgers’s target-relative descent principle. It supplies a sharp arithmetic adapter, not a new source of information. The interval must be justified independently; it cannot be inferred from the single modular residue. The code deliberately labels a caller-supplied interval as a premise. An incorrect narrow interval can silently select the wrong congruent integer, which no residue-only algorithm can prevent.

Completed record-law calculation

Searchable transcription

For a concrete nonnegative source, take hidden bits X0, . . . , X4, initial distribution (1/2, 1/2) and
transitions
(︄
4/5
1/5
1/5
4/5
)︄

Searchable transcription

P =
.

At each tick emit with probability 67 and its complement with probability 17, independently conditional on the hidden trajectory. These preparations and emission laws define a conventional finite stochastic source. They are not inferred from a readout or a Born-selection argument. For the retained word 0), factor contraction and an independently implemented forward recursion both give

Searchable transcription

Pr(Y = y) =
848
60025,
Pr(X0 = 0 | Y = y) = 1501
7420.

The second is a posterior under the nominated source measure, not an identification of the actual hidden initial bit. Clearing the ten factor denominators gives = 21 008 750 and scaled answer 296 800. The naive magnitude calculation supplies = 63 700 992, so the symmetric integer interval requires The initial distribution and transition rows sum to one, and each emitted word factor is at most 6 Consequently the event probability is between zero and (6, independently of computing its exact value. This yields the tighter scaled interval

Searchable transcription

0 ≤Zint ≤
⌊︂
Q(6/7)5⌋︂
= 9 720 000,

requiring only = 24. Both modular evaluations reconstruct the same answer. This is a three-bit precision saving for a specified task; it is not an empirical speedup or a new general worst-case ETH bound. For arbitrary nonnegative source factors, the adapter also supports exact event indicators and supplied record likelihoods. It normalizes numerator and denominator separately and returns an explicit undefined status if the conditioning weight is zero. Signed tables are rejected by the probability interface even though the algebraic contraction backend accepts them. No probability is assigned to an impossible observation, and no arbitrary uniform prior is silently introduced.

Verification, backends and an easy-instance ceiling

The reusable weighted.py exposes exact rational factor evaluation, ordinary variable elimination, integer denominator clearing, modular enumeration, interval decoding, posterior queries and a Boolean-wire network converter. It uses Python’s exact integers and Fraction. Its backends are not an implementation of the ETH paper’s recursive contraction theorem.

verify_weighted.py checks 140 random signed rational factor models against independently organized enumeration, modular evaluation and variable elimination. It checks 3 400 signed interval decodings, the sharp lower-precision failures, parity-versus-zero target counterexamples, and explicit port-network conversions including high incidence, isolated scalars and unused variables. It also rejects signed probability measures and handles impossible conditioning. As a nontrivial signed cyclic example, use the same matrix on every edge,

Searchable transcription

(︄
1/2
−2/3
3/5
−7/11
)︄
,
Zn =
∑︂
∏︂
M =
i
Mxi,xi+1,
xn = x0.
x∈{0,1}n

An independently computed matrix power gives Tr), which agrees with the adapter at 40. The small cases also agree with exhaustive and modular enumeration. For ordinary elimination uses 618 factor-entry evaluations with maximum bucket scope three, where exhaustive enumeration would inspect 2 assignments. This is a verified operation-count advantage of an established low-width method; the transfer-matrix solution is also polynomial. It is specifically evidence against replacing every easy source calculation with the general ETH algorithm. The universal claim is the conditional theorem transfer and the exact reconstruction proof. Finite diagnostics check the implementation, not the ETH paper’s whole proof. We do not establish continuous CP feasibility, a new trine-source resource bound, quantum outcome selection or a consciousness mechanism. Each would require its own additional interface.