acceptodds
Under review as a conference paper at ICLR 2027

OSET: Online Evidence Trees under Sublinear Retained-State Budgets

Abstract

Large language models can process increasingly long inputs, yet retaining every past token, passage, or index entry causes memory to grow linearly with the input stream. Many compression and retrieval approaches reduce only the context presented to the reader or the key–value cache resident on the GPU, while preserving a linear external history. We study online long-context reasoning under a closed sublinear retained-state constraint. After reading \(n\) input tokens, the memory is bounded by \(B(n)=B_0+\lceil cn^\alpha\rceil\), where \(0<\alpha<1\), and discarded source content cannot be recovered from an uncounted archive. We introduce OSET, an online evidence tree that incrementally incorporates incoming text and selectively compacts and prunes its contents to satisfy this state envelope. OSET separates short semantic access cues from source-bearing evidence, allowing a frozen language-model reader to recover verifiable information for questions that are unknown during memory construction. We evaluate OSET with Llama-3.1-8B-Instruct on HotpotQA, MuSiQue, 2WikiMultiHopQA, RULER from 8K to 128K tokens, and LongBench v2. Across the three multi-hop QA datasets, OSET obtains a macro F1 of 45.0, compared with 46.0 for full-context inference. On LongBench v2, it outperforms full-context inference, while retaining textual state equal to 10.97% of the source length. Across the complete RULER evaluation, OSET reduces the average reader context by 91.3% and logged peak GPU memory by 73.6%. On the evidence-oriented RULER task families, it achieves an average of 98.9 on needle-in-a-haystack retrieval and 97.1 on variable tracking, although tasks requiring corpus-wide aggregation remain challenging. These results show that online sublinear retention provides a distinct low-state operating regime rather than a lossless replacement for full context.

Primary area:
foundation or frontier models, including LLMs
Keywords:
long-context language models, online memory, memory-efficient inference

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_VHmtOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes OSET (Online Sublinear Evidence Tree), which addresses a problem largely overlooked by existing long-context methods in online settings: constraining the amount of full-text state retained by the system to grow sublinearly with the input length while minimizing the loss of critical evidence needed for future queries.

Critical strengths
  1. The paper defines a clear and practically relevant research problem. The proposed setting lies between fixed-capacity online memory and linearly growing external memory. It imposes stricter constraints than approaches that focus solely on KV-cache compression or retrieval, making it more representative of real-world streaming scenarios.

  2. The separation of semantic access from source evidence is a reasonable design choice. Summarization can lose precise information, such as entities and numerical values, while retaining only the original text leads to linear memory growth. OSET addresses this trade-off by storing semantic cues and supporting evidence (e.g., entities and values) separately, while accounting for both within the memory budget. This is a pragmatic approach to balancing retrieval efficiency and evidence preservation.

  3. The evaluation goes beyond end-task performance. The authors examine whether evidence is preserved, successfully retrieved, and effectively used by the reader, allowing them to distinguish memory failures from reasoning failures. This provides a more diagnostic analysis than relying solely on end-task metrics such as F1.

Critical weaknesses
  1. The benefits of the sublinear constraint are not robust. In their paper, the budget is still considerable at the 128K level. It proves that "it can work under this budget," but it doesn't fully demonstrate "how much sublinearity saves compared to linear growth or fixed capacity, and where the savings lie." The reader context has a maximum of 8 independent nodes, but the actual token occupancy curve of the persistent state is not clearly shown.

  2. The results show obvious problems. RULER's (FWE) dropped from 97.56 to 30.07, and the QA task also saw a significant decline. This means that OSET's applicability is narrower than the title suggests. It is more like a "sparse evidence retrieval-type long context" method than a general long context memory.

  3. Again, the results for multi-hop are not robust. On HotpotQA, OSET scores of 61.0 are higher than those of full context scores of 58.0, which is somewhat counterintuitive, possibly because the search context reduces interference; however, scores for MuSiQue (31.0 vs 36.0) and 2Wiki (43.0 vs 45.0) both decline. Overall, robustness in multi-hop scenarios has not yet been fully established.

Questions for authors

NA

2 comments

R3.1 — Practical storage savings from sublinear retention

The actual RULER occupancy trajectory (Table R3) shows source length increasing 16.9× between 8K and 128K, while retained active content increases only 3.7×. Correspondingly, active-content occupancy falls from 38.93% to 8.60%; its descriptive finite-range log–log slope is 0.468 (Table S3). At 2M input tokens, the additional streaming experiment retains 2.41% of source length in active textual memory (Table S7). These measurements demonstrate progressively selective active evidence retention; complete serialized-state accounting, including the metadata-reclamation issue, is reported separately in R2.Q2.

R3.2 — Global aggregation and multiple-evidence tasks

