acceptodds
Under review as a conference paper at ICLR 2027

Prophecy Transformer

Abstract

Autoregressive transformers trained on next-token prediction suffer from a key weakness; early decisions can restrict the model to suboptimal continuations. Furthermore, they do not learn a meta-model of how their mistakes correlate with ground truth, nor how to recover. These issues are critical in the context of reasoning, where such approaches often become trapped in irreconcilable dead-ends without a way to update their predictions based on these failures. To address this, we introduce Prophecy Transformer, an architecture which conditions its generations on a nonparametric latent variable encoding the model's internal activations produced during an initial rollout following its own policy. By attending to this latent variable from the start of generation, our model gets a view into its possible future internal state which reveals information that would only become apparent after committing to certain decisions. Tested on algorithmic reasoning tasks such as 3-SAT, graph coloring, TSP, and countdown, our method significantly outperforms autoregressive models due to its prospective and self-corrective capabilities. Across tasks, Prophecy Transformer acquires self-referential representations encoding the quality of its predictions and the ability to update the model's decisions based on its predicted future state, unlocking large gains in reasoning ability.

Primary area:
foundation or frontier models, including LLMs
Keywords:
transformers, latent variable models, reasoning, latent reasoning, constraint satisfaction, combinatorial optimization

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_tCRFOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors introduce a new architecture, the prophecy transformer, that uses latent activity from the whole transformer rollout to generate latent variables through non-parametric means that can then inform the next iteration of the prophecy transformer. This, in principle, can be done an infinite number of times. They then show that the architecture beats simple autoregressive and other baselines on mostly NP complete tasks. Finally, they provide an analysis of the latent variable generated by the prophecy transformer to show that it is indeed doing something useful.

Critical strengths
  • novel architecture
  • interesting idea with decent motivations
  • well written paper
  • clear improvements over compared baselines
Critical weaknesses
  • potentially weak baselines:
    • I would need to see a figure that shows performance against flops to be convinced by the approach. CoT can solve the motivating problems of short-sightedness by increasing the length of the rollout. Recursive transformers can solve the issue by more recursive iterations.
    • what is the scale and base model architecture for the baselines?
    • are parameter counts held equal for the prophecy transformer and the baselines?
  • methods could have expanded a bit more on the derichlet process (DP). I am not very familiar with such DPs and the paper's description wasn't detailed enough for me to implement the idea.

What would change my mind: if the authors provide a figure that shows performance against flops across model scales and rollout lengths, and the results are still strong, I will raise my score.

Questions for authors
  • How does this improve upon recursive transformers?
  • what is the scale and base model architecture for the baselines?
  • are parameter counts held equal for the prophecy transformer and the baselines?
2 comments

Thank you for writing this detailed review, and for the helpful feedback. We hope the following responses clarify your concerns.

what is the scale and base model architecture for the baselines?

Excluding vocabulary dependent embedding matrices which are identical between the two architectures, the exact parameter counts for PT and baseline are 142,762,753 and 141,580,032 respectively. This has been made more explicit in the updated paper.

Both PT and the baseline models share the same Qwen3 [1] transformer architecture backbone, whose details are described in Appendix A.4. The number of layers, hidden dim., attention heads, and MLP intermediate size are identical between PT and baselines. The only difference is that PT possesses exactly three additional projection matrices for the whole model to infer the parameters of the Dirichlet Process posterior.

[1] Yang, An, et al. "Qwen3 technical report." arXiv preprint arXiv:2505.09388 (2025).

are parameter counts held equal for the prophecy transformer and the baselines?

The difference in parameter count is within 0.8% of the baseline parameter count, with the only addition in PT being in the three projection matrices used to infer the posterior Dirichlet Process.

I would need to see a figure that shows performance against flops to be convinced by the approach. CoT can solve the motivating problems of short-sightedness by increasing the length of the rollout. Recursive transformers can solve the issue by more recursive iterations.

