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

This paper introduces UtilityMax Prompting, a formal framework that replaces ambiguous natural language instructions with mathematical influence diagrams and utility functions to guide Large Language Models toward explicitly maximizing expected utility, thereby achieving superior multi-objective optimization performance in tasks like movie recommendation compared to traditional prompting methods.

The Gist

Imagine you are hiring a brilliant but slightly literal-minded chef (the AI) to cook a meal for a very picky guest. You want the dish to be delicious, healthy, and cheap.

The Problem: The "Vague Order"

If you tell the chef in normal language, "Make me something delicious, healthy, and cheap," the chef has to guess what you mean.

• Does "cheap" mean $5 or$50?
• Does "healthy" mean no sugar, or just lots of veggies?
• Does "delicious" mean spicy or sweet?

The chef might guess wrong. They might make a $50 steak (delicious, but not cheap) or a bowl of plain broccoli (healthy and cheap, but not delicious). This is what happens when we use standard "natural language" prompts for complex AI tasks. The instructions are too fuzzy, and the AI has to guess how to balance the competing goals.

The Solution: The "Mathematical Recipe" (UtilityMax)

The paper introduces a new way to talk to the AI called UtilityMax Prompting. Instead of giving a vague order, you give the AI a mathematical formula to follow.

Think of it like this: Instead of saying "Make a good meal," you hand the chef a calculator and say:

"Your goal is to maximize this number: (Taste Score) × (Health Score) × (Price Score)."

Now, the chef can't just guess. They have to:

1. Look at every possible ingredient.
2. Calculate the "Taste," "Health," and "Price" for each one.
3. Multiply those numbers together.
4. Pick the ingredient that gives the highest total number.

This forces the AI to stop guessing and start calculating. It has to explicitly think about how much "health" it's getting versus how much "price" it's saving, rather than just hoping the vibe feels right.

How It Works (The "Influence Diagram")

The paper uses a concept called an Influence Diagram. Imagine a flowchart:

• The Decision: The AI's answer (the dish).
• The Variables: The different goals (Taste, Health, Price).
• The Utility: The final score (the result of multiplying the variables).

The AI is told: "You are the decision-maker. Your job is to find the answer that makes the final Utility number as big as possible."

The Movie Experiment

To test this, the researchers tried to get AI to recommend movies.

• The Goal: Recommend movies that are Comedies, Romances, and have a High Rating.
• The Old Way (Natural Language): "Recommend funny, romantic movies that are good."
  • Result: The AI sometimes recommended a sad drama because it thought "romantic" was more important than "funny," or it guessed the rating wrong.
• The New Way (UtilityMax): The AI was told to calculate: (Probability it's a Comedy) × (Probability it's a Romance) × (Predicted Rating).
  • Result: The AI became much better at finding movies that hit all three targets perfectly.

The Results

They tested this on three of the smartest AI models available (Claude, GPT, and Gemini).

• The Finding: The "Mathematical Recipe" (UtilityMax) consistently beat the "Vague Order" (Natural Language).
• Why? Even the smartest AIs get confused by words like "medium risk" or "very funny." But they are very good at math. If you give them a clear formula, they follow it perfectly.

The Catch

There is one rule: The AI has to be smart enough to guess the numbers correctly.

• If the AI is bad at guessing how "funny" a movie is, the math won't help.
• But for the current top-tier AIs, they are good enough at guessing these probabilities that the math makes them significantly better at their jobs.

In a Nutshell

UtilityMax Prompting is like switching from giving a human a vague wish ("I want a great vacation") to giving them a spreadsheet with a clear formula ("Maximize: Sun Hours + Beach Quality - Cost"). It stops the AI from guessing what you want and forces it to solve a math problem to find the perfect answer.

Technical Summary

1. Problem Statement

Current Large Language Model (LLM) prompting techniques (e.g., Chain-of-Thought, Program of Thoughts) and optimization methods (e.g., Optimization by Prompting) primarily rely on natural language to specify task objectives. While effective for single-objective tasks, natural language becomes inherently ambiguous when multiple, often competing, objectives must be satisfied simultaneously.

• The Challenge: In multi-objective scenarios (e.g., "maximize profit subject to medium risk"), terms like "medium" are subjective. The LLM must interpret these vague constraints, leading to inconsistent reasoning and suboptimal trade-offs between objectives.
• The Gap: Existing methods do not provide a mechanism to eliminate this ambiguity without requiring external exemplars (few-shot) or expensive scoring functions for iterative optimization.

2. Methodology: UtilityMax Prompting

The authors propose UtilityMax Prompting, a zero-shot framework that replaces natural language objectives with a formal mathematical specification. The core idea is to model the task as an influence diagram where the LLM acts as a decision-maker maximizing expected utility.

A. The Influence Diagram Framework

