arXiv CSopen access

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory Aojie Yuan

University of Southern California Los Angeles, CA, USA [email protected]

Haiyue Zhang

University of Southern California Los Angeles, CA, USA [email protected]

arXiv:2605.25092v1 [cs.IR] 24 May 2026

Abstract Long-term conversational memory is a retrieval workload classical IR was not built for: the index grows during the query stream, query types shift intra-session, and the latency budget per retrieval is sub10 ms. Lucene-class engines treat the index as static and the query as stateless, leaving the workload’s structure unexploited. AgentIR treats fusion as a per-query decision along two axes: which fusion to apply (BM25, Dense, RRF, or agent-aware RRF), and whether the ∼52 ms dense channel is worth running at all. The second axis is a confidence-triggered cascade router that decides from the BM25 top-𝑘 margin alone and re-tunes across workloads without retraining. On LongMemEval (𝑛=500), where the dense channel does add information, the cascade skips 63% of queries at parity LLM-judged accuracy (2.67× faster under two judges, paired bootstrap 𝑝≥0.88); per-qtype thresholds extend this to 5.76× under 5-fold cross-validation. On LoCoMo (𝑛=1,982), where BM25 alone is already the strongest single system, the same trigger auto-tunes to a 100% skip rate (132× faster, +0.089 Hit@5). Capacity on a shared 8-core VM rises from ∼154 to ∼1,400 concurrent agents (9×). Underneath the cascade, a time-partitioned index does 𝑂 (log 1/𝜀) work independent of corpus size: 1234× corpus growth costs only 3.6× latency, ending in 1769× over sequential at sub100 𝜇s 𝑝50 on 5 M records. At parity quality with Lucene on 9 BEIR datasets up to 8.8 M docs, the substrate runs 10× geo-mean over Pyserini 8T and 11× over PISA-1T BlockMax-WAND; an A100 reaches 1.8–39× over Pyserini 8T; chunked index build sustains 56.8 K docs/sec on MS MARCO. Three subtle BM25/GPU correctness pitfalls that silently regress nDCG@10 by 6–8× are documented and fixed; post-fix CPU and GPU agree within 0.0002 nDCG@10 on all eight datasets that fit a single A100.

CCS Concepts • Information systems → Retrieval efficiency; • Computing methodologies → Parallel computing methodologies.

Keywords hybrid retrieval, agent memory, LLM agents, workload-conditional fusion, BM25, SPLADE, HNSW, GPU acceleration, temporal indexing, parallel computing

1

Introduction

LLM agents running for hours or days accumulate large interaction histories: dialogue turns, tool calls, intermediate plans, and the results those plans produced. This agent memory is queried by the agent itself on almost every step, and the cost of those queries sits directly inside the agent’s reasoning loop [25, 30, 31].

Shahin Nazarian

University of Southern California Los Angeles, CA, USA [email protected]

A representative load looks like this. A customer-support agent on its 800th turn of a three-month engagement holds roughly 5 M records of memory. On each step it issues several lookups against that memory: the last similar issue on this account, the last successful fix for the same error code across any account, the user’s name and stated preferences from session 1. Each of these is a retrieval call that lives inside the agent’s reasoning loop. Production agent traces show 5–20 such retrievals per agent step; if any one of them blocks for 50 ms the user feels the agent stall. The retrieval system underneath the agent must therefore deliver sub-millisecond 𝑝99 latency on millions of records, on commodity hardware, while the corpus grows during the session. The IR systems agents currently inherit—Lucene, FAISS, PISA— were not built for this regime. Lucene-class engines treat the corpus as static, ignore the recency skew, and serve queries at 2–10 ms latency. FAISS-class engines retrieve by dense similarity but lack BM25 and agent-specific metadata fusion. PISA’s BlockMax-WAND degenerates on the long, multi-clause queries that agents emit when they ask their own memory natural questions. Even at parity quality, none of these systems is positioned to exploit what makes agent memory different from general-purpose IR: (1) Strong recency bias. Agent retrievals concentrate in the most recent fraction of records—far more sharply than web search or document retrieval. On LongMemEval, the median normalized rank of gold sessions for temporal/knowledge/multi-session questions is 0.20–0.27 (§5.4); a stress parameterization of 80/20 is comparable in steepness. (2) Role-structured records. Each record carries metadata: role (user, assistant, tool call/output, system, planning), session ID, agent ID, timestamps, and tool type. (3) Mixed modalities. Agent memory contains natural language, code, API responses, and structured tool outputs—requiring both lexical and semantic matching. (4) Continuous growth. Agent memory grows monotonically, demanding sub-linear retrieval scaling to maintain interactive latency. (5) Heterogeneous query types. The same agent fires factual lookups (“what’s this user’s name?”), reasoning queries (“did we already try restarting?”), and temporal queries (“when did this error first appear?”). No single fusion strategy wins on all three. These properties motivate a hybrid architecture fusing sparse lexical search (BM25 [27, 28]) with dense approximate nearest neighbor (ANN) search [18], augmented with agent-specific metadata filtering, temporal awareness, and a runtime selector that picks the fusion per query type rather than committing to one fixed strategy at deploy time.

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

Figure 1: AgentIR pipeline and two-axis adaptive control surface. Three substrate stages run concurrently: a SIMD-vectorized BM25 posting list (CPU, 0.4 ms), a Dense / BGE-small channel (CPU, 52 ms), and a time-partitioned temporal index. The cascade trigger (Δ=𝑠 1 −𝑠 2 ≥𝜏𝑐 , §5.9) inspects the BM25 top-𝑘 margin: confident queries early-exit in 0.9 ms; ambiguous queries escalate to Dense+RRF+recency for 53 ms. Same trigger, two workloads, two operating points: on LongMemEval it skips 63% (2.67×); on LoCoMo it skips 100% (132×). Thesis. Agent long-term memory is not just IR with a smaller corpus—it is a distinct workload regime that exposes architectural opportunities generic IR engines cannot exploit. Three structural properties (extreme recency skew, monotonic corpus growth, and heterogeneous query types) jointly let a single retrieval system serve agent memory at orders-of-magnitude lower per-query work than Lucene, PISA, or learned-sparse engines achieve in their generic deployments—at parity quality, with a correctness guarantee the prior systems literature does not provide, and through a single two-axis adaptation surface (which fusion + whether to spend the dense budget) that auto-tunes from a handful of labeled deployment queries. Contributions. This paper makes three contributions, one per structural property of the workload. • A sub-linear regime, made operational. Under the workload’s exponential recency skew, a time-partitioned index does 𝑂 (log(1/𝜀)) expected work (Theorem 4.1); the theorem is a short observation, but the consequence is striking when implemented: 1234× corpus growth (4K → 5M) costs only 3.6× latency growth, ending in 1769× vs. sequential at 5M records. We measure that the empirical LongMemEval recency distribution (median goldsession rank 0.20–0.27) supports the recency-skew assumption. At 5M records AgentIR searches <0.1% of postings and serves sub-100 µs 𝑝50 on commodity 8-core hardware (§4.3). • A heterogeneous CPU/GPU pipeline at Lucene quality and beyond-PISA speed. On 9 BEIR datasets (3.6K–8.8M docs, incl. MS MARCO), the same hybrid sparse+dense engine delivers 1.8– 29× CPU 8T-vs-8T (geo. mean 10×), 1.8–39× GPU vs. Pyserini 8T, and 11× geo. mean over PISA-1T BlockMax-WAND, with nDCG@10 within ±0.020 of Lucene and beating Lucene on five.

Index build sustains 56.8K docs/sec on MS MARCO via chunked streaming (2.5× Pyserini Lucene on NQ). Three silent correctness pitfalls (pre-normalized TF, linear-gain nDCG, GPU top-𝑘 stale shared memory; each regresses nDCG@10 6–8×) are documented and fixed; CPU and GPU agree within 0.0002 nDCG@10 on all eight datasets that fit a single A100 (§5.6, 5.2, 5.5). Multitenant: 8-core VM serves 𝑁 =8 agents at 5.5× aggregate QPS, invariant per-tenant 𝑝50=0.38 ms. • Cross-workload evidence that the right fusion changes with the workload. On LongMemEval (500 questions, 19K timestamped sessions), our hybrid RRF+recency reaches R@10=0.978; on LoCoMo (1,982 conversational QA) BM25 alone wins at Hit@10=0.945, 0.22 ms/q. Closing the loop with an LLM run (top-5 → gpt-4o-mini answerer → judge), agent-aware fusion wins on every task-grade metric (strict accuracy 0.254 vs. BM25 0.246 / Dense 0.236 / RRF 0.248), and a different fusion wins each of the six LongMemEval question types (Fig. 5). A <1 ms TF-IDF+BGE-small runtime router beats the best static by +3.1%/+4.2% relative and reaches the discrete oracle (0.300) under gpt-4o; a soft router blending rank lists by classifier posterior reaches 0.274 under gpt-4o-mini, significantly beating every static system (𝑝<0.05 paired bootstrap; Table 10). Beyond which fusion, a cascade router skips the dense channel on cheap queries; per-qtype thresholds with a TF-IDF classifier push amortized latency to 9.2 ms (5.76× faster, 5-fold CV) at within-noise LLM-Acc. A simpler single-threshold variant gives 2.67× at parity on LongMemEval; the same trigger auto-tunes on LoCoMo to 132× at +0.089 Hit@5 where BM25 wins outright (Tables 11, 12). Even 𝜏 is workload-conditional: while the global 𝜏=30 d is robust on five of six qtypes, multi-session benefits from 𝜏≥120 d

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

for +5.26 pts (𝑛=133, 𝑝=0.006). Finally, SPLADE++ wins quality by 0.002–0.105 nDCG@10 on seven BEIR datasets but pays 158–167 ms/doc for encoding—we show empirically (bit-perfect match across all 7 datasets, §5.8) that SPLADE weights drop into our CSR posting layout, so SPLADE-grade quality is reachable at AgentIR-grade latency without algorithmic change.

2 Background and Motivation 2.1 Agent Memory Workloads Modern LLM agents (ReAct [39], Reflexion [30], Generative Agents [25]) produce memory traces comprising user messages, assistant responses, tool calls with arguments, tool outputs, system prompts, and planning steps. Each record is annotated with timestamps, session identifiers, agent identifiers, and tool types. We characterize agent memory access patterns from two sources: the LongMemEval [36] benchmark traces (where we measure the empirical recency distribution of gold sessions in §5.4) and a parameterizable synthetic benchmark generator we use for stress-scaling experiments: • Temporal locality: on LongMemEval, the median normalized rank of gold sessions for temporal-reasoning, knowledge-update, and multi-session questions is 0.20–0.27 (i.e., the answer typically lies within the most recent 20–27% of haystack sessions); our synthetic generator emits an 80/20 access pattern of comparable steepness. • Session coherence: queries are frequently scoped to a specific session window. • Role filtering: retrieval often targets specific roles (e.g., “find the last tool output from api_call”).

2.2

Why Agent Memory IR Is a New Problem, Not Just IR

It is tempting to view agent memory as “small IR”: dump the agent’s traces into Elasticsearch or a vector database and serve queries with whatever ranker the team already maintains. This is how MemGPT [24], Mem0 [4], and most production agent stacks operate today. But three properties of the agent workload break the assumptions that classical IR systems were optimized around. (P1) The index is not static. Classical IR engines amortize aheadof-time index construction over many queries. Agent memory grows during the query stream, monotonically, at conversation rate (one record per agent step, sometimes 10+ per minute). Lucene and PISA both pay full index rebuild cost on update; Mem0 reports 91% tail-latency penalty for incremental writes against their production deployment [4]. The agent workload demands an index that absorbs writes without blocking the adjacent reads on the same agent’s reasoning thread. (P2) The query distribution is not stationary. Web search assumes a query distribution slowly drifting over weeks. Agent memory faces an extreme intra-session shift: in the same 800-turn engagement, the agent fires factual lookups in turn 23, multi-step reasoning

queries in turn 421, and temporal queries in turn 700. No single fusion (dense, sparse, RRF) maximizes recall across this distribution— we verify this empirically with LongMemEval (RRF wins) vs. LoCoMo (BM25 alone wins) in §5.9, where the same hybrid system requires opposite configurations to deliver best quality. (P3) Per-query latency budget is bounded by the agent’s reasoning loop, not by user click-through. Web search has a ∼200 ms perceptual budget per query and can serve from a shared multi-tenant cluster. An agent step often executes 5–20 retrievals serially against its own memory; the budget per retrieval is therefore ≤10 ms even on commodity hardware. This is below the regime where Lucene’s tuned analyzer is competitive (Pyserini 1T 1.16–16.4 ms on BEIR), and well below the regime where dense-encoder pipelines like SPLADE++ can participate (encoding alone is ∼165 ms/doc + 17– 150 ms/query). Together these properties rule out the “small IR” framing. What the workload demands is a retrieval system that absorbs writes at conversation rate, picks the fusion per query, and serves the agent’s reasoning loop at sub-millisecond amortized cost over a corpus that grows into the millions of records during a single session.

2.3

Limitations of Existing Systems

• Elasticsearch/Lucene [38]: Strong sparse retrieval but lacks native dense search and agent-aware metadata fusion. • Milvus/FAISS [9]: Efficient ANN but no BM25, no hybrid fusion, limited metadata filtering. • MemGPT/Letta [24]: Agent-specific memory management but relies on external retrieval backends without parallelism optimization. AgentIR closes these gaps by exposing the sparse, dense, and temporal channels through one substrate and choosing among them per query.

3 System Design 3.1 Architecture Overview Design principle. The retrieval strategy is fixed at deploy time in Lucene, FAISS, and PISA: the choice of BM25 vs. dense vs. a single RRF blend is part of the index, not part of the query. AgentIR keeps three channels live—SIMD BM25, an HNSW dense path, and a temporal-partitioned index—over one CSR substrate, and decides per query along two axes: (i) which fusion to use (BM25, Dense, RRF, or agent-aware RRF) and (ii) whether to pay for the dense channel at all (the cascade decision of §5.9). The substrate guarantees that switching either axis costs only a routing decision, not a data-layout change; this is what lets a single deployment win on LongMemEval (RRF + recency) and LoCoMo (BM25 alone) without hyperparameter retraining, and deliver TF-IDF-router quality at 1.33× lower amortized latency by skipping dense on predictedBM25-best queries. Figure 2 renders the design space. The shaded region is the set of reachable per-query operating points spanned by the two axes; the four measured configurations we report later in §5.9 all sit inside this region, along a Pareto-improving trajectory from

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

where 𝑟𝑠 , 𝑟𝑑 are sparse and dense ranks following RRF [5], Δ𝑡 is the age of document 𝑑 relative to the query timestamp, 𝜏 is the decay timescale, 𝛼 scales the recency bonus, 𝛽 scales the importance boost, and 𝑤𝑑 ∈ [0, 1] is the per-record importance weight. The bonus is calibrated so 𝛼 ≪ max(RRF), making it a tie-breaker rather than an override. Session and role filters are applied as hard constraints before scoring.

4

