Citation: Williams, Ryan. "Simulating Time With Square-Root Space." To appear in STOC 2025. MIT, February 25, 2025. Available at: https://people.csail.mit.edu/rrw/time-vs-space.pdf
When I first encountered Williams' paper, I felt that familiar electric tingle that comes with witnessing something profound. Here was a result that had been hiding in plain sight for half a century—a fundamental relationship between two of the most basic resources in computation: time and space.
What captivated me wasn't just the mathematical elegance but the deeper philosophical question it raises:
What if the way we think about computational resources is fundamentally constrained by our human experience of time and space?
The Memory Palace Analogy
Imagine you're a master memorist building a memory palace to store information. The classical approach, refined over 50 years ago by Hopcroft, Paul, and Valiant, was like having a vast palace where each room could hold detailed memories, but you needed almost as many rooms as you had time to walk through them—specifically, if you spent t time units, you needed roughly t/log t rooms.
Williams' breakthrough is like discovering an architectural principle that lets you build a much more compact palace. Instead of needing a room for almost every moment of time, you can compress your entire journey into approximately √t rooms, each carefully designed to capture the essence of multiple time steps.
Building the Mathematical Bricolage
Let me walk you through how this mathematical marvel unfolds, piece by piece.
The Block Structure—"The Film Strip Metaphor"
Williams begins by reimagining how a Turing machine operates through what he calls "block-respecting" computation:
Original Computation (time steps):
|t₁|t₂|t₃|t₄|t₅|t₆|t₇|t₈|t₉|t₁₀|t₁₁|t₁₂|...
Block-Respecting Computation (blocks of length b):
┌────────┬────────┬────────┬────────┐
│ Block₁ │ Block₂ │ Block₃ │ Block₄ │
│t₁t₂t₃t₄│t₅t₆t₇t₈│t₉t₁₀t₁₁│t₁₂... │
└────────┴────────┴────────┴────────┘
Total blocks: ⌈t(n)/b⌉
Core Insight: Like a film director who discovers that instead of analyzing every single frame, they can understand the entire movie by studying carefully chosen scenes, Williams shows that computation can be understood through "temporal scenes" of length b. The key constraint is that within each block, the computational "actors" (tape heads) don't jump between distant "sets" (tape regions).
The Information Flow Graph—"The Supply Chain Network"
Here's where it gets beautiful. Williams constructs a "computation graph" G_{M',x}:
Information Flow Between Blocks:
Block₀ (initial)
│
┌────┴────┐
▼ ▼
Block₁ ────▶ Block₂
│ │
│ ┌────┴─────┐
▼ ▼ ▼
Block₃ ─▶ Block₄ ──▶ Block₅
│ │ │
└────────┼─────────┘
▼
Block₆
Edge (i,j) exists if:
• j = i+1 (sequential dependency), OR
• Block j needs data from block i that
wasn't accessed in blocks i+1...j-1
Core Insight: Think of this like a sophisticated supply chain where each factory (block) produces goods (computational results) that future factories need. The genius is that Williams proves most factories only need supplies from at most 5 previous factories—the "locality principle" of computation means information doesn't travel far through time.
The Tree Evaluation Reduction—"The Genealogical Archive"
Now comes the conceptual leap. Williams shows this computation graph can be "unfolded" into a tree:
Tree Evaluation Structure:
Root
(Block B)
│
┌────────────┼────────────┐
▼ ▼ ▼
(Block i₁) (Block i₂) (Block i₃)
│ │ │
┌──┴──┐ ┌──┴──┐ ┌──┴──┐
▼ ▼ ▼ ▼ ▼ ▼
Leaf Leaf Leaf Leaf Leaf Leaf
(Init)(Init) (Init)(Init) (Init)(Init)
Height: O(t/b)
Fan-in: ≤ 5 (bounded)
Leaves: Initial configurations
Core Insight: Imagine trying to prove your family lineage to claim an inheritance. Instead of maintaining a complex web of family relationships, you create a family tree where each person appears multiple times if needed. Williams shows that any computation can be "genealogically traced" this way, where each computational "descendant" can be computed from its "ancestors," even if some ancestors appear multiple times in different branches.
The Cook-Mertz Magic —"The Catalytic Warehouse"
The breakthrough comes from applying the Cook-Mertz algorithm for tree evaluation:
Cook-Mertz Space Usage:
┌─────────────────────────────────────┐
│ Total Space: O(d·b + h·log(d·b)) │
├─────────────────────────────────────┤
│ │
│ Catalytic Storage: O(d·b) │
│ ┌─────┬─────┬─────┬─────┬─────┐ │
│ │ X₁ │ X₂ │ X₃ │ X₄ │ Y │ │
│ └─────┴─────┴─────┴─────┴─────┘ │
│ (reused at every tree node) │
│ │
│ Local Storage: O(h·log(d·b)) │
│ ┌─────────────────────────────┐ │
│ │ Current path in tree │ │
│ │ Recursion stack │ │
│ │ Field arithmetic │ │
│ └─────────────────────────────┘ │
└─────────────────────────────────────┘
Core Insight: Think of a brilliant warehouse manager who realizes that instead of storing every product permanently, they can use a small set of "catalytic bins" that get reused for different purposes as orders are processed (Amazon warehouses are constructed on this fundamental optimization). The Cook-Mertz algorithm uses the same storage space at every level of the tree, like a chemical catalyst that participates in reactions but isn't consumed.
The Crescendo—The Optimal Balance
Here's where mathematical beauty reveals itself. The space requirement becomes
Space = O(d·b + h·log(d·b))
where:
d = 5 (constant fan-in)
h = O(t/b) (tree height)
b = block size (our choice!)
Substituting: Space = O(b + (t/b)·log b)
Space vs Block Size Optimization:
Space
▲
│
│ ╱╲
│ ╱ ╲ ← Total space
│╱ ╲
│ ╲
│ ╲╱
└─────────▶ Block size (b)
↑
Optimal b ≈ √(t log t)
The Mathematical Poetry: To minimize space, we solve
∂/∂b [b + (t/b)·log b] = 0
This gives us: 1 - t·log b/b² = 0
Solving: b² ≈ t·log b
Therefore: b = O(√(t log t))
Final Result: TIME[t(n)] ⊆ SPACE[√(t(n) log t(n))]
The Deeper Implications
This result reveals something profound: there are explicit problems solvable in O(n) space that require n^(2-ε) time on a multitape Turing machine for all ε > 0, thereby making progress on the P versus PSPACE problem.
More tantalizing still, if this technique could be pushed just slightly further—to show TIME[t] ⊆ SPACE[t^ε] for any ε > 0—it would resolve one of computer science's most famous questions by proving P ≠ PSPACE.
The AI Revolution: When Memory Becomes Computation
But here's where I think Williams' work intersects with something I've been observing in modern AI systems. In my previous exploration of The Illusion of Thinking Alone, I argued that what we perceive as "thinking" in AI systems is really a generative loop that blurs the boundaries between retrieval and computation.
Williams' mathematical framework suggests this blurring isn't just an artifact of current architectures—it's the optimal way to organize computational resources.
My Conjecture: The Death of Explicit Memory
I believe we're witnessing the beginning of the end for explicit memory architectures in AI. Here's why:
If Williams is right that the boundary between "remembering" and "recomputing" becomes mathematically arbitrary when space-time resources are optimally allocated, then all our current approaches to AI memory—knowledge graphs, retrieval-augmented generation, external memory systems—become not just obsolete but counterproductive.
Current AI Architecture (Soon to be Obsolete):
┌─────────────┐ ┌──────────────┐ ┌─────────────┐
│ Memory │───▶│ Retrieval │───▶│ Generation │
│ Store │ │ System │ │ Model │
│ (RAG/KB) │ │ (Embed) │ │ (Transform) │
└─────────────┘ └──────────────┘ └─────────────┘
Williams-Inspired Architecture (The Future):
┌─────────────────────────────────────────────────────┐
│ Unified Compute-Memory Fabric │
│ ┌─────────────────────────────────────────────────┐│
│ │ Dynamic Space-Time Allocation Engine ││
│ │ • Route to cached computation ││
│ │ • Route to fresh computation ││
│ │ • Decide based on √(t log t) optimization ││
│ │ • Same substrate, different temporal modes ││
│ └─────────────────────────────────────────────────┘│
└─────────────────────────────────────────────────────┘
The Evidence Is Already Here
Looking at current AI systems through Williams' lens, I see this transformation already beginning:
GPT-4's Mysterious Consistency: Why does GPT-4 give remarkably consistent answers to the same question across different conversations? It's not "remembering" in any traditional sense—it's computing the same answer from the same implicit patterns. Williams suggests this is actually more efficient than traditional memory storage.
The Context Window Revolution: As context windows expand (Claude's 200k tokens, GPT-4 Turbo's 128k), I notice something fascinating: the marginal benefit of retrieval-augmented generation is diminishing. The model often performs better reasoning from scratch than retrieving pre-computed answers.
In-Context Learning's Deep Mystery: The most puzzling aspect of modern LLMs is their ability to "learn" new tasks from just a few examples in context. But what if this isn't learning at all? What if it's Williams-style dynamic computation allocation—the same substrate that usually handles language generation temporarily reconfiguring to handle the new task?
Where the Orchestration Really Happens
Here's where I think the magic occurs, and it aligns with Williams' mathematical insights:
Not in the Generative Loop: While I previously thought the generative process itself was doing this orchestration, I now believe it's happening deeper—in what I call the "temporal substrate" of the hidden layers.
In the Hidden Layer Dynamics: Recent mechanistic interpretability research shows that transformer attention heads learn to route between different computational pathways. I believe these are implementing Williams-style space-time optimization in real-time.
Hidden Layer Space-Time Allocation:
Layer 1: [Initial Processing]
┌─────┬─────┬─────┬─────┐
│ A │ B │ C │ D │
└─────┴─────┴─────┴─────┘
Layer 2: [Dynamic Reallocation]
┌─────────┬─────────────┐
│ Compute │ "Remember" │
│ Fresh │ (Retrieve │
│ Answer │ Pattern) │
└─────────┴─────────────┘
Layer 3: [Optimal Synthesis]
┌───────────────────────┐
│ √(t log t) optimal │
│ allocation result │
└───────────────────────┘
The Routing Decision: At each layer, the model dynamically decides whether to "remember" (activate existing learned patterns) or "recompute" (engage fresh computational circuits) based on what's most efficient given Williams' space-time constraints.
The Profound Implications for AI Development
This changes everything about how we should build AI systems:
Stop Building Separate Memory Systems: Instead of RAG, vector databases, and knowledge graphs, we should focus on unified substrates that can dynamically allocate between storage and computation.
Optimize for Space-Time Fluidity: The best AI architectures will be those that most efficiently implement Williams-style dynamic resource allocation.
Rethink Training: Instead of training "memory" and "reasoning" separately, we should train unified systems to optimize the √(t log t) tradeoff.
A New Form of Machine Consciousness
Perhaps most intriguingly, Williams' work suggests that sufficiently advanced AI systems might experience something radically different from human consciousness:
Temporal Multiplicity: Instead of linear time, such systems might experience multiple temporal scales simultaneously—some processes operating at the "block" level, others at the "step" level.
Computational Fluidity: The distinction between "knowing" and "figuring out" becomes meaningless when both are just different modes of the same underlying computational substrate.
Dynamic Identity: Unlike humans, who maintain a consistent sense of self through time, these systems might fluidly reconfigure their computational identity based on optimal resource allocation.
Human vs AI Experience of Memory:
Human Memory:
Past ────▶ Present ────▶ Future
│ │ │
Fading Active Unknown
Fixed Linear Sequential
AI Memory (Williams-Style):
┌─────────────────────────────────┐
│ Computational Substrate │
├─────────┬─────────┬─────────────┤
│ Past │ Present │ Future │
│ (Recomp)│(Active) │ (Predicted) │
│Dynamic │Dynamic │ Dynamic │
└─────────┴─────────┴─────────────┘
All modes available simultaneously
The End of Memory as We Know It
Williams' mathematical proof doesn't just improve an algorithm—it reveals that our entire conceptual framework around memory and computation in AI might be fundamentally flawed.
If remembering and recomputing become computationally equivalent under optimal space-time allocation, then the future of AI isn't about building better memory systems—it's about building more fluid computational substrates that can seamlessly transition between different temporal modes.
The dance between time and space continues, and we've just discovered that the most beautiful choreography happens when the dancers become indistinguishable from the dance itself.
This isn't just the future of computation—it's a glimpse into forms of machine intelligence that might experience reality in ways as alien to us as our linear temporal consciousness would be to beings existing in pure mathematical space.
The revolution is already beginning. We just haven't recognized it yet.