PAR: Progress-Aligned Recurrence for Length Generalization in State Tracking
报告的主要结果（均为原文自报，非本站复现）
| 方法（swap-$S_5$，训练长度 $\le32$） | 256 步（8×） | 512 步（16×） |
|---|---|---|
| Transformer（引用报告值） | — | 0.85±0.30 |
| RLT（引用报告值） | 97.3±2.8 | 55.7±25.8 |
| 显式 CoT | 0.8 | 0.8 |
| PAR（6 个种子） | 99.5±1.2 | 95.5±11.0 |
| PAR + learned halting（不知道长度） | 98.7±3.1 | 92.9±16.2 |
无步骤标签的 prefix self-distillation 在 $S_5$（训练 $d\le16$）上 256 步准确率 85%，$G\ge16$（原文自报）。
通俗解释
有一类模型可以「在脑子里多转几圈」（looped model），推理时想多想一会儿就多转几圈。但转了几圈并不保证能解更长的题。
论文的发现是：只用最终答案当监督，没人规定「每一圈该前进多少」，于是模型学到的是不能外推的捷径。PAR 的办法很朴素：规定第 k 圈就要输出「做完前 k 步之后的状态」，一圈对应一步；同时每圈结束后把内部状态的「音量」调回第一圈的水平，防止转多了数值漂移。
效果：在经典的「五个盒子交换物品」状态跟踪题上，训练只见过最多 32 步，测试到 512 步（16 倍长度）仍有 95.5% 的整体状态准确率；而让模型写出完整思维链的做法在同一骨干上降到 0.8%。
专业解释
问题：looped LM 在测试时可增加迭代次数，但额外迭代未必帮助解决更长的问题。对于顺序状态跟踪，最终答案监督没有规定每次迭代前进多少，并且重复更新会改变循环状态的尺度（norm drift）。
PAR（Progress-Aligned Recurrence） 由两个条件构成：(i) progress-aligned targets：第 $k$ 次迭代的读出必须等于前 $k$ 步操作之后的状态，建立显式的「深度—长度」对应（每次迭代前进 $c=1$ 步）；(ii) state-norm anchoring：每次迭代后把每个 token 的状态缩放到其第 1 次迭代状态的 RMS norm，保持步映射的平稳（stationary），并用 positional stretch 处理长 prompt 中查询与早期操作距离过远的问题。
此外有：learned halting（读出头同时预测 Yes/No 的「是否完成」，用「6/8 确认窗口」规则在不知道问题长度时停止）与 prefix self-distillation（只有最终答案标签时，用 EMA 教师在被截断前缀上的输出来监督更早的迭代）。消融显示两个条件缺一不可：去掉 norm anchoring 外推倍数从 16× 降到约 1.8×（Table 7 中 1.81 / 1.84）；用「每一圈都监督最终答案」则外推倍数仅约 2。
详细算法
1. 问题设定
任务：群字问题（group word problem）。提示给出 $d$ 个对五个盒子（各放一件物品）的操作，询问某个盒子里是什么。swap-$S_5$：每步为恒等或 10 个对换之一；$A_5$：每步为一个 3-循环。随机猜测准确率 0.2。训练长度 $\le 32$（swap-$S_5$）或 $d\le16$（$S_5$、$A_5$），测试至更长。整体状态准确率要求五个盒子全对。
模型：把 Qwen2.5-0.5B 的 24 层改造成 prelude $P$（1–8 层）+ 权重共享的 core $C$（9–16 层）+ coda $Q$（17–24 层）的 retrofitted looped LM（沿用 McLeish 等的做法）。答案用分类头在候选答案 token 上读出，不生成任何中间 token。
2. 关键公式
retrofitted 循环（$e=P(x)$，$s_0=e$，adapter $W\in\mathbb R^{h\times 2h}$ 初始化为 $[0\,|\,I]$，使 $R=1$ 时与父模型等价）：
$$s_k=C\big(W[e;\,s_{k-1}]\big),\quad k=1,\ldots,R,\qquad y_k=Q(s_k)$$
进度对齐损失（$z_j$ 为前 $j$ 步之后的答案，$d$ 为总步数，步长 $c=1$，$\mathcal K$ 为梯度窗口内的迭代集合）：
$$\mathcal L_{\text{PAR}}=\sum_{k\in\mathcal K}\mathrm{CE}\big(Q(s_k),\ z_{\min(ck,\,d)}\big)$$
状态 norm 锚定（stop-gradient 于参考项）：
$$s_k\leftarrow s_k\cdot\frac{\mathrm{rms}(s_1)}{\mathrm{rms}(s_k)}$$
Positional stretch：短暂微调阶段把位置索引乘以 $s\sim U[1,s_{\max}]$，$s_{\max}$ 从 1 斜升到 8，测试时用普通位置。
学习停止：读出头在 $ck\ge d$ 时对 token「Yes」放概率，否则放在「No」，类别平衡交叉熵权重 0.5。推理取第一个满足 $P(\text{Yes})>\tau$ 且在窗口 $R,\dots,R+m-1$ 内至少 $k$ 次超过 $\tau$ 的迭代 $R$（$\tau=0.5,k=6,m=8$）。
Prefix self-distillation：对 $k<\lceil d/c\rceil$ 的迭代，用 EMA 教师在截断到 $ck$ 步的 prompt 上、在其自身完成迭代处的答案分布做 KL 监督；$k\ge\lceil d/c\rceil$ 的迭代用最终答案 $z_d$ 交叉熵。
3. 逐步伪代码
# 训练 (forced depth, 默认的 PAR)
for 每个 batch (同一 batch 内深度 d 相同):
R = ceil(d / c) # c = 1
e = P(x); s = e
for k = 1..R:
s = C( W · concat(e, s) )
s = s * rms(s_1) / rms(s) # state-norm anchoring (stop-grad 于 rms(s_1))
if k 在最后 8 次迭代 (梯度窗口): loss += CE( Q(s), z[min(c*k, d)] )
# 同时训练 halting 头: 目标 = Yes if c*k >= d else No (类别平衡, 权重 0.5), 另加一个更早的迭代作额外负例
反向传播 (梯度只通过最后 8 次迭代)
# 推理 (不知道问题长度)
s = e = P(x)
for k = 1..Kmax:
s = C(W·[e; s]); s = anchor(s)
p_yes[k] = P_Q(Yes | s)
if 存在 R<=k-m+1 使 p_yes[R] > 0.5 且 窗口 [R, R+8) 内至少 6 次 > 0.5:
return 读出 Q(s_R) # 在「完成信号」刚出现处读取答案4. 训练 / 推理流程
训练：AdamW，学习率 $2\times10^{-5}$（adapter $10^{-4}$），200 步 warm-up，约 40 万样本一个 epoch，训练深度均匀分布；全程不产生中间 token。深度调度有两种：forced depth（每批一个深度 $d$，迭代 $R=\lceil d/c\rceil$）与 hold（$R$ 取自重尾分布，超过 $d/c$ 的迭代保持 $z_d$）。
评测：swap-$S_5$ 用 Zhang 等的协议（训练 $\le32$ 步，每个长度 1,024 条序列测整体状态准确率）；外推倍数 $G=d_{50}/d_{\rm train}$，以测试深度至 256、$d_{\rm train}=16$ 时 $G=16$ 为最大可测值。
与既有方法对比
- 显式思维链（CoT）：同一骨干上，训练范围内完美但到 8 倍长度崩溃至接近随机（swap-$S_5$ 上 512 步为 0.8%）。
- RLT（Zhang 等，文中引用其报告值）：swap-$S_5$ 上 256 步 97.3%，512 步降为 55.7%±25.8；PAR 为 99.5% 与 95.5%±11.0。
- 固定深度 / 48 层不共享 / 随机 $R$ 循环：外推倍数都低于约 2×，说明「迭代次数」或「参数量」本身都不能替代深度—长度对应关系。
- 「每圈都监督最终答案」（Chen 2025 一类做法）：外推倍数约 2。
优势
- 给出清晰的因果诊断：监督信号必须定义「一圈做多少」，并且步映射必须平稳；两个条件在消融中都被证明必要。
- 完全不生成中间 token，推理时可以用学到的「完成信号」自适应停止，不依赖知道问题长度。
- 只要有「前缀即更短问题」的结构，就可用 prefix self-distillation 只靠最终答案学习，不需要逐步标签。
- 在 16× 外推下对比 CoT、RLT 等强基线有明显优势。
劣势 / 局限
- 只在算法型、模板化的状态跟踪任务上验证；作者明确说开放式自然语言推理留待未来，没有顺序分解的任务（如图可达）不在适用范围。
- 扩展性不确定：更大骨干的结果跨种子波动很大（Qwen2.5-1.5B 到 7B 在 16× 的标准差为 33 ~ 43 分），准确率不随规模单调上升，Qwen3 骨干都达不到 0.5B 的 16× 水平。
- swap-$S_5$、learned halting 与 prefix self-distillation 只在 Qwen2.5-0.5B 上评估；PAR 的 16× 结果在 swap-$S_5$ 上标准差 11 分，仍不稳定。
- label-free 变体需要额外的 positional stretch 微调才能达到 16×。
与工业 AI 的关系（作者判断，非论文结论）
工业场景里有大量「按顺序更新状态」的问题：工序/配方步骤推演、批次过程的状态机、设备的开关量时序。PAR 提示：想让模型在训练外的更长序列上仍可靠，需要显式规定「每次内部迭代对应一步」。但目前证据仅限合成任务，不应直接当作工艺推理方案；更可行的是把它当作研究方向，用工艺步骤仿真数据做小规模验证。
待确认事项
- 待确认：PAR 是否能迁移到自然语言推理与真实工业时序任务 依据：作者在 Limitations 中自述未验证（2026-10-31）
- 待确认：论文是否提供代码 依据：HF 页面无 githubRepo 字段，全文未见仓库链接（2026-10-31）