Externalized reasoning is already exploited by transformer-based agents through chain-of-thought, but structured retrieval -- indexing over one's own reasoning state -- remains underexplored. We formalize the transformer context window as an I/O page and prove that tool-augmented agents with indexed external memory achieve exponentially lower retrieval cost than agents restricted to sequential scanning: O(logbN) versus Ω(N) page reads per query, and O(TlogbT) versus Θ(T2) cumulative cost over T reasoning steps -- a gap that widens as deliberation deepens. We test these predictions on a controlled lookup benchmark across three content types -- random hashes, ordered integers, and encyclopedia entries -- varying store size from 50 to 5,000 items, and replicate key conditions across two model generations (GPT-4o-mini and GPT-5.4). On abstract content, the indexed agent achieves median 1 page read regardless of store size, confirming the O(1) prediction. Sorted pages without an index fail to close the gap: the weaker model cannot sustain binary search at scale, and the stronger model achieves near-optimal log2N search but still loses to the index by 5×. On familiar content (encyclopedia entries), a competing failure mode emerges: the model recognizes the domain, bypasses the retrieval protocol, and generates answers from parametric memory, producing catastrophic token expenditure even when the index is sound. This parametric memory competition dissociates the two cognitive operations that indexing combines: understanding content (where language models excel) and following navigational protocols (where they fail when understanding tempts them to shortcut). The result argues for a separation of concerns: use language models for index construction, where semantic understanding helps, and deterministic algorithms for index traversal, where it hurts.
Figures & tables
M
FLAT R~
SORT R~
IDX R~
CORR R~
FLAT acc
SORT acc
IDX acc
CORR acc
50
3.0
4.0
1.0
3.0
100%
100%
100%
94%
100
6.0
5.0
1.0
6.0
100%
100%
100%
88%
200
9.0
7.0
1.0
11.0
98%
100%
94%
74%
500
21.0
21.0
1.0
15.5
94%
97%
94%
58%
Table 1: Median page reads ( R~ ) and accuracy by condition and item count M (hash content, GPT-4o-mini, P=10 ). FLAT and INDEXED: 50 trials/cell; FLAT-SORTED and CORRUPTED: 30 and 50 trials/cell respectively. Predicted FLAT cost: M/20∈{2.5,5.0,10.0,25.0} . SORT = FLAT-SORTED, IDX = INDEXED, CORR = INDEXED-CORRUPTED.
Figure 1: Page reads ( R ) and accuracy versus item count M for the three conditions (hash content). FLAT (red) grows linearly, tracking the M/(2P) prediction. INDEXED (blue) remains constant at ≈1 . INDEXED-CORRUPTED (pink) exceeds FLAT at large M , confirming causal index use. Shaded bands show interquartile range.
Figure 2: Left: separation ratio (FLAT/INDEXED page reads) versus M , with theoretical prediction M/20 (dashed). Right: per-trial read distributions by condition at each M . FLAT broadens rightward; INDEXED collapses to 1.
M
FLAT Tok
IDX Tok
Ratio
50
1,284
842
1.5 ×
100
3,191
952
3.4 ×
200
5,904
1,172
5.0 ×
500
25,005
1,832
13.7 ×
1,000
174,264
3,348
52.0 ×
2,000
913,983
5,950
153.6 ×
Table 2: Median total tokens ( Tok ) per trial (hash content). Large- M cells (1,000 and 2,000) use 20 trials; all others use 50. INDEXED token cost grows linearly (proportional to TOC size); FLAT cost grows quadratically.
Figure 3: Token cost ( Tok ) versus item count M (hash content). Left: median total tokens per trial by condition (shaded bands show interquartile range). FLAT scales as ≈M2 ; INDEXED is orders of magnitude cheaper. Right: token cost ratio FLAT/INDEXED (median).
Median reads R~
Accuracy
M
SORT
IDX
DEEP
SORT
IDX
DEEP
GPT-4o-mini
50
4.0
1.0
1.0
100%
100%
100%
100
5.0
1.0
1.0
100%
100%
100%
200
7.0
1.0
1.0
100%
94%
95%
500
21.0
1.0
1.0
97%
94%
90%
Table 3: Multi-model comparison on hash content (30 trials/cell). SORT = FLAT-SORTED, IDX = INDEXED, DEEP = DEEP-INDEXED. GPT-5.4 achieves near-optimal binary search on sorted pages (5 reads at M=500 vs. theoretical log250≈5.6 ) but INDEXED still dominates at 1 read.
Figure 4: Multi-model comparison. Left: GPT-4o-mini cannot sustain binary search on sorted pages; FLAT-SORTED converges to FLAT at M=500 . Center: GPT-5.4 binary-searches effectively ( R~=5 at M=500 ), but INDEXED and DEEP-INDEXED hold at 1. Right: accuracy by condition and model. Solid lines: GPT-4o-mini. Dashed: GPT-5.4.
Content
M
IDX R~
DEEP R~
IDX acc
DEEP acc
Hash
50
1.0
1.0
100%
100%
100
1.0
1.0
100%
100%
500
1.0
1.0
94%
90%
1,000
1.0
1.0
90%
87%
2,000
1.0
1.5
90%
76%
5,000
—
2.0
—
85%
Table 4: INDEXED versus DEEP-INDEXED across three content types. Median page reads ( R~ ) and accuracy. Hash and numeric content: retrieval works as predicted. Encyclopedia content: DEEP-INDEXED accuracy collapses at M≥200 despite median reads near 1, indicating the model generates answers from parametric memory rather than reading them from pages. The median reads of 0.0 at M=200 means the majority of trials hit the token budget before reading any page. 30 trials per cell except hash M≥1,000 (50 trials) and hash M≥3,000 (20 trials).
Figure 5: Two-level indexing: median page reads, tokens, and accuracy across store sizes. INDEXED (blue) degrades at M≥1,000 ; DEEP-INDEXED (green) holds near 1–2. FLAT (red, dashed) shown for reference. Shaded bands show interquartile range.
Figure 6: Content familiarity disrupts retrieval. DEEP-INDEXED performance across three content types at matched store sizes. Left: page reads—hash and numeric hold at 1; encyclopedia collapses. Center: token cost—encyclopedia inflates by 50× as trials exhaust the 100K budget. Right: accuracy—encyclopedia drops to 27% at M=200 . Shaded bands show interquartile range.
Retrieving external knowledge is essential for solving real-world tasks, yet it remains challenging when the relationship between a query and its relevant knowledge involves implicit and complex reasoning beyond surface-level semantic or lexical matching (e.g., mathematical problems relying on the same theorem or coding requiring deep reasoning). Existing approaches primarily rely on query-side reasoning (e.g., query rewriting), which introduces significant online latency and underutilizes the opportunity to perform reasoning over the knowledge corpus itself (i.e., index-side reasoning). In this paper, we propose RL-Index, an agentic indexing framework that formulates retrieval index reasoning as a reinforcement learning problem. Instead of performing reasoning at query time, RL-Index shifts reasoning to the indexing stage by augmenting documents with LLM-generated rationales that explicitly encode the latent query-knowledge relationship. To optimize the quality of these rationales, we employ Group Relative Policy Optimization (GRPO) and use retrieval similarity as a verifiable reward signal, enabling direct optimization of indexing decisions for retrieval effectiveness. Extensive experiments on the BRIGHT benchmark demonstrate that RL-Index consistently improves both retrieval and downstream question-answering performance, while significantly reducing online inference latency. Moreover, the learned rationale augmentation generalizes across diverse retrievers and generators, highlighting its robustness as a plug-and-play indexing strategy across different retrieval systems.
As agents operate over long horizons, their memory stores grow continuously, making retrieval critical to accessing relevant information. Many agent queries require reasoning-intensive retrieval, where the connection between query and relevant documents is implicit and requires inference to bridge. LLM-augmented pipelines address this through query expansion and candidate re-ranking, but introduce significant inference costs. We study computation allocation in reasoning-intensive retrieval pipelines using the BRIGHT benchmark and Gemini 2.5 model family. We vary model capacity, inference-time thinking, and re-ranking depth across query expansion and re-ranking stages. We find that re-ranking benefits substantially from stronger models (+7.5 NDCG@10) and deeper candidate pools (+21% from k=10 to 100), while query expansion shows diminishing returns beyond lightweight models (+1.1 NDCG@10 from weak to strong). Inference-time thinking provides minimal improvement at either stage. These results suggest that compute should be concentrated on re-ranking rather than distributed uniformly across pipeline stages.
Extraction at ingestion is the wrong primitive for agent memory: content discarded before the query is known cannot be recovered at retrieval time. We propose True Memory, a six-layer architecture that shifts the center of the system from a storage schema to a multi-stage retrieval pipeline operating over events preserved verbatim. The full system runs as a single SQLite file on commodity CPU with no external database, vector index, graph store, or GPU. On LoCoMo (1,540 questions across 10 multi-session conversations), True Memory Pro reaches 93.0% accuracy (3-run mean) against 61.4% for Mem0, 65.4% for Supermemory, approximately 71% for Zep, and 94.5% for EverMemOS under a matched gpt-4.1-mini answer model. On LongMemEval (500 questions), True Memory Pro reaches 87.8% (3-run mean). On BEAM-1M (700 questions at the 1-million-token scale), True Memory Pro reaches 76.6% (3-run mean), above the prior published result of 73.9% for Hindsight. A 56-configuration ablation shows a 1.3-percentage-point spread within the top-performing configuration family.