Hello there. Today we're going to look at Beyond A: Better Planning with Transformers via Search Dynamics Bootstrapping by Fair at Meta. This paper teaches a language model how to perform planning in the sense of it teaches it how to think about a planning problem and you know what steps you have to do to plan ahead.And applications of this are in this paper, kind of game applications. So, for example, this game right here, this Sokoban puzzle, where this person here has to push all the crates into the respective.Places, so any crate needs to go to a space at the on the floor. But you can only push, you cannot pull. And thus, if you push, for example, this crate down here, the game is over because you have no way of getting it back. So planning ahead is really important in these situations and in many many real world situations.This paper tackles planning using transformers or planning using language models in general. So that's what the paper largely is about. We'll go on how they do it. They do it via bootstrapping from a planning algorithm called A. And we'll go what kind of results they have at the end. They're going to be they're going to be at a place where they have this model called Searchformer.That model not only learns or has learned to plan and output optimal plans, but it has learned to do so in fewer search steps than standard A* would take to output optimal plans.And that's pretty cool. So we'll see how they do that. To be said, this paper we've discussed this in our Saturday paper discussions on Discord. So almost every Saturday we have paper discussions.on Discord, where we talk about different papers and and look at them in depth. So a lot of the things I'm gonna say right here are actually sourced from the community. If you wanna attend paper discussions or even present something to the group, you know, feel very free to come. It's not recorded, so any stupid questions can be asked freely without any consequences whatsoever.There are, by the way, there are even almost daily paper discussions going on on Discord at various times. So it's a very lively place.Alright, let's dive in. Planning. What is planning? Planning is very related toSomething like reinforcement learning, but it's also a little bit different. So it's kind of the same and kind of different. What you do in planning is you have a start and you have a goal, and let's say this is like a maze task. Maze tasks are very often used in in planning tasks just to illustrate. So in a maze task, you can either move like laterally or down.Okay, and so you will have to find a path from the start to the goal with these steps, but yourThe challenge is there are some some walls where you cannot go. So there might be a wall here and a wall here and a wall here and a wall here. So you'll have to somehow find a way around those around those walls.Now, we could just do it, right? We could just go and train a reinforcement learning agent, and every time it crashes into a wall, we're like, no, that's not good. Start over and so on, but.This is it's workable in a game scenario where we can restart the game, but it's not workable in a scenario where we're actually in the real world or we can't restart or something like this. Once we crash into a wall, we're actually kind of hurt, and thus we don't want to do that. What we want to do is we want to plan ahead.So planning is like doing this here, but in your mind. So in your mind, you walk ahead. You're like, okay, what happens if I do this step? Okay, I would be here. What happens if I go there? I can't do that. Okay, so maybe I consider going here. Ah, that might work out. And going here, going here. This looks good. Going here. Um, bit too far, so I kind of backtrack, backtrack, go here.Right. Now the backtracking isn't actually doing steps back, but it just says, okay.If I go, if I reach here, that might be a bit too far. So let me go back in my thinking process to this point here, and let's.In my mind, choose a different path to go along. So you can see that planning is a lot like acting in the world, except it's in your mind. And the only difference is you can sort of at any point.Choose a different path in the past. So if you go down one path and you don't like it, then you can just say, well, okay, how about that we don't do that? How about we go down here? And you cannot do that in the real world because in the real world you would have to actually do the steps back until you're in in this state here again. But in a plan, in a fictitious world, you can.And and that's the entire difference. So you can immediately see why that is super useful in especially in scenarios where going down one path could lead you into a situation where you can't go back anymore because you've pushed a crate at against the wall and you can't pull it anymore. And yeah, so I hope you can see a little bit the difference. So it's not huge, but there is a difference.The other difference is the output of a reinforcement learning process. Let's say is is a policy, right? And the the goal there is to to maximize reward using the policy in the world. The output of a planning process is a plan, and that plan. So the most basic the most basic plans are.The actions that you are going to take, right? So it says, okay, first go down, then go to the right, then go to the right, then go down, then go down, then go left, down, right, right. That's the output. So the output is is the plan itself. Now.Planning can be infinitely complex, right? So, for example, you can have conditional plans. You can, you can say, well, if you know, go down, go right, go right. In in case there is nothing here, which maybe you don't know ahead of time, in case there is nothing here, go there. In case there is something there, go around it. That could be a plan. So the plan could be the entirety of if this, then that, and so on. The plan.Um can be conditional. The plan can be probabilistic, and so on. In this work, we only consider very simple scenarios where the plan is, in fact, the steps you're going to take in order to reach the goal. The precondition in our setting is to have a model of the world. So that's also good in games because you know exactly, right? If I give you the situation, if I give youYou're here. Here's the goal, and then here are the walls right here. You know exactly what's going to happen if, for example, you make a step down. You will be you will be in this situation right here. You know exactly what happens if you make another step down. You can't do that.So, having an accurate world model is is giving rise to a subfield of planning that is quite easier than the places where you don't even have an accurate world model, right? Then you have to sort of plan ahead in
摘要或在习得的世界模型中等等。所以，嗯……是的，只是想稍微设定一下关于“规划”的框架，因为人们倾向于将其与强化学习混淆，这也很公平，因为它们非常相似。除了强化学习实际上是在世界中行动，而规划则不然。规划只是在脑海中在一个虚构的世界中行动，这个世界可能是对现实世界准确或不准确的表示。在这种情况下，它是一种准确的表示。好吧，回到正题。
事实是我们要做的实际上是在某种学习，但不是在行动中，而是在规划空间中行动。因此，我们将把规划动力学视为现实世界，并在那里实际上进行一种习得的过程。所以，抱歉，你现在可能比开始时更困惑了，但可以说的是，大型语言模型（LLMs）通常在解决规划和推理任务时表现不佳，对吧？人们知道 LLM 在创意写作等方面非常出色，但一旦给它们一个需要多步推理或某种程度地前瞻、如何达成目标并规划出来的任务，它们的通常表现并不好。
人们尝试过思维链（Chain of Thought）和思维树（Tree of Thought）等方法，但它们更像是拐杖而非解决方案。因此，在许多情况下，这些技术会导致更差的表现。例如，由于自我强化等原因。另一方面，现有的传统规划和搜索技术通常效果很好，对吧？我们有从简单到复杂的规划算法。如果你给它们一个规划问题，并且该问题以图的形式定义，对吧？
所以我们在上面看到的这个迷宫可以极好地展示为一个图。每一个你可能到达的地方都是一个图节点，如果我可以通过一个给定的动作从一个节点到达另一个节点，那么我将在这些图节点之间有一条有向的、甚至可能是加权的边。在这种情况下，规划仅仅表现为在图中寻找最短或最低成本的路径，我可以用广度优先搜索这样的简单方法来实现它。
规划是一门成熟的学科，所以大型语言模型的能力与那些在规划方面仍然比 LLM 表现得好得多的简单算法之间，存在一点差异——并不奇怪，但确实有这种反差。好吧，所以他们做的是演示如何训练 Transformer 来解决复杂的规划任务，并提出了 Searchformer，这是一种 Transformer 模型，它计算的步数少于 A* 搜索等符号规划算法。
好吧，我必须在此之前说明一下，他们最简单的方法是解决这个问题，并让经典的规划算法运行。经典规划算法会像这样：好吧，让我们去这里。好的，考虑这个。啊，不能这样做。好的，让我们去这里。好吧，考虑这个。不能这样做。我们去这里。我们去这里。我们去这里。不确定这是否还正确。也许我们试试上面那里？不，不，那似乎不对。好吧，也许我们再往下走一点。啊，好的，现在我们到达了目标。
就像我刚才做的这一系列步骤一样。这……也许在这里？好的，不，那似乎不错。那似乎不好。这就是一系列步骤，对吧？每一步，包括我说“啊，不，不要去那里，去别的地方”或者“不确定这是否正确，让我们考虑上面那个地方”的步骤。所有这些都可以简单地表达为一种语言字符串，就像我刚才做的那样。我只是顺序地执行了一些动作，这些动作反过来可以变成一系列标记（tokens）。
比如为了说明起见，“让我们往下走”，“哦不，我们不能去这里”。啊……你知道的？嗯……让我们走吧。对吧等等。这些都是标记，对吧？我可以基于此构建一个语言模型。所以这是一个标记，那是一个标记。这实际上是同一个标记。这是另一个标记。所以我可以定义这种语言的字汇表，然后我可以在此之上训练一个语言模型。
我可以训练一个语言模型来精确地学习这种语言，然后关键点在于：如果我对许多不同的迷宫任务进行此操作，在不同的变体中等等，并且我总是用语言编码这里的情况，然后用语言编码这里的规划算法（或者更准确地说，是计划本身），对吧？我在语言中表达我实际想要做的事情。这就定义了一种语言和一系列标记，我可以教给一个语言模型去输入这种语言并输出相同的内容。
所以如果下次我只喂入问题的描述，它自己就能输出搜索动力学和最终计划，就是这样。所以当他们说“我们演示了如何训练 Transformer 来解决复杂的规划任务，并以少于 A* 搜索等符号规划算法的步数计算最优计划”时，这就是他们的意思。他们训练一个 Transformer 来模仿规划算法，然后他们有了一种技术来实际减少这里的步数。
话虽如此，我对他们说“计算最优计划”这一点有个问题。因为这些都是语言模型，它们受到任何语言模型的缺点的影响，包括它们是随机的（stochastic）。它们容易幻觉等等。所以这里出来的东西是否是一个最优计划是完全无法保证的，对吧？他们通过实验测量并发现是的，实际上在许多情况下最后出来的确实是最优计划。那样还可以，但没有保证出来的是一个有效计划或最优计划。所以在接下来的内容中请牢记这一点。
他们构建了一个可验证的、既有效又最优的计划数据集，然后训练一个语言模型。但出来的东西只是模仿了规划的风格。没有保证它实际上会产生真正的计划。你可能会想，哦，这有点令人沮丧等等。但论文的想法并不是构建世界上最好的规划器。论文的想法是：我们可以探索吗？比如，如果我们教一个语言模型如何思考规划问题会发生什么。
这就是中间的部分，对吧？所以开始部分是问题，结尾部分是你所知道的模型输出的实际计划。
之前我们一直的做法是，把问题输入进去，然后训练模型直接输出解决方案。这就是目前的现状，中间可能有一些辅助手段。比如人们发现，如果在输入中加入“请一步步思考”之类的提示会怎样？这篇论文正是对这类做法的形式化，或者更准确地说，是更为严谨的实现。核心问题是：如果我们教模型如何思考规划问题会怎样？也就是说，我们在中间部分明确地教导它们：“看，这是解决规划问题所需的步骤。”主要疑问在于：这样做是否有效？与直接从问题陈述训练到输出相比，这是否能更频繁地输出最优计划？
这一切都是在为论文的核心内容做铺垫。该研究并非试图解决规划问题或构建最佳的规划算法，也不是在探讨使用大语言模型进行规划的某种特定方式。它的目的很简单，就是回答这个问题：如果我们明确教导语言模型如何思考规划问题，会发生什么？规划问题对它们来说是否变得更容易上手了？如果答案是肯定的，那么我们就可以对那些声称“规划需要真正的符号思维、完全超出语言模型能力范围”的人提出反驳或支持。这与下一个词元预测截然不同，这就是论文的研究定位。
正如我刚才在 rant 中所提到的大部分内容，让我们来看一些具体细节。这是一个迷宫任务示例：你有一个起始格和一个目标格，以及一个计划。算法的输出是你将要执行的动作，而中间的部分则是你如何达成该计划的整个过程。提示（Prompt）就是描述当前的情况：这里有一个起始格，一个目标格，以及墙壁格子。不过，这个例子我敢肯定是有问题的。论文本身存在不一致之处：这里的符号表示与附录中的不符，它们似乎搞反了；甚至这个例子本身也与文中描述的情况不匹配。所以如果你自己阅读这篇论文，不要感到困惑。这是我们周六讨论时发现的问题之一。
这是规划算法的输入和输出。这是一个计划，即“我将做什么以到达目标”。正如我之前所说，我们必须从输入过渡到输出。在经典意义上，我们使用规划算法来实现这一点，比如 A 算法。而在新时代，我们会通过深度学习来做这件事：输入数据并训练模型直接输出结果，即端到端学习。而这篇论文提出的是：如果我们还明确教导它中间过程应该是什么样子的，会发生什么？这个中间过程大致如下：在提供输入和输出之后，我们还希望生成中间的这部分内容。他们称之为 A 的执行轨迹（execution trace）。
A 是一种规划算法，它基本上做了我刚才演示的事情：它会想，“我能往这里走吗？能。嗯，这看起来不错。”“不，那不行。”然后退回去等等。它是通过操作封闭搜索节点集和前沿（frontier）节点集等来实现这一点的。稍后我们将详细探讨 A 是如何工作的，这是一个非常经典的算法；如果你已经了解它，就能跟上节奏。如果不了解也没关系，这只是一个内部执行某些步骤的算法。重要的是考虑它内部的这些步骤及其轨迹（trace），因为正是这个轨迹导致了最终的计划。
请注意，轨迹不同于计划本身。轨迹只是规划算法计算计划的内部过程。有趣的是，计划可能是最优的，也可能不是。例如，在特定假设下，A 保证产生最优计划，即以最短成本或距离到达目标的方案。对于同一个问题可能存在多个最优计划，但 A 肯定会找到其中一个。不同规划算法的区别在于：即使它们都保证能找到最优计划，其执行轨迹的长度和复杂程度也各不相同。甚至在同一个算法中，由于平局打破（tie-breaking）等机制导致执行顺序不同，轨迹的长短也会有所差异。
广度优先搜索和 A 都保证在迷宫任务中给出最短路径，但它们产生的执行轨迹截然不同。人们之所以使用不同的规划算法，即使它们都能提供最优计划，正是因为有些算法能以更少的内部步骤更快地达到最优解。因此我们的目标是：能否训练一个 Transformer 从输入直接得到正确的输出？这里的“正确输出”指的是最优计划，或者对于大型问题而言是接近最优的计划，并且具有尽可能短的中间过程（即最短的执行轨迹）。现在让我们看看 A 到底做了什么。
根据维基百科，A 算法本质上是一个带有启发式函数的 Dijkstra 算法。你可以看到：蓝色始终代表当前最有希望成为最优计划的候选节点，红色表示已经探索过的区域，绿色被称为“前沿”。在每一步中，算法会选择其中一个绿色的点（甚至可能是顶部的某个绿点）。它只选择一个绿点，然后考虑从该点可以执行的所有步骤并探索它们，接着再选择下一个绿色节点。如果你在这里进行广度优先搜索，你可以想象左上角或左侧及顶部区域也会被探索。然而，这个 A 算法似乎知道如何朝向目标前进（目标是右下角），这是因为它利用了启发式信息。
A 算法相较于经典图搜索的优势在于，它能朝着目标方向进行搜索。这是通过所谓的“启发式函数”实现的。A 算法从起点开始探索，在决定扩展某个节点时，始终考虑两个因素：一是距离起点的实际代价（即已走过的步数），二是启发式估计值。例如，若某节点距离起点为 1，而另一节点为 3，通常优先探索前者。但如果某些节点虽然距离起点远（如代价为 1），却更接近目标，那么即使当前路径较长，也可能更优。
A* 考虑的第二个因素是启发式函数，它通常估算当前点到目标的剩余距离。在空间规划任务中，这可以是直线距离（欧几里得距离）、曼哈顿距离或 L2 范数。启发式函数越小，意味着越接近目标，这是一个好迹象。尽管有时会被障碍物误导（如遇到墙壁需绕行），但总体而言这是有效的策略。
A 算法的一个关键属性是“可接纳启发式函数”。这意味着启发值必须始终低估到达目标的实际距离。在上述迷宫问题中，直线距离或曼哈顿距离都满足这一性质，因为两点间没有比直线更短的路径。只要启发式函数是可接纳的（即低估），A 算法结合起点距离和启发值，就能保证找到最优路径。
在 A* 的执行过程中，如果多个节点具有相同的评估值（即起点距离加启发式估计相等），就需要打破平局。这可以通过确定性方法或随机非确定性方法实现。虽然在这种情况下结果可能相同，但如果存在未知的障碍物（如墙壁），扩展节点的顺序就会影响最终路径的长度。随机选择可能导致更长的执行轨迹，因为需要回溯；也可能导致较短的轨迹。
这篇论文的关键部分在于：他们运行 A 算法并训练两种不同的模型。“仅解序列”模式直接输入问题描述，输出最优计划。他们通过合成数据生成这一数据集：创建不同的迷宫或推箱子谜题实例，运行 A 得到最优计划，然后将输入与输出配对。
另一种模式则在“提示”和“最终计划”之间加入 A* 的搜索轨迹。语言模型的输入包含这些中间步骤，目标是教会模型如何思考规划问题，最后才输出计划。评估标准包括：计划是否正确（是否撞墙）、是否最优，以及搜索轨迹的效率长短。
他们使用编码器-解码器架构的 T5 模型从头开始训练，因为搜索轨迹可能非常长。虽然模型规模相对 modest（不像 GPT-11 那么大），但由于序列长度极长，仍消耗大量 GPU 时间。他们使用了旋转位置嵌入（RoPE），这种技术擅长处理动态长度和超长序列。
结果显示，搜索增强模型即使规模较小，也优于仅解模式的大模型。“仅解”大模型需要大量训练数据才能达到与搜索增强模型相当的性能。这清楚地表明，通过展示思考过程（即 A* 轨迹），语言模型能更高效地学习规划。
无论是确定性还是非确定性的搜索顺序，搜索增强模型都表现出优势。尽管序列更长、噪声可能更多（因为计划位于轨迹末端），但性能反而更好。“仅解”模型直接从输入映射到输出，需要更多的训练样本才能达到相同效果。
达到相同的性能水平。这意味着，教导语言模型如何思考规划问题，能使它们在规划任务上表现得更好。相反，如果你没有明确教导它们这样做，那么模型就需要大量的数据来自己摸索出方法；甚至在其他实验中似乎表明，它们根本无法达到预期的性能水平。
我认为这非常有趣。是的，你可以看到即使是小型模型也能在少量训练样本上表现出众，它们的表现远超仅输出解决方案的模型。这里有很多细节，比如它们的优化标准是64次采样中取最优解，即样本化64次然后选取最佳结果等。我不想深入探讨这些细节，只想说明它们现在能够训练出一种模拟A*算法执行轨迹的模型。
接下来他们做了什么？他们说我们要超越这一步，实施一种方法来改变解码器生成执行轨迹的分布。首先，他们在非确定性A*实现上训练模型。引入“非确定性”很重要，因为这引入了变异性；相同的输入问题可能会有不同的执行轨迹来达到相同或同等低成本的目标方案。可能存在多个最优解，但即使达到相同的成本，中间的执行轨迹也会不同，因为我们随机打破平局、随机排序子节点的探索顺序等。
他们声称仅仅改变了不同节点被搜索的顺序，同时仍尊重A*算法的启发式成本计算。这导致每个执行轨迹的长度产生额外的方差。生成的搜索增强模型随后将近似训练序列生成的概率分布。一旦获得该模型，他们就利用它生成执行轨迹和方案。想象一下：你有一个原始数据集，包含输入、轨迹和计划，且该轨迹具有一定的长度。
他们接下来要做的是：使用相同的输入生成新的轨迹和计划，并检查该计划是否最优。他们可以通过将其与A计划的成本进行比较来做到这一点；如果成本相同，则它是优的，因为A保证找到最优计划。如果新轨迹比原来的更短，他们就替换掉这个训练样本。完成所有操作后，他们仅在新的数据集上重新训练一个新模型；根据定义，这个新数据集对于相同的输入问题具有更短的执行轨迹，并构造性地产生所有最优计划。
现在的问题是：这个新模型是否也能以更短的执行轨迹达到最优计划？答案是肯定的，这非常酷。然而，我对这篇论文有一点困惑，即如何解读这一结果。他们在文中不同地方提到：Searchformer模型不再模仿A*搜索，而是发现了一种使用更少搜索步骤解决规划问题的新方法。对此我持保留意见，因为这里可能发生两种情况。
第一种情况是：如果你确实发现了一种更短的轨迹且对应最优计划，那么它可能找到了一种不受约束的生成方式。也就是说，它不需要遵循任何特定算法，只需输出令牌；只要产生正确的计划即可。如果它在没有轨迹辅助的情况下也能更好地生成正确方案，那么这里的轨迹实际上是有帮助的，但它不再是A的标准轨迹，而是模型自行输出的内容。作者据此声称它找到了一种更好的方法——确实如此，因为它偏离了A的行为模式。
第二种情况（我认为更有可能）是：正如我们之前讨论的，执行轨迹的长度取决于执行的顺序。我们在训练时包含了这种方差，那么是否可能所有这些较短的执行轨迹仍然是完全有效的A轨迹？因为我们通过采样筛选出更短的轨迹加入数据集，这存在对短轨迹的选择偏差。因此，这些很可能都是有效的A轨迹，只是类似于非确定性图灵机的风格——那些因随机打破平局而导致总执行长度更短的情况。
我认为这种情况比“完全偏离A”的可能性更大。这意味着模型学会了以非随机、更优化的方式全局审视问题并打破平局，从而获得更短的执行轨迹。这本质上等同于学习到了更好的A启发式函数。例如，当你在两个节点间犹豫该扩展哪一个时，如果仅考虑到目标的欧几里得距离（L2），你可能无法决定；但如果考虑到墙的位置，你就能做出更优选择。
这只是一个更好的启发式函数而已。我认为这里发生的情况是：模型学会了以更具优化性的方式打破平局，生成的仍然是完全有效的A执行轨迹。区别在于标准的A算法不具备这种全局信息，而Transformer具备，因此这相当于教会了它更好的启发式规则。然而，论文中从未探讨过这一点：结果轨迹是否实际上是有效的A*轨迹？它们偏离了多少？这些轨迹看起来是否像模型真正学会了优化策略，还是仅仅反映了数据中的选择偏差？
还有一些非常新颖的内容，比如……这些方面尚未得到充分探索。是的，这也是我对那篇论文的批评所在。除此之外，它相当不错。他们展示了：如果我们重复这种类似“向下”的步骤——即用更短的样本替换训练数据，从而缩短这些执行轨迹的长度等。所有这些方面都得到了很好的研究。
同样地，当我们使用搜索增强来训练模型时……事实上我们会得到更好的结果：更优的解、更短的解，以及更多次出现最优解。这也很有趣。所以，如果你只是训练一个搜索增强模型，或者训练这些缩短长度的模型，你实际上会更频繁地得到有效解。这也很有趣，并留下了阐释的空间。
嗯……基本上这就是我想说的关于这篇论文的内容了。我不想过多深入实验细节，因为我认为我刚才的阐述已经很好地概括了它们。当然，非常欢迎大家去阅读论文原文。它绝对很有趣，确实是很棒的工作。
这确实表明：如果你教 Transformer 模型如何思考规划问题，它将比直接告诉它“好吧，一步步想”或者什么都不说（即不进行显式引导）时，具备更强的规划能力。
鉴于大型语言模型是在互联网数据上训练的，我们可以这样解读：“一步步思考”之所以有效这一事实意味着训练数据中包含某种形式的“逐步推理”。这进一步佐证了这一点。也就是说，如果我们确实针对这些思维步骤进行训练，模型在这些步骤上会变得更强，并且能够泛化。
在这种情况下，虽然是在同一问题领域内进行的泛化，但它们确实实现了泛化。我认为这是这篇论文的主要贡献，这非常酷。而关于超越 A* 算法、减少搜索步骤等内容……那算是锦上添花了。
就这些。感谢收听。请保持水分充足，再见。