LLMはほぼチューリングマシン — そう意識するのが使いこなしのコツ ... かも

---

注記: 本記事の調査（各手法や関連研究の裏取り）には、Claude と、そのリサーチ機能を利用しています。

はじめに

LLMを使いこなす上で、タスクに応じてコンテキストにどれだけの情報を積むか、という調整に悩まされます。盛りすぎても薄すぎてもうまくいかない。この根っこをたどると、LLMがステートレスであるという性質に行き着きます。

そして、ステートレスな変換器が外部のメモリ（テープ）に読み書きしながら計算を進める、というこの構造は、計算理論で古くから知られたチューリングマシンとほぼ同じものです。はるか昔に学生時代に教科書で見た、あのテープとヘッドの絵と重なります。

本記事では、この対応関係を改めて確認してみます。結論を先に述べておくと、LLMはほぼチューリングマシンである、と言えます。ただし先に主張の範囲をはっきりさせておきます。チューリングマシンと対応づけるのは、順伝播一回ではなく、トークンを生成してはコンテキストに戻す自己回帰ループ全体です。そして「ほぼ」には、細部の非対称と、有限資源という現実の制約、という二重の意味を持たせています。どこまでが厳密に一致し、どこからがずれるのか、まで含めて整理します。

LLMはステートレスである

まず出発点です。LLMの推論の中核である順伝播（forward pass）は、ざっくり書くと

output = f(input_tokens, weights)

という純粋関数です。同じ入力を入れれば同じ出力が出ます（サンプリングの乱数を除けば）。呼び出しの間に隠れ状態を持ち越しません。

入力（トークン列）と重みだけで出力が決まり、前回の呼び出しの影響は残りません。重みは学習で焼き付けた固定のパラメータで、推論中は書き換わりません。これが土台となる性質です。

ここで「ステートレス」という言葉を、どのレイヤに対して使っているのかを分けておきます。

レイヤ	状態
順伝播（一回の関数評価）	持たない（純粋関数）
自己回帰ループ	内部には持たない。状態はすべてコンテキスト（テープ）側にある
サービング実装（KVキャッシュ・会話履歴の管理）	持つ。ただしトークン列から決定的に再構成できる写しで、リクエスト境界で破棄される

KVキャッシュは生成を高速化するための一時状態ですが、コンテキストのトークン列から再計算できるため、意味論のレベルではステートレスのままと考えて差し支えありません。チャットで文脈が通じているように見えるのは、毎回の呼び出しで会話ログを丸ごとコンテキストに入れ直しているからです。

生成の様子を図にすると、こういうループになっています。

冒頭の「コンテキスト量の最適化」という悩みも、元をたどればこの構造から来ています。モデルは毎回この箱に入っているものしか見えないので、何をどれだけ入れるかがそのまま性能を左右するわけです。

かつては状態を持ち越していた — RNN/LSTM

このステートレス性は、最初からそうだったわけではありません。

かつて主流だったRNN/LSTMは、隠れ状態ベクトル h をトークンごとに更新して持ち越していました。

h_t = g(h_{t-1}, x_t)

一つ前の状態 h_{t-1} を受け取って次の h_t を作るので、系列を頭から順番に回さないと状態が確定しません。本質的に逐次処理です。

2017年のTransformer（Vaswani et al., "Attention Is All You Need"）が、この recurrence を意図的に取り除きました。狙いは並列学習で、ステートレス化はどちらかというとその副産物です。時間方向の依存を全部 attention に肩代わりさせることで、系列を一気に並列で流せるようにしました。状態を内部に抱えるのをやめた、と言い換えてもよいと思います。

	RNN/LSTM	Transformer
状態の持ち方	内部の隠れ状態 h を持ち越す	内部に持たない（ステートレス）
文脈の参照	h に圧縮された過去	コンテキスト全体を attention で直接参照
学習時の処理	逐次（前から順に）	系列全体を並列

つまりTransformer以降のLLMは、設計として明確に「状態を持たない変換器」の側に振り切っています。この点が、次に見るチューリングマシンとの対応を成り立たせる鍵になります。

チューリングマシンの定義を確認する

チューリングマシン（TM）の定義は次の通りです。

• 有限状態の制御部
• 無限に伸びるテープ
• 遷移関数 δ: (現在状態, 読んだ記号) → (次状態, 書く記号, ヘッド移動)

ここで注目したいのは、δ 自体は純粋関数だということです。制御状態は δ の中に溜め込まれるのではなく、毎ステップ引数として渡され、次の状態が返されるだけです。

