字符前缀条件化

这是一个系列问题中的第一题，展示了我们在 Cursor 所做工作的一个侧面。

设置

在使用语言模型进行代码补全时，我们通常希望模型生成的补全以用户已输入的内容开头。

然而，现代语言模型处理的是标记（token）序列而非字符，因此如果直接对用户输入进行朴素分词并发送给模型，当用户的插入点（编辑器光标）不在标记边界上时，会得到错误的结果。

因此，我们需要一种算法，在给定字符前缀的条件下对标记序列进行采样，而不是更常见的在给定标记前缀条件下采样。

我们将其称为字符前缀条件化，这是一种在字符前缀条件下对标记序列进行采样的算法。

我们希望从自回归模型 p(s) 指定的分布中采样一个标记序列 s=t1,t2,…,tn，其中

p(s) = p(t_1, t_2, \ldots, t_n) = \prod_{k=1}^n p(t_k | t_1, \ldots, t_{k-1})

并满足约束：s 以字符前缀 P 开头，即 P 是 repr(t1)+repr(t2)+⋯+repr(tn) 的前缀，其中 + 表示字符串连接，repr 将一个标记映射为其所代表的字符。

我们定义 q(s)=p(s∣s starts with P)。找到一种自回归地从 q(s) 采样的方法即可，即对每个 k 从 q(tk∣t1,…,tk−1) 中采样。

你能否构建一个高效的算法，从 q(tk∣t1,…,tk−1) 中采样，并尽量减少对原始语言模型的调用？提供算法描述即可，如能给出实际实现更佳。

欢迎把你的解答发邮件至 problems@cursor.com。

在使用语言模型进行代码补全时，我们通常希望模型生成的补全以用户已输入的内容开头。

因此，我们需要一种算法，在给定字符前缀的条件下对标记序列进行采样，而不是更常见的在给定标记前缀条件下采样。

我们将其称为字符前缀条件化，这是一种在字符前缀条件下对标记序列进行采样的算法。

我们希望从自回归模型 p(s) 指定的分布中采样一个标记序列 s=t1,t2,…,tn，其中

p(s) = p(t_1, t_2, \ldots, t_n) = \prod_{k=1}^n p(t_k | t_1, \ldots, t_{k-1})

并满足约束：s 以字符前缀 P 开头，即 P 是 repr(t1)+repr(t2)+⋯+repr(tn) 的前缀，其中 + 表示字符串连接，repr 将一个标记映射为其所代表的字符。

我们定义 q(s)=p(s∣s starts with P)。找到一种自回归地从 q(s) 采样的方法即可，即对每个 k 从 q(tk∣t1,…,tk−1) 中采样。

在使用语言模型进行代码补全时，我们通常希望模型生成的补全以用户已输入的内容开头。

因此，我们需要一种算法，在给定字符前缀的条件下对标记序列进行采样，而不是更常见的在给定标记前缀条件下采样。

我们将其称为字符前缀条件化，这是一种在字符前缀条件下对标记序列进行采样的算法。

我们希望从自回归模型 p(s) 指定的分布中采样一个标记序列 s=t1,t2,…,tn，其中

p(s) = p(t_1, t_2, \ldots, t_n) = \prod_{k=1}^n p(t_k | t_1, \ldots, t_{k-1})

并满足约束：s 以字符前缀 P 开头，即 P 是 repr(t1)+repr(t2)+⋯+repr(tn) 的前缀，其中 + 表示字符串连接，repr 将一个标记映射为其所代表的字符。

我们定义 q(s)=p(s∣s starts with P)。找到一种自回归地从 q(s) 采样的方法即可，即对每个 k 从 q(tk∣t1,…,tk−1) 中采样。