ADR-016 深度解析：RuVector 亚多项式算法在 WiFi-DensePose Rust 训练管线中的五处落地集成

本篇文章以仓库内已采纳的架构决策 ADR-016 RuVector Integration for Training Pipeline 为骨架，解析 RuView v2 Rust 工作区如何把 ruvector 生态中五个已发布的纯 Rust crate（亚多项式动态最小割、min-cut 门控注意力、时间张量分级量化、稀疏线性求解器、缩放点积注意力）接入 wifi-densepose-train 训练管线。你会看到每个决策点的"改造前/改造后"差异、实际源码实现证据、依赖声明方式，以及 O(n³) 匈牙利匹配 → O(n^1.5 log n) 动态更新的量化收益，可直接对照 v2/crates/wifi-densepose-train 代码深入。

一、决策背景：为什么要用 ruvector 替换标准实现

ADR-016 针对的是 wifi-densepose-train crate（现位于 v2/crates/wifi-densepose-train）。该 crate 是前序 ADR-015: Public Dataset Training Strategy 确立的训练管线实现载体：负责读取 MM-Fi、Wi-Pose 等公开 WiFi CSI 数据集，执行 114→56 子载波重采样与相位净化，训练端到端 WiFi-DensePose 模型（关键点热图 + DensePose part/UV + OKS 指标）。

初始实现依赖的是标准 Rust crate（petgraph、ndarray 以及自研信号处理代码）。而 ruvector 生态（当时在 crates.io 确认全部发布 v2.0.4）提供了一批带有次多项式/亚多项式复杂度的 Rust crate，可以直接替换其中的若干组件，从而把三个核心痛点——多帧人员匹配的状态维护、CSI 时序窗口的内存占用、子载波插值的求解精度——从算法层面解决，而不是靠"堆硬件"。

从当前仓库的 v2/crates/wifi-densepose-train/Cargo.toml 可以看到这套依赖已经真实落地（以 workspace = true 方式挂到工作区），且伴随 petgraph.workspace = true 仍被保留用于原始匈牙利算法：

# Graph algorithms (min-cut for optimal keypoint assignment)
petgraph.workspace = true

# ruvector integration (subpolynomial min-cut, sparse solvers, temporal compression, attention)
ruvector-mincut = { workspace = true }
ruvector-attn-mincut = { workspace = true }
ruvector-temporal-tensor = { workspace = true }
ruvector-solver = { workspace = true }
ruvector-attention = { workspace = true }

版本演进说明：ADR-016 决策时这些 crate 均为 v2.0.4；而仓库当前根工作区 v2/Cargo.toml 已把依赖前移，例如 ruvector-mincut = "2.0.6"、ruvector-temporal-tensor = "2.0.6"、ruvector-solver = "2.0.6"、ruvector-attention = "2.1.0"，ruvector-attn-mincut 仍为 "2.0.4"，另新增 ruvector-core、ruvector-crv、ruvector-gnn 等条目。阅读本文时注意：API 语义保持不变，但以仓库锁定版本为准。

候选 crate 全景（v2.0.4 时代）

Crate	能力说明	默认特性
ruvector-mincut	首个亚多项式动态最小割实现	exact, approximate
ruvector-attn-mincut	基于最小割门控的注意力（softmax 的图替代方案）	all modules
ruvector-attention	几何、图、稀疏注意力机制	all modules
ruvector-temporal-tensor	分级量化的时间张量压缩	all modules
ruvector-solver	O(log n) 到 O(√n) 的亚线性稀疏线性求解器	neumann, cg, forward-push
ruvector-core	基于 HNSW 索引的向量数据库核心	v2.0.5
ruvector-math	最优传输、信息几何	v2.0.4

前五个 crate 是 ADR-016 的主选，ruvector-core 与 ruvector-math 不在本次训练管线集成范围内。

二、五个集成点逐项拆解

ADR-016 的决策核心是"五 crate、五处代码集成点"。下面逐点给出官方记录的 API 形态、改造前后对比，并对照仓库源码验证落地情况。

集成点 1：ruvector-mincut → metrics.rs（多帧人员匹配）

改造前：metrics.rs 用 petgraph::DiGraph + DFS 增广路径实现 O(n³) Kuhn-Munkres 匈牙利匹配（Hungarian），且只支持单帧静态匹配——跨帧不保留任何状态，每帧都要全量重建。