もちろん、TMという計算モデルは有限制御部とテープの両方から成ります。ただ、計算能力を無限にしているのはテープの側です。制御部だけを取り出せば有限状態機械（FSM）で、状態数は有限。そこにいくら情報を詰めても有限どまりです。無限に伸びるテープがあって、初めてチューリング完全になります。

両者は対応している

先ほどのLLMの生成ループの図と、TMの図を見比べてください。矢印の形がまったく同じです。対応関係を表にするとこうなります。

チューリングマシン	LLM
遷移関数 δ（純粋関数）	固定された重みによる一回の順伝播
テープ	コンテキスト
ヘッドで記号を読む	コンテキストを入力に食わせる
テープに書く／ヘッドを進める	トークンを生成して末尾に追記
制御部（有限状態）	順伝播（固定深さの計算）

自己回帰生成、つまりトークンを一つ吐いてそれを文脈に戻す行為が、「テープに書いてヘッドを進める」に相当します。固定された δ（変わらない重み）を何度も適用しながら、テープ（コンテキスト）を伸ばしていくわけです。

固定された変換を何度も適用しつつ、状態そのものは外側の系列に書き出していく。状態を内側に閉じ込めず、外のテープに預けている。この構図はTMとLLMで共通しています。

細かく見れば違いもある

もっとも、細部まで同じというわけではありません。「ほぼ」と書いた理由の一つ目はここにあります。

• 書き込みは追記専用です。TMはテープの任意のマスを書き換えられ、ヘッドを左右どちらにも動かせますが、LLMは末尾に足すことしかできず、一度書いたトークンを消せません
• 読み出しは逆にTMより強力です。TMのヘッドは一度に1マスしか読めませんが、attention はテープ全体を毎ステップまとめて参照します
• 持ち越される制御状態がそもそもありません。TMは有限とはいえ制御部の状態をステップ間で持ち越しますが、LLMは状態に相当する情報まで全部テープ側に書き出しています。ある意味、TMより徹底したテープ依存です

それでも「状態を持たない変換器＋外部テープ」という骨格は共通です。この対応がどこまで理論で裏づけられるのかは、後の節で確認します。

だから Chain-of-Thought が効く

この対応が見えていると、chain-of-thought がなぜ効くのかについて、有力な説明の一つが自然に得られます。

一回の順伝播は深さが固定された計算なので、深い逐次計算を一発ではこなせません。ところが「考えを声に出す」＝途中結果をトークン列として書き出すと、それがテープになります。同じ変換を何度も適用して、逐次計算をテープの上で展開できるのです。

計算能力は一回の順伝播の中にあるのではなく、テープ＝トークン列の側に宿っています。これはTMで「制御部は有限でも、計算能力の源はテープ」なのとまったく同じ構図です。CoTは、一発の計算の非力さをテープの長さで補っている、と読めます。

実証面でも、この見方はよく整合します。途中の計算をスクラッチパッドとして書き出させると多段計算の精度が大きく上がること（Nye et al., 2021）、CoTプロンプティングが推論課題の性能を大きく改善すること（Wei et al., 2022）が報告されています。

理論的な裏付けと、現実の但し書き

以上は比喩にとどまらず、理論的にも裏づけがあります。ただし、定理の建付けには注意が要ります。

まず古典的な結果として、Pérez らの研究（"On the Turing Completeness of Modern Neural Network Architectures", 2019 / JMLR版 "Attention is Turing-Complete", 2021）は、Transformer がチューリング完全であることを示しました。この証明が置く理想化は、生成列（テープに相当）を必要なだけ延長できること、数値が任意精度であること、attention が hardmax（hard attention）であること、です。一方で論文自身の整理では、この完全性は外部メモリ装置を追加せず、内部の密な表現と自己回帰的な生成だけで達成される点が強調されています。つまりこの定理は、「コンテキスト＝外部テープ」という本記事の絵をそのまま証明したものではない、という点は正直に言っておくべきでしょう。

本記事の絵に直接対応する理論は、むしろ prompting の側にあります。Qiu らの研究（"Ask, and it shall be given: On the Turing completeness of prompting", ICLR 2025）は、ある有限サイズの decoder-only Transformer に対して、計算したい関数ごとに適切なプロンプトを与え、CoT で中間ステップを書き出させることで、任意の計算可能関数を計算できること——つまり prompting のチューリング完全性——を示しました。固定された δ（重み）に対し、プロンプトで「どのTMを走らせるか」を指定し、生成列をテープとして使う。まさに本記事の対応表の構図です。CoT を計算資源として明示的に扱う表現力の理論（Merrill & Sabharwal, ICLR 2024）も整備されてきており、「能力はテープに宿る」という描像は理論の言葉でも語れるようになっています。

