PaperlayerView exact revision on arXiv

Source-linked AI summary

The Cost of Conservation: Coordination-Memory Laws for Exact-Support Generation

Zhen Zhang, Amr Alanwar

arXiv:2609.26126v1cs.AIcs.CC

TL;DR

Exact-support generation poses a coordination–memory tradeoff when decisions must follow a fixed order with bounded persistent state. The paper matches the selector rate to a killed spectral profile and shows that the exchange depends on conservation rank; local statistics alone may not reveal execution cost.

  • Problem

    A central sampler can enforce a fixed quota, but it is unclear how preselected plans trade against online memory when generation is fixed-order, memory-limited, and every output must obey the quota.

    Source: §1 · p. 1

  • Method

    The paper analyzes a fixed-order interface with a preselected plan and bounded-state exact-support executors, using a spectral converse and a codeword-wise posterior construction.

    Source: §1 · p. 2, §2 · p. 3

  • Results

    At fixed conservation rank r, reducing the asymptotic plan-selection rate by a factor c costs (r/2) log2 c additional persistent-state bits.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Targets with matching one-token laws can remain locally similar while requiring Θ(log r) different execution memory, so local output statistics do not certify comparable execution cost.

    Source: §1 · p. 2

    For arbitrary position-specific real probabilities, the theorem does not bound the precision or joint description of program-specific tables.

    Source: §2.3 · p. 11

Abstract

from arXiv · show

Many AI systems make decisions locally, even when every realized output must obey an additive conservation law, such as selecting exactly a fixed number of items. This constraint can be statistically invisible: small subsets of a balanced fixed-budget output look increasingly independent, yet communication-free coordinate-parallel generation needs exponentially many pre-shared plans, while a sequential exact sampler needs only logarithmic memory. We study product measures conditioned on additive conservation laws in the intermediate regime where one plan is selected before a fixed-order pass, every plan is a bounded-state stochastic executor whose support is entirely legal, and the mixture of plan laws approximates the target distribution in total variation. Our main result identifies the optimal asymptotic selector rate, up to constant factors, with the killed spectral profile of the conservation-difference walk. The resulting coordination cost decreases as an inverse power of live-state width, with an exponent determined by intrinsic conservation rank rather than alphabet size; the law extends to noncentral budgets and heterogeneous local scores. The converse is driven by a state-versus-resource-sum obstruction, while a rate-matching construction compiles discrepancy control into exact-support finite-state plans. Complementary results characterize block-parallel plan complexity and the benefit of programmable output order. Together, these results show precisely how online memory substitutes for front-loaded coordination in exact-support generation.

1 Introduction

Exact-support generation is easy for a central sampler but costly when plans must be chosen before a fixed-order, memory-limited pass. The paper quantifies how pre-shared plans trade against online memory, with the exchange rate controlled by conservation rank.

1 Introduction

  • The studied interface chooses a plan before generation, then makes irrevocable fixed-order decisions with bounded persistent state, exact legal support, and a mixture approximating the conditioned product law.A central joint sampler and a one-plan remaining-budget program are high-state endpoints; the tradeoff concerns bounded-state execution without repair.Source: §1 · p. 1
  • Two targets with the same one-token law can have k-coordinate marginals close for k ≪ m/√r yet differ by Θ(log r) in execution-memory requirements.The passage identifies m/√r as the sharp-order detectability threshold, so matching local output statistics does not certify comparable execution cost.Source: §1 · p. 2
  • At fixed conservation rank r, cutting the asymptotic plan-selection rate by a factor c costs (r/2) log2 c additional persistent-state bits.The selector rate is identified, up to constant factors, with the killed spectral profile of the conservation-difference walk.Source: §1 · p. 2
  • The framework covers heterogeneous local scores and noncentral budgets, and also characterizes block-parallel execution and programmable output order.The contribution list also reports that fragmentation changes execution memory while remaining invisible to local checks.Source: §1 · p. 2
  • The result is interface-specific: execution cost depends on where coordination may be stored and used, not merely on constraint or local-statistical simplicity.Conditional-Poisson stochastic beam search is a direct AI instance, with its global dynamic program serving as the high-state endpoint.Source: §1 · p. 2

