Persistent-Cache Complexity: A Finite-State And Communication-Theoretic View of Causal Decoders

*How much memory does a causal decoder need to retain enough information to answer queries about an input it has already processed?* We study this question by counting all input-dependent information retained for future computation. For independent, uniformly distributed records compressed before an independent query is revealed, we derive memory lower bounds for a target average recall error. Under uniform queries, coding constructions asymptotically match these bounds, characterizing the optimal tradeoff between retained memory and recall accuracy. When queries have unequal frequencies, our bounds explain how memory can favor frequently requested records. We show that encoding a summary can outperform storing a fixed subset of records exactly, although this advantage at a fixed storage fraction decreases as the number of possible record values grows. Our analysis counts selection indices and reusable randomness, and distinguishes memory retained after compression from peak memory and physical cache storage. Experiments with finite-state models and Transformer caches on formal language recognition, synthetic associative recall and string retrieval illustrate these discovered tradeoffs and the importance of query timing.