Pre-Query Retention with Bounded Bit and Word Retrieval

Pranav Singh; Prashant Singh

cs.ITOct 18, 2026

Pre-Query Retention with Bounded Bit and Word Retrieval

Authors: Pranav Singh, Prashant Singh

Organizations: Indian Institute of Technology Ropar, Department of Mathematics, Rupnagar, Punjab, India

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.

Figures & tables

Figure 1. Pre-query writing and bounded raw retrieval. A full record enters the writer before a query exists. The writer produces fixed-length retained state. Later the reader uses that state, a query, and charged accesses to the unchanged raw archive to produce a Boolean answer.

Result	Established ingredient	Retained-state conclusion
Theorem 1	Coordinate stumps and binary shattering capacity ( Yıldız, 2012 ; Yıldız, 2015 )	Affine-hull characterization and equivalence of pairwise XOR-plus-AND support with universal one-read support.
Theorem 2	Binary-stump capacity and simplex-code features	Full-domain offset partitions attaining fixed-bit optima, with an affine-writer comparison.
Theorem 1	Selector shattering ( Yıldız, 2012 ) and decision-tree counting ( Leboeuf et al., 2022 )	Compatible global encoders and converse bounds, with an exact affine-writer optimum.
Theorem 1	Counting finite tree descriptions and the binary entropy inequality	A converse for randomized writers fixed before the query and uniform-source average error.
Theorem 1	Multiway capacity ( Yıldız, 2012 ; Yıldız, 2015 ) and multiway tree counting	Word-width bounds, a uniform two-bit gap, and an exact raw-caching regime.
Proposition 2	The entropy converse and the word-tree count	A finite-error condition under which integer retention still makes raw caching optimal.

Table 1. Established ingredients and retained-state conclusions. XOR denotes exclusive disjunction and AND denotes conjunction.

Check	Cases
XOR construction	458,748
Boolean-pair construction	1,212,352
Arbitrary truth tables	6,272
Multi-read construction	699,608
Independent binary-cell enumeration	65,808
Independent codec checks	201,660

Table 2. Construction and structural checks. XOR denotes exclusive disjunction.

Figure 2. Retention bounds for bit retrieval. The left panel compares one-read savings by query family. The right panel compares universal bounds and affine retention as the read budget increases.

Figure 3. One-word-read savings and upper bounds relative to raw caching. Bounds on the extra savings decrease as the response width increases. The exact caching regime has zero extra savings.

Quantity	Value
Record lengths (bits)	10, 16, 64
Worlds per method-condition cell	2,000
Method-condition cells	96
Archive bit-corruption probabilities	0.01, 0.10
Displayed condition	$n=10$ , $B=8$ , $R\leq 1$ , corruption $0.10$

Table 3. Controlled-source evaluation protocol.

Query	Method	Coverage	Reads	Removed coverage	Stale error
Pair XOR	Universal	1.000	0.937	0.068	0.088
Pair XOR	Raw cache	0.983	0.346	0.607	0.040
Pair AND	Universal	1.000	0.612	0.401	0.067
Pair AND	Raw cache	0.992	0.193	0.819	0.012
Masked parity	Universal	1.000	0.875	0.141	0.086
Masked parity	Raw cache	0.754	0.506	0.267	0.065

Table 4. Coverage, mean bit reads, and conditional stale error. XOR denotes exclusive disjunction. AND denotes conjunction.

Figure 4. Coverage and conditional error under archive failures. The panels compare fresh coverage, removed-archive coverage, and conditional error under archive corruption for matched retained budgets.

Quantity	Value
Official test dialogues	1,000
Included final states	999
Observed user turns	7,372
Primary dialogue clusters	738
Primary queries per source	67,346
Compatible / incompatible primary queries	19,242 / 48,104

Table 5. Matched dialogue-agent evaluation protocol. B denotes bytes.

Decision source	Accuracy	Balanced accuracy	95% interval
Native update	0.4725	0.6170	[0.4487, 0.4978]
History classifier	0.8070	0.8461	[0.7846, 0.8288]
Always reject	0.7143	0.5000	[0.6992, 0.7293]
Always accept	0.2857	0.5000	[0.2707, 0.3008]