OSET targets sparse, verifiable evidence and inter-evidence dependencies, while frequent-word extraction (FWE) requires global aggregation over many source locations and has a different information requirement. We also clarify a numerical mix-up in the review: submitted Table 3 reports FWE 83.60 → 30.07, whereas 97.56 is OSET's variable-tracking (VT) result, not the full-context FWE score.

Multi-evidence access remains meaningful under constrained memory: at 128K, OSET obtains 78.45 on multi-value retrieval, 76.20 on multi-query retrieval, and 42.40 on HotpotQA-based multi-hop QA2 (submitted Table 3). Together with the p(n)kp(n)^k illustration in R1.2, these observations support targeted evidence retention as a valuable alternative to indiscriminate selection, while identifying corpus-wide counting as outside the method's principal design target.

R3.3 — Multi-hop OpenQA and learned retrieval

OpenQA tests access to complementary evidence beyond direct lexical matches. In the submitted results, OSET improves HotpotQA over full context (61.0 vs 58.0 F1), while MuSiQue (31.0 vs 36.0) and 2Wiki (43.0 vs 45.0) are more challenging. The additional memory-system comparisons show OSET's highest macro F1 among the tested adapted baselines (45.00 vs 44.83, 41.36, and 38.18; Table R1). Under the separate main-score retriever comparison, learned retrieval improves F1 over frozen cosine by 3.05, 3.60, and 0.83 points, respectively (+2.49 macro F1; Table R4). These results support OSET's evidence-oriented organization and the value of learned semantic access for multi-hop reasoning under that setting.

Thanks for your response; I will maintain my initial rating.

Reviewer_FXeWOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

OSET studies online long-context reasoning under a closed sublinear retained-state constraint. After processing nn input tokens, the retained textual state must remain within B(n)=B0+⌈cnα⌉B(n)=B_0+\lceil cn^\alpha\rceil, where 0<α<10<\alpha<1, and discarded source content cannot be recovered from an uncounted external archive. The paper distinguishes the retained-state budget from the reader-context budget and considers memory construction before future queries are known. Its claimed contributions are this problem formulation, an online evidence tree, progressive evidence-aware compaction and pruning, and an evaluation that traces whether supporting evidence is retained, retrieved, and used by the reader.

OSET constructs memory nodes that separate semantic access cues, generated by a frozen LLM, from literal source-grounded evidence (entities, exact values, factual spans, and short source windows) with provenance. It organizes these nodes through online tree construction, using semantic compatibility, entity overlap, lexical overlap, and recency. To satisfy the sublinear state envelope, it applies redundancy removal, field-level degradation, and node pruning based on a query-independent retention utility. At query time, a retrieve-expand-rerank pipeline combines exact-match, lexical, semantic, and structural signals and passes at most eight nodes to a frozen reader. The neural retrieval component uses lightweight projections over frozen Llama hidden states, trained with evidence supervision from the training splits of HotpotQA, MuSiQue, and 2WikiMultiHopQA.

Experiments using Llama-3.1-8B-Instruct show that OSET achieves 45.0 macro F1 across three multi-hop QA benchmarks versus 46.3 for full context, outperforming it only on HotpotQA (Table 1). On RULER at 128K, it scores 78.37 versus 82.12, performing well on single- and multi-key needle retrieval and variable tracking but degrading on multi-value and multi-query retrieval, QA, and aggregation tasks (Tables 2–3). On LongBench v2, it achieves 31.6% versus 31.0% accuracy (Table 4). The authors also report substantial reductions in retained textual state, reader context, and peak GPU memory. Ablations indicate that preserving literal evidence improves answer survival and that FIFO pruning sharply reduces coverage (Table 6).

Critical strengths
  1. Explicit formulation of online memory under a closed sublinear retained-state budget. The paper bounds the complete persistent textual state by B(n)=B0+⌈cnα⌉B(n)=B_0+\lceil cn^\alpha\rceil and separates this retained-state budget from the reader-context budget. I find this distinction important: most compression and retrieval methods reduce what the answering LLM gets as input while their store still grows linearly. In addition, hierarchical memories such as RAPTOR or MemWalker are typically built offline over a fixed corpus, whereas OSET maintains its hierarchy incrementally as text arrives, without rebuilding it. This is consequential to my assessment because it makes persistent memory growth an explicit and measurable design axis, which matters for streaming and agentic settings where knowledge evolves continuously. My concerns about how this bound is accounted for and evaluated are listed under weaknesses, but I consider the formulation itself a useful contribution.

  2. Query-independent memory that preserves literal, source-grounded evidence. OSET builds its memory before any query is known and keeps entities, exact values, factual spans, and short source windows with provenance alongside generated semantic cues, rather than relying on summaries alone. This allows one memory to serve many future queries, and it avoids the bottleneck of query-conditioned selection, which can discard content that only becomes relevant to a later question. Their ablation supports this design choice (Table 6). This is consequential because it addresses a known failure mode of summary-based memory, namely the loss of the exact values and entities needed for verifiable answers.

