Can the geometry of a program’s execution reveal the program itself?

Inferring a program from examples is not always about matching inputs to final outputs. If we can see the sequence of states along the way, we have a trace: a record of the computation’s steps. Researchers use this kind of program induction to study how systems behave and to investigate whether a compact, readable program can explain an opaque process.

But how should a model represent a trace? Common approaches treat it as a sequence, using tools such as recurrent neural networks or Transformers. Mohamed Ghanem and Bernd Finkbeiner propose a different view: treat the trace as a path through a space of possible states, then describe its geometry with a mathematical representation called a log-signature.

From steps to shape

The basic intuition is that a program’s structure—its loops, choices and repeated actions—shows up in the path its execution takes. A log-signature summarizes aspects of that path, including how changes in different dimensions relate to one another over time. The researchers use the resulting summary as input to a Transformer decoder, which generates a program in the relevant domain-specific language.

They tested the approach on three benchmark domains: Karel, a grid-world language; List, a language for manipulating lists; and RASP, a language for describing sequence operations. The team compared the log-signature encoder with LSTM, Transformer and Fourier-based trace encoders. For Karel and List, the experiments used 100,000 training samples and 2,500 test samples. The RASP task used a different dataset and test setup.

The researchers also tested a bootstrapping procedure. When the model proposed a program that was both shorter than its current training label and able to reproduce all the supervised traces, they replaced the label with that shorter program. This let them examine whether their training examples contained redundant code, without relying on an external oracle to identify a better answer.

What the study found

By the paper’s measure—whether a generated program reproduced the supplied traces or outputs—the log-signature encoder had the highest accuracy in 11 of 12 combinations of domain and training-data volume. The exception was Karel with the full training set, where the LSTM and Transformer did better. The advantage was generally most pronounced when training data was scarce; with a quarter of the training data, the log-signature model nearly tripled the strongest baseline’s accuracy on Karel and led on List and RASP.

That does not mean it recovered the unique original code. Different programs can produce identical behavior on the examples provided. The study measures behavioral agreement, not exact recovery of the ground-truth program.

For the redundancy experiment, the researchers deliberately added equivalent but unnecessary structure to programs in modified datasets. The bootstrapping procedure found shorter valid labels across all four encoder types, not just the log-signature model. For example, the log-signature setup reduced the total training-program token count by about 21% on modified Karel and about 23% on modified List. These are results on datasets designed to contain redundancy; they are not estimates of how much redundancy occurs in ordinary software.

The team also examined learned state representations. In their analysis, the log-signature model’s nearest neighboring states stayed on the same execution trace across all three domains. That offers one way to inspect how its representations organize traces, but it is not by itself proof that the model’s decisions are understandable to people. The authors used t-SNE projections as visual aids; such plots should be interpreted cautiously because they compress high-dimensional data.

What remains uncertain

The results support a case for testing geometric trace representations, not for replacing other encoders across the board. The tasks use restricted programming languages and benchmark-generated data. Real software may have much longer executions, richer state spaces and behaviors not represented in these tests. The paper itself notes a technical limitation: log-signature features grow rapidly with the level of detail captured, so very long or complex traces may be difficult to handle. The main experiments use a low truncation level, which limits the higher-order interactions represented.

The authors’ theoretical motivation—that an expected signature can characterize a distribution of traces under certain conditions—also should not be confused with a guarantee that this trained model will identify the right program from a finite set of examples. In practice, the representation is truncated, and the decoder must learn from data.

This article is based on an arXiv preprint. Although the manuscript identifies itself as a NeurIPS 2026 paper, the supplied source does not independently establish its review or publication status. The paper reports its own experiments, and broader comparisons would require further evaluation on other tasks and data. For now, the main takeaway is narrower: on these three benchmarks, describing execution traces by their path geometry often helped a model produce programs that matched the observed behavior.