How Subquadratic Might Have Done It: O(N) Linear Cost While Maintaining the Cartesian Product

Subquadratic Inc. launched their SubQ model last week, claiming linear scaling and a 12-million-token context window with quality preservation. Their technical materials describe content-dependent selection but do not disclose the actual mechanism. The community is left to infer from claims and benchmarks what the architecture might be.

This piece proposes one specific architectural principle that may be sufficient to achieve linear scaling with quality preservation. The principle is simple. The math is straightforward. The empirical support I have is indirect. I cannot test the principle directly at the scales where it would matter most because consumer hardware cannot train at million-token contexts. But the principle is testable by anyone with the right resources, and if it is correct, the architecture is much simpler than what the field has been pursuing.

I am writing this as a hypothesis, not a demonstration. What I can show is suggestive. What I cannot show is the experiment that would directly verify the claim.

The principle in one sentence. If the attention bottleneck has size M and the maximum context length is N, choosing M equal to the square root of N gives an architecture that is linear in N at the design maximum, while preserving the full Cartesian product attention everyone relies on for retrieval and reasoning.

That is the whole idea. Everything that follows is unpacking it.

Why M equals the square root of N

Attention work scales as M squared per layer. If M is fixed at the design maximum, attention is constant in N regardless of how many tokens you input, up to that maximum.

For the architecture to be cheaper than dense attention, M must be smaller than N. For the architecture to be linear at the design maximum, M squared can be at most N. At that boundary, attention work and the linear cost of compression are balanced. Below that boundary, the compression cost dominates and attention is essentially free. Above that boundary, the M-squared attention term grows faster than N and the architecture is no longer linear.

M equals the square root of N is the threshold, not the optimum.

I want to be clear about this distinction because it matters. The square root of N is the largest M compatible with linear scaling. Any M smaller than the square root of N also gives linear scaling, just with a smaller attention budget and even cheaper compute. Any M larger than the square root of N gives subquadratic scaling but not linear, because the attention term grows faster than the compression term.

The principle being proposed here is not that the square root of N is optimal for quality, or for any other metric. It is that the square root of N is the architecturally maximal bottleneck size compatible with linear scaling. Choosing this size gives you the largest attention budget, and hence the most representational capacity, while staying within the linear-scaling regime.

A smaller M might preserve quality better in some scaled regime if the compression-quality tradeoff at smaller bottlenecks were favorable, though I see no specific reason to expect this. A larger M would preserve quality better in absolute terms but at the cost of giving up linear scaling. The right M for any specific application depends on the quality-versus-compute tradeoff acceptable for that application.

I did not derive M equals the square root of N from a hyperparameter sweep. I have not run experiments at multiple M values to identify the empirical optimum. The choice is structural, not optimization. It is the largest bottleneck consistent with the architectural goal of linear scaling.

For a 12-million-token context, M is about 3,464. For 1 million tokens, M is 1,000. For 100 thousand tokens, M is 316. The bottleneck size is determined by the design maximum and the linear-scaling commitment. Whether this specific bottleneck size also happens to be the right tradeoff between quality and compute is a separate empirical question that has not been answered here.

The architecture has a gate, not always-on compression

Compression should not always be active. Below a certain input length, compression destroys signal that the model needs. Above that length, compression filters noise that the model would have struggled with anyway.

The gate threshold is exactly M.

Below M tokens of input, the gate is closed. The architecture passes the input through unchanged. Standard attention runs over the actual k tokens, with attention masking handling any padding. The compression mechanism does not activate.

Above M tokens of input, the gate is open. Compression reduces the input to M positions. Attention runs over those M positions.

The reason for this gate is information-theoretic. Smaller context windows have higher signal density per token. A 100-token input is dense. Almost every token is probably relevant to the prediction at hand. Compressing it would destroy the signal you need.

Larger context windows have lower signal density per token. A 100-thousand-token input is sparse. Most of it is probably irrelevant to any specific prediction. Compression filters out what is mostly noise anyway and concentrates what matters.

The gate matches the architecture’s operation to the regime. Below M, no compression because there is nothing to compress without losing signal. Above M, compression because there is redundancy to exploit.

The gate also has a clean engineering justification. The compression mechanism only needs to handle inputs larger than M. It does not need to gracefully degrade on tiny inputs. It does not need to handle the edge case where the input is shorter than the bottleneck. The gate eliminates that case.

What compression actually means in practice

