コンテンツへスキップ

文字プレフィックス条件付け

作成者: Jacob Jackson製品

Cursor で取り組んでいる内容を垣間見せる、一連の課題の第1弾です。

セットアップ

コード補完に言語モデルを用いる際、通常はユーザーが既に入力した内容で補完が始まってほしいと考えます。

しかし、最新の言語モデルは文字ではなくトークン列を処理するため、ユーザー入力を安直にトークン化してモデルへ送ると、ユーザーのキャレットがたまたまトークン境界上にない場合に誤った結果になります。

その代わりに、より一般的な「トークンのプレフィックス」に条件付けしてサンプリングするのではなく、文字のプレフィックスに条件付けしてトークン列をサンプリングするアルゴリズムが必要です。

この手法を文字プレフィックス条件付けと呼び、文字プレフィックスに条件付けされたトークン列をサンプリングするアルゴリズムと定義します。

自己回帰モデル p(s) により定まる分布から、トークン列 s=t1,t2,…,tn をサンプリングしたいとします。そのとき

p(s)=p(t1,t2,,tn)=k=1np(tkt1,,tk1)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) と定義します。すなわち各 k について q(tk∣t1,…,tk−1) からサンプリングできれば十分であり、q(s) から自己回帰的にサンプリングする方法を見つければよいことになります。

問題

q(tk∣t1,…,tk−1) から効率的にサンプリングし、元の言語モデルへの呼び出し回数を最小化するアルゴリズムを構成できますか?アルゴリズムの説明でも構いません。実装があるとなお良いです。

解法は problems@cursor.com までお気軽にメールしてください。

カテゴリー: 製品

著者: Jacob Jackson