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:
- Candidate Generation: The LLM proposes candidate updates based on the conversation history and algorithm instructions.
- 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