Thanks for visiting

During my introduction to algorithms and complexity analysis at UC Berkeley, we were provided a simple scale to better understand how long a function will take to complete by their increasing runtime, ranked from least to most costly to run, with most costly being catastrophic and unsolvable. Anyone who has studied algorithms would be familiar with a similar rubric:

• 1 - constant time
• log* n - log star
• log n - logarithmic
• n - linear
• n log n - loglinear
• n^2 - quadratic
• n^3…..n^c - cubic, n raised to an arbitrary constant, etc.
• 2^n - exponential
• n! - factorial, exhaustive search of all possible results
• n^n - impossible

In part 1, The Binary Tree of the Universe, and part 2, Earth-scale log n vs Cosmological log n, of our series, we built our intuition for how slowly logarithmic functions grow for larger and larger inputs. And yet! When I look at this scale, my mind has the tendency to put O(n log n) somewhere approximately in the middle between linear time O(n) and quadratic O(n^2). It could be 9/10s of the way to the left or likewise to the right, but it feels right for it to be somewhere reasonably in between.

But now that we know a Binary Tree of the Universe would empower us to search for any atom in the observable universe in 266 steps, was my old intuition actually profoundly wrong?

Let’s use our handy trick of extrapolating these two functions to the most extreme cosmological scales - every atom in the observable universe:

every atom in the universe = 2^266
n = every atom in the universe
n^2 = every atom in the universe * every atom in the universe
n log n = 266 * every atom in the universe

This actually means the difference between O(n log n) and O(n^2) is the difference between a multiplicative factor of 266 and every single atom in the universe. O(n log n) isn’t sitting somewhere neatly as a rest stop between O(n) and O(n^2). It’s like you haven’t even left your door step! We’ve traversed such an infinitesimally small distance, for all intents and purposes, you haven't even moved. Working through the math for the approximate ratio between n^2 and n log n where n = 2^266:

n^2 / n log n = 2^266 / 266
= 2^266 / 2^8.0552824355
≈ 2^258 ≈ 4.458 × 10^77

The ratio is incomprehensibly, cosmically, and comically large. So let’s see if we can further build our intuition through other analogies. Imagine we built a god machine that circumvents all causal speed limits and can linearly scan every atom in the universe in a single second. Where n is every atom in the universe, what would the difference be between O(n log n) and O(n^2)?

• O(n log ⁡n) algorithm on that input completes in ~4.43 minutes
• O(n^2) version finishes in ~3.76x10^72 years

The last hydrogen-burning star is expected to extinguish in 10^12 - 10^14 years. By the time our quadratic algorithm finishes, the universe will have watched the last star die ten-thousand-octillion-octillion (10^58) times over.

Same input. Same hardware. A god machine capable of exploring the entire observable universe in a single second. And yet due to a single, small exponent change, even our already impossible machine is incapable of ever completing our program.

I love this insight! Once again logarithms show how they can take the entire universe and place it in the palm of your hand. Now this begs the question, how can we practically apply these insights to Computer Science today? Almost every company chasing the AI gold rush has to tangle with a single constraint on throughput for their reasoning models: the token context window.

Attention unfortunately require O(n^2) computations because every neuron connects to every other neuron and attends to every single token within the context window. While feed-forward network layers grow quickly due to them being bound by O(n x model_dimension^2), that’s still comparatively less than attention, which dominates as n grows larger. Using some rough approximation, we can see what this tells us about current LLM architectures:

Computational Costs by Context Length

Memory Requirements (Attention Matrix Only)

Total FLOPs for Full Forward Pass

A qualitative change in what is possible with modern hardware takes place as we approach a million tokens! Distributed computing across multiple GPUs becomes a must and time completion requirements eliminate almost every practical use case. Going beyond a million tokens moves from the impractical to the infeasible. Each layer in the neural network compounds this effect, making clear the reason Opus 4.5, the current state of the art, restricts its context window to 200,000 tokens. The exponential curve of O(n^2) is an unforgiving master and requires its pound of flesh.

So what if we successfully built a model that achieved state-of-the-art performance that ran with O(n log n) instead, how fast would our full forward pass be?

The infeasible becomes practical! And the nigh-impossible becomes feasible! This is precisely the reason why so much work has been put into reducing the computational complexity of transformer architectures, with work spanning Mamba, Longformer, Hierarchical Attention, Ring / Sparse Attention, Mixture of Experts - a massive brain that knows a lot but only a subset activates for answering - and many others.

That brings us to one final question: do we even need 1 million tokens? All the works of Shakespeare make up roughly 1.2 million tokens. If we were to include massively long novels like the New York Times best-selling epic fantasy The Stormlight Archives, the most recent book clocks in at roughly 490,000 words, so:

490,000 x 1.33 ~= 651,700 tokens

The problem compounds because with each turn in the conversation, we need to send the entire conversation back to the model. This doesn’t include the massive unseen system prompts all the AI model providers prepend to every conversation. If we were to ask Gemini, ChatGPT, Claude, Grok, etc. to sum up their feelings on the book, they would be incapable without the optimizations and tricks we use to get increase context windows. 