そのうえで、理想化と現実には次のギャップがあります。「ほぼ」の二つ目の出どころです。

	理論の仮定	現実のデプロイ
テープ（生成列／コンテキスト）	必要なだけ延長できる	固定長の窓
数値精度	無限（任意精度）	有限（浮動小数点）
attention	hardmax（Pérez らの証明）	softmax
計算モデルとしての正体	チューリング完全	巨大なFSM

有限テープのTMは、取りうる構成が有限個しかないので結局 FSM に落ちます。だから実機のLLMは「途方もなく状態数の多い有限状態機械」であって、厳密にはチューリングマシンそのものではありません。無限テープという理想を外した瞬間、教科書のTMからは一段降りてしまいます。

さらに一回の順伝播だけを見ると、これはかなり弱い計算クラスに入ります。Merrill と Sabharwal は、log精度のTransformerが uniform TC⁰（定数深さの回路で解けるクラス）でシミュレートできることを示しています。これは log精度という特定の理論化の下での上界であり、実機の順伝播一般に無条件で貼れるラベルではありませんが、「一発の計算は浅い並列計算のクラスに収まる」という方向感を与えてくれます。逐次計算のパワーは、あくまでトークンを吐いてループを回すところから出てくるのです。

なお、この種の議論では「何を固定し、何を伸ばせる資源とみなすか」で結論が変わります。モデルと窓を完全に固定すればFSMですし、生成列を資源として伸ばせるとみなせばチューリング完全側の議論になります。LLM単体の能力とコンテキスト管理の設計は切り分けて考える必要がある、という点は押さえておきたいところです。

使いこなしのコツは「良いテープを作る」こと

ここまでの見方を実務に落とすと、シンプルな結論が出ます。モデル（δ＝重み）は固定されていて、利用者が触れません。動かせる変数はテープの中身だけです。したがって、良い答えが得やすいテープをどう組むか、が使いこなしの本体になります。

意識するとよい軸を整理します。

• 何を載せるか。無関係な記号はヘッド（attention）の邪魔にしかなりません。エラーログを全文貼るより、エラーメッセージと該当箇所だけに絞る。テープはノイズが少ないほど良いです
• どこに載せるか。位置で効きが変わります。系列の先頭と末尾は効きやすく、長文の中盤は埋もれやすい（lost in the middle と呼ばれる現象）。効かせたい記号は端に置きます
• どの順序で書くか。前提 → 材料 → 問い、の順に積むと、後段の順伝播が読みやすい系列になります
• 途中結果を書く余白を残すか。答えだけを急かすとテープに展開できず、一発の順伝播の弱さがそのまま出ます。「まず方針を書いてから」と促すのは、テープを作業領域として使わせる指示です

エンジニアリング的に一番効くのは、テープを使い捨てないことです。1本のテープで延々粘るより、迷走してきたら要点を書き出して、きれいなテープに載せ替える。エージェントに中間生成物をファイルへ書き出させるのも、有限窓の外へテープを延長する行為です。

プロンプトエンジニアリングと呼ばれている工夫の多くは、煎じ詰めれば「有限テープに何をどう書くか」の最適化だった、と捉え直せます。この視点があると、個々のテクニックが場当たりのノウハウではなく、一つの原理から導かれるものとして見えてきます。

小さいモデルでも、テープで補えるのか

ここで自然にわいてくる疑問があります。δ（重み）が固定で触れないなら、いっそ小さくて弱いモデルでも、テープ側でがんばれば何とかなるのではないか、と。答えは「半分はイエス、ただし明確な天井がある」です。テープで稼げる方向と、稼げない方向を分けると本質が見えます。

	内容	小さいモデルでも効くか
テープで稼げる（逐次計算の深さ）	CoTで途中結果を書きながら回し、実効的な計算ステップ数を増やす	効く
テープで稼げる（知識）	重みに無い事実をRAGでテープに載せて補う	効く
テープで稼げる（手本）	in-contextの例示で解き方を示す	効く
テープで稼げない（1ステップの質）	δそのもの、つまり順伝播1回の正確さ	効かない（天井）

稼げる側は、いま流行りの test-time compute（推論により長いテープを使わせて性能を上げる路線）そのものです。「小さいモデル＋良い足場」が「大きいモデル＋素のプロンプト」に迫る、という現象は実際に起きています。