Thank you for raising this point. We have run additional experiments scaling inference time compute on all of our search baselines, and have plotted their performance at three inference-time FLOP budgets for 3-SAT, graph coloring, TSP, and countdown. Our results/figures are presented in the updated version of our paper uploaded to openreview, in §5.3 ‘Scaling inference-time compute for search baselines.’ Modifications to the paper are colored blue for clarity.

In order to achieve the reported inference compute budgets, we scaled:

  • Beam width [4~96] for ToT/Beam search
  • Simulation counts [4~96] for MCTS
  • Number of rollouts [4~512] and rollout length [4~16] for Predictive Decoding

Models evaluated use the base model scale of 140M parameters trained on 500k unique examples for 25k steps. Details on the search baseline hyperparameters used in this analysis are presented in Appendix. A5.

Our results in Fig. 5 show that Prophecy Transformer continues to significantly outperform every search baseline across all tasks at every compute budget, including those utilizing more inference time compute.

Furthermore, in order to demonstrate that PT retains its advantage at larger model scales and at a larger number of unique training examples, we trained larger PT and baselines at 340M parameters and 1M unique training examples. We similarly plot their performance against FLOPs on all tasks (Fig. 5), and show that PT outperforms all of the search baselines we tested at all inference-time compute budgets on all tasks at this larger scale.

We note that because expended FLOPs for MCTS and Predictive Decoding depend on KV cache hits/misses when sampling rollouts, it is possible for the base scale models to expend more FLOPs than the large scale models.

How does this improve upon recursive transformers?

We ran an experiment testing TRM (Tiny Recursive Model) [2] on 3-SAT, trained with the same data used in the base experiments (500k unique examples, 25k steps). Matching inference compute to PT at 128 GFLOPs/problem, TRM scored 2.72% on the 3-SAT test set (95% confidence interval [2.42%, 3.06%]). This is significantly worse than PT’s score of 96.5%.

We note that because TRM applies 336 forward passes per problem by default, the inference compute matched TRM has orders of magnitude fewer parameters than PT (0.62M vs 140M).

[2] Jolicoeur-Martineau, Alexia. "Less is more: Recursive reasoning with tiny networks." arXiv preprint arXiv:2510.04871 (2025).

methods could have expanded a bit more on the derichlet process (DP). I am not very familiar with such DPs and the paper's description wasn't detailed enough for me to implement the idea.

Thank you for this feedback. We have added more detailed exposition regarding Dirichlet Processes and further references for clarity. Modifications to the paper are colored blue.

Dear reviewer tCRF,

Since the discussion period is coming to an end, we would appreciate an acknowledgement of our rebuttal, and thanks for your time.

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

This paper introduces Prophecy Transformer, a two-pass architecture that uses internal representations from an initial generation to guide the final output. Hidden states from the first pass are encoded through a Dirichlet-process-based nonparametric variational information bottleneck and accessed through cross-attention in the second pass. The model is trained with next-token prediction and variational regularization, without annotated correction trajectories.

The evaluation covers four synthetic algorithmic tasks: 3-SAT, graph coloring, sparse TSP, and Countdown. The paper reports gains over an autoregressive baseline and several search-based decoding methods. Further analyses examine corrections and regressions between passes, whether the learned representations predict solution correctness, and ablations using direct attention and a separate decoder on 3-SAT.

Critical strengths

1. An innovative approach to learning self-corrective generation

Encoding a model’s own rollout states into a nonparametric latent variable and using it to guide a subsequent attempt is an interesting architectural contribution. The combination of parameter sharing and a variational information bottleneck distinguishes the method from conventional two-pass generation and provides a way to use internal information from earlier attempts. This is a promising direction for learning corrective behavior without explicitly annotated correction trajectories.

2. Substantial gains on controlled tasks, supported by behavioral analysis

The reported gains are substantial, particularly on 3-SAT, where the exact solve rate increases from 57.5% for the autoregressive baseline to 96.5%. The correction–regression analysis shows that the second pass yields a net improvement over the model’s own first-pass predictions on all four tasks. The direct-attention ablation also shows that access to first-pass hidden states alone is insufficient to reproduce the full method’s performance.

