這是一系列問題的第一題，帶你一窺我們在 Cursor 的工作。

設定

使用語言模型進行程式碼補全時，我們通常希望模型產生的補全能以使用者已輸入的內容開頭。

然而，現代語言模型運作於權杖（token）序列而非字元；若直接將使用者輸入進行權杖化並送入模型，當使用者的游標不在權杖邊界上時，可能會產生錯誤結果。

因此，我們需要一個演算法，能在給定字元前綴的條件下取樣一段權杖序列，而不是較常見的「權杖前綴」條件取樣。

我們稱此為字元前綴條件化，一種在字元前綴條件下取樣權杖序列的演算法。

我們希望從自迴歸模型所指定的分佈 p(s) 中取樣一段權杖序列 s=t1,t2,…,tn，其定義為

並需滿足以下限制：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。