Critical weaknesses
  1. The experimental comparisons do not sufficiently isolate the contribution of the proposed memory design. The individual components of OSET have been explored in previous work, including hierarchical summarization (RAPTOR), online tree construction (MemTree), and capacity-constrained memory maintenance (ProStream, MemAgent). The contribution therefore appears to lie mainly in combining these mechanisms under a sublinear retained-state budget, which makes comparisons with existing memory systems essential. However, ProStream, MemAgent, and MemTree are discussed but not evaluated. The baselines are predominantly KV-cache eviction, sparse-attention, and offloading methods, which, as Section 2.1 itself notes, generally do not bound persistent state. The only explicitly budget-matched baseline, H2O-Sublinear, applies the same growth schedule to KV-token positions rather than textual state, so its memory footprint is not matched either. In addition, the neural retriever is trained with evidence supervision from the training splits of HotpotQA, MuSiQue, and 2WikiMultiHopQA (Appendix A.6), but the comparisons do not adequately control for this benchmark-specific training. This is consequential to my assessment because, without direct memory-system baselines under matched retained-state budgets and a training-free OSET variant, the results do not sufficiently isolate the advantages of the proposed sublinear evidence-tree design from those of supervised retrieval.

  2. It is not clear whether the evaluated benchmarks sufficiently exercise the sublinear budget. With the default parameters in Section 4.2 (B0=1024B_0=1024, c=8c=8, α=0.6\alpha=0.6), the budget is approximately 1,529 tokens after reading 1,000 tokens and 1,668 tokens after reading 1,500 tokens, and it first becomes smaller than the input length at 1,726 tokens. For relatively short multi-hop QA contexts, the constraint may therefore be weak or even nonbinding. Generated semantic fields can enlarge the charged state and trigger maintenance even for shorter inputs, but the paper reports neither the input-length distribution nor how frequently the budget becomes binding or how much information is removed during maintenance. Table 6 reports a group survival rate of 69.0%, suggesting that some required evidence is absent from the retained memory, but it is unclear how much of this loss results from memory construction versus pruning, and the dataset and input-length distribution underlying this table are not specified. At 128K, the default budget corresponds to approximately 8% of the input length. However, RULER results are reported only at 128K, despite the stated evaluation range of 8K to 128K. Consequently, the experiments do not sufficiently characterize how the accuracy-retention trade-off evolves under sublinear memory growth or how it compares with a linear fixed-fraction retention policy. This is consequential because the sublinear regime is central to the paper's contribution. I believe evaluation with multi-hop questions embedded in longer distractor streams, retained-state ratios across context lengths, and a sweep over α\alpha and cc would provide stronger support for the proposed formulation.

Questions for authors

Clarification Questions

  1. How frequently is budgeted memory maintenance triggered? With the default parameters (B0=1024B_0=1024, c=8c=8, α=0.6\alpha=0.6), B(n)B(n) first becomes smaller than the input length at 1,726 tokens. What are the input-length distributions of the evaluated benchmarks, on what fraction of inputs is budgeted maintenance triggered, and how much information is removed through compaction and pruning? On which dataset and input lengths is Table 6 computed?

  2. What is included in the retained-state budget? Section 3.4 defines the retained-state size in terms of textual tokens and excludes structural identifiers and pointers. Are the semantic, entity, lexical, and recency indexes, as well as any stored representations used for retrieval, included in the budget? If not, how does their storage grow with the input length, and does the sublinear constraint apply to the complete persistent memory or only to its textual fields?

  3. What is the contribution of the trained neural retriever? Appendix A.6 states that the retriever is trained using evidence supervision from HotpotQA, MuSiQue, and 2WikiMultiHopQA. How does OSET perform on the end tasks without the trained neural component, for example, using the rule-only ranker in Table 5? Additionally, Table 5 shows that the trainable neural ranker performs worse than frozen cosine retrieval across all reported metrics (MRR 0.522 versus 0.622). Could the authors explain this result and clarify the benefit of training the neural retriever?

  4. What is the advantage of a sublinear retained-state budget over fixed-capacity memory? Section 2.3 discusses ProStream and MemAgent, which also constrain memory growth through fixed-capacity storage. What motivates allowing OSET's retained-state budget to grow sublinearly with input length rather than keeping it fixed? Could the authors provide experimental evidence showing the advantages of this choice in terms of memory efficiency and answer quality?

  5. How does OSET perform across different context lengths? Section 4.4 states that RULER is evaluated from 8K to 128K tokens, but Tables 2 and 3 report results only at 128K. Additionally, the abstract reports average scores of 98.9 for needle-in-a-haystack retrieval and 97.1 for variable tracking, which differ from the results in Table 3. Could the authors provide per-task results across all evaluated context lengths and clarify how the averages reported in the abstract were calculated?

