Episode 140, October 2026

Exact equations, limited memory

A claimed lower bound: a learner with order d² bits of memory needs on the order of d log(1/ε) exact Gaussian equations to find a hidden direction to angle ε

Covers result 140 in OpenAI’s catalog: all 6 papers. See its connections to other results and the work it cites.

Play Episode 140: Exact equations, limited memory. A sphere, the circle left by one exact equation, two candidate points and the hidden direction.

6:13. English captions available. The video loads from YouTube when you press play.

Chapters

The claim, in plain words

A hidden unit vector s lives in d-dimensional space. Each sample is a Gaussian vector x together with its exact inner product ⟨x, s⟩: a linear equation with no noise. With unlimited memory, d such equations determine s exactly. A learner that reads the equations once, in order, and keeps only M bits between them cannot store real numbers exactly. The Kaczmarz method with real-number registers shrinks its expected squared error by a factor 1 − 1/d per equation, so it needs about 2d log(1/ε) equations to reach angle ε. Sharan, Sidford and Valiant proved memory–sample lower bounds for a noisy version of this regression and asked whether this dependence on precision is optimal under bounded memory; earlier, Raz showed that learning parities needs either quadratic memory or exponentially many samples.

Result 140 is six OpenAI preprints, 301 pages dated September 27, 2026. The headline (42 pages) claims that for every fixed A, a learner keeping at most A·d² bits between equations needs at least c_A·d·log(1/ε) equations to reach angle ε with probability at least 2/3 for a random hidden direction, for every ε up to 1/10, once d is large. Transitions may use unlimited computation and randomness, but the answer must come from the last memory state, the stopping time and fresh coins. The same holds when success is required for every direction, and with memory o(d²) the constant is universal. The companions give alternative proofs and tools: subsphere methods (25 pages; an explicit 2⁻¹⁶·d·log₂(1/ε) for o(d²) memory), posterior replicas (60 pages), localization costs (93 pages), projection moments (29 pages; the trade-off c·d·log(1/ε)/(1 + M/d²)) and replacing observations (52 pages).

What it doesn’t claim

A matching bounded-memory algorithm: the Kaczmarz calculation stores real numbers and, in the paper’s words, “supplies no finite-bit upper bound”. Tightness: at exponentially small ε the true cost is far higher. Any constant that is uniform as A grows. The constants are tiny: the Lean proof’s constant for A = 1 is 1/1,600,400, so the result is about how the count scales, not about concrete sample sizes. Noisy regression is reached only through a consequence for the Sharan–Sidford–Valiant setting.

Where it stands

Posted as preprints: OpenAI, six preprints, 301 pages, dated September 27, 2026
Peer reviewed: Not yet
Checked in Lean: The headline and many supporting statements, with explicit constants. We have not run the check

Last checked October 19, 2026. None of the six preprints has been revised. OpenAI published a Lean formalization of the headline (subquadratic and fixed-quadratic memory, with explicit constants c_A = 1/(4·(400000 + 100A)) and d ≥ 32) and of many supporting statements, through eight comparators (headline comparator; 415 proof files and 74,493 lines in their imports, not counting Mathlib, with no unproved steps that we could find). The 1/(1 + M/d²) trade-off and the 3/5-success streaming theorems are not among the comparators; an uncatalogued file in the repository proves a subquadratic-memory version with success probability 3/5. We have not run the check. The papers are not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

Work backward. For each memory state, consider the chance of eventual success for each possible hidden direction. At the end, a fixed answer is right only on a cap of angle ε. The paper tracks one number R that bounds how concentrated the successful directions can be around any point; at the end, R = ε.
One block, a constant factor. Going backward across a block of about d/8 equations, R grows by at most a factor exp(C(1 + M/d²)), a constant when M is a constant times d². Constant success needs R of order one, so the number of blocks is proportional to log(1/ε): on the order of d log(1/ε) equations.
Inside a block. The learner may use all of a block’s exact real data, but must land in one of about 2^M states. The density of the block’s data is bounded by expanding a moment into independent copies of the hidden direction; the chance their labels coincide is an inverse Gram determinant, controlled by successive orthogonalization (with a close predecessor in Sharan–Sidford–Valiant). The size of the region cancels between the density bound and the projected volume.
Other routes. An accurate answer carries about d log(1/ε) nats about the hidden direction while each block of order d equations adds order d nats; each block leaves a random residual subsphere; and the equations a message depends on can be swapped for fresh ones at small cost.

The numbers in the video

In three dimensions, one exact equation leaves a circle of possible directions, two leave two points, three leave one.
Kaczmarz in 50 dimensions: mean squared error following (1 − 1/d)^t; a median of 223 equations to reach angle 0.1 and 670 to reach 0.001.
Naming the answer to angle 10⁻⁶ at d = 100 takes about 1,978 bits, against d² = 10,000.
Storing 50 equations at b bits per number and solving: median angular error 0.26 at b = 8 and 1.5 × 10⁻⁸ at b = 32, about 33·d² bits.

Read the source

