Research map / Multi-agent systems and games / LLM agents

MOTIF: Multi-strategy Optimization via Turn-based Interactive Framework

AAAI 2026 · Multi-agent systems and games › LLM agents · approach: Agent data synthesis and behavior studies · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes MOTIF, a Monte Carlo Tree Search framework where two gpt-4o-mini agents take turns improving multiple interdependent solver strategies for combinatorial optimization, with competitive operators and dynamic baselines.

Problem

Automatically designing multiple interdependent algorithmic components (strategies) of solvers for NP-hard combinatorial optimization problems, which prior LLM-based automatic heuristic design methods restrict to a single heuristic function.

Approach

Formulates solver design as multi-strategy optimization and uses a two-player competitive MCTS (counter, learning, innovation operators; Q-value mixing absolute and relative gains; dynamic baselines) in which two LLM agents alternately revise one component while seeing the opponent's history, followed by system-aware refinement with full solver visibility.

Key results

• On GLS for TSP, MOTIF achieves 0.5577% gap at TSP500 versus 0.5611% for MCTS-AHD and 2.4593% for HSEvo (3 runs).
• For the deconstruction-then-repair framework, jointly optimizing all three strategies gives 10.98% improvement on CVRP50 and 23.94% on BPP100 over the human baseline, versus at most 6.34% and 12.70% for single strategies.
• Innovation operator achieves 97% success rate versus 93% for counter and 92% for learning.

Surprising findings

• Single-strategy MOTIF gains on TSP over strong LLM baselines are small (e.g., 0.0007% vs 0.0012% for EoH at TSP100), with differences largely within standard deviation.

Limitations

• Uses a weak, inexpensive model (gpt-4o-mini) chosen for cost, not stronger coders
• Single-strategy TSP gains over baselines are marginal and within variance
• Evaluated on a limited set of algorithm frameworks and small instance sizes

Experimental setup

Datasets: TSP instances (training TSP50, test TSP100) CVRP instances BPP instances MKP instances OP instances

Benchmarks: TSP CVRP BPP ACO on five COP domains GLS on TSP50-500

Metrics: optimality gap (%) percentage improvement over human-designed baseline success rate novelty score silhouette score

Baselines: EoH ReEvo HSEvo MCTS-AHD

Builds on: MCTS-AHD EoH ReEvo HSEvo Chain-of-thought prompting

Closest papers by meaning

• PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (ICML 2026 · similarity 0.88)
• CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization (AAAI 2026 · similarity 0.87)
• Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.87)
• $\texttt{STRCMP}$: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization (NeurIPS 2025 · similarity 0.86)
• ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution (NeurIPS 2024 · similarity 0.85)
• AgentSwift: Efficient LLM Agent Design via Value-Guided Hierarchical Search (AAAI 2026 · similarity 0.85)