[Prefix-KV #7] Research: Radix Tree memory index for prefix-aware retrieval

[AugustChaoTW]

Background

SGLang's RadixAttention organizes KV cache entries as a Radix Tree (prefix tree) so that requests with overlapping token prefixes can share cached computation along the common path. This paper-level concept has an analogue at the memory retrieval layer: if two queries share a common prefix of terms, we can traverse a prefix tree to find matching memories without re-scanning the full FTS5 index.

Research Question

Can a Radix Tree (or Trie) index over memory content tokens provide measurable retrieval speedup for the opencode-owl query patterns, compared to FTS5 BM25?

Current Retrieval Architecture

memory_query("kv cache prefix") →
  1. FTS5 BM25 search: O(n log n)
  2. Vector KNN (Ollama): O(k) cosine distance
  3. RRF merge + decay sort

FTS5 already uses an inverted index internally, which is efficient for exact token matches. The question is whether a Radix Tree would help for prefix queries specifically (e.g., repeated queries that share leading terms across an AHE eval batch).

Proposed Investigation

Step 1: Characterize query prefix overlap in actual usage

Instrument memory_query calls to log the first N tokens of each query and compute Jaccard similarity between consecutive queries in an AHE run. If prefix overlap > 60%, a Radix Tree index is worthwhile.

# ahe analysis script
queries = [t.get("query") for t in access_log]
pairwise_prefix_overlap = ...

Step 2: Prototype Radix Tree index

Implement a TrieIndex class in TypeScript alongside FTS5:

class TrieIndex {
  private root: TrieNode = { children: {}, memoryIds: [] };

  insert(tokens: string[], memoryId: string): void { ... }
  prefixSearch(tokens: string[], maxResults: number): string[] { ... }
}

Tokenize memory content with the same porter-stemmed tokenizer as FTS5, build the trie at startup, update it on memory_add / memory_delete.

Step 3: Benchmark

Compare:

• FTS5-only retrieval latency (baseline)
• Trie-assisted retrieval latency (for queries sharing prefix with recent queries)
• Overhead: trie build time, memory usage

Decision Criteria

Result	Decision
Trie > 30% faster for prefix queries	Implement as opt-in mode via MEMORY_USE_TRIE=true
Trie < 10% faster	Close as won't-fix; FTS5 inverted index already handles this
Trie slower	Close as won't-fix

Limitations

Unlike LLM KV Cache where prefix sharing is on exact token sequences, owl memory queries are semantic (approximate keyword match), not exact prefix match. The Radix Tree benefit is most relevant for AHE batch eval where tasks have identical or near-identical query prefixes.

Deliverables

• Analysis notebook: query prefix overlap in AHE eval logs
• Benchmark results comparing FTS5 vs Trie for owl workload
• Decision documented in this issue; implement or close

Effort: 1–2 days research | Priority: Low (exploratory)