PaperlayerView exact revision on arXiv

Source-linked AI summary

Making Neural Programming Architectures Generalize via Recursion

Jonathon Cai, Richard Shin, Dawn Song

arXiv:1704.06611v1cs.LGcs.NEcs.PL

TL;DR

Learning programs from few examples remains difficult to generalize and verify. This paper adds recursion to neural programming architectures and reports perfect generalization across four tasks after very little training data.

  • Problem

    Neural program learners struggle to infer robust program semantics from few examples and to provide guarantees for unseen or more complex inputs.

  • Method

    The paper incorporates recursion into Neural Programmer-Interpreter-style architectures and trains recursive behavior through explicitly recursive execution traces.

  • Results

    100% accuracy on all valid inputs was achieved across addition, bubble sort, topological sort, and quicksort after training on very few examples.

  • Takeaways & Limitations

    Recursion enables provably perfect generalization in neural programs within the evaluated tasks.

  • Takeaways & Limitations

    For very large or potentially infinite input domains, exhaustive verification sets may be infeasible and the proposed verification procedure is inadequate.

Abstract

from arXiv · show

Empirically, neural networks that attempt to learn programs from data have exhibited poor generalizability. Moreover, it has traditionally been difficult to reason about the behavior of these models beyond a certain level of input complexity. In order to address these issues, we propose augmenting neural architectures with a key abstraction: recursion. As an application, we implement recursion in the Neural Programmer-Interpreter framework on four tasks: grade-school addition, bubble sort, topological sort, and quicksort. We demonstrate superior generalizability and interpretability with small amounts of training data. Recursion divides the problem into smaller pieces and drastically reduces the domain of each neural network component, making it tractable to prove guarantees about the overall system's behavior. Our experience suggests that in order for neural architectures to robustly learn program semantics, it is necessary to incorporate a concept like recursion.

1 INTRODUCTION

The paper addresses neural program synthesis’s difficulty learning robust semantics from few examples by explicitly incorporating recursion into neural architectures. It argues that recursion can improve generalization and enable provable guarantees for neural programs.

  • Motivation: Neural program synthesis is difficult because the space of possible programs and inputs is extremely large, while few examples cannot readily disambiguate the correct program.The goal is to learn the underlying program’s correct semantics from limited data.
  • Limitations: Existing evaluations primarily test whether models generalize expected behavior from simple training inputs to inputs of greater complexity.For addition, models trained on short inputs are tested on numbers with many more digits.
  • Limitations: Curriculum learning gradually increases input complexity, but prior models eventually fail beyond a certain complexity level across multiplication, sorting, and graph tasks.The cited failures include single-digit multiplication, bubble sort, and graph tasks.
  • Contribution: The authors propose explicitly incorporating recursion into neural architectures to reduce program complexity and improve learning of program semantics.They implement recursion in the Neural Programmer-Interpreter framework.
  • Contribution: Recursion makes neural programs easier to learn and generalize to unknown situations while enabling provable behavioral guarantees without exhaustively enumerating all inputs.The paper presents this as an investigation of provable generalization properties for neural programs.

2 THE PROBLEM AND OUR APPROACH

The paper argues that neural programs generalize poorly because they learn spurious dependencies and lack tractable guarantees, and proposes recursion as an essential abstraction for decomposition, generalization, and proof. It implements recursive neural programs in NPI by modifying training to learn recursive execution traces.

  • The Problem: Existing neural programming approaches generalize poorly because they may learn spurious dependencies on training-example characteristics such as input length.This causes models trained on simple inputs to fail on more complex inputs.
  • The Problem: Current neural programming approaches provide no method for provable generalization because their memory updates are complex and interdependent.These dependencies make behavior on previously unseen situations, including longer inputs, difficult to reason about.
  • Our Approach: Recursion is proposed as essential for neural programs to generalize and makes their generalization tractable to prove.The approach decomposes larger problems into smaller instances, enabling proofs based on correct base cases and reduction rules.
  • Our Approach: Recursion is implemented by allowing a neural program to call itself while storing the caller context on a stack and starting the callee in a fresh context.Tail recursion optimization can prevent excessive call-stack growth.
  • Our Approach: The authors enable recursive neural programs in NPI by modifying training, yielding perfectly generalizable programs for tasks such as sorting where the original non-recursive NPI fails.Their example supplies an explicit recursive training execution trace, while alternative training methods remain future work.