改造后：新增 DynamicPersonMatcher 结构体，内部包装 ruvector_mincut::DynamicMinCut，把预测框与真值的二分分配图跨帧增量维护：

• insert_edge(pred_id, gt_id, oks_cost)：新人员进入场景时添加边；
• delete_edge(pred_id, gt_id)：人员离开场景时删边；
• partition() 返回 S/T 划分，cut_edges() 给出被选中的 pred→gt 匹配边。

官方验证的 API 形态如下（注意 VertexId 实际是 u64 而非 u32，Edge 字段为 { source: u64, target: u64, weight: f64 }）：

use ruvector_mincut::{MinCutBuilder, DynamicMinCut, MinCutResult, VertexId, Weight};

let mut mincut = MinCutBuilder::new()
    .exact()                                        // 或 .approximate(0.1)
    .with_edges(vec![(u: VertexId, v: VertexId, w: Weight)])  // (u64, u64, f64)
    .build()
    .expect("Failed to build");

mincut.insert_edge(u, v, weight) -> Result<f64>   // 返回新的割值
mincut.delete_edge(u, v) -> Result<f64>
mincut.min_cut_value() -> f64
mincut.min_cut() -> MinCutResult                  // 含划分
mincut.partition() -> (Vec<VertexId>, Vec<VertexId>)
mincut.cut_edges() -> Vec<Edge>

MinCutResult 字段：value: f64（最小割权值）、is_exact: bool、approximation_ratio: f64、partition: Option<(Vec<VertexId>, Vec<VertexId>)>（S/T 节点集合）。

仓库落地证据：metrics.rs 中 DynamicPersonMatcher 的图结构注释给出了精确编码方案：

• 节点 0 = 源点 S；
• 节点 1..=n_pred = 预测节点；
• 节点 n_pred+1..=n_pred+n_gt = 真值节点；
• 末尾节点 = 汇点 T；
• S→pred_i 与 gt_j→T 的容量均为 LARGE_CAP = 1e6；
• pred_i→gt_j 容量 = LARGE_CAP - oks_cost（OKS 成本越低，边容量越高，越容易被割保留），由此"最大割容量保留"天然等价于"最小成本匹配"。

关键方法均与 ADR 描述一一对应：add_person 调用 inner.insert_edge，remove_person 调用 inner.delete_edge，assign() 过滤掉 source/sink 边后从 cut_edges() 中还原 (pred_idx, gt_idx) 匹配对，min_cut_value() 透传。配套的便捷入口 assignment_mincut（metrics.rs 附近）以及内部基于动态最小割的 DynamicMinCut 覆盖了多帧匹配路径。

性能结论：单帧场景从 O(n³) 全量重建降为 O(n^1.5 log n) 均摊更新，对 >3 人多目标与逐帧视频跟踪收益显著；且原有的 hungarian_assignment（metrics.rs）被特意保留，用于单帧静态匹配和 proof 验证，保证确定性哈希可复现。

集成点 2：ruvector-attn-mincut → model.rs（模态翻译器中的天线路径门控）

改造前：ModalityTranslator 中振幅/相位各自经过 FC 编码器 → 拼接 [B, 512] → 融合 Linear → ReLU 的扁平融合，靠显式学到的 mask 做特征筛选。

改造后：把 n_ant = T * n_tx * n_rx（天线×时间路径）视为序列 token、把 n_sc 子载波视为特征维度 d，用 attn_mincut 对"不相关的天线对相关性"做门控——本质是一次自动天线选择，无需显式 mask，且比学到的门控更具计算原理上的可解释性。官方 API 签名：

use ruvector_attn_mincut::{attn_mincut, attn_softmax, AttentionOutput, MinCutConfig};

// Q、K、V 均为扁平 &[f32]，形状 [seq_len, d]
let output: AttentionOutput = attn_mincut(
    q: &[f32], k: &[f32], v: &[f32],
    d: usize,        // 特征维度
    seq_len: usize,  // token 数 / 天线路径数
    lambda: f32,     // 最小割阈值（越大剪枝越狠）
    tau: usize,      // 时间滞回窗口
    eps: f32,        // 数值 epsilon
);
// AttentionOutput { output: Vec<f32>, gating: GatingResult }