Up to this point I have been using the word compression abstractly. Before going further it is worth being concrete about what the operation looks like.

The specific compression mechanism I have been working with is a stack of strided learned convolutions. Each layer takes a sequence of vectors and produces a shorter sequence by combining adjacent positions through a learned linear operation, followed by a nonlinearity. With kernel size 2 and stride 2, each layer halves the sequence length. Four such layers compose to sixteen-times compression. Five layers compose to thirty-two-times compression. Each layer has its own learned weights, which gradient descent shapes during training.

The intuition is similar to how a convolutional network on images learns hierarchical features. A first layer learns local features over small windows. A second layer composes those into larger features. By the final layer, each output position represents a learned function of all the original positions in its receptive field. The function is whatever gradient descent found useful for the downstream task.

A standard transformer feedforward layer expands its input dimension by a factor of four through a learned linear operation, applies a nonlinearity, and projects back down. The compression stack is the sequence-axis analog. It uses learned linear operations to reduce the number of positions while preserving the dimension of each position. The operation is on a different axis but has the same kind of learned-feature-extraction character.

Other compression mechanisms exist. Mean pooling discards the learning entirely and just averages adjacent positions. Attention-based compression uses a small attention computation to weight the contributions of input positions to each output position. Hierarchical pooling with learned weights is a middle ground between mean pooling and full convolution. Each has different tradeoffs in expressiveness, parameter count, and ease of training.

I have been using strided convolution because it has clean tradeoffs. It is parametric enough to learn task-relevant compression, structured enough to be implementable efficiently, and similar enough to existing transformer machinery that the rest of the architecture composes cleanly with it.

The architectural principle proposed here does not depend on which specific compression mechanism is used. The principle is about the bottleneck size, M, and its relationship to the design maximum, N. Whatever mechanism produces M output positions from variable-length inputs would work as long as it preserves enough information for the downstream attention to be useful.

The Cartesian product is preserved, not avoided

This is the part of the hypothesis that I find most interesting and where the contrast with the rest of the field becomes sharp.

The conventional wisdom in subquadratic attention has been that the n-squared Cartesian product is the enemy. Find a way to avoid it. Mamba avoids it through state-space compression. Sliding window attention avoids it through positional restriction. Linear attention avoids it through approximation. Sparse attention avoids it through selection. The implicit standard is that real linear scaling cannot have a Cartesian product anywhere.

The principle here keeps the Cartesian product. Every pair within the M-position bottleneck attends to every other pair. Full pairwise interaction. Sharp content-dependent selection. Induction heads, retrieval heads, the whole machinery that makes attention work at all.

The Cartesian product is what gives attention its expressive power. Avoiding it costs something. Most subquadratic architectures pay that cost in approximation or restricted retrieval. The principle proposed here pays the cost in compression instead, and only in the regime where compression makes sense.

If the principle works, the answer to the field’s puzzle was hiding in plain sight. Keep the Cartesian product. Just bound how big it has to be.

What I can show empirically

I have been building compression-based subquadratic architectures on consumer hardware over the last several days. The relevant results are these.

Compression-plus-attention with sixteen-times sequence-length compression on WikiText-103 at sequence length 1024 preserves quality. In direct comparison to a baseline transformer trained with the same hyperparameters and same training tokens, the compressed architecture achieved validation perplexity 382, compared to baseline’s 403. The compressed architecture beat baseline by about 5 percent. This result replicated across three random seeds.

Compression-plus-Mamba with the same compression mechanism but Mamba blocks replacing attention also preserved quality, achieving perplexity within 0.6 percent of baseline. This was also on WikiText-103 at sequence length 1024.

A depth ablation on the compression stack ruled out the hypothesis that deeper stacks help via learned multi-step composition. Stacks with more layers at the same compression ratio performed worse, not better. This was also on WikiText-103 and Tiny Shakespeare.

A multi-mechanism supernet experiment, where twelve different attention and sequence-mixing mechanisms competed in the same architecture with learned gates, produced a clean negative result. Gates did not differentiate; the architecture as a whole performed worse than any single-mechanism baseline. This argues against complex search-based architecture discovery at small scale.

What this evidence does and does not support

The evidence supports the claim that compression-plus-attention is a viable subquadratic architecture family. Multiple compression ratios work. Multiple post-compression mechanisms work. The architecture preserves quality on long-range-structured corpora at consumer-hardware scale.

