Modelling Program Spaces in Program Synthesis with Constraints

• URL: http://arxiv.org/abs/2508.00005v1
• Date: Thu, 10 Jul 2025 14:00:53 GMT
• Title: Modelling Program Spaces in Program Synthesis with Constraints
• Authors: Tilman Hinnerichs, Bart Swinkels, Jaap de Jong, Reuben Gardos Reid, Tudor Magirescu, Neil Yorke-Smith, Sebastijan Dumancic,
• Abstract summary: A core challenge in program synthesis is taming the large space of possible programs.<n>We introduce BART, a solver that efficiently propagates and solves these constraints.
• Score: 6.9643857920106855
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: A core challenge in program synthesis is taming the large space of possible programs. Since program synthesis is essentially a combinatorial search, the community has sought to leverage powerful combinatorial constraint solvers. Here, constraints are used to express the program semantics, but not as a potentially potent tool to remove unwanted programs. Recent inductive logic programming approaches introduce constraints on the program's syntax to be synthesized. These syntactic constraints allow for checking and propagating a constraint without executing the program, and thus for arbitrary operators. In this work, we leverage syntactic constraints to model program spaces, defining not just solutions that are feasible, but also ones that are likely useful. To demonstrate this idea, we introduce BART, a solver that efficiently propagates and solves these constraints. We evaluate BART on program space enumeration tasks, finding that the constraints eliminate up to 99 percent of the program space, and that modeling program spaces significantly reduces enumeration time.

Related papers

• Programming over Thinking: Efficient and Robust Multi-Constraint Planning [54.77940831026738]
  SCOPE is a framework that disentangles query-specific reasoning from generic code execution.<n>SCOPE achieves state-of-the-art performance while lowering cost and latency.
  arXiv  Detail & Related papers  (2026-01-14T02:58:07Z)
• Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning [2.8425837800129696]
  Lagrangian decomposition (LD) is a relaxation method that provides a dual bound for constrained optimization problems. This work presents the first generic method for learning valid dual bounds in constraint programming.
  arXiv  Detail & Related papers  (2024-08-22T19:26:29Z)
• Intertwining CP and NLP: The Generation of Unreasonably Constrained Sentences [49.86129209397701]
  An approach for generating constrained sentences in CP has been proposed in (Bonlarron et al, 2023)<n>This paper introduces a novel more generic approach to tackle many of these previously untractable problems.<n>Thanks to CP-based approach, strongly constrained sentences have been successfully generated.
  arXiv  Detail & Related papers  (2024-06-15T17:40:49Z)
• NAPG: Non-Autoregressive Program Generation for Hybrid Tabular-Textual Question Answering [52.10214317661547]
  Current numerical reasoning methods autoregressively decode program sequences. The accuracy of program generation drops sharply as the decoding steps unfold due to error propagation. In this paper, we propose a non-autoregressive program generation framework.
  arXiv  Detail & Related papers  (2022-11-07T11:25:21Z)
• Learning logic programs by combining programs [24.31242130341093]
  We introduce an approach where we learn small non-separable programs and combine them. We implement our approach in a constraint-driven ILP system. Our experiments on multiple domains, including game playing and program synthesis, show that our approach can drastically outperform existing approaches.
  arXiv  Detail & Related papers  (2022-06-01T10:07:37Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space. We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
  arXiv  Detail & Related papers  (2022-03-11T17:19:26Z)
• Latent Execution for Neural Program Synthesis Beyond Domain-Specific Languages [97.58968222942173]
  We take the first step to synthesize C programs from input-output examples. In particular, we propose La Synth, which learns the latent representation to approximate the execution of partially generated programs. We show that training on these synthesized programs further improves the prediction performance for both Karel and C program synthesis.
  arXiv  Detail & Related papers  (2021-06-29T02:21:32Z)
• Controller Synthesis for Golog Programs over Finite Domains with Metric Temporal Constraints [5.254093731341154]
  Executing a Golog program on an actual robot typically requires additional steps to account for hardware or software details of the robot platform. We describe how to formulate such constraints based on a modal variant of the Situation Calculus. We show that for programs over finite domains, the problem of synthesizing a controller that satisfies the constraints while preserving the effects of the original program can be reduced to MTL synthesis.
  arXiv  Detail & Related papers  (2021-02-19T10:07:29Z)
• Representing Partial Programs with Blended Abstract Semantics [62.20775388513027]
  We introduce a technique for representing partially written programs in a program synthesis engine. We learn an approximate execution model implemented as a modular neural network. We show that these hybrid neuro-symbolic representations enable execution-guided synthesizers to use more powerful language constructs.
  arXiv  Detail & Related papers  (2020-12-23T20:40:18Z)
• Optimal Neural Program Synthesis from Multimodal Specifications [45.35689345004124]
  Multimodal program synthesis is an attractive way to scale program synthesis to challenging settings. This paper proposes an optimal neural synthesis approach where the goal is to find a program that satisfies user-provided constraints.
  arXiv  Detail & Related papers  (2020-10-04T20:51:21Z)
• Synthesize, Execute and Debug: Learning to Repair for Neural Program Synthesis [81.54148730967394]
  We propose SED, a neural program generation framework that incorporates synthesis, execution, and debug stages. SED first produces initial programs using the neural program synthesizer component, then utilizes a neural program debugger to iteratively repair the generated programs. On Karel, a challenging input-output program synthesis benchmark, SED reduces the error rate of the neural program synthesizer itself by a considerable margin, and outperforms the standard beam search for decoding.
  arXiv  Detail & Related papers  (2020-07-16T04:15:47Z)
• Generating Random Logic Programs Using Constraint Programming [12.47276164048813]
  We present a novel approach to generating random logic programs using constraint programming. We show how the model scales with parameter values, and use the model to compare probabilistic inference algorithms across a range of synthetic problems.
  arXiv  Detail & Related papers  (2020-06-02T19:12:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.