仓库落地证据：model.rs 中 apply_antenna_attention(x, lambda) 逐 batch 元素把 [n_ant, n_sc] 搬到 CPU、转成扁平 Vec<f32>，以 Q = K = V = 天线特征 的自注意力形式调用 attn_mincut：

let out = attn_mincut(
    &flat,       // q: [n_ant * n_sc]
    &flat,       // k: [n_ant * n_sc]
    &flat,       // v: [n_ant * n_sc]
    n_sc_usize,  // d: 特征维度 = n_sc 个子载波
    n_ant_usize, // seq_len: 天线路径数
    lambda,      // 0.3 = 中等剪枝
    1,           // tau: 单帧无需时间滞回
    1e-6,        // eps
);

值得注意的是：函数开头 if n_ant <= 1 || n_sc <= 1 { return x.shallow_clone() } 处理了退化情形（单天线或单子载波时注意力为 no-op），说明该 bridge 在真实数据形状下是有条件的激活逻辑。

集成点 3：ruvector-temporal-tensor → dataset.rs（CSI 时序窗口压缩）

改造前：MmFiDataset 把原始 CSI 窗口以完整 f32 精度 Array4<f32> 常驻内存，默认 100 帧/样本的时序窗口占用可观，直接限制 batch size。

改造后：CompressedCsiBuffer 结构体以 TemporalTensorCompressor 为后端，按帧访问新鲜度分级量化：

• hot 帧（最近 10 帧）：保持近似 f32 保真度（8-bit 量化约比 f32 小 4 倍）；
• warm 帧（第 11–50 帧）：5/7-bit 量化（约 4.6–6.4 倍）；
• cold 帧（>50 帧）：3-bit（约 10.67 倍）。

push_frame 编码、get(idx) 透明解码，调用方无感知。官方 API 示例：

use ruvector_temporal_tensor::{TemporalTensorCompressor, TierPolicy};
use ruvector_temporal_tensor::segment;

let mut comp = TemporalTensorCompressor::new(
    TierPolicy::default(),
    element_count: usize,   // n_tx * n_rx * n_sc（每 CSI 帧元素数）
    id: u64,                // tensor 标识：0=振幅, 1=相位
);
comp.set_access(timestamp: u64, tensor_id: u64);          // 驱动 tier 选择
comp.push_frame(frame: &[f32], timestamp: u64, &mut segment_buf);
comp.flush(&mut segment_buf);
segment::decode(&segment_buf, &mut decoded);
segment::decode_single_frame(&segment_buf, frame_index) -> Option<Vec<f32>>;
segment::compression_ratio(&segment_buf) -> f64;

仓库落地证据：dataset.rs 定义了 CompressedCsiBuffer。与 ADR 描述的差异在于真实实现把编码数据组织为可独立解码的段数组（segments: Vec<Vec<u8>>，配合 segment_frame_starts 前缀和定位帧号），原因是 tier 切换或帧间漂移会产生新的 segment 边界；from_array4 在逐帧 set_access(t, t) 模拟"越近越热"的访问计数、push_frame 到临时段缓冲区，并在检测到完整段（通过 tt_segment::parse_header 读取帧数）后归档。最终按 compression_ratio = 原始 f32 字节数 / 压缩字节数 计算整体压缩比并暴露为字段，测试位于同文件 1488 行附近（CompressedCsiBuffer::from_array4 用例）。

收益量化：默认 100 帧时间窗可取得 50–75% 内存缩减，从而在受限硬件上把 batch size 提升 2–4 倍——这正是 56 子载波、Atheros/ESP32 目标硬件与单 GPU（RTX 3090/A100）训练约束下最实际的收益。

集成点 4：ruvector-solver → subcarrier.rs（稀疏正则最小二乘子载波插值）

改造前：interpolate_subcarriers 用预计算的 (i0, i1, frac) 元组在子载波间做线性插值。

改造后：interpolate_subcarriers_sparse 用 NeumannSolver 求解稀疏正则最小二乘问题 A·x ≈ b：CSI 频谱被建模为傅里叶/高斯/sinc 基函数的稀疏组合（物理上对应多径传播），每个目标子载波是相邻源子载波的稀疏组合，对 114→56 的重采样物理意义更强。官方配置为 NeumannSolver::new(tolerance=1e-5, max_iter=500)。