問題は稼げない側です。テープをどう工夫しても、δ（1ステップの質）は上がりません。ここが天井です。1ステップあたりの誤り率を p とすると、n ステップの計算が最後まで通る確率はざっくり (1−p)ⁿ で、誤差は積もっていきます。δが弱いモデルは p が高いので、テープで深さを伸ばすほど、むしろ早い段階で破綻します。多桁掛け算がまさにこれで、途中式を書かせても桁を増やせばいずれ崩れるのは、1桁ぶんの誤りが積み上がるからです。

理論と実機のギャップもここに出ます。先に挙げた Qiu らの「プロンプトはチューリング完全」は、字面だけ見ると「小さいδでもテープで何でもできる」に読めます。しかしあの定理は、モデルが指示された1ステップを毎回正確に実行できることを前提にしています。実機の小さすぎるモデルはその前提が崩れるので、理論上の万能性はそのまま出てきません。

この構図は多サイクル展開に置き換えると腹落ちしやすいはずです。浅い組み合わせ論理を、複数サイクルに分けて回すことで大きな計算を稼ぐ。1サイクルぶんのロジックが正しければ、サイクル数（＝テープ長）で規模を稼げます。ところがそのロジックにバグや精度不足があると、サイクルを回すほど誤差が伝播して悪化する。テープはサイクル数を増やしてくれるだけで、ロジックそのもの（δ）を直してはくれません。

さらにテープ側にもコストがあります。attention は系列長に対して二乗で効くので長いテープは重く遅い、長文の中盤は埋もれやすい（lost in the middle）、そもそも窓の上限もある。無限に盛れるわけではありません。

結論はこうです。「1ステップを確実にこなせる」という閾値を超えているモデルなら、テープ側の工夫（CoT・RAG・足場・外部ツール）で相当な底上げができます。けれど閾値を下回る小さすぎるδは、テープでは救えません。良いテープは万能の魔法ではなく、まともなδがあって初めて効く増幅器、という位置づけになります。

まとめ

改めて整理すると、LLMはほぼチューリングマシンである、と言えます。

• 順伝播はステートレスな純粋関数で、TMの遷移関数 δ に対応します
• コンテキストがテープ、自己回帰生成が「書き込み＋ヘッド移動」に対応します
• 逐次計算の能力は一回の順伝播ではなくトークン列＝テープに宿ります。CoTの有効性はこの見方とよく整合します
• 理想化の下で Transformer はチューリング完全です（Pérez et al.）。さらに、固定された有限サイズのモデルにプロンプトで対象関数を指定する形の完全性も示されています（Qiu et al.）
• ただし現実は有限テープ＋有限精度なので、実体は巨大なFSMです。一回の順伝播は（log精度という理論化の下で）TC⁰ に収まります

「ほぼ」の中身は二つです。一つは細部の非対称（追記専用の書き込み、全テープを見る読み出し、制御状態の不在）。もう一つは現実の制約で、有限テープ＋有限精度のため実体は巨大なFSMであり、理論の完全性はあくまで資源を伸ばせるとみなした理想化の下での話だという点です。それでも骨格は明確にチューリングマシンのそれです。

コンテキストに何をどれだけ積むか、という日々の実務的な問いは、突き詰めれば「有限のテープに何を書いておくか」というチューリングマシンの問題そのものです。実際、普段なんとなくやっているテクニックの多くは、テープの言葉にきれいに翻訳できます。

実務でよくやること	テープの言葉に翻訳すると
エラーログ全文ではなく、エラーメッセージと該当箇所だけ貼る	有限テープに載せる記号の厳選。無関係な記号はヘッドの邪魔になるだけ
「まず方針を箇条書きにしてから実装して」と指示する	テープを作業領域として使わせる（CoTの明示的な誘発）
会話が長くなって迷走してきたら、要点をまとめて新しいチャットに引き継ぐ	ノイズだらけのテープを捨て、要約を書き込んだきれいなテープに交換する
エージェントに中間結果をファイルやメモへ書き出させる	コンテキスト窓の外へのテープの延長
RAGで必要な文書だけをその都度取り込む	必要になった時点で、必要な記号だけをテープに載せる

