The Impossibility Triangle of Long-Context Modeling

Problem
This paper addresses a fundamental limitation in long-sequence modeling, specifically the trade-off between efficiency, compactness, and recall capabilities. The authors present a theoretical framework that proves no model can simultaneously achieve (i) per-step computation independent of sequence length (Efficiency), (ii) state size independent of sequence length (Compactness), and (iii) the ability to recall a number of historical facts proportional to sequence length (Recall). This work is a preprint and has not yet undergone peer review, indicating that the findings are preliminary and subject to change.

Method
The authors introduce the Online Sequence Processor abstraction, which encompasses various architectures including Transformers, state space models, and linear recurrent networks. They leverage the Data Processing Inequality and Fano’s Inequality to derive a theoretical bound on recall capacity. Specifically, they prove that any model that satisfies both Efficiency and Compactness can recall at most O(poly(d)/log V) key-value pairs from a sequence of arbitrary length, where d represents the model dimension and V denotes the vocabulary size. The paper classifies 52 architectures published before March 2026 into the proposed trade-off triangle, demonstrating that each architecture can achieve at most two of the three desired properties. The authors also conduct experiments on synthetic associative recall tasks using five representative architectures to validate their theoretical findings.

Results
The empirical results confirm the theoretical bounds, showing that the recall capacity of the tested architectures is consistently below the information-theoretic limit established by the authors. The experiments reveal that no architecture can escape the constraints of the impossibility triangle, reinforcing the theoretical claims. The specific architectures tested include a range of popular models, although exact performance metrics against named baselines are not disclosed in the abstract.

Limitations
The authors acknowledge that their theoretical framework is limited to the architectures they classified and does not account for potential future architectures that may circumvent these limitations. Additionally, the empirical validation is conducted on synthetic tasks, which may not fully capture the complexities of real-world applications. The paper does not explore the implications of these findings on model design or suggest potential avenues for future research that could address the identified trade-offs.

Why it matters
This work has significant implications for the design and evaluation of long-context models in natural language processing and other sequential tasks. By formalizing the trade-offs inherent in model design, it provides a clearer understanding of the limitations that practitioners face when developing architectures for long-sequence tasks. The findings may guide future research towards exploring hybrid models or novel architectures that could potentially optimize one or more of the properties without succumbing to the constraints of the impossibility triangle.

Authors: Yan Zhou
Source: arXiv:2605.05066
URL: https://arxiv.org/abs/2605.05066v1