Critical weaknesses

1. The advantage over scaling conventional autoregressive training remains unestablished

All main experiments use a single model configuration, 500,000 training examples per task, and 25,000 training steps. This controls the training data volume and update count, but does not show whether PT retains its advantage when the baseline receives more unique examples, longer training, or greater model capacity. Without data- or compute-scaling curves, the paper demonstrates a gain at one operating point rather than a clear advantage over conventional scaling.

2. The trade-off between computational cost and performance is not sufficiently characterized

PT requires an initial rollout and additional processing of its hidden states, so matching training steps does not match training compute. Inference comparisons report accuracy without corresponding latency, FLOPs, or memory costs. The search baselines may also consume substantial compute, but their configurations and resource use are not documented well enough to establish PT’s relative efficiency. This limits the practical interpretation of the reported gains.

3. The evaluation has limited coverage of reasoning difficulty and distributional generalization

The benchmarks use small, fixed-size instances: 12-variable SAT, 16-vertex graph coloring and TSP, and four-number Countdown. Graph coloring and TSP also use constrained generators with planted structure. These are useful controlled tasks, but the difficulty of the general problem families does not establish the representativeness of these specific distributions. Apart from held-out Countdown targets, the paper provides little evidence of generalization to larger instances, longer solutions, or different generation distributions.

4. The ablations do not fully isolate the contributions of individual architectural choices

The direct-attention and separate-decoder comparisons are limited to 3-SAT. Removing the entire variational mechanism does not distinguish the benefits of nonparametric modeling from those of simpler compression, stochastic regularization, or a parametric bottleneck. The separate-decoder baseline freezes the first decoder and uses raw hidden states, changing both the training setup and the latent representation relative to PT. Its performance therefore does not isolate the benefit of parameter sharing.

Questions for authors

1. Scaling and resource matching

What are the actual training and inference costs of PT and the strongest baselines, including the initial rollout, hidden-state processing, and search? Can you run a small sweep over data size or training compute, with matched-budget comparisons, to test whether PT retains its advantage as conventional autoregressive training scales?

2. Generalization

Does PT retain its advantage on larger instances or under changes to the benchmark generators, such as different SAT clause densities, graphs without the balanced-coloring constraint, or denser TSP instances? These tests would help establish whether the model learns a transferable corrective mechanism rather than improvements specific to the evaluated distributions.

3. Architectural attribution

Can you compare the nonparametric bottleneck with a simpler regularized or parametric alternative on more than one task? To isolate the effect of parameter sharing, can the separate-decoder comparison retain the same bottleneck and allow both decoders to train? These controls would clarify which architectural components are necessary for the observed gains.

2 comments

Thank you for the detailed review.

The trade-off between computational cost and performance is not sufficiently characterized

In order to better contextualize our method regarding evaluation compute, we have run additional experiments measuring performance of all search baselines on all tasks at three inference-time FLOP budgets.

Our results/figures are presented in the updated version of our paper uploaded to openreview, in §5.3 ‘Scaling inference-time compute for search baselines.’ Modifications to the paper are colored blue for clarity.

In order to realize the reported inference compute levels, we scaled:

  • Beam width [4~96] for ToT/Beam search
  • Simulation counts [4~96] for MCTS
  • Rollouts [4~512] and rollout horizon [4~16] for Predictive Decoding

Models evaluated use the base model scale of 140M parameters trained on 500k unique examples for 25k steps. Details on the search baseline hyperparameters used in this analysis are presented in Appendix. A5.

Our results in Fig. 5 show that Prophecy Transformer continues to significantly outperform every search baseline across all tasks at every compute budget, including those utilizing more inference time compute.

The advantage over scaling conventional autoregressive training remains unestablished

In order to demonstrate that PT retains its advantage at larger model scales and at a larger number of unique training examples, we trained larger PT and baselines at 340M parameters and 1M unique training examples. We similarly plot their performance against FLOPs on all tasks (Fig. 5), and show that PT outperforms all of the search baselines we tested at all inference-time compute budgets at this larger scale.