2 Coordination-memory laws

This section studies coordination costs for exact-support generation under additive conservation laws, including the tradeoff between preselected plans and persistent state. It also examines how fragmentation, block-parallel execution, and programmable output order shape coordination and implementation scope.

2 Coordination-memory laws

  • A width-S plan is a fixed-order stochastic executor with exact legal support; only its bounded live state carries information between steps, while the plan is chosen in advance.The plan identity is front-loaded advice, and fresh private randomness is free.Source: §2 · p. 3

2.1 Core result: the spectral coordination-memory law

  • The killed difference walk governs both bounds: a width-S executor retains at most S cumulative differences, and a bounded-discrepancy compiler realizes exact-support plans matching the spectral rate.Each compiled plan has width at most the discrepancy-set size and samples the target conditioned on its selected auxiliary variables and legal endpoint.Source: §2.1 · pp. 4–6
  • For the fixed-rank law, writing B = log2 S, selector rate is Rfix(B) = Θ(2^-2B/r); its exponent depends only on intrinsic conservation rank, not alphabet size.The exponent remains −2/r for independent position-specific laws on the same finite alphabet.Source: §2.1 · p. 4
  • For quota-safe routing, the uniform balanced target has rate Θq(2^-2B/(q−1)); bounded state requires linear selector control, while sublinear control requires growing state.The result concerns a fixed-order, no-drop router, not the systems cited as examples of different interface relaxations.Source: §2.1 · p. 7
  • A shard needs at least k dimensions in any deterministic continuous pre-sampling summary to reproduce the exact quota law; sending its first k elementary-symmetric coefficients attains this bound.On a compact family of ordered local weights, the optimal message length at quota-law TV error η is k log2(1/η) + O_k(1).Source: §2.1 · p. 8

2.2 Structural consequence: fragmentation and local invisibility

  • Fragmenting rank r into k equal rank blocks costs r/2 log2 k + Θη(r) persistent-memory bits at fixed small selector rate, interpolating between binary budgets and one exclusive quota.The endpoints are r/2 log2 r + Θη(r) bits for independent binary budgets and Θη(r) for one exclusive (r+1)-category quota.Source: §2.2 · p. 8
  • Two rank-r targets on the same alphabet with the same uniform one-token law can differ by Θ(log r) in execution memory despite becoming locally indistinguishable below the sharp-order threshold m/√r.Their local distance tends to zero when k√r/m → 0 and to one when k = o(m) and k√r/m → ∞.Source: §2.2 · p. 9
  • For the balanced-slice targets, shared one-token marginals coexist with count-statistic variance O(rk^2), and total variation tends to one when k√r/m → ∞.The two targets arrange balanced columns and category counts differently; this demonstrates that local statistical similarity does not imply global similarity.Source: §2.2 · p. 9
  • A noncentral budget uses the profile of its mean-matching Gibbs tilt; bounded local odds also give a weighted size-k slate the rank-one law Θ(S^-2).The slate distribution is exactly a heterogeneous Bernoulli product conditioned on its count.Source: §2.2 · pp. 9–10
  • Finite-rank CPU calculations recover slopes −1.964 and −0.948 in irregular rank-one and rank-two examples, while grouped-law checks verify key identities to machine precision.For balanced fixed-q targets and fixed S, the seeded construction has an Oq,S(m)-bit executable description; arbitrary real-valued transition tables are not covered by that descriptor result.Source: §2.2 · p. 10
  • For odd S, hard-coding a coordinate permutation in a width-S binary executor closes the factor-four asymptotic constant gap left by immutable fixed-order streams.Permutations must be part of the plan and require addressable outputs; the fixed-order gap is not removed by changing the stationary-weight profile within the analyzed family.Source: §2.2 · p. 10

