# UPA: Unsupervised Prompt Agent via Tree-Based Search and Selection

arXiv: https://arxiv.org/abs/2601.23273 · HTML: https://mlsanity.com/paper/2601.23273/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 41 of its 57 references that are in the map.
- First posted on arXiv 30 Jan 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 30 of 41)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework](https://mlsanity.com/paper/2308.00352/) (2023)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [DeepSeek-V3.2: Pushing the Frontier of Open Large Language Models](https://mlsanity.com/paper/2512.02556/) (2025)
- [AGIEval: A Human-Centric Benchmark for Evaluating Foundation Models](https://mlsanity.com/paper/2304.06364/) (2023)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [Agent Laboratory: Using LLM Agents as Research Assistants](https://mlsanity.com/paper/2501.04227/) (2025)
- [Hard Prompts Made Easy: Gradient-Based Discrete Optimization for Prompt Tuning and Discovery](https://mlsanity.com/paper/2302.03668/) (2023)
- [Training Software Engineering Agents and Verifiers with SWE-Gym](https://mlsanity.com/paper/2412.21139/) (2024)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Optimization](https://mlsanity.com/paper/2310.16427/) (2023)
- [Data Interpreter: An LLM Agent For Data Science](https://mlsanity.com/paper/2402.18679/) (2024)
- [Take a Step Back: Evoking Reasoning via Abstraction in Large Language Models](https://mlsanity.com/paper/2310.06117/) (2023)
- [Rephrase and Respond: Let Large Language Models Ask Better Questions for Themselves](https://mlsanity.com/paper/2311.04205/) (2023)
- [Code Generation with AlphaCodium: From Prompt Engineering to Flow Engineering](https://mlsanity.com/paper/2401.08500/) (2024)
- [ChartInsights: Evaluating Multimodal Large Language Models for Low-Level Chart Question Answering](https://mlsanity.com/paper/2405.07001/) (2024)
- [Beyond Chain-of-Thought: A Survey of Chain-of-X Paradigms for LLMs](https://mlsanity.com/paper/2404.15676/) (2024)
- [Self-Supervised Prompt Optimization](https://mlsanity.com/paper/2502.06855/) (2025)
- [Prompt Optimization with Human Feedback](https://mlsanity.com/paper/2405.17346/) (2024)
- [PRompt Optimization in Multi-Step Tasks (PROMST): Integrating Human Feedback and Heuristic-based Sampling](https://mlsanity.com/paper/2402.08702/) (2024)

## Built on by (most cited first, 1 of 1)

- [Self-Supervised Skill Optimization](https://mlsanity.com/paper/2607.28777/) (2026)

## Abstract (arXiv)

Prompt agents have recently emerged as a promising paradigm for automated prompt optimization, framing prompt discovery as a sequential decision-making problem over a structured prompt space. While this formulation enables the use of advanced planning algorithms, these methods typically assume access to supervised reward signals, which are often unavailable in practical scenarios. In this work, we propose UPA, an Unsupervised Prompt Agent that realizes structured search and selection without relying on ground-truth (GT) rewards. Specifically, during search, UPA iteratively constructs an evolving tree structure to navigate the prompt space, guided by fine-grained and position-debiased pairwise comparisons from Large Language Models (LLMs). Crucially, as these local comparisons do not inherently yield a consistent global scale, we decouple systematic prompt exploration from final selection, introducing a two-stage framework grounded in the Bradley-Terry-Luce (BTL) model. This framework first performs path-wise Bayesian aggregation of local comparisons to filter candidates under uncertainty, followed by global tournament-style comparisons to infer latent prompt quality and identify the optimal prompt. Experiments across multiple tasks demonstrate that UPA consistently outperforms existing prompt optimization methods, showing that agent-style optimization can remain highly effective even in unsupervised settings.