The evaluation has limited coverage of reasoning difficulty and distributional generalization

Does PT retain its advantage on larger instances or under changes to the benchmark generators, such as different SAT clause densities, graphs without the balanced-coloring constraint, or denser TSP instances? These tests would help establish whether the model learns a transferable corrective mechanism rather than improvements specific to the evaluated distributions.

Our experiments are designed to demonstrate the advantages of attending to a latent variable encoding information about the model’s future internal states when solving algorithmic reasoning tasks. Therefore, we believe that measuring generalization on the task attributes raised such as SAT clause density, graph balance, and TSP graph density are outside the scope of this paper, since we are not making a specific claim about OOD generalization.

We also note that, as stated in the paper, the SAT clause densities in our experiments are chosen according to the cross-over point formula [1] and are thus calibrated to be challenging.

[1] Crawford, James M., and Larry D. Auton. “Experimental Results on the Crossover Point in Random 3-SAT.” Artificial Intelligence, vol. 81, no. 1, 1996, pp. 31–57, https://doi.org/10.1016/0004-3702(95)00046-1.

The ablations do not fully isolate the contributions of individual architectural choices

Can you compare the nonparametric bottleneck with a simpler regularized or parametric alternative on more than one task? To isolate the effect of parameter sharing, can the separate-decoder comparison retain the same bottleneck and allow both decoders to train? These controls would clarify which architectural components are necessary for the observed gains.

Thank you for raising this point. We have implemented both of the requested baselines:

  • A parametric latent variable baseline, where instead of sampling from a DP posterior, we project the last hidden state before the prophecy layer into the parameters of a Gaussian distribution and sample a fixed-size embedding as the prophecy variable, and allow bi-directional attention to this embedding.
  • A 'separate decoder with DP posterior' baseline, where both decoders are allowed to train jointly.

We evaluated both baselines on 3-SAT and TSP after training on the same data as our base experiments (500k unique examples, 25k steps). Our results are presented below, demonstrating that PT significantly outperforms both the parametric baseline as well as the separate decoder baseline with DP posterior. These results indicate that our nonparametric latent variable treatment is necessary to achieve the observed gains, and that these results also depend on PT’s parameter sharing approach.

TaskPT (Ours) accuracyParametric baseline accuracySeparate decoder with DP posterior accuracy
3-SAT96.51%74.97%79.71%
TSP76.36%68.60%73.01%

Thank you for the thorough rebuttal and supplementary experiments. I appreciate the authors’ responses to several of my concerns and the additional results that strengthen the paper’s persuasiveness. That said, my overall view is still that the paper is not yet fully acceptable, so I will maintain my original rating.

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

This paper introduces the Prophecy Transformer - essentially an autoregressive transformer with architectural level inference scale. That is achieved by encoding earlier trajectories and supplying them to the subsequent iterations. The authors show advantages of the architecture for solving a several symbolic tasks.

Critical strengths
  1. The architecture makes use of variational latents between the different 'rollouts'.
  2. The reuse of previous solution experience is a topic of active research and beating SAT methods at SAT problems is hard.
Critical weaknesses
  1. While the authors train an AR baseline and report improvements, some things are not evident, specifically - is the evaluation compute matched? Also I could not find the details for the parameter counts used.
  2. The authors have not compared to several relevant methods: e.g. the variants of TRM and RRMs (Recurrent Reasoning Models) that could be employed for this tasks.
  3. While the LLM-neurosymbolic approaches are beyond the scope of the paper, would be nice if they discussed those in related work.