3 APPLICATION TO LEARNING RECURSIVE NEURAL PROGRAMS WITH NPI

The section adapts NPI to learn recursive programs by training it on traces that explicitly contain recursive calls. The resulting programs can achieve provably perfect generalization when all base cases and reductions are verified.

  • NPI architecture: The NPI combines a task-agnostic core, program-key embedding, and domain-specific encoders, while its LSTM controller selects returns, programs, and arguments from environment observations.Inference either calls a subprogram, writes to the environment for primitive functions, or terminates when return probability exceeds α = 0.5.
  • Recursive execution: Recursion is implemented by resetting the LSTM hidden state at each subprogram call, restricting computation to the currently relevant recursive context.The recursive traces are constructed for grade-school addition and bubble sort by adding recursive elements to existing program traces.
  • Recursive training traces: Explicitly recursive training traces enable NPI to learn recursive programs by adding recursive elements to execution traces.The approach changes supervision rather than requiring the model to discover recursive abstractions.
  • Results: NPI programs incorporating recursion achieve provably perfect generalization across different tasks when correct behavior is verified for all base cases and reductions.Provably perfect generalization means correct behavior on any valid input.
  • Verification and limitations: Verification sets can establish provably perfect generalization by checking that generated traces and results are correct, but exhaustive verification is infeasible for very large or infinite state spaces.The paper leaves more suitable verification procedures for such settings as future work.

4 EXPERIMENTS

Across four algorithmic tasks, recursive neural programs generalized more reliably than non-recursive programs, including from extremely small training sets. Recursive models also supported verification-based generalization claims that non-recursive models could not receive.

  • Generalization results: Recursive programs generalized strongly across all four tasks: addition up to 5000 digits, topological sort up to 120 vertices, and arbitrary arrays for bubble sort and quicksort.Non-recursive addition generalized to 5000 digits in these experiments, compared with 3000 digits previously reported; non-recursive quicksort correctness degraded at length 11 and beyond.
  • Grade-School Addition: With only five one-digit addition traces, the recursive model generalized perfectly to long sums, whereas the non-recursive model failed on those problems.The test example was 822+233, constructed from trained one-digit components.
  • Bubble Sort: On randomly generated arrays, the fully recursive bubble-sort program sorted every tested array, while partial recursion only slightly improved over non-recursion at length 3.Table 1 reports results for non-recursive, partially recursive, and fully recursive programs, with 30 random problems tested at each length.
  • Topological Sort: From a single five-node execution trace, the recursive topological-sort model solved all tested randomly generated DAGs across graph sizes.The models were evaluated on 30 randomly generated DAGs for each graph size.
  • Verification: Verification results show that recursive models can generalize from training step input-output pairs to unseen inputs in the verification set, unlike non-recursive models.The verification procedure tests learned traces and results against those of the true program, and cannot be performed for non-recursive versions because of hidden-state propagation in the core LSTM.

5 CONCLUSION

The paper’s main contribution is introducing neural recursive programs, showing that recursion enables provably perfect generalization and verification of neural-program behavior. The authors instantiate recursion in the Neural Programmer-Interpreter and identify broader recursive architectures and reduced supervision as future directions.

  • 5 CONCLUSION: The main contribution is introducing neural recursive programs, a concept not previously presented in the literature.The authors characterize this contribution as novel and central to the paper.
  • 5 CONCLUSION: Recursion enables provably perfect generalization and supports the first reported verification of a neural program’s behavior.The paper presents verification as providing provable guarantees about neural-program behavior.
  • 5 CONCLUSION: The authors instantiated recursion in the Neural Programmer-Interpreter by changing its training traces.
  • 5 CONCLUSION: Future work includes supporting more recursively structured tasks, reducing supervision, and integrating recursion directly into new Neural Programming Architectures.Proposed supervision reductions include training from partial or non-recursive traces.