Questions 1–3 would most directly affect my assessment.

Suggestions for Additional Experiments and Analysis

  1. Comparison with relevant memory systems. Compare OSET with flat BM25/dense RAG, RAPTOR, MemTree, ProStream, and MemAgent under matched retained-state and reader-context budgets.

  2. Evaluation under restrictive memory budgets. Evaluate multi-hop questions embedded in 32K–128K-token distractor streams, with a sweep over α\alpha and cc and comparisons against a fixed-fraction linear retention baseline. Report evidence survival, retrieval quality, and answer accuracy across different input lengths.

  3. Computational and memory efficiency analysis. Report memory construction time, maintenance overhead, retrieval latency, TTFT, and the total memory footprint, including retrieval indexes and structural metadata.

  4. Detailed failure analysis. Distinguish errors introduced during evidence extraction and semantic abstraction from evidence loss during pruning, retrieval failures, and errors made by the answering LLM. This analysis would also help substantiate the paper's claimed contribution of tracing whether supporting evidence is retained, retrieved, and used.

4 comments

R2.Q1 — When does maintenance bind? What does Table 6 measure?

The nominal crossover B(n)≈nB(n)\approx n occurs near 1.7K tokens, but it is not a performance inflection point. Summaries, retained evidence fields, and internal abstractions can trigger maintenance even on shorter inputs. The original submitted Table 1 OpenQA scores used short-input budget relaxation, so we do not present them as results from the new strict Llama-token protocol.

We audited the full OpenQA source-length distributions: 2Wiki (12,576 examples; mean 951.31, median 856 tokens), HotpotQA (7,405; mean 1,320.72, median 1,294), and MuSiQue (2,417; mean 2,393.77, median 2,346; Table S1). In a separate strict Llama-token experiment with 500 prespecified examples per dataset and no short-input relaxation or source rereading, substantive maintenance occurred in 1,498/1,500 cases and all 15,451 post-maintenance checkpoints satisfied the charged active-text budget (Table S2). This shows that the maintenance mechanism genuinely operates under the strict protocol. Because the original context is sometimes shorter than the generated memory representation, maintenance does not necessarily imply net compression relative to source length on short OpenQA inputs.

Clarification of submitted Table 6. The memory-design ablations use the full evaluated sets of HotpotQA, MuSiQue, and 2WikiMultiHopQA, without short-input budget relaxation, rather than the new 500-example strict-audit subset. The metric is defined before query-time ranking: Group survival is the proportion of evaluated questions for which every required evidence group remains represented in the retained memory after construction and maintenance. Hence 69.0% means that the complete required group set is represented for 69.0% of evaluated questions; it does not mean that 69.0% of individual evidence groups survived or that the remaining 31.0% of questions necessarily failed at the reader stage. This definition is distinct from All-group Recall@8, which checks the retrieved evidence set.

Why is survival below 100%? Memory construction relies on an LLM writer and source-span selection. Imprecise extraction, incomplete abstractions, and omitted cross-passage dependencies can prevent a required group from being represented even before subsequent compression; compaction and pruning can create additional losses. Without a stage-matched counterfactual, these contributions should not be assigned exclusively to pruning. The controlled ablation remains informative: submitted Table 6 reports 54.6% group survival for flat memory and 13.6% under FIFO pruning, compared with 69.0% for OSET under the corresponding ablations. Separate strict-protocol node-deletion frequencies are provided in Table S2; they are not presented as the causal breakdown of the submitted Table 6 result.

R2.Q2 — Which state is subject to the budget?

We account for summary/topic fields, literal evidence, duplicated textual content, provenance, and retained routing/relation text in active textual memory. The new strict OpenQA audit applies the local Llama tokenizer directly to these active fields; source overlap is not double-counted in the processed-input coordinate. No persistent node embeddings or query encoder cache are included as an uncharged retrieval archive in that strict setup; query representations are computed when needed.

Table R3. State occupancy in the audited RULER runs (same tokenizer for all columns).

ContextSource Llama tokensActive-content tokensActive/source
8K7,657.512,981.3638.93%
16K15,716.523,956.5125.17%
32K32,127.135,456.2616.98%
64K64,663.747,752.0011.99%
128K129,336.6211,123.988.60%

