acceptodds
Under review as a conference paper at ICLR 2027

DeepDP: Automated Synthesis of Recurrences for Dynamic Programming Problems

Abstract

Dynamic programming (DP) solves many problems efficiently once an appropriate recurrence is known, but discovering that recurrence is often the key algorithmic step. We ask whether this process can be reversed: can small DP tables, constructed by solving each state independently through exhaustive search, provide enough evidence to recover a recurrence that scales to larger instances? We present DeepDP, which learns a structural prior from synthetic executable rules, represents recurrences through typed DP components, and adapts to new tasks using only table-reconstruction feedback, without target recurrence labels. Across 26 held-out tasks spanning four DP geometries, with target recurrence behaviors excluded from the training rule banks, DEEPDP achieves full functional generalization and improves mean accuracy by up to 49.11 percentage points over program-synthesis and symbolic baselines in the low-information regime. These results show that small exact computations can support the discovery of interpretable, executable algorithmic structure.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Recurrence Synthesis, Dynamic Programming, Rule Recovery

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_FifBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes DeepDP to recover executable recurrence relations from solved Dynamic Programming (DP) tables. The method combines human-defined recurrence components, synthetic rule pre-training, and task adaptation based on table reconstruction rewards, requiring no ground-truth recurrence formulas for target tasks. The authors tested DeepDP on 26 held-out tasks across four DP structures, reporting 100% functional generalization accuracy.

Critical strengths
  1. Research value: Recovering reusable recurrence relations from small-scale exact computations provides a concrete, verifiable scenario for automated algorithm discovery.

  2. Interpretable and executable output: The recovered recurrences can be directly inspected and executed independently, and verified by reconstructing full DP tables.

  3. Solid mechanism analysis: The method can distinguish between syntactic consistency and functional correctness.

Critical weaknesses
  1. Conclusions on "low-information recovery" require qualification: Although only a single table is input during inference, the model has already adapted using 900 training tables for that task and used 600 validation tables for model selection. Thus, the results are not showing as discovering unknown recurrences solely from a single table.

  2. Unequal information conditions compared to symbolic baselines: DeepDP accumulates target task information through adaptation, whereas Z3 (as described) works based on the current single table. Symbolic baselines utilizing the same cumulative samples and clear search budgets should be added.

  3. Algorithm discovery relies heavily on strong human priors: The state space, input features, execution order, and candidate components are pre-defined, limiting the system to combining recurrences within a constrained rule space. The human modeling effort required to extend this to new DP types has not been evaluated.

  4. Insufficient evidence for small-to-large scale extrapolation: Achieving 100% accuracy on the test set is valuable, but the paper does not explicitly state the scale ranges for training and testing, nor does it conduct out-of-distribution, length, or numerical range testing to validate the core motivation of "discovering scalable algorithms from small tables."

  5. Unclear independent gains from pre-training and complex pipelines: Existing ablations removed adaptation and self-distillation, but lacked comparisons such as direct adaptation from random initialization or simple enumerative search under the same budget. Compute costs were also unreported, making it difficult to justify the necessity and efficiency of extensive synthetic pre-training.

Questions for authors
  1. Can you elaborate on the comparision to Z3/symbolic solvers?

  2. Is there more evidence on the scalability of the method?

Reviewer_Lj83OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents DeepDP, a two-stage model that recovers executable DP recurrences from solved tables. It first learns recurrence structure from synthetic rules across four DP geometries, then adapts to new tasks using solved support tables and execution-based reconstruction rewards, without target recurrence labels. Candidates are evaluated by their ability to reconstruct held-out tables, and the paper reports strong functional generalization over symbolic and program-synthesis baselines. However, its practical use case is unclear: every new task requires solved tables and task-specific adaptation, and no comparison is made with contemporary LLM-based methods.

Critical strengths
  1. A formulation guided by execution. The paper captures recurrence using typed DP constructs and validates potential rules by executing them and comparing their respective tables. This approach is a good way to relate structural prediction to executable validity, and it makes sense to allow behaviorally similar recurrences instead of syntactically identical ones.

  2. Comprehensive evaluation in the proposed scenario. The authors conduct their experiments on 26 tasks and four DP geometries and also conduct experiments without adaptation and self-distillation to validate the exactness of rule generation vs. table construction.