最後に、すぐ手元で試せる実験を一つ。LLMに桁数の大きい掛け算（3桁×3桁、4桁×4桁……）を、「途中式を書かずに答えだけ」と「筆算の途中式を書きながら」の二通りで解かせて、正答率を比べてみてください。前者は途中結果をテープに書かせない計算、後者はテープに展開しながら進める計算です。桁数を増やしていくと、答えだけの方が先に壊れる桁数が見つかるはずです（思考モードや電卓・コード実行ツールを持つモデルでは、それらを切って試すと差がはっきり出ます）。テープの有無が計算能力そのものを変えることが、体感できると思います。なお、この現象は実証・理論の両面で確認されています。多桁掛け算で直答が先に壊れ、途中式で改善することは Dziri et al.（2023, "Faith and Fate"）が体系的に示しており、定数深さのTransformerが直答では解けない算術を十分な長さのCoTなら解けることは Feng et al.（2023, NeurIPS）が証明しています。

LLMをほぼチューリングマシンとして捉える視点は、単なるアナロジーを超えて、日々の使い方にも効いてくる見方だと思います。

---

Appendix: テスト時計算（test-time compute）─ テープに計算を積む技術

本編では「δ は固定で、動かせるのはテープだけ」という話をしました。この付録では、その「テープ側に計算を積む」を体系立てた考え方、テスト時計算（test-time compute、推論時計算とも）を整理します。

二つの計算軸：学習時と推論時

モデルを賢くする計算には、大きく二つの投じ方があります。一つは学習時計算（train-time compute）で、より大きなモデルをより多くのデータで事前学習する、従来の主軸です。もう一つが推論時計算＝テスト時計算で、学習済みのモデル（δ）はそのままに、一つの問いに答えるときの計算量を増やして質を上げます。本編の言葉に直せば、前者は δ を作り込む投資、後者はテープ側で稼ぐ投資です。

Snell らの研究（2024, arXiv:2408.03314）は、この後者を体系的に分析し、テスト時計算をうまく配分すれば、単純にパラメータを増やすより効果的な場合があると示しました。鍵は「難しさに応じて配分する」ことで（compute-optimal）、簡単な問いには少なく、難しい問いには多く計算を割り当てます。彼らの報告では、この配分戦略で Best-of-N より4倍以上効率が良くなり、計算量を揃えた比較では、素の小モデルがそれなりに解ける問題では、14倍大きいモデルを上回ることもありました。

手法は三系統に分かれる

テスト時計算の手法は、テープの使い方で三つに整理できます。

一つ目は、逐次に深く伸ばす系です。chain-of-thought で思考をトークン列として展開させるやり方で、いわゆる推論特化モデル（OpenAI の o1 系、DeepSeek R1、Claude の拡張思考など）がこれに当たります。DeepSeek R1（2025, arXiv:2501.12948）は、強化学習で長い思考を引き出す訓練を行い、公開モデルながら o1 に匹敵する数学・コード性能を示しました。テープに思考を長く書くほど質が上がる、というのがこの系統です。

二つ目は、並列に広く試す系です。同じ問いに何通りも答えさせて選ぶやり方で、代表が self-consistency（Wang ら, 2022）です。複数の思考を独立に生成し、最終的な答えの多数決を取ります。PaLM-540B では、貪欲な CoT に対し GSM8K で約18ポイント改善したと報告されています。検証器（報酬モデル）で一番良い候補を選ぶのが Best-of-N で、古くは Cobbe ら（2021）が GSM8K 向けに検証器を訓練する形で導入しました。

三つ目は、木で分岐を探索する系です。途中の枝分かれを評価しながら探索する Tree of Thoughts（Yao ら, 2023）が代表で、GPT-4 の Game of 24 では、CoT の4%に対し74%まで正答率が上がりました。モンテカルロ木探索（MCTS）を組み合わせる手法（rStar-Math など）もこの系統です。

これらに加え、検証結果で直す反復系もあります。自己批評で反復改善する Self-Refine（Madaan ら, 2023）や、続編で扱ったコーディングハーネスのように、テストやコンパイラの結果を戻して修正させる自己修正ループです。

一覧にまとめます。

手法	仕組み	計算の向き	外部検証器	代表研究
CoT / 推論特化モデル	思考をトークン列に展開する	逐次	不要	Wei 2022；o1；DeepSeek R1 2025
Self-Consistency	複数の思考を多数決で集約	並列	不要（多数決）	Wang 2022
Best-of-N	N個生成し検証器で選抜	並列	要（報酬モデル等）	Cobbe 2021
Tree of Thoughts	分岐を評価しながら探索	木探索	要（評価器）	Yao 2023
MCTS 系	木探索 ＋ 価値推定	木探索	要（価値・報酬）	rStar-Math 他
Self-Refine	自己批評で反復改善	逐次（反復）	任意	Madaan 2023
ツールの自己修正ループ	test / compile 結果で直す	逐次（反復）	要（テスト等）	続編のハーネス

