The Shape of a Program: Path Signatures for Trace-to-Program Induction

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 expected signature provably characterizes the trace distribution a program induces. Our signature-based trace encoder outperforms LSTM, Transformer, and Fourier baselines and remains strong with substantially less training data on two classical DSL domains. We further observe that the trace-to-program pipeline is naturally \emph{contractive}: it tends to produce shorter valid programs than the ground truth, which we turn into a bootstrapping procedure that surfaces redundancy in the released ground-truth supervision without any external oracle. Finally, signature-based models induce a markedly more interpretable latent geometry than classical sequence models.