The task is reconstructed using the following components:

• Knowledge ($K$): The LLM's internal parameters and external context.
• Decision Node ($A$): The space of all possible answers the LLM can generate given $K$.
• Chance Nodes ($X_1, ..., X_n$): Random variables representing the components of the objective (e.g., genre match, predicted score).
• Utility Node ($U$): A multiplicative utility function defined over the chance nodes: $U(X_1, ..., X_n) = \prod f_i(X_i)$.

The Objective: The LLM is instructed to find the answer $a^*$ that maximizes the expected utility:
$$a^* = \arg\max_{a \in A} E[U | A=a]$$

Due to the conditional independence of chance nodes given the decision $A$, the expected utility factorizes:
$$E[U | A] = \prod_{i=1}^{n} E[f_i(X_i) | A]$$

B. Handling Dependencies (Binary Chance Nodes)

The framework addresses a special case where chance nodes are binary and dependent. By introducing a gating mechanism, the authors relax the strict conditional independence assumption. If a child node $X_i$ depends on parents $pa(X_i)$, the node is only active if all parents are active ($X_j=1$). This allows the expected utility to be calculated as a product of conditional probabilities without requiring full joint distribution modeling, preserving tractability.

C. The Prompting Template

The framework utilizes a specific prompt structure that instructs the LLM to:

1. Define the knowledge base $K$.
2. Identify random variables ($X_1, X_2, ...$) representing objective components.
3. Generate candidate answers.
4. Explicitly estimate the expected value (or probability) for each component for every candidate.
5. Compute the composite utility $O(a)$ and select the answer maximizing it.

3. Experimental Setup

• Dataset: MovieLens 1M.
• Task: Multi-objective movie recommendation. Given a user's history, recommend the top 10 movies from a test set.
• Constraints: The user is interested in Comedy AND Romance genres, and the movies must have a high predicted rating.
• Models Tested: Three frontier models:
  • Claude Sonnet 4.6
  • GPT-5.4
  • Gemini 2.5 Pro
• Baselines:
  1. Basic: Natural language prompt ("User likes comedy and romance").
  2. Harsh: Strict natural language prompt ("Only suggest comedy and romance; do not suggest others").
  3. UtilityMax: Formal mathematical prompt maximizing $E[\text{Score}] \times P(\text{Comedy}) \times P(\text{Romance})$.
• Metrics: Precision@10 and Normalized Discounted Cumulative Gain (NDCG@10).

4. Key Results

UtilityMax demonstrated consistent superiority over natural language baselines across all three models and both metrics.

• Performance Gains (Claude Sonnet 4.6):
  • Precision@10: +12.7% over Basic; +11.9% over Harsh.
  • NDCG@10: +16.5% over Basic; +18.8% over Harsh.
• Performance Gains (GPT-5.4):
  • Despite GPT-5.4 achieving the highest absolute scores (likely due to training data overlap), UtilityMax still outperformed both baselines significantly.
• Statistical Significance:
  • One-sided paired Wilcoxon signed-rank tests confirmed that UtilityMax significantly outperformed both baselines ($p < 0.01$) across all models.
• Observation on Baselines: The "Harsh" natural language prompt did not consistently outperform the "Basic" prompt, suggesting that simply increasing the forcefulness of natural language instructions does not resolve the ambiguity of multi-objective weighting.

5. Key Contributions

1. Formal Framework: Introduction of UtilityMax, a zero-shot method that converts multi-objective LLM tasks into formal optimization problems using influence diagrams.
2. Ambiguity Elimination: The framework forces the LLM to reason explicitly about each objective component (e.g., calculating specific probabilities) rather than relying on subjective natural language interpretation.
3. Tractable Dependency Handling: A novel gating mechanism that allows for dependencies between binary chance nodes while maintaining computational tractability.
4. Empirical Validation: Comprehensive validation across three state-of-the-art models showing that formal specification yields better alignment with complex, multi-constraint goals than natural language prompting.

6. Significance and Future Directions

• Significance: This work challenges the dominance of natural language in prompt engineering for complex tasks. It demonstrates that formal mathematical specification acts as a stronger signal for LLMs, guiding them toward precise optimization targets without needing external scoring functions or few-shot examples.
• Limitations & Future Work:
  • Model Capability: The framework relies on the LLM's ability to produce well-calibrated probability estimates. Weaker models may not benefit or could perform worse.
  • Automation: Future research should focus on automating the extraction of variables and the construction of the UtilityMax prompt from natural language descriptions.
  • Complex Dependencies: Extending the framework to handle more complex dependencies between chance nodes beyond the current gating mechanism.

In conclusion, UtilityMax Prompting offers a robust, mathematically grounded alternative to traditional prompting, significantly improving LLM performance in multi-objective scenarios by removing the inherent ambiguity of natural language instructions.