✗ Failed on benchmark 2026

Sharp JL Hidden-State Bottleneck

Implementation & benchmark of arXiv:2608.13782 — The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma

Usefulness7/10

Difficulty5/10

Novelty5/10

Architecture Memory Speedup Accuracy Transformer Attention Mlp Embedding Inference speedup Linear algebra Metric geometry Probability Approximation theory

Source paper: The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma arXiv:2608.13782 ⓘ · analyzed Sep 1, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Insert a linear Johnson–Lindenstrauss bottleneck around a set of jointly processed representations, choosing its width from the sharp finite-set dimension bound rather than from the model's nominal hidden size. The projection should preserve pairwise distances between tokens, patches, or retrieved items, allowing a downstream attention or MLP block to operate at lower width while retaining the geometry relevant to similarity computations.

Formulas

$$\lambda\left\lVert x-y\right\rVert_{2}\leq\left\lVert f(x)-f(y)\right\rVert_{2}\leq(1+\varepsilon)\lambda\left\lVert x-y\right\rVert_{2},\qquad \forall x,y\in X.$$

$$r=\Theta\left(\min\left\{d,n-1,\frac{\log(2+\varepsilon^{2}n)}{\varepsilon^{2}}\right\}\right).$$

$$P_{ij}\sim\mathcal N(0,1/r),\qquad z_i=Px_i,\qquad \widehat d_{ij}=\lVert z_i-z_j\rVert_2.$$

Mathematical statement

The paper defines distortion at most 1+epsilon by requiring a scale lambda>0 such that lambda ||x-y||_2 <= ||f(x)-f(y)||_2 <= (1+epsilon) lambda ||x-y||_2 for every pair x,y in an n-point set X subset R^d. Its sharp dimension bound is r = Theta(min{d, n-1, log(2+epsilon^2 n)/epsilon^2}), and the upper bound is attained by a linear map. Here x and y are input representations, d is their original feature dimension, n is the number of representations whose mutual geometry must be preserved, epsilon is the allowed relative distortion, and r is the projected dimension. Use a Gaussian linear map P in R^{r x d}, with P_ij sampled independently from N(0,1/r), so that f(x)=Px approximately preserves Euclidean norms and pairwise distances. The theorem supplies the functional width rule, while the hidden absolute constant in Theta must be selected empirically.

Implementation notes

(1) Integration point: place a frozen or trainable projection P immediately before a width-sensitive block, such as self-attention or an MLP, for a tensor X with shape [batch,n,d]. In the first MVP, use a frozen Gaussian P and make the downstream block operate at width r. Compute r = ceil(C * min(d, n-1, log(2 + epsilon^2*n)/epsilon^2)), with C in {1,2,4} because the theorem hides constants, and cap r at d. (2) Pseudocode: sample P[i,j] from Normal(0,1/r); compute Z = X @ P.T; run the compressed attention or MLP on Z; optionally reconstruct Y = Z @ Q.T if the following block requires width d. During training, add L_dist = mean over sampled pairs of (||Z_i-Z_j||_2/(||X_i-X_j||_2+delta)-1)^2, with a small delta for numerical stability. (3) The mathematical calculation is the width schedule and target distortion definition. Estimate empirically the distortion ratio rho_ij = ||Z_i-Z_j||_2/(||X_i-X_j||_2+delta), its 95th percentile, downstream task loss, and activation memory. Compare frozen Gaussian, orthogonal-row, and learned projections. (4) First experiment: use a small Transformer on CIFAR-10 patch tokens or a two-layer language model on WikiText-2. Compare the original width against epsilon values 0.1, 0.2, and 0.3 and C values 1, 2, and 4. Measure validation accuracy or perplexity, pairwise-distance distortion, activation memory, and throughput. Success means at least 1.5x lower activation cost with less than 1% relative accuracy loss, and a transition in useful width near the predicted min of d, n-1, and epsilon^{-2} log(2+epsilon^2 n).

Verification

Failed on benchmark

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

Stage 2 · Practical benchmark result: No measurable effect

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Built and verified a frozen Gaussian JL hidden-state bottleneck with the sharp finite-set width rule. The core predictions were observed: mean squared norm ratio 0.986 versus 1, fixed-pair ratio SD 0.1235 versus the predicted 0.125 at r=32, and finite-set distortion decreased approximately with the predicted r^{-1/2} trend; the schedule also saturated at n−1 and d as expected. In the toy downstream task, projected representations preserved 100% validation accuracy at r=16–23 versus full width d=96, giving 4.2–6x lower activation width, but no realistic Transformer or speed benchmark was tested.

Agent confidence: 8/10

Baseline: Full-width d=96: validation accuracy 1.000, validation loss 0.000807, activation width 96.
Idea: Best narrow settings retained accuracy 1.000: epsilon=0.3,C=1,r=16 (width ratio 0.167, p95 absolute pair distortion 0.358, loss 0.000849) and epsilon=0.1,C=1,r=23 (width ratio 0.240, p95 distortion 0.278, loss 0.001945). At epsilon=0.2,C=4,r=92, p95 distortion was 0.161 and loss 0.000678.

Limitations: The downstream task is synthetic and linearly separable, so accuracy is not a stringent test of representation quality. No CIFAR-10/LM Transformer, wall-clock throughput, actual attention/MLP memory, learned or orthogonal projections, repeated seeds, or rigorous high-probability distortion certification was evaluated; the finite-set maximum-error scaling comparison is a heuristic concentration-scale check rather than a theorem-tight constant test.

How to run: python3 run_experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.13782) Sep 2, 2026

Ahead of the baseline (−1.4%) but not statistically significant (p=0.6679, wins 5 / 8 paired seeds).

Benchmark: Sequence modeling
Model: transformer_tiny
Paired seeds: 8
Baseline mean: 0.4544
Idea mean: 0.4479
Effect (Δ): -0.0065 (−1.4%; negative = idea better)
Wins: 5 / 8 paired seeds
p-value: 0.6679 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±7.9%
Mechanism: Not confirmed ✗
Practical effect: No effect
Baseline tuning: swept over 3 configs

Limitations:

Only the built-in sequence track was tested. The full protocol used 400 training and 200 test examples, epsilon=0.30 and C=1, and did not separately measure wall-clock throughput or activation memory. The observed signature used trained scalar-input token embeddings, which were nearly collinear and therefore did not provide a strong isotropic JL test.

How to run: python3 stage2_jl_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Sep 1, 2026 latest Failed ✗

Agent confidence: 9/10

The Sharp JL Hidden-State Bottleneck was implemented as a frozen Gaussian projection inside the matched sequence-level transformer and evaluated with the full 8-seed paired protocol. It slightly reduced mean test MSE, but the paired permutation test was not significant and the trained-model mechanism signature was not quantitatively confirmed. Therefore the benchmark does not establish a real win.

Baseline: transformer_tiny sequence track; tuned lr=0.001, epochs=12; mean test MSE 0.45439932495355606 across 8 seeds.
Idea: Frozen Gaussian JL bottleneck; epsilon=0.30, C=1, projected width r=18 versus d=64; best lr=0.003, epochs=12; mean test MSE 0.4479260928928852 across 8 seeds.
Paired delta: -0.006473232060670853; permutation p=0.66785; 5/8 idea wins.

Benchmark result