2.3 Secondary boundary: block-parallel execution

  • For ε < 1/5, the minimum number of block-product plans is characterized by a block-profile coordination sandwich.The rounding argument uses independent-sum concentration to replace components with a legal single-profile block product, with averaging giving a 5ε cost.Source: §2.3 · p. 10
  • For exact block-parallel generation, minimum selector entropy equals the entropy of the joint block-resource totals.For approximate representations, the corollary also gives an entropy bound in terms of approximation error and the support size of the block-total profile, though its formula is not included in these passages.Source: §2.3 · p. 11
  • Balanced-slice outputs can be locally product-like while coordinate-parallel execution remains globally expensive, so local statistical similarity does not determine execution cost.The local bound comes from coupling sampling without replacement, while the global coordination bound comes from the block-profile sandwich.Source: §2.3 · p. 11
  • The selector-rate converse survives charging for library provisioning, but compact library descriptions are established only for balanced fixed-q targets and fixed S.For arbitrary position-specific real probabilities, finite-state posteriors exist but their precision and joint program-table description are unbounded here; no compact descriptor theorem is claimed for the permutation library.Source: §2.3 · p. 11

3 Finite-scale audits

Finite-scale audits test rank-law predictions and exactly evaluate a real-score fixed-budget curation target, while Table 1 distinguishes the priced interface from comparison endpoints and capabilities that remove its obstruction.

3 Finite-scale audits

  • At TV 0.05, the 9-of-18 slates need a median 5,938 coordinate-parallel plans; block sizes 2, 3, and 6 need 454, 87, and 7 plans, respectively.The remaining-budget baseline uses one plan with at most 4 persistent bits.Source: §3 · p. 11
  • The real-score validation exactly evaluates 200 stochastic slates from 122,270 finite GPT-4 UltraFeedback scores and is target-side validation, not a natural workload.Source: §3 · p. 11
  • Table 1 separates the priced coordination–memory interface from comparison endpoints and capabilities that remove its obstruction.Source: Table 1 · p. 12

4 Related work and conclusion

The section distinguishes the paper’s fixed-order, memory-limited interface from neighboring sampling and resource frameworks, then concludes that online state substitutes for front-loaded coordination at a rank-controlled rate.

4 Related work and conclusion

Claim-to-proof and scope index

The index maps the paper’s main claims to their proof locations and records scope boundaries for the fixed-order coordination–memory law and secondary results.

Claim-to-proof and scope index

  • The appendix is a navigation layer for the main text’s claims and proof roadmaps, not a source of additional claims.Source: Claim-to-proof and scope index · p. 13
  • The core law covers fixed-order bounded-state execution with legal support, free within-step randomness, charged persistent state, and read-only transition tables treated as nonuniform configuration.Source: Claim-to-proof and scope index · p. 13
  • The conservation-rank spectral law’s fixed-order converse, binary matching construction, and general-rank heterogeneous result are located in Sections D, E, and F.Source: Claim-to-proof and scope index · p. 13
  • The codeword-wise exact posterior compiler and uniform heterogeneous stability results are proved in Sections E–F, with the stability proof establishing minorization and bounded increments under a probability floor.Source: Claim-to-proof and scope index · p. 13
  • The index locates proofs for finite-length quota routing, the minimal shard interface, rank-partition geometry, local-statistics bounds, programmable order, and block-profile results across Sections H–M.Source: Claim-to-proof and scope index · p. 13
  • The programmable-order result is a separate boundary result and is not used to claim a sharp fixed-order constant.Source: Claim-to-proof and scope index · p. 13

Technical dependency and boundary index

The index collects technical proof dependencies, asymptotic qualifications, provisioning boundaries, and the scope of numerical and AI-system evidence.

