I4MediumPart I · Inference, Decoding & Quantization

Beam Search Decoding with Length Penalty

Mastery Status

Industrial-grade implementation and mathematical foundations of Beam Search Decoding with Length Penalty.

⏱️ Time Complexity: O(T * B * V)

💾 Space Complexity: O(B * T)

💡

Core Mental Anchor / Mnemonic

Master Beam Search Decoding with Length Penalty: enforce numerical stability, check tensor shapes, and eliminate redundant memory allocations.

📐 Mathematical Derivation & Core Formula

\mathrm{Score}(y_1, \dots, y_t) = \frac{\sum_{i=1}^t \log P(y_i \mid y_{<i})}{LP(t)}, \quad LP(t) = \frac{(5 + t)^\alpha}{(5 + 1)^\alpha}

### Mathematical Derivation & Theoretical Principles
Detailed first-principles formulation and architectural mechanics for Beam Search Decoding with Length Penalty.

Refer to the LaTeX equation above for the core operator definition. The operator is designed to ensure strict numerical bounds, avoiding floating-point overflows and gradient anomalies.

🔄 Tensor Dimensions & Shape Flow

当前 B 条路径 -> 乘积扩展为 B*V 种可能 -> 计算带 LP 分数 -> 排序取 Top B

🛡️ Industrial Numerical Stability & Pitfalls

Ensure proper multi-dimensional tensor broadcasting and keepdims retention.
Enforce numerical guards (eps clamping and overflow thresholds) during exponentiation and division.
Verify train versus eval mode behavioral distinctions (e.g. frozen running statistics and dropout bypass).

💻 Industrial Code Implementation

import numpy as np

def simple_beam_search_step(
    current_beams: list,        # [(score, [token_ids])] 长度为 B 的当前候选路径
    next_token_log_probs: np.ndarray, # (B, V) 各路径扩展下一词的对数概率
    beam_width: int = 3,
    alpha: float = 0.6
) -> list:
    all_candidates = []
    
    # 遍历当前每条活跃的 Beam
    for b_idx, (prev_score, seq) in enumerate(current_beams):
        log_probs = next_token_log_probs[b_idx] # (V,)
        for token_id, lp in enumerate(log_probs):
            new_seq = seq + [token_id]
            new_raw_score = prev_score + lp
            
            # 计算长度惩罚
            length = len(new_seq)
            lp_factor = ((5.0 + length) / 6.0) ** alpha
            normalized_score = new_raw_score / lp_factor
            
            all_candidates.append((new_raw_score, normalized_score, new_seq))
            
    # 按归一化分数降序排序，仅截取前 beam_width 条
    all_candidates.sort(key=lambda x: x[1], reverse=True)
    best_beams = [(raw, seq) for raw, norm, seq in all_candidates[:beam_width]]
    return best_beams

🧪 Runnable Assertions & Validation

Copy and run directly in Python / Jupyter to verify correctness:

import numpy as np
init_beams = [(0.0, [101])] # [CLS]
# 假设词表大小 3
next_lps = np.array([[-0.1, -2.0, -5.0]])
step1 = simple_beam_search_step(init_beams, next_lps, beam_width=2)
assert len(step1) == 2
# 概率最高的词 0 应排在第 1 位
assert step1[0][1][-1] == 0
print("✓ Beam Search 束搜索自测通过")

🎯 Core Architecture Follow-up Q&A

Q1:What are the key trade-offs and memory bottlenecks when deploying Beam Search Decoding with Length Penalty in high-throughput inference?

Memory bandwidth (HBM to SRAM I/O) is the primary latency factor. Fusing element-wise operations and avoiding intermediate tensor materialization significantly outperforms naive implementations.

Q2:How does Beam Search Decoding with Length Penalty handle extreme numerical boundaries or precision reduction (FP16/BF16/INT8)?

Under low precision, operations must be upcasted to FP32 during accumulation to prevent underflow/overflow, followed by proper scaling and clamping before converting back to the target format.

←Prev: Speculative Decoding Verification & Accept/Reject All 69 Kernels Next: Factorization Machine (FM) O(kd) Implementation→