We turn cumulative population-average conditional KL error into hard computational guarantees for parallel sampling. For a target distribution on [V]n, let Δ be the expected cumulative conditional KL over a uniformly random reveal order. Under Δ ≤ ε2/32, we obtain total variation error at most ε with two complementary resource guarantees. Binary blocked recursive speculative rejection sampling uses O(√(n(1 + log V)) log3(2n)/ε) rounds and O(n log(2n)/ε) full-vector queries. Shallow trees use Oh(n1/2 + 1/(2h) polylog(n, V, 1/ε)) rounds and O(n(h + 1)/ε) queries for fixed h ≥ 2. Both guarantees hold on every run for fixed, strictly positive conditional interfaces, including incompatible answers. Complete execution histories capture the cost of discarded trials; residual-KL control yields the sharper precision dependence. Online truncation enforces both budgets. An algorithm-specific Ω(nΔ) expected-depth construction exposes the cost of direct single-root execution. We identify the precision regimes relative to sequential and prefetch baselines, and illustrate the budget-error relation with exact finite-state calculations. This preprint includes the complete proof appendices and summaries of the archived computational checks. Executable verification files are not included in this record.
We turn cumulative population-average conditional KL error into hard computational guarantees for parallel sampling. For a target distribution on [V]n, let Δ be the expected cumulative conditional KL over a uniformly random reveal order. Under Δ ≤ ε2/32, we obtain total variation error at most ε with two complementary resource guarantees. Binary blocked recursive speculative rejection sampling uses O(√(n(1 + log V)) log3(2n)/ε) rounds and O(n log(2n)/ε) full-vector queries. Shallow trees use Oh(n1/2 + 1/(2h) polylog(n, V, 1/ε)) rounds and O(n(h + 1)/ε) queries for fixed h ≥ 2. Both guarantees hold on every run for fixed, strictly positive conditional interfaces, including incompatible answers. Complete execution histories capture the cost of discarded trials; residual-KL control yields the sharper precision dependence. Online truncation enforces both budgets. An algorithm-specific Ω(nΔ) expected-depth construction exposes the cost of direct single-root execution. We identify the precision regimes relative to sequential and prefetch baselines, and illustrate the budget-error relation with exact finite-state calculations. This preprint includes the complete proof appendices and summaries of the archived computational checks. Executable verification files are not included in this record.
We determine how errors in a coherent receiver's outputs change the cost of calibrating an exponentially rare quantum component. For a smooth moment-matched phase family, one receiver exposes informative events that counting misses. The optimal robust cost follows an explicit curve: an ideal-cost plateau ends at a tail-mass threshold, then an increasing branch approaches the feasibility boundary. One stopping rule attains this exponent at every unknown label, even when conditional errors depend on the observed history. Near the boundary, the remaining contamination margin δ and an explicit midpoint variance v* determine a finer law. As δ and the error target α vanish, the minimax cost is 2v* δ⁻² log(1/α), without a relative-rate restriction for a fixed receiver. This coefficient governs fixed sampling and every fixed positive-moment cost of arbitrary randomized stopping; a single clean source forces the lower bound. A uniform theorem carries the constant to changing finite receivers under explicit margin conditions and gives a computable critical strip for the physical family. These laws locate the loss of efficient calibration and quantify the cost of approaching the last feasible regime. This author preprint includes the main manuscript, complete proofs, LaTeX sources and computational materials. Journal peer review has not been completed. The scientific files are preserved unchanged; author identity is provided in the record metadata and the accompanying README. Version V1.7. All files are embargoed until 1 February 2027, when they will automatically become publicly accessible. Bibliographic metadata are public.
We study independent one-message shuffling through a common channel with replacement adjacency and arbitrary deterministic backgrounds. Under one local Rényi budget, without a pointwise likelihood-ratio cap, the optimal uniform same-order rate is n−min{1,α−1} for fixed α>1; a local KL budget alone gives no uniform amplification. We determine the exact asymptotic worst-case approximate-DP envelope at each fixed positive privacy parameter and the leading inverse calibration at failure probability d/n for all fixed α>1. Matching upper bounds are uniform over channels and alphabets varying with n. At and above order three, the calibration coefficient is the square root of an attained local triple-variance frontier, realizable on at most nine output symbols. At order three we evaluate this frontier on a certified budget interval and identify the unique extremal ratio law. The same frontier determines the limiting central-window profile for α>2 and the logarithmic moderate-window exponent. Under local χ2 diameter C, the exact asymptotic neighboring coefficient is 2C(C+5)/(C+4); we also give explicit finite amplification bounds and a fixed-channel background reduction. Formal verification. All statements of the paper have been formalized in Lean 4 (version 4.35.0) with Mathlib (release v4.35.0), including the computer-assisted order-three theorem, for which all certificate computations are checked by the Lean kernel. The formal proofs contain no sorry and use only the standard axioms propext, Classical.choice and Quot.sound. The project builds from scratch, every module passes a replay by the Lean kernel (leanchecker), and all theorems of the interface file Statements.lean, together with everything they depend on (69 078 declarations in total), were rechecked by the independent type checker nanoda. ChatGPT was used to write the Lean code and Claude to audit it; the author takes full responsibility for all results. Files. The PDF is the paper (24 pages). The ZIP archive Uniform_Renyi_arXiv_source_2026-11-09.zip is the LaTeX source. Its folder anc/ contains the exact rational polynomial certificate for the computer-assisted order-three theorem (verify_order_three_frontier.py, needs only the Python standard library) and further exact checks. The ZIP archive UniformRenyiShuffle-Lean-1.0.0-2026-11-09.zip is the Lean project UniformRenyiShuffle 1.0.0; its file MAP.md gives the Lean name of every statement of the paper. Changes from version 1. The Lean formalization is added. The paper and its LaTeX source are unchanged.
This theoretical and computational preprint integrates standard QND measurement and posterior-martingale results with finite-confidence decisions and physically retained observer records. Under a declared quantum instrument and its standard outcome probabilities, the posterior is a bounded martingale on an increasing observation filtration. A precise sufficient identification condition yields asymptotic terminal weights; a binary Gaussian benchmark gives exact mean stopping times, finite-threshold latch probabilities, and a controlled population-transfer bias bound. Version 2.3 is the first public release. It distinguishes accumulated observations from lossy current memory; assumed Born/instrument probabilities from derived consistency results; expected entropy from pathwise ambiguity; continuous confidence endpoints from discrete overshoot and unresolved runs; and Kramers first escape from endpoint readout error. It also clarifies the conditional D18/D19 persistence-selector interface and the separate D1092 finite-resource ledger, with direct attribution to established QND convergence and filtering literature. The companion archive includes the editable manuscript, PDF, equation sources, a fixed validation protocol, executable independent checks, numerical results, a revision ledger, and unchanged historical inputs. Historical simulation summaries are explicitly distinguished from new executions; some older executable sources were unavailable. The new audit includes exact finite-kernel and stopped-posterior checks, Gaussian likelihood-mixture calculations, five neutral and four population-transfer boundary-value cases, and retention/accounting controls. All examples are analytic or synthetic. No laboratory measurements, independent Born-rule derivation, measurement-problem solution, universal physical selector, or new empirical anchor are claimed.
One random output can require much less work than numerical evaluation. We study exact neural sampling, counting input probes, random bits, arithmetic, and every precision refinement. For dense tanh networks with absolute row sums at most one, weight preprocessing permits polylogarithmic expected sampling work at logarithmic depth. With zero biases, the sharp query scale is the square root of depth at every fixed first-layer rank, and also at arbitrary rank when a column envelope is bounded. The unrestricted gap between square-root and linear query cost remains open. Prefill changes attention. We construct an appendable cache index and a complete exact decoder with positive RMSNorm stabilizers. Its expected work is polynomial in model size and log T when each layer has a common affine key space of fixed rank and the context has length T. The decoder's polynomial degree grows with rank. These bounds give no useful speed prediction at the large ranks of ordinary models. A completely fixed full-rank model still has a formal polylogarithmic context bound, with potentially enormous constants. The decoder maintains finite Taylor moments, prepares precision in the background, and charges rare complete refinements by their probability. Its cost includes neural key and value creation. Without a context index, standard scaling can force linear positional search; arbitrary indexed queries face a conditional barrier in growing dimension. We also prove exact normalization factories and a matching law for an explicit additive-residual family. A checkpoint section gives the certificates and cost formulas needed to apply each positive result.
We show how to use parallelization to speed up sampling from an arbitrary distribution µ on a product space [q]n, given oracle access to counting queries: ℙX∼ µ[XS=σS] for any S⊆ [n] and σS ∈ [q]S. Our algorithm takes O(n2/3· polylog(n,q)) parallel time, to the best of our knowledge, the first sublinear in n runtime for arbitrary distributions. Our results have implications for sampling in autoregressive models. Our algorithm directly works with an equivalent oracle that answers conditional marginal queries ℙX∼ µ[Xi=σi | XS=σS], whose role is played by a trained neural network in autoregressive models. This suggests a roughly n1/3-factor speedup is possible for sampling in any-order autoregressive models. We complement our positive result by showing a lower bound of Ω(n1/3) for the runtime of any parallel sampling algorithm making at most poly(n) queries to the counting oracle, even for q=2.
Research preprint, version 0.3.0. We study a hypothetical Born sampler that independently projects its sampled register with probability epsilon, with immediate outcome/flag feedback on the same persistent state and a noiseless input oracle. Constant-success unique-item search has optimal total query/readout/preparation/ordinary-measurement cost Theta(N^(1/3)+sqrt(epsilon N)), with separately paid gates, classical work, space, transcript bits and precision. The revision adds a second main theorem: every finite Boolean promise problem with success at least 2/3 satisfies Q min{P+1,ceil(1/epsilon)} >= Adv_+(f)/36, using P+1 at epsilon=0. Adv_+ is the entrywise-nonnegative spectral adversary. A complete-history spectral query charge covers entangled workspace, partial measurements, permitted resets, feedback and unequal stopping without a history-count factor. Fixed and decreasing powers are proved separately. The parity application gives Omega(n) queries at any fixed positive collapse rate. The sharper search theorem is retained. The algorithmic template, ideal endpoint and conditional-copy framework are attributed to ABFL and Miloschewsky--Podder; prior imperfect-readout robustness to Abbas et al.; positive weighted/spectral adversary machinery to the established literature including Miloschewsky--Podder and Spalek--Szegedy. Certificates may be exponentially large analytical objects. No signed-adversary extension, efficient certificate discovery, physical implementation, classification of all noisy PDQP or ordinary BPP/BQP result is claimed. OpenAI Codex assisted derivation, literature comparison, drafting and internal checking. Separate provider CLI AI-review reports and dispositions are archived; no independent human peer review or formal certification has occurred.