Technical dependency and boundary index

  • Exact support forces each live state to determine one prefix resource sum, yielding a one-plan support bound that feeds the killed-walk converse.Source: Technical dependency and boundary index · p. 14
  • The intrinsic-rank law has both bounds at Θ(S^-2/r), while its power-law simplification applies after blocklength tends to infinity and then live width grows.Source: Technical dependency and boundary index · p. 14
  • The binary construction is leading-constant optimal within the smooth stationary nearest-neighbor family; closing the remaining gap needs another construction or a stronger converse.Source: Technical dependency and boundary index · p. 14
  • The core law prices selector bits and persistent live state, with an executable random-access library established for balanced fixed-alphabet targets but not arbitrary position-specific real transition tables.Source: Technical dependency and boundary index · p. 14
  • Remaining-count autoregression uses one plan but live width grows with the horizon; deployed routers may relax the priced interface through dropping, batchwise assignment, dynamic dispatch, or target-aware repair.Source: Technical dependency and boundary index · p. 14
  • Real-score slate validation is exact target-side enumeration, not a learned-model, latency, or deployment claim; the AI-system results connect conditional-Poisson beam laws and exact-quota streaming allocation to their stated interfaces.Source: Technical dependency and boundary index · p. 15

A Formal execution model

A plan is a finite-state, fixed-order stochastic executor: private randomness may affect a transition, but information that persists must be carried in state. The paper distinguishes the width of each exact-support plan from the size of the library mixing such plans.

A Formal execution model

  • A fixed-order executor carries information between steps only through its state, while fresh randomness may be used within a transition.Its future outputs and states are conditionally independent of earlier history given the plan and current state.Source: A Formal execution model · p. 16
  • Exact support requires every plan to assign positive probability only to outputs in the legal language.The aggregate mixture may combine plans, but each component itself remains legal.Source: A Formal execution model · p. 16
  • For binary outputs, one width-S plan is exactly a width-S KRVZ sampler, while K width-S plans flatten to width at most KS.Ordinary sampler width captures the flattened implementation, not the minimum library size at prescribed component width.Source: A Formal execution model · p. 16
  • A remaining-count sampler for the uniform balanced slice uses one plan at width m/2 + 1, whereas width-one exact-support plans require all legal words as plans.A single flattened-width parameter does not describe the selector-state frontier between these endpoints.Source: A Formal execution model · p. 16
  • For an exact type class, each live state determines one prefix-count vector because distinct vectors cannot share a state with a co-reachable legal suffix.A persistent seed outside the state would violate the stochastic-state convention.Source: A Formal execution model · pp. 16–17

B Interface scope and provenance

The results concern a specific interface: fixed-order exact-support plans with bounded live state and preselected coordination. Their bounds depend on the resource accounting and order of limits, and do not cover every architecture or claim empirical speedups.

B Interface scope and provenance

  • For binary outputs, a K-plan width-S library flattens to width at most KS, but ordinary width does not preserve the selector-state frontier at fixed component width.The frontier decomposes a flattened sampler into truthful low-width components; truthfulness means support inclusion, as in Goldreich et al. (2010, Definition 2.8).Source: B Interface scope and provenance · p. 17
  • Heterogeneous achievability is an existence result unless the separate descriptor term L(Cm) is controlled.The theorem treats transition tables as nonuniform read-only configuration.Source: B Interface scope and provenance · p. 17, §B.1 · p. 18

B.1 Boundary audit for the main claims

  • The selector rate takes m →∞ at fixed live width S, then the exponent −2/r describes sufficiently large S at fixed rank r; general bounds do not claim a sharp leading constant.In the balanced binary fixed-order case, the displayed asymptotic constants differ by four; the gap closes only when plan-specific output order is added as a priced capability.Source: §B.1 · p. 17
  • Only the aggregate library law is TV-approximate; each component has support entirely within the legal language.Mixing therefore cannot hide illegal outputs.Source: §B.1 · p. 17
  • A one-plan remaining-count program samples the balanced target exactly but has width growing with the horizon, so it occupies a different point on the coordination–memory plane.Global scheduling, target-aware repair, token dropping, and dynamic dispatch relax fixed-order exact-support premises rather than contradicting the lower bound.Source: §B.1 · p. 18
  • The numerical audits verify finite spectral slopes, exact profile masses, and reported medians, not learned-model quality or wall-clock speedups.Figure 2 is labeled a numerical audit.Source: §B.1 · p. 18