These columns describe different tokenizations of serialized components, not additive byte partitions; as noted above, the underlying RULER pruning decisions used the historical weighted-cost protocol. At 2M, the independent streaming audit retains approximately 50,592 active-content tokens (2.41% of input), consistent with a sublinear active-text capacity profile (Table S7). Thus the reported active-text bound is experimentally supported. We distinguish persistent storage from cumulative processing work, which naturally increases with the input processed.

R2.Q3 — What does the trained retriever contribute?

The trained projection is designed to improve semantic alignment and complementary evidence access for multi-hop QA, not merely direct lexical matching. We added a main-score-setting OpenQA comparison:

Table R4. Trained retrieval versus frozen cosine on the reported OpenQA configuration (F1).

Retrieval setupHotpotQAMuSiQue2WikiMacro F1
OSET, trained retrieval61.0031.0043.0045.00
OSET, frozen cosine retrieval57.9527.4042.1742.51
Difference (trained − cosine), pp+3.05+3.60+0.83+2.49

The trained retriever improves end-task F1 on all three reported OpenQA benchmarks under this configuration. This directly motivates supervised access to semantically related and complementary evidence. The submitted Table 5 instead measures ranking quality under a different candidate-evaluation setup, where frozen cosine has higher MRR (0.622 vs 0.522). In the additional strict-budget OpenQA evaluation, the macro-F1 difference is +0.17 pp, while frozen cosine scores higher on RULER (88.76 vs 86.00). Thus, the effect of learned projection is task- and protocol-dependent, with its clearest observed gains in the main-score multi-hop QA configuration; it is not a prerequisite for OSET's evidence-tree retention mechanism.

R2.Q4 — Why increase memory sublinearly rather than keep it fixed?

A fixed budget satisfies a sublinear asymptotic bound but cannot increase its representational capacity as evidence accumulates. OSET occupies a distinct intermediate regime: its capacity grows, while its fraction of the processed history decreases. Under the same construction and reader protocol, the growth laws were matched at 32K (Table S3). At 128K, sublinear retention achieves 78.37 RULER score versus 69.69 for fixed capacity, with 11.12K vs 6.60K active-content tokens; compared with linear growth it uses 31.52% fewer active tokens and obtains 78.37 vs 75.77 observed score (Table R2). These data characterize a favorable quality–capacity trade-off under the evaluated workload.

We also conducted nine predefined budget configurations, varying B0B_0 and cc individually and sweeping α\alpha while matching the budget at a 32K anchor. This is not a full Cartesian grid. Scores were not monotonically improved by increasing capacity (Table S4), reinforcing the need to jointly consider information selection and available state.

R2.Q5 — RULER results across lengths; NIAH/VT clarification

We report results for the paper's ten fixed tasks, at 8K, 16K, 32K, 64K, and 128K (20 examples per task–length cell). Per-task breakdown is supplied in Table S8; Table R5 summarizes the ten-task mean at each length.

Table R5. Mean RULER task score across lengths.

ContextExamplesRuleFrozen cosineTrained projection
8K20087.7595.0091.50
16K20081.4895.2091.00
32K20077.7490.8087.00
64K20070.3283.5082.07
128K20062.9679.3078.37
All lengths1,00076.0588.7686.00

Abstract-number clarification. The submitted 98.9 NIAH figure was intended as an aggregate over multiple NIAH subtasks, not a single RULER task. To make the statistic unambiguous and directly reproducible from submitted Table 3, we will instead report the 128K mean of the four single-/multi-key needle retrieval tasks (S1, S2, M1, M2): (100.00+99.80+98.60+99.00)/4=99.35(100.00+99.80+98.60+99.00)/4=\mathbf{99.35}. This subset does not include the distinct multi-value (MV) or multi-query (MQ) tasks. The 97.1 VT figure in the abstract was a typographical error; the submitted 128K Table 3 value is 97.56 (97.6 to one decimal). These are corrections of aggregation labeling and typography, not changes to the submitted per-task scores.

R2.Q6 — Related memory-system baselines

The direct online-memory comparisons in Table R1 isolate the relevance of alternative organization and maintenance strategies more directly than additional KV-cache-only baselines. OSET achieves 45.00 macro F1, compared with 44.83 for adapted MemTree-text, 41.36 for adapted ProStream-text, and 38.18 for flat BM25. OSET is competitive with adapted hierarchical memory and clearly stronger than the evaluated flat BM25 reference, while the component-level ablations in submitted Table 6 separately show the role of tree structure and evidence-aware maintenance. We distinguish our text-only, common-model adaptations from original systems and do not present them as exact author implementations.

R2.Q7 — Construction, retrieval, and paced-streaming latency

The 10-task RULER resource profile distinguishes memory construction, maintenance, retrieval, and reading (Table S5). On a single A100-PCIE-40GB worker, mean construction time rises from 4.433 s at 8K to 25.043 s at 128K, while query time rises from 1.060 s to 2.217 s. The 128K build-plus-query mean is therefore approximately 27.26 s, and the reader-stage first-token latency is 0.285 s.

