Memory Sample Tradeoff: Why Perfect Gaussian Measurements Still Demand More Samples

A stack of exact Gaussian equations can pin down an unknown vector after just as many measurements as it has coordinates. Put those same equations through a learner that can read each pair only once and retain at most a fixed multiple of the dimension squared in bits, and the precision changes what it needs. OpenAI’s September 2026 preprint proves a memory sample tradeoff for noiseless Gaussian regression. In sufficiently high dimension, achieving angular error at most $\epsilon$ with probability at least two thirds requires a sample horizon of at least a constant times $d\log(1/\epsilon)$, where $d$ is the dimension. Each label can carry arbitrarily fine information. The proof measures how much of that information can influence the estimate after repeated finite-state updates.

1. What Is the Memory Sample Tradeoff in Noiseless Gaussian Regression?

An exact label supplies a linear constraint on the signal. After the learner reads that constraint, any influence it has on later computation must pass through the persistent state or the decision to stop. Success means recovering the direction of the signal on the unit sphere to a prescribed angular tolerance.

The theorem concerns the deterministic deadline by which the learner must stop. A learner may end some runs earlier. This matters when reading the result as a statement about Gaussian regression sample complexity. The lower bound applies to the allowed horizon of any learner meeting the success guarantee.

2. Why $d$ Exact Gaussian Measurements Normally Determine the Signal

Let $s$ be the unknown unit vector. Each independent standard Gaussian row $x_t$ has covariance $I_d$, the identity matrix. The observation model is

Stack $d$ rows into a square matrix $X$ and the labels into a vector $y$. Each new row avoids the span of the preceding rows with probability one, because a proper linear subspace has Gaussian measure zero. Thus $X$ is invertible almost surely, and the retained system $Xs=y$ has the unique solution $s=X^{-1}y$.

For a small example, take rows $(1,1)$ and $(1,-1)$ with labels $7/5$ and $-1/5$. Adding and subtracting the two equations recovers the unit vector $(3/5,4/5)$. These are illustrative rows. In the Gaussian experiment, the independence of the row directions needed to solve the full system holds almost surely. The example shows what a solver needs from both observations. It must preserve enough information to combine their constraints. An exact real entry can require arbitrarily many bits to retain.

3. The Finite-Memory Learner and What It Can Remember

A learner with $M$ bits has at most $2^M$ persistent states at each index. Its rules may depend on dimension, accuracy and sample index. It can examine the entire current pair, use fresh randomness and compute without a time bound before retaining its next state. The initial state and any shared seed that selects the rules are jointly independent of the signal and all Gaussian rows.

The learner reads the stream in order, can stop at index zero, and must stop by a prescribed finite horizon $T$. Given the shared seed, the output rule uses the terminal state, the stopping index and fresh randomness to produce a unit vector. The stopping index can itself carry information, so the proof counts distinct stopping times alongside memory states.

The paper also imposes joint measurability on the experiment and requires Borel or reference-measure-completed transition and stopping probabilities at fixed seeds, states and indices. The proof handles completed-measurable rules by replacing them with Borel versions for almost every shared seed, preserving success averaged over the sphere. The model isolates persistent storage as a resource in streaming linear regression and memory-bounded learning.

4. The Main Theorem on Precision and $\Omega(d\log(1/\epsilon))$ Samples

Theorem 1.2 fixes any finite $A>0$. There are constants $c_A>0$ and $d_A$ such that for $d\ge d_A$, integer $0\le M\le Ad^2$, and $0<\epsilon\le 1/10$, the following implication holds. Draw $S$ uniformly from the unit sphere, independently of the rows and the learner’s data-independent randomness. If the unit output $\hat{s}$ meets the guarantee below, the horizon obeys the stated lower bound.

The angle is in radians. The probability averages over the signal, rows and learner randomness. A guarantee of at least two thirds for every fixed signal implies the average guarantee. For $M=o(d^2)$, the constant can be absolute once the dimension is sufficiently large for the given memory sequence.

For example, tightening the tolerance from $10^{-2}$ to $10^{-4}$ changes the natural logarithm from $2\log 10$ to $4\log 10$. At fixed dimension and memory cap, that doubles the theorem’s lower-bound expression. The bound leaves the optimal horizon unspecified.

5. What Earlier Noisy Regression Lower Bounds Could Not Establish