C Full proofs for the coordination-rate results

The proofs connect exact-support coordination and fixed-order plan-memory bounds to conserved-block profiles, spectral deficits, bounded discrepancy, and the roles of sequential state and front-loaded randomness. They also analyze information-rate concentration and stationary-profile asymptotics, including whether retuning smooth stationary weights can close the factor-four theorem gap.

C Full proofs for the coordination-rate results

  • The approximate selector complexity is bounded by the smooth support size of the profile law, with a matching construction by conditioning on a high-mass profile set.For exact representations, the minimum common entropy equals the entropy of the profile law.Source: C Full proofs for the… · p. 19

C.1 Fixed block size and the closed coordination rate

  • At fixed block size b, the zero-approximation common-entropy rate is cb = (log2 b)/(2b) + O(1/b).This follows from the binomial entropy expansion for the fixed-block profile law.Source: §C.1 · p. 20

C.2 Local equivalence and sequential escape

  • Sampling without replacement from a balanced population couples to independent fair bits until an index repeats; an exact sequential sampler uses an O(mk)-cell table.The sequential construction distinguishes online state from front-loaded common randomness and does not reduce output entropy.Source: §C.2 · p. 21

D A moving-layer spectral converse

  • For sets of at most S states, the moving-layer spectral deficit yields a one-plan support bound for exact generation on the balanced q-ary type class.For q = 2, the bound can use [2 cos(π/(2S + 1))]^m; the argument permits state sets to move arbitrarily with time.Source: D A moving-layer spectral converse · pp. 22–23

E A fixed-order plan-memory frontier

  • A fixed-order width-S plan library attains the S^-2 coordination order, closing the S^-2 versus S^-1 gap left by the block-residual construction.The result does not claim a new constrained-coding eigenvalue or a sharp leading constant.Source: E A fixed-order plan-memory frontier · pp. 23–24

E.1 A stationary bounded-discrepancy channel

  • A stationary bounded-discrepancy channel keeps the discrepancy within D while producing an auxiliary output sequence that is iid Bern(1/2).Its front-loaded plan is Zm = (A, Bm).Source: §E.1 · p. 24

E.2 Bayes reversal gives width-S plans

  • Conditioning the channel on the balanced event yields exact posterior distributions realizable by fixed-order width-S stochastic machines.The balancing endpoint is enforced without an additional counter, using only the S discrepancy states.Source: §E.2 · p. 25

E.3 Information rate and stability

  • For fixed S, the conditioned plan-to-output channel has spectral sup-mutual-information rate cS, with information density stable before and after balancing.The unconditioned deviation probability is exponentially small.Source: §E.3 · pp. 25–26
  • Exponential concentration of the edge-additive information term and polynomial probability of the conditioning event establish the conditioned information-rate claim.The remaining terms are sublinear under the conditioning, completing the proof of (15).Source: §E.3 · p. 26
  • For sine-square weights, boundary edges contribute O(∆^3), while Riemann-sum and Taylor estimates yield the asymptotic rate from (14).Here ∆ = (S + 1)^−1; quadratic vanishing controls the endpoint contribution.Source: §E.3 · p. 27
  • Within the smooth stationary nearest-neighbor fair-output family, the sine profile is leading-constant optimal, so closing the factor-four gap requires a different construction or a stronger converse.The limiting rate is proportional to the ratio of ∫g′² to ∫g², whose minimum is attained by g(x) ∝ sin(πx).Source: §E.3 · p. 27

E.4 Achievability and converse

