arXiv cs.AI· Mohamed Ghanem, Bernd Finkbeiner·· 10 小时前AI 评分31
用路径签名做执行轨迹到程序归纳：log-signature 编码器在 Karel、List、RASP 上超越 LSTM、Transformer 与 Fourier 基线
The Shape of a Program: Path Signatures for Trace-to-Program Induction
AI 导读
研究者提出用粗糙路径理论做程序归纳，将执行轨迹视为高维粗糙路径并用路径签名变换编码，其期望可刻画程序所诱导轨迹的分布。在 Karel、List、RASP 三个程序归纳任务上，log-signature 轨迹编码器几乎在所有设置下优于 LSTM、Transformer 和 Fourier 基线，训练数据稀缺时优势最大。该编码器还诱导出更可解释的潜在几何——每个状态的最近邻都落在其自身的执行轨迹上。
正文 · 原文
Abstract:Synthesizing programs from execution traces is a fundamental challenge in algorithmic interpretability and the reverse engineering of complex systems. We bring a rough-path-theoretic perspective to program induction, treating execution traces as high-dimensional rough paths and encoding them with the path signature transform, a tool from stochastic analysis whose expectation provably characterizes the distribution of traces a program induces. On three program-induction domains, Karel, List, and RASP, our log-signature trace encoder outperforms LSTM, Transformer, and Fourier baselines in almost every setting, with its largest margins when training data is scarce. We further observe that the trace-to-program pipeline is naturally contractive: it often produces valid programs that are shorter than the ground truth. We turn this into a bootstrapping procedure that exposes redundancy in the ground-truth supervision without any external oracle, which we demonstrate on redundancy-injected versions of our datasets. Finally, the log-signature encoder induces a markedly more interpretable latent geometry than the baselines, in which the nearest neighbors of every state lie on its own execution trace.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2611.13005 [cs.LG] |
| (or arXiv:2611.13005v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2611.13005 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Mohamed Ghanem [view email]
[v1]
Sun, 8 Nov 2026 19:53:00 UTC (255 KB)
来源：arXiv cs.AI · arxiv.org