- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies the relationship between persistent state, shared transformations, stepwise supervision, and gradient truncation in recursive reasoning models. It proposes an interpretation based on variational EM. Memory for each problem instance controls the latent prior. The E-step infers latent explanations from the input, target, and current memory. The instance-level M-step then updates memory while keeping the shared model parameters fixed, bringing the next prior closer to the current posterior. Based on this formulation, the authors introduce Variational Autoreasoners, which use a posterior network and a memory adapter for recursive computation. Training uses local variational objectives. The objective at the next step trains the preceding memory update, while gradients through earlier steps are truncated. The experiments evaluate depth scaling, solution coverage, memory updates, and training GPU memory use on graph coloring, N-Queens, complete Sudoku grid generation, and a Gaussian mixture toy task.
Critical strengths
-
Separating shared parameters, instance memory, and the current latent variable clarifies how one step affects later generation. Memory enters the model only through the prior, allowing the ideal memory update to be written as a KL projection that fits the next prior to the previous posterior. The paper also explains how the next objective trains the memory adapter and how gradient truncation limits long-term credit assignment.
-
The paper increases test depth while keeping the trained parameters fixed, separating the effect of additional computation from that of additional training. On NQ10, Table 9 shows that both single-answer accuracy and solution coverage over 20 independent draws improve when the same checkpoints are run beyond the training depth. These results support the benefit of additional iterations in the learned loop.
-
Both removing memory updates and replacing the sampled latent input to the memory updater with a learned constant token substantially reduce success on GC8. These ablations support the usefulness of memory updates that depend on the sampled latent content. Table 10 also shows that, with the backbone, hardware, and batch size fixed, VAR’s peak GPU memory use remains at about 2.88 GiB across the tested training horizons. Memory use increases with the horizon in its full-BPTT controls, which do not use gradient checkpointing.
Critical weaknesses
-
The paper describes GRAM’s objective as a truncated surrogate of a trajectory ELBO and VAR’s objective as a complete local ELBO. However, GRAM also uses a posterior conditioned on the target during training, prior sampling at test time, a recurrent state, and gradient truncation. Conditional on the current deterministic state, GRAM’s Equation (14) can also be interpreted as a local ELBO for a single-step model. The distinction between these descriptions does not by itself establish the algorithmic contribution. A clearer comparison of the actual objectives, state updates, and gradient paths is needed.
-
The ideal M-step holds the previous posterior fixed and updates memory to fit it. In the method, the adapter receives a single sample, the posterior is recomputed under the new memory, and the next objective trains the adapter. This objective does not directly require the new prior to match the previous posterior. It acknowledges this difference and relates the next objective to the target likelihood under exact inference. However, the paper provides limited direct evidence that the learned updates approximate the ideal M-step or follow the power reweighting process. Whether this EM interpretation explains the observed gains from greater depth therefore remains unclear.
-
The Sudoku task is to generate a complete grid from a blank input, as stated in Appendix E.1. Repeatedly outputting one valid training grid would achieve 100% validity. Near-perfect validity therefore does not by itself show that the model generates diverse solutions or unseen grids. For Sudoku, the paper does not report duplicate rates, the number of unique valid grids, overlap with the training set, or diversity after accounting for grid symmetries. These missing measurements limit what can be concluded about the diversity and generalization of the generated solutions.
Questions for authors
-
What is the specific algorithmic contribution beyond GRAM? With one stochastic transition per supervision interval and the same supervision frequency, how do the objectives, state updates, and gradient paths differ? Could you compare the two methods using the same backbone and optimization settings and evaluate the contribution of each difference separately?
-
How closely do the learned memory updates approximate the ideal instance-level M-step? In a controlled setting where the exact posterior and ideal memory update can be computed, could you compare the learned updates with the ideal ones and examine how the differences relate to the gains from increasing test depth?
-
For Sudoku, could you report the number of distinct valid grids and the fraction of valid outputs that appear in the training set, using the same number of samples at each execution depth? As depth increases, do the valid outputs remain diverse, or do they become concentrated on a small set of solutions?
5 comments
[W2, Q2] How closely the learned memory updates, which do not fit the new prior to the previous posterior, approximate the ideal M-step, and how this relates to the gains from greater depth
The ideal M-step and VAR's learned update are derived separately from the same root objective, the ELBO (line 114), rather than VAR's update being derived from the ideal M-step. Section 2 adds idealized assumptions to this objective, namely exact, target-conditioned inference and explicit memory optimization. Here, "idealized" means restrictive and impractical, not a standard that VAR's update should follow. These assumptions only make the role of each step analyzable through EM, as the paper states at the start of Section 3 ("…to specify the roles of the two steps, not to prescribe an update algorithm"). Under these assumptions, the ideal M-step fits the new prior to the previous posterior (line 126), but it needs the target and cannot run at test time (lines 180–181). Section 3 therefore does not implement the ideal M-step. It returns to the root objective without these assumptions and amortizes both steps, so that the memory can be built from prior samples without the target (line 182). Removing these assumptions provides no explicit guarantee but makes the algorithm usable in practice.
Amortizing these explicit optimizations of the memory and the posterior follows common practice. A VAE replaces per-instance posterior optimization with an amortized encoder, and trains the encoder and decoder jointly through the ELBO instead of alternating exact E- and M-steps. Iterative amortized inference (Marino et al., 2018) trains a network that outputs the updated posterior so that the resulting ELBO increases. Like VAEs and iterative amortized inference, VAR does not hold the posterior fixed and trains the adapter to directly raise the ELBO recomputed at the updated memory (line 210). The ideal M-step fits the new prior to the previous posterior only because it holds the posterior fixed (line 126).
We applied each update once from the same initial memory in the Gaussian toy of Figure 3, which is already the controlled setting the reviewer describes: the exact posterior and the ideal memory update can be computed. The two updates raise the evidence almost equally (+3.15 vs. +3.19 nats), although the KL between the new prior and the previous posterior differs (0 vs. 23.1 nats). The learned update thus raises the objective by almost as much as the ideal M-step without fitting the prior to the previous posterior.
The gains from greater depth have no ideal counterpart, because the ideal M-step needs the target at every step and cannot run at test time; this is one motivation for amortizing the update. The adapter instead learns a rule that raises the ELBO from the incoming memory , so in the same toy the mode-region mass keeps rising beyond the 7 updates used in training, from 47.0% after 7 updates to 61.1% after 15 (Figure 3). We will add this controlled comparison to the revision.
[W3, Q3] Whether high Sudoku validity reflects diverse, novel grids rather than reproduced training data, and whether diversity holds as depth increases
VAR generates distinct valid Sudoku grids, even up to Sudoku symmetries, with no training-set overlap or diversity collapse as depth increases. At the same sample count, distinct valid grids increase from 5,377.3 (K=8) to 39,851 (K=32), with zero duplicates.
We evaluated the 40,000-board banks from Appendix E.4 (blank input, three seeds, the same VAR checkpoints trained with N=8 steps and executed for K steps) against 50,000 training grids.
| Execution depth K | Valid (of 40,000) | Distinct valid | In training set |
|---|---|---|---|
| 8 | 5,377.3 | 5,377.3 | 0 |
| 16 | 36,460 | 36,460 | 0 |
| 32 | 39,851 | 39,851 | 0 |
Results are averaged over seeds; every seed individually shows zero duplicates and zero training-set overlap. Thus, the fraction of distinct grids among valid outputs remains 100% at every depth, indicating no observed concentration onto repeated solutions, while the absolute number of distinct valid grids increases with validity.
Symmetry-aware diversity. The results remain unchanged when accounting for all Sudoku symmetries (digit relabeling, row/column permutations within bands/stacks, band/stack permutations, and transposition; approximately 1.2 × 10¹² transformations). No two valid outputs are equivalent, and none is equivalent to a training grid.
Why the samples are novel. Learning the training distribution does not mean reproducing training grids. A 9×9 Sudoku has about 6.7 × 10²¹ valid grids, so a model that samples from this distribution would match one of the 50,000 training grids with expected count ~10⁻¹³ among 40,000 outputs (~0.4 even modulo symmetry). Zero overlap is therefore what distribution learning predicts, whereas memorization would produce repeated training grids.
We will include this analysis in Appendix E.
Thanks for the authors' detailed response.
I agree that the mode-region mass keeps rising beyond the training depth, and that "The gains from greater depth have no ideal counterpart". My remaining concern is how much this result explains about why the extra steps help.
We thank the reviewer for the constructive feedback and thoughtful questions. We address each concern below, including the comparison with GRAM, the relationship to the idealized M-step, and Sudoku diversity.
[W1, Q1] Algorithmic contribution beyond GRAM when GRAM's Eq. 14 can also be read as a local ELBO
Our main contribution is to explain recursive reasoning as variational EM, a view that GRAM does not provide. Under this view, each recursion step can be read as one step of instance-level EM that updates the prior for the next step, which explains how recursion turns additional steps into better predictions. Prior recursive reasoning models, including GRAM, show that this recursion is effective but leave open why it works (lines 33–37).
This view also resolves a critical mismatch in GRAM between its objective and its per-step parameter updates. Like HRM and TRM, GRAM updates its parameters at every recursion step. Its objective, however, is a single ELBO over the whole trajectory, which assumes no update until the trajectory ends, so GRAM treats its per-step updates as a biased approximation. In our framework, each step has its own complete objective, the local ELBO, so per-step updates follow directly from the objective. This explains why Eq. 14, which the reviewer reads as a local ELBO, is a valid objective for per-step updates. GRAM's trajectory ELBO does not account for this.
GRAM's architecture can be seen as one implementation of our framework. In our framework, the parameters at each step are trained with the local ELBO of the model p(y∣x,ht) conditioned on the memory ht, which is a complete objective at that step (Algorithm 1). GRAM implements this core with additional structures, such as the H/L hierarchy, the inner low-level recursion, and ACT (adaptive computational time). Because the framework does not require these structures, VAR implements only the core.
We compared the two methods under the reviewer's condition: one stochastic transition per supervision interval and the same supervision frequency. To do so, we reduced GRAM's H cycle to 1 and set the maximum number of supervision intervals to 8, the value used by VAR. On N-Queens (table below, %), the simpler VAR performs comparably to GRAM (H=1) on NQ8 and better on NQ10. In the revision, we will explicitly describe how the EM framework explains the per-step parameter updates that the trajectory ELBO does not.