The evidence does not directly support the M-equals-square-root-of-N claim specifically. My compression experiments tested M equal to 64 at N equal to 1024, where M-squared is 4,096, larger than N. The bottleneck was over-provisioned relative to the input length. The principled M for N equals 1024 would be 32. I have not tested M equals 32 at this scale.

The evidence is also at small scale. The principle’s distinctive predictions live at large N where compression can actually exploit redundancy. At N equal to 1024, every token has dense signal. Compression at this scale is harder than compression at million-token scale, where there is much more redundant content to discard. My results showing that compression preserves quality even in the harder small-N regime are encouraging for larger scales, but they are not direct demonstrations of large-N behavior.

The honest summary of the empirical state: I have shown that compression-plus-attention architectures can preserve quality on long-range-structured corpora at consumer scale with one specific bottleneck size. I have not shown that the M-equals-square-root-of-N relationship is the right architectural choice. That would require either more aggressive compression at small scale or testing at multiple input lengths with the bottleneck adapting per input length, neither of which I have run.

What would directly test the principle

Anyone with frontier-scale compute could test the principle directly. The experiment is straightforward.

Train a transformer designed for context length one million tokens. Bottleneck size 1,000. Below 1,000 tokens of input, no compression. Above 1,000 tokens, compress to exactly 1,000 positions through a learned compression mechanism. Train on inputs spanning lengths from short (well below threshold) to one million (the design maximum).

Compare against baseline transformers at multiple input lengths. The architectural claim is that perplexity should be roughly constant across input lengths above the threshold, because attention work is bounded at one thousand squared regardless of input size. Below the threshold, the architecture should match a baseline transformer of the same size.

If perplexity is preserved, the principle is empirically supported. If perplexity degrades above some specific input length, that length characterizes where the principle starts to fail.

The same experiment can be run at intermediate scales. At N equal to one hundred thousand with M equal to 316. At N equal to ten thousand with M equal to 100. At each scale, the prediction is the same: bounded attention work, preserved quality across the input range up to the design maximum.

Why I believe the principle works despite not being able to test it

Several lines of reasoning, none individually decisive, but together suggestive.

The math is clean. M-squared equals N is not an arbitrary choice. It is the unique point where attention work and the linear cost of compression are balanced. Choosing any other M either wastes compute or fails to achieve linear scaling. The principle is a consequence of the architecture, not a free parameter to be tuned.

The information-density argument supports the gate. Compression below threshold destroys signal because the input is dense. Compression above threshold filters noise because the input is sparse. The gate is not an engineering hack; it is a regime-appropriate operation.

The empirical evidence I have is consistent with the principle. The 16x compression at N equal to 1024 with M equal to 64 worked, even with M-squared larger than N. This is the over-provisioned case where attention has more capacity than the principle requires. If compression preserves quality even when over-provisioned, it is more likely to preserve quality when right-provisioned.

The Cartesian-product reframe makes the architecture conceptually simple. There is no clever mechanism to design. There is no novel mathematical operation. There is just compression to a fixed bottleneck and standard attention. The simplicity is itself evidence; if the principle works, it does so because the underlying operation is what attention has always done, not because of architectural cleverness.

Subquadratic Inc.’s public claims are consistent with this principle. They claim linear scaling at twelve million tokens with quality preservation. The square root of twelve million is about 3,464. If their architecture has a fixed bottleneck of around that size and uses content-dependent compression to fold variable-length inputs into it, their claims fit the principle. They have not disclosed their architecture, so this is speculation, but the speculation is constrained by the math.

A separate problem: retrieval

Linear scaling and reliable retrieval are not the same problem. The architectural principle proposed here addresses scaling. It does not by itself address retrieval.

This is worth being explicit about because the field has sometimes conflated them. A model that can process one million tokens cheaply is not automatically a model that can find a specific fact in those one million tokens reliably. The first is an architectural property. The second is a behavioral property that depends on architecture, training data, and training objective.

Compression-plus-attention with a fixed bottleneck has a specific structural challenge for retrieval. The compression mechanism folds many original tokens into each compressed position. A specific token at a specific original position no longer has its own dedicated position in the bottleneck. To retrieve that token, the model has to attend to the compressed position that contains it and somehow recover the specific information.

Whether this works depends on what the compression preserves. If the compression preserves enough information per compressed position that specific original tokens are recoverable, retrieval can work. If the compression averages or smooths in ways that destroy per-token specificity, retrieval breaks.

