The Cost of Remembering Every Possible Answer

TL;DR for operators

An agent must often retain information before knowing which question it will need to answer later. Compressing that information reduces immediate storage, but some answers may then require access to an archived record. The relevant costs include retained state, archive storage, retrieval width, decoding latency, and the questions the representation can still answer.

Pranav Singh and Prashant Singh establish mathematical limits on this tradeoff for exact Boolean queries and bounded raw-data retrieval.¹ Their results identify when sophisticated encoding saves retained bits and when simply caching raw words is already optimal.

The deployment comparison is instructive: in a categorical dialogue task, a three-byte state preserved the source model’s decisions without an archive and decoded substantially faster than the tested universal encoder. Compressing further to two bytes introduced shared storage costs and reduced coverage of unfamiliar questions.

For agent platform operators, the choice is a memory representation matched to the required decisions and retrieval contract—not the strongest compression guarantee considered in isolation. The mathematical results apply to raw bit and word retrieval, not arbitrary semantic memory systems.

A smaller state answered the same customer questions

Consider a customer-service agent that has accumulated a customer’s requirements. The next question might concern a particular hotel, restaurant, or attraction. Before that question arrives, the system must decide what information to preserve and what it can afford to retrieve later.

A compact representation might preserve every decision the application currently makes. A more general representation could support questions the application has never asked, but require additional storage and decoding work.

In the paper’s matched dialogue evaluation, the difference was measurable.

Source: Section 8.3, Table 7. Native-update observation source; local reference-implementation timings, excluding upstream extraction. The catalogue statistic also requires a separate shared codebook.

The mixed-radix representation stores the identifiers of valid categorical attributes in a compact integer. It can reconstruct the categorical state needed for the tested offer-validation decisions without consulting an archive.

The universal encoder instead protects a much broader guarantee: it can answer every Boolean question about the underlying binary record, provided the specified raw retrieval remains available.

Both preserved the same fixed source decisions under fresh conditions. The universal encoder’s additional guarantee therefore bought no improvement in correctness on those particular decisions.

This comparison establishes a resource difference within a defined workload, not that categorical encoding universally dominates general memory systems.

The mathematical price of answering any future question

The paper formalizes pre-query retention: a writer sees an entire $n$-bit record and creates a fixed-length retained state before learning the future query. A reader then receives that state and may inspect at most $R$ original archive bits.

Every record must be supported, and an unrestricted Boolean-query guarantee requires correct answers to every possible yes-or-no function of that record.

For one raw bit read, the authors prove two exact optima:

Here $B_{\oplus}$ is the minimum retained length for pairwise XOR queries, while $B_{\mathrm{all}}$ covers every Boolean query.

For a 64-bit record, the XOR workload requires 58 retained bits. Universal Boolean queries require 62. Both figures are exact under the one-read interface.

A surprising structural result explains the second bound. If a retained-state equivalence class supports both pairwise XOR and AND queries with one raw read, it already supports every Boolean function on that class.

The authors establish more than the maximum size of an individually decodable class. Building on earlier decision-tree capacity results, they construct explicit encoders that partition the entire record space into compatible classes, attaining the bounds for every input.

With multiple adaptive bit reads, the universal minimum satisfies

uniformly when $1\le R\le\lfloor n/2\rfloor$.

Thus, beyond the bits available through retrieval, sophisticated nonlinear encoding yields only a doubly logarithmic additional saving, up to a bounded constant. Fixed affine writers require exactly $n-R$ retained bits.

An entropy-based converse further shows that allowing a fixed positive average error below one-half does not remove this leading-order requirement. That statement assumes uniformly distributed records, an error bound for each fixed query, and a worst-case retrieval cap.

These are strong guarantees, but deliberately demanding ones.

Wider archive reads can make raw caching optimal

A storage system rarely retrieves just one bit. It may return an entire aligned word.

