← 回首頁
序列解碼（Viterbi + Beam Search）
你有沒有想過,手機輸入法或 AI 是怎麼「一個字接一個字」拼出整句話的?每一步都有好幾個字可挑,如果每次
都只選當下分數最高的那個,很可能一開頭就貪心走岔、整句話都毀了。這頁比較兩種「挑出整串最佳序列」的辦法:
Viterbi 像把所有可能路線的分數全填進一張表、再回頭挑出最好的那條,保證不出錯,但前提是選項數量
有限;Beam Search 則每一步只留下幾個最有希望的候選繼續往下接,放棄「保證最好」換取速度,正是
現在 LLM 生成文字的主流做法。下面你會看到只留 1 個候選的貪心怎麼漏掉全域最優,而留 2 個剛好救回來。
兩者都是在「指數量級的路徑/序列空間」中尋找最佳序列，但取捨不同：Viterbi 靠動態規劃逐格填表——
每個時間步只需保留每個狀態當下的最佳機率與回溯指標，就能保證找到全域最機率的狀態序列，代價是狀態數
必須有限（隱馬可夫模型 HMM）；Beam Search 則放棄「保證最優」，每步只展開所有候選的延伸，依分數排序
後只保留固定寬度 B 個候選（beam）繼續、其餘剪枝丟棄，換取在狀態空間隨長度指數成長、DP 已不可行時
（例如 LLM 逐 token 生成）仍可用線性代價搜尋——但 B 太小可能漏掉全域最優序列，本頁用具體分數表誠實
示範這件事：B=1（greedy 貪婪）確實找不到 B=2 找到、與窮舉一致的全域最優解。
為什麼 AI 時代重要
LLM 生成文字時逐 token 解碼，主流做法正是 beam search（或其退化版 greedy 貪婪，B=1）：每步從詞彙表中
展開候選延伸、依分數（通常是對數機率）排序，只保留固定寬度的候選序列繼續生成；語音辨識要把聲學模型
輸出的一串觀測（音框）對齊回最可能的音素/詞序列，是隱馬可夫模型（HMM）的經典應用，Viterbi 演算法正是
在有限狀態空間裡用動態規劃求解此「強制對齊」問題的標準解法，至今仍是許多語音辨識與詞性標註系統的
核心子程序。
它是 DP 與 BFS/貪婪的混血
Viterbi 是動態規劃（逐格填表 + 回溯重建路徑）在「機率乘積取 max」轉移方程下的特化版本，血緣直通
費波那契/LCS/硬幣找零那類 DP 表 →
動態規劃基礎；
Beam Search 則可視為「只保留部分節點繼續擴展」的受限 BFS——不剪枝（B=∞）就是完整 BFS/窮舉展開，
B=1 則退化為每步只認局部最優的 greedy 貪婪，兩者共用「逐層展開」的搜尋骨架，只是保留候選數不同。
1. Viterbi（隱馬可夫模型動態規劃解碼 + 回溯）
dp[state][t] = max over 前驅狀態 之 dp[prevState][t-1] × trans[prevState][state] × emit[state][obs[t]]：
每一格先比較所有前驅狀態的候選值取最大，記下回溯指標（backpointer），再乘上發射機率填格；t=0 無前驅，
直接以初始分佈 × 發射機率填入。DP 表填滿後比較終態欄（t=T-1）各狀態的值，取最大者的狀態沿
backpointer 逐步往前回溯，重建出全域最機率的狀態序列（bestPath）。
固定資料：經典 2 狀態天氣 HMM（Rainy/Sunny），觀測序列 [walk, clean, shop, walk]（T=4）；
初始分佈 [0.6, 0.4]；轉移矩陣 [[0.7,0.3],[0.4,0.6]]；發射矩陣（欄序 walk/shop/clean）
[[0.1,0.5,0.4],[0.6,0.1,0.3]]。
已計算格數（cells）：0
階段：fill
列 0 = Rainy、列 1 = Sunny（依 V_STATES 順序）；欄 = 時間步 t=0..3（觀測依序
walk/clean/shop/walk）。格值為該狀態於該時間步的 DP 機率（原始乘積，非 log 機率）。
尚未計算的格顯示「∞」：這是 GridRenderer 沿用最短路徑頁面「未知值」的通用佔位符號，
在本頁不代表真的無窮大，只代表該格尚未輪到計算，計算後會被實際機率值覆蓋。藍色外框（active）=
當前計算格；粉紅（pivot）= 候選比較階段被選中的最佳前驅格，或回溯階段當前確認格；
綠色（finalized）= 回溯已確認、屬於最佳路徑的格（更早步驟留下的標記持續保留）。
生產環境的提醒：本例僅 4 步，機率連乘仍在 double 可讀範圍；序列一旦拉長，原始機率連乘會
很快下溢為 0，實務上必須改用 log 機率相加（log(a·b) = log(a) + log(b)）取代直接相乘，本頁為教學
清晰度刻意不做此優化。
暴力枚舉互證（bruteNote）
（宣告幀才會填入）
2. Beam Search（集束搜尋，前綴樹剪枝 + 全域最優對照）
每一步展開所有保留候選（kept）的所有可能延伸（vocab 個 token），依分數降冪排序（同分數以 token
序列字典序為第二鍵）後，只保留前 beamWidth 名（kept）繼續展開，其餘（pruned）捨棄、其後不再有任何
後代節點。本頁主視覺化固定跑 beamWidth=2，展開成一棵前綴樹；greedy（B=1）與窮舉全域最優
（vocab^length 條序列逐一算總分取 max）只用於宣告幀的數值對照，不建圖——因為兩者都只有單一路徑，
沒有「剪枝」可視覺化。
固定資料：詞彙表 4 個 token（A/B/C/D），序列長度 3，分數表 score[step][prevTok][tok] 固定設計為
「greedy（B=1）在 step0 選局部最高分 A，但 A 之後的延伸分數極低，最終總分遠輸給 step0 次高分 B（B
之後的延伸分數極高）」；beam width=2 能同時保留 A、B 兩條前綴，B 分支得以存活並在後續步驟持續勝出。
beam 主視覺化固定跑 B=2。
累計展開數（expansions）：0
階段：init
前綴樹：root（虛擬起點）之下，每個 step 展開的候選皆為新節點，往下一層即延伸一個 token。
橘色（current）= 根節點初始標示；灰色（frontier，本頁 CSS 覆寫）於展開幀表示「剛建立、尚未決定
去留」的候選，於剪枝幀則表示「被剪、確定不再展開」的節點——被剪節點自此之後的所有幀都不會
再長出任何子節點，剪枝是真的丟棄，不是文字宣稱；綠色（finalized）於剪枝幀標示本輪保留的 kept
節點，於宣告幀標示最終獲勝路徑（root→…→最佳葉節點）沿途所有節點。
三方對照：greedy（B=1）vs beam（B=2）vs 窮舉全域最優
Viterbi 靠 DP 窮盡所有狀態組合保證全域最優，Beam Search 靠剪枝換取效率但不保證最優——同屬「在指數量級
路徑空間中搜尋最佳序列」的血緣，只是取捨方向相反 →
動態規劃基礎
序列解碼決定「每一步該選哪個 token」，推測解碼（Speculative Decoding）則是在 token 已選定的解碼流程上
換一個問題：如何用小模型連續猜測候選、大模型一次驗證，換取更少的目標模型呼叫——同屬 LLM 逐 token 解碼
家族，兩者解決不同軸向的問題 →
推測解碼 Speculative Decoding