Critical weaknesses
  1. The practical benefit of training a specialized model is not justified. The paper does not compare DeepDP with current frontier LLMs or modern small models. Recurrence induction from a few demonstrations may already be feasible for models such as GPT-6 Astra or Qwen3.5. It is therefore unclear why a dedicated architecture and training pipeline are preferable to prompting or adapting a general-purpose model.

  2. Deployment is inconvenient, and adaptation costs are not reported. Applying DeepDP to a new task requires solved DP tables and task-specific adaptation. In realistic settings, obtaining these tables may already require substantial computation or an additional exact solver. The paper should report adaptation time, optimization steps, compute requirements, and table-generation costs.

  3. The scale of the test problems is unclear. Although the paper reports the number of test tables and claims scalability, it does not specify the input-size ranges or table dimensions for different DP geometries. It is therefore difficult to determine whether the experiments demonstrate genuine scale extrapolation or only recurrence generalization within a similar synthetic size range.

  4. The baseline comparison is outdated. DeepCoder, DreamCoder, and Z3 are useful historical baselines, but the paper does not compare against recent LLM-based program-synthesis, execution-guided reasoning, or neural algorithmic-reasoning methods. Thus, its competitiveness against current alternatives remains unclear.

Questions for authors

Why is a dedicated recurrence-induction neural model necessary in the current LLM landscape?

Reviewer_2oHUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

DeepDP recovers executable dynamic-programming recurrences from completed small-instance tables within a supplied geometry-specific rule language. It pretrains geometry-specific support-table encoders and typed component decoders on synthetic executable rules, combining component supervision with execution reward. It then adapts to each target task using table-reconstruction feedback and an elite-rule self-distillation buffer, without target recurrence labels. The paper reports 100% functional generalization on 26 held-out tasks across four geometries, where a successful inference attempt must reconstruct every valid cell in all 1,500 test tables. Comparisons with adapted DeepCoder/DreamCoder and a Z3 solver focus on six low-information tasks. The reported single-table inference occurs after task-specific adaptation; it is not recovery of an entirely new task from only one table in total.

Critical strengths
  1. Predicting typed predecessors, costs, aggregators, boundaries, and branch choices is well aligned with the stated discovery problem. Evaluating by execution rather than only component-label accuracy appropriately accepts semantically equivalent rules, as illustrated by Boolean or/max and the Uncrossed Lines example. This is more informative than predicting only final answers.

  2. The benchmark spans 26 tasks and four state geometries, including interval and coupled-state recurrences. Requiring a recovered rule to reproduce every valid state of every held-out table is a strong empirical criterion. The adaptation and self-distillation ablations show large, geometry-dependent effects, making the contribution of task-level optimization visible.

Critical weaknesses
  1. Section 4.1 gives each target task 900 adaptation and 600 validation examples, while a single support table is supplied per episode or inference attempt. Appendix G states that DeepCoder and DreamCoder are also adapted, which is a useful control, but describes Z3 as synthesizing directly from the single observed support table. Thus at least the symbolic comparison mixes the effect of a learned prior with access to accumulated target-task evidence. Table 4 shows that adaptation is decisive, especially for interval tasks (0.51% without adaptation versus 100% with it), but there is no adaptation-from-random-initialization or matched cumulative-support symbolic control. The number of distinct adaptation tables actually consumed, update counts, candidate evaluations, and inference search budgets are also needed to interpret the gains. The reported result establishes successful post-adaptation recovery, but not yet the claimed source of the low-information advantage.

  2. The motivation emphasizes inferring from small tables and executing on larger instances, but the PDF does not give task-wise support/test size ranges or an explicit size-extrapolation experiment. Correctness on 1,500 sampled tables is valuable, but does not establish universal equivalence or larger-size behavior. In addition, Table 6 lists component types without their complete admissible value sets, and the behavioral fingerprint filter is described without the probe-set sizes and input ranges needed to audit the held-out-rule split. Because success depends on a finite supplied grammar, geometry, and feature interface, these details determine how challenging the discovery problem actually is. This is not an allegation of leakage; it is a limitation of the evidence available to assess the perfect results.

Questions for authors
  1. Protocol clarification: How many distinct target-task tables and execution evaluations does each method use before its 150 inference attempts, and what are the adaptation, checkpoint-selection, and inference budgets? In particular, what happens if Z3 or enumeration receives the same accumulated target-table constraints rather than only the final single table?

  2. Attribution request: Under the same target-data and execution budget, how does adaptation from a randomly initialized model compare with adaptation from the synthetic foundation model? Table 4 removes adaptation, but does not separate the value of pretraining from target-task search. A matched comparison could materially strengthen the central claim.

  3. Generalization clarification: Please give the complete rule-component domains, behavioral exclusion probe counts/distributions, and task-wise support/adaptation/test size ranges. Are there tests at substantially larger sizes and different value ranges? For low-canonical-agreement tasks, can the recovered rules be shown equivalent beyond the sampled test set, or characterized by counterexample search?

Comments on the paper

1 comment

Dear reviewers,

Thank you for your work reviewing this paper!

The authors have submitted their responses. If you haven't already, please acknowledge them in a comment and adjust your reviews as needed. The discussion period finishes on November 18.

Best regards, Area Chair

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.