OSET: Online Evidence Trees under Sublinear Retained-State Budgets

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.