On this page
Queryable permutation SDK: reviewable implementation specification
This specifies dossier 040's candidate framework. The finite reference implements shared-switch replay, small exact laws and seeded-support bounds. It does not implement these provider or distributed SDK interfaces. No universal numerical sweep count, source proof, realistic workload or commercial advantage has been verified.
Task and user outcome
Given a fixed logical index space, return a few shuffled positions or inverse positions consistently across queries, restarts and workers. A successful adapter avoids building an unnecessary full index table for a sparse access workload and preserves the batching/reproducibility behavior the user actually needs. A source statistical full-law guarantee and a useful deterministic seeded order are separate product modes.
Plan record
The plan is immutable by edition. It contains plan ID, input-to-output convention, dimension d, target size m<=2^d, complete sweep count, epoch ID, provider kind/revision, implementation hash and source-assurance status. The provider namespace includes the immutable plan/epoch and each key (sweep,coordinate,pair). Forward and inverse endpoints use the same provider assignment. Dataset membership/order must remain fixed; a changed dataset gets a new plan.
Production wire indices and pair addresses should be decimal strings: the Python reference accepts exact JSON integers, while JavaScript Number cannot represent every 63-bit integer. A browser or cross-language adapter must explicitly validate/parse the string to an exact integer. Reject fractions, signs where disallowed, noncanonical strings and out-of-domain indices. Do not claim wire compatibility merely because Python replay passes.
Provider interfaces and guarantees
| Provider | Required behavior | Suitable claim | Open work |
|---|---|---|---|
| Immutable explicit bit map | One fixed 0/1 per key; missing key returns unknown | Exact deterministic replay for supplied paths | Implemented by finite reference; no bit distribution established |
| Authoritative lazy independent-bit store | Generate a fair bit once per new key, retain it and serve that same value to every worker/restart | Intended source model, conditional on actual independent-bit backend and validated sweep threshold | Backend randomness, atomic persistence, cache growth and cost are unverified |
| Seeded counter/key provider | Stable deterministic function of plan seed and key, shared across workers | Reproducible permutation structure if the switching implementation is correct | No transfer of independent-bit statistical full-law theorem; practical ordering quality/cost must be measured |
A b-bit seed alone has at most 2^b output permutations and cannot be statistically close to all n! possibilities when the support bound is near one. This does not prevent seeded modes from serving goals that do not require that full statistical guarantee. A lazy store cannot obtain replay consistency merely by using the same sequential RNG seed in workers with different query orders: key assignment must have one authoritative value or a separately defined deterministic keyed mapping.
Endpoint behavior
point(plan, index)follows complete forward sweeps. With m=2^d it uses exactly vd switch lookups; missing input or exhausted work returns unknown, not a fabricated index.inverse(plan, index)reverses both sweep and coordinate order using the same switches. It should compose with point to the original index under one immutable plan.- For m<2^d, both endpoints delete outside elements from cycles by repeated full-permutation calls. Worst case is 2^d-m+1 calls, so a logarithmic worst-case claim requires a separate bridge or a different model.
shard(plan, rank, world_size)assigns disjoint logical input slots, then maps those slots through point. Ranks with unequal sizes may produce different batch counts. Padding, dropping and distributed training synchronization must be chosen explicitly and compared under the same policy.- A report names the implementation/provider revisions, work budget, completed/unknown results, retained trace limits, observed finite evidence and unresolved source obligations. Successful replay is not a mixing certificate.
Source assurance gate
The selected CoordinateTrace statement requires independent fair switches, dyadic slots and an integer v with 2v>=P for a universal P. Its source solution obtains P=2u from an imported tail estimate; numerical contraction coefficients and a useful u/P were not selected here. A point-access corollary is described in the companion paper and is not a separate verified SDK compiler.
The exact four-card source target is 1/2048. Four/five sweeps fail it, while six pass that single finite instance. One-card uniformity also does not imply a small full-law error: the eight-card one-sweep TV is 283/315. Keep global source-assurance status unknown until the chosen threshold, exact randomness and code correspondence are independently established.
Acceptance experiment
Use one fixed sparse-query workload and one full-domain workload, with the same logical dataset/order, epoch semantics, rank batching and provider requirements in each compared implementation. Record end-to-end peak memory, retained random-state/cache bytes, CPU and storage/network lookup latency, restart replay, point/inverse composition, shard coverage and duplicates, and unknown/budget behavior. A generated workload establishes engineering behavior only; select a realistic public task before claiming business value.
Do not compare a source-model fair-bit store with a tiny-seed baseline while presenting the randomness cost as equivalent. Do not turn a second exposure to the same workload into independent performance evidence. No benchmark values are filled in until those runs exist. 176 protocol controls and 21 entropy controls provide small reference cases.
Business decision
Proceed with a sparse-access adapter only if measured memory/restart/inverse value exceeds provider, cache and support cost. Defer a source-guaranteed seeded data loader and any security claim. Reject the candidate if existing permutation/RNG tooling already meets the chosen task cheaper, fair-bit persistence erases savings, or bespoke integration consumes the hypothetical fee. Dossier and earning assumptions.