We propose to utilize a neural network to build transition proposal distributions in simulated annealing (SA), which we use for combinatorial optimization on 2D-binary grids applied to nanophotonic inverse design. To accomplish this we introduce a novel class of network architectures called template networks. A template network learns a template to construct a proposal distribution for state transitions of the stochastic process of the Metropolis algorithm, which forms the basis of SA. Motivated by NeRFs [16], each network represents a single pattern and is trained on the evaluation results of intermediate states of a single optimization run. Using this learning scheme we equip the Metropolis algorithm with the ability to utilize information about past states, intentionally violating the Markov property of memorylessness, and therefore call our method Memory Metropolis (MeMe). Moreover, the emergence of structural clusters is encouraged by incorporating layers with limited local connectivity in the template network. Viewing the optimization objective of the Metropolis algorithm as a reward maximization allows to train the template network to find high-reward template-patterns. We apply our algorithm to combinatorial optimization in nanophotonic inverse design and demonstrate that MeMe results in clustered design patterns suitable for direct optical chip fabrication which can not be found by alternative algorithms resulting in the discovery of nanophotonic devices which where inaccessible before. Code is available at https://github.com/MarlonBecker/MeMe .