A APPENDIX · A.1 PROGRAM SET FOR NON-RECURSIVE TOPOLOGICAL SORT · Argument Sets for WRITE and MOVE.

The non-recursive topological-sort program defines WRITE and MOVE operations through constrained argument sets. WRITE updates colors, active vertices, stack state, saved vertices, and results, while MOVE selects among five pointers and changes them upward or downward.

  • Argument Sets for WRITE and MOVE.: WRITE’s main action supports coloring, pointer-based activation, stack manipulation, saving the active vertex, and writing results.Its main-action arguments are COLOR CURR, COLOR NEXT, ACTIVE START, ACTIVE NEIGHB, ACTIVE STACK, SAVE, STACK PUSH, STACK POP, and RESULT.
  • Argument Sets for WRITE and MOVE.: COLOR CURR colors vactive, while COLOR NEXT colors Vertex DAG[vactive][childList[vactive]].Both are main-action WRITE arguments that apply colors to the current active vertex or its child.
  • Argument Sets for WRITE and MOVE.: ACTIVE START, ACTIVE NEIGHB, and ACTIVE STACK write pstart, the active child, or Qstack(pstack) to vactive.These WRITE actions determine the next active vertex from a start pointer, child list, or stack lookup.
  • Argument Sets for WRITE and MOVE.: SAVE, STACK PUSH, STACK POP, and RESULT respectively save vactive, push or clear the stack top, and write vactive to Qresult(presult).These actions manage saved state, stack state, and the output queue.
  • Argument Sets for WRITE and MOVE.: WRITE’s auxiliary variable selects either COLOR GREY or COLOR BLACK.These arguments color the given vertex grey or black, respectively.
  • Argument Sets for WRITE and MOVE.: MOVE’s pointer argument can be presult, pstack, pstart, childList[vactive], or childList[vsave].The operation takes the pointer identity itself rather than the value to which the pointer refers.
  • Argument Sets for WRITE and MOVE.: Because MOVE accepts only those five pointer identities, its first argument has five possible values.This restriction concerns pointer identity, not the pointed-to object.
  • Argument Sets for WRITE and MOVE.: MOVE’s second argument specifies whether the selected pointer is incremented or decremented through UP or DOWN.These are the two allowed increment-or-decrement arguments.

A.2 TRACE-GENERATING FUNCTIONS FOR TOPOLOGICAL SORT · A.2.1 NON-RECURSIVE TRACE-GENERATING FUNCTIONS

The non-recursive topological-sort trace generator uses a top-level loop to initiate traversals, explore vertices, and advance to subsequent starting positions. Its child-checking routine skips already explored children before exploration proceeds.

  • A.2 TRACE-GENERATING FUNCTIONS FOR TOPOLOGICAL SORT: The top-level TOPOSORT procedure repeatedly runs while the starting vertex has a valid color, indicating that unexplored vertices remain.Each iteration writes the active start and grey color before invoking traversal.
  • A.2 TRACE-GENERATING FUNCTIONS FOR TOPOLOGICAL SORT: Each top-level iteration writes ACTIVE_START and COLOR_CURR as COLOR_GREY, then calls TRAVERSE before moving upward and selecting the next start.
  • A.2.1 NON-RECURSIVE TRACE-GENERATING FUNCTIONS: TRAVERSE is decomposed into CHECK_CHILD followed by EXPLORE, defining the non-recursive traversal sequence.
  • A.2.1 NON-RECURSIVE TRACE-GENERATING FUNCTIONS: CHECK_CHILD repeatedly advances through childList[vactive] while the current child is neither white nor invalid.The procedure moves upward in the child list for each skipped child.
  • A.2.1 NON-RECURSIVE TRACE-GENERATING FUNCTIONS: The color-invalid condition denotes that all vertices have been explored, while child colors determine whether CHECK_CHILD continues scanning.
  • A.2 TRACE-GENERATING FUNCTIONS FOR TOPOLOGICAL SORT: After traversal, MOVE(pstart, UP) and NEXT_START() advance control toward the next topological-sort starting position.

