NeurIPS 2026

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

Mohamed Ghanem1 Bernd Finkbeiner1,2
1CISPA Helmholtz Center for Information Security 2Technical University of Munich
Architecture: a hidden program is executed from K initial states to produce traces of grid states; each state is embedded by a state encoder, a positional code is added, the embedded states form a path whose log-signature is projected and read by a Transformer decoder that writes the predicted program, trained with cross-entropy against the hidden one.
Executing a hidden program ρ from K initial states gives K traces. A state encoder φ embeds each state and a positional code PE(t) is added, so each trace becomes a path in ℝd. Its log-signature summarizes the path's shape (at level 2, the signed areas between the path and its chord); a linear projection gives the trace embedding hk, and a Transformer decoder reads the embeddings to write the program ρ̂, trained with cross-entropy against ρ.

TL;DR  We treat program execution traces as paths and encode them with the log-signature, a parameter-free summary of a path's shape from rough path theory. It is the most accurate trace encoder in 11 of 12 settings across three domains, and its lead is largest when training data is scarce.

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.

How it works

  1. Run. The hidden program is executed from several initial states, giving a set of execution traces (sequences of states).
  2. Embed. A state encoder φ maps every state to a point in ℝd. Each step between points is rescaled to unit length and a sinusoidal positional code is added, so each trace becomes a path.
  3. Summarize. The truncated log-signature (level 2) turns each path into a fixed-size vector, whatever its length. A linear projection is the encoder's only trainable part.
  4. Decode. A Transformer decoder attends over the trace embeddings and writes the program token by token. Grammar masking keeps every output syntactically valid.

A program is pinned down by its traces

Running a program from random initial states induces a distribution over traces. For bounded-length traces such as ours, the expected signature uniquely determines this distribution (Chevyrev & Lyons, 2016), so averaging signatures over executions estimates an object that identifies the program up to behavior.

Signatures compose like executions

By Chen's identity, the signature of a path split at any time t is the tensor product of the signatures of its two pieces:
S(X[0,T]) = S(X[0,t]) ⊗ S(X[t,T])
Executions that share a segment, such as the same loop body or the same subroutine, share a signature factor.

Domains

Karel

A robot in a 2D grid world with walls and markers. Stands in for visual and spatial domains: robot control, tile puzzles, agent navigation.

List

Symbolic manipulation of a variable-length integer list through a cursor. Stands in for array and string tasks: sorting, searching, counting.

RASP

Maps, shifts, thresholds and counts over token sequences, from the language of Transformer computations. Stands in for functional sequence-to-sequence programs.

A decoded program counts as correct if, run from the same initial states, it reproduces every given trace. We call the share of correct test programs semantic accuracy.

Highlights

Finding 1

The log-signature encoder outperforms the LSTM, Transformer, and Fourier baselines in almost every setting, with its largest margins when training data is scarce.

11 / 12
(domain, training data volume) settings where log-signature is the most accurate encoder
+0.22
lead on Karel with 25% of the data (0.35 vs 0.13); +0.09 on List, +0.18 on RASP
½
the features of the full signature, at nearly the same accuracy on all three domains
Line plots of semantic accuracy against training data volume for Karel, List, and RASP. The log-signature curve is highest at all points except Karel at full volume.
Test semantic accuracy against training data volume, as a percentage of each domain's full training set (100K programs for Karel and List, 32K for RASP; log scale). Each point is the best epoch, averaged over 3 seeds; shading is ±1 standard deviation. The one exception is Karel at full volume, where the Transformer (0.679) and LSTM (0.669) lead the log-signature encoder (0.647).
Finding 2

Bootstrapping exposes substantial redundancy in the ground-truth supervision, with no external oracle required.

The trace-to-program pipeline is contractive: the model often outputs a program that is shorter than the ground truth yet reproduces every trace. We replace a training label whenever the model finds such a strictly shorter, verified program, and repeat. What this removes is a lower bound on how much shorter the supervision could have been. Our datasets hold little such redundancy (on Karel and List, a greedy search over trace-preserving local edits removes only 4.5% and 5.2% of the tokens), so we measure it on redundancy-injected copies, Karel+, List+ and RASP+: half of each set's programs are rewritten with extra structure that leaves every trace unchanged, such as S → REPEAT 1 (S), which adds about 20% of the tokens. Every encoder removes a substantial share, so contractivity is better understood as a property of the trace-to-program pipeline than of any one encoder.

Karel+List+RASP+
EncoderTokens removedPrograms shortenedTokens removedPrograms shortenedTokens removedPrograms shortened
LSTM21.11%58.66%22.37%59.42%13.41%32.33%
Transformer20.92%57.81%22.58%59.82%18.26%44.08%
Fourier18.43%52.89%18.19%49.62%18.64%44.98%
Log-Signature21.07%58.59%22.70%59.88%19.84%47.92%
Share of all training-label tokens removed, and share of training labels shortened at least once, on the redundancy-injected datasets.
Finding 3

The log-signature encoder induces a more interpretable latent geometry.

For the log-signature model, the embedded states of each trace form a separate chain; for the baselines, the traces of different programs run alongside and across one another. Measured over 20 test programs, the five nearest neighbors of every log-signature state lie on its own trace, on all three domains.

Four t-SNE panels (Logsig, LSTM, Transformer, Fourier) of embedded Karel traces for five programs. The log-signature traces are short separate segments; the baseline traces overlap and cross.
t-SNE of the embedded traces each encoder reads on Karel, for five test programs with six traces each. Each line is one trace, its points are the trace's states in order, and the traces of a program share a color. For a common view, the state embeddings of all four encoders are normalized to unit-length steps before the positional code is added. Each panel is a separate t-SNE fit.

BibTeX

@inproceedings{ghanem2026shape,
  title     = {The Shape of a Program: Path Signatures for Trace-to-Program Induction},
  author    = {Ghanem, Mohamed and Finkbeiner, Bernd},
  booktitle = {Advances in Neural Information Processing Systems},
  year      = {2026}
}