この問題に対処するため, 上のコードでは, スライスサンプリングを使って確率的に 候補を減らしています。
スライスサンプリングは, 簡単に言うとNLPでよくある「閾値」を, それ自体確率的にサンプリングすることで, 効率的かつ正確な学習を可能に する方法です。 IBISの武井-牧野君の話ではBeam samplingとしてPCFGに適用していましたが, ここでは 動的計画法が実際上使えないので, 局所的なGibbsに使っています。

HPYLMの場合, nグラムが内部的には1グラム-2グラム-3グラムと樹構造になっています が, スライスがPY過程の「バックオフ係数」にあたる (θ+d*t_u)/(θ+n_u)より大きかった場合, 木を上にバックオフしてもスライスより確率の高い候補は 現れないため, 比較的効率的にサンプリングの候補を計算することができます。

..が, 実際やってみると, 特に名詞が来る位置で, 1グラムまでバックオフして スライスを超える候補を見つける必要があることが多いことがわかりました。
1グラム(木のルート)には全ての単語が存在しているため, スライス s を超える確率 を持った単語を探すためには, ここで数万個の候補をなめる必要が生じてしまいます。 ユニグラムが頻度順に並んでいたりすれば枝刈りは容易ですが, LWLMではnグラム自体 がサンプリングされた潜在語によって動的に書き換わるため, そうした静的な性質は 期待できません。

このために, record という特別なデータ構造を用意することに。 岡野原君に相談したところ, ベクトルで順番に持って, 頻度が変更された時に書き換え ればいいのではないかとのこと。(感謝。)
真面目に完全に頻度順にしようとすると, restaurant * が頻度順に 46 32 15 4 4 4 3 3 2 2 [2] 1 1 1 のように並んでいるベクトルで[2]->3になった時 に, 二分探索で最左の3を探し(数字を入れ換えるのではなくて, restaurant * を入れ換える), swap()を実行すればいいですが, 単語の頻度は学習時にもの凄い勢いで増減するので, 二分探索とはいえ, ここ自体が 計算のボトルネックになってしまう可能性があります。 *2

よく考えると, 完全に単語が頻度順に並んでいる必要はなく, 枝刈りができる程度に ソートされていればよいので, 少し考えて, 頻度が 2^n 以下になる境界だけを配列で コンパクトに持つことに。
頻度が1増減する毎に, それが2^nになっているかどうか調べ (これは二の補数表現を使うと, record.cpp の pow2() というトリッキーなコードで 高速に調べられます), 2^nになった/そこから減った場合は swap を行って境界の値を書き換えます。
さらにメタ関数 foreach を書いて, 2^n境界を使って頻度の高い順からアイテムに 関数ポインタで受け取った関数を実行する Lisp 的な関数を定義しました。
正直これを正しく, かつ美しく実装するのに3日かかりました。。(record.cpp)

効果は劇的で, ここまでやって初めて, 語彙の数にそれほど依存せずに高速な学習 ができるようになりました。長かった。。
最近, Phil Blunsomがslice samplingを使って Synchronous grammar の構文木を サンプリングするという話を出しているようですが(NAACL 2010), 莫大な候補から 効率的にサンプリングするという意味では, 似たところがあるかもしれません。

ちなみに, 実はこのコードの売りは, HPYLMの完全な実装が含まれていることかも しれません。 Songfang Huang のページでは, (恐らく彼がIBMに援助されているという事情もあって)ソースは公開 されていないので, これが多分, 現在唯一の公開されているベイズnグラム(HPYLM)の コードなのではないかと思います。
僕はNTTにいるので研究用のコードは公開できませんが, これは(実装に色々工夫が あるとはいえ)他の人の研究なので, 公開できるという感じです。