WorksComputer Science
The Shape of a Program: Path Signatures for Trace-to-Program Induction
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.
https://oschart.github.io/program-signature
Introduction
Program synthesis, the task of automatically generating code that satisfies a given specification, stands as one of the central challenges in modern artificial intelligence. While much of the recent progress has focused on synthesizing programs from functional specifications, typically provided as input-output (I/O) pairs [8, 1, 2, 4], this represents only one facet of the problem. A distinct but equally important challenge is synthesizing programs from behavioral specifications in the form of execution traces. This task is commonly referred to as program induction. Unlike I/O pairs, which treat the program as a black box, execution traces reveal the how of the computation, offering a granular view of the algorithmic decision-making process. Mastering this form of synthesis is essential for real-world applications such as reverse-engineering legacy systems, malware analysis, and algorithmic interpretability, where the goal is not just to replicate an output, but to recover the underlying logic that produced a specific sequence of states.
This direction is essential for algorithmic interpretability, as it allows us to distill opaque agents into human-readable code [30]. By synthesizing programs that faithfully reproduce the trace of a policy rather than just its final output, we gain verifiable insights into agent behavior, revealing safety constraints and logic gaps that are otherwise hidden in high-dimensional weight matrices. Towards this end, it is compelling to find more optimal methodologies for encoding behavioral traces. Unlike static I/O pairs, behavioral traces possess intrinsic temporal and geometric structure that characterizes how a task is solved, not just what the solution is. Consequently, the success of the synthesis process hinges on the representation’s ability to capture these dynamics robustly.
To tackle this task, the dominant paradigm has been to treat execution traces as discrete sequences, processing them with standard sequence models like LSTMs [13] or Transformers [29]. In this work, we propose a fundamental shift in perspective. Rather than viewing traces merely as sequences of tokens, we conceptualize them as high-dimensional rough paths and encode them using the path signature transform, a tool from stochastic analysis and rough path theory [3] that has been of growing interest in machine learning for time-series forecasting and reinforcement learning [5, 15]. Under this lens, a program is a generator of rough paths: each execution traces out a curve in the latent state space whose geometric shape reflects the underlying control flow. The signature transform turns that geometry into a fixed-size, length-invariant embedding with a principled algebraic structure, providing a representation that is naturally aligned with how programs structure execution.
Several properties of the signature reinforce this perspective. First, the expected signature characterizes the trace distribution a program induces [6], so aggregating signatures across executions of the same program can, in principle, identify it. Second, signatures factor under any temporal decomposition of the path: by Chen’s identity, , so the signature of a trace is the product of the signatures of its parts (§ 4.2). Third, the signature captures the shape of the path in a fixed-size representation regardless of path length. Fourth, its runtime is linear in the path length, making it much more practical for processing long traces than Transformers with their quadratic attention complexity (Appendix § 8.§ 5). Beyond these four points, the signature is a universal nonlinearity: any continuous functional of the path can be linearly approximated from its signature, so no expressive power is sacrificed for these structural advantages. This last property notably does not hold for classical operators like the Fourier transform.
Contributions. We make the following key contributions:
We explore the use of path signature methods for learning programmatic behavior, bringing a rough-path-theoretic perspective into program induction. On three program-induction domains, 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 show that our trace-to-program pipeline is naturally contractive: it produces shorter valid programs than the ground-truth program in a sizable fraction of cases. We turn this property into a bootstrapping procedure that progressively replaces ground-truth training programs with model-generated ones whenever they are valid and shorter, and use it as a measurement instrument that exposes redundancy in the supervision without any external oracle.
We show that the log-signature encoder induces a markedly more interpretable latent geometry than the baselines: the states of each execution trace form a separate chain, and the nearest neighbors of every state lie on its own trace.
Related work
Path signature in deep learning. Early applications utilized the truncated signature as a static feature vector for standard supervised learning tasks, such as handwriting analysis and financial time-series classification [17, 11]. It has also been used to summarize trajectories in non-Markovian reinforcement learning as an agent memory [15]. More recently, Neural Rough Differential Equations [21] have used the log-signature transform as the driving control of a continuous-time architecture for long time series, embedding signature theory directly into the model’s dynamics rather than treating it as a fixed feature map. A common thread between these methods is that they aim to extract some information from the signature features. In contrast, we use the signature of a behavioral trace not only to summarize it but also to characterize and reconstruct the generating process, i.e., the program.
Neural program induction. This paradigm leverages the insight that traces provide a denser supervisory signal than I/O pairs, reducing the search space for complex algorithms. Many existing works learn the programs in the latent weights of the model [22, 10, 32]. This has the downside of losing interpretability over the learned programs. Reed and de Freitas [25] introduced the Neural Programmer-Interpreter (NPI), which learned to execute programs by composing sub-programs, trained to imitate full execution traces, though it required expensive step-by-step supervision. To relax this requirement, Shin et al. [26] proposed a two-stage trace-inference framework, where a model first predicts a latent execution trace from I/O pairs and subsequently decodes the program code from that predicted trace, significantly improving performance on DSL tasks like Karel. Closest to our setting, Sun et al. [27] synthesize Karel programs from multiple demonstrations, i.e., sequences of environment states, which they encode with recurrent networks. In this paper, we take a simpler and more focused approach that employs an encoder-decoder architecture with the ultimate goal of evaluating the efficacy of different trace encoders.
Preliminaries
Let be a path. The signature of , denoted by , is an infinite graded sequence of iterated integrals that provides a faithful representation of the path’s geometric shape.
Formally, the signature is an element of the extended tensor algebra . It is defined as the collection of all iterated integrals of the path coordinates:
where the -th level term is a tensor in with components given by:
The term at level is conventionally 1.
In the context of discrete data analysis, we typically observe a discrete time series where . To compute the signature, we treat as a continuous path by applying a piecewise linear interpolation. Let be the continuous path obtained by linearly interpolating between the points in .
Utilizing Chen’s identity [3], which states that where denotes their concatenation, the signature of the discrete path can be computed efficiently as the tensor product of the signatures of its linear segments:
where the exponential map is defined within the tensor algebra.
Key properties and invariances. The path signature possesses several algebraic and geometric properties [5] that make it a highly desirable feature map for machine learning tasks. Firstly, the signature map is injective for paths up to tree-like equivalence [12]. Essentially, uniquely determines the path (up to “backtracking”), ensuring that no information regarding the shape of the trajectory is lost during the transformation. Secondly, the signature is a universal nonlinearity: linear functionals on the signature can approximate any continuous function of the path arbitrarily well. This allows linear models (like linear regression) trained on signature features to learn complex, nonlinear relationships in the original data space.
Truncation and log-signature. The full signature is an infinite-dimensional object. For computational feasibility, we compute the truncated signature up to level , denoted as . The dimension of the feature vector for a path in truncated at level is , which grows geometrically with .
To mitigate this dimensionality explosion, we utilize the log-signature . The logarithm of the signature maps the elements from the tensor algebra into the underlying Lie algebra. The log-signature is a more compact representation that retains the same information as the signature (up to tree-like equivalence) but removes the redundant terms generated by the shuffle product.
The dimension of the log-signature at level is given by Witt’s formula, which is significantly smaller than . For example, while the signature of a path in truncated at has 30 terms, the log-signature has only 8.
Approach
We propose an encoder-decoder architecture for synthesizing programs from execution traces. Our pipeline consists of three key networks: (1) a state encoder that embeds the semantic state of the environment, where each state embedding is a -dimensional point on the latent trace. Next, we use (2) a trace encoder that embeds state sequences into a single representation that gets passed to (3) a Transformer-based program decoder to synthesize the trace-generating program. Our trace encoder is based on the path log-signature transform, which captures the geometric properties of the state sequence. An overview of our architecture is shown in Figure 1. Note that Karel grids are just one example of a domain to which our approach applies; the same architecture and training procedure are used for the List and RASP domains.