The section establishes fixed-order achievability and support-converse arguments, then extends the spectral law to heterogeneous positions and growing conservation rank.

E.4 Achievability and converse

  • The fixed-order achievability and support converse match the rate exponent, but their constants remain a factor of four apart.The theorem closes the exponent gap, not the exact-constant problem; retuning the stationary profile does not improve the leading constant.Source: §E.4 · p. 28

F.1 Moving-layer converse

  • Exact support prevents prefixes with different resource sums from sharing a state, bounding one plan’s target mass through the killed resource-difference walk.A mixture close in total variation must cover target mass at least 1 − ε across its plans.Source: §F.1 · p. 29

F.2 A marginal-preserving discrepancy compiler

  • The discrepancy compiler uses only |D| states while ensuring every supported word satisfies the conservation endpoint.Weighted cancellation preserves the source-symbol marginal independently across steps.Source: §F.2 · p. 30

F.3 Information cost and resolvability

  • Information-cost comparison and one-shot resolvability turn the compiler into a mixture of exact-support width-S plans approximating the conditioned law in total variation.The construction chooses discrepancy sets and profiles near the killed-profile optimum.Source: §F.3 · pp. 30–31

F General conservation-rank spectral law

  • For finite-range conservation differences generating a rank-r lattice, the killed spectral profile scales as Θ(S^-2/r).This links the live-state-width exponent to intrinsic lattice rank.Source: §F.4 · p. 31

F.4 Intrinsic-rank profile and heterogeneous positions

  • For heterogeneous local laws bounded below uniformly, the rank law persists with average cost Oη,v(R^-2), taking blocklength to infinity at each fixed R before increasing R.The argument uses uniform mixing and proceeds through endpoint conditioning and resolvability.Source: §F.4 · p. 32

G Growing-rank conservation geometry

  • For growing rank, the converse retains the killed spectral radius while the construction controls connected multinomial superlevel sets and optimizes widths under one state budget.That optimization produces the entropy of the rank partition.Source: G Growing-rank conservation geometry · p. 33

G.1 An exact log-spectral converse

This section develops spectral converse bounds and a dimension-uniform compiler for exact-support generation, relating conservation rank to memory, local distinguishability, and a simultaneous blocklength-rank window. It also treats matching selector-rate scales under triangular-array conditions, memory for independent balanced binary budgets versus one exclusive quota, and sharp support fractions in programmable-order zero-distortion generation.

G.1 An exact log-spectral converse

  • The grouped killed-profile bound scales as c g W^-2, and retaining -log ρ is essential to preserve the factor g for growing-rank products.The log-spectral converse uses the operational bound together with the grouped profile bound.Source: §G.1 · p. 34

G.2 A dimension-uniform compiler

  • A dimension-uniform compiler uses connected probability-threshold state sets and achieves O(W^-2) one-step selector information, yielding the matching upper bound.The state-set construction applies for sufficiently large d and W0 ≤ W ≤ e^(c0d), with n = ⌊αdW^2⌋.Source: §G.2 · pp. 35–37

G.3 Partition entropy, covariance volume, and memory

  • For rank partitions, memory is priced by partition entropy, while covariance volume is comparable to rank-partition size only for products of simplex groups.Resource-neutral label refinement leaves the operational rate unchanged; the memory endpoints include Θη(r) for one exclusive (r + 1)-category quota and (r/2) log2 r + Θη(r) for r independent binary budgets.Source: §G.3 · pp. 37–38

G.4 Local statistics do not reveal the memory class

  • Local marginals can hide distinct memory classes when k√r/m → 0, but their total variation tends to one when k√r/m → ∞.For n fresh outputs with at most k adaptively chosen coordinates each, transcript total variation is bounded by n times the one-query bound.Source: §G.4 · p. 39

