一、用于LM Agent的树搜
论文名称：Tree Search for Language Model Agents
论文地址：https://arxiv.org/pdf/2407.01476
1. 简介
基于LLM的Agent已经展现出了执行决策任务的能力，但是LM主要是针对自然语言理解和生成进行优化的。在基于多步推理、计划和理解环境反馈来求解现实计算机任务对于LM来说很难。本文为LM agent提出了一种推理时搜索算法，用于在web环境中执行探索和多步计划。
2. 方法
成功求解web环境中的一个任务，可以被解释为给定正向奖励 R ( s ∗ ) = 1 R(s_*)=1 R(s∗)=1时达到某个目标状态 s ∗ s_* s∗。agent起始于状态 s 0 s_0 s0。给定自然语言指令 I I I，agent的目标是通过执行一组动作 ( a 0 , … , a t ) ∈ A (a_0,\dots,a_t)\in\mathcal{A} (a0,…,at)∈A来达到目标状态。每个动作会产生一个新状态 s t + 1 ∈ S s_{t+1}\in\mathcal{S} st+1∈S和观察 o t + 1 ∈ Ω o_{t+1}\in\Omega ot+1∈Ω。状态的转移 s t → s t + 1 s_t\rightarrow s_{t+1} st→st+1是由转移函数 T : S × A → S T:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S} T:S×A→S决定的。
大多数方法将其看作是一个部分可观察Markov决策过程，仅基于当前观测 o t o_t ot来预测下一个动作 a t a_t at。这有一个显著的限制：agent的错误会随着步骤累加，若在某个t时刻采取了错误的动作，这将导致未来的不良状态且难以纠正。
2.1 Agent Backbone
大多数SOTA web agent都是建立在LLM上的。一个预训练语言模型或者多模态模型 f ϕ f_{\phi} fϕ被要求基于当前的webpage观测 o t o_t ot来预测下一个要执行的动作 a t a_t at。通常会利用一些prompting技术，例如ReAct、RCI或者CoT等来改善agent的效果。
2.2 Value Function
本文基于价值函数 f v f_v fv实现了best-first搜索启发算法，该价值函数用于估计当前状态 s t s_t st的期望奖励 E [ R ( s t ) ] \mathbb{E}[R(s_t)] E[R(st)]，而真实的目标状态将提供值为1的完美奖励。由于模拟器的状态 s t s_t st并不能总是被agent访问，价值函数使用当前和先前的观测以及自然语言任务指令 I I I来计算价值 v t v_t vt：
v t = f v ( I , { o 1 , … , o t } ) ∈ [ 0 , 1 ] v_t=f_v(I,\{o_1,\dots,o_t\})\in[0,1] \\ vt=fv(I,{o1,…,ot})∈[0,1]
在本文的实验中，价值函数(value function)是通过提示一个多模态语言模型来实现的。
2.3 搜索算法
本文提出的算法是受A*搜索启发的best-first搜索算法。使用语言模型agent来提出搜索树的候选分支。该搜索具有超参数深度 d d d、分支因子 b b b和搜索预算 c c c，这些决定了搜索树的最大尺寸和终止阈值 θ \theta θ。
在执行轨迹的时刻 t t t，agent先前已经执行了一系列动作达到了状态 s t s_t st。从 s t s_t st开始搜索算法，初始化一个最大优先级队列 F ← { } \mathcal{F}\leftarrow\{\} F←{}，该队列包含了计算进行评估的状态集合。目前找到的最优状态为 s ^ t ← s t \hat{s}_t\leftarrow s_t s^t←st，最优序列分数为 v ^ t ← 0 \hat{v}_t\leftarrow 0 v^t←0，搜索计数器为 s ← 0 s\leftarrow 0 s←0。
在每次搜索过程中，从 F \mathcal{F} F中抽取下一项 s p ← pop ( F ) s_p\leftarrow\text{pop}(\mathcal{F}) sp←pop(F)。然后使用价值函数来计算状态 s p s_p sp的分数：
v p = f v ( I , { o 1 , … , o p } ) v_p=f_v(I,\{o_1,\dots,o_p\}) \\ vp=fv(I,{o1,…,op})
然后，增强搜索计数器 s s s，若 v p v_p vp比当前的最优分数 v ^ t \hat{v}_t v^t更高，则更新分数和最优状态：
s ← s + 1 s ^ t ← { s p if v p > v ^ t s ^ t otherwise v ^ t ← max ( v ^ t , v p ) \begin{align} s&\leftarrow s+1 \\ \hat{s}_t&\leftarrow \begin{cases} s_p&\text{if }v_p>\hat{v}_t \\ \hat{s}_t&\text{otherwise} \\ \end{cases} \\ \hat{v}_t&\leftarrow\max(\hat{v}_t,v_p) \end{align} \\ ss^tv^t←s+1←{sps^tif vp>v^totherwise←max(v^t,vp)
若 v p ≥ θ v_p\geq\theta vp≥θ或者 s ≥ c s\geq c s≥c(超出搜索预算)，将会终止搜索并转移到目前为止最优状态 s ^ t \hat{s}_t s^t。
若当前分支没有超过最大深度 ( 即 ∣ ( s 0 , … , s p ) ∣ < d ) (即|(s_0,\dots,s_p)|<d) (即∣(s0,…,sp)∣<d)，那么会从语言模型agent f ϕ f_\phi fϕ中获取 b b b个候选动作 { a p 1 , … , a p b } \{a_p^1,\dots,a_p^b\} {ap1,…,apb}作为分支的下一步动作。对于每个 i i i，执行动作 a p i a_p^i api并添加结果状态 s p i s_p^i spi至优先队列中：
F ← F ∪ ( v p , s p i ) for i = 1 , … , b \mathcal{F}\leftarrow\mathcal{F}\cup(v_p,s_p^i)\quad\text{for }i=1,\dots,b \\ F←F∪(vp,spi)for i=1,…,b
这样就结束了搜索迭代。若两个终止条件都没有达到，回溯并重复这个过程。
二、理解和缓解LLM的语种困惑
论文名称：Understanding and Mitigating Language Confusion in LLMs
论文地址：https://arxiv.org/pdf/2406.20052
1. 简介
本文研究LLM的局限性：它们无法始终如一地以用户期望的语言生成文本。创建了一个语言困惑基准（Language Confusion Benchmark, LCBl）来评估语言一致性，其覆盖了15种不同类型的语言。评估了一系列单语或者多语LLM，发现Llama Instruct和Mistral展现出高度的语言困惑，即使是最强的模型也无法始终以正确的语言进行应答。本文发现base模型和以英语为中心的指令模型更容易产生语言混乱，复杂的指令和高采样温度会加剧语言困惑。few-shot提示、多语言SFT和偏好微调能够部分缓解语言困惑。
2.Language Confusion Benchmark
2.1 生成设置
在两种设置中衡量语言困惑：单语言生成和跨语言生成。单语言生成：使用语言 l l l进行查询并期望使用语言 l l l应答。跨语言生成：用户使用语言 l l l来提示模型并期望使用另一种语言 l ′ l' l′来响应。
2.2 语言困惑度量
行级检测。将响应划分为行，并使用fastText来检测每行是否为用户期望的语言。
词级检测。没有现成的词级别语种检测工具，并且LLM的准确率不足以作为自动评估器。观测到单词级困惑主要是在英语中，因此选择启发式评估一个语种子集，包括Arabic(ar)、Hindi(hi)、Japanese(ja)、Korean(ko)、Russian(ru)和简体中文(zh)。
二值评估。计算二值度量来表明应答中是否包含实例：(a) 一行不正确的语言；(b) 非Latin语言中包含度量的英文单词或短语。
行级通过率(LRP)：模型应答能够通过行级语言困惑检测的百分比。若一个应答的所有行都满足用户期望的语言则为正确。
LRP = ∣ R \ E L ∣ ∣ R ∣ \text{LRP}=\frac{|R\backslash E_L|}{|R|} \\ LRP=∣R∣∣R\EL∣
其中 R R R是所有应答的集合， E L E_L EL是包含行级错误的应答集合。
词级通过率(WPR)：应答中所有单词都是用户期望语言的比例。
WPR = ∣ ( R \ E L ) \ E W ∣ ∣ R \ E L ∣ \text{WPR}=\frac{|(R\backslash E_L)\backslash E_W|}{|R\backslash E_L|} WPR=∣R\EL∣∣(R\EL)\EW∣
其中 R R R是所有应答集合， E L E_L EL是具有行级错误的应答集合， E W E_W EW是具有单词级错误的应答集合。
语言困惑通过率(LCPR)：LPR和WPR的调和平均值
LCPR = 2 × LPR × WPR LPR+WPR \text{LCPR}=2\times\frac{\text{LPR}\times\text{WPR}}{\text{LPR+WPR}} \\ LCPR=2×LPR+WPRLPR×WPR
2.3 数据源
Aya、Dolly、Okapi、ShareGPT、Native prompts、Complex prompts。
3. 实验
单语生成。Command和GPT模型在LPR上表现很好，但是Llama和Mistral表现比较差。Mistral在一些欧洲语言上表现会好一些，但是Llama即使在德语这种高资源语言上表现也比较差。大多数模型的WPR在相同范围，Mixtral 8x7B则要差的多。GPT-4 Turbo在LCPR上最强，GPT-3.5 Turbo和Command R+位列第二。
跨语言生成。Command和OpenAI模型总体是最好的。Llama表现相当差，仅有30多分，因为其倾向于英语应答。
三、理解事实知识抽取的微调
论文名称：Understanding Finetuning for Factual Knowledge Extraction
论文地址：https://arxiv.org/pdf/2406.14785
1. 简介
本文研究QA微调数据对下游事实性的影响。研究表明，即使在预训练时见过所有的事实，但是使用鲜为人知的事实进行微调要不熟悉事实微调的效果差的多。
2. Preliminaries
事实知识定义。将事实知识表示为从主实体 s s s和关系类型 r r r到答案 a a a的映射。表示这些映射为知识三元组 ( s , r , a ) (s,r,a) (s,r,a)，其中 s ∈ S , r ∈ R , a ∈ A s\in\mathcal{S},r\in\mathcal{R},a\in\mathcal{A} s∈S,r∈R,a∈A，且 S , R , A \mathcal{S,R,A} S,R,A是所有实体、关系和答案的集合。单个三元组 ( s , r , a ) (s,r,a) (s,r,a)在自然语言中有多种表示。这里，建模自然语言为token序列的集合，token来自于集合 T \mathcal{T} T。
知识格式化函数。知识可以有很多种文本表示。通过引入一个格式化函数 g : S × R × A → T k g:\mathcal{S}\times\mathcal{R}\times\mathcal{A}\rightarrow\mathcal{T}^k g:S×R×A→Tk来将三元组 ( s , r , a ) (s,r,a) (s,r,a)映射为token序列。
预训练和微调。给定一个知识三元组集合 D k = { ( s , r , a ) i = 1 N } D_k=\{(s,r,a)_{i=1}^N\} Dk={(s,r,a)i=1N}和一个预训练格式化函数，那么生成预训练语料 D p r e = { g p r e ( s , r , a ) ∣ ( s , r , a ) ∈ D k } D_{pre}=\{g_{pre}(s,r,a)|(s,r,a)\in D_k\} Dpre={gpre(s,r,a)∣(s,r,a)∈Dk}。对于一个下游格式化函数 g d o w n g_{down} gdown，生成下游数据集 D d o w n = { g d o w n ( s , r , a ) ∣ ( s , r , a ) ∈ D k } D_{down}=\{g_{down}(s,r,a)|(s,r,a)\in D_k\} Ddown={gdown(s,r,a)∣(s,r,a)∈Dk}。实践中，微调数据集相对于预训练来说是有限的，因此将 D d o w n D_{down} Ddown划分为 D f t D_{ft} Dft和 D e v a l D_{eval} Deval，其中 D f t D_{ft} Dft用于微调且 D e v a l D_{eval} Deval用于测试集。
在QA的设置中， g p r e g_{pre} gpre以书籍或者文章的形式呈现知识，而 g d o w n g_{down} gdown以问答对的方式呈现知识。
3. 合成实验
3.1 合成设置
对于三元组中每个subject、relation和answer都是单个token，并令 g p r e ( s , r , a ) = ( s , r , a ) g_{pre}(s,r,a)=(s,r,a) gpre(s,r,a)=(s,r,a)。为了能够模拟下游任务的变化，为每个relation类型引入QA-prompt token p r p_r pr。QA-prompt token在预训练中未见过，但是会在下游的格式化函数中使用： g d o w n ( s , r , a ) = ( s , p r , a ) g_{down}(s,r,a)=(s,p_r,a) gdown(s,r,a)=(s,pr,a)。因此，在微调时语言模型必须学会对于 ( s , r ) (s,r) (s,r)使用 ( s , p r ) (s,p_r) (s,pr)应答。token空间 T = S ∪ R ∪ A ∪ { p r ∣ r ∈ R } \mathcal{T}=\mathcal{S}\cup\mathcal{R}\cup\mathcal{A}\cup\{p_r|r\in\mathcal{R}\} T=S∪R∪A∪{pr∣r∈R}。
在预训练过程中， ( s , r , a ) (s,r,a) (s,r,a)是从分布 s ∼ Zipf ( S ) , r ∼ Unif ( R ) s\sim\text{Zipf}(\mathcal{S}),r\sim\text{Unif}(\mathcal{R}) s∼Zipf(S),r∼Unif(R)中独立同分布采样出来的。这个建模选择类似于预训练语料了，即包含流行的实体也包含未见的实体。在微调时，在 D f t D_{ft} Dft上执行标准的batch。假设呈现给模型的所有知识序列都与 D k D_k Dk中的ground truth ( s , r , a ) (s,r,a) (s,r,a)一致的。
最终，所有下游微调和测试数据集 D f t D_{ft} Dft和 D e v a l D_{eval} Deval中的事实都在 D p r e D_{pre} Dpre中有呈现。
3.2 模拟观测
主要发现：微调事实流行度影响下游表现。上图2(a)绘制了在最流行(FT-Top)和最不流行(FT-Botton)实体上微调的准确率。我们发现微调数据的选择会显著影响下游QA的事实性。具体来说，在最流行事实上微调会为模型的事实性带来10%的改善。当在测试集中包含不太流行的事实时，这种差异会被放大。例如，当将测试集中最受欢迎的5%实体扩展至10%时，FT-Top和FT-Bottom的差异会翻倍。当逐步增加不流行实体比例，这种差异会持续存在。
预训练语料中长尾的影响。上图2(b)展示了 Zipf α \alpha α参数影响。直觉上，随着 α \alpha α增加，流行和不流行事实的差异会增大。另一方面，低 α \alpha α值会导致事实的更均匀分布。我们发现，增加 α \alpha α会加剧微调数据集的差异。这些发现表明微调数据集差异的影响与预训练中事实频率差异有关。
预训练步数的影响。先前，我们观察到预训练分布中的长尾性会控制微调数据集的敏感性。这个现象的一种解释是，低频率的事实可能并没有存储在模型中，但是我们观察到即使所有的事实都可以通过 ( s , r ) (s,r) (s,r)的形式抽取，但是高频和低频事实的差距仍然存在。这表明这种差异是由内部事实存储的差异造成的。在图2©中，通过绘制FT-Top和FT-Bottom之间的差距作为预训练步数的函数来研究这个问题。可以发现，更多的预训练步数会缩小差距，表明随着事实被看到足够的次数，事实存储的内部差异消失了。
3.3 事实显著性
在模拟中的发现表明，一个模型是否"知道"一个特定的事实是一个持续的过程。这控制了下游任务中抽取事实的程度。此外，模型对事实的了解程度也觉得了微调的行为。将模型对事实的了解程度这种直观数量称为事实显著性。
本文的模拟结果表明，事实显著性和预训练语料中的事实频率有关。特别地，可以看到随着预训练分布变的更加长尾，显著性差于会被加剧。然而，我们也发现这些差异可以通过额外的预训练来缓解，这表明差异主要是由见过事实的次数驱动的。
四、Quiet-STaR：语言模型可以学会说话前思考
论文名称：Quiet-STaR: Language Models Can Teach Themselves to Think Before Speaking
论文地址：https://arxiv.org/pdf/2403.09629
1. 简介
人在写作或者说话时，有时会暂停下来进行思考。先前的一些工作将推理作为回答问题或者完全特定任务的方法，但是推理通常隐含在文本中。例如，在数学证明的步骤中有很多没有明说的步骤；对话的背后同样有很多心理活动。在Self-Taught Reasoner中，用few-shot的方式令模型学会使用rationales进行推理。本文Quiet-STaR则是对Self-Taught的推广。
2. Quiet-STaR
2.1 并行生成
Quiet-STaR的关键挑战是为输入序列中每个token位置高效的生成rationales。这需要对每个token进行独立的前向传播，对于长序列来说在计算上难以处理。
观察到语言模型的一次推理能够为所有的输入token产生下一个token的概率分布，因此可以高度并行生成。当然，这允许为每个输入中的token采样下一个token。若已经为每个token生成了后继，那么就无法使用原始序列来继续生产。例如，为"<bos> the cat sat"中的每个token生成next token，则可能得到"yes orange saw down"，每个后继都是前缀序列的合理的next token。可以利用这些后继来为每个观察到的token生成隐思考。
为了能够有效地做到这一点，缓存每次的前向传播，并拼接对角注意力mask至先前的注意力mask。这样，每个生成的token仅能关注生成它的所有token以及其本身。此外，这个并行化的采样过程可以重复任意次数。
2.2 “混合”头
对于最初的预训练模型，thoughts是分布外的，因此会损害语言模型的效果。为了能够平稳转移到思考模式，在LM使用thought和不使用thought之间引入了一个插值。给定一个end-of-thought token的hidden state以及原始文本token的hidden state，混合头会输出一个决定权重，该权重决定了post-thought预测logit被使用的程度。这个头使用一个浅层的MLP，为每个token输出标量值。
2.3 优化Rationale生成
优化Start-of-Thought和End-of-Thought token
<|startofthought|>和<|endofthought|> token作为meta-token来控制模型的rationale生成。优化这些token的表示至关重要。使用"—"的embedding来初始化start和end token的embedding，因为其在文本数据中通常表示暂停或者思考。这可以利用语言模型已有的知识。此外，为了使这些embedding能够更快的被优化，在更新时为这些embedding的梯度添加了一个权重。
Non-myopic评分和Teacher-forcing
由于并不期望在预测每个token都使用thoughts，那么更希望模型的奖励较少依赖于准确的下一个单词，而是后面的语义内容。这里有两个主要的挑战。首先，不同于基于transformers的典型语言建模，仅有那些与给定next-token预测对应的thought才能从预测中接收梯度，这是并行采样策略的结果。我们可以通过采样先前的token来为未来的token添加Loss项，从而接近这个问题。然而，这将导致语言建模更多的熵太高，降低生成文本的质量。相反，本文使用并行注意力mask来计算true next token的对数概率，通过假设模型选择了正确的next ground-truth token来应用teacher forcing。
目标函数
使用REINFORCE来优化rationales的似然，即给定先前观测的tokens和一个rationale，语言模型对于 n t r u e n_{true} ntrue个true next tokens X j + 1 : j + n t r u e + 1 X_{j+1:j+n_{true}+1} Xj+1:j+ntrue+1的对数似然。为了降低方差，为输入序列中的每个token生成多个rationale continuations。因此，定义每个rationale T j T_j Tj的奖励 r j r_j rj为 p j : j + n t r u e t a l k p_{j:j+n_{true}}^{talk} pj:j+ntruetalk和rationales的平均值 ( p ˉ j : j + n t r u e t a l k ) (\bar{p}_{j:j+n_{true}}^{talk}) (pˉj:j+ntruetalk)：
r j = log p j : j + n t r u e t a k l ( X j + 1 : j + n t r u e + 1 ) − log p ˉ j : j + n t r u e t a l k ( X j + 1 : j + n t r u e + 1 ) r_j =\log p_{j:j+n_{true}}^{takl}(X_{j+1:j+n_{true}+1})-\log\bar{p}_{j:j+n_{true}}^{talk}(X_{j+1:j+n_{true}+1}) \\ rj=logpj:j+ntruetakl(Xj+1:j+ntrue+1)−logpˉj:j+ntruetalk(Xj+1:j+ntrue+1)
然后在REINFORCE损失中使用该奖励来更新语言模型的参数 θ \theta θ，从而增加rationales的似然：
∇ θ L j REINFORCE = − r j ⋅ ∇ θ log p θ ( T j ∣ [ X : j ; <|startofthought|> ] ) \nabla_{\theta}\mathcal{L}_j^{\text{REINFORCE}}=-r_j\cdot\nabla_{\theta}\log p_{\theta}(T_j|[X_{:j};\text{<|startofthought|>}]) \\ ∇θLjREINFORCE=−rj⋅∇θlogpθ(Tj∣[X:j;<|startofthought|>])
该损失函数鼓励模型生成能够改善未来预测的rationales。
模型的参数 θ \theta θ，从而增加rationales的似然：
∇ θ L j REINFORCE = − r j ⋅ ∇ θ log p θ ( T j ∣ [ X : j ; <|startofthought|> ] ) \nabla_{\theta}\mathcal{L}_j^{\text{REINFORCE}}=-r_j\cdot\nabla_{\theta}\log p_{\theta}(T_j|[X_{:j};\text{<|startofthought|>}]) \\ ∇θLjREINFORCE=−rj⋅∇θlogpθ(Tj∣[X:j;<|startofthought|>])
该损失函数鼓励模型生成能够改善未来预测的rationales。