Decoding
Issue Date: 2025-10-12 [Paper Note] DeepPrune: Parallel Scaling without Inter-trace Redundancy, Shangqing Tu+, arXiv'25, 2025.10 GPT Summary- DeepPruneという新しいフレームワークを提案し、並列スケーリングの計算非効率を解決。80%以上の推論トレースが同一の回答を生成する問題に対処し、焦点損失とオーバーサンプリング技術を用いた判定モデルで同等性を予測。オンラインの貪欲クラスタリングで冗長な経路をプルーニングし、80%以上のトークン削減を達成しつつ、精度を維持。効率的な並列推論の新基準を確立。 Comment
pj page: https://deepprune.github.io
HF: https://huggingface.co/collections/THU-KEG/deepprune-68e5c1ea71f789a6719b2c1c
元ポスト:
#Pocket #NLP #Search #LanguageModel #Reasoning #Test-Time Scaling #TreeSearch
Issue Date: 2025-10-08 [Paper Note] MITS: Enhanced Tree Search Reasoning for LLMs via Pointwise Mutual Information, Jiaxi Li+, arXiv'25, 2025.10 GPT Summary- 相互情報量ツリー探索（MITS）を提案し、推論経路の評価と探索を効率化。PMIに基づくスコアリング関数を用い、計算コストを抑えつつ優れた推論性能を実現。エントロピーに基づく動的サンプリング戦略でリソースを最適配分し、重み付き投票方式で最終予測を行う。MITSは多様なベンチマークでベースラインを上回る結果を示した。 Comment
元ポスト:
#EfficiencyImprovement #Pocket #NLP #LanguageModel #DiffusionModel
Issue Date: 2025-10-06 [Paper Note] Free Draft-and-Verification: Toward Lossless Parallel Decoding for Diffusion Large Language Models, Shutong Wu+, arXiv'25, 2025.09 GPT Summary- Diffusion Large Language Models (DLLMs)は、双方向の注意メカニズムにより文脈を捉える能力が高いが、推論効率が自己回帰モデルに劣る。既存の並列デコーディングアルゴリズムは性能低下を伴う。これを解決するために、損失のない並列デコーディングを実現する新しいアルゴリズム「Free Draft-and-Verification（Freedave）」を提案。Freedaveにより、DLLMsのスループットは数学的推論タスクで最大2.8倍向上する。 Comment
元ポスト:
元ポスト:
#Pocket #NLP #LanguageModel #Evaluation #NAACL #Non-Determinism Issue Date: 2025-09-09 [Paper Note] The Good, The Bad, and The Greedy: Evaluation of LLMs Should Not Ignore Non-Determinism, Yifan Song+, NAACL'25 GPT Summary- LLMの評価は非決定性を見落としがちで、単一出力に焦点を当てるため性能の変動理解が制限される。本研究では、貪欲デコーディングとサンプリングの性能差を探求し、非決定性に関するベンチマークの一貫性を特定。実験により、貪欲デコーディングが多くのタスクで優れていることを確認し、アライメントがサンプリングの分散を減少させる可能性を示した。また、小型LLMが大型モデルに匹敵する性能を持つことを明らかにし、LLM評価における非決定性の重要性を強調した。 Comment
関連:
- Non-Determinism of "Deterministic" LLM Settings, Berk Atil+, arXiv'24
利用されているデータセット:
- [Paper Note] Are We Done with MMLU?, Aryo Pradipta Gema+, NAACL'25
- AlpacaEval, tatsu-lab, 2023.06
- [Paper Note] MixEval: Deriving Wisdom of the Crowd from LLM Benchmark Mixtures, Jinjie Ni+, NeurIPS'24
- From Live Data to High-Quality Benchmarks: The Arena-Hard Pipeline, Li+, 2024.04
- Training Verifiers to Solve Math Word Problems, Karl Cobbe+, arXiv'21
- [Paper Note] Evaluating Large Language Models Trained on Code, Mark Chen+, arXiv'21
#EfficiencyImprovement #Pocket #NLP #LanguageModel #RAG(RetrievalAugmentedGeneration) #LongSequence #read-later #Selected Papers/Blogs #SpeculativeDecoding Issue Date: 2025-09-07 [Paper Note] REFRAG: Rethinking RAG based Decoding, Xiaoqiang Lin+, arXiv'25 GPT Summary- REFRAGは、RAGアプリケーションにおける遅延を改善するための効率的なデコーディングフレームワークであり、スパース構造を利用して初回トークンまでの時間を30.85倍加速します。これにより、LLMsのコンテキストサイズを16まで拡張可能にし、さまざまな長コンテキストタスクで精度を損なうことなくスピードアップを実現しました。 Comment
元ポスト:
興味深い。Speculative Decodingの新手法ともみなせそう。
同時期に出た下記研究と比較してどのようなpros/consがあるだろうか？
- [Paper Note] Set Block Decoding is a Language Model Inference Accelerator, Itai Gat+, arXiv'25
解説:
#EfficiencyImprovement #Pocket #NLP #read-later Issue Date: 2025-09-05 [Paper Note] Set Block Decoding is a Language Model Inference Accelerator, Itai Gat+, arXiv'25 GPT Summary- Set Block Decoding（SBD）を提案し、次トークン予測とマスクトークン予測を統合して生成を加速。SBDは複数の未来のトークンを並行してサンプリング可能で、従来の手法よりも速度向上を実現。アーキテクチャ変更なしで既存モデルをファインチューニングし、フォワードパスの数を3-5倍削減しつつ同等のパフォーマンスを達成。 Comment
元ポスト:
#EfficiencyImprovement #Controllable #Pocket #NLP #Search #LanguageModel #Test-Time Scaling Issue Date: 2025-08-30 [Paper Note] Skip a Layer or Loop it? Test-Time Depth Adaptation of Pretrained LLMs, Ziyue Li+, arXiv'25 GPT Summary- 事前学習済みのLLMの層をモジュールとして操作し、各サンプルに最適なアーキテクチャを構築する手法を提案。モンテカルロ木探索を用いて、数学および常識推論のベンチマークで最適な層の連鎖（CoLa）を特定。CoLaは柔軟で動的なアーキテクチャを提供し、推論効率を改善する可能性を示唆。75%以上の正しい予測に対して短いCoLaを見つけ、60%以上の不正確な予測を正すことができることが明らかに。固定アーキテクチャの限界を克服する道を開く。 Comment
解説:
事前学習済み言語モデルのforward pathにおける各layerをbuilding blocksとみなして、入力に応じてスキップ、あるいは再帰的な利用をMCTSによって選択することで、test time時のモデルの深さや、モデルの凡化性能をタスクに対して適用させるような手法を提案している模様。モデルのパラメータの更新は不要。k, r ∈ {1,2,3,4} の範囲で、"k個のlayerをskip"、あるいはk個のlayerのブロックをr回再帰する、とすることで探索範囲を限定的にしtest時の過剰な計算を抑止している。また、MCTSにおけるsimulationの回数は200回。length penaltyを大きくすることでcompactなforward pathになるように調整、10%の確率でまだ探索していない子ノードをランダムに選択することで探索を促すようにしている。オリジナルと比較して実行時間がどの程度増えてしまうのか？に興味があったが、モデルの深さという観点で推論効率は考察されているように見えたが、実行時間という観点ではざっと見た感じ記載がないように見えた。
<img width="948" height="301" alt="Image" src="
<a href="https://github.com/user-attachments/assets/0a03cdc2-141b-40a1-a11e-9560187ff7b6"" target="_blank" rel="noopener noreferrer">https://github.com/user-attachments/assets/0a03cdc2-141b-40a1-a11e-9560187ff7b6"</a>
/>
以下の広範なQA、幅広い難易度を持つ数学に関するデータで評価（Appendix Bに各データセットごとに500 sampleを利用と記載がある）をしたところ、大幅に性能が向上している模様。ただし、8B程度のサイズのモデルでしか実験はされていない。
- [Paper Note] Think you have Solved Question Answering? Try ARC, the AI2 Reasoning
Challenge, Peter Clark+, arXiv'18
- [Paper Note] DART-Math: Difficulty-Aware Rejection Tuning for Mathematical Problem-Solving, Yuxuan Tong+, NeurIPS'24
<img width="986" height="682" alt="Image" src="
<a href="https://github.com/user-attachments/assets/c6d88c0a-4ae0-41b7-8526-17d041692f49"" target="_blank" rel="noopener noreferrer">https://github.com/user-attachments/assets/c6d88c0a-4ae0-41b7-8526-17d041692f49"</a>
/>
関連:
- [Paper Note] Looped Transformers are Better at Learning Learning Algorithms, Liu Yang+, ICLR'24
- [Paper Note] Looped Transformers for Length Generalization, Ying Fan+, ICLR'25
- [Paper Note] Universal Transformers, Mostafa Dehghani+, ICLR'19
- [Paper Note] Mixture-of-Recursions: Learning Dynamic Recursive Depths for Adaptive
Token-Level Computation, Sangmin Bae+, arXiv'25
#Pocket #NLP #LanguageModel #read-later #Selected Papers/Blogs #MajorityVoting Issue Date: 2025-08-24 [Paper Note] Deep Think with Confidence, Yichao Fu+, arXiv'25 GPT Summary- 「Deep Think with Confidence（DeepConf）」は、LLMの推論タスクにおける精度と計算コストの課題を解決する手法で、モデル内部の信頼性信号を活用して低品質な推論を動的にフィルタリングします。追加の訓練や調整を必要とせず、既存のフレームワークに統合可能です。評価の結果、特に難易度の高いAIME 2025ベンチマークで99.9%の精度を達成し、生成トークンを最大84.7%削減しました。 Comment
pj page:
https://jiaweizzhao.github.io/deepconf
vLLMでの実装:
https://jiaweizzhao.github.io/deepconf/static/htmls/code_example.html
元ポスト:
tooluse、追加の訓練なしで、どのようなタスクにも適用でき、85%生成トークン量を減らした上で、OpenModelで初めてAIME2025において99% Acc.を達成した手法とのこと。vLLMを用いて50 line程度で実装できるらしい。
reasoning traceのconfidence(i.e., 対数尤度)をgroup sizeを決めてwindow単位で決定し、それらをデコーディングのプロセスで活用することで、品質の低いreasoning traceに基づく結果を排除しつつ、majority votingに活用する方法。直感的にもうまくいきそう。オフラインとオンラインの推論によって活用方法が提案されている。あとでしっかり読んで書く。Confidenceの定義の仕方はグループごとのbottom 10%、tailなどさまざまな定義方法と、それらに基づいたconfidenceによるvotingの重み付けが複数考えられ、オフライン、オンラインによって使い分ける模様。
vLLMにPRも出ている模様？
#Pocket #NLP #LanguageModel #DiffusionModel #PostTraining Issue Date: 2025-08-22 [Paper Note] Time Is a Feature: Exploiting Temporal Dynamics in Diffusion Language Models, Wen Wang+, arXiv'25 GPT Summary- dLLMsは中間予測を捨てがちだが、時間的振動が重要な現象である。本研究では、時間的一貫性を活用する2つの方法を提案。1つ目は、テスト時に予測を集約する時間的自己一貫性投票、2つ目は中間予測の安定性を測る時間的意味エントロピーを報酬信号とする時間的一貫性強化。実験結果では、Countdownデータセットで24.7%の改善を達成し、他のベンチマークでも向上を示した。これにより、dLLMsの時間的ダイナミクスの可能性が強調される。 Comment
元ポスト:
dLLMのデノイジング過程において途中に正解が表出しているのに時間発展とともに消えてしまう問題があるらしく、それに対して、デノイジングステップにおいてstableな予測を行うSelf-Consistencyベースのdecoding手法と、意味的なエントロピーをrewardに加え時間発展で安定するようにpost trainingすることで対処します、みたいな話らしい。
#NeuralNetwork #MachineTranslation #Pocket #NLP #LanguageModel #ACL Issue Date: 2025-07-20 [Paper Note] Unveiling the Power of Source: Source-based Minimum Bayes Risk Decoding for Neural Machine Translation, Boxuan Lyu+, ACL'25 GPT Summary- ソースベースのMBRデコーディング（sMBR）を提案し、パラフレーズや逆翻訳から生成された準ソースを「サポート仮説」として利用。参照なしの品質推定メトリックを効用関数として用いる新しいアプローチで、実験によりsMBRがQE再ランキングおよび標準MBRを上回る性能を示した。sMBRはNMTデコーディングにおいて有望な手法である。 Comment
元ポスト:
#Analysis #Pretraining #Pocket #DiffusionModel #ICML Issue Date: 2025-07-15 [Paper Note] Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions, Jaeyeon Kim+, ICML'25 GPT Summary- マスク付き拡散モデル（MDMs）は、自己回帰モデル（ARMs）と比較してトレーニングの複雑さと推論の柔軟性をトレードオフする新しい生成モデルです。本研究では、MDMsが自己回帰モデルよりも計算上解決不可能なサブ問題に取り組むことを示し、適応的なトークンデコード戦略がMDMsの性能を向上させることを実証しました。数独の論理パズルにおいて、適応的推論により解決精度が$<7$%から$\approx 90$%に向上し、教師強制でトレーニングされたMDMsがARMsを上回ることを示しました。 Comment
openreview: https://openreview.net/forum?id=DjJmre5IkP
ICML'25 outstanding papers
日本語解説:
#EfficiencyImprovement #Pocket #NLP #LanguageModel #ICLR #Test-Time Scaling #Verification #SpeculativeDecoding Issue Date: 2025-05-13 Faster Cascades via Speculative Decoding, Harikrishna Narasimhan+, ICLR'25 GPT Summary- カスケードと推測デコーディングは、言語モデルの推論効率を向上させる手法であり、異なるメカニズムを持つ。カスケードは難しい入力に対して大きなモデルを遅延的に使用し、推測デコーディングは並行検証で大きなモデルを活用する。新たに提案する推測カスケーディング技術は、両者の利点を組み合わせ、最適な遅延ルールを特定する。実験結果は、提案手法がカスケードおよび推測デコーディングのベースラインよりも優れたコスト品質トレードオフを実現することを示した。 Comment
元ポスト:
OpenReview: https://openreview.net/forum?id=vo9t20wsmd
#Pocket #NLP #LanguageModel #Evaluation #Selected Papers/Blogs #Non-Determinism Issue Date: 2025-04-14 Non-Determinism of "Deterministic" LLM Settings, Berk Atil+, arXiv'24 GPT Summary- 本研究では、5つの決定論的LLMにおける非決定性を8つのタスクで調査し、最大15%の精度変動と70%のパフォーマンスギャップを観察。全てのタスクで一貫した精度を提供できないことが明らかになり、非決定性が計算リソースの効率的使用に寄与している可能性が示唆された。出力の合意率を示す新たなメトリクスTARr@NとTARa@Nを導入し、研究結果を定量化。コードとデータは公開されている。 Comment
- 論文中で利用されているベンチマーク:
- Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models, Aarohi Srivastava+, N/A, TMLR'23
- Measuring Massive Multitask Language Understanding, Dan Hendrycks+, N/A, ICLR'21
同じモデルに対して、seedを固定し、temperatureを0に設定し、同じ計算機環境に対して、同じinputを入力したら理論上はLLMの出力はdeterministicになるはずだが、deterministicにならず、ベンチマーク上の性能とそもそものraw response自体も試行ごとに大きく変化する、という話。
ただし、これはプロプライエタリLLMや、何らかのinferenceの高速化を実施したInferenceEngine（本研究ではTogetherと呼ばれる実装を使っていそう。vLLM/SGLangだとどうなるのかが気になる）を用いてinferenceを実施した場合での実験結果であり、後述の通り計算の高速化のためのさまざまな実装無しで、deterministicな設定でOpenLLMでinferenceすると出力はdeterministicになる、という点には注意。
GPTやLlama、Mixtralに対して上記ベンチマークを用いてzero-shot/few-shotの設定で実験している。Reasoningモデルは実験に含まれていない。
<img width="701" height="325" alt="Image" src="
<a href="https://github.com/user-attachments/assets/b33f14d8-ed86-4589-a427-18a70b35d61a"" target="_blank" rel="noopener noreferrer">https://github.com/user-attachments/assets/b33f14d8-ed86-4589-a427-18a70b35d61a"</a>
/>
LLMのraw_response/multiple choiceのparse結果（i.e., 問題に対する解答部分を抽出した結果）の一致（TARr@N, TARa@N; Nはinferenceの試行回数）も理論上は100%になるはずなのに、ならないことが報告されている。
<img width="712" height="432" alt="Image" src="
<a href="https://github.com/user-attachments/assets/3159ff26-fc92-4fa8-90a6-f8c5e7ccf20e"" target="_blank" rel="noopener noreferrer">https://github.com/user-attachments/assets/3159ff26-fc92-4fa8-90a6-f8c5e7ccf20e"</a>
/>
correlation analysisによって、応答の長さ と TAR{r, a}が強い負の相関を示しており、応答が長くなればなるほど不安定さは増すことが分析されている。このため、ontput tokenの最大値を制限することで出力の安定性が増すことを考察している。また、few-shotにおいて高いAcc.の場合は出力がdeterministicになるわけではないが、性能が安定する傾向とのこと。また、OpenAIプラットフォーム上でGPTのfinetuningを実施し実験したが、安定性に寄与はしたが、こちらもdeterministicになるわけではないとのこと。
deterministicにならない原因として、まずmulti gpu環境について検討しているが、multi-gpu環境ではある程度のランダム性が生じることがNvidiaの研究によって報告されているが、これはseedを固定すれば決定論的にできるため問題にならないとのこと。
続いて、inferenceを高速化するための実装上の工夫（e.g., Chunk Prefilling, Prefix Caching, Continuous Batching）などの実装がdeterministicなハイパーパラメータでもdeterministicにならない原因であると考察しており、**実際にlocalマシン上でこれらinferenceを高速化するための最適化を何も実施しない状態でLlama-8Bでinferenceを実施したところ、outputはdeterministicになったとのこと。**
論文中に記載がなかったため、どのようなInferenceEngineを利用したか公開されているgithubを見ると下記が利用されていた:
- Together:
https://github.com/togethercomputer/together-python?tab=readme-ov-file
Togetherが内部的にどのような処理をしているかまでは追えていないのだが、異なるInferenceEngineを利用した場合に、どの程度outputの不安定さに差が出るのか（あるいは出ないのか）は気になる。たとえば、transformers/vLLM/SGLangを利用した場合などである。
論文中でも報告されている通り、昔管理人がtransformersを用いて、deterministicな設定でzephyrを用いてinferenceをしたときは、出力はdeterministicになっていたと記憶している（スループットは絶望的だったが...)。
あと個人的には現実的な速度でオフラインでinference engineを利用した時にdeterministicにはせめてなって欲しいなあという気はするので、何が原因なのかを実装レベルで突き詰めてくれるととても嬉しい（KV Cacheが怪しい気がするけど）。
たとえば最近SLMだったらKVCacheしてVRAM食うより計算し直した方が効率良いよ、みたいな研究があったような。そういうことをしたらlocal llmでdeterministicにならないのだろうか。
- Defeating Nondeterminism in LLM Inference, Horace He in collaboration with others at Thinking Machines, 2025.09
においてvLLMを用いた場合にDeterministicな推論をするための解決方法が提案されている。
#BeamSearch #Pocket #NLP #LanguageModel #Reasoning #SelfCorrection #NeurIPS #KeyPoint Notes Issue Date: 2025-10-01 [Paper Note] Self-Evaluation Guided Beam Search for Reasoning, Yuxi Xie+, NeurIPS'23, 2023.05 GPT Summary- LLMの推論プロセスを改善するために、段階的自己評価メカニズムを導入し、確率的ビームサーチを用いたデコーディングアルゴリズムを提案。これにより、推論の不確実性を軽減し、GSM8K、AQuA、StrategyQAでの精度を向上。Llama-2を用いた実験でも効率性が示され、自己評価ガイダンスが論理的な失敗を特定し、一貫性を高めることが確認された。 Comment
pj page: https://guideddecoding.github.io
openreview: https://openreview.net/forum?id=Bw82hwg5Q3
非常にざっくり言うと、reasoning chain（＝複数トークンのsequence)をトークンとみなした場合の（確率的）beam searchを提案している。多様なreasoning chainをサンプリングし、その中から良いものをビーム幅kで保持し生成することで、最終的に良いデコーディング結果を得る。reasoning chainのランダム性を高めるためにtemperatureを設定するが、アニーリングをすることでchainにおけるエラーが蓄積することを防ぐ。これにより、最初は多様性を重視した生成がされるが、エラーが蓄積され発散することを防ぐ。
reasoning chainの良さを判断するために、chainの尤度だけでなく、self-evaluationによるreasoning chainの正しさに関するconfidenceスコアも導入する（reasoning chainのconfidenceスコアによって重みづけられたchainの尤度を最大化するような定式化になる（式3))。
self-evaluationと生成はともに同じLLMによって実現されるが、self-evaluationについては評価用のfew-shot promptingを実施する。promptingでは、これまでのreasoning chainと、新たなreasoning chainがgivenなときに、それが(A)correct/(B)incorrectなのかをmultiple choice questionで判定し、選択肢Aが生成される確率をスコアとする。
#Pocket #NLP #LanguageModel #ICLR #Selected Papers/Blogs Issue Date: 2025-04-14 The Curious Case of Neural Text Degeneration, Ari Holtzman+, ICLR'20 GPT Summary- 深層ニューラル言語モデルは高品質なテキスト生成において課題が残る。尤度の使用がモデルの性能に影響を与え、人間のテキストと機械のテキストの間に分布の違いがあることを示す。デコーディング戦略が生成テキストの質に大きな影響を与えることが明らかになり、ニュークリアスsamplingを提案。これにより、多様性を保ちながら信頼性の低い部分を排除し、人間のテキストに近い質を実現する。 Comment
現在のLLMで主流なNucleus (top-p) Samplingを提案した研究
#Article #EfficiencyImprovement #LanguageModel #python #Blog #LLMServing #SpeculativeDecoding Issue Date: 2025-08-21 vLLMのSpeculative Decodingによる推論高速化を試す, Aratako, 2025.05 #Article #EfficiencyImprovement #NLP #LanguageModel #LLMServing #SpeculativeDecoding Issue Date: 2025-07-24 Speculative Decoding：Faster Inference Without Paying for More GPU, ELYZA, 2025.07