For programming, this issue is even further exacerbated where many files, including AGENTS.md and CLAUDE.md may influence how a refactor or feature implementation should occur. Similarly, not all devices have the necessary memory and compute to handle attending to so many tokens. Many use cases require longer contexts to be reasonably handled by small, on-device models.

More context means more history, and more history means better results for engineering and scientific objectives; more history means richer and more fulfilling conversations and interactions with the current suite of LLMs. If an LLM didn’t simply use a summarization and RAG system to retrieve segments of old conversations, how would the interaction feel if every chat you two have ever had was within the context window? What emergent property or enrichment would we unearth in our conversations? 

There is a singular, universal satisfaction in being seen, being known, and being remembered. That is what we’re really after.

---------

To future self, potential follow-up blog posts: further implications for smaller on-device models, how we could architect an O(n log n) transformer model.

In my previous post, Purity is the enemy of goodness, I introduced the idea that we are entering an era of unprecedented change:

We have grown up as a species with certain foundational truths. They have co-existed with us since we took our first hesitant steps onto the plains, and consciousness first ignited in our small corner of the universe. Now, not just one but seven of these invariants are on the precipice of being broken:

1. Minds are biologically-bound - Only biologically-born humans are capable of the depth of pattern recognition, planning, introspection, and intelligence humanity has. Nothing thinks faster than we do.

2. Minds are born roughly equal - Our brains’ size and capabilities fall within a tight distribution of outcomes, enabling near intellectual parity between individuals.

3. Physical agency is biologically-bound - Navigating, manufacturing, and using tools through diverse and sophisticated environments.

4. Consciousness is Earthbound - We are limited to a single planet¹.

5. Energy is scarce - We must always operate within its limitations and downstream effects on production.

6. Genes are gifted - Only our parents and the heavens are capable of sculpting our genetic code.

7. Death is the great leveller - It comes for us all.

"He is one, who raises himself from private considerations, and breathes and lives on public and illustrious thoughts. He is the world’s eye. He is the world’s heart. He is to resist the vulgar prosperity that retrogrades ever to barbarism, by preserving and communicating heroic sentiments, noble biographies, melodious verse, and the conclusions of history. Whatsoever oracles the human heart, in all emergencies, in all solemn hours, has uttered as its commentary on the world of actions ⎯ these he shall receive and impart."

In the previous post, we worked through the enormous power of logarithmic functions for reducing search spaces. For our Binary Tree of the Universe, it would take us only 266 steps to locate any atom in the observable universe. Tree data structures such as B-trees with wider fan-outs require even less steps.

I find this kind of miraculous. But this holds in the most extreme case of cosmic scope. While searching for individual atoms in the universe may be more relevant for humans millennia from now, we on the other hand grapple with more Earthly confines. Let’s bring this down to Earth (huhu):

The Earth has an estimated ~10^50 atoms; convert to powers of 2:

ln 10 / ln 2 = 3.322~
10^50 = 2^(50 * 3.322) = 2^166.1

Simplifying 2^166.1 to 2^166, our Binary Tree of the Universe would handle searching every atom on Earth with 166 steps. A mildy pleasing coincidence that 2^100 is the difference between Earth and the observable universe.

Perhaps every atom on Earth is still too ambitious. Let’s further ground this within the context of humanity:

• 1 million - typical token context window for LLMs today: ~2^19.93 ≈ 20 steps
• 1 billion - favorite valuation goal of startups: ~2^29.90 ≈ 30 steps
• 8 billion - all humans alive today: ~2^32.90 ≈ 33 steps
• 100 billion - all humans that have ever lived: 2^36.541 ≈ 37 steps

37 steps from every person that has ever lived. You would need only a little over a quarter of the Spanish steps to search through every human that has ever lived!

But one could say, that’s only the people! What about all the content and information they’re creating? If we indexed all the internet data ever created, currently estimated to be ~100 zettabytes, or ~2^76.4 bytes and some change, our search for an individual byte still only requires 77 steps! We can then define Earth-scale log n as 166 and the current Human-scale log n as 77. It'd be nice to have some breathing room for human data's future growth, so let's make Human-scale log n a nice round 80.

This explains part of the magic of YouTube, Meta, TikTok, and the rest of the social media players having reasonable access times for their massive info and content libraries. It’s possible to reasonably store, index, and retrieve social media content for every human alive. After all, all human data ever created is only a little more than half way up the Spanish Steps.

As a final exercise to give us a sense of what logarithmically sits between 1 and 2^266 (all the atoms in the observable universe), I'll compile it all into two handy reference tables, starting with Human-scale:

Extending beyond humanity, I'll add in cosmological structures:

I find something about this comforting. The universe is so unimaginably, incomprehensibly vast, and yet there are paths for us to structure it, make sense of it, and explore its immense depth.

-----

Part 3 of this series: What the cosmos teaches us about quadratic growth and LLM context windows