Towards Optimizing with Large Language Models

Pei-Fu Guo, Ying-Hsuan Chen, Yun-Da Tsai, Shou-De Lin

TL;DR

This paper investigates whether Large Language Models (LLMs) can serve as iterative numerical and combinatorial optimizers across four distinct paradigms: Gradient Descent, Hill Climbing, Grid Search, and Black-Box Optimization. By designing three novel, scale-insensitive evaluation metrics, the authors find that LLMs excel at small-scale optimization—sometimes even matching or outperforming ground-truth algorithmic steps—primarily driven by pretrained mathematical reasoning rather than in-context heuristics.

What Problem Does This Paper Address?

While LLMs have shown impressive reasoning in single-turn question-answering and coding benchmarks, their ability to act as iterative, interactive search algorithms remains underexplored. Optimization requires evaluating candidate solutions, updating parameters based on past trial feedback, and escaping local minima over sequential turns.

Rather than attempting to beat state-of-the-art numerical solvers, the authors seek to understand:

  • Can conversational LLMs systematically execute standard optimization algorithms purely via natural-language prompting?
  • Can they perform black-box optimization on unknown loss functions without explicit update rules?
  • How does performance degrade as problem dimensionality and search spaces scale?

Methods

The authors employ an interactive conversational prompting setup (using Chat completions with Chain-of-Thought reasoning). The LLM first specifies an objective function (Mean Squared Error over sample targets), then enters an iterative feedback loop:

  1. Candidate Generation: The LLM proposes candidate updates based on the conversation history and algorithm instructions.
  2. Evaluation Feedback: The environment computes the true loss of the proposed parameters and appends the result to the prompt history for the next iteration.

They evaluate four optimization tasks:

  • Gradient Descent: Continuous parameter space; the LLM calculates derivatives and applies an explicit learning rate ($\alpha = 0.1$).
  • Hill Climbing: Discrete local search; the LLM generates $\pm 1$ coordinate neighbors and selects the best candidate.
  • Grid Search: Discrete exhaustive search over bounded integer ranges.
  • Black-Box Optimization: Zero-shot optimization where the model receives past evaluated $(x, f(x))$ pairs with no formula or search rules and must discover improved candidates.

To evaluate progress reliably across diverse scales, they introduce three ratio-based metrics:

  • Goal Metric ($G$): Normalized relative loss reduction from the initial starting point ($\frac{\text{loss}_{\text{init}} - \text{loss}_i}{\text{loss}_{\text{init}}}$).
  • Policy Metric ($P$): Normalized divergence between LLM steps and theoretical ground-truth updates ($\frac{\text{loss}_{\text{LLM}} - \text{loss}_{\text{truth}}}{\text{loss}_{\text{truth}}}$). Values near zero mean strict algorithmic fidelity; negative values indicate outperforming the ground truth.
  • Uncertainty Metric ($U$): Output variance across independent trials under identical starting conditions (sampling at temperature $T = 0.8$).

Datasets

The authors benchmark using synthetic Mean Squared Error (MSE) minimization tasks across five dimensionalities:

  • Parameter dimensions: $d \in \{3, 6, 12, 24, 48\}$.
  • Coordinate bounds: $x \in [0, 10]^d$.
  • Ground truth baselines: Exactly calculated analytical steps (e.g., standard gradient updates or exhaustive grid evaluations) for each synthetic instance.

Key Insights and Ideas

  • Pretrained Knowledge Trumps In-Context Heuristics: LLMs performed best on Gradient Descent (hovering close to ground-truth steps) but struggled heavily on Hill Climbing. The model readily leverages mathematical concepts embedded during pretraining, but struggles to strictly adhere to custom, multi-step heuristic rules passed in-context.
  • Higher Uncertainty Correlates with Better Optimization: In low-dimensional problems ($d=3, 6$), the uncertainty metric is high, indicating the model explores a wider, richer solution space before converging. As dimensions scale ($d \ge 12$), uncertainty drops, but so does optimization performance—the model becomes rigidly constrained and fails to explore effectively.
  • LLMs as Autonomous Black-Box Searchers: Even without explicit instructions, both GPT-3.5 and GPT-4 showed natural capability to infer underlying loss trends and propose improving points in small dimensions ($d=3, 6$).
  • Self-Consistency Divergence: Applying self-consistency (voting over 5 sampled paths) significantly boosted stability and narrowed confidence bounds for GPT-4 in Gradient Descent, but failed to reliably improve GPT-3.5.

Key Results

  • Gradient Descent Superiority: GPT-3.5 achieved a Policy Metric near zero across several configurations and achieved negative Policy Metrics at $d=6$, meaning it converged to lower loss values faster than standard fixed-step gradient descent.
  • Black-Box Performance: GPT-4 outperformed GPT-3.5 by a slight margin in stability and goal reduction for $d \in \{3, 6\}$, but both models degraded sharply when scaled to $d=24$ and $d=48$.
  • Heuristic Struggle: Hill Climbing policy metrics significantly exceeded zero across all dimensions, reflecting severe failure in following neighbor generation and selection rules.

Limitations and Future Work

  • Curse of Dimensionality: Performance sharply collapses beyond $d=12$, underscoring that LLMs cannot handle medium-to-large parameter spaces without external dimension reduction or tool integration.
  • Numerical Sensitivity and Token Biases: LLMs exhibit inherent biases toward specific numbers and digit patterns, making them sensitive to initialization points and prompting phrasing.
  • Future Directions: The authors propose using LLMs as hybrid meta-optimizers—agents that dynamically swap between optimization tools (e.g., switching from exploratory search to gradient-based local descent via natural language) based on trajectory states.

Summary updated

Abstract

In this study, we evaluate the optimization capabilities of Large Language Models (LLMs) across diverse mathematical and combinatorial optimization tasks, where each task is described in natural language. These tasks require LLM to iteratively generate and evaluate solutions through interactive prompting, where each optimization step involves generating new solutions based on past results and then pass to subsequent iterations. We demonstrate that LLMs can perform various optimization algorithms and act as effective black-box optimizer, capable of intelligently optimizing unknown functions. We also introduce three simple yet informative metrics to evaluate optimization performance, applicable across diverse tasks and less sensitive to test sample variations. Our findings reveal that LLMs excel at optimizing small-scale problems with limited data and their performance is significantly affected by dimension of problem and values, highlighting the need for further research in LLM optimization.
BibTeX
@inproceedings{guo2024towards,
  author = {Pei-Fu Guo and Ying-Hsuan Chen and Yun-Da Tsai and Shou-De Lin},
  title = {{Towards Optimizing with Large Language Models}},
  booktitle = {KiL @ KDD},
  year = {2024},
}
Figure