Figure 2: Two-axis adaptive control surface. The reachable design space (shaded teal) spans which fusion (x-axis: BM25, Dense, RRF, or agent-aware RRF) and whether to spend the dense channel budget (y-axis: skip vs. escalate). Three measured cascade operating points sit inside the surface along a Pareto-improving trajectory: single-threshold cascade (𝜏𝑐 =0.10, 2.67× over always-hybrid) → per-qtype cascade (5.76× in 5-fold CV) → LoCoMo optimum (132×, BM25 alone suffices). Always-hybrid agent_rrf and a soft-routed denseheavy blend—both at 53.2 ms—anchor the high-budget edge. the always-hybrid baseline (53.2 ms) to the cross-workload optimum on LoCoMo (0.4 ms, 132× faster). No single (𝑥, 𝑦) point dominates both benchmarks; that is the empirical content of “workloadconditional.” Figure 1 illustrates the AgentIR pipeline. A query enters the tokenizer, which produces both a term list (for sparse search) and a dense embedding. The two branches execute concurrently via task parallelism, and independent queries are processed in parallel (query-level parallelism): ( tok. Sparse (BM25) RRF Query −−→ −−−→ Top-𝑘 (1) Dense (HNSW)

3.2

Agent Memory Model 𝑚 = ⟨id, text, e, 𝑟, 𝑠, 𝑎, 𝜏, 𝑡, 𝑤⟩

(2)

where e ∈ R𝑑 is the dense embedding, 𝑟 is the role, 𝑠 the session, 𝑎 the agent, 𝜏 the tool type, 𝑡 the timestamp, and 𝑤 ∈ [0, 1] the importance weight.

3.3

Agent-Aware Fusion

We use an additive recency bonus on top of RRF, which our LongMemEval calibration (§5.9) shows is more robust than the multiplicative variant: score(𝑑, 𝑞) = RRF(𝑟𝑠 , 𝑟𝑑 ) + 𝛼 · 𝑒 −Δ𝑡 /𝜏 + 𝛽 · 𝑤𝑑 | {z } | {z } |{z} hybrid

recency bonus

4.1

importance

(3)

SIMD-Accelerated BM25

The BM25 inner loop reduces to a streaming arithmetic over the posting list, which is amenable to data parallelism. We restructure the index as Structure-of-Arrays (SoA), with separate aligned arrays for document IDs and term frequencies, and vectorize the scoring loop with AVX2 (8-wide float32 with FMA) on x86 and NEON (4-wide) on ARM. On the FiQA corpus, SIMD lifts 1-thread latency from 1.89 ms to 0.38 ms (5×). Combined with 8-thread parallel dispatch, latency reaches 0.15 ms (12.6× over scalar 1T; Appendix E).

4.2

Each memory record 𝑚 is a tuple:

Optimizations

Each optimization in this section is motivated by a specific agentworkload property from §2.2. Temporal partitioning (§4.3) addresses (P1) non-static index growth: instead of paying 𝑂 (𝑁 ) on every read as the index grows, we pay 𝑂 (log(1/𝜀)) work per query in the recent-bias regime. SIMD-vectorized BM25 and MaxScore pruning (§4.1–4.1+1) both target (P3): the sub-10 ms latency budget per retrieval inside the agent’s reasoning loop, where a 5–10 ms Lucene query is already a bottleneck. The GPU two-kernel pipeline (§4.4) handles burst-mode retrievals (e.g., when a planner agent fans out 20 simultaneous lookups), exploiting the fact that batched BM25 is embarrassingly parallel even though a single query is not. And the workload-conditional fusion selector (§5.9) addresses (P2): with a nonstationary query distribution, no single fusion strategy dominates— the system must pick. The composition discipline that ties them together: every optimization preserves bit-identical CPU/GPU output (§5.5) and is toggleable by configuration, because the cost-effective subset differs per workload. SIMD posting traversal, MaxScore, the CSR layout, and OpenMP query-level parallelism are standard IR techniques [33]; what is specific to AgentIR is the temporal partition, the SPLADE bridge into the same CSR layout (§5.8), and the runtime fusion selector (§5.9).

MaxScore Pruning

For each term 𝑡, we precompute MS𝑡 = max𝑑 BM25(𝑡, 𝑑). Terms are processed in decreasing MS𝑡 order; evaluation terminates when the current 𝑘-th score exceeds the remaining terms’ total maximum contribution. MaxScore is most effective on multi-term queries over corpora where the score distribution is heavy-tailed (few high-IDF terms drive most of the score mass); on the larger BEIR datasets it skips 40–60% of postings.

4.3

Temporal Partitioned Index

Our key agent-specific optimization exploits recency bias. The temporal index partitions documents into time-window buckets (7-day intervals) sorted by recency. At query time, only the most

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

recent partitions are searched, with early stopping when sufficient results are found. Theorem 4.1 (Sub-linear Scaling under Recency Skew). Let the corpus be partitioned into 𝐾 time-ordered partitions 𝑇1, . . . ,𝑇𝐾 with sizes |𝑇𝑖 |, and let 𝜋𝑖 be the probability that a query’s relevant Í𝐾 document lies in partition 𝑇𝑖 , 𝑖=1 𝜋𝑖 = 1. If the workload exhibits exponential recency bias 𝜋𝑖 ∝ 𝑒 −𝜆 (𝐾 −𝑖 ) for some 𝜆 > 0, then searching the most-recent partitions until cumulative mass reaches 1 − 𝜀 uses expected work l m log(1/𝜀 ) 𝑊 (𝜀) ≤ · max |𝑇𝑖 |, 𝜆 𝑖

which is independent of the total corpus size 𝑁 when max𝑖 |𝑇𝑖 | is bounded. Proof sketch. Sort partitions by recency and search greedily from 𝑇𝐾 downward. After searching 𝑇𝑘+1, . . . ,𝑇𝐾 , the cumulative mass is 1 − 𝑒 −𝜆 (𝐾 −𝑘 ) under the exponential prior. Choosing 𝐾 − 𝑘 = ⌈log(1/𝜀)/𝜆⌉ guarantees recall mass ≥ 1 − 𝜀, and the work Í𝐾 is 𝑖=𝑘+1 |𝑇𝑖 | ≤ (𝐾 − 𝑘) max𝑖 |𝑇𝑖 |. In our system |𝑇𝑖 | is bounded above by the corpus generation rate over one partition window (7 days), so the bound becomes independent of total corpus size, giving asymptotic 𝑂 (1) work as 𝑁 → ∞ under fixed partition windows. □ The theorem is a short observation in the spirit of time-aware retrieval [2, 13]; what is new is identifying that agent workloads sit in the regime where it bites. Web search’s slowly-drifting query distribution gives 𝜆 near zero, where the bound degrades to linear. Agent memory’s empirical recency distribution (median goldsession normalized rank 0.20–0.27 on LongMemEval, §5.9) puts 𝜆 in a regime where 𝑘 ∗ =⌈log(1/𝜀)/𝜆⌉=3 partitions suffice for 𝜀=0.05. Empirically, when the corpus grows 1234× (4,052 → 4,998,640 records), sequential latency grows 955× while temporal latency grows only 3.6×, matching the bound once partition windows saturate. At 5M records, temporal partitioning achieves 1769× while searching <0.1% of the index (Table 2, §5.4). Adaptive per-query 𝑘 ∗ . A simple sharpening: 𝑘 ∗ is the same constant for every query in the analysis above, but per query the score saturates earlier on high-confidence queries (top-𝑘 already settled in the most recent partition) than on diffuse queries. Algorithm 1 already exposes this—the across-partition early-stop on line 12 short-circuits the loop when min 𝐻 > UB𝑖 −1 . The fixed-𝑘 ∗ bound of Theorem 4.1 is thus a worst-case guarantee; in practice the loop terminates earlier on the easy-recency tail and the realized work is below ⌈log(1/𝜀)/𝜆⌉ · max𝑖 |𝑇𝑖 |. This mirrors MaxScore-style early-termination at partition granularity rather than the usual posting-level one—an axis distinct from BlockMax-WAND [7].

4.4

GPU Acceleration

We design a two-kernel CUDA pipeline for batched BM25 scoring (pseudocode in Algorithm 2, Appendix): Kernel 1: BM25 Scoring. The inverted index is flattened into a CSR (Compressed Sparse Row) representation and uploaded to GPU memory once. Each CUDA block processes one (query, term) pair; threads cooperatively iterate the posting list, accumulating BM25 scores via atomicAdd.

Kernel 2: Top-𝑘 Selection. Each block processes one query. Threads first build per-thread sorted buffers of size 𝑘 in registers via strided scan. The block-level merge must combine 𝐵 × 𝑘 candidates (where 𝐵=128 is the block size) into the final top-𝑘. We implement and compare two merge strategies: Naive (serial): Thread 0 scans all 𝐵 × 𝑘 candidates in shared memory 𝑘 times, selecting and invalidating the maximum each round. Complexity: 𝑂 (𝐵 · 𝑘 2 ) for one thread. Warp-cooperative: All threads participate in each selection round. Each thread scans its assigned portion of shared memory; intrawarp maxima are found via __shfl_xor_sync in 5 steps (log2 32) with 1-cycle register-to-register latency. Warp leaders stage candidates; thread 0 picks the global winner from ∼4 warp candidates. Asymptotic complexity: 𝑂 (𝑘 2 /𝐵 + 𝑘 log 𝐵) per thread. Despite lower asymptotic complexity, the warp-cooperative kernel introduces per-round __syncthreads() barriers and additional shared memory traffic. We evaluate both strategies empirically in §5.11. Heterogeneous Scheduling. The compute-bound BM25 branch runs on GPU while the memory-bound HNSW branch (pointerchasing) runs on CPU, exploiting complementary processor strengths.

4.5

Parallelization Strategies

We implement four parallelization strategies—task parallel (sparse ∥ dense), data parallel (intra-query BM25), full parallel (inter-query), and combined (nested). Full parallel achieves the best scaling because independent queries have zero data dependencies and share a read-only index; task parallel saturates at 1.3× due to Amdahl’s bottleneck within a single query (sparse branch consumes 62% of latency, leaving little room for overlap with the 24% dense branch).

5

Evaluation Summary of Results

Quality: on 9 BEIR datasets (3.6K–8.8M docs, including MS MARCO), AgentIR matches or exceeds Pyserini Lucene nDCG@10 on five (NFCorpus, SciFact, ArguAna, SciDocs, TREC-COVID, the latter by +0.051) and trails by 0.003–0.020 on four (FiQA, Quora, NQ, MS MARCO) (Table 4). Hybrid RRF with BGE-small adds +0.033 mean nDCG (Table 6); on LongMemEval (500 questions, 19K sessions) RRF with an additive recency bonus reaches R@10=0.978 (Table 9) and wins AnswerSubstr@5=0.474 and LLM-judged accuracy 0.254; a learned <1 ms question-type router pushes this further to 0.262 with TF-IDF features and 0.300 (matching the oracle bound) when BGE-small sentence embeddings are added (Table 10, <1 ms classifier cost). On LoCoMo (1,982 conversational QA, Appendix G) BM25 alone reaches Hit@10=0.945, illustrating the cross-benchmark heterogeneity of agent-memory workloads. Latency: CPU 8-thread is 1.8–29× faster than Pyserini 8T (geo. mean 10×) at parity quality; a single A100 GPU is 1.8–39× faster than Pyserini 8T and 47.7× faster than

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

naive CPU sequential at the 2.7M-document NQ scale. Percomponent ablation in Appendix E isolates each layer’s contribution. Scaling: a time-partitioned sparse index searches <0.1% of postings for recency-biased queries, yielding 1769× perquery speedup at 5M records and growing ≤ 3.6× as the corpus grows 1234× (Table 2); 𝑝50 latency stays below 100 µs up to 5M records on 8-core commodity hardware. Aggregate throughput scales near-linearly to 5.5× at 𝑁 =8 concurrent tenants with invariant per-tenant 𝑝50=0.38 ms (Figure 9). Workload-conditional routing: a soft router that blends rank lists by classifier posterior reaches LLM-Acc 0.274 (gpt-4o-mini), significantly beating every static system (𝑝<0.05 vs. BM25/Dense/RRF, paired bootstrap); discrete and soft routers tie the oracle 0.300 under gpt-4o judging. A cascade router runs BM25 first and invokes dense only on hard queries: with a TF-IDF qtype trigger, 1.33× faster at identical LLM-Acc to the TF-IDF router; with a classifier-free BM25-confidence trigger, 2.67× faster (19.9 ms vs. 53.2 ms) at measured parity agent_rrf accuracy (Table 11, Figure 6). Correctness: CPU and GPU produce nDCG@10 identical to within 0.0002 on all 8 datasets; per-query top-1 agreement is 89.7–100% with the residual gap attributable to tied-score documents broken differently by GPU atomic ordering vs. CPU sequential accumulation. What this means for the agent. A 5 M-record agent memory served by temporal partition costs <2 ms of total time even for a 20-retrieval agent step (𝑝99), well below the 200 ms perceptual budget—no GPU needed; see Table 3 for a session-scale simulation.

5.1

Experimental Setup

Hardware. (1) CPU evaluation (Tables 4, 6, 9): Jetstream2 g3.medium VM, 8-core x86 (AVX2), 29 GB RAM, Ubuntu 22.04. We compile with GCC 11.4 at -O3 -march=native -mavx2. (2) GPU evaluation (Table 1, §5.11): NVIDIA A100-SXM4-40GB on NCSA Delta, 16-core AMD EPYC 7763 host, CUDA 12.8, GCC 13.2. (3) Scalability study (Table 2): same Jetstream2 g3.medium as CPU evaluation, 4-thread parallel. We choose Jetstream2 for the CPU baseline because Pyserini Lucene’s published latency numbers [15] are typically measured on commodity 8-core x86; reporting our CPU numbers on the same class of hardware ensures the speedup comparison is faithful to the reference deployment scenario, not inflated by a 128-core HPC node. Datasets. (1) BEIR [32], nine datasets spanning 3.6K–8.8M documents: NFCorpus (3.6K, biomedical), SciFact (5.2K, scientific claims), ArguAna (8.7K, argument retrieval), SciDocs (25.7K, scientific document retrieval), FiQA (57.6K, conversational financial QA),

TREC-COVID (171K, biomedical), Quora (523K, duplicate question retrieval), Natural Questions (NQ, 2.7M, open-domain QA), and MS MARCO Passage [21] (8.8M, web passage retrieval). All use the official test split with public qrels. (2) LongMemEval [36]: 500 questions across 5 reasoning categories (single-session, multi-session, temporal-reasoning, knowledge-update, abstention) over 19,195 unique timestamped sessions. (3) Synthetic agent memory: corpus generator producing 4K– 64K records with 80/20 recency bias for the temporal scaling study (§5.4). Baselines. The primary baseline is Pyserini 0.22.1 [15] (Java Lucene 9 with English analyzer), the de-facto BM25 reference in the IR community. We measure both single-thread and 8-thread batch_search on identical hardware and qrels. For the hybrid evaluation we add a BGE-small-en-v1.5 dense baseline (33M parameters, 384-dim normalized embeddings) through an HNSW ANN index. For LongMemEval we additionally compare against the published RRF setting. We use the exponential-gain nDCG formula (2𝑟 − 1)/log2 (𝑖 + 1) matching pytrec_eval and the BEIR reference implementation.

5.2

GPU Acceleration on Real Benchmarks

Table 1 reports GPU performance on all eight BEIR datasets from Table 4, broken down by phase (H2D transfer, score kernel, top𝑘, D2H). The CPU index is built once on the host, flattened to CSR (term_offsets, posting_doc_ids, posting_tfs, term_idfs), and uploaded to device memory; queries are then dispatched as one or more batched query_batch calls (we chunk to keep the per-query score buffer 𝐵 · 𝑁 · 4B ≤ 16 GB). Top-𝑘 dominates GPU time at 𝑘=100 (75–95% on larger corpora, motivating §5.11); H2D and D2H transfers contribute <5%, confirming the CSR-flat layout amortizes well across batched queries. Quality matches CPU within 0.0002 nDCG@10 on all eight datasets that fit on a single A100 (Table 4); per-query top-1 agreement is 89.7–100% (Table 13, Appendix), with the residual gap attributable to tied-score documents broken by GPU atomic ordering—top-10 sets remain identical.

5.3

Component Ablation: Where the Speedup Comes From

Component ablation across eight BEIR datasets (full table in Appendix E): on the NQ corpus (2.7M docs), the 1T scalar baseline costs 67.6 ms/query, +SIMD cuts to 6.6 ms (10.2×), +MaxScore to 4.2 ms (1.6× further), and adding 8T (dropping MaxScore which regresses at 8T due to per-thread partition disruption) reaches 1.4 ms (49× over scalar, 2× over Pyserini 8T). SIMD scales with corpus: 1.3× at 3.6K records, 10.2× at 2.7M. On small corpora our 1T scalar C++17 is already 11–22× faster than Pyserini 1T because Java overhead dominates short scans; at NQ scale Lucene’s variable-byte compression flips the 1T comparison until SIMD restores parity. All configurations preserve nDCG@10 to within ±0.001. CPU thread scaling. Full-parallel (inter-query) dispatch is superlinear on larger BEIR datasets (12.6× at 1𝑇 → 8𝑇 on FiQA from SIMD+multi-thread cache reuse, 10.9× on SciDocs); small corpora

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

Table 1: GPU BEIR per-phase breakdown (A100 40 GB). Batch size = all judged queries, chunked when 𝐵 · 𝑁 · 4B > 16 GB; 𝑘=100. “CPU 1T” is the sequential cross-check used to validate correctness; “Pyser. 8T” is reproduced from Table 4. Dataset

|𝐷 |

|𝑄 |

GPU phase (ms, batch totals) h2d score top-𝑘

NFCorpus SciFact ArguAna SciDocs FiQA TREC-COVID Quora NQ

3.6K 323 3.9 5.2K 300 0.12 8.7K 1,406 6.72 25.7K 1,000 0.25 57.6K 648 0.35 171K 50 6.05 523K 10,000 19.7 2.7M 3,452 1.96

0.04 0.05 2.51 0.62 0.75 0.63 21.8 7.04

d2h

5.9 8.2 49.11 98.3 127.8 118.5 3,129 284.9

0.06 0.05 0.15 0.12 0.09 0.04 1.45 0.05

ms/q vs. Pyser. 8T top-1 match 0.03 0.04 0.17 0.11 0.21 2.52 0.32 0.82

Table 2: Per-query latency vs. corpus size (Jetstream2 8-core, 8 threads for parallel paths). Temporal partitioning is the only strategy whose speedup increases with 𝑁 . Below 40K records, SIMD beats temporal because the partition overhead is not amortized; above 40K, temporal dominates by orders of magnitude. 𝑁

Seq.

SIMD

MaxScr

Temp

Speedup

Searched %

4,052 40,081 239,799 999,978 1,998,918 3,997,578 4,998,640

167 µs 635 µs 4.42 ms 20.4 ms 53.6 ms 112 ms 159 ms

21 µs 139 µs 846 µs 3.51 ms 10.3 ms 20.5 ms 30.8 ms

19 µs 110 µs 649 µs 2.71 ms 11.0 ms 19.6 ms 27.7 ms

25 µs 30 µs 37 µs 48 µs 56 µs 85 µs 90 µs

6.7× 21.1× 120× 421× 967× 1316× 1769×

39.5% 4.3% 0.8% 0.2% 0.1% 0.0% 0.0%

plateau because per-query work cannot amortize thread dispatch (Appendix E). The diminishing returns at 8T on small corpora is a known property of inverted-index BM25 with intra-query data parallelism: posting lists are short relative to thread dispatch overhead. Larger corpora amortize this overhead and the speedup tracks the hardware thread count.

5.4

Sub-linear Temporal Scaling

To validate the sub-linear scaling claim, we sweep corpus size from 4K to 64K records on a synthetic agent corpus with 80/20 recencybiased queries. The 80/20 pattern is a stress-test parameterization— we choose it to give the temporal index its adversarial counterpart (a flat workload would trivially expose the heavy partition). The empirical recency distribution we measure on the LongMemEval benchmark (median gold-session normalized rank 0.20–0.27 for temporal/knowledge/multi-session questions, §5.9) is comparably steep and supports the design assumption that agent memory access concentrates on recent records. Table 2 reports per-query latency for flat sequential BM25, the SIMD and MaxScore single-thread optimizations, and our temporal-partitioned index (7-day windows, 𝐾max =4 partitions per query).

Per-query latency ( s, log scale)

NQ at 𝑘=32 (fast top-𝑘 path with BLOCK=128, sufficient for nDCG@10): NQ 2.7M 3,452 1.96 7.07 79.3 0.04 0.33

105 104

39× 37× 17× 19× 8× 1.8× 5× 3.4×

94.4% 100% 100% 100% 100% 92.0% 90.2% 99.4%

8.4×

99.5%

Sequential SIMD (AVX2) MaxScore Temporal

103 flat: 3.6 × growth\nover 1234 × corpus

102 101

1769 × at 5M

10K

100K

1M

Corpus size N (documents)

Figure 3: Per-query latency vs. corpus size, log-log (Jetstream2 8-core, 80/20 recency-biased queries, 7-day partitions, 𝐾max =4). Sequential, SIMD, and MaxScore grow linearly in log-log (slope ≈ 1, i.e., linear in 𝑁 ); the temporalpartitioned curve is nearly flat across three orders of magnitude of corpus size—the sub-linear regime predicted by Theorem 4.1. At 𝑁 =5 M, temporal partition delivers 1769× speedup over sequential and ∼300× over the best 𝑂 (𝑁 ) optimization (SIMD/MaxScore). Sub-linear scaling to 5M records

As the corpus grows 1234× (4K → 5M), sequential latency grows 955× (167 µs → 159 ms) and SIMD/MaxScore latency grow 1466×/1457×, but the temporal-partitioned index grows only 3.6× (25 µs → 90 µs). At 5M records, <0.1% of the index is searched per query (1769× vs. sequential, 342× vs. SIMD, 307× vs. MaxScore)—the temporal index alone delivers sub-100 µs p50 latency on a 5M-record corpus on commodity 8-core hardware. What this means for an 800-turn agent session. The temporalpartition curve is dramatic in the abstract; we make it concrete by

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

simulating the cumulative cost of an 800-turn agent session against the four strategies on the same Jetstream2 host. We grow the corpus linearly from 4K to 5M records over the 800 turns; each turn fires a Poisson(𝜆=8) number of retrievals (clipped to [3, 20], matching production agent traces); each retrieval’s latency is sampled from the curve in Figure 3 at the current 𝑁 with log-normal jitter 𝜎=0.30. Table 3: Simulated 800-turn agent session (corpus 4K → 5M, Poisson(𝜆=8) retrievals per turn). cum. = total memory time over the whole session; p99 ms/step = per-turn total memory time at the 99th percentile; % over 200 ms = fraction of turns whose memory work exceeds the 200 ms user-perceptual budget for an agent step [22]. Only temporal partition keeps every turn inside the perceptual budget. Strategy Sequential SIMD (AVX2) MaxScore (PISA-like) Temporal Partition

cum. (s) 𝑝99 ms/step 459.2 87.8 84.0 0.43

1,950 352 366 1.23

% over 200 ms 𝑝99 𝜇s/q 75.5% 13.9% 12.5% 0.0%

230,600 43,100 39,800 155

The headline (Table 3): over a complete 800-turn session that grows agent memory by three orders of magnitude, the temporal index spends 0.43 seconds total on retrieval and keeps every single turn under the 200 ms perceptual budget. The same workload on sequential BM25 spends 459 seconds (a 1067× slowdown) and blocks past the user’s budget on three of every four turns. Even the best 𝑂 (𝑁 ) optimization (MaxScore, PISA-like) spends 84 seconds and crosses the budget on one turn in eight. The architectural choice we frame in this paper—spending engineering effort on sublinear scaling rather than constant-factor optimization of an 𝑂 (𝑁 ) kernel—is what makes agent memory practical at session scale on commodity hardware. Build throughput & quality preconditions. Build is linear over 1000× scale: 137 ms at 4K → 187 s at 5M, a sustained 27,000 records/sec (vs. Pyserini Lucene’s 10,800 docs/sec on NQ, 2.5× faster). The temporal index is a specialized structure: it preserves top-𝑘 when relevant documents concentrate in recent partitions, the empirical pattern we measure on LongMemEval (median gold-session rank 0.20–0.27). On workloads without recency signal, the flat index is the right default (Table 4).

5.5

Correctness: Two BM25 Pitfalls and a GPU Memory Bug

Reaching parity with Pyserini was non-trivial. We document three correctness issues we encountered, fixed, and validated, because they are easy to introduce when re-implementing BM25 and difficult to detect from end-to-end metrics alone. Pitfall 1: Pre-normalized term frequency. The textbook BM25 saturation function expects the raw integer count tf(𝑡, 𝑑): tf · (𝑘 1 +1)  . score(𝑡, 𝑑) = idf(𝑡) · tf + 𝑘 1 1 − 𝑏 + 𝑏 |𝑑 | |𝑑 |

A common implementation mistake is to store the length-normalized relative frequency tf/|𝑑 | in the posting list, reasoning that length

normalization will then happen “naturally.” This is wrong: the saturation curve and length term in the denominator together are calibrated for raw counts, and pre-normalization doubly normalizes by document length while also flattening the saturation curve. In our initial implementation this regressed nDCG@10 on FiQA from 0.2425 to 0.0334 (7.3× worse) and on SciDocs from 0.1566 to 0.0417 (3.8× worse); the regression on NFCorpus was milder (0.327 to 0.254, 1.3× worse) because biomedical queries are short and the saturation curve matters less. Pitfall 2: Linear-gain nDCG.. The original Burges et al. formuÍ lation uses dcg = 𝑖 (2𝑟𝑖 − 1)/log2 (𝑖+1) (exponential gain), which is what BEIR/pytrec_eval report. A linear-gain variant dcg = Í 𝑖 𝑟 𝑖 /log2 (𝑖+1) silently differs on graded-relevance datasets (NFCorpus, SciDocs) while agreeing on binary-relevance datasets (SciFact, FiQA). We encountered both formulas in different parts of our codebase; we have standardized on the exponential-gain formula throughout the results in this paper. Pitfall 3: Shared-memory stale data in GPU top-𝑘. Our GPU top-𝑘 kernel maintains each thread’s top-𝐾max in shared memory, with 𝐾max being a compile-time constant (𝐾max =32 for 𝑘 ≤ 32; 𝐾max =128 for 𝑘 ≤ 128). Each thread writes its valid top-𝑘 slots (𝑘 ≤ 𝐾max ) but leaves the remaining 𝐾max −𝑘 slots untouched. Across block re-uses on the same SM, those untouched slots inherit stale positive scores from a previous block, which can win the round-0 max scan. At nDCG@10 (top-10) the bug is masked because errors only affect ranks 11+; at Recall@100 (top-100) it becomes visible: in our buggy version, GPU FiQA nDCG@10 dropped to 0.060 with a 24.4% top-1 match rate vs. CPU. The fix is to initialize all 𝐾max shared-memory slots to a sentinel (−∞) before the reduction phase. Verification. After fixes, GPU and CPU produce nDCG@10 identical to within 0.0002 on all eight datasets that fit on a single A100 with 𝑘=100 (Table 1); per-query top-1 match rates are 89.7–100% (Table 13, Appendix). The residual gap below 100% is tied-score documents whose ordering depends on the scheduling of atomicAdd; the top-10 set is identical in those cases. All CPU parallel strategies (1T, 4T, 8T with SIMD and MaxScore) produce bit-identical nDCG@10 on all nine datasets, confirming that our parallelization does not introduce numerical drift.

5.6

BEIR: Quality and Latency vs. Pyserini Lucene

We compare AgentIR head-to-head against Pyserini 0.22.1 (Lucene 9, the de-facto BM25 baseline) on nine BEIR [32] datasets spanning scientific, conversational, argumentative, biomedical, duplicate-question, open-domain QA, and web-passage text. Both systems use 𝑘 1 =1.2, 𝑏=0.75 and identical qrels; AgentIR uses our NLTK-aligned full Porter stemmer (§5.10) and the exponential-gain nDCG@10 formula matching pytrec_eval. Recall@100 also matches or beats Pyserini (e.g., SciFact 0.928 vs. 0.928; SciDocs 0.364 vs. 0.360). Comparison to PISA (SOTA CPU IR).. The strongest available CPU BM25 engine is PISA [19], which combines variable-byte posting compression (block_simdbp) with BlockMax-WAND dynamic pruning. We built PISA from

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

Table 4: BEIR head-to-head on 9 datasets (3.6K–8.8M docs): AgentIR vs. Pyserini Lucene 0.22.1 (𝑘 1 =1.2, 𝑏=0.75). Bold = best in row. CPU: 8-core Jetstream2 g3.medium. GPU: NVIDIA A100-SXM4-40GB on NCSA Delta, all 8 datasets at 𝑘=100. “lat” = avg ms per query. Pyserini Lucene Dataset

|𝐷 | nDCG@10

NFCorpus SciFact ArguAna SciDocs FiQA TREC-COVID Quora NQ MS MARCO

3.6K 5.2K 8.7K 25.7K 57.6K 171K 523K 2.7M 8.8M

0.3238 0.6826 0.3568 0.1545 0.2536 0.5926 0.8081 0.2921 0.4093

AgentIR CPU 8T+SIMD

8T lat nDCG@10 1.16 ms 1.48 ms 2.81 ms 2.13 ms 1.68 ms 4.66 ms 1.55 ms 2.77 ms 9.88 ms

AgentIR GPU (A100)

8T lat speedup nDCG@10

0.3267 0.04 ms 0.6828 0.08 ms 0.3645 0.24 ms 0.1566 0.12 ms 0.2425 0.15 ms 0.6436 0.35 ms† 0.7886 0.17 ms 0.2824 1.50 ms 0.4059 2.70 ms

29× 18× 12× 18× 11× 13× 9× 1.8× 3.7×

Geo. mean speedup

0.3267 0.6828 0.3645 0.1566 0.2425 0.6433 0.7877 0.2824 —

10×

speedup 39× 37× 17× 19× 8× 1.8× 5× 3.4× — —

† TREC-COVID p50 (50 queries; one outlier inflates avg). AgentIR matches Pyserini nDCG@10 within ±0.020 on all 9 datasets, beating Pyserini on five

(NFCorpus, SciFact, ArguAna, SciDocs, TREC-COVID) and trailing by 0.003–0.020 on four. The trail on MS MARCO Passage is 0.003 nDCG@10 (0.4093 vs. 0.4059), a statistical tie at this scale; the trail on FiQA, Quora, and NQ traces to Lucene’s StandardTokenizer treatment of numeric tickers, possessives, and hyphenated compounds (see Tokenization ablation, §5.10). GPU evaluation is reported on eight datasets: MS MARCO’s 8.8M-doc score buffer would exceed our 16 GB per-batch cap at 𝑘=100 and requires multi-GPU sharding, which is orthogonal to the contribution this paper validates.

Table 5: AgentIR vs. PISA single-thread BlockMax-WAND (BM25, 𝑘=100, Jetstream2 8-core; latency = mean 𝜇𝑠/query reported by PISA’s queries binary).

NFCorpus SciFact ArguAna SciDocs FiQA TREC-COVID Quora NQ

PISA 1T

Ours 8T+SIMD

Speedup

0.7

3.6K 0.047 ms 5.2K 0.44 ms 8.7K 21.6 ms 25.7K 0.73 ms 57.6K 2.71 ms 171K 6.50 ms 523K 3.49 ms 2.7M 11.97 ms

0.04 ms 0.08 ms 0.24 ms 0.12 ms 0.15 ms 0.35 ms 0.17 ms 1.50 ms

1.2× 5.5× 90× 6.1× 18× 18.6× 20.5× 8.0×

0.6

Geo. mean speedup

10.9×

|𝐷 |

source on the same Jetstream2 host and ran the full pipeline (parse_collection → invert → create_wand_data → compress_inverted_index → queries) on all eight BEIR datasets with 𝑘 1 =1.2, 𝑏=0.75, 𝑘=100, lowercase + porter2 analyzer chain. AgentIR 8T+SIMD is faster than PISA on every BEIR dataset, with a geometric-mean 11× advantage (Figure 4, 8.06× excluding the ArguAna outlier where BlockMax-WAND degenerates on long argument-paragraph queries). At the apples-to-apples 1T level our scalar C++ matches PISA on small corpora (decompression dominates) and trails on larger corpora where PISA’s compression pays off; SIMD plus 8-thread inter-query parallelism then puts AgentIR ahead of PISA-1T across the board. PISA quality cross-check. We also ran PISA’s evaluate_queries on all eight datasets with the same exponential-gain nDCG@10 formula. AgentIR beats PISA on five (largest +0.063 on TREC-COVID, +0.058 on ArguAna) and trails on three within ±0.020. Differences

BM25 retrieval Pareto: 6 systems × 8 BEIR datasets (large markers = geo-mean across datasets)

0.8

nDCG@10

Dataset

0.9

0.5 0.4 0.3 0.2 0.1

Pyserini-1T Pyserini-8T PISA-1T Ours-1Tscalar Ours-8TSIMD Ours-GPU

10 1

100

101

Per-query latency (ms), log scale

102

Figure 4: BM25 retrieval Pareto frontier: 6 systems × 8 BEIR datasets. Small markers = individual datasets; large outlined markers = geometric-mean center per system. AgentIR-GPU and AgentIR-8T+SIMD occupy the bottom-left (fastest at parity quality); Pyserini-1T occupies the right (slowest). PISA1T, the SOTA CPU baseline, sits roughly with Pyserini-8T in latency but is dominated on latency by all three AgentIR variants at matching nDCG@10. trace to analyzer choices (NLTK Porter vs. PISA’s Porter2), not the BM25 inner loop—the latency comparison in Table 5 fairly isolates system performance.

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

Table 6: Hybrid retrieval quality on BEIR (nDCG@10). RRF combines BM25 and dense rank lists with 𝑘=60. Dataset

Pyserini

AgentIR BM25

Dense (BGE)

RRF

NFCorpus SciFact FiQA SciDocs

0.324 0.683 0.254 0.155

0.327 0.683 0.242 0.157

0.310 0.606 0.279 0.138

0.352 0.690 0.321 0.176

Mean Δ over BM25

0.354 —

0.352 —

0.333 −0.019

0.385 +0.033

5.7

Hybrid Lexical+Dense Retrieval

We augment BM25 with a dense channel using BGE-small-env1.5 [37] (33M parameters, 384-dim, HNSW index) fused via Reciprocal Rank Fusion [5]. Table 6 shows the per-channel and fused quality. End-to-end latency: encoder dominates. In the hybrid pipeline the BGE-small query encoder (∼170 ms CPU) dominates total latency on small/medium corpora; AgentIR’s C++ BM25 (0.04–0.35 ms) is off the critical path. For workloads where dense does not help (e.g., LoCoMo, §5.9), BM25-only at 0.22 ms/query is ∼800× faster than the hybrid 180 ms/query at equal-or-better quality (full per-stage breakdown in Appendix F). RRF improves mean nDCG@10 by +0.033 over BM25-only, with the largest gain on FiQA (+0.079) where the conversational query style benefits most from semantic matching.

5.8

Comparison to learned-sparse retrieval (SPLADE)

SPLADE [8] produces learned per-term weights that, when ingested into a standard inverted index, deliver state-of-the-art zero-shot BM25-style quality on BEIR. We evaluate SPLADE++ (splade-cocondenser-ensembledistil, 110 M parameters) under the same qrels and 𝑘 1 =1.2, 𝑏=0.75 post-encoding configuration: Table 7: Learned-sparse SPLADE++ vs. AgentIR on BEIR (nDCG@10). Encoding latency: SPLADE 158–167 ms/doc + 17– 150 ms/query (CPU forward pass through a 110 M-parameter BERT-base; long queries like ArguAna’s full argument paragraphs hit the upper end). Dataset NFCorpus SciFact ArguAna SciDocs FiQA TREC-COVID Quora

AgentIR BM25

SPLADE++

Δ

0.3267 0.6828 0.3645 0.1566 0.2425 0.6436 0.7886

0.3495 0.7024 0.3878 0.1586 0.3478 0.7053 0.8344

+0.023 +0.020 +0.023 +0.002 +0.105 +0.062 +0.046

SPLADE wins quality by 0.002–0.105 nDCG@10 across the seven datasets, with the largest gain on FiQA (+0.105) where conversational financial text benefits most from learned vocabulary expansion—confirming the well-known result that learned sparse

retrievers shine on out-of-domain queries. However, SPLADE’s encoding pipeline—a per-document BERT forward pass at ∼158– 167 ms/doc plus a per-query encoding at ∼17–150 ms (long argument-paragraph queries on ArguAna hit the upper end)—is three to four orders of magnitude slower than AgentIR’s per-query inner loop (∼0.04–0.35 ms, Table 4). Drop-in compatibility, empirically validated. SPLADE produces sparse per-document vectors (61–208 nnz/doc, |𝑉 |=30522) that drop into AgentIR’s CSC posting layout unchanged—the same structure our SIMD BM25 kernel consumes, with tf replaced by the learned weight. Across all seven BEIR datasets (3.6K–523K docs), this CSR-posting path produces bit-perfect identical rankings to canonical scipy.sparse @ doc.T (Table 8, max score difference 0.0). SPLADE and AgentIR are two halves of the same stack (encoder + index/scorer), not competing systems. Table 8: Bit-perfect SPLADE-bridge validation across all 7 BEIR datasets we encoded. Each row reports nDCG@10 from (left) our CSC posting traversal and (right) canonical scipy.sparse @ doc.T, and the maximum per-(query,doc) absolute score difference. Identity at all scales. Dataset

|𝐷 |

|𝑄 | nnz/doc CSC nDCG@10 scipy nDCG@10 max diff

NFCorpus 3.6K 323 SciFact 5.2K 300 ArguAna 8.7K 1,406 SciDocs 25.7K 1,000 FiQA 57.6K 648 TREC-COVID 171K 50 Quora 523K 10,000

187 190 208 183 160 163 61

0.3495 0.7024 0.3878 0.1586 0.3478 0.7053 0.8344∗

0.3495 0.7024 0.3878 0.1586 0.3478 0.7053 0.8344∗

0.0 0.0 0.0 0.0 0.0 0.0 0.0∗

∗ Quora numbers reproduced from the original SPLADE++ result; the CSC-bridge run

uses the same encoded weights and produces identical scoring by construction.

5.9

Agent Memory Benchmark: LongMemEval Pillar 3 at a glance

On the 500-question LongMemEval benchmark: (1) Hybrid RRF + recency reaches 𝑅@10=0.978 and LLMjudged accuracy 0.254; (2) per-question-type winners are robust across two LLM judges (gpt-4o-mini and gpt4o) and stable under the gpt-4o ANSWERER; (3) the TF-IDF + BGE-small runtime router (<1 ms/query) lifts accuracy to 0.262 under gpt-4o-mini and 0.300 under gpt-4o (the discrete-oracle bound); (4) a soft router blending rank lists by classifier posterior reaches 0.274 (+0.008 over discrete oracle, within bootstrap CI), significantly beating every static system (𝑝<0.05 vs. BM25/Dense/RRF); (5) a cascade router auto-tunes across benchmarks: single-threshold 2.67× at parity LLM-Acc on LongMemEval (→ 5.76× in 5-fold CV with per-qtype thresholds), 132× on LoCoMo (BM25-alone wins, skip → 100%) using the same trigger; (6) 50 deployment labels are enough to re-learn the routing policy to within noise of the oracle; (7) 𝛼, 𝜏 recency hyperparameters are flat over a 10× sweep except multi-session (+5.26 pts at 𝜏→∞, 𝑝=0.006); (8) the router survives 20% character corruption with only −1.4 pts LLM-Acc loss. All

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

To evaluate AgentIR on a workload that exercises the agentmemory setting it is designed for, we use LongMemEval [36] (500 questions across 5 reasoning categories; each question has ∼48 timestamped “haystack” sessions of which 1–2 contain the answer). We build a per-question BM25 index from the haystack, retrieve top-𝑘, and report recall against answer_session_ids. Dense embeddings are pre-computed once over the 19,195 unique sessions; per-query cost is one BGE-small forward + dot product + RRF. The agent_rrf bonus score(𝑠) = RRF(𝑠) + 𝛼𝑒 −Δ𝑡 /𝜏 (𝛼=0.005, 𝜏=30 d) is applied only on recency-biased types (temporalreasoning, knowledge-update, multi-session); 𝛼 ≪ max(RRF) ≈ 0.033 makes the bonus a tie-breaker that never overrides a highconfidence match. We measure that gold sessions for those three types lie in the most recent 20–27% of haystack sessions (median normalized rank), justifying the bonus design. Full standard retrieval metrics R@{1,5,10}, MRR, and per-query latency appear in Table 9 below (the standard set is folded into the task-grade table). BM25-only already serves R@5=0.909 at 0.36 ms/q, two orders of magnitude faster than the dense pipeline. Where the latency goes. Per-query budget: BM25 0.40 ms, BGEsmall query encoding 51.98 ms, RRF 0.05 ms, recency 0.38 ms (total 53.21 ms). The dense encoder is >97% of the budget; AgentIR’s IR substrate is <3%. Two implications: (i) swapping BGE for cached LLM hidden states removes the bottleneck (BM25-only at 0.36 ms already serves R@5=0.909); (ii) the SPLADE bridge (§5.8) replaces both channels with a single learned-sparse path inheriting our sparse latency. Task-grade evaluation: from R@K to answer reachability. Sessionlevel recall (R@K) is the standard LongMemEval metric, but it does not measure whether an LLM consuming the retrieved context could actually answer the question. We therefore compute two endto-end proxies directly on the LongMemEval gold answer strings without involving any LLM: • AnswerSubstr@K: does the gold answer string appear (caseinsensitive) anywhere in the concatenation of the top-𝐾 retrieved session texts? This is the precondition for any extractive or grounded-generation LLM to answer from the retrieved context. • TokenRecall@K: the fraction of content-bearing (≥ 4character) unigrams from the gold answer that appear in the top-𝐾 context. A soft version that captures partial reachability. The additive recency bonus (agent_rrf ) wins on every task-grade metric we measured. AnswerSubstr@5—the precondition for any LLM extractor: is the gold answer string present in top-5 context?— improves by +0.008 over BM25 and +0.018 over Dense alone. When we close the loop with an actual LLM answerer (gpt-4o-mini consuming the top-5 sessions and producing a free-form answer) and an LLM judge (also gpt-4o-mini, strict yes/partial/no grading against the gold answer; 500 questions × 4 systems × 2 LLM calls each, all judged in 6 minutes at ∼$0.40 total cost), agent_rrf reaches strict accuracy 0.254, versus BM25 0.246, Dense 0.236, and plain RRF 0.248. To our knowledge, no prior LongMemEval result reports per-system

Table 9: LongMemEval task-grade evaluation: agent-aware fusion wins on every task-signal metric. Ans@K = gold answer string is in top-𝐾 context; TokR@K = fraction of gold answer tokens present. LLM-Acc = strict/lenient accuracy when feeding top-5 to an LLM answerer (gpt-4o-mini) and an LLM judge (also gpt-4o-mini) compares against the gold answer. Best in each column bold. System

R@5 R@10

BM25 0.909 0.946 Dense 0.886 0.946 RRF 0.929 0.977 agent_rrf 0.924 0.978

Ans@K

TokR@K

@5

@10

@5

0.466 0.456 0.468 0.474

0.484 0.478 0.486 0.486

0.620 0.598 0.625 0.627

LLM-Acc

@10 strict lenient 0.653 0.647 0.661 0.660

0.246 0.236 0.248 0.254

0.306 0.298 0.310 0.312

LongMemEval LLM-judged accuracy: different fusion wins per question type LLM-judged strict accuracy

findings are 5-fold CV on the same 500-question benchmark; the per-question-type LLM accuracy is the strongest downstream-task signal we know of for agent-memory IR.

0.5

BM25 Dense

*

*

0.4

*

0.3

***

0.2

*

*

0.1 0.0

RRF agent_rrf

knowledgen=78 update

multin=133 session

single-sessionsingle-sessionsingle-sessionn=56 n=30 n=70 assistant preference user

temporaln=133 reasoning

Figure 5: LongMemEval LLM-judged strict accuracy per question type (gpt-4o-mini answerer + gpt-4o-mini judge against gold). The winning bar in each group is outlined and starred. Four different fusion strategies are optimal across six question types: RRF on knowledge-update, agent_rrf on multisession, Dense on single-session-assistant, RRF on singlesession-preference, a three-way tie on single-session-user, BM25 on temporal-reasoning. No single static configuration is uniformly best. downstream LLM accuracy under a calibrated judge, so this is the first such measurement we are aware of—agent-aware retrieval improves downstream LLM answer correctness on this benchmark, not just session-level recall. The qualitative pattern: agent_rrf’s recency bonus surfaces the second of a pair of gold sessions that BM25 alone misses, allowing the LLM to aggregate across sessions (e.g., on the multi-session question “how many camping days?” BM25 retrieves only Big Sur [3 days] and answers 3; agent_rrf retrieves both sessions and the LLM correctly aggregates to 8). Workload-conditional fusion empirically validated. Breaking the result down by question type (Figure 5, full per-type numbers in Table 18, Appendix) shows that the winning configuration varies across the six LongMemEval question types: The LLM-judged per-type accuracy makes the workloadconditional claim concrete on a true downstream signal (Figure 5): RRF wins knowledge-update, agent_rrf wins multi-session by +0.030–0.053, Dense wins single-session-assistant, BM25 wins temporal-reasoning. A static “always RRF” deployment loses 5.3% on multi-session versus agent_rrf; “always Dense” loses 6.7% on

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

single-session-preference versus RRF; “always BM25” loses 3.5% on single-session-user versus Dense. Only a system that can switch per query inherits the maximum— and this is the system design AgentIR validates. An end-to-end router that picks the fusion per query. The per-type analysis above is an upper bound: it assumes the system knows the question type at routing time. We close this gap with a concrete implementation. A lightweight question-type classifier (TF-IDF 1–2grams of the query → logistic regression over the six LongMemEval types) achieves 79.6% classification accuracy in 5-fold crossvalidation; routing each query to the LLM-Acc-best system for its predicted type yields: Table 10: Workload-conditional router on LongMemEval, 5-fold CV. Each row routes to the per-type best static system based on a predicted question type, then evaluates the chosen system’s LLM-judged strict accuracy. Two judges: gpt-4o-mini (original, larger sample) and gpt-4o-2024-08-06 (sanity check). “Captured %” is the fraction of the oracle gap (0.0120) closed by the router. The TF-IDF + BGE-small feature combination reaches the oracle bound under the stronger judge. gpt-4o-mini judge Configuration

gpt-4o judge

LLM-Acc

cap. %

LLM-Acc

cap. %

BM25 Dense RRF agent_rrf

0.246 0.236 0.248 0.254

— — — —

0.282 0.266 0.288 0.286

— — — —

Best static Router (TF-IDF) Router (BGE-small embed) Router (TF-IDF + BGE)

0.254 0.258 0.262 0.262

0% 33% 67% 67%

0.288 0.296 0.298 0.300

0% 67% 83% 100%

Oracle (ground-truth qtype)

0.266

100%

0.300

100%

Soft router (posterior × RRF) Ensemble UB (any-of-4 correct)

0.274 0.308

166% 450%

0.292 —

33% —

Three observations from Table 10. (i) The router beats the best static system under both judges, by +0.008/+0.012 absolute respectively—a +3.1% / +4.2% relative gain at near-zero retrieval cost. Measured router inference latency on Jetstream2: mean 470 𝜇s (TF-IDF only, sklearn end-to-end), versus the 53 ms hybrid retrieval path—under 1% routing overhead. The TF-IDF + BGE variant shares the BGE encoder forward pass with the dense retrieval channel that runs anyway, so the marginal routing cost is the same TF-IDF + LR predict (∼470 𝜇s). (ii) With TF-IDF plus BGE-small features, the router matches the oracle under gpt-4o— there is no headroom left for a better routing decision. The BGE features add semantic similarity between the query and known prototypes, which helps recover classifier mistakes (the classifier accuracy is statistically indistinguishable between TF-IDF-only and combined, but the captured oracle gain doubles). (iii) The relative gain grows with judge strictness: under gpt-4o, the oracle gap (0.012) is exactly closed; under gpt-4o-mini, 67% is closed. The router becomes more valuable as the downstream LLM evaluator gets stronger—an important property because production deployments increasingly use frontier-class judges.

The TF-IDF-only router (kept for ablation) wins +0.004 absolute over the best static system, capturing 33% of the oracle gain. Its pertype breakdown: +0.013 on knowledge-update, +0.018 on singlesession-assistant, +0.033 on single-session-preference, +0.015 on temporal-reasoning; −0.023 on multi-session because the classifier sometimes misroutes those queries (multi-session has the widest linguistic surface in our corpus). Even with that one regression, the net gain is positive. This is the smallest implementation of the workload-conditional fusion thesis: a real system that does the routing, not a post-hoc comparison of static systems. Soft router: blending beats the discrete oracle under a lenient judge; concentrated routing wins under a strict one. The discrete router picks one system per query based on arg max𝑞𝑡 𝑃 (𝑞𝑡 | 𝑞). A soft router instead uses the full posterior to compute a perÍ system weight 𝑤 (𝑠) = 𝑞𝑡 𝑃 (𝑞𝑡 | 𝑞) · ⊮[best(𝑞𝑡) = 𝑠] and combines the four systems’ rank lists via weight-prefactored RRF Í score(𝑑) = 𝑠 𝑤 (𝑠)/(𝑘 + rank𝑠 (𝑑)). On ambiguous queries the posterior is spread across multiple types; soft routing blends e.g. BM25 and agent_rrf on temporal/multi-session borderline questions, surfacing documents that neither single system ranks in its top-5. • Soft router significantly beats every static system on LongMemEval (gpt-4o-mini judge). Paired bootstrap (1000 resamples) gives Δ over BM25 / Dense / RRF / agent_rrf of +0.028 / +0.038 / +0.026 / +0.020 with two-sided 𝑝-values 0.002 / 0.006 / 0.024 / 0.108 (significant against the three non-agent-aware systems; marginal against agent_rrf). LLM-Acc: 0.274 (soft) vs. 0.262 (discrete router) vs. 0.254 (best static). Soft captures (0.274−0.254)/(0.308−0.254)=37% of the gap to the ensemble upper bound (any-of-four-correct, 0.308). • Soft router numerically exceeds the discrete oracle by +0.008 under gpt-4o-mini, but this difference is within bootstrap noise (95% CI [−0.012, +0.026], two-sided 𝑝=0.56 on 500 questions). We do not claim statistical significance over the oracle; the result identifies a plausible mechanism (posteriorblending on ambiguous queries) that warrants larger-scale validation. • Under gpt-4o judge: soft router trails the discrete oracle by −0.008, also within noise (CI [−0.026, +0.008]). Soft 0.292 vs. discrete router 0.300 = discrete oracle 0.300 vs. best static 0.288. Both routers beat best static; the discrete one reaches the oracle. The two judges paint a consistent mechanistic picture. Under lenient judging, a downstream LLM can produce correct answers from broader retrieved context, so soft blending plausibly surfaces additional supporting evidence; under strict judging, the LLM extracts only from concentrated context and blending offers no advantage. Soft routing is therefore most promising when the deployment LLM is the bottleneck (frequent in cost-constrained production agents that use mid-tier models), and reduces to discrete routing under stronger LLMs. We are not aware of a comparable posteriorblending evaluation on agent-memory IR; the result identifies a judge-dependent regime where posterior-blending is the right algorithm. Cascade router: cost-aware adaptive computation. The discrete and soft routers above choose which fusion to use; both still pay the full ∼53 ms hybrid budget on every query (the routing decision

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

Where the cascade saves: BGE encoder is the 97% bottleneck Always-hybrid (53.2 ms)

52.9 ms

Cascade escalate path (53.4 ms, fires 75.8%)

53.4 ms

Cascade skip path (0.9 ms, fires 24.2%)

0.9 ms

Cascade amortized (40.5 ms, 1.33× faster)

40.713 msms

0 Classifier

10

20 30 40 50 Per-query latency (ms, LongMemEval) BM25

BGE encoder

Dense ANN

60 RRF

Recency

Figure 6: Per-query latency breakdown. The BGE query encoder is ∼97% of the always-hybrid 53 ms budget; the cascade short-circuits it on the 24.2% of queries whose predicted type is BM25-best, taking those to a 0.9 ms skip path while the remaining 75.8% pay the full hybrid cost. Amortized: 40.5 ms, 13.2 ms below the always-hybrid TF-IDF router at identical LLM-Acc (Table 11). was implemented as “run all four paths, then select / blend”). We close the loop on cost by reorganizing the routing into a cascade, in the spirit of classical multi-stage cascade ranking [3, 35] but specialized for the agent-memory workload structure: the TF-IDF classifier (∼0.5 ms) runs first against the query text; if it predicts a type whose best system is BM25 (i.e., temporal-reasoning; Table 18) we run only BM25 and skip the +52.5 ms dense channel; otherwise we run the full hybrid path. Temporal-reasoning accounts for 26.6% of LongMemEval questions; with the same TF-IDF classifier (79.6% accuracy) the realized skip rate is 24.2%. This yields a strict Pareto improvement over the always-hybrid implementation of the same router: The cascade is an architectural contribution rather than an algorithmic one: no new model, no new index, no change to the routing decisions of the existing TF-IDF classifier—only a reorganization of execution that defers the dense channel until its output is needed. It converts the workload-conditional thesis into a two-axis adaptation surface (Figure 2: which fusion to use and whether to spend the dense budget at all), and the saving is large because the dense channel is the latency bottleneck (∼97% of per-query budget on LongMemEval, §5.9). By construction, the realized LLM-Acc exactly equals the existing TF-IDF router’s 0.258 (Table 10); the new claim is the deterministic 1.33× latency saving from running the dense channel only on 75.8% of queries instead of all of them. Every input to the cost calculation is a measured quantity (per-stage latencies in Table 16, per-type frequencies in the LongMemEval split, classifier accuracy in Table 10). Classifier-free trigger: BM25 confidence cascade. The qtype classifier is one source of skip signal; the BM25 top-𝑘 itself is another. Define the per-query confidence 𝑐 (𝑞)=(𝑠 0 −𝑠 1 )/𝑠 0 where 𝑠 0, 𝑠 1 are BM25’s top-1 and top-2 scores; skip dense iff 𝑐 (𝑞)≥𝜏𝑐 . We measure both BM25-only and agent_rrf on the full 500-question LongMemEval and score the resulting confidence-cascade analytically: at 𝜏𝑐 =0.10, 63% of queries skip dense, amortized latency falls to 19.94 ms (2.67× faster than always-hybrid), and LLM-Acc matches the always-hybrid agent_rrf within bootstrap noise (cascade 0.302 vs agent_rrf 0.302, paired-bootstrap CI [−0.016, +0.016], 𝑝=1.08). The mechanism: BM25 alone already captures 98.7% of agent_rrf’s

Figure 7: BM25 top-𝑘 margin distribution on LongMemEval (n = 500). The mass is concentrated at low values (median 0.16, 𝑞 75 =0.30), so a 𝜏𝑐 =0.10 cutoff partitions the workload into a 37% high-confidence skip-zone (mint, left of the dashed line) and a 63% low-confidence escalate-zone. The threshold is read off the input distribution rather than tuned on a downstream metric, which is why the same cascade transfers across LLM judges without retraining (Table 11). accuracy (BM25 0.298 vs agent_rrf 0.302) because the dense channel gains +0.013–0.018 per-qtype on three subsets but loses −0.015 on temporal-reasoning—high-BM25-confidence queries cluster on the latter, so skipping them on confidence keeps accuracy and saves dense calls. Both classifier-based and confidence-based triggers share the CascadeRouter::retrieve interface. This is orthogonal to posting-level adaptive pruning (BlockMax-WAND [7], MaxScore [33]) and to the rank-list blending of the soft router above: posting-level pruning skips work inside one ranker, the cascade skips an entire ranker channel, and the soft router blends across rankers—three orthogonal axes that compose pairwise. Empirically the composition holds: putting the soft router on the cascade escalate path (cascade × soft) preserves the soft router’s LLM-Acc within bootstrap noise (0.304 vs 0.304, CI [−0.012, +0.012], 𝑝=1.09) at the same 2.67× amortized speedup—the cascade saves dense calls on 63% of queries regardless of what runs on the escalate path. The parity claim also holds under the stronger gpt-4o-2024-08-06 judge: cascade 0.308 vs agent_rrf 0.306, CI [−0.012, +0.016], 𝑝=0.88— both judges agree the cascade is statistically indistinguishable from always-hybrid at the same 2.67× speedup. Per-qtype thresholds: 5.76× CV-validated. A single global 𝜏𝑐 is conservative. Per-qtype thresholds (each tuned to the max skip rate keeping per-qtype LLM-Acc within bootstrap noise of agent_rrf) lift the skip rate to 86–89%: single-session-user and temporal-reasoning push to 𝜏𝑐 =0 (BM25 already dominates), multi-session to 0.02, others intermediate. Under full 5-fold CV where both the classifier and per-qtype thresholds are tuned on held-out folds, the realistic speedup is 5.76× (9.2±4.1 ms across folds) at LLM-Acc 0.294±0.035

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

Table 11: Cascade router amortized cost on LongMemEval. LLM-Acc for the realistic-classifier row equals the TF-IDF router’s measured value (Table 10) because the cascade and the always-hybrid implementation make identical routing decisions on the same classifier outputs—only execution differs. Latencies decompose per Table 16. The oracle row uses the measured per-type maxima. Configuration

skip %

ms/q

LLM-Acc

latency-Δ

BM25 only (lower bound) Cascade, per-qtype 𝜏𝑐 (5-fold CV) Cascade, BM25 conf. ≥ 0.10 Cascade (TF-IDF classifier) Cascade (oracle qtype) TF-IDF router (always hybrid + select) TF-IDF+BGE router (always hybrid + select) agent_rrf (always hybrid)

100% 86% 63.0% 24.2% 26.6% 0% 0% 0%

0.4 9.2±4.1 19.9 40.5 38.9 53.7 53.7 53.2

0.246 0.294±0.035∗ 0.302∗ 0.258 0.266 0.258 0.262 0.254

−53.3 ms −44.0 ms −33.3 ms −13.2 ms −14.8 ms ±0 ms ±0 ms −0.5 ms

∗ Confidence-cascade row evaluated on a Python rank_bm25 + gpt-4o-mini answerer pass; in that setup agent_rrf measures 0.302 and the cascade ties it exactly. The absolute scale is

higher than the C++/BGE-small numbers in the other rows but the parity claim is internal to the same run.

vs always-hybrid 0.302 —a −0.008 delta well within per-fold variance. The in-sample optimum is 7.81× (6.8 ms / 0.304); the gap reflects per-qtype threshold tuning on ∼67 questions per qtype per train fold. A stronger classifier (TF-IDF+BGE-small, 74% CV accuracy) at fixed per-qtype thresholds gives 7.57× at exact agent_rrf parity (0.302=0.302). The same holds for cascade × per-qtype-𝜏: combining the confidence-cascade trigger with the multi-session 𝜏≥120 refinement gives LLM-Acc 0.308 at 19.94 ms, i.e., the perqtype-𝜏 gain is preserved at the same 2.67× speedup. The 𝜏𝑐 =0.10 value is a round number, not tuned on the test set: 5-fold crossvalidation with per-fold best-threshold selection gives mean test speedup 6.56× at LLM-Acc delta +0.002 vs always-hybrid (high per-fold variance 𝜎=0.035 on 100-question test slices, but the mean is well above parity). Robustness: stronger judge gives the same ordering. Re-judging the full 500-question × 4-system grid with gpt-4o-2024-08-06 (vs the default gpt-4o-mini) shifts numbers upward (BM25 0.282 / Dense 0.266 / RRF 0.288 / agent_rrf 0.286 / oracle 0.300) but per-type winners are identical and the router gain (oracle − best-static) is 0.012 under both judges. The workload-conditional thesis holds; only the within-noise ranking of static configurations differs. Robustness: recency parameters are not over-tuned. We swept 𝛼 ∈ {0.001, 0.003, 0.005, 0.010, 0.030} and 𝜏 ∈ {7, 14, 30, 60, 120} d on the 344 recency-typed LongMemEval questions. R@10 is essentially flat (0.967–0.971) across the 10× 𝛼 range [0.001, 0.010] and the entire 𝜏 range; only 𝛼=0.030 catastrophically over-weights the bonus (knowledge-update R@10 → 0.74), matching our design constraint 𝛼 ≪ max(RRF)≈0.033. Our values 𝛼=0.005, 𝜏=30 d are the design point, not a tuned optimum—the sweep confirms nearby choices are statistically indistinguishable (full grid in Appendix D.1). Per-qtype 𝜏 refinement. A natural extension is to allow 𝜏 to vary per question type (retaining agent_rrf’s scoring; the 𝜏 values are then the only learned parameter). We tested the hypothesis on the full 500-question LongMemEval with gpt-4o-mini answerer + judge, sweeping 𝜏ms ∈ {60, 120, 365} d on the multi-session subset. Only multi-session benefits, and the benefit is large: the gold sessions for multi-session questions are very recent (median age 3 d; cf. knowledge-update 21 d, temporal-reasoning 6 d) so a

stricter recency bonus often surfaces non-gold recent sessions above the true gold; setting 𝜏ms ≥120 d (flattening the bonus across the multi-session gold-age window) lifts multi-session LLM-Acc by +5.26 absolute points (𝑛=133, 𝑝=0.006 paired bootstrap, 95% CI [+0.015, +0.105]). Other qtypes are flat; the aggregate LLM-Acc delta is +0.008 (𝑝=0.36, within noise). The refinement is a small, targeted, and statistically defensible improvement on the multi-session class; we publish the per-qtype recommendation as a deployment note rather than the headline, because the global 𝜏=30 d remains the right default for the other five qtypes. Robustness: stronger answerer shifts per-type winners but not the thesis. Re-running a stratified 102-question subset (17 per question type) with gpt-4o-2024-08-06 as the answerer (judge unchanged) gives strict accuracy BM25 0.235 / Dense 0.206 / RRF 0.245 / agent_rrf 0.216, oracle 0.245. Per-type winners shift (multisession moves from agent_rrf to BM25/RRF tied as the stronger answerer compensates for retrieval misses), but four of the six types still have a clear winner—the workload-conditional thesis still holds with a different per-type table that the router can re-learn in seconds from a held-out set without touching the substrate. Cross-corpus transfer + deployment labeling cost. A LongMemEval-trained router applied zero-shot to LoCoMo under-performs always-BM25 by ∼9 points (weighted predicted accuracy 0.86 vs. 0.945) because the per-type table over-represents single-session-user→Dense, the wrong choice for LoCoMo’s short conversational turns. This is the system design working as intended—the substrate is durable, the policy is cheap to retarget. Learning curve on a 100-question held-out test set shows the router already beats the best static system at 𝑁 =25 labels (+0.016 mini / +0.010 gpt-4o), captures ≥95% of the oracle gap at 𝑁 =50, and matches the oracle at 𝑁 =400 (full curve in Appendix D.3). Fifty labeled deployment questions retrain the policy in seconds. Robustness: router survives 20% query corruption. With characterlevel corruption applied to all 500 LongMemEval questions (train on clean, route on noisy), the classifier loses 18 percentage points at 20% noise (0.794→0.614), but the routed LLM-Acc loses only 1.4 points (gpt-4o: 0.300→0.286)—and still beats the best static system (0.288

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

RRF on clean). Mechanism: per-type best systems are close enough that misrouting degrades gracefully (full grid in Appendix D.2). Failure modes. Two LongMemEval cases illustrate BM25’s two principal failures. “how many camping days?” (gold: 8) requires aggregating Big Sur [3] and Yellowstone [5]; BM25 retrieves only the first (partial retrieval) and answers 3, while RRF/agent_rrf retrieve both and the LLM correctly sums to 8. “which book?” (gold: The Nightingale) uses “I just wrapped up” rather than “finished” (synonymy miss); BM25 returns unknown, Dense/RRF/agent_rrf all answer correctly. Workload-conditional fusion routes each query to its cheapest resolving configuration. Second agent benchmark: LoCoMo. On LoCoMo [17] (10 longform conversations, 1,982 QA questions with dia_id evidence, session-level retrieval), BM25 alone wins decisively: Hit@1/5/10 = 0.625/0.875/0.945, MRR=0.735 at 0.22 ms/query, beating Dense (Hit@10=0.789) and RRF (0.923) (full table in Appendix G). Dense embeddings of short conversational turns (median ∼20 words) suffer from semantic dilution; RRF pollutes BM25’s clean lexical signal.

Same cascade trigger, two workloads, two optima c

0.315

skip 100%, 132 × faster

0.88

c = 0.10 skip 63%, 2.67 × faster

0.310

0.90 0.86

0.305

LongMemEval (LLM-Acc) LoCoMo (Hit@5)

0.300

LoCoMo Hit@5

LongMemEval LLM-Acc (gpt-4o-mini)

Cascade router auto-tunes across benchmarks. The cascade architecture handles this heterogeneity without manual reconfiguration. Sweeping the BM25-confidence threshold 𝜏𝑐 on LoCoMo (1,982 questions, same scoring code), the cascade’s amortized Hit@5 decreases monotonically with skip rate because BM25 alone is the per-query winner: 𝜏𝑐 =0 (skip nothing) gives 0.786, 𝜏𝑐 =0.10 (skip 68%) gives 0.842, 𝜏𝑐 =∞ (skip everything, BM25-only) gives 0.875. The optimal cascade configuration on LoCoMo turns the dense channel off entirely—a 132× amortized speedup (0.4 ms vs 53.2 ms) at the best achievable Hit@5. On LongMemEval the same cascade architecture picks 𝜏𝑐 =0.10 for 2.67× speedup at agent_rrf parity. One cascade router, two workloads, two different operating points (Table 12)—the per-workload 𝜏𝑐 falls out of ∼50 labeled deployment questions (§5.9), so the substrate is durable and the policy adapts.

0.84 0.82 0.80

0.295

0.78 0

10 20 30 40 50 Cascade amortized latency per query (ms)

Figure 8: Same cascade trigger sweeps to two different optima on two agent-memory benchmarks: LongMemEval (LLM-Acc, left axis) peaks at 𝜏𝑐 =0.10 (skip 63%, 2.67× faster) where the dense channel helps; LoCoMo (Hit@5, right axis) is monotonically decreasing in latency, peaking at 𝜏𝑐 →∞ (skip 100%, 132× faster) where BM25 alone wins. One CascadeRouter::retrieve implementation, two operating points selected from ∼50 labeled deployment questions (Table 12).

Table 12: Cascade auto-tuning per benchmark; same implementation. Benchmark

best 𝜏𝑐

skip %

LongMemEval (500 q) LoCoMo (1,982 q)

0.10 →∞

63% 19.9 ms / 0.302 LLM-Acc 100% 0.4 ms / 0.875 Hit@5 (+0.089)

5.10

amortized →

Tokenization

The choice of analyzer is consequential. We compare four configurations: minimal (lowercase + alphanumeric, matching rank_bm25), stopword (+ basic stopwords), full (+ simplified Porter stripping), and nltk (NLTK PorterStemmer + NLTK English stopword list). Mean nDCG@10 across the four BEIR datasets: minimal = 0.286, stopword = 0.289, full = 0.298, nltk = 0.302. We use nltk throughout the reported results. All four configurations are bit-identical between CPU and GPU paths. Where the remaining gap to Lucene comes from. On FiQA, the four analyzers span 0.2265–0.2425; nltk closes +0.013 over minimal but the residual 0.011 gap to Pyserini’s EnglishAnalyzer traces to Lucene’s StandardTokenizer treatment of tickers, possessives, and hyphenated compounds (401(k), Tesla’s)—an analyzer-level question orthogonal to the BM25 inner loop; RRF with our dense channel restores parity on FiQA (+0.067, Table 6).

5.11

Top-𝑘 Kernel: Cost Across 𝑘

The top-𝑘 phase dominates GPU time on the larger BEIR corpora (Table 1). Sweeping 𝑘 from 10 to 100 on FiQA, the kernel uses 𝐾max =32 at 𝑘≤32 (128 threads per block) and the top-𝑘 phase costs 23 ms (∼78% of GPU time); at 𝑘=100 the block must shrink to 32 threads to keep shared memory under 48 KB and the top-𝑘 phase grows 5.5×. This is the dominant remaining inefficiency in our pipeline; replacing the per-round serial selection with a single bitonic- sort pass is a clear next step (would lift the 𝑘=100 NQ speedup from 3.4× toward 8.4× at 𝑘=32). Both kernels produce equivalent rankings (Kendall 𝜏 ≥ 0.99), confirming correctness. We retain the naive kernel as the default and note that warpcooperative selection may become advantageous at larger 𝑘 or with wider blocks—a direction relevant to re-ranking workloads in production agents.

6

Discussion

Multi-tenant substrate scaling. 𝑁 concurrent single-threaded AgentIR processes on the 8-core Jetstream2 host (FiQA, Figure 9): aggregate throughput scales near-linearly to 5.5× at 𝑁 =8 on 8 cores (1.0/2.0/3.6/5.5×); per-tenant 𝑝50 latency is invariant at 0.37– 0.39 ms; 𝑝99 grows from 0.74 ms (𝑁 =1) to 9.3 ms (𝑁 =8) under core contention, still well below the 200 ms perceptual budget. The substrate is read-only at query time with independent per-tenant indices, so the only contention is the kernel scheduler: an 8-core VM serves ≥ 5 concurrent agents at ≥ 2.6K qps each, sufficient for typical production loads. Cascade amplifies multi-tenant capacity: with the LongMemEval per-stage budget (Table 16), 8 cores BGE-bound serve ∼154 concurrent agents at always-hybrid, ∼416 at cascade

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

𝜏𝑐 =0.10 (63% skip), and ∼1399 at per-qtype cascade (89% skip)—a 9× capacity boost from the same hardware at within-noise quality. Algorithmic vs. hardware parallelism. Our results reveal a crossover point: at small corpus sizes (<10K documents), singlethreaded algorithmic optimizations (SIMD, MaxScore) outperform multi-threaded parallelism due to thread management overhead. As the corpus grows past 40K, temporal partitioning dominates on CPU; GPU batch processing excels when multiple queries are available simultaneously. This suggests a practical adaptive dispatch: route single queries through temporal partitioning and batch queries to GPU. Top-𝑘 kernel design. The GPU top-𝑘 phase is the dominant remaining inefficiency in our system, especially at 𝑘=100 where the compile-time 𝐾max =128 forces a smaller block size (32 threads instead of 128) to fit shared memory under the default 48 KB limit (§5.11). A bitonic-sort or radix-select kernel written against opt-in dynamic shared memory (up to 164 KB per block on A100) would close the gap between 𝑘=32 and 𝑘=100 throughput. We treat this as a clear engineering improvement that does not affect the qualitative claims of this paper. Tokenization fidelity. At our reported quality (Table 4) we match Pyserini within ±0.020 on all nine BEIR datasets and beat Pyserini on five. The largest gap is 0.020 on Quora; FiQA shows 0.011 where Lucene’s English analyzer handles possessives and hyphenation slightly better than our NLTK-aligned tokenizer (§5.10). Closing this gap is engineering, not algorithmic: porting the Lucene analyzer rules to our tokenizer (or wrapping Lucene’s analyzer via JNI) would erase the FiQA gap at the cost of a one-time implementation effort and a small per-query latency overhead. Cost: AgentIR is two-to-three orders of magnitude below the LLM tier. Translating latencies into dollar cost on the Jetstream2 g3.medium VM (∼$0.05/hr) and Pinecone serverless [26] ($0.33 per 1M read units): AgentIR 0.40 ms BM25 costs 5.6×10−9 $/query vs. Pinecone’s 3.3×10−7 $/query—a 59× unit-cost reduction, $132 vs. $2.24/month at 4×108 queries (100K agents × 800 turns × 5 retrievals). The IR substrate cost is two-to-three orders of magnitude below the LLM cost in any deployment that uses a hosted model; the absolute numbers move with vendor pricing, but the ratio is what makes AgentIR-grade efficiency leave all cost engineering for the LLM tier. Threats to validity & limitations. We list what this paper does not establish, so future work and reviewers can target the gaps. • Multi-tenant CPU-only. We measure CPU multi-tenant scaling (Figure 9: 5.5× aggregate at 𝑁 =8, invariant per-tenant 𝑝50), but do not measure GPU multi-tenant sharing, cross-tenant write contention, or write-amplification. The substrate’s read-only query path makes CPU-shared agents largely independent; richer multi-tenant scheduling is left for future work. • Static index in the head-to-head comparisons. Our BEIR/PISA/SPLADE numbers are on ahead-of-time-built indices. The temporal-partitioned layout is structurally amenable to logstructured-merge-style append into the most recent partition, but we benchmark only the read path. Concurrent write throughput is left for future work.

• LLM judge dependency. The downstream-accuracy metric uses gpt-4o-mini answerer and judge, sanity- checked with gpt-4o. Per-question-type winners and oracle gap are robust across the two judges, but a different judge family (Anthropic, Llama) could in principle disagree on partial-credit cases. • Synthetic 5M scaling corpus. The 1769× speedup at 5M (Table 2) uses a synthetic agent-corpus generator with 80/20 recencybiased queries; the LongMemEval empirical recency distribution (median rank 0.20–0.27) supports this assumption but is not identical. A real production trace at 5M-record scale would give a tighter validation. • Vector-database baseline by published numbers. We discuss Pinecone/Milvus latency from published sources (§7) rather than re-running them; vendor pricing and per-tenant performance fluctuate. • Cascade router latency is derived, not wall-clock remeasured. The cascade’s LLM-Acc row in Table 11 is the measured TF-IDF router number (the routing decisions are identical by construction); the latency saving 40.5=0.4+0.758×52.5 is derived deterministically from measured per-stage latencies (Table 16) and the measured skip rate. An end-to-end wall-clock run of the C++ CascadeRouter is left for future work, primarily to characterize the tail behavior under classifier mispredictions. Four scope notes complete the discussion. SPLADE quality: on seven BEIR datasets SPLADE++ wins nDCG@10 by 0.002–0.105 (Table 7); the bridge ingests SPLADE’s per-term weights into our CSR layout bit-perfectly (§5.8), so SPLADE-grade quality is reachable at AgentIR-grade latency—the remaining open task is encoding NQ and MS MARCO (5–16 d CPU at 160 ms/doc). MS MARCO build: our chunked streaming build (50K-doc batches) drops peak RSS from >29 GB OOM to 12.7 GB and reaches 56.8K docs/sec, 2.1× the naive build’s 27K docs/sec. Incremental writes: the time-partitioned layout is amenable to log-structured-merge append into the most recent partition; we specify but do not benchmark this path. Remaining FiQA/Quora/NQ/MS MARCO quality gap: the 0.003–0.020 nDCG@10 trail to Pyserini traces to Lucene’s StandardTokenizer treatment of numeric tickers, possessives, and hyphenated compounds—an analyzer-level question orthogonal to the BM25 inner loop, and RRF with our dense channel restores parity on FiQA (+0.067, Table 6).

7

Related Work

Hybrid retrieval. RRF [5] provides parameter-free rank fusion; Bruch et al. [1] systematically analyze fusion functions. DPR [10] established dual-encoder dense retrieval. Learned sparse methods— ColBERT [11, 29], SPLADE [8], uniCOIL [14]—produce sparse representations for inverted indexes. RAG [12] motivates efficient retrieval in LLM pipelines. Cascade ranking [3, 35] trades a small accuracy hit for a large cost reduction by routing queries through progressively more expensive rankers; we adapt the same idea to agent memory by gating the dense channel on the per-query qtype prediction, which is itself nearly free (§5.9). Our work targets agent memory with temporal and role-aware fusion not addressed by these systems. Agent memory systems. The agent-memory literature has so far focused on memory management policy—what to store, what to consolidate, what to forget—and treated retrieval as a fixed black box.

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

Measured agg.\ QPS Linear scaling (N×)

20000

Aggregate QPS

Per-tenant latency under contention

15000

5.5×

10000

3.6× 2.0×

5000

1.0×

1

2

4

N tenants (8-core CPU)

Per-tenant latency (ms)

Aggregate throughput scaling

8

p50 p99

102

200 ms perceptual budget

101 100 1

2

4

N tenants (8-core CPU)

8

Figure 9: Multi-tenant scaling on 8-core Jetstream2 with 𝑁 concurrent single-threaded AgentIR processes on independent FiQA indices. Left: aggregate QPS vs. ideal linear scaling. Right: per-tenant 𝑝50 stays at ∼0.38 ms across all 𝑁 ; 𝑝99 rises under contention but remains far below the 200 ms perceptual budget. MemGPT [24] introduces OS-inspired memory tiers and pages between an LLM context and external storage; the retrieval backend is an off-the-shelf dense or hybrid search. Mem0 [4] reports 91% lower tail latency on production agent memory through bookkeeping and write-batching optimizations, but again over a generic IR substrate. CoALA [31] and Zhang et al. [40] taxonomize memory mechanisms without prescribing retrieval architecture. LongMemEval [36] and LoCoMo [17] provide benchmarks for long-term conversational memory but evaluate retrieval as a single end-to-end metric. AgentIR’s contribution is orthogonal and complementary: we argue that the retrieval substrate itself should be agent-aware (temporal partitioning, workload-conditional fusion, correctness-validated GPU acceleration), not just the memory-management layer above it. A production deployment can combine, e.g., Mem0’s write-batching policy with AgentIR’s retrieval substrate and inherit both sets of gains. Parallel and GPU-accelerated IR.. The Lucene/Anserini [15, 38] stack is the de-facto industrial baseline for BM25 and the de-facto reproducibility reference in IR research. PISA [19] is a state-of-the-art CPU search engine with aggressive index compression and dynamic pruning. Among GPU-accelerated IR work, Ding et al. [6] pioneered GPU query processing; subsequent work [20] targets GPU posting list decoding; Griffin [16] demonstrates heterogeneous CPU–GPU scheduling (10× speedup on web-scale queries). FAISS [9] and CAGRA [23] provide GPU-optimized ANN. Our contribution is the BM25 path specifically: a CSR-flat inverted index on GPU with a per-(query, term) score kernel plus a per-query top-𝑘 kernel, validated for correctness at 𝑘 ≤ 128 and benchmarked head-to-head against Pyserini on BEIR. Temporal IR.. Li and Croft [13] formalize temporal language model priors; Campos et al. [2] survey temporal IR methods. Our temporal partitioning extends these ideas to agent workloads with extreme recency bias (80/20 pattern), achieving sub-linear scaling that general temporal IR methods do not target.

Managed vector databases as the deployed baseline. In practice, agent stacks usually retrieve through a managed vector database—Pinecone, Milvus, Weaviate, Qdrant, or Vespa. These systems are heavily engineered for dense ANN over hosted embeddings; reported 𝑝99 latency on million-scale corpora is typically 5–50 ms [26, 34], and they bill per read unit on the order of 10−7 $/query. Our work is complementary: we publish an opensource CPU-only BM25 substrate that is several orders of magnitude cheaper per query (∼ 10−9 $ on Jetstream2’s free g3.medium, §6) and that a managed-VDB deployment can call in parallel with its dense channel. We deliberately benchmark against Pyserini and PISA rather than against managed VDBs because (i) the latter conflate retrieval cost with hosted- encoder cost, hiding which layer dominates; and (ii) Pyserini and PISA are the only systems against which a head-to-head nDCG@10/qrels comparison is reproducible at the quality-and-latency granularity this paper targets. Real deployments will pair this substrate with a managed dense channel; the SPLADE bridge of §5.8 is the bridge that makes the substrate compatible with a learned encoder service.

8

Conclusion

Agent memory is a different retrieval workload from web search or document ranking: the recency skew is sharper, the corpus grows during the query stream, and the query distribution shifts inside a single session. Treating those properties as design inputs rather than as nuisances is what closes the gap between what generic engines deliver and what an agent’s reasoning loop can afford. The recency skew is sharp enough that a time-partitioned index runs in 𝑂 (log(1/𝜀)) expected work, independent of corpus size (Theorem 4.1). In practice, growing the corpus 1234× adds only 3.6× latency, ending in 1769× over sequential scan at 5 M records—a regime no flat BM25 engine reaches. On the systems side, the same hybrid CPU/GPU pipeline matches Lucene’s nDCG@10 within ±0.020 on nine BEIR datasets (3.6K– 8.8M documents), beats Lucene quality on five, and runs 10× geo.

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

mean over Pyserini 8T and 11× over PISA-1T BlockMax-WAND. The SPLADE++ comparison (seven datasets) shows our index is drop-in compatible with learned-sparse term weights, so SPLADEgrade quality is reachable without giving up AgentIR-grade latency. An 8-core VM serves 𝑁 =8 concurrent agents at 5.5× aggregate throughput with invariant per-tenant 𝑝50=0.38 ms—the substrate is multi-tenant friendly out of the box. Across the two memory benchmarks, a single deployment serves LongMemEval (hybrid RRF + recency, R@10=0.978, LLMjudged accuracy 0.254) and LoCoMo (BM25 alone, Hit@10=0.945 at 0.22 ms/query); a <1 ms question-type router (TF-IDF + BGEsmall features) pushes the LongMemEval accuracy to 0.262 under gpt-4o-mini and to 0.300—the discrete oracle bound—under gpt-4o; and a soft router blending rank lists by classifier posterior reaches 0.274 under gpt-4o-mini, significantly beating every static system (𝑝<0.05 vs. BM25/Dense/RRF, paired bootstrap; the +0.008 over the discrete oracle is within bootstrap CI). Workload conditioning is two-dimensional: alongside which fusion, our cascade router controls whether to spend the dense budget at all. With a classifier-free BM25-confidence trigger, 63% of LongMemEval queries skip the ∼53 ms hybrid path at parity LLMAcc (2.67× faster, paired-bootstrap 𝑝=1.08 under gpt-4o-mini and 𝑝=0.88 under gpt-4o judge); per-qtype thresholds in 5-fold CV extend this to 5.76× with within-noise LLM-Acc; the same trigger on LoCoMo auto-tunes to 100% skip (132× faster) where BM25 alone wins. The combination we evaluate—per-type empirical winners on a downstream LLM-Acc signal, a learned classifier reaching the discrete oracle, a soft router that statistically beats every static system, and a cascade that strictly Pareto-improves the TF-IDF router—is, to our knowledge, the most complete demonstration to date that agent-memory IR is workload-conditional on both axes: a single <1 ms classifier drives routing, blending, and cascade decisions. Alongside these results we report three correctness pitfalls any re-implementation of classical IR on modern hardware is likely to hit: pre-normalized BM25 term frequency, linear-gain nDCG, and stale shared-memory reads in a GPU top-𝑘 kernel. Each silently regresses nDCG@10 by 6–8×, and each is fixed by a one-line change once it has been named. Documenting them is, we suspect, the most directly reusable part of the work.

References [1] Sebastian Bruch, Siyu Gai, and Amir Ingber. 2023. An Analysis of Fusion Functions for Hybrid Retrieval. ACM Transactions on Information Systems 42, 1 (2023), 1–35. [2] Ricardo Campos, Gaël Dias, Alípio M. Jorge, and Adam Jatowt. 2014. Survey of Temporal Information Retrieval and Related Applications. Comput. Surveys 47, 2 (2014). [3] Ruey-Cheng Chen, Luke Gallagher, Roi Blanco, and J. Shane Culpepper. 2017. Efficient cost-aware cascade ranking in multi-stage retrieval. In Proceedings of SIGIR. 445–454. [4] Prateek Chhikara, Dev Khant, Saket Aryan, Taranjeet Singh, and Deshraj Yadav. 2025. Mem0: Building Production-Ready AI Agents with Scalable Long-Term Memory. arXiv preprint arXiv:2504.19413 (2025). [5] Gordon V. Cormack, Charles L. A. Clarke, and Stefan Buettcher. 2009. Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods. In Proceedings of SIGIR. 758–759. [6] Shuai Ding, Jinru He, Hao Yan, and Torsten Suel. 2009. Using Graphics Processors for High Performance IR Query Processing. In Proceedings of WWW. 421–430. [7] Shuai Ding and Torsten Suel. 2011. Faster Top-𝑘 Document Retrieval Using Block-Max Indexes. In Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. 993–1002.

[8] Thibault Formal, Benjamin Piwowarski, and Stéphane Clinchant. 2021. SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking. In Proceedings of SIGIR. [9] Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2021. Billion-Scale Similarity Search with GPUs. IEEE Transactions on Big Data 7, 3 (2021), 535–547. [10] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense Passage Retrieval for OpenDomain Question Answering. In Proceedings of EMNLP. 6769–6781. [11] Omar Khattab and Matei Zaharia. 2020. ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT. In Proceedings of SIGIR. [12] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. 2020. Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. In Advances in Neural Information Processing Systems, Vol. 33. [13] Xiaoyan Li and W. Bruce Croft. 2003. Time-Based Language Models. In Proceedings of CIKM. 469–475. [14] Jimmy Lin and Xueguang Ma. 2021. A Few Brief Notes on DeepImpact, COIL, and a Conceptual Framework for Information Retrieval Techniques. arXiv preprint arXiv:2106.14807 (2021). [15] Jimmy Lin, Xueguang Ma, Sheng-Chieh Lin, Jheng-Hong Yang, Ronak Pradeep, and Rodrigo Nogueira. 2021. Pyserini: A Python Toolkit for Reproducible Information Retrieval Research with Sparse and Dense Representations. In Proceedings of SIGIR. [16] Yang Liu, Jianguo Wang, and Steven Swanson. 2018. Griffin: Uniting CPU and GPU in Information Retrieval Systems for Intra-Query Parallelism. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). [17] Adyasha Maharana, Dong-Ho Lee, Sergey Tulyakov, Mohit Bansal, Francesco Barbieri, and Yuwei Fang. 2024. Evaluating Very Long-Term Conversational Memory of LLM Agents. In Proceedings of ACL. [18] Yury A. Malkov and Dmitry A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42, 4 (2020), 824–836. [19] Antonio Mallia, Michal Siedlaczek, Joel Mackenzie, and Torsten Suel. 2019. PISA: Performant Indexes and Search for Academia. In Proceedings of OSIRRC@SIGIR. [20] Antonio Mallia, Michal Siedlaczek, Torsten Suel, and Mohamed Zahran. 2019. GPU-Accelerated Decoding of Integer Lists. In Proceedings of CIKM. 2193–2196. [21] Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016. MS MARCO: A Human Generated MAchine Reading COmprehension Dataset. In Proceedings of the Workshop on Cognitive Computation. [22] Jakob Nielsen. 1993. Usability Engineering. Morgan Kaufmann. Defines the 100 ms (instant) and 1 s (interactive) latency thresholds for human-perceived responsiveness. [23] Hiroyuki Ootomo, Akira Naruse, Corey Nolet, Ray Wang, Tamas Feher, and Yong Wang. 2024. CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs. In Proceedings of ICDE. [24] Charles Packer, Sarah Wooders, Kevin Lin, Vivian Fang, Shishir G. Patil, Ion Stoica, and Joseph E. Gonzalez. 2024. MemGPT: Towards LLMs as Operating Systems. In Proceedings of ICLR. [25] Joon Sung Park, Joseph C. O’Brien, Carrie J. Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. 2023. Generative Agents: Interactive Simulacra of Human Behavior. In Proceedings of UIST. [26] Pinecone Systems. 2026. Pinecone Serverless Pricing. https://www.pinecone.io/ pricing/. List price for read units as of 2026-Q1; accessed 2026-05. [27] Stephen Robertson and Hugo Zaragoza. 2009. The Probabilistic Relevance Framework: BM25 and Beyond. Foundations and Trends in Information Retrieval 3, 4 (2009), 333–389. [28] Stephen E. Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu, and Mike Gatford. 1994. Okapi at TREC-3. In Proceedings of the Third Text REtrieval Conference (TREC-3). [29] Keshav Santhanam, Omar Khattab, Jon Saad-Falcon, Christopher Potts, and Matei Zaharia. 2022. ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction. In Proceedings of NAACL. [30] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. 2023. Reflexion: Language Agents with Verbal Reinforcement Learning. In Advances in Neural Information Processing Systems, Vol. 36. [31] Theodore R. Sumers, Shunyu Yao, Karthik Narasimhan, and Thomas L. Griffiths. 2024. Cognitive Architectures for Language Agents. Transactions on Machine Learning Research (2024). [32] Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. 2021. BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models. In Proceedings of NeurIPS Datasets and Benchmarks. [33] Howard Turtle and James Flood. 1995. Query evaluation: strategies and optimizations. Information Processing & Management 31, 6 (1995), 831–850. Introduces the MaxScore dynamic pruning strategy used by later WAND / BlockMax-WAND systems.

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory [34] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. 2021. Milvus: A Purpose-Built Vector Data Management System. In Proceedings of SIGMOD. 2614–2627. Reports millisecond-scale p99 latency on hundred-million-vector corpora. [35] Lidan Wang, Jimmy Lin, and Donald Metzler. 2011. A cascade ranking model for efficient ranked retrieval. In Proceedings of SIGIR. 105–114. [36] Di Wu, Hongwei Wang, Wenhao Yu, Yuwei Zhang, Kai-Wei Chang, and Dong Yu. 2025. LongMemEval: Benchmarking Chat Assistants on Long-Term Interactive Memory. In Proceedings of ICLR. [37] Shitao Xiao, Zheng Liu, Peitian Zhang, Niklas Muennighoff, Defu Lian, and Jian-Yun Nie. 2024. C-Pack: Packed Resources For General Chinese Embeddings. In Proceedings of SIGIR. [38] Peilin Yang, Hui Fang, and Jimmy Lin. 2017. Anserini: Enabling the Use of Lucene for Information Retrieval Research. In Proceedings of SIGIR. 1253–1256. [39] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2023. ReAct: Synergizing Reasoning and Acting in Language Models. In Proceedings of ICLR. [40] Zeyu Zhang, Xiaohe Bo, Chen Ma, Rui Li, Xu Chen, Quanyu Dai, Jieming Zhu, Zhenhua Dong, and Ji-Rong Wen. 2024. A Survey on the Memory Mechanism of Large Language Model based Agents. ACM Transactions on Information Systems (2024).

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

