# Queryable permutation SDK: reviewable implementation specification

This specifies dossier 040's candidate framework. The [finite reference](../tools/queryable_permutation_reference.py) implements shared-switch replay, small exact laws and seeded-support bounds. A separate [provider reference](../tools/permutation_provider_reference.py) now implements decimal-wire point/inverse access with a seeded keyed backend or local locked append-only store. Distributed shard and data-loader interfaces remain a specification. 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.

The new provider reference validates canonical decimal wire indices and stored pair addresses as exact Python integers; production adapters should preserve that format: the Python reference accepts exact JSON integers, while JavaScript Number cannot represent every 63-bit integer. A browser or cross-language adapter must still 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 | Local OS-entropy assignment/locking/restart tested; independent fairness, network/power-loss behavior and compact cache remain 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 | HMAC-backed finite reference implemented; no transfer of independent-bit full-law theorem or security claim; realistic quality/cost pending |

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; selected Harmonic contraction excerpts use eventual thresholds and finite positive minima. The gap minorant uses a classically selected convolution exponent/full-group minimum. Numerical coefficients and a useful u/P were not selected here. [Exact reviewed extents](coordinate-contraction-review-2026-10-09-v1.md). 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. One synthetic 256-slot sparse/full observation is now saved; realistic task, shard policy and production-baseline measurements remain pending. [176 protocol controls](../snapshots/2026-10-08-baseline/queryable-permutation-validation-2026-10-09-v1.json) and [21 entropy controls](../snapshots/2026-10-08-baseline/permutation-entropy-validation-2026-10-09-v1.json) 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](../opportunities/040-queryable-permutation-framework/2026-10-09-v2.md).

## Implemented local provider and measured boundary

[62 provider controls](../snapshots/2026-10-08-baseline/permutation-provider-validation-2026-10-09-v1.json) include two local processes using one POSIX locked file, reordered queries and restart/inverse composition. New rows are persisted before their bit is returned. Files are bounded to 100,000 rows/8 MB, each batch to 256 requests/four million switch lookups, and lock waits to at most five seconds (default one). The loader validates the plan and canonical/hash-linked rows; mismatched, duplicate or incomplete data is refused, with bytes preserved. Interrupted writes, remote filesystems, rogue writers, external rollback and power loss require a separate protocol. Hash chaining is not authenticated history, and an unanchored tail removal is undetectable.

The [synthetic repeated run](../prototypes/permutation-provider-benchmark-2026-10-09-v2/measurements.json) retained 35,972 bytes for 249 switches after 16 sparse queries, and 293,486 bytes for all 2,048 switches after materialization on 256 slots/two sweeps. The packed int64 index representation is 2,048 bytes. This JSON backend has a concrete unfavorable storage cost at that scale; compact encoding and larger sparse workloads remain open. Tracemalloc observes Python allocations, not RSS or total service memory. The original 8 MB loader buffer was corrected and both runs are retained; timings are single dependent phases with a simple Python oracle, not an optimized sampler comparison or speedup evidence. [Post-fix controls](../snapshots/2026-10-08-baseline/permutation-provider-hardening-validation-2026-10-09-v1.json).