A.2.2 RECURSIVE TRACE-GENERATING FUNCTIONS

The section presents altered recursive functions for trace generation, illustrated by a recursive topological-sort procedure. The procedure recurses at the top level and while checking children, using vertex colors to control exploration.

  • A.2.2 RECURSIVE TRACE-GENERATING FUNCTIONS: The altered functions use color validity to determine whether vertices or children remain available for exploration.The top-level call proceeds when the start vertex has a valid color, while child checking excludes white and invalid colors.
  • A.2.2 RECURSIVE TRACE-GENERATING FUNCTIONS: The recursive topological-sort routine makes a recursive top-level call after traversing and selecting the next start vertex.The call occurs after writing the active start and current color, traversing, moving upward, and invoking NEXT_START().
  • A.2.2 RECURSIVE TRACE-GENERATING FUNCTIONS: The child-checking routine recursively revisits itself after moving to an eligible child.A child is eligible when its color is neither white nor invalid; invalid denotes that all children have been explored.

A.3 NON-RECURSIVE QUICKSORT … A.6 BASE CASES, REDUCTION RULES, AND VERIFICATION SETS

The appendix develops iterative and recursive neural quicksort implementations, specifies their primitive operation spaces, and constructs verification sets covering relevant base cases and reduction rules. Verification results show that the recursive bubble-sort variant generalizes better than the non-recursive variant as array length increases.

  • A.3 NON-RECURSIVE QUICKSORT: Iterative quicksort partitions an array around a pivot and uses two stacks to store the lower and upper subarray bounds.The algorithm initializes the array and stacks, partitions the current interval, and stores the resulting subproblem ranges.
  • A.4 PROGRAM SET FOR QUICKSORT: The quicksort program set represents control flow through STACK, MOVE, SWAP, and WRITE operations with finite argument sets over pointers, stack objects, and pointer updates.STACK pushes or pops subarray bounds; MOVE changes selected pointers; SWAP exchanges pivot or array positions; WRITE copies stack or pointer-derived values.
  • A.5.1 NON-RECURSIVE TRACE-GENERATING FUNCTIONS: The non-recursive trace-generating functions implement quicksort by explicitly managing stack state, partitioning, and subproblem pushes.The trace includes STACK_POP, PARTITION, STACK_PUSH_CALL2, and STACK_PUSH_CALL1 operations.
  • A.5.2 RECURSIVE TRACE-GENERATING FUNCTIONS: The recursive trace-generating functions replace explicit continuation handling with recursive calls after partitioning and pushing both resulting subproblems.The recursive function performs two QUICKSORT recursive calls, with stack writes and pops surrounding those calls.
  • A.6 BASE CASES, REDUCTION RULES, AND VERIFICATION SETS: Verification sets are constructed to cover the base cases and reduction rules required by each task.Addition permits analytical construction, whereas other tasks use randomly generated candidates until the relevant cases and rules are covered.
  • A.6 BASE CASES, REDUCTION RULES, AND VERIFICATION SETS: For addition, the verification set contains 20,181 input problems under equal-length, no-leading-zero assumptions, with coverage organized around adjacent-column transitions and carry-related states.The construction separately handles null and non-null left columns and focuses especially on CARRY and LSHIFT operations.
  • A.6 BASE CASES, REDUCTION RULES, AND VERIFICATION SETS: The verified recursive bubble-sort program generalizes better than the non-recursive program, whose accuracy degrades sharply when arrays increase from length 7 to length 8.The non-recursive model was trained on two traces from length-7 arrays and one from length 6; the recursive model was verified.
  • A.6 BASE CASES, REDUCTION RULES, AND VERIFICATION SETS: Quicksort’s verification set covers all derived cases and rules with a single empirically selected 10-element array.The reported array is [8,2,1,2,0,8,5,8,3,7].
Loading 1704.06611v1…