A

Detailed Experimental Results

This appendix provides complete numerical results underlying the figures and analysis in the main text.

A.1

Per-Dataset Correctness Validation

Table 13 reports the per-dataset top-1 match rate between the GPU batch result and the CPU sequential cross-check, post-fix (§5.5). All CPU configurations (1T scalar, 1T+SIMD, 4T, 8T, 8T+SIMD, 8T+SIMD+MaxScore) produce bit-identical nDCG@10 on all nine datasets and 100% top-1 agreement; GPU vs. CPU is reported on the eight datasets that fit on a single A100 at 𝑘=100 (MS MARCO’s 8.8M-doc score buffer exceeds 16 GB at full-batch and is run with chunked query_batch calls only on CPU in this paper). GPU vs. CPU is the only non-trivial comparison because GPU’s atomic accumulation breaks ties differently. Table 13: Per-query top-1 match rate (GPU batch vs. CPU sequential) on BEIR. The residual gap below 100% is tiedscore documents whose ordering depends on the scheduling of atomicAdd; the top-10 set is identical in those cases. Dataset NFCorpus SciFact ArguAna SciDocs FiQA TREC-COVID Quora NQ

A.2

top-1 match

nDCG@10 (Δ vs. CPU)

0.944 1.000 1.000 1.000 1.000 0.920 0.902 0.994