G.5 A simultaneous blocklength-rank window

  • A conservative simultaneous blocklength-rank window rules out an order-of-limits artifact; before endpoint conditioning the compiler information-density mean is at most C0W^-2 when m ≥ Ψ(d, W).After conditioning on the balanced endpoint, the concentration bound is multiplied by at most (m + 1)q, with an additional term of the form (m + 1)q2^-cm/W^2.Source: §G.5 · pp. 39–40
  • Under Theorem G.12’s triangular-array and compiler conditions, vanishing-error width-W_m libraries have optimal selector rate Θ(g_m W_m^-2).The theorem gives matching upper and lower bounds, with constants C and c respectively.Source: §G.5 · p. 40
  • For r_m growing under the stated growth condition, independent balanced binary budgets require r_m^2 log2 r_m + Θ_η(r_m) memory bits, versus Θ_η(r_m) for one balanced (r_m+1)-category quota.Both use vanishing-error libraries whose components have exact legal support.Source: §G.5 · p. 41
  • The dimension-uniform result applies only in the stated interior compiler regime; the triangular condition is conservative, and no universal covariance descriptor is claimed outside products of simplex groups.The new claim is the matching exact-support composition, entropy law across rank decompositions, and finite-block persistence; the component tools are borrowed.Source: §G.5 · p. 41

H Zero-distortion support law for programmable order

  • For odd S, Lemma H.1 gives a sharp zero-distortion support-fraction bound for fixed-order width-S exact-support binary plan languages, attained by a centered width-S count corridor along even m.Its fair-iid corridor probability is cos(π/(2S+1))^{m+o(m)}.Source: H Zero-distortion support law for… · p. 42
  • The centered corridor’s uniform law is generated by a fixed-order suffix-count dynamic program with at most S states per layer.Suffix path counts determine exact next-bit probabilities from the current live count.Source: H Zero-distortion support law for… · p. 42
  • The programmable-order result uses this neighborhood fact only; no positive-distortion covering theorem is claimed in the main paper.Source: H Zero-distortion support law for… · p. 42

I Order-programmable achievability by orbit symmetrization

Programmable address order preserves live-state width while changing exact-support languages, and closes the factor-four binary constant gap. For balanced q-ary type classes, a root-lattice posterior construction realizes exact fixed-order plans whose selector-rate exponent is q−1.

I Order-programmable achievability by orbit symmetrization

J Plan-memory exchange for balanced type classes

  • For balanced type classes, the q−1 independent count constraints set the exchange exponent between front-loaded coordination and online memory.The theorem’s constants are effective for each fixed q but inherit nonoptimized graph-isoperimetric and channel bounds.Source: J Plan-memory exchange for balanced… · p. 44

J.1 The root-lattice Bayes channel

  • The auxiliary emitted symbols are iid uniform on [q], while the discrepancy conditioned on the emitted symbol has law πR.This holds at every time under the auxiliary source and channel.Source: §J.1 · p. 44
  • The root-lattice Bayes decomposition exactly realizes each positive-probability plan as a fixed-order width-SR stochastic machine.The source is conditioned on equal symbol counts, producing the uniform balanced type-class law.Source: §J.1 · p. 45
  • Once the plan is fixed, the discrepancy state determines every remaining symbol budget, so the endpoint constraint needs no additional state.The machine uses the SR discrepancy values as its state.Source: §J.1 · p. 45

J.2 The posterior construction has quadratically small plan rate

The posterior construction has per-symbol information rate at most C_q R^-2, enabling exact fixed-order plans at a matching selector-rate scale. A spectral converse identifies q−1 as the exchange exponent, while seeded libraries provide compact executable descriptions without claiming universally minimal program length.

J.2 The posterior construction has quadratically small plan rate

  • For every fixed q, the posterior channel’s per-symbol information rate satisfies c_q,R ≤ C_q R^-2.The constant C_q depends on q.Source: §J.2 · p. 45
  • A codebook of at most 2^{m(c_q,R+o(1))} fixed-order width-SR plans has a mixture converging in total variation to the balanced type-class law.The plans are exact-support posterior realizations; the codebook construction follows from the information-stability bound.Source: §J.2 · pp. 46–47

