Memory retention limits set by future queries and response size
Pre-Query Retention with Bounded Bit and Word Retrieval
Information TheoryArtificial Intelligence
Summary
Sometimes a computer or agent needs to remember information before being asked a question, but can only retrieve a limited amount of data later. This paper looks at how much and what kind of information can be stored in fixed-size memory when the agent can only read a few bits or words each time. The authors provide ways to encode and retrieve data that balance storage size and the ability to answer any future question. They also tested these ideas in a dialogue system to show their methods use less memory and work faster than a general approach.
What this means in practice
- •For dialogue system engineers: Reduce memory needs and decoding delay in dialogue agents by using encoded retention tailored to query types.
- •For embedded systems developers: Design memory-efficient data retrieval systems that respect strict limits on bits or words read per query.
Authors
Pranav Singh, Prashant Singh
Abstract
An agent can retain information before receiving a future question and later retrieve evidence from an archive. Evaluating this arrangement requires accounting for both retained information and the width of each retrieval response. Decision-tree capacity bounds describe individual sets of distinguishable records, but a memory writer must encode every possible record before the query is known. We study fixed-length retention beside an immutable binary archive, with a worst-case limit on raw bit or word reads. We characterize feasible one-bit-read memory cells and construct encoders that partition the complete record space. Supporting pairwise exclusive disjunction and conjunction with one bit read is equivalent to supporting every Boolean query. For multiple reads, we combine explicit encoders with decision-tree counting and an entropy converse. The word-read bounds differ by at most two retained bits when the read budget is at most half the archive length. Under an explicit condition on word width and archive length, raw-word caching attains the exact optimum among all writers. A related condition preserves this optimum under positive average error. Exhaustive checks validate the implementations. In a matched dialogue-agent study, a categorical sufficient statistic preserves source decisions with less storage and lower decoding latency than the universal encoder. A catalogue-specific index reduces private state further and requires additional shared storage. The results characterize how response width and future query structure determine retention requirements.