検証器の質がすべてを決める

並列系や反復系の多くは「候補を出して、良いものを選ぶ／直す」という形なので、選ぶ側＝検証器の質が効いてきます。検証器には二種類あり、最終結果だけで採点する結果報酬モデル（ORM）と、途中の各ステップを採点する過程報酬モデル（PRM）です。Lightman らの研究（2023, "Let's Verify Step by Step"）は、難しい MATH データセットで、過程を監督する PRM が結果だけの ORM を大きく上回ることを示しました。誤りの位置を細かく指摘できるぶん、フィードバックが精密になるためです。

ここで注意したいのが、生成と選択のギャップです。Brown らの研究（2024, "Large Language Monkeys"）は、サンプル数を増やすと「少なくとも1個は正解を含む」割合（カバレッジ）が対数的に伸び続ける一方、正解を自動で選び出す能力はそれに追いつかない、と示しました。完璧な検証器が無いと、たくさん当たりを引いても、当たりを選べない。検証器が弱ければ、テスト時計算は「検証を通るが間違っている答え」に収束してしまいます。これは続編で書いた「スコアボードの質が自己修正の質になる」と同じ話です。

効きには天井がある

テスト時計算は万能ではありません。本編・続編の但し書きが、ここでもそのまま効いてきます。

まず誤りの蓄積です。1ステップの誤り率を p とすると、n ステップが最後まで通る確率はざっくり (1−p)ⁿ で、思考を長く伸ばすほど誤差は積もります。多桁掛け算で、途中式を書かせても桁を増やせばいずれ壊れるのが典型例です（Dziri ら, 2023）。定数深さの Transformer が直答では解けない算術を、十分な長さの CoT なら解ける、という理論的な裏づけもあります（Feng ら, 2023）が、裏を返せば、必要な思考長は問題の難しさとともに伸び、どこかで有限のテープや誤り率に阻まれます。

次にコストです。self-consistency の改善は、サンプルを増やしても k が10〜15あたりで頭打ちになりやすいと報告されています。新しい思考が既存の経路と重なりだすためです。テープを長くすれば attention のコストは系列長の二乗で増え、中盤は埋もれやすく（lost in the middle、Liu ら 2023）、窓の上限もあります。伸ばすほど良い、ではなく、逓減していきます。

実務的な含意

テスト時計算のいちばんの効用は、コストと質のトレードオフを推論時に動かせることです。難しい問いには計算を厚く、簡単な問いには薄く、と配分できる（compute-optimal の考え方）。そして続編で見たコーディングハーネスは、この「生成して、検証して、直す」を人手を介さず自動で回す装置でした。

本編の枠組みで言えば、テスト時計算は「δ は固定のまま、テープ側の作業を増やして質を上げる」技術の総称です。長く考える・広く試す・検証して直す、という三つの形はどれも、浅い一発の順伝播をテープの上で補うための手立てでした。良いテープは、まともな δ があって初めて効く増幅器。テスト時計算は、その増幅器をどう賢く回すか、という工学だと言えます。

参考文献

• Wei et al. (2022) Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. arXiv:2201.11903
• Wang et al. (2022) Self-Consistency Improves Chain of Thought Reasoning in Language Models. arXiv:2203.11171
• Cobbe et al. (2021) Training Verifiers to Solve Math Word Problems. arXiv:2110.14168
• Lightman et al. (2023) Let's Verify Step by Step. arXiv:2305.20050
• Yao et al. (2023) Tree of Thoughts: Deliberate Problem Solving with Large Language Models. arXiv:2305.10601
• Madaan et al. (2023) Self-Refine: Iterative Refinement with Self-Feedback. arXiv:2303.17651
• Snell et al. (2024) Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters. arXiv:2408.03314
• Brown et al. (2024) Large Language Monkeys: Scaling Inference Compute with Repeated Sampling. arXiv:2407.21787
• DeepSeek-AI (2025) DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning. arXiv:2501.12948
• Liu et al. (2023) Lost in the Middle: How Language Models Use Long Contexts. arXiv:2307.03172
• Dziri et al. (2023) Faith and Fate: Limits of Transformers on Compositionality. NeurIPS 2023
• Feng et al. (2023) Towards Revealing the Mystery behind Chain of Thought. NeurIPS 2023