J.3 Matching spectral converse

  • The spectral converse and posterior construction identify q−1 as the exponent parameter for the coordination-versus-memory exchange in balanced type classes.The converse limits one plan’s support; the posterior channel converts a resolvability codebook into exact fixed-order plans.Source: §J.2 · p. 47, §J.3 · p. 48

K Linear-description seeded plan libraries

  • For fixed q and R, seeded codebooks retain the asymptotic selector rate, vanishing TV error, exact balanced support, and width SR with an Oq,R(m)-bit executable description.The construction avoids exponential library storage.Source: K Linear-description seeded plan… · pp. 48–49
  • The seeded result does not claim universally minimum program length, since specially structured targets may admit shorter deterministic descriptions.Its optimality claim is limited to the selector-rate exponent under the stated shared-library interface.Source: K Linear-description seeded plan… · p. 50

L Restricted-interface corollary: quota-safe streaming allocation

The corollary studies quota-safe routing with fixed-order execution, bounded persistent state, and preselected control. For uniform balanced targets, it establishes a coordination–memory tradeoff and identifies the scope of that result.

L Restricted-interface corollary: quota-safe streaming allocation

  • Every router in the model uses a preselected plan, then routes in fixed order with at most B persistent bits and exact quotas on every realization.The target-law approximation is measured in total variation; batch and plan tables are free side information.Source: L Restricted-interface corollary:… · pp. 50–51
  • With fixed q and a uniform balanced target, bounded persistent state forces C_m = Ω_q(m), while sublinear control requires B_m → ∞.These consequences hold when the allowed approximation errors remain bounded away from one and the stated deficit condition is met.Source: L Restricted-interface corollary:… · p. 51
  • The frontier rules out jointly retaining fixed physical order, exact no-drop quotas, bounded state, sublinear control, and vanishing TV error.Table 3 compares deployed systems by the capabilities they purchase to avoid this frontier; it describes resource placement, not latency or activation memory.Source: L Restricted-interface corollary:… · p. 51, Table 3 · p. 52
  • The bound concerns preserving a stochastic routing law, not finding one feasible assignment; it becomes vacuous for a deterministic target assignment.The paper does not claim existing routers instantiate the restricted executor.Source: L Restricted-interface corollary:… · p. 52

M Conditional-Poisson beam admission

The paper analyzes exact fixed-size conditional-Poisson admission, including sequential execution and shardwise coordination. It also reports real-score fixed-budget validation of plan-count bounds.

M Conditional-Poisson beam admission

  • Conditional-Poisson admission samples exactly k weighted candidates without replacement using remaining admissions r as its online state.The exact one-program implementation uses a width-(k + 1) state and a precomputed (n + 1)(k + 1) suffix table.Source: M Conditional-Poisson beam admission · pp. 52–53
  • Conditional on the shard-count profile, shard subsets are independent conditional-Poisson samples, and the profile attains the minimum common-plan entropy and support size.A coordinator can sample the profile while shards use local suffix programs, without gathering vocabulary logits.Source: M Conditional-Poisson beam admission · pp. 53–54
  • For every positive weight vector, an exact deterministic one-round shard summary needs at least k dimensions; the k elementary-symmetric coefficients attain equality.On a compact regular weight family, the optimal deterministic message length for quota-law TV error η scales as Θ_k(η^-k).Source: M Conditional-Poisson beam admission · p. 54

N Real-score fixed-budget validation

  • At ε = .05 and β = 1, median singleton smooth-support bounds were 5,938/17,946, and exact profile entropy was 13.42 bits.Median lower bounds fell from 5,938 at block size 1 to 1 at size 18; at singleton granularity, the median lower bound was 859.5 for β = 2.Source: N Real-score fixed-budget validation · p. 55

Related papers

Loading 2609.26126v1…