UtilityMax Prompting: A Formal Framework for Multi-Objective Large Language Model Tasks

Ofir Marom

cs.CLMar 12, 2026

UtilityMax Prompting: A Formal Framework for Multi-Objective Large Language Model Tasks

Authors: Ofir Marom

Organizations: Independent Researcher

Abstract

The success of a Large Language Model (LLM) task depends heavily on its prompt. Most use-cases specify prompts using natural language, which is inherently ambiguous when multiple objectives must be simultaneously satisfied. In this paper we introduce UtilityMax Prompting, a framework that specifies tasks using formal mathematical language. We reconstruct the task as an influence diagram in which the LLM's answer is the sole decision variable. A utility function is defined over the conditional probability distributions within the diagram, and the LLM is instructed to find the answer that maximises expected utility. This constrains the LLM to reason explicitly about each component of the objective, directing its output toward a precise optimization target rather than a subjective natural language interpretation. We validate our approach on the MovieLens 1M dataset across three frontier models (Claude Sonnet 4.6, GPT-5.4, and Gemini 2.5 Pro), demonstrating consistent improvements in precision and Normalized Discounted Cumulative Gain (NDCG) over natural language baselines in a multi-objective movie recommendation task.

Figures & tables

Panel of Figure 1 — Figure 1: Influence diagram for UtilityMax Prompting under conditional independence, showing decision node $A$ , chance nodes $\{X_{1},X_{2},\ldots,X_{n}\}$ , and utility node $U$ .

Model	Prompt	Precision@10	NDCG@10
Claude Sonnet 4.6	Basic	0.418 (0.054)	0.570 (0.070)
	Harsh	0.421 (0.067)	0.559 (0.083)
	UtilityMax	0.471 (0.060)	0.664 (0.064)
GPT-5.4	Basic	0.532 (0.052)	0.739 (0.056)
	Harsh	0.518 (0.050)	0.712 (0.060)
	UtilityMax	0.578 (0.047)	0.788 (0.050)

Table 1: Precision@10 and NDCG@10 averaged over

20

users and

20

queries per user. Standard deviations are shown in parentheses.

Model	vs Basic	vs Harsh
Claude Sonnet 4.6	0.0028	0.0006
GPT-5.4	0.0068	0.0042
Gemini 2.5 Pro	0.0014	0.0032

Table 2: One-sided paired Wilcoxon signed-rank test p-values for UtilityMax vs each baseline on NDCG@10. All results are significant at the

p<0.01

level.

LLM Prompting

Large language model prompting studies how instructions, examples, context, and formats steer model behavior at inference time.

See all 429 papers

Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits
May 14, 2026Donghao Li, Chengshuai Shi, Weijuan Ou +2Multi-Armed Bandits LLM Prompting
University of Virginia, Charlottesville, VA 22904, USA · Princeton University, Princeton, NJ 08544, USA · Southern University of Science and Technology, Shenzhen, Guangdong 518055, China
Less Back-and-Forth: A Comparative Study of Structured Prompting
May 19, 2026Saurav Ghosh, Gabriella Polach, Abdou SowLLM Evaluation Structured Prompting
Washington University in St. Louis Saint Louis, Missouri, USA
LLM Routing as Reasoning: A MaxSAT View
Mar 13, 2026Son Nguyen, Xinyuan Liu, Ransalu SenanayakeLLM Routing Large Language Model-Based Recommendation
Arizona State University

May 14, 2026J/K move · Enter open · S save

Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits

Donghao Li, Chengshuai Shi, Weijuan Ou, Cong Shen+1

University of Virginia, Charlottesville, VA 22904, USA · Princeton University, Princeton, NJ 08544, USA · Southern University of Science and Technology, Shenzhen, Guangdong 518055, China

Multi-Armed Bandits LLM Prompting Automatic Prompt Optimization Prompt Optimization Combinatorial Multi-Armed Bandits

Open paper AskPDF arXiv

Prompt engineering has become central to eliciting the capabilities of large language models (LLMs). At its core lies prompt selection -- efficiently identifying the most effective prompts. However, most prior investigations overlook a key challenge: the inherently multi-faceted nature of prompt performance, which cannot be captured by a single metric. To fill this gap, we study the multi-objective prompt selection problem under two practical settings: Pareto prompt set recovery and best feasible prompt identification. Casting the problem into the pure-exploration bandits framework, we adapt provably efficient algorithms from multi-objective bandits and further introduce a novel design for best feasible arm identification in structured bandits, with theoretical guarantees on the identification error in the linear case. Extensive experiments across multiple LLMs show that the bandit-based approaches yield significant improvements over baselines, establishing a principled and efficient framework for multi-objective prompt optimization.

Abstract

LLM Prompting

Explore similar work

Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits

Less Back-and-Forth: A Comparative Study of Structured Prompting

LLM Routing as Reasoning: A MaxSAT View