In a separate paced-streaming study (Table S6), incoming tokens were released using wall-clock arrival times, and the writer could access only chunks that had arrived. At 128 and 512 input tokens/s, all three 32K streams and all three 128K streams at each rate met the study's prespecified service criteria. At 8,192 tokens/s, the experiment intentionally probes overload: full-chunk-to-commit P95 is 26.75–29.33 s for 32K and 79.44–94.32 s for 128K, and neither length passes the same service criteria. This quantifies both a supported operating regime and the saturation boundary of this single-worker configuration.

R2.Q8 — Failure attribution and H2O-Sublinear matching

Additional same-reader diagnostics indicate that retained tree text can provide useful answer-bearing evidence: relative to empty-context prompting, tree-guided prompting increases F1 by 11.62, 15.75, and 11.48 points on 2Wiki, HotpotQA, and MuSiQue, respectively. The observations are consistent with extraction, organization, and retrieval all contributing to eventual failures; they do not isolate the causal effect of each compression operation.

For H₂O-Sublinear, one retained token position with its complete KV states across the model's layers/heads counts as one unit of its cache-position budget. Its number of retained positions follows the same B(n)B(n) growth schedule as OSET's textual-token budget. This makes the comparison a matched token-position growth law, not a claim that one KV position occupies the same physical bytes as one textual token. GPU memory and textual retained state are therefore reported separately.

Thanks a lot for your response and effort! I appreciate it.

If you have time and results to answer this question, it would be very helpful: With frozen cosine retrieval, OSET gets 42.51 macro F1, which is lower than adapted MemTree-text (44.83). With the trained retriever, it is only 0.17 points higher. Did MemTree-text and ProStream-text use the same budget and retriever? Is the advantage over MemTree mainly from the supervised retriever, which is trained on the same three datasets?

Reviewer_2b5ZOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes an interesting formulation on memory as sublinear. Memory storage increases less than O(n)O(n), n as the input length. To compactly store information and allows it to be retrieved, it segments input as chunks, for each chunk, store the summary and facts, for summary as the key for searching and facts to answer questions on the details. When memory storage is over sublinear budget, it is being compacted by removing duplicated information, less important ones. When compared with another sublinear methods H2OH_2O-Sublinear, the paper outperforms. For other memory approaches, sometime better and sometimes worse in terms of score.

Critical strengths

Introduction of the sublinear formulation for memory storage. Providing concrete methods to achieve the sublinear goal.

Critical weaknesses

The final performance is not always better than other methods. In the result tables, only the scores are compared, not the storage space that the paper proposes.

Questions for authors

Should we limit the memory storage envelope? In the long run, the size would be limited by physical space. In the mean time, sometimes, many memorable events can happen altogether. Limiting storage to the sublinear envelope may cause losing of important memory.

1 comment

R1.1 — Accuracy and retained storage

We agree that final quality should be interpreted jointly with the retained state. The additional RULER audit reports Llama-tokenized active content and separately serialized complete-tree state, rather than only a nominal budget. At 128K, the mean input is 129,336.62 Llama tokens, active content is 11,123.98 tokens (8.60%), and the full serialized tree is 74,991.37 encoded tokens (57.98%). The latter includes structural/index/deletion representations and is not a direct measure of resident bytes. The RULER occupancy values are a common-tokenizer re-encoding of historical weighted-cost maintenance runs; they should not be confused with the nominal Llama-token budget ratio.

Table R2. Fixed, sublinear, and linear growth policies at 128K.

Growth policyActive-content Llama tokensFull-tree JSON Llama tokensRULER score
Fixed6,602.2259,466.6269.69
Sublinear11,123.9874,991.3778.37
Linear16,243.2091,916.4675.77

At 128K, sublinear retention improves on fixed capacity by approximately 8.7 points, while retaining 31.52% fewer active-content tokens than the linear-growth control and attaining a 2.60-point higher observed score. The capacity laws are matched at a 32K anchor, not at every length (Table S3). This demonstrates a useful quality–capacity operating point for progressively growing memory, without requiring a lossless representation of the full stream.

R1.2 — Can a sublinear budget preserve important evidence?

The objective is selective, evidence-aware retention, rather than keeping an arbitrary fraction of the history. Under our nominal schedule B(n)=1024+⌈8n0.6⌉B(n)=1024+\lceil8n^{0.6}\rceil, the nominal fraction p(n)=min⁡(1,B(n)/n)p(n)=\min(1,B(n)/n) decreases from approximately 34.3% at 8K to 8.0% at 128K. Under a simplified uniform, independent random-retention model, the probability that all kk nonredundant required evidence units survive is approximately p(n)kp(n)^k. At 128K, this is about 0.63% for two and 0.004% for four required units.