In 2019, Vatsal Sharan, Aaron Sidford and Gregory Valiant studied memory-constrained linear regression with the same isotropic Gaussian covariates and independent uniform additive noise of half-width $2^{-d/5}$. Their lower bound was $\Omega(d\log k)$ at Euclidean tolerance $d^{-k}$, for memory at most $d^2/4$ bits and $k$ from a sufficiently large constant up to order $d/\log d$.

An exact-data learner can generate independent noise inside its current transition and simulate a noisy-data learner with the same state budget. A lower bound for the noisy task leaves open whether a learner could exploit exact labels to use fewer samples. A lower bound for the exact task can carry over to that noisy experiment under the appropriate model and accuracy conversion.

6. Why Exact Observations Break the Usual Posterior-Density Argument

After seeing a raw pair $(x,y)$, the compatible signals lie where the unit sphere intersects the hyperplane $\langle x,s\rangle=y$. This section has zero mass under the original sphere prior, even though it contains the conditional signal almost surely. The raw-data posterior is therefore singular relative to the original spherical measure.

The proof instead fixes a state and index and asks a different question. For each signal $s$, what is the chance of success if the learner starts in that state and receives fresh future rows? Call this probability $h(s)$. Integrating $h$ against the original sphere prior weights signals by their future success. This includes states the learner never visits. Defining the continuation this way lets the proof work backward from the output rule without conditioning the prior on past observations.

7. Step One: Measure Successful Signals Using Local Spherical Mass

Let $\sigma_d$ denote uniform probability on the sphere and $B(z,r)$ the closed Euclidean ball of radius $r$ centered at a sphere point $z$. The ball cuts out a spherical cap of mass at most $r^{d-1}$. For $r\le1$, one can see this by projecting the cap onto the coordinate plane perpendicular to $z$. Its projected radius is at most $r$ and its surface-area factor is at most two. For larger radii, the total mass bound of one suffices.

For a fixed terminal output, successful signals have chord distance at most $\epsilon$ from that output, because chord distance is at most angular distance. Averaging over the terminal output distribution preserves the resulting global mass bound $\epsilon^{d-1}$. Inside any $B(z,r)$, the successful mass is also at most $r^{d-1}$ since $h\le1$. The smaller bound is at most their geometric mean. This initializes the invariant

at $R=\epsilon$. Here $R$ controls how concentrated successful mass may be, through an upper bound on the mass inside every test ball. The inequality must hold at every radius so the next step can restrict the measure to any ball and still control its mass on smaller balls.

8. Step Two: Control Exact Gaussian Projections Using Gram Determinants

Fix a destination and restrict its success-weighted measure to $B(z,r)$. Denote the resulting finite measure by $\mu$. Write $G$ for the Gaussian matrix of a block of $m$ rows, reserving $A$ for the memory-cap constant. The exact data map is $s\mapsto(G,Gs)$. The proof bounds the density of the joint image measure relative to Gaussian matrix probability times Lebesgue measure on the labels.

The density calculation starts by smoothing the labels with a Gaussian of variance $\delta^2$ in each coordinate. This is a proof device that is removed in the limit. To bound the $q$th moment of the smoothed density, expand it using $q$ copies $s_1,\ldots,s_q$ integrated against $\mu$. For $V=[s_2-s_1,\ldots,s_q-s_1]$, the zero-density calculation for the Gaussian label differences is controlled by $\det(V^{\mathsf T}V)^{-m/2}$. Gram–Schmidt writes the determinant as a product of squared distances from each new point to the affine span of the preceding points.

Small distances could make those inverse powers large. The local mass bound controls how much measure can lie in a thin tube around each affine span. For a tube of width $\rho$ around a $j$-dimensional affine span, covering the relevant portion of the tube takes order $(r/\rho)^j$ balls of radius proportional to $\rho$, with dimension-dependent constants. The resulting mass bound decays like $\rho^{a-j}$. This decay makes the inverse $m$th moment finite when $a-j>m$, which holds for the block lengths and moment order used in the proof. The resulting bounds are uniform as $\delta$ tends to zero. Testing against continuous functions of compact support then gives an $L^q$ density for the exact data.

9. Step Three: Why Projected Ellipsoid Volume Cancels the Density Loss

