cs.LGNov 8, 2026

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

Authors: Mohamed Ghanem, Bernd Finkbeiner

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

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Interactive Program Induction with Language Model Priors

    Nov 13, 2026Robin Shing Moon Chan, Ryan CotterellInductive InferenceActive Learning

  2. Gradient-Based Program Synthesis with Neurally Interpreted Languages

    Apr 20, 2026Matthew V. Macfarlane, Clément Bonnet, Herke van Hoof +1Program SynthesisDifferentiable Programming

  3. Transformers for Program Termination

    Mar 25, 2026Yoav Alon, Cristina DavidStatic Code AnalysisTransformer