Table 6. Offer-validation accuracy and dialogue-bootstrap intervals. Intervals concern accuracy.

Method	State (B)	Archive (B)	$R_{\max}$	Returned (B/query)	Write ( $\mu$ s)	Query ( $\mu$ s)	p95 ( $\mu$ s)
Posterior summary	312	0	0	0.0000	31.042	8.250	26.500
Category vector	7	0	0	0.0000	4.250	1.208	2.708
Mixed radix	3	0	0	0.0000	7.333	1.708	5.459
Catalogue statistic	2	0	0	0.0000	14.625	2.875	4.834
Universal bit code	4	4	1	0.1322	54.167	39.875	143.959
Raw cache, 0 B	0	4	4	1.2382	10.042	10.500	35.375

Table 7. Native-source resource costs. B denotes bytes,

R_{\max}

is the cap on byte reads per query, and p95 is the query-latency 95th percentile.

$n$	$R$	Bits	Bytes	Write ( $\mu$ s)	Query ( $\mu$ s)	Query p95 ( $\mu$ s)
10	1	8	1	7.5	14.2	14.8
10	4	5	1	6.6	14.5	15.0
10	10	0	0	3.2	5.6	6.1
64	1	62	8	29.2	21.3	22.2
64	4	59	8	28.0	21.3	22.5
64	16	47	6	23.5	22.5	23.2

Table 8. Median bit-codec latency, query 95th percentile (p95), and retained state.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Method	State (B)	Archive (B)	$R_{\max}$	Returned (B/query)	Write ( $\mu$ s)	Query ( $\mu$ s)	p95 ( $\mu$ s)
Posterior summary	312	0	0	0.0000	15.791	5.500	11.291
Category vector	7	0	0	0.0000	2.000	1.000	1.625
Mixed radix	3	0	0	0.0000	3.583	1.208	3.375
Catalogue statistic	2	0	0	0.0000	11.875	2.167	4.000
Universal bit code	4	4	1	0.1202	38.667	34.458	55.916
Raw cache, 0 B	0	4	4	1.3297	4.416	7.833	20.209

Appendix

Table 9. History-source resource costs. B denotes bytes,

R_{\max}

is the cap on byte reads per query, and p95 is the query-latency 95th percentile.

Source	Method	Removed coverage	Stale coverage	Stale disagreement
Native	Mixed radix	1.0000	1.0000	0.0000
Native	Catalogue statistic	1.0000	1.0000	0.0000
Native	Universal bit code	0.8678	1.0000	0.0009
Native	Raw cache, 1 B	0.3274	0.9527	0.0084
Native	Raw cache, 2 B	0.8530	0.9848	0.0027
Native	Raw cache, 3 B	0.8617	0.9937	0.0017

Appendix

Table 10. Archive-failure coverage and disagreement with source decisions. Stale disagreement is conditional on answering.

Source	Method	Queries	Coverage	Conditional error
Native	Catalogue statistic	12,900	0.9606	0.7334
Native	Mixed radix	12,900	1.0000	0.7244
History	Catalogue statistic	12,900	0.8663	0.1774
History	Mixed radix	12,900	1.0000	0.1952

Appendix

Table 11. Selective answering on unseen attribute profiles.

Source	Query population	Queries	Accuracy	Balanced accuracy
Native update	Active constraints	67,346	0.4725	0.6170
Native update	All domains	221,778	0.8318	0.6322
History classifier	Active constraints	67,346	0.8070	0.8461
History classifier	All domains	221,778	0.9331	0.8679

Appendix

Table 12. Accuracy under a change of query population.

Source	Predictions	Text (B)	Extraction (s)	Update (s)	Load (s)
Native update	51,604	1,094,742	0.639	1.134	3.014
History classifier	7,000	1,238,071	0.307	0.000	0.784

Appendix

Table 13. Shared model processing costs. B denotes bytes.

Method	State (B)	Archive (B)	Extra shared (B)	Cohort total (B)
Posterior summary	312	0	0	311,688
Category vector	7	0	0	6,993
Mixed radix	3	0	0	2,997
Catalogue statistic	2	0	8,878	10,876
Universal bit code	4	4	0	7,992
Raw cache, 0 B	0	4	0	3,996

