- 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
-
Research value: Recovering reusable recurrence relations from small-scale exact computations provides a concrete, verifiable scenario for automated algorithm discovery.
-
Interpretable and executable output: The recovered recurrences can be directly inspected and executed independently, and verified by reconstructing full DP tables.
-
Solid mechanism analysis: The method can distinguish between syntactic consistency and functional correctness.
Critical weaknesses
-
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.
-
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.
-
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.
-
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."
-
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
-
Can you elaborate on the comparision to Z3/symbolic solvers?
-
Is there more evidence on the scalability of the method?
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