This calculation explains why indiscriminate retention is especially unsuitable for questions requiring complementary evidence; it is an illustrative evidence-survival calculation, not a measured random-baseline QA score. OSET prioritizes literal, source-grounded evidence and the connections needed to access it. Its RULER performance on multi-query, multi-value, and multi-hop QA tasks (submitted Table 3) shows useful recovery even in a strongly selective retention regime. The method does not target exhaustive corpus statistics, such as exact global word-frequency extraction.

R1.3 — Presentation

We will explicitly distinguish query-independent online construction, progressive maintenance under a capacity envelope, and query-time retrieval/reading. The additional state accounting makes more concrete resource implications (Table R3).

Table R3. State occupancy in the audited RULER runs (same tokenizer for all columns).

ContextSource Llama tokensActive-content tokensActive/sourceFull-tree JSON tokensIndex JSON tokensDeletion-record JSON tokens
8K7,657.512,981.3638.93%12,493.573,744.18706.72
16K15,716.523,956.5125.17%18,261.644,891.642,281.66
32K32,127.135,456.2616.98%27,746.826,669.905,518.22
64K64,663.747,752.0011.99%44,631.479,384.9412,695.17
128K129,336.6211,123.988.60%74,991.3713,572.0227,588.65

Comments on the paper

3 comments

We thank the reviewers for recognizing the significance of explicitly bounded online memory and for requesting stronger evidence on storage accounting, relevant memory baselines, and long-context behavior. OSET studies an online, query-unknown evidence memory whose retained textual capacity increases sublinearly with the input stream. Its design combines source-grounded evidence preservation, incremental hierarchy updates, and selective budgeted maintenance. We have added direct online-memory comparisons, strict-budget audits, fixed/sublinear/linear growth controls, retriever comparisons, storage measurements, per-length RULER results, and paced-streaming latency measurements. We distinguish the submitted results from additional experiments using different budget and reader protocols.

Additional online-memory comparisons (Table R1). We implemented ProStream-inspired and MemTree-style text-only adaptations, along with a flat BM25 reference. These systems are not claimed to be exact reproductions of the original implementations.

Table R1. Submitted OpenQA scores and additional memory-system comparisons (F1).

MethodHotpotQAMuSiQue2WikiMacro F1
Full context58.0036.0045.0046.33
OSET61.0031.0043.0045.00
ProStream-text / Sublinear (adapted)58.0028.9137.1841.36
MemTree-text (adapted)60.3133.1041.0944.83
Flat BM2553.0821.0540.4038.18

Macro F1 is the unweighted mean of the three dataset scores. OSET achieves the highest reported macro F1 among the tested memory baselines, while MemTree-text performs better on MuSiQue. These are method-level comparisons under the reported OpenQA evaluation, not evidence of equal physical-byte footprints.

Adaptation details. ProStream-text organizes incoming text chunks into scene–event–atomic units. A common Llama writer generates scene/event summaries and selects numbered spans that are restored verbatim as atomic memories; duplicate suppression, same-event merging, and an experimental access/recency/text-cost utility enforce its retention policy. It does not reproduce the original entity–relation triplet extractor, and the utility, thresholds, and single-call writer are study-specific. MemTree-text incrementally inserts new text along the most semantically compatible path and updates ancestor summaries and representations. We added FIFO leaf eviction and empty-parent cleanup to enforce the budget; surviving ancestor summaries remain charged. Flat BM25 is a nonhierarchical retrieval reference, rather than a tree-organization ablation or a claim of identical physical storage.

AuthorsOpenReview ↗

Supplementary experimental tables

The tables below present additional protocol and measurement detail. Submitted Table 1–6 results and the supplementary strict-budget RULER results are different experiments. Storage figures expressed as Llama-tokenized serializations are not interchangeable with resident bytes; historical RULER pruning used weighted state costs, whereas the new strict OpenQA audit directly charged Llama tokens.

Table S1. Original OpenQA source-length distributions (Llama tokens)

DatasetNMeanP10P50P90Maximum
2WikiMultiHopQA12,576951.31524.00856.001,494.004,219
HotpotQA7,4051,320.72941.001,294.001,740.603,405
MuSiQue2,4172,393.771,748.202,346.003,087.004,557

Table S2. Strict Llama-token OpenQA budget enforcement and occupancy

DatasetExamplesSubstantive maintenance casesDeleted ≥1 nodePost-maintenance checks
2Wiki5005004123,467
HotpotQA5004984874,464
MuSiQue5005005007,520
Total1,5001,4981,39915,451

Table S3. Fixed/Sublinear/Linear growth-policy settings and finite-range slopes