Figure 1. Overall trace-to-program architecture.
Problem formulation
We consider the general task of trace-to-program synthesis: given a set of execution traces produced by an unknown program, recover a program in a target domain-specific language (DSL) that reproduces them. Formally, fix a DSL and a runtime environment that endows with a state space and an execution semantics: running a program from an initial state produces a trace
where is the (program- and state-dependent) execution length. Given a set of traces produced by a hidden program from initial states , the goal is to learn a mapping such that for every . Different choices of instantiate different program-induction domains. Throughout, we use to denote the -th trace and its length.
We illustrate the formulation with the Karel [24] and List DSLs (Figure 2), which share an identical control-flow skeleton (sequencing, conditionals, bounded repetition, unbounded loops over a perception predicate) and differ in their state-dependent perceptions and primitive actions. RASP programs (Figure 2c) have no intermediate states, so there is an input and a position , and , with the input with its -th token set to .

Figure 2. The Karel, List, and RASP domain-specific languages used in our experiments. Karel and List support classical control flow (sequencing, conditionals, bounded repetition, unbounded loops over a perception predicate) and differ in their state-dependent perceptions and primitive actions. A RASP program is a single sequence operation () or a COMBINE of two categorical ones (); DEF and m) are the start/end tokens.
Each state is mapped to a dense embedding by a domain-specific encoder . For grid-based domains such as Karel, is a Convolutional Neural Network applied to the visual grid; for symbolic domains such as list manipulation, is a small elementwise embedder; for RASP, it is a linear map followed by a residual MLP. In all cases, each trace is transformed into a sequence of latent vectors .
Why signatures match programs
Encoding each trace by its (log-)signature, rather than by a learned recurrent or attention-based summary, is the central design choice of our approach. Two foundational results from rough path theory ground this choice.
First, a program is determined, up to behavioral equivalence, by the distribution it induces over execution traces, with the randomness coming from the choice of initial state. Chevyrev and Lyons [6] show that the expected signature uniquely characterizes whenever it has an infinite radius of convergence, which holds automatically for bounded-length traces such as ours. Aggregating per-trace signatures across multiple executions of the same program therefore estimates an object that, in principle, suffices to identify the generating program.
Second, by Chen’s identity [3], the signature is multiplicative under any temporal split of a path:
This is an algebraic property of paths, not of program syntax: traces whose embedded paths share a contiguous sub-segment (e.g., the same loop body iterated, the same inner subroutine called) share a corresponding signature factor, so structurally similar executions land in structurally similar regions of the embedding space. As such, signatures respect the temporal structure of any single execution, equipping the embedding manifold with closed-form algebraic structure under temporal sub-decomposition.
By contrast, none of the baseline encoders has a closed-form law relating the embedding of a trace to those of its parts: an LSTM’s embedding depends on state order through a fixed recurrence, a Transformer encoder recovers order only because its positional encoding breaks the permutation equivariance of self-attention, and the truncated Fourier spectrum of a concatenation cannot be recovered from the spectra of its parts.
Trace encoding via signature-based transforms
Embedding a sequence given the embeddings of its elements (states in our case) typically involves a choice of an aggregation scheme, such as recurrence in LSTMs and pooling as well as [CLS] tokens for Transformers. In practice, this choice is nontrivial and depends on the task at hand. For example, recurrent aggregation famously suffers from forgetting and vanishing gradients in long sequences. The signature is a natural aggregator: it outputs a fixed-size embedding regardless of the sequence length, and its runtime and memory complexities are linear in the sequence length rather than quadratic as in Transformers.
A more fundamental difference that sets the signature apart from LSTM and Transformer encoders is that it operates on geometry while the latter operate on content. The signature captures the geometric shape of the path traced out by the sequence of state embeddings, while LSTMs and Transformers learn a content-based summary. We argue that programmatic behavior is fundamentally geometric: the control flow of a program structures the execution into subroutines, loops, and conditionals that manifest as geometric features in the trace. By encoding geometry directly, the signature is naturally aligned with the underlying structure of program execution and bypasses content-level noise.
Positional augmentation. Standard path signatures satisfy tree-like equivalence, meaning they are invariant to backtracking (e.g., a sequence of actions like turnRight, turnLeft that returns to the original state might be nullified). To resolve this and preserve the distinct execution history, we augment the state embeddings with positional encodings. We define a time-augmented path sequence where:
Here, is a fixed sinusoidal positional encoding. Because differs at every step, an action sequence that returns to an earlier state reaches a different point of the augmented path, so it no longer forms a backtracking segment that the signature ignores. In many standard signature applications, time is instead added as an extra channel, which rules out tree-like equivalence altogether. In our setting, we found that additive positional encodings work better on Karel and List domains. On RASP, where step of every trace sets the swept token to , the log-signature encoder instead appends a one-hot encoding of .
Log-signature encoder. We treat the sequence as a discrete approximation of a continuous path . To handle variable-length traces within the batch, we pad by repeating the embedding of the last state in the trace: , . Each repeated point adds a zero increment, whose signature is the identity , so by Chen’s identity the padding leaves the signature unchanged; this is an instance of the invariance of the signature to reparameterization, as stalling at a point does not change the shape of the path. This is preferable to zero-padding, which introduces an artifact in the form of a false increment at the end of the path.
Before adding the positional encoding, we normalize every step of the embedded trace to unit length while keeping its direction: with , we set and , where the small constant keeps zero-length steps at zero, and use in place of when forming . We apply this normalization because the signature has no weights of its own to rebalance steps of different sizes: its level- terms are sums of products of increments, so a few long steps dominate it. In List, for example, pushZero and pop shift several elements at once, and their steps in the embedded path are often ten times longer than those of incElem and decElem, so the in-place edits contribute little to the log-signature. With unit steps, every state change contributes equally, and the log-signature records which changes occurred and in what order rather than how far each one moved the embedding.
We then compute the truncated log-signature of this padded path up to level , denoted . We choose as the smallest truncation level that retains pairwise interaction terms between coordinates of the embedded path; an ablation over in Appendix § 8.§ 1 shows that going beyond yields no consistent benefit, at a substantial dimensional cost. The log-signature creates a fixed-size representation of the path regardless of the trace length . Since the dimension of the log-signature grows rapidly with the truncation level , we project it back to a compact representation space via a learnable linear map with bias :
The projection is the only trainable component of this encoder, so the underlying signature representation remains parameter-free.
Program decoding
To generate the program tokens, we employ a Transformer decoder. The decoder conditions on the set of trace embeddings through a cross-attention mechanism.
where is the -th token of the predicted program . The decoder queries the trace memory , allowing the model to attend to specific features of the execution traces (captured by the signatures) that correspond to specific program subroutines. Similar to Bunel et al. [2], we mask out syntactically invalid tokens as they are easy to recognize. In doing so, we ensure that the decoder always outputs syntactically valid programs.
Optimization
The model is trained end-to-end by minimizing the cross-entropy loss between the predicted program distribution and the ground-truth program :
Contractivity and bootstrapping. We empirically observe that our trace-to-program pipeline is naturally contractive: in a sizable fraction of cases, the model produces a program that is shorter than the ground-truth program but still reproduces every supervising trace. We exploit this property as a way to expose redundancy in the ground-truth labels without external supervision. Starting from the original training set , we interleave training with relabeling passes, one every five epochs after a five-epoch warm-up: at pass , the current model generates a prediction for each training instance, and we form from by replacing each label whenever the prediction is both valid (executing on each initial state in reproduces the corresponding trace) and shorter than the current label:
Training then continues on , and the total training-program length decreases monotonically. The cumulative length reduction and the fraction of training samples whose labels are ever shortened give a direct, encoder-derived lower bound on how much shorter the supervision could have been, with no external oracle required. We quantify this on redundancy-injected versions of our datasets (§ 5.1) in Section 5.4.
Experiments
Datasets
We evaluate trace-to-program synthesis on three complementary program-induction domains: Karel, a 2D grid-world programming language with visual state, List, a symbolic list-manipulation language, and RASP, a language for expressing Transformer computations as sequence operations. Together they cover a broad slice of the program-induction problem space: Karel is representative of visual and spatial-reasoning domains (robotics control, tile-based puzzles, agent navigation), List is representative of symbolic array- and string-manipulation domains (sorting, searching, counting, sequence transformations), and RASP is representative of functional sequence-to-sequence programs. For Karel and List we adopt a similar data generation process to that of Trivedi et al. [28], with 100K training and 2500 test samples. To mitigate overfitting during training, we randomly sample 5 out of 6 traces for each program, and use all 6 traces during testing. An output program is marked as correct if it reproduces all input traces when executed on their respective initial states.
RASP. RASP [31] composes elementwise maps (MAP), positional shifts (SHIFT), thresholds (CMPC), and selector-width counts (HIST, COUNT) over a token sequence. RASP programs can be compiled into Transformer weights [18], and Transformers can be trained so that they convert into human-readable programs [9]. We use programs of nesting depth at most two (Figure 2c) on length-16 sequences of tokens in , one per distinct non-constant behavior: 5,816 for training and 2,500 for testing, so every test program computes an unseen function. A trace is a sweep: from a random input, the token at one position is set to in turn, and each step is the pair of input and output sequences, a point in . Each program has sweeps at distinct positions, of which we sample 4 during training and use all 8 for testing; redrawing the sweeps of the training programs gives 32K training samples. A decoded program is correct if it reproduces every output of every sweep.
Redundancy-injected datasets. Bootstrapping (§ 4.5) can only shorten a label if a shorter program reproduces the same traces, and our datasets contain little such redundancy: on the Karel and List test splits, a greedy search over trace-preserving local edits shortens about a quarter of the programs but removes only 4.5% and 5.2% of their tokens. To highlight the contractive effect of our pipeline, we therefore build redundancy-injected versions of the three datasets, denoted Karel⁺, List⁺, and RASP⁺, by rewriting the ground-truth programs. In each split, half of the programs are rewritten with extra structure that leaves their actions (Karel, List) or outputs (RASP) unchanged on every input, so injected tokens make up about 20% of the total. For Karel and List, the rewrites invert standard simplification rules, e.g. or . For RASP, we rewrite one categorical operation into an equivalent COMBINE of two, e.g. CMPC EQ into COMBINE min (CMPC GEQ ) (CMPC LEQ ), allowing COMBINEs to nest. The traces are unchanged, and we use these datasets only for the bootstrapping experiment (Finding #2).
Baselines
We compare our log-signature trace encoder against three classical baselines that differ from it only in the trace encoder, up to one minior exception for Fourier (Appendix § 8.7).
LSTM. We pass the state embeddings as the input sequence to an LSTM [13], and the last hidden state is taken as the trace embedding. Although the temporal order is implicit in LSTM recurrence, we found that adding sinusoidal positional encoding to the input state sequence improved its performance.
Transformer. We use a 2-layer Transformer encoder [29] with 8 self-attention heads and sinusoidal positional encoding added to the input sequence. We found that adding more layers did not significantly improve performance, and resulted in a collapse in the case of 8 or more layers. We obtain the trace embeddings by mean-pooling over the output state embeddings.
Fourier transform. We compute the truncated orthonormal real-to-complex DFT [7] of the (positionally augmented) state sequence, retaining the lowest-frequency modes and stacking their real and imaginary parts into the trace embedding. Full equations are given in Appendix § 8.§ 6.
Hyperparameters
All models are trained for 100 epochs with a batch size of 32 and an embedding size of 256 ( for the RASP log-signature encoder). We use the Adam optimizer [16] with a learning rate of (details in Appendix A.7). We clip the global gradient norm at 0.5 [23]. The training pipeline is implemented using PyTorch, including a PyTorch-native reimplementation of Signatory [14] for differentiable log-signature computations, and runs on a single NVIDIA A100 GPU.
Results
We organize our findings around three claims, each stated up front and then supported by the corresponding evidence. We report semantic accuracy: the fraction of test programs whose decoded program is correct in the sense of § 5.1, i.e., it reproduces every given trace (Karel, List) or output (RASP), whether or not it matches the ground-truth program token for token.
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. Figure 3 reports test semantic accuracy across training data volumes for each encoder on the Karel, List, and RASP domains. The log-signature encoder is the most accurate encoder at 11 of the 12 (domain, volume) settings. The exception is Karel at full volume, where the Transformer and the LSTM lead it by more than the spread across seeds. The advantage is largest in the low-data regime: with a quarter of the training data, the log-signature encoder nearly triples the accuracy of the strongest baseline on Karel and clearly leads it on List and RASP, where the margin narrows at full volume. The parametric encoders need the most data: with a quarter of the training data, the LSTM and Transformer barely learn Karel, and on RASP they stay far behind the log-signature encoder at every volume. The Fourier encoder beats the LSTM and Transformer at low volumes on Karel and at every volume on RASP, but trails them on Karel at full volume and is the weakest encoder on List at every volume. We further find that the log-signature encoder reaches 90% of its best accuracy in fewer epochs than the LSTM and Transformer at every volume where these learn, and the Fourier encoder does so in most settings. Two ablations indicate that the advantage of the log-signature encoder does not stem from the size of its representation. When we vary the width of the state embeddings at 50% of the training data volume, even the narrowest log-signature encoder is more accurate than every baseline at any width on List and RASP, and on Karel it leads from onwards (Figure 7, Appendix § 8.§ 3). Furthermore, the log-signature encoder performs nearly identically to its full-signature counterpart on all three domains, while using half as many features and, on Karel and List, about a third fewer parameters (Figure 6, Appendix § 8.§ 2).

Figure 3. Generalization performance across training data volumes for each trace encoder on the Karel, List, and RASP domains. Training data volume is a percentage of each domain’s full training set, on a log scale. Each point is the highest test semantic accuracy over the 100 training epochs, averaged over 3 random seeds. The test set (2500 samples) is the same for all volumes.

Figure 6. Signature versus log-signature encoder at truncation level , trained on each domain’s full training set.

Figure 7. Semantic accuracy of each trace encoder as a function of the state embedding width , at 50% of each domain’s training data. Each point is the highest test semantic accuracy over the 100 training epochs on the 2500-sample test set.
Finding #2: Bootstrapping exposes substantial redundancy in the ground-truth supervision, with no external oracle required. We run the bootstrapping procedure of § 4.5 on each (encoder, task) configuration, using the redundancy-injected datasets Karel+, List+, and RASP+ (§ 5.1), and report two quantities: Tokens removed, the cumulative percent reduction in total training-program token count from the labels of the redundancy-injected dataset to the final labels; and Programs shortened, the percent of training programs whose label was shortened at least once during the procedure. We frame this as a measurement rather than a self-improvement claim: the procedure replaces each ground-truth label only when the model has produced a strictly shorter program that is verified to reproduce every supervising trace, so both quantities are encoder-derived lower bounds on how compressible the supervision was. Stronger encoders expose more of this redundancy because they recover more valid alternatives; the absolute numbers therefore vary across the rows of Table 1, but every cell is a lower bound on the same underlying quantity. Notably, every encoder, including the parametric LSTM and Transformer baselines and the spectral Fourier baseline, produces nontrivial values of both quantities, so contractivity is better understood as a property of the trace-to-program pipeline than as a property unique to any one encoder.
| Encoder | Karel+ Tokens removed (%) | Karel+ Programs shortened (%) | List+ Tokens removed (%) | List+ Programs shortened (%) | RASP+ Tokens removed (%) | RASP+ Programs 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 |
Table 1. Reduction statistics in the ground-truth supervision of the redundancy-injected datasets (§ 5.1), uncovered by bootstrapping.
Finding #3: The log-signature encoder induces a more interpretable latent geometry. We investigate the geometry of the learned representations using t-SNE [20]. Figure 4 shows the projection of high-dimensional latent state embeddings (the state embeddings each trace encoder reads, after the unit-step normalization and positional encoding) into a reduced two-dimensional space. This is essentially a visualization of our main thesis: that programs have an inherent shape that manifests in their traces. As shown in Figure 4, the embeddings of the log-signature-based model are much more spatially structured and interpretable: states from the same execution trace remain clustered and form separate chains of nearby points within the embedding manifold, without crossing into each other as is the case with the baselines. This geometry reveals that the model preserves the sequential nature of the data. Figure 8 in Appendix § 8.§ 4 extends this view to the List and RASP domains.
Figure 4. t-SNE projections of the embedded traces that each trace 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 temporal 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 as in § 4.3 before the positional encoding is added. Each panel is a separate t-SNE fit.
Figure 8. State-level t-SNE projections as in Figure 4, for each trace encoder (columns) on the Karel, List, and RASP domains (rows), five test programs per domain with six traces each on Karel and List and eight on RASP. Each line is one trace, the traces of a program share a color, and each panel is a separate t-SNE fit.
Conclusion
Summary. In this paper, we brought a rough-path-theoretic perspective to program induction, exploring the path log-signature transform as a trace encoder for trace-to-program synthesis. Our results have shown an inherent advantage of the log-signature encoder over traditional sequence models. However, this is not to say the signature transform should necessarily be treated as a complete replacement for other sequence encoders, but rather to establish grounds for future research in employing geometric methods for program learning. The essence of this work is demonstrating that geometry potentially reveals more about programmatic structure than content. Furthermore, we have empirically shown that the trace-to-program pipeline is naturally contractive, which, as our experiments on redundancy-injected datasets show, serves as a convenient tool for exposing redundancy without any external oracle. Finally, we have shown that the log-signature encoder induces a markedly more interpretable latent geometry than classical sequence models.
Limitations. The truncated log-signature provides a compact representation for moderately complex traces, but the dimensionality of the feature space still grows exponentially with the truncation level . We keep small in practice (Appendix § 8.§ 1), but very-long-horizon programs that require fine-grained higher-order interactions across the full trace remain a challenging case for the approach.
Acknowledgments and Disclosure of Funding
This work was partially supported by the European Union with ERC Grant HYPER (No. 101055412). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
Appendix
This appendix collects probe experiments that complement the three main findings in § 5. Each subsection is self-contained and may be read independently of the others.
Signature truncation depth ablation
The truncation level controls the maximum interaction order captured by the log-signature: retains only the displacement of the path, adds pairwise interactions (Lévy areas), and higher captures progressively higher-order shape statistics at exponential dimensional cost. We jointly sweep and the underlying state embedding dimension at half of each domain’s training data volume, and report semantic accuracy on the standard 2500-sample test set.
Figure 5 shows that falls far short of on every domain and dimension, and stays near zero on Karel and RASP, confirming that pairwise interactions are the load-bearing component of the representation. Going further to does not help on List and RASP, where it matches at and is at or below it at larger . On Karel, improves on at and , but not at . Since multiplies the number of log-signature features by more than 40 at for a gain on one domain only, we use in the main experiments.
Figure 5. Truncation depth ablation at half the training data volume (50K samples for Karel and List, 16K for RASP). Semantic accuracy (the highest over the 100 training epochs) on the 2500-sample test set as a function of the log-signature truncation level and the underlying state embedding dimension .
Signature versus log-signature
The log-signature is the compact alternative to the full signature: it removes the redundant terms generated by the shuffle product. At these redundant terms make up half of the signature. For a path with channels, the signature has non-constant coordinates and the log-signature . The extra coordinates are the symmetric part of the second level, which by the shuffle identity equals , i.e. products of first-level coordinates, while its antisymmetric part is the Lévy area that the log-signature keeps. To test whether these redundant coordinates help the learned projection, we replace the log-signature with the signature at , keep every other setting of the main experiments, and train on each domain’s full training set (100K samples for Karel and List, 32K for RASP). Figure 6 shows that doubling the number of features leaves semantic accuracy essentially unchanged: the two encoders differ by at most 0.011 on any domain, in either direction. Since the input of the projection doubles, the signature model is also larger, with about 50% more parameters on Karel and List. The log-signature thus matches the signature at half the representation size, which is why we use it throughout.
State embedding width
At , the log-signature of a -dimensional path has coordinates, so the advantage of the log-signature encoder in Finding #1 could come from this large representation rather than from the structure of the signature. To test this, we vary the width of the state embeddings fed to every trace encoder, at 50% of each domain’s training data volume and with all other settings as in the main experiments. For the LSTM only the input width changes, the Transformer operates at width throughout, and the number of Fourier features grows linearly with . Figure 7 shows that the log-signature encoder is the least sensitive to this choice. On List and RASP its accuracy is nearly flat across the whole range, and even its narrowest variant is more accurate than every baseline at any width. Karel is the exception: there the log-signature encoder gains substantially from wider embeddings, and the LSTM matches or exceeds it at the two smallest widths. The baselines respond to width in different ways. The Transformer is the most width-hungry encoder: it improves markedly as grows on List and RASP but trails far behind at small widths, and it stays low at every width on Karel. The Fourier encoder shows the opposite trend, being most accurate at the smallest width and degrading as grows on all three domains. The LSTM peaks at an intermediate width and remains far behind on RASP throughout. Overall, the ranking of the main experiments does not hinge on the chosen width: the log-signature encoder leads at every width on List and RASP and from onwards on Karel, and on two of the three domains a narrow state embedding, and hence a small log-signature, suffices.
State-level latent geometry on all domains
Figure 8 extends the state-level view of Finding #3 (Figure 4) from Karel to the List and RASP domains, with the same projection and the same unit-step normalization of every encoder’s state embeddings. To quantify how well the traces stay apart, we take, for every state, its five nearest states in the full embedding space (over 20 test programs, before the t-SNE projection) and count the share that belongs to the same trace. The log-signature encoder scores 1.00 on all three domains: the nearest neighbors of every state lie on its own trace. On Karel, all three baselines fall far short of this, with most of a state’s neighbors coming from other traces. On RASP, they range from about half for the LSTM to nearly perfect for the Fourier encoder, and on List all four encoders keep most traces apart.
Encoder forward-pass wall-clock scaling
To check the linear-time claim empirically, we time the forward pass of each trace encoder on a single trace of length , up to , on one NVIDIA A100 GPU. Each encoder has its configuration from the Karel and List experiments, with state embeddings of width 256, and only the trace encoder itself is timed, not the state encoder, the set encoder (Appendix § 8.7) or the program decoder around it. Figure 9 shows that the log-signature and LSTM encoders grow linearly with , while the Transformer grows quadratically, as its attention compares every pair of steps. The Transformer overtakes the LSTM at around 45,000 steps, and at it is about 18 times slower than the log-signature encoder, which is in turn about 8 times faster than the LSTM. The Fourier encoder, whose FFT is cheap at these lengths, is the fastest throughout.

Figure 9. Forward-pass wall-clock time of each trace encoder as a function of the trace length , on one trace of width-256 state embeddings on one NVIDIA A100 GPU, with each encoder configured as in the Karel and List experiments. Only the trace encoder is timed. Each point is the mean of 5 timed passes after 3 warm-up passes; the standard deviations are below 2 ms.
Fourier encoder: full definition
For a single trace, we drop the trace index : let be its state embeddings and their positionally augmented version, with the additive sinusoidal positional encoding PE of § 4.3. The Fourier encoder applies the orthonormal DFT to each of the coordinates of , keeps the lowest-frequency modes, and stacks their real and imaginary parts into the trace embedding :
Further optimization details
Set encoder. Before decoding, the trace embeddings of a program pass through a set encoder, a 2-layer Transformer encoder with 8 heads and no positional encoding, which lets each trace embedding attend to the others. We treat it as part of the program decoder, whose cross-attention reads the outputs of the set encoder rather than itself. The Fourier encoder is the one exception and is trained without the set encoder on all three domains, since with it the Fourier model did not learn on Karel at any training data volume.
Weight decay. All models are trained with Adam and without weight decay, except the LSTM on RASP, which we train with AdamW [19] and a weight decay of 1.0 on its weight matrices. Without weight decay, the RASP LSTM does not learn: its semantic accuracy stays at about 0.03 or below at every state embedding width and training data volume we tried, and weight decay rescues it partly.
Compute resources
Every run uses a single NVIDIA A100 GPU. At half the training data volume, a training run takes about 4 h on Karel, 1–2 h on List, and 0.5 h on RASP, and the time grows roughly in proportion to the volume. A bootstrapping run takes about 10 h on Karel+, 5 h on List+ (with two runs sharing one GPU), and 1–2 h on RASP+. The experiments reported in this paper total roughly 500 GPU-hours; the full project, including preliminary and discarded configurations, used more.
References
- [1]Matej Balog, Alexander L Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. DeepCoder: Learning to write programs. In International Conference on Learning Representations, 2017.arxiv.org/abs/1611.01989
- [2]Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. In International Conference on Learning Representations, 2018.arxiv.org/abs/1805.04276
- [3]Kuo-Tsai Chen. Integration of paths, geometric invariants and a generalized Baker-Hausdorff formula. Annals of Mathematics, 65(1):163–178, 1957.
- [4]Xinyun Chen, Chang Liu, and Dawn Song. Execution-guided neural program synthesis. In International Conference on Learning Representations, 2019.
- [5]Ilya Chevryev and Andrey Kormilitzin. A primer on the signature method in machine learning. In Signature Methods in Finance: An Introduction with Computational Applications, pages 3–64. Springer Nature Switzerland Cham, 2025.
- [6]Ilya Chevryev and Terry Lyons. Characteristic functions of measures on geometric rough paths. 2016.
- [7]James W Cooley and John W Tukey. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90):297–301, 1965.DOI
- [8]Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. RobustFill: Neural program learning under noisy I/O. In International Conference on Machine Learning, pages 990–998. PMLR, 2017.arxiv.org/abs/1703.07469
- [9]Dan Friedman, Alexander Wettig, and Danqi Chen. Learning transformer programs. Advances in Neural Information Processing Systems, 36, 2023.
- [10]Alex Graves, Greg Wayne, and Ivo Danihelka. Neural Turing machines. arXiv preprint arXiv:1410.5401, 2014.arxiv.org/abs/1410.5401
- [11]Lajos Gergely Gyurkó, Terry Lyons, Mark Kontkowski, and Jonathan Field. Extracting information from the signature of a financial data stream. arXiv preprint arXiv:1307.7244, 2013.
- [12]Ben Hambly and Terry Lyons. Uniqueness for the signature of a path of bounded variation and the reduced path group. Annals of Mathematics, 171(1):109–167, 2010.DOI
- [13]Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8):1735–1780, 1997.
- [14]Patrick Kidger and Terry Lyons. Signatory: differentiable computations of the signature and logsignature transforms, on both CPU and GPU. In International Conference on Learning Representations, 2021. https://github.com/patrick-kidger/signatoryarxiv.org/abs/2001.00706
- [15]Patrick Kidger, Patric Bonnier, Imanol Perez Arribas, Cristofer Salvi, and Terry Lyons. Deep signature transforms. Advances in Neural Information Processing Systems, 32, 2019.
- [16]Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.arxiv.org/abs/1412.6980
- [17]Songxuan Lai and Lianwen Jin. Offline writer identification based on the path signature feature. In 2019 International Conference on Document Analysis and Recognition (ICDAR), pages 1137–1142. IEEE, 2019.arxiv.org/abs/1905.01207
- [18]David Lindner, János Kramár, Sebastian Farquhar, Matthew Rahtz, Tom McGrath, and Vladimir Mikulik. Tracr: Compiled transformers as a laboratory for interpretability. Advances in Neural Information Processing Systems, 36, 2023.arxiv.org/abs/2301.05062
- [19]Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019.
- [20]Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9(Nov):2579–2605, 2008.
- [21]James Morrill, Cristopher Salvi, Patrick Kidger, and James Foster. Neural rough differential equations for long time series. In International Conference on Machine Learning, pages 7829–7838. PMLR, 2021.arxiv.org/abs/2009.08295
- [22]Arvind Neelakantan, Quoc V Le, and Ilya Sutskever. Neural programmer: Inducing latent programs with gradient descent. In International Conference on Learning Representations, 2016.arxiv.org/abs/1511.04834
- [23]Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International Conference on Machine Learning, pages 1310–1318. PMLR, 2013.arxiv.org/abs/1211.5063
- [24]Richard E Pattis. Karel the robot: a gentle introduction to the art of programming. John Wiley & Sons, 1994.
- [25]Scott Reed and Nando de Freitas. Neural programmer-interpreters. In International Conference on Learning Representations, 2016.arxiv.org/abs/1511.06279
- [26]Eui Chul Shin, Illia Polosukhin, and Dawn Song. Improving neural program synthesis with inferred execution traces. Advances in Neural Information Processing Systems, 31, 2018.
- [27]Shao-Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph Lim. Neural program synthesis from diverse demonstration videos. In International Conference on Machine Learning, pages 4790–4799. PMLR, 2018.
- [28]Dweep Trivedi, Jesse Zhang, Shao-Hua Sun, and Joseph J Lim. Learning to synthesize programs as interpretable and generalizable policies. Advances in Neural Information Processing Systems, 34:25146–25163, 2021.arxiv.org/abs/2108.13643
- [29]Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.arxiv.org/abs/1706.03762
- [30]Abhinav Verma, Vijayraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. In International Conference on Machine Learning, pages 5045–5054. PMLR, 2018.arxiv.org/abs/1804.02477
- [31]Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In International Conference on Machine Learning, pages 11080–11090. PMLR, 2021.arxiv.org/abs/2106.06981
- [32]Yujun Yan, Kevin Swersky, Danai Koutra, Parthasarathy Ranganathan, and Milad Hashemi. Neural execution engines: Learning to execute subroutines. Advances in Neural Information Processing Systems, 33:17298–17308, 2020.arxiv.org/abs/2006.08084


