TIIPS

Abstract

Abstraction and reasoning in program synthesis has seen significant progress through both inductive and transductive paradigms. Inductive approaches generate a program or latent function from input-output examples, which can then be applied to new inputs. Transductive approaches directly predict output values for given inputs, effectively serving as the function themselves. Current approaches combine inductive and transductive models via isolated ensembling, but they do not explicitly model the interaction between both paradigms. In this work, we introduce TIIPS, a novel framework that unifies transductive and inductive strategies by explicitly modeling their interactions through a cooperative mechanism: an inductive model generates programs, while a transductive model constrains, guides, and refines thesearch to improve synthesis accuracy and generalization. We evaluate TIIPS on two widely studied program synthesis domains: string and list manipulation. Our results show that TIIPS solves more tasks and yields functions that more closely match optimal solutions in syntax and semantics, particularly in out-of-distribution settings, yielding state-of-the-art performance. We believe that explicitly modeling the synergy between inductive and transductive reasoning opens promising avenues for general-purpose program synthesis and broader applications.

Core Technologies

💻 Execution-guided Inductive Program Synthesis
🧭 Transductive Guidance
🤖 Transformer-Based Synthesis Model
🎯 Keywords
Program Synthesis, Transductive Guidance, Compositional Generalization, Execution-Guidance

Motivation

Synthesizing programs directly from input-output examples is inherently difficult due to the large search space and the absence of intermediate supervision. To mitigate this, recent approaches employ explicit task decomposition: rather than synthesizing the full program in one step, the task is divided into smaller subtasks that are solved sequentially. This improves both interpretability and synthesis efficiency-but also introduces new challenges, especially when the predicted decompositions are misleading.

Recent work (Li et al., 2024) demonstrates that PBE tasks can be addressed using both inductive methods (program synthesis) and transductive methods (predicting the output directly via neural networks), and that these strategies are highly complementary. The below figure illustrates this phenomenon: The left task can be addressed without trandsductive guidance using a loop while the denoising task on the right is easier to solve using transductive guidance. We hypothesize that this complementarity also holds at the subtask level: some subtasks are best handled through inductive synthesis, while others benefit from transductive guidance.

Programmnig by example

Programming by Example (PBE) is a paradigm where users specify a program by providing a few input-output examples instead of writing code. The goal is to synthesize a program that is consistent with all provided examples-typically from a domain-specific language (DSL) designed for the task.

Illustrative PBE task

Methodology

We build on this insight by introducing a novel approach: Transductively Induced Iterative Program Synthesis (TIIPS). TIIPS leverages a powerful pre-trained Synthesizer to iteratively generate subprograms, which are executed on the task specification. The results of each execution are used to update the specification, and the process is repeated for n steps. If this inductive procedure fails to solve the task entirely, a second model predicts an intermediate output-effectively proposing a decomposition. This intermediate output defines a new PBE subtask, which is then passed back to the inductive procedure. After solving the subtask, the remaining steps of the original task are completed without further transductive guidance.

TIIPS

Evaluation Framework

Comprehensive evaluation across two program synthesis domains:

String manipulation
List manipulation

Quantitative Results

TIIPS consistently outperforms the baseline that uses no transductive guidance. This shows the importance of guidance, whether it is strict or sparse. TIIPS consistently improves the performance of decomposition-based synthesis by adaptively combining inductive and transductive methods. Specifically, on the List manipulation domain, TIIPS reaches 30% task accuracy, outperforming ExeDec significantly. Interestingly, the Baseline model performs similar to ExeDec on the List manipulation domain. While fully inductive baselines struggle in generalization tasks, they perform competitively in list operations-suggesting that transductive interventions should be applied selectively.

Qualitative Results

A key insight behind TIIPS is that transductive guidance can both help and hinder task-solving, depending on the context. TIIPS outperforms ExeDec while requiring fewer guidance calls, especially in the list domain, where most guidance is only needed early in the synthesis process (Figure below). This minimal and well-timed use of guidance allows TIIPS to maintain high performance with lower overhead, avoiding the pitfalls of rigid or excessive decomposition. The results highlight the benefits of adaptive, domain-aware guidance policies, which improve both efficiency and robustness across tasks.