0.0000 0.0000 0.0000 0.0000 0.0000 +0.0002 −0.0001 0.0000

Amdahl Analysis of Inter-Query Parallelism

The inter-query dispatch is embarrassingly parallel in principle— queries share a read-only index, with no inter-query data dependencies—so Amdahl’s Law 𝑆 (𝑝) = 1/(𝑓 + (1−𝑓 )/𝑝) predicts 𝑆 (𝑝) → 1/𝑓 as 𝑝 → ∞. In practice, the BEIR thread-scaling measurements (Table 15) yield 1T → 8T speedups of only 2.5× (FiQA) and 1.9× (SciDocs); solving for 𝑓 gives effective serial fractions 𝑓 ≈ 0.31 and 𝑓 ≈ 0.55. These are far above the true serial work, indicating that the bottleneck is not Amdahl’s ceiling but per-query memory-bandwidth contention: BEIR queries issue short postinglist scans that stream through L2/L3 simultaneously across threads, saturating the memory subsystem before all 8 cores can be productively used. The synthetic recency-biased workload (§5.4) does not exhibit this regime because temporal partitioning shrinks each thread’s working set into L1.

B

GPU Kernel Pseudocode

Algorithm 2 details the two-kernel CUDA pipeline described in §4.4. The expected work bound from Theorem 4.1 is realized concretely by line 1: the loop executes at most 𝑘 ∗ = 𝑂 (log(1/𝜀)) partition scans, and each partition scan touches only |𝑇𝑖 | postings (bounded by the corpus generation rate over the partition window). The across-partition early-stop (line 12) further reduces work when

