# Queryable permutation and sparse shuffle framework

Decision: **Prototype sparse replay; defer a source-guaranteed seeded data loader**. Edition: 9 October 2026 Australia/Brisbane. Commercial demand, performance advantage and profitability are unvalidated.

## Research finding

Family 238's signed-tensor companion describes a decision forest that always outputs a permutation on n=2^d slots and computes each point using Ld adaptive queries to shared independent fair switch bits. For one absolute L, the full permutation law approaches uniform as d grows. The trace-smoothing companion supplies a stronger all-size bound: there exists an absolute P>=2 such that any integer v with 2v>=P gives full-law total variation at most (1/2)n^(-5). Its selected CoordinateTrace formal interface covers that latter mixing statement; it does not separately certify a production point-query compiler.

This makes an on-demand ordering API a concrete application hypothesis. The older primary cell-probe paper records an O(log^2 n) upper bound and distinguishes cell probes from bit probes. The source's O(log n) corollary is an improvement claim conditional on its proof, not an independently accepted finding here. [Earlier primary paper, version-one PDF](https://arxiv.org/pdf/2512.02724v1).

## Problem and buyer

A data-infrastructure or large simulation team may need a few reproducible positions from a huge shuffled index space, inverse lookup, or a resumable random test schedule. Materializing an entire index array can be wasteful when only a small portion is queried. A fully stored int64 array for 2^30 slots occupies 8,589,934,592 bytes before other overhead; this is a representation cost, not a lower bound on every sampler. Candidate buyers must already have a sparse access workload whose memory, restart or inverse-lookup cost matters.

## What the finding could enable

A framework could expose point(i), inverse(j), an immutable epoch plan and disjoint slot-based shard views. Shared switch addresses let every worker see the same permutation; reverse layer order gives inverse access. With a separately validated universal sweep count and independent fair-bit backend, the source could support an approximate-uniform full-law claim without constructing the full index table. The references supply switching/replay, exact tiny laws, decimal-wire queries, a seeded keyed backend and local append-only OS-bit assignment. Actual independent fairness, the universal threshold and a distributed data loader remain unverified.

## Technical and commercial limits

[queryable_permutation_reference.py](../../tools/queryable_permutation_reference.py) accepts explicit sparse bit values, supports forward/inverse queries on dimensions up to 63, and returns unknown for missing bits or budget exhaustion. It caps 64 sweeps, 256 queries, 100,000 supplied bits, four million lookups/image evaluations and 5,000 retained trace records. Exact whole-law calculation is limited to at most eight slots, eight sweeps and 50,000 states; it can exhaust earlier. Replay uses deterministic supplied values and establishes no randomness distribution. Trace truncation does not truncate successful query results.

A short seed is a material bridge failure for the source's statistical claim. If a fixed deterministic system has only a b-bit seed as randomness, it can output at most 2^b permutations. Its statistical total variation from uniform is at least max(0,1-2^b/n!). For 64 slots, a 256-bit seed already forces a distance greater than 0.999. This is a support fact, not a cryptographic-security conclusion or a criticism of seeded training goals that require different guarantees. Lazy independent-bit storage preserves the intended model but its cache can grow substantially as more of the domain is queried.

Non-dyadic cycle restriction preserves bijection but is an additional conventional construction. Worst-case access can require n-m+1 full-permutation calls for m retained slots, so logarithmic worst-case access does not automatically survive. On the four-slot one-sweep fixture restricted to three slots, TV is 1/12 and marginals are biased, despite exact single-card uniformity on the full four-slot domain. Training quality, balanced batches, padding, fault recovery and security are separate obligations.

The [provider reference](../../tools/permutation_provider_reference.py) adds canonical decimal-wire requests, a fixed plan identity, 256-bit HMAC mapping or local POSIX locked append-only bit assignment. Sixty-two initial and eleven post-fix controls cover ordering, restart, two local processes, capacity, exact 63-bit indices and refusal to change damaged/mismatched stores. This is local consistency evidence, not a distributed service, source mixing or security certificate. Hash-linked records are not authenticated against rewriting or tail removal.

The [measured synthetic case](../../prototypes/permutation-provider-benchmark-2026-10-09-v2/measurements.json) has 256 slots/two sweeps: 16 sparse points retained 249 switches/35,972 file bytes, while materializing the same permutation reached 2,048 switches/293,486 bytes. A packed int64 index array is 2,048 bytes. This JSON backend loses that storage comparison. A needless 8 MB loader allocation was found and corrected; repeated sparse traced Python peak is 43,318 bytes, while full reload/parsing remains heavier. These are one small synthetic observation with a simple oracle, not a production speedup or real dataset benchmark.

## Minimal architecture