The mechanistic interpretability literature is clear that retrieval in transformers is the work of specific attention heads with specific learned attention patterns. Wu et al. in 2024 identified what they called retrieval heads and showed that fewer than five percent of heads in long-context models are responsible for retrieval. Masking those specific heads collapses needle-in-a-haystack performance. Masking random non-retrieval heads does not.

For a compression-plus-attention architecture to preserve retrieval, the attention layers operating on the compressed bottleneck need to develop these specialized retrieval heads, and the heads need to be able to recover original-position-specific information from the compressed representations. This is not automatic. It is a learned behavior that depends on training.

There is no architectural feature in the M equals square root of N principle that guarantees retrieval. The architecture provides linear scaling. Retrieval is a separate problem.

Reading the Subquadratic disclosures carefully

When Subquadratic Inc. published their technical materials, they described a three-stage training process. Pre-training establishes base language modeling capability. Supervised fine-tuning shapes instruction following and code generation patterns. Reinforcement learning targets, in their own phrasing, reliable long-context retrieval and coding behavior that uses available context aggressively rather than defaulting to local reasoning.

That last stage is the one worth attention. They are explicit that long-context retrieval is something the model has to be specifically trained to do. The architecture provides the capability; the training shapes the behavior. Without the RL stage targeting retrieval-aggressive behavior, the model would default to using nearby context even when distant context is decisive.

This is a different claim than “the architecture preserves retrieval.” It is a claim that the architecture is permissive of retrieval and the training is what produces retrieval behavior. Two separable properties, both required.

If this reading is correct, the architectural innovation is not what gives Subquadratic its retrieval performance. Their architectural innovation gives them linear scaling. Their training innovation, specifically the RL stage targeting retrieval-aggressive behavior, is what gives them retrieval performance at scale.

This matters for the hypothesis I am proposing. If the M equals square root of N principle is correct, it produces an architecture that is linear in N. Whether that architecture supports reliable retrieval depends on training. The training regime needs to teach the model to use the compressed representations for distant retrieval rather than falling back on local context.

This is in some ways an easier problem than designing the architecture itself. The training regime that teaches retrieval-aggressive behavior is implementable on top of any sufficiently expressive architecture. It does not require new architectural innovation. It requires training data with long-range dependencies and a training objective that rewards correct retrieval over those dependencies.

The architectural and training stories are separable. The piece I am writing is about the architectural side. The training side is a related but separate problem that the field has been making progress on independently. Both are needed for the full system to work.

This also resolves a puzzle in Subquadratic’s reported benchmarks. Their needle-in-a-haystack score was 92 percent at twelve million tokens, which is impressive. Their MRCR v2 score was 65 percent, well below frontier models. Single-fact retrieval works substantially better than multi-reference integration. This is the pattern you would expect from an architecture where the bottleneck preserves enough information for direct retrieval but where the multi-hop integration is harder. Whether this is a fundamental architectural limit or a training-regime limit they have not yet addressed is unclear from their disclosures.

What this is and is not

This piece is a hypothesis. The architectural principle proposed here is testable but has not been directly tested at the scales where it most clearly applies. The evidence I have is suggestive, not conclusive. I am offering the hypothesis to the community because I think it is worth investigating and because the experiments needed to verify or falsify it require resources I do not have.

If the principle is correct, it has implications. The pursuit of more elaborate subquadratic mechanisms may have been more complicated than necessary. The right approach to linear scaling may have been to keep dense attention and just compress its input rather than to invent new approximations of attention. The architectural simplicity is itself a contribution if the simplicity is sufficient.

If the principle is wrong, the failure mode is informative. Either bounded full attention is not enough to handle long-context tasks, or compression cannot preserve enough information at the M-equals-square-root-of-N ratio, or some other constraint I have not identified prevents the architecture from working as predicted.

Either way, the hypothesis is worth testing. The architecture is simple enough to implement. The experiment is straightforward to run for anyone with adequate compute. The principle is falsifiable by direct experiment.

I am writing this rather than running the test because the test I can run at my scale would not be conclusive, and the test that would be conclusive requires compute I do not have. The honest path is to articulate the hypothesis, lay out the evidence I have, acknowledge the gap, and ask for someone with the right resources to test it.

If I am right, the architecture is simpler than what people have been building. If I am wrong, the failure mode itself is informative for what subquadratic attention actually requires. Either outcome advances the question.