这是 Cursor 系列问题中的第一个，让您一窥我们在 Cursor 所做的工作。

设置

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

然而，现代语言模型在 token 序列上运行，而不是字符，因此如果用户的光标恰好不在 token 边界上，则简单地对用户输入进行 token 化并将其发送到模型会产生错误的结果。

相反，我们需要一种算法，该算法基于字符前缀对 token 序列进行采样，而不是更典型的基于 token 前缀进行采样的情况。

我们称之为字符前缀条件化，这是一种基于字符前缀对 token 序列进行采样的算法。

我们想要从自回归模型指定的分布中采样 token 序列 $s = t_1, t_2, \ldots, t_n$，该分布由下式给出

受限于约束条件 $s$ 以字符前缀 $\mathcal{P}$ 开头，即 $\mathcal{P}$ 是 $\text{repr}(t_1) + \text{repr}(t_2) + \cdots + \text{repr}(t_n)$ 的前缀，其中 $+$ 表示字符串连接，repr 将 token 映射到它表示的字符。

我们定义 $q(s) = p(s \mid s \text{ starts with } \mathcal{P})$。 找到一种从 $q(s)$ 自回归采样的方法就足够了，也就是从每个 $k$ 的 $q(t_k | t_1, \ldots, t_{k-1})$ 中采样。

问题

你能构建一个高效的算法，用于从 $q(t_k | t_1, \ldots, t_{k - 1})$ 中采样，并最大限度地减少对原始语言模型的调用吗？ 算法的描述很棒。 实际实现更佳。

请随时通过电子邮件将您的解决方案发送至 problems@cursor.com。