ZetaEvolve: Learning to Search through History-Conditioned Potential Value

Self-evolving agents have shown strong empirical performance in mathematical discovery and code optimization, where the challenge is that the search space is too large and unstructured for exhaustive exploration. However, most existing methods lack systematic modeling of self-evolution, resulting in inefficient and even redundant component designs. In this paper, we model self-evolution through the lens of Partially Observable Markov Decision Process (POMDP). We treat the contexts surrounding each search node (the current program and its information to be evolved) as history, while the node’s state, shaped dynamically by the ongoing search process, remains latent and unobservable. This perspective combines parent-node selection, prompt transformation, and child-code generation into a single sequential decision framework, and better aligns with the optimization process of self-evolution. We then develop ZetaEvolve, a search strategy that improves Predictor Upper Confidence bound applied to Trees (PUCT) with a history-conditioned mechanism tailored to partial-observation signals in self-evolving search. Empirically, ZetaEvolve outperforms strong baselines across various benchmarks and achieves faster convergence than existing SOTA methods.