Questions for authors
  1. Can you provide compute matched comparison of the prophecy transformer vs pure AR?
  2. Could a multiturn AR model leverage the `reuse' effect?
1 comment

First of all, thank you for the helpful review. We hope our response clarifies your concerns.

Also I could not find the details for the parameter counts used.

Excluding vocabulary dependent embedding matrices which are identical between the two architectures, the exact parameter counts for PT and baseline are 142,762,753 and 141,580,032 respectively. This has been made more explicit in the updated paper.

Both PT and the base model share the same Qwen3 [1] transformer architecture backbone, whose details are described in Appendix A.4. The number of layers, hidden dim., attention heads, and MLP intermediate size are identical between PT and baselines. The only difference is that PT possesses exactly three additional projection matrices for the whole model to infer the parameters of the Dirichlet Process posterior.

[1] Yang, An, et al. "Qwen3 technical report." arXiv preprint arXiv:2505.09388 (2025).

While the authors train an AR baseline and report improvements, some things are not evident, specifically - is the evaluation compute matched?

In order to better contextualize our method regarding evaluation compute, we have run additional experiments measuring performance for all search baselines on all tasks at three inference-time FLOP budgets. We also measure and report inference-time FLOPs for PT and the pure AR baseline.

Our results/figures are presented in the updated version of our paper uploaded to openreview, in §5.3 ‘Scaling inference-time compute for search baselines.’ Modifications to the paper are colored blue for clarity.

In order to achieve the reported inference compute levels, we scaled:

  • Beam width [4~96] for ToT/Beam search
  • Simulation counts [4~96] for MCTS
  • Rollouts [4~512] and rollout horizon [4~16] for Predictive Decoding

Models evaluated use the base model scale of 140M parameters trained on 500k unique examples for 25k steps. Details on the search baseline hyperparameters used in this analysis are presented in Appendix. A5.

Our results in Fig. 5 show that Prophecy Transformer continues to significantly outperform every search baseline across all tasks at every compute budget, including those utilizing more inference time compute.

Furthermore, in order to demonstrate that PT retains its advantage at larger model scales and at a larger number of unique training examples, we trained larger PT and baselines at 340M parameters and 1M unique training examples. We similarly plot their performance against FLOPs on all tasks (Fig. 5), and show that PT outperforms all of the search baselines we tested at all inference-time compute budgets at this larger scale.

The authors have not compared to several relevant methods: e.g. the variants of TRM and RRMs (Recurrent Reasoning Models) that could be employed for this tasks.

We ran an experiment testing TRM (Tiny Recursive Model) [2] on 3-SAT, trained with the same data used in the base experiments (500k unique examples, 25k steps). Matching inference compute to PT at 128 GFLOPs/problem, TRM scored 2.72% on the 3-SAT test set (95% confidence interval [2.42%, 3.06%]). This is significantly worse than PT’s score of 96.5%.

We note that because TRM applies 336 forward passes per problem by default, the inference compute matched TRM has orders of magnitude fewer parameters than PT (0.62M vs 140M).

[2] Jolicoeur-Martineau, Alexia. "Less is more: Recursive reasoning with tiny networks." arXiv preprint arXiv:2510.04871 (2025).

While the LLM-neurosymbolic approaches are beyond the scope of the paper, would be nice if they discussed those in related work.

Thank you for the suggestion. If the reviewer could suggest work relevant to our paper, we would be happy to cite them in the updated draft.

Could a multiturn AR model leverage the `reuse' effect?

Thank you for this suggestion. We found this to be an interesting idea and implemented a ‘Repetition AR’ baseline, which is trained on sequences where the solution span is repeated twice. This allows the Repetition AR baseline to utilize additional compute (worth one extra rollout, similar to PT) and attend to its previous generation when predicting its final answer. Our experiment is performed at the base 140M scale on the same 500k unique examples over 25k steps.

We present the results of this experiment below. We find that PT continues to outperform this baseline across all tasks. Interestingly, the Repetition AR baseline significantly improves in 3-SAT and graph coloring compared to the standard AR baseline, but degrades in performance for TSP and countdown.

TaskPT (Ours) accuracyRepetition AR accuracyStandard AR accuracy
3-SAT96.51%93.73%57.54%
Graph coloring69.45%61.06%53.24%
TSP76.36%57.77%58.91%
Countdown47.42%39.05%41.76%

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.