The three budget functions were matched at 32,768 simple tokens in the historical RULER comparison:

  • Fixed: B_fixed = 5120.
  • Sublinear: B_sub = 1024 + ceil(8 N^0.6).
  • Linear: B_linear = 1024 + ceil(0.125 N).
PolicyActive-content log–log slope β (exploratory 95% interval)Full-tree JSON slope β (exploratory 95% interval)
Sublinear0.468 [0.463, 0.471]0.633 [0.631, 0.635]
Fixed0.017 [0.015, 0.020]0.364 [0.361, 0.367]
Linear0.727 [0.725, 0.729]0.798 [0.796, 0.800]

Table S4. Budget-parameter sensitivity under the audited RULER protocol

SettingB0cαReported scoreMean active Llama tokens
Baseline102480.678.376,254.02
b0_51251280.677.865,606.56
b0_2048204880.677.747,581.15
c_4102440.676.813,757.48
c_161024160.677.2011,287.24
alpha_0.41024640.478.66,150.43
alpha_0.5102422.62740.577.896,188.78
alpha_0.710242.82840.777.736,382.22
alpha_0.8102410.877.626,556.76

Table S5. Construction, retrieval, and query latency by length

LengthBuild mean / P90 (s)Maintenance mean (s)Cosine retrieval mean (s)Reader TTFT mean (s)Reader time mean (s)Query mean / P90 (s)Mean build throughput (tokens/s)
8K4.433 / 5.5990.00860.4890.2940.5291.060 / 1.3481,728
16K5.082 / 6.4890.02490.6190.2820.5101.168 / 1.4443,093
32K6.929 / 9.5140.07010.8620.2800.5241.426 / 1.7414,637
64K12.760 / 15.6780.19671.2440.2970.5151.806 / 2.1995,068
128K25.043 / 32.4050.54761.6700.2850.5092.217 / 2.6345,165

Table S6. Paced online-arrival latency and stress behavior

Stream lengthArrival rate (input tokens/s)Complete chunk → commit P95 (s)First token → commit P95 (s)Drain (s)Met study-specific service criteria
32K1281.81–1.855.81–5.850.89–1.243/3
32K5122.22–2.793.22–3.790.80–1.033/3
32K2,04811.07–24.2111.32–24.469.60–23.610/3
32K8,19226.75–29.3326.81–29.3927.68–29.850/3
128K1281.61–1.685.61–5.680.49–0.523/3
128K5122.20–2.223.20–3.221.06–1.543/3
128K2,04825.57–40.3725.82–40.6224.65–40.070/3
128K8,19279.44–94.3279.51–94.3881.42–97.290/3

Table S7. Measured 2M Llama-token streaming snapshots and state decomposition

SeedInput tokensActive-content tokens
422,097,15250,535
432,097,15250,605
442,097,15250,636
Mean2,097,15250,592
State view (128K–2M empirical fit)Mean log–log slopeRange across three streams
Active literal content0.5780.577–0.578
Full uncleaned tree JSON0.9920.986–0.998
Serialized index JSON1.0251.019–1.029
Serialized deletion records1.0501.036–1.062
AuthorsOpenReview ↗

Supplementary experimental tables

Table S8. Per-task RULER scores across five context lengths

The first table is the learned-projection result; the second is the frozen-cosine ablation.

S8a. Trained projection

Task8K16K32K64K128KMean
niah_single_1100.00100.00100.00100.00100.00100.00
niah_single_2100.00100.00100.00100.0099.8099.96
niah_multikey_1100.0099.0099.00100.0098.6099.32
niah_multikey_2100.00100.0099.0099.0099.0099.40
niah_multiquery100.00100.00100.0085.0078.4592.69
niah_multivalue100.00100.00100.0082.7576.2091.79
vt99.00100.00100.00100.0097.5699.31
fwe61.0056.0039.0033.0030.0743.81
qa_186.0087.0069.0064.0061.6073.52
qa_269.0068.0064.0057.0042.4060.08
Macro91.5091.0087.0082.0778.3786.00

S8b. Frozen cosine

Task8K16K32K64K128KMean
niah_single_1100.00100.00100.00100.00100.00100.00
niah_single_2100.00100.00100.00100.0099.0099.80
niah_multikey_1100.00100.00100.00100.00100.00100.00
niah_multikey_2100.00100.0099.0099.00100.0099.60
niah_multiquery100.00100.00100.0087.0082.0093.80
niah_multivalue100.00100.00100.0082.0078.0092.00
vt100.0099.00100.00100.0096.0099.00
fwe93.0098.0071.0050.0034.0069.20
qa_185.0087.0073.0063.0062.0074.00
qa_272.0068.0065.0054.0042.0060.20
Macro95.0095.2090.8083.5079.3088.76

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.