Each destination density has an $L^q$ bound with a factor $R^a r^{a-m(1-1/q)}$. All these densities are supported in the same set of matrix–label pairs. For fixed $G$, the label region is the ellipsoid $Gz+GB(0,r)$. Almost surely, its semiaxes are $r$ times the $m$ singular values of $G$, so the label volume scales as $r^m$. After averaging over $G$, the joint reference measure of the support is at most $C_E^d r^m$ for an absolute constant $C_E$.

Hölder’s inequality pairs each density with its routing probability. A second application across destinations collects the routing terms. Their sum of conjugate powers is at most one at any data point, since raising numbers in the unit interval to a power greater than one can only decrease them and the probabilities sum to at most one. The resulting support-volume factor is raised to $1-1/q$. Multiplying the radius factors gives

The same radius power returns in the bound before the block, so it can be used again at the preceding boundary. Density control alone would leave the wrong power of $r$.

10. Step Four: How Finite Memory Forces the Backward Sample Bound

A block of $m$ observations has at most $m+1$ local stopping indices, including its entrance. Each stopping index contributes up to $2^M$ terminal states. Continuing past the block contributes at most another $2^M$ states. Thus the number of destinations is $N\le(m+2)2^M$, even though the block may route using its entire real-valued data.

Hölder across destinations costs a factor $N^{1/q}$ in the local mass bound. Taking the $a$th root to update $R$ changes this to $N^{1/(aq)}$. With $q=\lfloor(d-1)/8\rfloor$, both $a$ and $q$ grow proportionally to $d$. Consequently the logarithm of the scale multiplier per block is at most $C(1+M/d^2)$ for an absolute constant $C$. The finite state contributes through its logarithmic size, which explains the quadratic memory scale in this argument.

Starting at the last block with $R=\epsilon$, each backward step can multiply the scale by at most a constant for fixed $A$. A ball of radius two centered at any sphere point covers the whole sphere. Average success of at least two thirds forces the initial scale to reach a positive constant. If $K_A$ bounds the scale multiplier and $B=\lceil T/q\rceil$ is the block count, then the initial scale is bounded by $\epsilon K_A^B$. To reach constant success, that upper bound must itself be at least a positive constant. Taking logarithms forces $B$ to grow at least proportionally to $\log(1/\epsilon)$ at fine precision. Since all blocks except possibly the last have length $q$, this gives the factor of $d$ in the sample bound.

11. Completing the Proof With Constant Accuracy, Kaczmarz, and Limitations

For constant accuracy the proof uses a separate argument. Give the learner every row and label up to the deadline. Reflect the signal across the row span by negating its perpendicular component. The uniform prior is unchanged, and both signals give identical data. If the perpendicular component has norm greater than $\epsilon$, the two signals are more than $2\epsilon$ apart. A single estimate cannot be within chord distance $\epsilon$ of both. The expected squared length in the row span is at most $T/d$. A Markov bound on that length and the reflected-pair argument give success below two thirds for $T\le d/4$ throughout the stated tolerance range. This supplies the linear floor where the backward estimate alone can be too weak.

The paper uses Kaczmarz as a real-register benchmark. Start from $z_0=0$ and project the current estimate onto each new measurement hyperplane. For a nonzero row the update is

The correction changes the estimate along the current row by the amount needed to satisfy the new equation. This removes the error component parallel to the fresh row. By isotropy this removes $1/d$ of the squared error in expectation, conditional on the current estimate. After $t$ steps, the expected squared error is $(1-1/d)^t$. Since this is at most $e^{-t/d}$, reducing the expected squared error to order $\epsilon^2$ takes order $d\log(1/\epsilon)$ steps.

OpenAI’s release announcement describes the broader project. For this manuscript, the Family 140 scope document identifies the main memory–precision theorem and supporting inverse Gram moment, exact projection, regularization and block estimates in Lean. The linked Lean comparator records the selected formal statements. The theorem concerns fresh isotropic Gaussian rows and finite-state, one-pass estimation. Its hypotheses fix the row law and the access pattern, leaving adaptive measurement design and repeated passes outside the result. It leaves open a matching finite-bit algorithm and gives no uniform constant for a memory multiplier that grows with dimension.

The memory sample tradeoff distinguishes the information in an exact observation from what a streaming learner can carry forward. Here the cost of recovering a more precise direction shows up in how many fresh measurements the learner must be allowed to read. Follow Binary Verse AI for more research explainers on time–space tradeoffs, dimension reduction and machine-checked mathematical proofs.