仓库落地证据：subcarrier.rs 第 20 行导入 NeumannSolver，第 75 行的 interpolate_subcarriers（线性插值，作为默认路径）与第 186 行的 interpolate_subcarriers_sparse 并存；第 265 行以模块内常量 SPARSE_SOLVER_TOL、SPARSE_SOLVER_MAX_ITERS 构造求解器。模块文档（第 24 行附近）特别说明稀疏路径中的常量与线性路径保持 bit 级一致，确保两套实现可交叉验证。同文件包含对 interpolate_subcarriers_sparse 与 interpolate_subcarriers 的成对测试（如 114→56、子带截断等场景），证明"稀疏路径正确性由测试兜底、线性路径仍是可回退的默认实现"这一 ADR 约定确实被执行。调用关系上，dataset.rs 与 dataset/widar.rs 均通过 crate::subcarrier::interpolate_subcarriers 在数据加载期完成子载波对齐。

集成点 5：ruvector-attention → model.rs（空间解码器的长程依赖）

改造前：KeypointHead / DensePoseHead 使用标准 ConvTranspose2D 上采样，只能看到局部感受野。

改造后：ScaledDotProductAttention 作用于空间特征节点——把 [B, C, H, W] 展平成 [B, H*W, C]，每个空间位置（天线脚印区域的网格点）是一个 token，注意力在 H×W 节点间捕捉卷积局部感受野之外的长程空间依赖，对多人场景尤其重要。官方 API：

use ruvector_attention::{attention::ScaledDotProductAttention, traits::Attention};

let attention = ScaledDotProductAttention::new(d: usize);   // 特征维度
let output: Vec<f32> = attention.compute(
    query: &[f32],       // [d]
    keys: &[&[f32]],     // n_nodes × [d]
    values: &[&[f32]],   // n_nodes × [d]
) -> Result<Vec<f32>>;

仓库落地证据：model.rs 提供 apply_spatial_attention(x)：每个 batch 元素先 reshape([c, h*w]) 再 transpose 成 [H*W, C]，转 CPU 扁平化后逐 token 交给 ScaledDotProductAttention::new(d)。需要如实说明的是：该函数带有 #[allow(dead_code)] 注解，其文档注释表明它"为完整性而定义，可能被 head 实现或未来 backbone 变体调用"——也就是说，从当前源码看第 5 个集成点在 ADR 状态表中标记为 Complete，但实际以"预留可调用点"的形式存在，接入具体 head 仍需后续工作。这是阅读源码时能观察到的唯一一处"状态表与调用链不完全一致"的点。

三、决策保留项：为什么原实现没有删除

ADR-016 明确要求两处原实现保留为确定性/回退路径，仓库代码也一一印证：

原实现	保留位置	保留理由
hungarian_assignment（petgraph 匈牙利）	metrics.rs 及 hungarian_assignment_v2（metrics.rs）	单帧静态匹配 + proof 验证需要确定性（同一输入永远产生同一匹配，供 SHA-256 复现）
interpolate_subcarriers（线性插值）	subcarrier.rs	作为稀疏求解路径的默认/回退实现，配置层 config.rs 亦引用它做说明

这体现了一个工程原则：引入亚多项式新路径不等于删除确定性基线——训练可复现性（见 wifi-densepose-train 的 proof.rs 与 verify-training 二进制）由旧路径保障，性能提升由新路径负责。

四、实施计划、状态与依赖声明方式

ADR-016 规划的改动清单与实际仓库结构完全吻合：

文件（计划）	改动内容	仓库现状
Cargo.toml（workspace + crate）	添加五个 ruvector crate = "2.0.4"	已生效，且版本前移至 2.0.4–2.1.0（见 v2/Cargo.toml）
metrics.rs	新增 DynamicPersonMatcher 包装 DynamicMinCut；保留 hungarian_assignment	见 metrics.rs
model.rs	ModalityTranslator::forward_t 中加 attn_mincut bridge；空间 head 加 ScaledDotProductAttention	apply_antenna_attention 已接线；apply_spatial_attention 为预留调用点
dataset.rs	CompressedCsiBuffer 由 TemporalTensorCompressor 支撑，MmFiDataset 使用之	见 dataset.rs
subcarrier.rs	interpolate_subcarriers_sparse 用 NeumannSolver；保留 interpolate_subcarriers 兜底	两函数并存于 subcarrier.rs

