[NVIDIA #5] GPU-accelerated memory eviction scheduling via cuOpt (replace LRU)

[AugustChaoTW]

Summary

Replace opencode-owl's current LRU-based memory eviction with a GPU-accelerated optimal scheduling policy using NVIDIA cuOpt. cuOpt solves combinatorial optimization problems (LP, MILP, VRP) on GPU orders-of-magnitude faster than CPU solvers. The memory eviction problem maps naturally to an Integer Programming formulation.

Problem Formulation

Given:

• N active memories, each with score s_i = importance × decayScore × memoryStrength
• K cache slots (configurable MEMORY_ARCHIVAL_ACCESS threshold)
• Goal: select which K memories to retain to maximize total expected future utility

This is a Knapsack / Integer Programming problem:

maximize:   Σ s_i × x_i
subject to: Σ x_i ≤ K        (slot constraint)
            x_i ∈ {0, 1}     (binary: keep or evict)
            x_i = 1  if access_count > ACCESS_THRESHOLD  (pinned memories)

cuOpt solves this via GPU-accelerated MILP in milliseconds for N < 10,000.

Why Not Just LRU

LRU is optimal when all items have equal value and access patterns are recency-biased. Memory entries have heterogeneous value: a skill memory with high importance but infrequent access should be kept over a stale fact with many accesses. cuOpt finds the globally optimal eviction set instead of a heuristic approximation.

This directly addresses the research in Prefix-KV #7 (Radix Tree research) which found LRU can be suboptimal for semantic memory workloads.

Installation

# GB10 has CUDA 13.0 — use cuopt-cu13
pip install --extra-index-url=https://pypi.nvidia.com cuopt-cu13

# Verify (GB10 SM 12.1 satisfies cuOpt requirement of ≥ SM 7.0)
python3 -c "import cuopt; print(cuopt.__version__)"

Implementation

New file: src/cuopt-eviction.ts (TypeScript wrapper via child_process)

// Calls Python cuopt solver via subprocess for eviction decisions
export async function cuoptEvict(
  memories: Array<{ id: string; score: number; pinned: boolean }>,
  slots: number
): Promise<string[]> {  // returns IDs to evict
  const payload = JSON.stringify({ memories, slots });
  const result  = spawnSync("python3", [
    join(__dirname, "cuopt_eviction.py"), payload
  ], { encoding: "utf8", timeout: 5000 });
  return JSON.parse(result.stdout).evict_ids;
}

New file: src/cuopt_eviction.py

import sys, json, cuopt
from cuopt import optimization

def solve_eviction(memories: list[dict], slots: int) -> list[str]:
    n = len(memories)
    scores = [m["score"] for m in memories]
    pinned = [m["pinned"] for m in memories]

    # MILP: maximize Σ score_i * x_i, subject to Σ x_i <= slots
    model = optimization.MILPModel()
    x = [model.add_binary_variable(name=f"x_{i}") for i in range(n)]

    model.set_objective(
        optimization.maximize(sum(scores[i] * x[i] for i in range(n)))
    )
    model.add_constraint(sum(x) <= slots)
    for i, m in enumerate(memories):
        if m["pinned"]:
            model.add_constraint(x[i] == 1)

    sol = model.solve()
    keep_ids = {memories[i]["id"] for i in range(n) if sol.get_value(x[i]) > 0.5}
    evict_ids = [m["id"] for m in memories if m["id"] not in keep_ids]
    return evict_ids

if __name__ == "__main__":
    data = json.loads(sys.argv[1])
    result = solve_eviction(data["memories"], data["slots"])
    print(json.dumps({"evict_ids": result}))

Integration into MemoryStore.archiveOldMemories()

// src/index.ts & mcp-server.ts
archiveOldMemories(): { projectArchived: number; globalArchived: number } {
  if (this.cuoptAvailable && process.env.MEMORY_EVICTION === "cuopt") {
    return this.archiveViaCuopt();
  }
  return this.archiveViaLRU();   // existing fallback
}

Environment Variable

Variable	Default	Description
MEMORY_EVICTION	lru	lru or cuopt

Expected Improvement

For a memory store with 500 entries competing for 100 active slots:

• LRU: O(n log n), CPU-bound, suboptimal value retention
• cuOpt: O(1) GPU time (~2ms), globally optimal, pins high-value memories

Acceptance Criteria

• pip install cuopt-cu13 verified on GB10 CUDA 13 environment
• cuopt_eviction.py solves a 500-memory test case in < 100ms
• MEMORY_EVICTION=cuopt env var switches eviction policy
• LRU remains default; cuOpt is opt-in
• memory_stats output includes eviction_policy: "cuopt" when active
• Ablation test: compare LRU vs cuOpt memory value retention over 1000 operations
• Graceful fallback to LRU if cuOpt not installed

Effort: 2 weeks | Priority: P3

[AugustChaoTW]

GPU-agnostic requirement: This feature must degrade gracefully without an NVIDIA GPU. See #56 for the full compatibility contract, fallback implementation details, and CI requirements that must pass before this issue can be merged.