Towards Optimizing with Large Language Model
题目
用大语言模型进行优化
论文地址：https://arxiv.org/abs/2310.05204
摘要
在这项研究中，我们评估了大型语言模型(LLM)在各种数学和组合优化任务中的优化能力，其中每个任务都用自然语言描述。这些任务要求LLM通过交互式提示迭代地生成和评估解决方案，其中每个优化步骤都涉及基于过去的结果生成新的解决方案，然后传递给后续迭代。我们证明了LLM可以执行各种优化算法，并充当有效的黑盒优化器，能够智能地优化未知函数。我们还引入了三个简单但信息丰富的指标来评估优化性能，适用于不同的任务，对测试样本的变化不太敏感。我们的发现揭示了LLM在优化有限数据的小规模问题方面的优势，并且它们的性能受到问题的维度和价值的显著影响，突出了LLM优化的进一步研究的需要。
引言
大型语言模型在各种基于自然语言的任务中表现出非凡的推理能力[7]。然而，他们的潜力超出了多项选择题或单项答题。这项工作探索了LLMs在不同任务和问题维度上的优化效果。优化包括迭代地生成和评估解决方案，以改进给定的目标函数。我们的研究评估了LLM在交互式优化中的性能，其中每一步都基于以前的解决方案及其价值生成新的解决方案。
我们用四种不同类型的优化算法进行研究:梯度下降、爬山、网格搜索和黑盒优化。为了提供对LLM性能的全面评估，我们引入了三个不同的指标。这些指标提供了任务性能的多方面视图，适用于广泛的优化任务，降低了对样本变化的敏感性。
我们的发现表明LLM显示出令人印象深刻的优化能力，尤其是在小规模问题中。然而，它们的性能明显受到样本大小和值范围等因素的影响。这些观察强调了在为LLM定制的优化任务领域内进行进一步研究的需要。重要的是要注意，我们的工作并不旨在超越数学优化或组合优化问题的最先进的优化算法。相反，我们的目标展示LLM在这些优化领域中的潜力，并找出这些设置中的限制。
我们的贡献总结如下:
- 探索LLMs在数学和组合优化场景中的潜力。
- 引入三种新的指标来评估LLM在优化任务中的表现。
- 使用我们的指标深入研究影响LLM绩效的因素，特别强调问题维度和任务类型的影响。
本文的其余部分结构如下。在第2节中，我们介绍了解决优化挑战的LLM的初步工作。在第3节中，我们在案例研究中定义了4种优化算法。在第4节中，我们论证了具有迭代激励策略的LLM作为优化器的功能。在第5节中，我们给出了我们设计的三个指标，用于评估LLM在执行优化任务时的整体性能。第6节详细介绍了我们的实验结果，展示了使用LLM作为优化器的有效性。在第7节中，我们综合了实验中值得注意的观察结果和讨论要点。最后，第8节对本文进行了总结和归纳。
相关工作
在各种优化场景中，大型语言模型(LLM)的利用对于能够处理复杂和信息丰富的基于文本的反馈的优化算法或代理系统的开发已经变得不可或缺。在本节中，我们总结了三个重要的相关工作，这些工作利用LLM来解决优化和强化学习的挑战。这些作品展示了LLM在解决不同领域的优化和学习挑战方面的适应性和有效性。
通过提示进行优化(OPRO) [8] OPRO通过在自然语言提示中描述优化任务，将LLM作为多功能优化器。它从这些提示中迭代地生成和评估解决方案，在诸如线性回归和旅行推销员问题等任务中表现出卓越的性能。在具有挑战性的任务上，OPRO比人类设计的提示高出50%。
Reflexion [5] Reflexion引入了一个新颖的框架来训练语言代理，它依赖于语言反馈而不是传统的强化学习。该框架提供了出色的结果，在编码任务上拥有令人瞩目的91%的pass@1准确率，比以前的最先进模型提高了11%。Reflexion的成功强调了语言反馈作为一种强大的培训机制的潜力。
EvoPrompt [2] EvoPrompt通过将LLM与进化算法相结合，实现了提示优化的自动化。这种自动化的过程比人工设计的提示高出25%，比现有的自动提示生成方法高出14%。EvoPrompt的成功凸显了大型语言模型和传统算法之间的关系，展示了通过这种协同融合增强问题解决能力的潜力。
问题设置
我们设计了四个优化任务，要求模型用算法搜索参数的最优值。这些任务包括梯度下降、爬山、网格搜索和黑盒优化，每一个都代表独特的优化领域:基于梯度、元启发式、决策理论和贝叶斯。就参数类型而言，网格搜索和爬山涉及离散搜索空间，而梯度下降和黑盒优化处理连续搜索空间。以下是每个优化任务的详细信息。
梯度下降评估模型在高级计算中的熟练程度及其对梯度下降原则的掌握。我们指示LLM根据他们定义的损失函数进行传统的梯度下降优化过程。LLM需要计算梯度，并使用梯度信息和给定的学习率更新参数。
爬山评估LLM遵守他们以前没有见过的自定义预定义规则的能力。LLM从一个初始解决方案开始，通过进行小的增量更改来迭代地探索附近的解决方案。在我们的任务中，通过选择解决方案中的特定元素并每次增加或减少1来生成相邻解决方案。随后，选择具有最小损失的邻居解作为新的解，并传递给下一次迭代。
网格搜索评估LLM进行彻底搜索和在预定义的搜索空间内找到最优解的能力。LLM的任务是生成所有网格点，并根据给定的损失函数系统地搜索导致最低损失的点。
黑盒优化评估LLM在抽象的问题解决环境中做出明智决策和优化的能力。我们将LLM视为试图拟合未知损失函数的黑盒。我们为LLM提供了一组有限的解决方案，每个解决方案都与其各自的真实损失值配对。LLM的目标是在每次迭代中发现比现有解决方案损失更低的新解决方案。
方法
在这一节中，我们展示了LLM如何在迭代提示的指导下，有效地发挥优化器的作用，类似于各种优化算法。为了系统地导航搜索空间，我们引入了一个迭代提示框架，使LLM能够通过迭代过程在搜索空间内逐步实现更好的解决方案。
我们应用了思路链和迭代提示作为我们的提示方法。LLM将通过推理完成每一步作为中间输出的思想。在这些任务(优化算法)的每一个中，LLM最初被要求基于给定的样本公式化损失函数。然后，每次优化迭代由两个步骤组成:(1)基于算法指令和过去的搜索结果生成新解(2)计算新解的损失并将结果添加到下一次迭代的提示中。
图1:我们的提示策略概述。(1)LLM基于给定样本公式化损失函数。(2)给定算法指令和过去的结果，LLM生成新的解。(3)计算新解的损失，并将解-分数对添加到下一次迭代的提示中。(4)重复第二步和第三步，直到满足停止标准。
我们不断重复这两个步骤，直到满足停止标准。图1显示了LLM如何在交互式设置中执行优化的概述。为了创建一个交互式的环境，我们利用了GPTs的聊天模式，其中整个对话历史作为提示。这允许LLM保留过去搜索结果和推理路径的记忆。随着每次迭代，新的指令被附加到正在进行的对话记录中。如果对话超过了令牌限制，前面的部分将被删除。
评估
我们为LLM能力的综合评估设计了三个新颖的度量标准。在本节中，我们将解释每个指标的设计和目标。这些指标提供了跨不同任务评估LLM性能的通用性，使得并发评估更加容易。他们依赖比率指标，而不是差异，这使得他们对样本变化不太敏感。
目标度量
目标度量评估LLM执行优化的效率。它提供了LLM对最小化损失函数值的贡献程度的定量测量。换句话说，确保最终溶液损失低于初始溶液。我们将测试样品𝑗的𝑔𝑜𝑎𝑙 𝑚𝑒𝑡𝑟𝑖𝑐定义为:
其中𝑙𝑜𝑠𝑠𝐿𝐿𝑀,𝑖𝑛𝑖𝑡是样品𝑗的初始溶液损失，𝑙𝑜𝑠𝑠𝐿𝐿𝑀,𝑖是试验𝑖的LLM输出损失，𝑁是每个样品的试验次数。度量值越高，优化进度越大。目标度量在我们的评估框架中起着至关重要的作用，特别是在缺乏基本事实的场景中，比如黑盒优化场景。
策略度量
策略度量评估最终模型输出和实际情况之间的一致程度。除了由𝑔𝑜𝑎𝑙 𝑚𝑒𝑡𝑟𝑖𝑐衡量的自我改进，评估LLM以与我们的真实模型算法一致的方式运行的能力也是至关重要的。这一指标作为LLM在遵循特定任务指令方面的熟练程度的指标。我们将测试样品𝑗的𝑝𝑜𝑙𝑖𝑐𝑦 𝑚𝑒𝑡𝑟𝑖𝑐定义为:
其中𝑙𝑜𝑠𝑠𝐿𝐿𝑀,𝑖是试验𝑖的LLM输出损失，𝑙𝑜𝑠𝑠𝑡𝑟𝑢𝑡ℎ是样本𝑗的地面实况，𝑁是试验次数。因为策略度量测量的是基础事实和LLM输出之间的差异，所以较低的策略度量值表示LLM的操作与规定的指导方针更加有效地一致。当值为负时，意味着LLM的性能超过了地面真实。
不确定性度量
不确定性度量量化了相同条件下LLM解决方案的可变性。稳定性是优化任务中的一个重要特征。我们希望LLM在涉及相同样品的每次试验中产生相同的结果，即使是在温度高于零度的条件下。我们将测试样品𝑗的𝑢𝑛𝑐𝑒𝑟𝑡𝑎𝑖𝑛𝑡𝑦 𝑚𝑒𝑡𝑟𝑖𝑐定义为:
其中，𝑙𝑜𝑠𝑠𝐿𝐿𝑀,𝑖是第I次试验的LLM输出，𝑙𝑜𝑠𝑠𝐿𝐿𝑀是试验输出的平均值，𝑁是试验次数。一个稳定的LLM更值得信赖，因为它需要一致和可重复的结果。在我们的例子中，如果语言模型真正理解了问题的上下文，那么在同一样本的每次试验中，最终的最优输出应该是相同的。
实验
这一部分提供了我们的实验配置的细节，并强调了实验的结果。第6.1小节概述了为所有优化任务生成合成数据集的过程，而第6.2小节阐明了我们实验的详细设置。最后，第6.3小节简要总结了我们实验的结果。
数据集
在实验中，我们用从集合{3，6，12，24，48}中选择的𝑑值创建五个数据集，并在每个数据集中生成属于[0，10] 𝑑的实例，以检查对代表优化问题的维度的参数数量的敏感性。
例如，𝑑 = 3表示损失函数中有3个变量，并且这个优化问题的维数是3。然后，我们将每个实例应用于损失函数，并找到每个参数搜索任务的真实解。这些经过验证的解决方案，加上它们的相关损失，不仅作为任务的基础事实，而且作为关键的基准，在随后的分析中系统地评估和比较由LLM导出的解决方案。
详细设置
在我们的实验中，我们将LLM温度设置为0.8，重置为默认值。我们对数据集中的每个实例执行了5次重复测试，LLM在每次重复中进行10次参数搜索迭代。我们排除了过度有偏见的结果，以防止我们的指标被少数表现不佳的测试结果扭曲。所有实验都采用GPT涡轮增压3.5 '0613 '版本作为语言模型。
主要结果
我们总结了我们实验的结果，并随后检查了在所有实验中观察到的共同趋势。在每个图中，x轴显示优化问题的维度。在目标度量和策略度量图中，y轴表示相应任务的平均度量值，而浅色阴影区域表示度量的置信区间，表示为[𝑣𝑎𝑙𝑢𝑒𝑠𝑡𝑑，𝑣𝑎𝑙𝑢𝑒+𝑠𝑡𝑑].]至于不确定性度量图，y轴显示了不确定性度量值，对应于LLM最终解决方案损失的标准偏差。值得注意的是，目标度量图排除了非迭代网格搜索任务，因为它的非迭代性质，而策略度量图省略了黑盒任务，因为无法实现基本事实。
LLM在小规模问题中表现出强大的优化能力。我们的实验测试了LLMs的综合优化能力。观察图2，GPT涡轮增压3.5展示了各种情况下相当大的优化能力。令人印象深刻的是，在梯度下降任务中，GPT涡轮3.5甚至超过了地面真相，特别是在样本维数等于6的情况下。同样令人惊讶的是，该模型在网格搜索任务中取得了令人满意的结果，因为它必须计算大量的网格点，这些网格点随着问题规模的扩大而呈指数增长。该模型在爬山任务中面临挑战，从一个显著超过零的政策指标中可以明显看出。这表明，与其他任务相比，元启发式算法可能给LLM带来更大的困难。
LLM显示出作为黑盒优化器的潜力。黑盒实验中的良好性能表明，LLM可以用作优化器，而无需给出任何算法指令。从图3中，我们可以看到，当问题的维数是3时，GPT-turbo-3.5表现显著，而当维数是3和6时，GPT-4表现优异。有趣的是，随着维度的增加，两种模型的性能都逐渐减弱。最终，GPT 4以微弱优势击败了GPT涡轮3.5优化和稳定。
LLM在梯度下降中表现出很强的性能。梯度下降实验测试模型在高级计算方面的熟练程度和对数学原理的掌握。图4通过揭示一个始终徘徊在零附近的策略度量强调了这一点，表明LLM的输出和实际情况之间存在显著的一致性。尽管随着样本量的增加，目标指标有所下降，但政策指标始终较低且稳定的值强调了一个事实，即GPT在梯度下降任务中的表现几乎与真实模型相当。
分析和讨论
在这一部分中，我们巩固了从我们的实验结果中得出的几个重要见解，并对它们进行了分析。预先训练的知识决定了LLM的优化能力。在LLMs执行的所有优化任务中，梯度下降是最主要的表现，而爬山带来了更大的挑战。这两个任务之间的主要区别在于，爬山是一种具有更多用户特定参数的启发式算法，而梯度下降是一种更依赖于数学原理的优化算法。
图3:目标度量反映了LLMs作为黑盒优化器的性能，显示了较小维度实例的强大性能。
图2:目标度量和策略度量从正值徘徊到接近零，表明LLM的输出和实际情况之间的实质性优化能力和一致性。
这表明LLM优化能力主要来自存储在模型参数中的预先训练的知识，而不是来自用户提供的上下文知识。我们的发现与之前的研究一致[1，3，9],表明语言模型通常优先考虑他们先前的知识而不是新的上下文。实现对先验知识和上下文知识的平衡关注对于进一步研究以提高语言模型的优化能力是至关重要的。
LLM是潜在的混合优化器。在大多数任务和数据集上占主导地位的正目标度量值表明了LLMs的优化能力。这突出了它们跨不同问题空间进行优化的多功能能力，潜在地允许在一个单一任务。这种转换可以帮助LLM更好地探索解决方案空间，并避免陷入局部最优。这是LLM在优化方面的一个显著优势，因为它们可以在迭代过程中通过简单的自然语言提示轻松地改变方法。此外，LLM可以充当使用不同算法作为工具(动作)的代理(世界模型)，通过评估从过去到现在(状态)的优化路径来切换方法。
图4:策略指标中的低值和目标指标中的高正值表明LLM在梯度下降任务中的稳健性能。
这种适应性强调了LLMs通过动态方法选择和战略性问题解决来增强优化过程的潜力。LLM在小规模问题中拥有更丰富的解空间。在我们的实验中，当样本具有较小的维度时，我们观察到高不确定性度量值以及策略和目标度量中的显著变化。有趣的是，LLM倾向于在更小的维度实例中更有效地执行，这表明了更高的不确定性和更好的性能之间的相关性。
各种任务和模型之间的这种一致模式表明，在处理小规模问题时，LLM具有更丰富的解决方案空间。扩展的解决方案空间导致更高的不确定性，为LLM提供了更广泛的解决方案供探索。这突出了数据预处理中降维对于LLMs有效优化的重要性。图2和图5都强调了不确定性的模式，其中不确定性最初上升，然后逐渐下降。
图5:随着实例维度的增长，不确定性度量先是上升，然后下降，这表明LLM对于小规模问题可能有更丰富的样本空间，在任务和模型之间是一致的。
LLM对数值很敏感。值得考虑的是，上述结果可能会受到测试样本生成中固有随机性的影响。先前的研究表明，LLM可能会表现出对特定数字、单词和符号的偏好[4]，这可能会在他们的回答中引入一定程度的偏差。鉴于LLM对输入提示的高度敏感性，初始起点和提供的数据会对其输出产生重大影响。本质上，在解释基于LLM的实验结果时，应该仔细考虑指令描述和数据初始化的影响，以确保更准确地评估它们的性能。
自我一致性提示提高了稳定性。在GradientDescent任务中，我们采用自洽技术[6]，其中我们对每次迭代进行五次重复，并选择出现频率最高的解决方案。从图6中，我们可以看到GPT协议-4的性能大幅提高，策略指标和目标指标的置信区间变窄，这表明稳定性和可靠性有所提高。尽管如此，这种方法在应用于GPT涡轮3.5时并没有产生良好的结果。这表明需要在方差减小的范围内进行进一步的研究。
图6:GPT协议4的政策和目标度量的置信区间变窄，表明稳定性提高。具有高目标度量的负策略度量表示显著优于具有六维实例的基础事实模型。
结论和未来方向
在这篇文章中，我们展示了在优化领域中评估大型语言模型的深入研究，其中LLM逐步生成新的解决方案来优化目标函数。我们调查了LLM在四个优化任务中的性能，这些优化任务要求LLM理解算法指令，并能够基于以前的解决方案及其相应的值生成新的解决方案。
我们的评估表明，LLM展示了跨不同领域的优化能力。在我们研究的四个任务中，逻辑硕士在梯度下降任务中表现出最大的优势，在这一领域表现出非凡的能力。然而，他们在元启发式任务中遇到了更明显的困难，他们必须遵守他们以前没有遇到过的预定义规则。此外，LLM在网格搜索任务中展示了令人印象深刻的技能，展示了它们有效进行穷举搜索的能力。在黑盒任务中，LLMs更胜一筹，尤其是在处理有限的样本量时，表明了它们内在的优化能力。
我们还巩固了从我们的实验结果中得出的一些重要的见解，并对它们进行了分析。我们发现，预先训练的知识在LLMs的优化能力中占主导地位，同时它们在小规模问题中也拥有更丰富的解空间。此外，我们阐述了LLM作为混合优化器的潜力。这些见解和分析揭示了大量有待进一步研究的未决问题。
附录
