Exact Local Optimality Does Not Compose: The Complexity of Chronological Realization

In the study of systems that evolve over time, such as weather patterns, stock markets, or even the way a human learns a new language, scientists often try to build a simplified model of the underlying reality. These models rely on the idea that the future behavior of a system depends on its current state. If you know the state, you can predict what happens next. However, in the real world, we rarely see the true state directly; we only see a stream of inputs and the resulting outputs. To make sense of this, researchers use a method called predictive state representation. Instead of guessing the hidden internal condition, they build a model based entirely on what the system has done in the past and what it is likely to do in the future. The goal is to find the smallest, most efficient description of the system that still allows for perfect prediction.

For decades, a prevailing intuition suggested that if every individual part of a system could be described simply, then the whole system should also be describable simply. If you can predict the outcome of a single experiment with a small amount of memory, it seemed logical that you could predict a sequence of experiments using roughly the same amount of memory. This assumption underpins much of modern artificial intelligence and control theory, where efficiency is paramount. If a system is complex, it is usually because its parts are complex. But what if the complexity arises not from the parts themselves, but from the way they are forced to work together over time?

A recent study by Yixin Zhao challenges this intuition directly. The researcher investigated a specific type of system where a single, shared memory must be used to predict a wide variety of different future scenarios. The question was straightforward: if every individual scenario can be predicted using a small, fixed amount of memory, does the entire collection of scenarios still fit within that same small memory when they must all share the same underlying dynamics? The answer, proven with mathematical certainty, is a definitive no. The study demonstrates that the requirement for a single, shared timeline can force the memory size to explode, growing far beyond what the individual parts would suggest.

To understand the discovery, imagine a library of instructions. Each instruction tells the system how to react to a specific sequence of events. The researcher constructed a family of these instructions where each one, standing alone, could be executed perfectly using a small, fixed number of internal states. However, when the researcher tried to build a single machine that could execute all these instructions in the correct order, sharing the same internal memory for every task, the machine required a vastly larger number of states. The size of the memory did not just increase slightly; it multiplied by a factor that could be made arbitrarily large. This phenomenon, which the author calls a "state blow-up," reveals that the cost of maintaining a consistent history is a hidden tax that does not appear when looking at the tasks in isolation.

The research goes further than just showing that the memory size grows. It proves that determining whether a system can be built with a specific, limited amount of memory is an incredibly difficult computational problem. In the world of computer science, problems are categorized by how hard they are to solve. Some are easy, some are hard, and some are so hard that no known algorithm can solve them efficiently. The study shows that for these shared systems, deciding if a solution exists is among the hardest problems known. It is not merely a matter of running a calculation and waiting; the structure of the problem itself resists efficient solution. Even if the individual tasks are simple and the memory limit is set just slightly above the minimum needed for each task, checking if a shared solution exists becomes a task that likely requires impossible amounts of computing power.

The author developed two distinct ways to prove this. The first involves a specific, constructed family of tasks that acts as a clear counterexample. In this scenario, the researcher showed that while the local memory needs are small, the shared memory needs grow linearly with the number of tasks, creating a gap that can be as large as desired. The second approach uses a more complex, abstract construction to show that the problem of finding a solution is computationally intractable. This means that even with the most powerful computers, there is no efficient way to determine if a system can be compressed into a small shared model. The proof relies on translating the problem into a geometric puzzle involving shapes and their relationships, showing that solving the memory problem is equivalent to solving a known, extremely difficult geometric problem.

These findings have profound implications for how we think about learning and control. They suggest that the difficulty of managing a complex system is not just about the complexity of its components, but about the rigidity of the timeline they must follow. When a system must remember a shared history to make predictions, it may be forced to carry a much heavier cognitive load than the sum of its parts would suggest. This is not a failure of current technology or a temporary limitation of algorithms; it is a fundamental structural property of how time and memory interact in predictive systems. The study isolates this intrinsic cost, showing that the price of chronological consistency is a state dimension that can be unbounded.

The work also clarifies the limits of what can be efficiently learned. If a system is too complex to be compressed into a small shared model, then any learning algorithm that tries to find such a model is fighting against a mathematical barrier. The researcher showed that even when the data is perfect and the rules are clear, the question of whether a small shared model exists is often impossible to answer quickly. This distinguishes between the ability to predict individual events and the ability to maintain a unified, efficient model of the entire process. The gap between these two capabilities is not a bug that can be fixed with better software; it is a feature of the mathematics governing sequential systems.

In the broader context of artificial intelligence, this result serves as a cautionary tale. It warns against assuming that because a system behaves simply in isolation, it will behave simply when integrated into a larger, time-dependent framework. The complexity of the whole can be fundamentally different from the complexity of the parts. The study provides a rigorous framework for understanding this difference, offering a new way to measure the cost of shared memory in dynamic systems. By proving that local optimality does not compose, the research forces a re-evaluation of how we design and analyze systems that must learn from a stream of experiences.

The paper concludes by pointing toward future questions. While the results are proven for classical systems, the author notes that similar challenges likely exist in the quantum realm, where the rules of probability and state are even more exotic. The study opens a door to understanding how these fundamental limits apply to more advanced forms of computation. For now, the core finding stands: the demand for a single, shared history can force a system to expand its internal complexity in ways that are both mathematically inevitable and computationally daunting. The efficiency we hope for in our models may be an illusion when the timeline is shared, revealing a deep and unavoidable cost to the coherence of time.