Memory and precision in noiseless Gaussian regression (PDF), 42 pages.
Subsphere methods for memory–sample lower bounds in noiseless Gaussian regression (PDF), 25 pages.
Posterior replicas and conditional information in Gaussian regression (PDF), 60 pages.
Localization costs and information growth for exact Gaussian observations (PDF), 93 pages.
Projection moments, positive cap domination, and Riesz estimates on the sphere (PDF), 29 pages.
Replacing Gaussian observations in memory-constrained inference (PDF), 52 pages.
The Lean scope note.
The collection’s catalog, where this is result 140.

The 6 papers in this result

OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.

Transcript

Read the full script

0:00Exact equations, limited memory

Somewhere in d-dimensional space there is a hidden direction, a unit vector. Each sample is a random Gaussian vector together with its exact inner product with the hidden one: a linear equation with no noise at all. With unlimited memory, d of these equations pin the hidden vector down exactly. In three dimensions, one equation leaves a circle of possibilities, two leave two points, and three leave one. But a learner that reads the equations once, in order, and keeps only a limited number of bits between them, cannot store real numbers exactly. How many equations does it need to find the direction to within an angle ε? A natural benchmark is the Kaczmarz method: move the current guess onto each new equation. With real-number registers, its expected squared error shrinks by a factor of 1 − 1/d per equation, so it needs about 2d log(1/ε) equations. In our run in 50 dimensions, it took about 220 equations to reach an angle of 1/10, and about 670 to reach 1/1000. Sharan, Sidford and Valiant proved memory-sample lower bounds for a noisy version of this regression, and asked whether this dependence on precision is optimal under bounded memory. Earlier, Raz showed that learning parities needs either quadratic memory or exponentially many samples.

1:23The claim

Result 140 is six OpenAI preprints, 301 pages in all, dated September 27. The headline paper claims that for every fixed A, a learner that keeps at most A·d² bits between equations needs at least a constant times d log(1/ε) equations to reach angle ε with probability at least two thirds, for a random hidden direction, for every ε up to 1/10, once d is large. Transitions may use unlimited computation and randomness, but the final answer must come from the last memory state, the stopping time and fresh coins. Requiring success for every direction is covered too, and with memory below the order of d², the constant can be universal. The other five papers supply tools and alternative proofs; as one says of its own routes, they offer distinct tests rather than a succession of stronger bounds. One gives an explicit constant, 2^(−16), with base-2 logarithms, for memory below the order of d². Another trades the bound smoothly against memory M: a constant times d log(1/ε), divided by one plus M/d². The papers give no matching upper bound: the Kaczmarz calculation stores real numbers and, in the paper’s words, supplies no finite-bit upper bound. The constants are tiny; the Lean proof’s constant, for A equal to one, is about 1/1,600,000. The headline and many supporting statements, though not that trade-off, are formalized in Lean: eight comparator files, backed by four hundred fifteen proof files and about 74,000 lines.

3:05How the proof goes

The headline proof works backward from the end. Fix a memory state, and ask how likely eventual success is for each possible hidden direction. At the end, a fixed answer is right only on a small cap of angle ε. The paper tracks one number, R, which bounds how concentrated the successful directions can be around any point; at the end, R is ε. The key step: going backward across a block of about d/8 equations, R grows by at most a constant factor, when memory is of order d² bits. Constant success needs R of order one, so climbing from ε takes a number of blocks proportional to log(1/ε): on the order of d log(1/ε) equations. Why only a constant factor? Within a block, the learner may use all the exact real data, but it must land in one of about 2^M states. The paper bounds the density of a block’s data by expanding a moment into independent copies of the hidden direction, replicas, and computing exactly how likely their labels are to coincide: an inverse Gram determinant, controlled by successive orthogonalization, with a close predecessor in work of Sharan, Sidford and Valiant. Then the size of the region cancels: what the density bound loses, the volume of the projected data gives back. Choosing among 2^M destinations adds at most a constant times M/d² to the logarithm of R, a constant when M is a constant times d². The companion papers reach the same scaling by other routes. Information: an accurate answer must carry about d log(1/ε) nats about the hidden direction, while each block of order d exact equations adds only order d nats. Geometry: each block leaves a random residual subsphere. And replacement: the equations a stored message depends on can be swapped for fresh ones at small cost. Our toy shows why memory matters: storing 50 equations at 8 bits per number and solving gives an angular error of about a quarter; at 32 bits it is about 10^(−8), but that takes about 33 times d² bits.

5:22Where it stands

None of the six preprints is peer reviewed or revised. The headline theorem and many supporting results are formalized in Lean, with explicit constants; we did not build it or run the comparators. The repository also holds an uncatalogued Lean proof of a subquadratic-memory version with success probability 3/5. The papers are not among those OSVerify reviewed, and we have seen no expert review. If it holds, a learner with at most order d² bits of memory needs at least on the order of d log(1/ε) exact equations to reach angle ε, even though d equations would determine the answer exactly. The papers give no matching bounded-memory algorithm, and the constants are far from practical.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.