The paper extends the model to $M$ immutable words of $w$ bits each. A word read provides $w$ original bits in a single charged operation.

When

the exact universal retention optimum becomes

Retaining every word except the $R$ words scheduled for retrieval is therefore mathematically optimal, even compared with unrestricted nonlinear encoders.

For eight-bit words, the sufficient condition extends to $M\le 2^{255}$, far beyond ordinary archive sizes. The result concerns retained logical bits with an unchanged, aligned raw-word archive; it is not a runtime comparison of retrieval software.

Outside this exact regime, the paper’s constructive and converse word bounds remain within two retained bits when the read budget is at most half the number of words. Under an additional entropy condition, the exact caching result also survives a positive uniform-source average-error allowance.

For infrastructure designers specifying raw-data retrieval APIs, response width changes the theoretical value of compression. A more elaborate encoder may provide no retained-bit advantage over caching once a read returns a sufficiently wide original word.

Two private bytes can require more total storage

The dialogue evaluation introduces another distinction: a representation can be sufficient for a particular query family without preserving the complete categorical state.

The catalogue-specific statistic groups states that produce identical answers to the fixed public catalogue questions. Its 5,904 possible combined answer patterns require just 13 logical bits, serialized into two bytes.

But decoding those indices requires an additional 8,878-byte shared codebook.

Across the study’s 999 stored states:

Source: Appendix G, Table 14. Totals exclude resources shared by all methods.

The catalogue approach becomes smaller than mixed radix only from 8,879 stored states onward, assuming one unchanged codebook is shared across them.

Its other limitation is coverage. In the paper’s constructed unseen attribute-profile tests, catalogue-statistic coverage fell to 96.06% for the native source and 86.63% for the history source. Mixed radix answered 100% of the tested profiles in both groups.

These tests are a query-shift sensitivity analysis, not the primary catalogue evaluation. They show that preserving every answer in today’s catalogue does not necessarily preserve answers to an expanded query family. Coverage also should not be confused with accuracy among answered queries.

Correct retention cannot repair incorrect observations

The source models themselves impose a separate limit.

The primary evaluation uses 999 final dialogue states and 67,346 catalogue queries per observation source. Accuracy against annotated offer-validation constraints was 47.25% for the native-update source and 80.70% for the full-history classifier.

These different accuracies reflect different fixed observation mechanisms, not improvements caused by retention encoding. Losslessly preserving a source decision also preserves that source’s mistakes.

Archive reliability adds another consideration. In the native-source archive-removal test, the universal encoder retained 86.78% query coverage, while mixed radix retained 100%. Controlled synthetic tests likewise showed that complete coverage with a fresh archive need not imply resilience when archived bits are missing or corrupted.

The computational correctness checks establish that the implemented codecs obey their stated rules on tested finite instances. Archive-failure experiments test robustness, while the dialogue comparison measures representation costs and decision preservation. None establishes improved end-to-end dialogue success.

Choosing the guarantee before choosing the codec

Cognaptus inference: For an agent platform with known categorical decisions, a compact archive-free representation is a credible default candidate. Where arbitrary future questions must remain answerable, the retrieval contract and the associated mathematical bounds become more relevant.

The selection should make four quantities explicit: the required query family, the accessible raw-data interface, the total physical and shared storage, and acceptable behavior when archives fail or questions change. Upstream source accuracy needs separate measurement.

The remaining boundary matters. The proofs assume immutable raw coordinates or aligned words, unrestricted encoding computation, and fully accessible retained state. They do not provide equivalent limits for vector search, compressed document stores, natural-language questions, or changing semantic indexes. Nor do logical-bit optima automatically minimize serialized bytes or runtime.

The paper’s central contribution is a precise account of what broader answerability costs under specified retrieval rules. Its application illustrates why paying that cost is not always economical.

An agent should retain enough to answer the questions it is responsible for, with a clear account of what happens when those questions—or its archive—change.

Cognaptus: Automate the Present, Incubate the Future.