Appendix

Table 14. Cohort storage and catalogue amortization, excluding common resources. B denotes bytes.

Observation source	Peak resident memory (B)	Allocation pairs
Native source	223,133,696	200
History source	260,161,536	200

Appendix

Table 15. Upstream resident memory and traced writer/reader call pairs. B denotes bytes.

Source method	Slot accuracy	Relation accuracy	95% interval
Native Nous	0.792	0.900	[0.894, 0.906]
Full-history classifier	0.901	0.947	[0.942, 0.952]
Last local report	0.772	0.891	[0.884, 0.897]

Appendix

Table 16. Source accuracy and encoding mismatches on dialogue-derived records. Intervals are dialogue-bootstrap confidence intervals.

Quantity	Value
Controlled record lengths (bits)	10, 16, 64
Worlds per method-condition cell	2,000
Method-condition cells	96
Archive bit-corruption probabilities	0.01, 0.10
Displayed controlled condition	$n=10$ , $B=8$ , $R\leq 1$ , corruption $0.10$
Complete dialogues / included user turns	999 / 7,360

Appendix

Table 17. Evaluation protocol and physical resources.

Agent Memory

Agent memory lets AI systems retain, update, and use facts, experiences, and skills across sessions and long-horizon tasks.

See all 191 papers

EMBER: Efficient Memory via Budgeted Evidence Retention for Long-Horizon Agents
Jun 4, 2026Yilong Li, Suman Banerjee, Tong ChePersistent Memory for Language Models Long-Term Conversational Memory
University of Wisconsin–Madison · NVIDIA Research
What Should an Agent Remember? Disentangling Retention from Retrieval in Bounded-Memory Evaluation
Sep 30, 2026Juli HuangAI Agent Evaluation Memory Agent Benchmarks
Stanford University
Knowing the Store: What a Memory Backend Must Write Down Before an Agent Can Read It
Oct 3, 2026Ansuman Mullick, Eray TüzünLLM Agent Memory Agent Memory Management
Bilkent University, Ankara, Türkiye

Jun 4, 2026J/K move · Enter open · S save

EMBER: Efficient Memory via Budgeted Evidence Retention for Long-Horizon Agents

Yilong Li, Suman Banerjee, Tong Che

University of Wisconsin–Madison · NVIDIA Research

Persistent Memory for Language Models Long-Term Conversational Memory Evidence Retrieval Agent Memory Management Long-Horizon Reasoning

Open paper AskPDF arXiv

Long-horizon agents can archive large histories, but future answers still incur retrieval, rereading, and context costs. When retained memory misses answer-relevant evidence, the system must return to larger portions of the raw history. We study budgeted evidence survival: before the query is known, which source evidence should be retained so that it remains recoverable and usable under a fixed retained source-evidence token budget? We instantiate this setting as Budgeted Pre-Query Retention, where memory is written during ingestion and later read without access to the full raw stream. We introduce EMBER, a learned retention policy that constructs a compact, source-backed evidence state. EMBER stores evidence capsules: verbatim source excerpts paired with retrieval keys and update metadata, preserving both grounding and read-time access. Post-query outcome feedback trains the writer to preserve evidence across the ingestion-retrieval-answer chain. On LongMemEval-RR, our LongMemEval-derived retained-evidence protocol, EMBER-14B reaches 0.3017 F1 at the 8192-token retained-evidence comparison point, compared with 0.1765 for the strongest non-EMBER budgeted baseline. Across retained source-evidence budgets, EMBER improves F1, Retain-Recall, and Read-Recall, indicating that long-horizon memory depends on retaining evidence within the budget rather than rereading larger histories.

Abstract

Agent Memory

Explore similar work

EMBER: Efficient Memory via Budgeted Evidence Retention for Long-Horizon Agents

What Should an Agent Remember? Disentangling Retention from Retrieval in Bounded-Memory Evaluation

Knowing the Store: What a Memory Backend Must Write Down Before an Agent Can Read It