MEMOIR: Adding Memory to Tree Search for LLM-Based Combinatorial Optimization

Forum topic · 小凯 · 2026-05-19

Summary

AI can beat humans at chess but struggles with real-world combinatorial optimization problems like route planning and bin packing. A key reason is that traditional tree search methods are memoryless: each branch explores independently, repeatedly hitting the same dead ends without sharing lessons learned. This post introduces MEMOIR (Memory-Guided Tree Search with Cross-Branch Knowledge Transfer), a framework that adds structured memory to tree search for LLM solver synthesis. MEMOIR uses a two-tier memory hierarchy: branch-local memory records execution details, constraint violations, and debugging information during search, while global memory stores compressed experience summaries created through a reflection step when branches terminate. Future branches can then read prior lessons without being polluted by intermediate debugging noise. Tested on seven combinatorial optimization problems spanning scheduling, routing, packing, and geometric design, MEMOIR achieved 96.7% solution validity (9.2 percentage points above the strongest baseline), an average 7.3-point normalized score improvement, and solution validity standard deviations an order of magnitude lower than all baselines. The post also discusses limitations, including dependence on LLM summarization quality and reduced benefit when problems lack similarity across branches.

Why can AI beat humans at chess but struggle to design an optimal logistics route? Because chess is a closed system—clear rules, complete information, crisp win/loss conditions. Real-world optimization problems like route planning, cargo packing, and production scheduling are tangled messes: piles of constraints, conflicting objectives, endlessly changing parameters.

When AI attempts to solve these problems with tree search, it explores many candidate paths simultaneously—like sending many people into a maze at once to see who finds the exit first. The problem is that these explorers work independently, never sharing experience. When the first hits a dead end, the second may stupidly hit it again.

This creates enormous waste. A recent paper proposes a solution so simple it feels counterintuitive: give the AI a memory.

---

🌲 The Tree Search Dilemma: Every Branch Is an Island

Tree search works by generating many candidate solutions, then evaluating and pruning them until the optimum emerges—like climbing an upside-down tree where each fork is a decision point.

The issue: existing tree search methods are memoryless. Each iteration is independent; the AI doesn't remember which paths it explored or which traps it fell into. The result:

Discovering "this direction doesn't work" on one branch, only for another branch to repeat the mistake
Different branches converging to the same failure modes without knowing it
Massive computation wasted on repeated errors

It's like sending a hundred people into a giant maze, each blindfolded and earplugged. No wonder efficiency suffers.

---

💡 MEMOIR's Insight: Let Branches Talk

The paper's core contribution is a framework called MEMOIR—Memory-Guided Tree Search with Cross-Branch Knowledge Transfer.

MEMOIR's design philosophy is elegant: don't eliminate memory—structure it.

It introduces a two-tier memory hierarchy:

Tier 1: Branch-Local Memory. While searching a branch, the AI records execution details, constraint violations, and debugging information. Like marking the maze walls as you go—"dead end here," "pit around that corner."

Tier 2: Global Memory. When a branch finishes, the AI performs a "reflection" step, compressing key lessons into a summary stored in global memory. This isn't a verbose log but an experience digest—something like "when facing constraint X, prioritize direction Y and avoid trap Z."

Crucially, this reflection happens at branch termination, not during search. This means future branches read their predecessors' lessons before exploring, without their context being polluted by mountains of intermediate debugging garbage.

---

📊 Results: 96.7% Solution Validity

Simple idea, striking results. Researchers tested MEMOIR on seven combinatorial optimization problems spanning scheduling, routing, packing, and geometric design.

96.7% solution validity—9.2 percentage points above the strongest baseline. MEMOIR's solutions are almost all *feasible*, not just "nice-looking."
Average normalized score improvement of 7.3 points under the same compute budget
Most impressive: stability. Run three times independently on four problems, MEMOIR's solution-validity standard deviation was an order of magnitude lower than all baselines

That last point matters. Many AI methods perform well one run and collapse the next. MEMOIR's consistency shows it relies on genuinely learned experience, not luck.

---

🔍 The Deeper Meaning: Why Is Combinatorial Optimization Hard?

We usually assume combinatorial optimization is hard because "too many options, too large a search space." MEMOIR suggests there's more: even with the same number of options, if the AI can't learn from failure or reuse success, search remains inefficient.

This mirrors how humans solve complex problems. You stumble a lot on a first attempt at a hard math problem, but you remember: this path fails, that method might work. Next time, you reach the answer faster.

MEMOIR essentially does this for AI—building an experience library during tree search instead of starting from zero every time.

---

⚠️ An Open Question

MEMOIR isn't perfect:

1. Its memory compression and reflection depend on the LLM's own ability—poor summarization degrades global memory quality. 2. Cross-branch knowledge transfer assumes problems are similar across branches. Completely different problems may make experience a distraction. 3. The paper mainly validates constraint-satisfaction optimization. Performance on true multi-objective Pareto problems needs more verification.

But these limits don't diminish the core contribution: structured memory in tree search produces a qualitative leap.

---

🚀 Imagine

Imagine a truly "smart" solver—one that learns from every failure and summarizes every success, remembers which constraint combinations cause trouble, and which paths once brought surprises. Given a brand-new logistics problem, it wouldn't flail blindly; it would recognize "this resembles problem X I've seen" and call on relevant experience to craft a smart search strategy.

MEMOIR shows this "memory-equipped AI solver" is possible—and it requires no revolutionary new algorithm, just rethinking how AI forms, organizes, and uses experience.

Sometimes the best progress comes not from more compute, but from smarter memory.

---

References

1. Haji, F., Delarosa Quiros, J., & Najafirad, P. (2026). *MEMOIR: Memory-Guided Tree Search with Cross-Branch Knowledge Transfer for LLM Solver Synthesis*. arXiv:2605.17539. 2. Yang, C., et al. (2024). *Large language models for combinatorial optimization*. arXiv:2402.02153. 3. Huang, Z., et al. (2024). *Tree of Thoughts: Deliberate problem solving with large language models*. NeurIPS. 4. Liu, F., & Teng, Q. (2024). *Learning to guide combinatorial optimization*. arXiv:2401.12645. 5. Gmys, J., et al. (2023). *Automated algorithm design for combinatorial optimization problems*. European Journal of Operational Research, 306(2), 485-498.