不动的文件：config.rs、losses.rs、trainer.rs、proof.rs、error.rs 无需任何改动——说明这五处集成被刻意设计为模块内局部替换，不触碰训练主循环、损失计算与可证明性框架。

Feature gating 策略：所有 ruvector 集成都 always-on（不做 feature 门控），理由是该系列 crate 是纯 Rust、无 C FFI，因此不引入任何平台约束。这也意味着下游任何 crate 引入 wifi-densepose-train 都会静态链接这些依赖（Cargo.toml 中它们被列为非 optional 依赖，只有 tch/tch-backend/cuda 是可选特性）。

五、影响评估与权衡

正面收益（ADR 决策记录 + 源码可验证）：

• 多帧跟踪匹配从每帧 O(n³) 重建降为 O(n^1.5 log n) 均摊增量更新；
• 最小割门控注意力把"天线路径选择"变成物理意义明确的图划分问题，替代显式学习 mask；
• 时间分级量化带来 50–75% 的训练数据内存缩减，等价扩大 batch size 2–4 倍；
• 稀疏正则最小二乘插值比线性插值在子载波边界更精确，且对 114 个源子载波是 O(√n) 级求解。

代价与限制（需在选型时知晓）：

• 新增编译期依赖，工作区构建图变大；
• attn_mincut 每个 batch 元素都要做 tensor↔Vec<f32> 的 CPU 往返转换（model.rs 中清晰可见逐 batch to_device(Device::Cpu)），这是纯 Rust 内核与 tch GPU 张量之间的桥接开销；
• TemporalTensorCompressor 是有损压缩，给数据加载增加编解码延迟，且 warm/cold tier 会损失数值细节（训练精度容忍度需实测）；
• NeumannSolver 收敛前提是矩阵对角占优，因此系统在正规方程中加入稀疏 Tikhonov 正则项（λI）保证收敛——这与 ADR 文档的 negative consequences 记录一致。

六、与相邻 ADR 的承接关系

• 上游：ADR-015 确立 MM-Fi 主训练集、114→56 子载波插值策略与 wifi-densepose-train crate 的职责边界，ADR-016 是其工程实现里的算法选型环节；
• 下游：ADR-017 RuVector Integration for Signal Processing and MAT Crates 把同一套五个 crate 复用到 wifi-densepose-signal（子载波灵敏度选择、频谱门控、BVP 加权、Fresnel 几何求解）与 wifi-densepose-mat（多 AP 三角定位、呼吸/心跳波形压缩），并把 ADR-016 称作"completed reference implementation"——也就是说，训练管线是 ruvector 集成模式的样板；
• 纠偏作用：ADR-017 顺带修正了 ADR-002 依赖策略中不存在于 crates.io 的虚构 crate 名（ruvector-core/ruvector-data-framework 等 v0.1 条目），实际统一走 ADR-016 验证过的五个发布 crate。

七、如何基于本文继续深挖

1. 想读"API 签名 → 图结构编码 → 匹配还原"的完整链路，从 metrics.rs 开始，再到其单测区（约 metrics.rs 起的 hungarian_assignment/hungarian_assignment_v2 确定性测试）；
2. 想验证压缩收益的数值，直接读 dataset.rs 起的 CompressedCsiBuffer 测试，观察 compression_ratio 字段如何被断言；
3. 想对比"线性 vs 稀疏"两套插值的 bit 级一致性约束，读 subcarrier.rs 顶部模块文档与其 400 行之后的成对测试；
4. 若关心整个 v2 工作区如何统一管理这些依赖，看 v2/Cargo.toml 中 ruvector 段的 workspace 版本声明。

需要提醒的现实边界：ADR-016 引用的 github.com/ruvnet/ruvector 与 crates.io 上的 v2.0.4 属外部公开资料，本文仅转述其在仓库内被采信时的记录状态；而仓库工作区实际锁定版本已高于该文档，任何二次开发请以 v2/Cargo.lock 与 v2/Cargo.toml 的锁定结果为准。