Pisot-Orbit Deterministic JL Layer
Implementation & benchmark of arXiv:2608.13078 — Deterministic Johnson--Lindenstrauss Projections from Pisot $β$-Transformations for Zero-Knowledge Private Routing
Source paper: Deterministic Johnson--Lindenstrauss Projections from Pisot $β$-Transformations for Zero-Knowledge Private Routing arXiv:2608.13078 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Replace a dense random projection used before retrieval, classification, or expert routing with a publicly reproducible matrix generated by a Pisot beta-transformation orbit. Search over a small public seed and sampling gap to select one matrix that preserves the calibration set's pairwise distances, then freeze it for training and inference. The projection removes random-matrix storage and makes the same embedding transform exactly reproducible across servers or proof systems.
Formulas
Mathematical statement
Let beta>1 be a Pisot number, meaning an algebraic integer whose non-principal Galois conjugates have modulus strictly less than one. Define the beta-transformation on the unit interval by T_beta(u)=beta u-floor(beta u), and let u_t=T_beta^t(u_0) be its orbit from seed u_0. Convert consecutive orbit values into centered, unit-variance coefficients z_t=(u_t-mu)/sigma, where mu and sigma are the empirical mean and standard deviation of a long calibration orbit. Form a projection P in R^{m x d} by P_{r,i}=z_{s+(r-1)g+i}/sqrt(m), with seed offset s and sampling gap g; rescale P once so that the squared-norm estimator targets the original squared norm. The spectral-gap argument gives geometrically decaying correlations, so the estimator has bias bounded by |E[||Px||_2^2]-||x||_2^2| <= C rho^g ||x||_2^2 for 0<rho<1, and variance bounded by Var(||Px||_2^2) <= (V_0/m)||x||_2^4. Here C depends on the observable and the beta-map spectral gap, rho is its correlation-decay factor, V_0 is dimension-independent under the paper's concentration hypothesis, m is the projected dimension, and x is the input vector. For a finite set of N calibration vectors, search over seed s and gap g and minimize maximum pairwise distortion. In a finite-field implementation, replace real orbit arithmetic with the exact recurrence induced by beta's minimal polynomial and perform arithmetic modulo the circuit field.
Implementation notes
(1) Integration point: insert the fixed projection immediately after a high-dimensional embedding or pooled transformer representation and before cosine retrieval, nearest-centroid classification, or an MoE router. For a 768-dimensional embedding and m=128, use a 128x768 deterministic matrix. During training, freeze this projection initially; optionally add a learned diagonal scale after projection so the representation can compensate for mild anisotropy without learning a full dense matrix. (2) Pseudocode: choose beta, seed u0, offset s, and gap g; iterate u=T_beta(u) and collect at least m+d orbit values; compute mu and sigma on a long burn-in orbit; set P[r,i]=z[s+(r-1)*g+i]/sqrt(m); compute a scalar alpha from calibration data using alpha^2=(sum_a ||c_a||_2^2)/(sum_a ||P*c_a||_2^2); output y=alpha*P*x. Enumerate several hundred seeds and gaps, evaluate maximum relative pairwise centroid distortion, and freeze the best matrix. (3) Compute from the mathematics: the beta orbit, centered coefficients, projection entries, and the proposed geometric dependence on g. Estimate empirically: mu, sigma, alpha, the best seed, pairwise distortion, and V0 from held-out vectors. Measure correlation decay by estimating |corr(z_t,z_{t+k})| and fitting an exponential envelope A*rho^k. For a proof-oriented prototype, implement the orbit with fixed-point or finite-field arithmetic and compare projection hashes across machines. (4) First cheap experiment: use CIFAR-10 class embeddings or a small language-model retrieval benchmark; compare against Gaussian JL, sparse JL, and a learned linear projection at equal m. Measure retrieval recall, centroid accuracy, maximum pairwise distortion, projection-generation time, stored bytes, and downstream training loss. Success means matching Gaussian-JL accuracy within measurement noise while being exactly reproducible, reducing generation or commitment cost, observing approximately geometric bias reduction with larger g, and observing variance proportional to 1/m.
Verification
Stage 1 · Toy mechanism gate: Failed ✗
Stage 2 · Mechanism transferred to benchmark: Not tested
Stage 2 · Practical benchmark result: Not run
Methodology: Toy-system gate first; the benchmark stage runs only after a pass. How verification works
Stage 1 — Mechanism check agent confidence 9/10
Built a deterministic Pisot-orbit JL layer using the golden-ratio beta transformation, empirical centering/scaling, scalar norm calibration, seed/gap search, reproducibility hashing, and Gaussian-JL comparison. Correlations decayed strongly after a short transient and calibration search improved worst pairwise distortion from 1.891 to 0.522, but the global correlation fit was non-decaying (rho≈1.0001) and norm-estimator variance scaled with slope -0.72 rather than the predicted -1.0. Under the required mechanism criterion, this is not a validated win.
- Agent confidence
- 9/10
- Baseline
- Gaussian JL, d=24,m=16: max pairwise distortion 2.021, mean 0.288.
- Idea
- Fixed Pisot orbit: max pairwise distortion 1.891, mean 0.396; searched seed/gap: max 0.522, mean 0.189 at gap=2; global correlation fit rho=1.0001, post-transient rho=0.898; variance-vs-m slope=-0.724.
Limitations: Only a small synthetic Gaussian-vector experiment was tested; no CIFAR, retrieval, classifier, router, learned post-scale, sparse-JL comparison, GPU benchmark, exact finite-field implementation, or proof of the stated spectral-gap bounds was performed. The calibration search uses the same small calibration set for selection and evaluation, so its distortion improvement may overfit.
How to run: python3 compare.py
Verdict computed by deterministic test code from paired-seed statistics — not by the language model.
Artifacts
- compare.py 2.3 KB View Raw
- experiment.py 4.8 KB View Raw
- report.md 1.5 KB View
- results.json 3.2 KB View Raw