Immutable plan (domain, coordinate convention, sweep count, epoch and bit-source revision) -> shared switch provider -> point/inverse path evaluator -> optional cycle restriction -> disjoint logical-slot shard adapter -> replay and model report. A fair-bit provider must assign each key (epoch,sweep,coordinate,pair) one stable bit; changing it between queries can destroy the intended joint output. A seeded provider must visibly use a separate randomness/guarantee model. Do not make a production memory or latency promise before measuring lookup/cache cost.

## Existing alternatives and differentiation

PyTorch's current DistributedSampler implementation generates a randperm index list and then pads or drops indices before rank slicing. It is a substantial baseline, including equal-length shard behavior. A sparse point/inverse API would need to improve a real workload while preserving the chosen batching policy. [Primary implementation](https://github.com/pytorch/pytorch/blob/main/torch/utils/data/distributed.py).

Random123 already provides stateless counter/key pseudorandom generators. Such a provider can be practical for reproducible switching bits but does not become the source's independent fair-bit oracle or preserve its statistical full-law guarantee merely by passing RNG tests. The library itself excludes cryptographic use. The proposed difference must be useful permutation/inverse/shard behavior plus honest guarantee tracking, not a new RNG. [Random123](https://github.com/DEShawResearch/random123).

## Monetization hypothesis

Hypothesis: AUD 8,000–20,000 for a data-access benchmark and adapter, only after a team shows a recurring sparse lookup problem. At an assumed AUD 12,000 fee and 40 hours at AUD 180/hour, AUD 4,800 remains before support, sales and overhead; 70 hours exceed the fee. No quote, interview, workload or paid engagement exists. An open research SDK may be more appropriate until a measurable advantage is shown. Do not count the shared evidence adapter as a second customer subscription.

## Validation experiment

[176 finite controls](../../snapshots/2026-10-08-baseline/queryable-permutation-validation-2026-10-09-v1.json) compare independent physical-shuffle all-coin enumeration with coordinate laws, materialized switching with point/inverse replay, cycle deletion, missing-input/budget failures and a sparse 63-bit path. One sweep has uniform one-card marginals but full-law TV 1/3 on four slots and 283/315 on eight. Four/six sweeps on four slots have TV 1/192 and 1/3072 respectively. The trace target there is 1/2048; four and five sweeps fail, while six pass that one instance. No universal sweep selection follows.

[21 entropy controls](../../snapshots/2026-10-08-baseline/permutation-entropy-validation-2026-10-09-v1.json) verify exact small support bounds and symbolic large-domain arithmetic. A [63-bit sparse replay](../../prototypes/coordinate-sparse-63bit-2026-10-09-v1.json) uses 126 switch lookups in each direction with two sweeps, but those deterministic values do not demonstrate uniform mixing. Next compare a sparse access workload with the existing sampler under identical batching, randomness and restart requirements. Measure total memory, lookup latency, cache growth and numerical/model gaps; record training outcomes only if a training experiment actually runs.

## Conditions to reject or defer

Defer the source statistical guarantee until P/u and the exact implementation/randomness bridge are validated. Reject a short-seed claim of statistical closeness to the full uniform permutation law when the support bound rules it out. Reject the memory-saving product hypothesis for workloads that query the whole domain and require a large persistent fair-bit cache, or if existing seeded permutation methods already solve sparse access cheaper. Defer non-dyadic worst-case latency, balanced distributed batching and security claims until separately justified. A short query-depth theorem alone is not an end-to-end speedup.

## Next concrete action

Run [the decimal-wire seeded fixture](../../fixtures/permutation-provider-seeded-63bit-2026-10-09-v1.json) under the provider reference. Choose a realistic sparse access/inverse/resume task, implement a compact keyed store, and compare it with an appropriate existing baseline under the same provider and batching requirements. Read the [selected contraction audit](../../plans/coordinate-contraction-review-2026-10-09-v1.md): eventual thresholds and a classically selected full-group minorant still leave numerical P open. The local append store and seeded mapping are implemented, but no source proof, full distributed SDK, real data task, customer pilot or security evaluation has been completed.

## Pinned source evidence

- [Signed companion](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/Signed-tensor-densities-and-diagram-budgets-for-coordinate-sweeps-September-26-2026/paper.pdf): full introduction/preliminaries and amplification/query section lines 320–462 read.
- [Trace companion](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/Random-subspace-tests-and-trace-smoothing-for-coordinate-sweeps-September-26-2026/paper.pdf): abstract, full introduction and closing induction lines 548–633 read. The paper chooses large range/base thresholds and a bounded exponent product; no usable numerical P was selected here.
- [Selected family scope](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/lean/docs/238.md), [CoordinateTrace challenge](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/lean/ComparatorChallenges/CoordinateTrace.lean), [solution](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/lean/OAI/Probability/ThorpRouting/RegularTrace.lean): selected source inspection, not kernel or program verification.