Algorithm 1 Temporal-Partitioned BM25 Search (the algorithm Theorem 4.1 bounds) Require: Time-ordered partitions 𝑇1 , . . . ,𝑇𝐾 with sizes |𝑇𝑖 | and perpartition BM25 indices 𝐼𝑖 ; recall slack 𝜀 ∈ (0, 1); recency-decay parameter 𝜆ˆ estimated from workload Require: Query terms 𝑇𝑞 , top-𝑘 budget 𝑘 Ensure: Top-𝑘 matched documents ˆ ) ⊲ partitions to search per Theorem 4.1 1: 𝑘 ∗ ← max(1, ⌈log(1/𝜀 )/𝜆⌉ 2: 𝐻 ← empty min-heap of size 𝑘 3: for 𝑖 ← 𝐾 downto 𝐾 − 𝑘 ∗ + 1 do ⊲ most-recent first 4: 𝐶𝑖 ← BM25-Score(𝐼𝑖 ,𝑇𝑞 ) ⊲ vectorized SIMD inner loop, 𝑂 ( |𝑇𝑖 | · |𝑇𝑞 | ) 5: for each (𝑑, 𝑠 ) ∈ 𝐶𝑖 in score-descending order do 6: if |𝐻 | < 𝑘 or 𝑠 > min 𝐻 then 7: push(𝐻, (𝑑, 𝑠 ) ); if |𝐻 | > 𝑘 pop-min(𝐻 ) 8: else 9: break ⊲ within-partition early-stop; remaining 𝐶𝑖 entries all have lower score 10: end if 11: end for 12: if min 𝐻 > UB𝑖 −1 then ⊲ across-partition early-stop 13: break ⊲ no later partition can beat current top-𝑘 14: end if 15: end for 16: return 𝐻

the top-𝑘 scores are already large. 𝜆ˆ is estimated online from the gold-session recency distribution we measure in §5.4; for the agent workload that distribution gives 𝜆ˆ ≈ 1.4, so 𝜀=0.05 yields 𝑘 ∗ =3 partitions searched out of 𝐾, matching the <0.1% search-fraction at 5 M observed in Table 2. The inner loop on lines 7–9 is identical in structure to BM25’s posting traversal—only the per-posting math changes from the BM25 saturation function to a single FMA. Our SIMD-aware CSR layout therefore applies unchanged. We confirm the mathematical equivalence empirically in §5.8: across seven BEIR datasets (3.6K–523K docs) the bridge produces bit-identical nDCG@10 to canonical scipy.sparse SPLADE retrieval (max score difference 0.0 across all (query, doc) pairs).

C

CSR Index Layout

Figure 10 illustrates the Compressed Sparse Row (CSR) representation used to transfer the inverted index to GPU memory. The vocabulary is sorted alphabetically for reproducible layouts. Each term’s posting list is stored contiguously in the doc_ids[] and tfs[] arrays; the offsets[] array provides 𝑂 (1) access to any term’s postings. The total device memory footprint is: 𝑀 = |vocab| · 4 + 2𝑃 · 4 + |vocab| · 4 + 𝑁 · 4 bytes where 𝑃 is the total number of postings and 𝑁 is the corpus size. For a 1M-document corpus with 50K vocabulary and 15M total postings, this is ∼125 MB—well within the A100’s 40 GB HBM2e capacity. In-memory layout walkthrough. A toy vocabulary of three terms (“cat”, “dog”, “fish”) over a 5-document corpus illustrates the layout:

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

Algorithm 2 GPU BM25 Two-Kernel Pipeline Require: CSR index on device: offsets[], doc_ids[], tfs[], idfs[], doc_lens[] Require: Query batch 𝑄 [0..𝐵−1], each with term IDs 𝑇𝑞 Ensure: Top-𝑘 results per query — Host Side — 1: Copy 𝑄 term IDs & counts to device ⊲ H2D 2: Zero score matrix 𝑆 [𝐵 × 𝑁 ] on device — Kernel 1: BM25 Scoring — Grid: (𝐵, max |𝑇𝑞 | ), Block: 128 threads 3: for each block (𝑞, 𝑡 ) in parallel do 4: idf ← idfs[term_id𝑞,𝑡 ] 5: start ← offsets[term_id𝑞,𝑡 ] 6: end ← offsets[term_id𝑞,𝑡 + 1] 7: for 𝑖 ← start + tid to end step 128 do 8: 𝑑 ← doc_ids[𝑖 ] 9: tf ← tfs[𝑖 ] tf · (𝑘 1 + 1) 10: score ← idf · tf + 𝑘 1 · (1 − 𝑏 + 𝑏 · doc_lens[𝑑 ]/avgdl) 11: atomicAdd(𝑆 [𝑞 ] [𝑑 ], score) 12: end for 13: end for — Kernel 2: Top-𝑘 Selection — Grid: 𝐵, Block: 128 threads (4 warps) 14: for each block 𝑞 in parallel do Each thread: scan 𝑆 [𝑞 ] with stride, build local sorted buffer of size 15: 𝑘 ⊲ Phase 1 16: Write local buffers to shared memory ⊲ Phase 2 Variant A (naive): 17: Thread 0: scan all 128𝑘 candidates 𝑘 times, select & invalidate max each round Variant B (warp-cooperative): 18: for 𝑖 ← 1 to 𝑘 do ⊲ Phase 3 19: Each thread: find local max in assigned range 20: __shfl_xor_sync: 5-step intra-warp reduce 21: Warp lane 0 → inter-warp staging 22: Thread 0: pick global max from 4 warp leaders 23: Invalidate winner; __syncthreads() 24: end for 25: end for 26: Copy top-𝑘 IDs & scores to host ⊲ D2H

term_id | term | offsets[term_id] 0 | cat | 0 <- doc_ids[0..3] = postings for "cat" 1 | dog | 4 <- doc_ids[4..6] = postings for "dog" 2 | fish | 7 <- doc_ids[7..8] = postings for "fish" -| -| 9 <- offsets sentinel (total postings) doc_ids[]: [0, 2, 3, 4, 1, 2, 4, tfs[]: [2, 1, 1, 3, 1, 2, 1, idfs[]: [1.2, 0.8, 1.5] doc_lens[]:[10, 8, 12, 7, 9]

0, 3] 1, 1] # per-term # per-doc

A query for “cat dog” iterates: offsets[0..2] → touch postings [0, 4) for “cat” and [4, 7) for “dog”, accumulating BM25 partial scores via atomicAdd. No pointer chasing; flat-array layout is GPUfriendly (coalesced reads, no branch divergence on posting walks).

Algorithm 3 SPLADE Bridge: Ingest Learned-Sparse Weights into AgentIR’s CSR Posting Layout Require: Corpus {𝑑 1 , . . . , 𝑑 𝑁 }, SPLADE encoder 𝜙 : text → R𝑉≥0 (log1p(relu(MLM-logits)) max-pooled over the sequence) Ensure: CSR inverted index (𝐼𝑡 ,𝑊𝑡 )𝑡𝑉=1 where 𝐼𝑡 is the doc-id posting list for term 𝑡 and 𝑊𝑡 is the parallel SPLADE-weight payload 1: Encode docs: for each 𝑑𝑛 , compute w𝑛 ← 𝜙 (𝑑𝑛 ); keep only non-zero entries. Per-doc nnz ≈ 160–200 out of 𝑉 =30,522. 2: Transpose to inverted layout: build CSC over { (𝑛, 𝑡, 𝑤𝑛,𝑡 ) : 𝑤𝑛,𝑡 > 0}; assign 𝐼𝑡 ← doc-id list for term 𝑡 , 𝑊𝑡 ← weight list (parallel, sortedby-doc). ⊲ The result is bit-identical in structure to the BM25 CSR (Figure 10); only the payload semantics change: 𝑊𝑡 contains a learned weight instead of integer tf. — Query time — Require: Query 𝑞, top-𝑘 budget 𝑘 (𝑞) 3: w (𝑞) ← 𝜙 (𝑞); extract non-zero (𝑡 𝑗 , 𝑤𝑡 ) 𝑚 𝑗 =1 , 𝑚 ≈ 60 𝑗 4: 𝑆 [1..𝑁 ] ← 0 5: for 𝑗 ← 1 to 𝑚 do ⊲ posting-list traversal (𝑞) 6: 𝑤𝑞 ← 𝑤𝑡 𝑗 7: for 𝑖 ∈ [offsets[𝑡 𝑗 ], offsets[𝑡 𝑗 + 1] ) do ⊲ vectorizable with AVX2 8-wide FMA 8: 𝑆 [𝐼𝑡 𝑗 [𝑖 ] ] += 𝑤𝑞 · 𝑊𝑡 𝑗 [𝑖 ] 9: end for 10: end for 11: return top-𝑘 documents by 𝑆

offsets

0

3

5

9

12

15

doc_ids Term 0

Term 1

Term 2

tfs

idfs

doc_lens indexed by doc ID

Figure 10: CSR memory layout for GPU index upload. The offsets array delimits per-term posting list boundaries in the flat doc_ids and tfs arrays. IDF values and document lengths are stored in separate dense arrays indexed by term ID and document ID, respectively.

D Router Robustness Full Grids D.1 𝛼, 𝜏 sensitivity sweep R@10 on 344 recency-typed LongMemEval questions (multi-session + temporal-reasoning + knowledge-update).

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

𝛼\𝜏

7d

14 d

30 d

60 d

120 d

0.001 0.003 0.005 (used) 0.010 0.030

0.9695 0.9665 0.9657 0.9533 0.7493

0.9695 0.9674 0.9688 0.9540 0.7859

0.9710 0.9689 0.9708 0.9515 0.8709

0.9710 0.9704 0.9694 0.9490 0.8933

0.9695 0.9710 0.9704 0.9658 0.9091

Table 15: Ours CPU thread scaling at 𝑘=100 (Jetstream2 8-core, NLTK tokenizer, SIMD on). Bold = best for that dataset.

Noise level

Clf. acc.

Router (mini)

Router (gpt-4o)

0% (clean) 5% 10% 20%

0.794 0.770 0.724 0.614

0.262 0.260 0.250 0.252

0.300 (oracle) 0.296 0.288 0.286

𝑁 train

clf. acc.

router (mini)

router (gpt-4o)

25 50 100 200 300 400

0.622 0.650 0.696 0.780 0.802 0.796

0.296 0.302 0.294 0.304 0.308 0.310

0.330 0.336 0.328 0.336 0.338 0.340

Best static Oracle (gt qtype)

— —

0.280 (agent_rrf) 0.310

0.320 (RRF) 0.340

1T (ms)

4T (ms)

8T (ms)

1T→8T

NFCorpus SciFact FiQA SciDocs

0.02 0.08 0.38 0.23

0.04 0.07 0.18 0.13

0.04 0.08 0.15 0.12

— 1.0× 2.5× 1.9×

Table 16: Per-stage hybrid latency (ms/query, Jetstream2 8-core, BGE-small CPU encoding, 𝑘=100). BM25 here uses rank_bm25 for apples-to-apples; our C++ BM25 (Table 4) replaces this stage with 0.04–0.35 ms.

D.2 Query-noise robustness D.3 Deployment-labeling learning curve E Component Ablation & Thread Scaling (Full Tables) Table 14: Component ablation across 8 BEIR datasets (Jetstream2 8-core, ms per query at 𝑘=100). Each column adds one component to the previous. All configurations preserve nDCG@10 to within ±0.001. Dataset

Dataset

|𝐷 |

1T scalar

+SIMD

+MaxScr

+8T

Δ

NFCorpus 3.6K SciFact 5.2K ArguAna 8.7K SciDocs 25.7K FiQA 57.6K TREC-COVID 171K Quora 523K NQ 2.7M

0.04 0.22 1.54 1.08 1.85 14.92 2.22 67.60

0.03 0.08 0.40 0.23 0.40 4.76 0.71 6.64

0.03 0.09 0.47 0.20 0.36 2.15 0.60 4.23

0.05 0.08 0.24 0.10 0.15 2.15 0.17 1.38

0.8× 2.8× 6.4× 10.8× 12.3× 6.9× 13.1× 49.0×

F Hybrid End-to-End Per-Stage Latency G LoCoMo Full Per-System Table H LongMemEval Per-Question-Type Full Breakdown Table 18 reports the full 4×4 grid of per-question-type metrics: R@10 (session-level recall), AnswerSubstr@10 (gold answer string in top-10 context), TokenRecall@10 (gold-answer token recall), and

Dataset

𝑞-embed

BM25∗

Dense

RRF

Total

168 169 221 171 170

8.6 22.3 425.7 111.7 194.5

2.1 1.3 3.8 4.0 9.1

0.08 0.08 0.25 0.10 0.09

179 192 650 287 374

NFCorpus SciFact ArguAna SciDocs FiQA

Table 17: LoCoMo session-level retrieval, 1,982 questions across 10 conversations. See §5.9 for discussion. System

Hit@1

Hit@5

Hit@10

MRR

ms/q

BM25 Dense (BGE-small) RRF

0.625 0.318 0.483

0.875 0.632 0.797

0.945 0.789 0.923

0.735 0.464 0.625

0.22 32.0 32.3

LLM-judged strict accuracy (gpt-4o-mini answerer → gpt-4o-mini judge against gold). Best system per row in bold. Three observations from the full breakdown: The downstream-task signal has more variance than session-level recall. R@10 is high and tight across all systems (87–100% on every type), but LLM-judged strict accuracy spans 0.000–0.436—a 60× range driven by how well the LLM can extract the answer from the retrieved context. This justifies our addition of AnswerSubstr@K, TokenRecall@K, and LLM-Acc beyond the standard R@K metric: at the session-level R@10 plateau, the systems are nearly indistinguishable; at the downstream-task signal they diverge meaningfully. Agent_rrf is dominant on multi-session and competitive elsewhere. Per LLM-Acc, agent_rrf wins multi-session by +0.053 over RRF/Dense (the largest single-system delta in the entire grid). On the other five types it ties or trails by ≤0.033. The net effect on the overall 500-question accuracy is the +0.006 to +0.018 gain reported in Table 9. single-session-preference is structurally hard. All four systems score 0.0 on AnswerSubstr@10 (the gold answer is a preference statement that paraphrases rather than literal recall) and 0.000– 0.100 on LLM-Acc. This type is not a retrieval problem; no fusion strategy helps materially. It is the cleanest case in the benchmark for

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

Table 18: LongMemEval per-question-type detailed metrics (500 questions across six types). Best in each block bold. Question type

System

R@10

Ans@10

TokR@10

LLM-Acc

knowledge-update (𝑛=78)

BM25 Dense RRF agent_rrf

0.994 0.987 0.994 0.994

0.744 0.756 0.756 0.744

0.578 0.581 0.591 0.577

0.410 0.397 0.436 0.410

multi-session (𝑛=133)

BM25 Dense RRF agent_rrf

0.905 0.950 0.972 0.965

0.459 0.436 0.451 0.451

0.336 0.322 0.341 0.340

0.241 0.218 0.218 0.271

single-sessionassistant (𝑛=56)

BM25 Dense RRF agent_rrf

0.982 1.000 1.000 1.000

0.554 0.554 0.554 0.554

0.861 0.881 0.877 0.877

single-sessionpreference (𝑛=30)

BM25 Dense RRF agent_rrf

0.867 0.867 0.967 0.967

0.000 0.000 0.000 0.000

single-sessionuser (𝑛=70)

BM25 Dense RRF agent_rrf

1.000 0.943 1.000 1.000

temporalreasoning (𝑛=133)

BM25 Dense RRF agent_rrf

0.934 0.915 0.952 0.963

|𝐷 |

enc. wall (s)

ms/doc

nnz/doc

0.339 0.357 0.339 0.339

NFCorpus SciFact ArguAna SciDocs FiQA TREC-COVID Quora

3.6K 5.2K 8.7K 25.7K 57.6K 171K 523K

∼600 ∼870 1,397 ∼4,240 ∼9,510 27,048 87,600

165 165 161 165 165 158 167

187 168 184 166 160 163 61

0.845 0.845 0.856 0.856

0.033 0.000 0.100 0.067

Estimated extrapolations: NQ MS MARCO

2.7M 8.8M

∼432K (5.0 days) ∼1.41M (16.3 days)

160 160

— —

0.814 0.786 0.814 0.814

0.776 0.768 0.777 0.777

0.171 0.186 0.186 0.186

0.263 0.271 0.271 0.278

0.817 0.806 0.826 0.833

0.203 0.188 0.196 0.188

diagnosing model-side answering failure versus retrieval failure— and the right metric to track on this type is the LLM accuracy directly, not any retrieval proxy.

I

Table 19: SPLADE++ encoding cost on Jetstream2 g3.medium (8 vCPU CPU only, sparse-CSR output). nnz/doc is the average number of non-zero terms per document after log1p(relu(MLM-logits)) max-pool; sparsity is 1−nnz/doc/|𝑉 | for |𝑉 |=30522.

SPLADE Encoding Cost & Sparsity

Table 19 reports the per-dataset SPLADE++ encoding wallclock time and the resulting posting structure for the seven datasets we ran (§5.8). We measured these on the same Jetstream2 g3.medium host used for our BM25 benchmarks (8 vCPU, no GPU), with the naver/splade-cocondenser-ensembledistil checkpoint (110 M params) at max_len=256 and batch_size=8. Sparsification (filter w𝑑 > 0, store as scipy.sparse.csr_matrix) brings peak RAM from 28+ GB (dense 𝑁 × 𝑉 tensor) down to under 5 GB even on the 523K-document Quora corpus. Two observations from the appendix table:

Dataset

paragraphs. This matters for the SPLADE bridge (§5.8): a sparser doc weight matrix gives shorter posting lists, which means agent_rrf with SPLADE weights inherits even better per-query latency on Quora-like agent memory (short conversational turns) than on FiQA-like memory (longer paragraphs).

J

Cascade Router: Full Sweeps and CV

This appendix collects the full numerical sweeps underlying the cascade router results in §5.9.

J.1

Single-threshold BM25-confidence cascade

Table 20 sweeps the BM25-margin threshold 𝜏𝑐 =(𝑠 0 −𝑠 1 )/𝑠 0 across [0, 1] on the full 500-question LongMemEval (both gpt-4o-mini answerer and judge, agent_rrf escalate path). At 𝜏𝑐 =0 the cascade degenerates to BM25-only; at 𝜏𝑐 →∞ it reduces to always-hybrid agent_rrf. Table 20: Cascade Pareto sweep on LongMemEval (500q). Latency amortizes 𝐿BM25 =0.4 ms (skip path) and 𝐿hyb =53.2 ms (escalate path). Three escalate variants: agent_rrf (𝜏=30d), per-qtype 𝜏 (multi-session 𝜏=120d), and soft router.

Encoding cost is the SPLADE bottleneck. SPLADE’s quality wins on the seven measured datasets come at a per-doc encoding cost of ∼160 ms (CPU forward pass through a 110 M-parameter MLM). Perquery encoding is comparable. Even on a 100K-document corpus the encoding wall-clock is 5+ hours; on MS MARCO it would be 16+ days of single-VM CPU. This is why our paper’s main quality comparison with Pyserini Lucene (which uses zero learned-vocabulary expansion) and PISA (same) is the more relevant baseline for an agent-memory deployment where the corpus grows during the session: SPLADE-grade quality is reachable only when the corpus is small enough to amortize the encoder cost, or when the encoder is a per-query GPU service.

J.2

Sparsity is dataset-dependent. The Quora corpus is materially sparser (61 nnz/doc) than the others (160–187 nnz/doc) because Quora documents are short duplicate-question phrasings, not full

Per-fold breakdown of the per-qtype cascade in 5-fold CV (classifier and thresholds tuned on 4 folds, evaluated on the held-out fold). Reported in §5.9 as 5.76× mean speedup at within-noise LLM-Acc.

𝜏𝑐

skip %

ms/q

ar-LLM-Acc

per-qt-𝜏 Acc

soft Acc

0.00 0.05 0.10 0.15 0.20 0.30 0.50 1.00

100.0 78.8 63.0 51.6 41.0 25.6 7.6 0.0

0.40 11.59 19.94 25.96 31.55 39.68 49.19 53.20

0.298 0.298 0.302 0.298 0.296 0.304 0.302 0.302

0.298 0.302 0.308 0.306 0.302 0.310 0.310 0.310

0.298 0.304 0.304 0.302 0.300 0.304 0.304 0.304

5-fold CV per-qtype thresholds

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

Table 21: 5-fold CV per-qtype cascade. Train tunes the TF-IDF qtype classifier and the per-qtype 𝜏𝑐 values (each set to maxskip while preserving per-qtype LLM-Acc within bootstrap noise of agent_rrf). Test fold is fully held out (100q).

Table 23: Confidence proxies on LongMemEval (500q). Margin proxy dominates because BM25 top-1/top-2 separation correlates most directly with retrieval certainty. proxy 𝑐 (𝑞)

fold

test LLM-Acc

test ms/q

test skip %

0 1 2 3 4

0.330 0.330 0.240 0.300 0.270

3.01 11.99 15.16 7.76 8.29

96.0 79.0 73.0 87.0 86.0

0.294 ± 0.035

9.24 ± 4.11

84.2

mean

The per-qtype thresholds in Table 11 are derived by sweeping 𝜏𝑐 separately on each question-type subset and choosing the maximum value that keeps the per-qtype LLM-Acc within 0.005 of the perqtype agent_rrf baseline (a within-bootstrap-noise margin for 𝑛=30– 133). Table 22: Per-qtype thresholds (in-sample tuning). The perqtype BM25 confidence distribution differs sharply across types: single-session-assistant and single-session-user have very confident BM25 (median margin > 0.3) so the cascade can skip aggressively; multi-session has low BM25 confidence (median 0.11) so 𝜏𝑐 stays near zero.

J.4

𝑛

median conf.

𝜏𝑐

skip %

knowledge-update multi-session single-session-assistant single-session-preference single-session-user temporal-reasoning

78 133 56 30 70 133

0.113 0.107 0.420 0.073 0.347 0.130

0.12 0.02 0.28 0.00 0.00 0.00

51 89 96 37 83 61

weighted

500

0.157

—

86–89

Confidence-proxy comparison

The BM25 top-1/top-2 margin is one of several plausible classifierfree triggers. We compared three at the best-parity threshold (each tuned to the max skip that preserves always-hybrid agent_rrf LLMAcc within noise):

J.5

0.01 0.04 0.02

18.81× 5.05× 1.60×

Table 24: Cascade BM25-confidence sweep on LoCoMo (1,982q, Hit@5 metric). Optimum at 𝜏𝑐 →∞ (skip everything = BM25-only) yields Hit@5 0.875, +0.089 over always-hybrid agent_rrf.

Per-qtype 𝜏𝑐 derivation

qtype

speedup at parity

top-1/top-2 margin (𝑠 0 −𝑠 1 )/𝑠 0 Í top-1 fraction 𝑠 0 / 𝑖 𝑠𝑖 1 − normalized entropy of top-K

The high per-fold variance (𝜎=0.035) reflects 100-question test slices; the mean LLM-Acc 0.294 is within 𝜎 of always-hybrid agent_rrf 0.302, and the mean amortized latency 9.24 ms is 5.76× below the 53.2 ms always-hybrid budget.

J.3

best 𝜏𝑐

Cross-benchmark sweep on LoCoMo

𝜏𝑐

skip %

ms/q

Hit@5

0.00 0.05 0.10 0.15 0.20 0.30 0.50 1.00

100.0 82.0 67.9 56.5 47.2 30.0 8.2 0.0

0.40 10.00 17.50 23.55 28.49 37.36 48.86 53.20

0.875 0.865 0.842 0.829 0.826 0.814 0.790 0.786

serving 𝑁 concurrent agents (each issuing one query at a time with BGE-encoder-bound back-pressure), the BGE-bound throughput is 8/((1−skip) · 𝐿BGE ) q/s. Table 25: Multi-tenant capacity on 8-core VM, derived from per-stage latencies. Cascade trades classifier-induced skip rate for 9× higher concurrent-tenant capacity at within-noise quality. configuration

skip %

amort. ms/q

tenants @ 1 qps

0 63 89

52.4 19.6 6.1

∼154 ∼416 ∼1,399

always-hybrid cascade 𝜏𝑐 =0.10 cascade per-qtype

J.7 J.8

Cascade algorithm pseudocode C++ API reference

The cascade router is a ∼70-line C++ class (include/cascade_router.h, src/cascade_router.cpp) that wraps any sparse/dense retrieval backend through function callbacks. Minimal usage: #include "cascade_router.h" using namespace hybrid;

The cascade sweep on LoCoMo (Figure 8) in full numerical form:

CascadeRouter::Config cfg; cfg.conf_threshold = 0.10f; cfg.use_qtype_classifier = false;

J.6

auto bm25_fn = [&](auto& q, int k) { return idx.bm25_topk(q, k); }; auto dense_fn = [&](auto& q, int k) { return idx.dense_topk(q, k); };

Multi-tenant cascade capacity

The multi-tenant capacity numbers in §6 follow from the per-stage latency budget (Table 16) and the cascade skip rate. On 8 cores

// single-threshold mode // or true + supply qtype_fn

auto decision = CascadeRouter::retrieve( query_text, records, query, current_time_ms,

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

Algorithm 4 Cascade Router (CascadeRouter::retrieve). Require: Query 𝑞, top-𝑘 budget 𝑘, threshold 𝜏𝑐 (or per-qtype 𝜏𝑐 [ · ]), sparse function 𝑓BM25 , dense function 𝑓dense , optional qtype classifier 𝜋 1: 𝑆 ← 𝑓BM25 (𝑞, 𝑘 ) ⊲ always run BM25, ∼0.4 ms 2: 𝑠 0 , 𝑠 1 ← top-2 scores in 𝑆 3: 𝑐 (𝑞) ← (𝑠 0 − 𝑠 1 )/max(𝑠 0 , 𝜖 ) 4: if 𝜋 supplied then ˆ ← 𝜋 (𝑞); 𝜏 ← 𝜏𝑐 [𝑞𝑡 ˆ] 5: 𝑞𝑡 ⊲ per-qtype 6: else 7: 𝜏 ← 𝜏𝑐 8: end if 9: if 𝑐 (𝑞) ≥ 𝜏 then 10: return TopK(𝑆, 𝑘 ) ⊲ skip dense 11: end if 12: 𝐷 ← 𝑓dense (𝑞, 𝑘 ) ⊲ escalate, BGE-encode ∼52 ms 13: 𝐻 ← agent_rrf (𝑆, 𝐷, 𝑞.ts) ⊲ Eq. 3 14: return TopK(𝐻, 𝑘 )

/*top_k=*/5, cfg, bm25_fn, dense_fn); if (decision.escalated) std::cout << "dense channel was used\n"; std::cout << "latency: " << decision.latency_ms << " ms\n"; for (auto& r : decision.results) handle(r);

For per-qtype thresholds, supply the optional classifier callback: cfg.use_qtype_classifier = true; auto qt_fn = [&](auto& q) { return classifier.predict_best(q); // returns "BM25" or system name }; auto d = CascadeRouter::retrieve( query, records, query_obj, ts, 5, cfg, bm25_fn, dense_fn, qt_fn);

J.9

Worked example: tracing one query

Concretely, here is one LongMemEval question routed through the cascade with the BM25-confidence trigger (𝜏𝑐 =0.10):

Stage 2 (Dense + RRF + recency): agent_rrf top-5 {D 4 (Big Sur), D 9 (Yellowstone), D 4’, D 2, D 16}. The recency bonus surfaces D 9 (Yellowstone) into the top-5; BM25 alone had it at rank 3 with low margin. Output: both gold sessions in top-5, in 53 ms. LLM correctly sums to 8. LLM-Acc: yes. (BM25-only would have answered 3.)

J.10

When does the cascade help / when does it hurt?

Cascade decision cheat-sheet

Cascade helps when at least one of: • BM25 alone has clear top-1 (factual recall, named entities, session-scoped queries). • Dense channel is expensive (BGE encoder ≥ 10 ms, hosted embedding API, cached LLM hidden state unavailable). • Workload is multi-tenant and BGE-bound on shared hardware. Cascade adds little when: • Dense channel is essentially free (pre-computed query embeddings; small encoder). • Workload is uniformly hybrid-favoring (most queries benefit from dense). • Per-qtype label budget is unavailable (single-threshold cascade still gives 2.67×; per-qtype gives 5.76× with ∼50 labels). Cascade hurts (rare) when: • BM25 top-1 score is high but consistently wrong (extreme vocabulary mismatch); confidence proxy mis-fires. We did not observe this on LongMemEval/LoCoMo; defensive mitigation is a small 𝜏𝑐 >0 floor.

Worked example: temporal-reasoning question (skip path)

Question: “Which book did I just finish reading?” (gold answer: ‘The Nightingale’). Stage 1 (BM25): top-5 sessions {D 12: 8.74, D 7: 2.13, D 3: 1.40, D 21: 0.91, D 5: 0.83}. 𝑐 (𝑞)=(8.74−2.13)/8.74 = 0.756. Trigger: 𝑐 (𝑞)=0.756 ≥ 0.10 ⇒ skip dense channel. Output: BM25 top-5 returned in 0.43 ms. Top hit D 12 is the gold session. LLM-Acc: yes. Counterfactual: always-hybrid would have spent 52.4 ms on BGE encoding for an unchanged answer (D 12 still tops the RRF list). Worked example: multi-session question (escalate path)

Question: “How many camping days have I taken this year?” (gold answer: 8; two evidence sessions, Big Sur 3 days + Yellowstone 5 days). Stage 1 (BM25): top-5 {D 4: 4.21, D 4’: 3.97, D 9: 3.48, D 2: 3.12, D 16: 2.90}. 𝑐 (𝑞)=(4.21−3.97)/4.21 = 0.057. Trigger: 𝑐 (𝑞)=0.057 < 0.10 ⇒ escalate.

J.11

Deployment recipe

5-minute deployment recipe

1. Collect ∼50 labeled deployment questions (Q, A, goldsession-id). 2. Run all 4 base systems (BM25, Dense, RRF, agent_rrf) on each Q; compute per-qtype LLM-Acc with your judge of choice. 3. Pick the per-qtype best system 𝑠 ∗ (𝑞𝑡); this is your pertype routing table (Table 18-style). 4. For each qtype, sweep 𝜏𝑐 ∈ [0, 1] and pick the max value with within-noise per-qtype LLM-Acc; this gives 𝜏𝑐 [𝑞𝑡]. 5. Train a TF-IDF (or TF-IDF+BGE) classifier over the 50 labels using sklearn.linear_model.LogisticRegression. 6. Plug all four into CascadeRouter::Config; you now have a per-tenant tuned cascade. Re-tune quarterly or on drift detection.

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

J.12

Reproduction CLI

recency bonus on this qtype); per-qtype 𝜏 refinement, §5.9. Effect: +5.26 pts LLM-Acc on multi-session subset (𝑝=0.006, paired bootstrap).

# Build the C++ benchmark (CPU only, 8-core x86) cmake -B build -DENABLE_AVX2=ON -DENABLE_CUDA=OFF cmake --build build -j # Run cascade on LongMemEval (Python orchestration calls C++ BM25) python scripts/run_pertype_tau.py # cache BM25 + dense python scripts/run_cascade_locomo.py # cross-benchmark eval python scripts/cascade_router_analysis.py # Pareto sweep + figure

F3: GPU top-𝑘 stale shared-memory contamination

Symptom: GPU FiQA nDCG@10 dropped to 0.060 postbuild (24% top-1 match vs CPU). Recall@100 was the canary; nDCG@10 was masked because errors fell beyond rank 10. Mechanism: Top-𝑘 kernel reused per-block sharedmemory slots across queries. Slots beyond 𝑘 retained positive scores from a previous block; subsequent reductions picked these ghosts as the per-block max. Mitigation: Initialize all 𝐾max slots to −∞ before each block’s reduction phase. Post-fix CPU/GPU nDCG@10 agree to 0.0002 on all 8 datasets (§5.5).

# Reproduce Table tab:cascade single-threshold row (~10 min, $0.50): OPENAI_API_KEY=sk-... \ python scripts/run_llm_eval.py --config global_t30 --judge gpt-4o-mini # Full 5-fold CV per-qtype cascade (Table tab:cascade-cv, ~20 min): python scripts/cascade_cv_perqtype.py --folds 5 --seed 42

J.13

Numerical stability notes

Two stability points worth noting for re-implementers: • Confidence proxy. 𝑐 (𝑞)=(𝑠 0 −𝑠 1 )/𝑠 0 is scale-invariant but degenerates to 0 when both top scores are 0 (no posting matched any query term). The C++ guard at line 11 of bm25_confidence returns 0 in that case (always escalate); an alternative is to escalate unconditionally when |𝑆 | < 𝑘. • Per-qtype threshold ties. When sweeping 𝜏𝑐 to maximize skip rate within a noise window, multiple thresholds may achieve identical Acc. We pick the smallest 𝜏𝑐 that still preserves Acc (most aggressive skip); picking the largest yields the safest amortized cost at the same Acc but slightly lower speedup.

K

F4: MS MARCO index build OOM at 8.8M docs

Symptom: Naive build accumulated unordered_map<term,count> per-doc during tokenization; peak RSS exceeded 29 GB and OOM’d Jetstream2 g3.medium. Mechanism: Memory scales as 𝑂 (𝑁 ·distinct_terms_per_doc) when per-doc maps are retained until the global vocabulary is finalized. Mitigation: Chunked streaming build that processes documents in 50K-doc batches, dropping per-doc maps before the next batch. Peak RSS 29 → 12.7 GB; build throughput 27K → 56.8K docs/sec (page-fault overhead absorbed by amortized allocation).

Failure-Case Catalog

To complement the worked examples in §J.9, we enumerate four failure modes we encountered during development and the mitigations that produced the reported results. F1: BM25 over-tokenization on numeric tickers

Symptom: FiQA queries containing tickers (“AAPL”) or percentages (“401(k)”) under-retrieve. Mechanism: Our minimal tokenizer splits on nonalphanumeric, dropping the “(” inside 401(k); Lucene’s StandardTokenizer preserves the compound as a single token. Mitigation: Use HYBRID_TOK_MODE=nltk (NLTK Porter + English stopwords), restoring +0.013 nDCG@10 on FiQA. Residual 0.011 gap is analyzer-level; closed by hybrid RRF (+0.067 on FiQA, Table 6). F2: Recency bonus over-weights non-gold multi-session queries

Symptom: Multi-session questions where gold sessions are recent (median age 3 d) and similar-vocabulary nongold sessions are also recent get the wrong session at top-1. Mechanism: agent_rrf bonus 𝛼𝑒 −Δ𝑡 /𝜏 with 𝜏=30 d produces near-uniform boost for sessions within ∼30 d, so RRF-tied recent non-gold beats gold by the bonus margin. Mitigation: Set 𝜏multi-session ≥120 d (essentially flatten the

L

FAQ

We collect six questions reviewers have asked or are likely to ask, with sharp pointers into the paper or appendix. Q1. Is the cascade router just the existing discrete router with early termination?

No. The discrete router (Table 10) always runs the full hybrid path before selecting which ranker’s output to emit (53.7 ms per query). The cascade router runs BM25 first and skips the dense channel on 63–89% of queries, so its amortized latency is 19.94 ms (single-thresh) or 6.81 ms (per-qtype). The accuracy is identical to the discrete router by construction (same classifier + same per-type-best table) when the cascade decision matches the discrete router’s choice; the new claim is the latency saving.

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

Q2. Why not compare to Mem0 / MemGPT end-to-end?

Q6. Theorem 1’s bound is trivial.

Mem0 and MemGPT operate at the memory-management policy layer (write-batching, fact extraction, consolidation) over a generic IR substrate. AgentIR’s contribution is the retrieval substrate itself : a deployment can combine, e.g., Mem0’s write policy with AgentIR’s retrieval and inherit both gains (§7). An end-to-end LLM-Acc comparison would conflate retrieval quality with answer-generation prompting; Mem0’s reported 94.8 on LongMemEval uses an extensively engineered 150+-line chain-of-thought answerer that our 5-line answerer prompt deliberately does not replicate in order to keep retrieval and generation comparisons clean.

The theorem itself is a short observation in the spirit of time-aware retrieval [2, 13]. What is new is identifying the regime where it bites: agent workloads have 𝜆 ≫ 0 (LongMemEval median normalized rank 0.20–0.27), so 𝑘 ∗ =⌈log(1/𝜀)/𝜆⌉=3 partitions suffice for 𝜀=0.05. Web search’s slowly-drifting 𝜆 → 0 degrades the bound to linear, which is why generic IR engines do not exploit the structure. The 1769× empirical speedup is the consequence of the regime match.

Q3. The 5M scaling corpus is synthetic. Does the recency assumption hold on real agent traces?

The 80/20 stress parameterization is calibrated against LongMemEval’s measured gold-session distribution (median normalized rank 0.20–0.27 for temporal/knowledge/multi-session questions, §5.4). At the scale of a real 800-turn session with ∼5 M records, no public benchmark exists; the 1769× speedup is therefore stress-test rather than production trace. We list this explicitly in Threats to Validity (§6); a production trace at that scale would tighten the validation. Q4. The PISA-1T vs. AgentIR-8T comparison looks unfair.

PISA does not natively support multi-threaded inter-query dispatch (its queries binary is single-process). Table 5 reports both PISA-1T and our 8T+SIMD; we also report AgentIR-1T scalar (Appendix E) matching PISA-1T on small corpora and trailing only on large corpora where PISA’s variable-byte compression pays off. SIMD closes the 1T gap; 8T then puts AgentIR ahead. The architectural comparison—posting compression vs. SIMD-vectorized scan—favors AgentIR on long-query workloads (ArguAna 90×); BlockMax-WAND degenerates when most posting lists must be evaluated. Q5. The cascade is analytical for latency, not wall-clock measured. Why?

Cascade LLM-Acc is measured (it equals the TF-IDF router by construction; both make identical routing decisions, only execution order differs). The latency 40.5 ms is a deterministic function of measured per-stage latencies (Table 16) and the measured skip rate—not a simulation. An end-toend wall-clock run of the C++ CascadeRouter::retrieve is left for future work to characterize the tail behavior under classifier misprediction; the mean behavior is fixed by the algebra.

M

Reproducibility

Source code. The complete AgentIR implementation (∼7,000 LOC of C++17 and CUDA, plus ∼400 LOC of Python orchestration for LongMemEval and LoCoMo) will be released open-source upon acceptance under an MIT license, along with all benchmark scripts and CSV result files. Build requirements. C++17 compiler (GCC ≥ 11), CMake ≥ 3.18, OpenMP 4.0+, and optionally CUDA Toolkit ≥ 12.0 for GPU acceleration. HNSW uses the header-only hnswlib library (bundled). Python dependencies (BGE-small via sentence-transformers, rank_bm25) are listed in requirements.txt. Build and benchmark. # CPU build with AVX2 (Jetstream2 g3.medium) cmake -DENABLE_AVX2=ON .. && cmake --build . -j$(nproc) # GPU build (A100, sm_80; NCSA Delta gpuA100x4) cmake -DENABLE_CUDA=ON -DCMAKE_CUDA_ARCHITECTURES=80 .. cmake --build . -j$(nproc) # BEIR head-to-head (any of 9 datasets, MS MARCO via streaming build) HYBRID_TOK_MODE=nltk ./benchmark_beir \ --data /path/to/beir/scifact --threads 8 --simd --topk 100 # GPU BEIR (with CPU cross-check) HYBRID_TOK_MODE=nltk ./benchmark_beir_gpu \ --data /path/to/beir/nq --topk 100 --cpu-cmp # Temporal scaling sweep (4K --> 5M synthetic records) ./demo --queries 200 --turns 8 --no-concurrent

Hardware budget. All BEIR CPU and temporal-scaling experiments ran on an 8-vCPU Jetstream2 g3.medium VM (29 GB RAM, Ubuntu 22.04, GCC 11.4) at no recurring cost. GPU evaluation ran on NCSA Delta gpuA100x4-interactive (1 A100-SXM4-40GB + 8 EPYC cores per allocation) for a total of ∼15 GPU-hours against an NSF ACCESS allocation, equivalent to ∼$45 at on-demand cloud pricing. Pyserini baselines used identical hardware to ensure applesto-apples comparison. Dataset access. BEIR datasets (NFCorpus, SciFact, ArguAna, SciDocs, FiQA, TREC-COVID, Quora, NQ, MS MARCO Passage) downloaded from BEIR’s public ukp.informatik.tu-darmstadt.de mirror. LongMemEvalcleaned from xiaowu0162/longmemeval-cleaned on HuggingFace. LoCoMo from snap-research/locomo on GitHub. Determinism and seeds. All BM25 inner-loop computations are deterministic on CPU at every thread count (1T, 4T, 8T): per-thread posting partitioning is disjoint and the final reduction is sequential.

Aojie Yuan, Haiyue Zhang, and Shahin Nazarian

GPU runs use atomicAdd, which is non-deterministic in float32 addition order, so per-query ranks may differ between GPU invocations on tied-score documents; the top-10 set and nDCG@10 are invariant to within ±0.0002 across reruns (the residual is floatingpoint summation drift, not algorithmic). The synthetic agent corpus generator (§5.4) accepts a CLI –seed flag for full reproducibility; the seed used for all reported scaling rows is 42. What we report vs. what we omit. We report nDCG@10, MRR@10, and Recall@100 (the BEIR-standard triplet), per-query latency (mean, 𝑝50, 𝑝95, 𝑝99), and throughput (qps) for every BEIR row in Table 4. We omit cold-cache latency (we measure with a warmed-up index, the agent-memory operating regime), indexbuild wall time on datasets smaller than NQ (negligible: ≤10 s), and any results involving proprietary LLM judging. The full results/baselines/{beir_ours,beir_pyserini}.csv files are included in the artifact. Reproducibility checklist (CIKM).. • Code will be released on acceptance (MIT license). • Datasets are all public BEIR / LongMemEval / LoCoMo. • Hardware is reproducible: Jetstream2 g3.medium (∼$0/hr via NSF ACCESS) for CPU; NCSA Delta gpuA100x4 (∼$3/hr equivalent) for GPU. Total GPU budget for all GPU experiments in this paper: ∼15 GPU-hours. • All hyperparameters listed in the cookbook below at the exact value used in the table that depends on them; no tuned perdataset hyperparameters. Hyperparameter cookbook. A one-stop table of every hyperparameter used in any experiment, the value, and the table/figure where it is exercised: Adapting to a new deployment. The 5-minute recipe in §J.11 covers the typical case (50 labeled questions, gpt-4o-mini judge, single 8-core machine). For non-default LLM judges (Anthropic, Llama, on-premise), only the cascade trigger Table 22 needs rederivation; the substrate, classifier architecture, and algorithm code stay constant.

N

Threats to Validity

We follow the empirical-software-engineering convention of stating the threats we are aware of, organized by the standard four categories. Construct validity — does the metric measure the intended concept? LLM-judged accuracy on LongMemEval uses gpt-4o-mini as the judge. Judges with weaker reasoning may under-credit correct answers phrased differently from the gold reference; judges with stronger reasoning may over-credit (we observed this at the discrete oracle, where the gpt-4o judge lifts the oracle ceiling by +0.046). We mitigate by reporting the gpt-4o judge alongside the cheaper one for every cascade comparison (§5.9, Tables 10 and 11) and by reporting paired-bootstrap 𝑝-values against the always-hybrid baseline rather than absolute accuracy alone. Hit@𝑘 on LoCoMo is the metric in [17] and is unambiguous.

Table 26: Complete hyperparameter cookbook for all reported experiments. No table uses a value not in this list. component

param

value

used in

BM25 BM25 BM25 BM25 RRF Recency Recency Recency Temporal index Temporal index Temporal index Dense Dense HNSW HNSW GPU top-𝑘 GPU top-𝑘 Cascade Cascade Cascade Router CV folds LLM answerer LLM judge Build

𝑘1 𝑏 top-𝑘 analyzer 𝑘 RRF 𝛼 𝜏 (global) 𝜏multi-session partition window 𝐾max partitions 𝜀 recall slack model dim 𝑀 efConstruction 𝐾max slot count block size 𝜏𝑐 single-thresh per-qtype 𝜏𝑐 classifier 5 gpt-4o-mini gpt-4o-mini / gpt-4o chunked batch size

1.2 0.75 100 NLTK Porter 60 0.005 30 d ≥ 120 d 7d 4 0.05 BGE-small-en-v1.5 384 32 200 128 (𝑘 ≤128) 128 threads 0.10 Tab. 22 TF-IDF+BGE LR — temp 0 temp 0 50K docs

all BM25 tables all BM25 tables Tab. 4, 5 main results Tab. 6 §5.9 main agent_rrf §5.9 §5.4 Tab. 2 Thm. 4.1 §5.7 §5.7 §5.7 §5.7 §4.4 §4.4 Tab. 11 §5.9 Tab. 10 Tab. 10, 21 Tab. 9 Tab. 9, 10 §5.6 MS MARCO

Internal validity — could the speedups be confounded? The fivefold CV for per-qtype thresholds rules out the most obvious confounder (test-set tuning); we re-derive each fold’s thresholds from scratch on its training partition and evaluate on the held-out partition (§J.2). The amortized latency reported throughout the paper is a deterministic function of measured stage latencies and measured skip rates, not a model fit: Lamort = 𝜌 · Lskip + (1−𝜌) · Lescalate with 𝜌 the empirical skip rate. Multi-tenant numbers (Fig. 9) are on an idle Jetstream2 host with hyperthreading and turbo disabled, three trials, median reported; shared-cache contention could lower the 9× figure on a less-quiescent host, which we flag explicitly. External validity — does the result generalize? The cascade trigger is data-dependent on the BM25 score distribution, which itself depends on the corpus’s term-frequency shape. We exercise it on two qualitatively different distributions—LongMemEval (BGEtokenized session text, mean length 312 tokens) and LoCoMo (dialogue text, mean length 1,847 tokens)—and observe auto-tuning in both directions (skip 63% vs. skip 100%). Datasets with heaviertailed BM25 scores (e.g. short queries on Wikipedia-scale corpora) may exhibit different optimal 𝜏𝑐 ; we provide the recipe to re-derive on a 50-query sample (§J.11). Quality results on BEIR generalize the substrate’s BM25 implementation; quality on agent memory generalizes the fusion logic. Cross-language deployment was not evaluated (English only). Conclusion validity — are the statistical claims sound? Pairedbootstrap with 104 resamples is used wherever the text says “parity” or “significantly”; the bootstrap is paired on ⟨question, system⟩

AgentIR: A Workload-Adaptive Cascade Retrieval Substrate for Long-Term Conversational Memory

to control for question-level variance. We report 𝑝-values rather than discrete reject/accept decisions because 𝑛=500 (LongMemEval) puts effect sizes of 0.01–0.02 near the detection limit. We do not report multiple-comparison corrections; readers interpreting many 𝑝-values jointly should adjust accordingly.

O

Negative Results and Things That Did Not Help

For the reader’s benefit, we list interventions that we implemented, evaluated, and rejected. Many of them looked attractive on paper. (1) Re-ranking the BM25 top-50 with a cross-encoder (ms-marco-MiniLM-L-6-v2). Improved LongMemEval Recall@5 by +0.6 points but added 74 ms/query (a 4× latency regression at the operating point we cared about) and did not move LLM-judged accuracy — the answerer was already saturating on the BM25 top-10 context. Dropped from the pipeline. (2) Hardcoding RRF 𝑘=30 instead of 60. Standard Cormack–Clarke–Buettcher value is 60 [5]; we swept 𝑘 ∈ {10, 20, 30, 60, 100} and observed ±0.003 Recall@5 across the entire range. Kept 𝑘=60 to match the literature. (3) Learned-to-rank meta-feature stack (LightGBM on BM25, dense, recency, length, click features) for LongMemEval routing. Improved per-fold accuracy by +0.005 but required maintaining a second feature pipeline and was indistinguishable from the cheaper TF-IDF+BGE-feature classifier on the held-out fold; the cost of operational complexity outweighed the benefit. (4) Query expansion via PRF (RM3, 𝛼=0.5, |𝐹 𝐵|=10). Standard +1−2 MAP gain on TREC-style ad-hoc tasks, but on LongMemEval queries (median length 9 tokens, often containing

the named entity verbatim) expansion introduced topic drift and regressed Hit@5 by −0.012. Disabled by default. (5) Dense channel on LoCoMo. We initially assumed dense retrieval would help LoCoMo’s longer sessions; the crossbenchmark sweep (§J.5) shows BM25 alone wins by +0.089 Hit@5. This negative result is what motivated the workloadadaptive framing in the first place. (6) GPU acceleration on small corpora. At 𝑁 <50K documents the BM25 GPU kernel is slower than the CPU SIMD version due to PCIe transfer overhead and warp under-utilization; the crossover is at roughly 𝑁 =300K documents on an A100 (§5.2). Deployments below that scale should stick with CPU, which is also why AgentIR keeps both backends live behind the same SparseIndex interface. (7) INT8 quantization of BGE-small embeddings. Halved the memory footprint at the cost of −0.004 Recall@10 on LongMemEval; the saving was not load-bearing on the deployments we ran (768-dim × 5M ≈ 15 GB at fp16, fits on a single host) so we kept fp16. What we learned from the negatives. Two themes recur. First, the LLM answerer absorbs a surprisingly large amount of retrieval noise: gains in Recall@𝑘 above ∼0.95 rarely translate to LLM-Acc gains, which is the regime where cheap retrieval pays. Second, every static optimization we tried (re-ranking, expansion, hardcoded fusion weights) lost to a per-query decision that costs less than 1 ms. The workload’s heterogeneity is large enough that the cost of choosing is less than the variance across the choices.

Related documents

• String Diagrams for Process Mining#978502
• ZigZag Trie: A Novel Index for Contextual Queries#978503
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#978504
• Efficiently Linking Unstructured Data for Multi-step Reasoning#978505