The Shape of a Program: Path Signatures for Trace-to-Program Induction
Organizations: CISPA Helmholtz Center for Information Security · Technical University of Munich
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.
Figures & tables
| Karel + | List + | RASP + | ||||
|---|---|---|---|---|---|---|
| Encoder | Tokens | Programs | Tokens | Programs | Tokens | Programs |
| removed (%) | shortened (%) | removed (%) | shortened (%) | removed (%) | shortened (%) | |
| LSTM | 21.11 | 58.66 | 22.37 | 59.42 | 13.41 | 32.33 |
| Transformer | 20.92 | 57.81 | 22.58 | 59.82 | 18.26 | 44.08 |
| Fourier | 18.43 | 52.89 | 18.19 | 49.62 | 18.64 | 44.98 |
| Log-Signature | 21.07 | 58.59 | 22.70 | 59.88 | 19.84 | 47.92 |
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.