Posted on Nov 8, 2025 by Xingyu Dang
Reinforcement Learning with Verifiable Rewards (RLVR) has driven many recent successes in reasoning models—from mathematical problem solving to code synthesis. In this blog, we’ll connect RLVR to the modeling of Time-Traveling Turing Machines (TTTMs). We’ll see that a “one-bit signal from the future” leads, mathematically, to the same equations that govern KL-regularized RLVR.
In short: RLVR is time-traveling.
The idea of a “time-traveling computer” originates in theoretical computer science. Suppose a Turing machine can send a single bit of information to its own past. How much more powerful would it become?
Imagine a machine that asks itself: “Did I output the correct answer?” If a bit from the future flips to 1 when the answer is correct, the machine can search for a self-consistent computation—one that will produce the same bit it already received.
That’s the core idea behind time-traveling computation: the system must reach a self-consistent fixed point between present and future.
Deutsch Closed Timelike Curves (CTC).
Introduced by David Deutsch in 1991, this model enforces that the distribution of messages sent into the past equals the distribution received—like a steady-state of time loops. Aaronson and Watrous (2009) famously showed that access to such CTCs boosts both classical and quantum computers to PSPACE power.
Postselection (PostBQP / PostBPP).
Instead of requiring fixed points, this weaker model allows conditioning on rare events that “would have happened.” For example, Aaronson (2005) showed that a quantum computer that can postselect on measurement outcomes has power PP-wiedly believed to be beyond BQP but below PSPACE.
Intuitively, CTCs represent hard self-consistency (nature must find a fixed point), while postselection represents soft conditioning ("imagine we are only in the universe where X happened").
Now, let's apply this idea to language models.
A time-travel bit (TTB) is a noisy one-bit message sent from the future back to the present during sequence generation. In general, this bit could encode any function of the final output \(y_{1:T}\)—it could signal success, failure, quality scores, or any binary property.
Consider a base autoregressive language model \(\pi_0(y_{1:T}\mid x)=\prod_t \pi_0(y_t\mid h_{t-1})\). Suppose we have a task with a binary global verifier \(V(y_{1:T})\in\{0,1\}\) that checks whether the generated sequence is correct (e.g., a math problem solution passes unit tests, a code snippet compiles correctly).
Key insight: For such tasks, the optimal TTB is precisely the verifier outcome. Since the verifier \(V(y_{1:T})\) is a deterministic function of the sequence, let \(b\in\{0,1\}\) be any (possibly randomized) 1-bit summary generated from \(y_{1:T}\) via a channel \(P(b\mid y_{1:T})\). The goal is to maximize the mutual information between this bit and the verifier, \[ I(b;V) \;=\; \sum_{b,v} P(b,v)\log\frac{P(b,v)}{P(b)P(v)}\,, \] which measures how much information the bit carries about whether the output passes verification.
The induced conditional \[ P(b\mid V=v)=\mathbb{E}_{y_{1:T}\mid V=v}\!\big[P(b\mid y_{1:T})\big],\quad v\in\{0,1\}, \] implies that the joint law of \((b,V)\)—and hence \(I(b;V)\)—depends only on \(P(b\mid V)\). Thus, without loss of optimality we may take \(b\) to depend on \(y_{1:T}\) only through \(V\). With a single-bit budget we have \(I(b;V)\le H(V)\le 1\), and the upper bound is achieved precisely when \(b\) is a bijection (or a noisy copy) of \(V\).
Formally, with a symmetric noise channel (BSC\((\varepsilon)\)) applied to this one-bit copy of the verifier, after the model finishes generating \(y_{1:T}\) a bit \(b\) is produced: \[ b\sim \begin{cases} \mathrm{Ber}(1-\varepsilon), & V(y_{1:T})=1,\\ \mathrm{Ber}(\varepsilon), & V(y_{1:T})=0, \end{cases} \] where \(\varepsilon\in(0,\tfrac12)\) is the noise level. Define the inverse temperature \[ \beta = \log\frac{1-\varepsilon}{\varepsilon}. \] Larger \(\beta\) (smaller \(\varepsilon\)) means a more reliable signal from the future. Conditioning on \(b=1\) then enforces retrocausal consistency between the generated sequence and a successful verification.
We call the resulting system a Time-Traveling Language Model (TTLM). Two versions mirror the CTC vs. postselection divide:
We'll focus on the postselected picture in this blog .
Conditioning on \(b=1\) modifies the model's sequence distribution as follows: \[ q_\beta(y_{1:T}\mid x) = \frac{\pi_0(y_{1:T}\mid x)\,e^{\beta V(y_{1:T})}}{Z_\beta(x)}, \quad Z_\beta(x)=\mathbb{E}_{\pi_0}[e^{\beta V}\mid x]=(1-p)+e^{\beta}p, \] where \(p=\Pr_{\pi_0}(V=1\mid x)\).
By Bayes' theorem, \(q_\beta(y_{1:T}\mid x)=\Pr(y_{1:T}\mid b=1, x)\) equals: \[ \frac{\Pr(b=1\mid y_{1:T})\,\pi_0(y_{1:T}\mid x)}{\Pr(b=1\mid x)}. \] From the TTB channel, \(\Pr(b=1\mid y_{1:T}) = \varepsilon \cdot e^{\beta V(y_{1:T})}\) where \(\beta = \log\frac{1-\varepsilon}{\varepsilon}\). By the law of total probability: \[ \Pr(b=1\mid x) = \varepsilon \mathbb{E}_{\pi_0}[e^{\beta V}\mid x] = \varepsilon\big[(1-p) + e^{\beta}p\big] = \varepsilon Z_\beta(x), \] where \(p=\Pr_{\pi_0}(V=1\mid x)\). Substituting yields: \[ q_\beta(y_{1:T}\mid x) = \frac{\pi_0(y_{1:T}\mid x)\,e^{\beta V(y_{1:T})}}{Z_\beta(x)}. \qquad \square \]
As \(\varepsilon\to0\) (\(\beta\to\infty\)), \(q_\beta\) collapses onto the successful set \(\{V=1\}\): perfect postselection.
Let’s step back to RLVR—Reinforcement Learning with Verifiable Rewards.
We start from the same ingredients: - base policy \(\pi_0\), - verifier \(V(y)\in\{0,1\}\), - and a KL-regularized objective \[ J_\beta(\pi) = \mathbb{E}_\pi[\beta V(y)] - \mathrm{KL}(\pi\|\pi_0). \]
This formulation appears in linearly-solvable MDPs (Todorov, 2007) and “control as inference” (Levine, 2018).
Its optimal solution is exactly[2]:
\[
\pi^*(y)\propto \pi_0(y)e^{\beta V(y)}.
\]
That is identical to the TTLM postselected distribution \(q_\beta\).
Hence, KL-regularized RLVR is mathematically the same as time-traveling.
The key correspondences reveal why RLVR is time-traveling:
| Time-Travel View | RLVR View |
|---|---|
| Postselection on \(b=1\) | KL-regularized RL |
| Conditional distribution \(q_\beta(y) \propto \pi_0(y)e^{\beta V(y)}\) | Optimal policy \(\pi^*(y) \propto \pi_0(y)e^{\beta V(y)}\) |
| Retrocausal consistency (future \(\to\) past) | Credit assignment (reward \(\to\) action) |
| Prefix success probability \(p_{\text{succ}}(h)\) | Value function / Q-function |
The first two rows establish the equivalence: postselection and optimal policy have identical mathematical forms. The agent adjusts its present behavior to remain compatible with a favorable future.
The one-bit from the future conveys at most one bit of information, yet that small hint can exponentially reduce the expected samples needed to reach success:
\[
p_\beta = \frac{e^{\beta}p}{(1-p)+e^{\beta}p},
\]
so rare events with probability \(p\) become \(e^{\beta}\) times more likely.
The total information gain is bounded by \(1\) bit,
but the search efficiency gain can be enormous.
That’s the paradoxical power of time travel: not adding information, just re-weighting futures.
The exponential tilt also yields a clean autoregressive update rule: \[ q_\beta(y_t\mid h_{t-1}) = \pi_0(y_t\mid h_{t-1}) \frac{Z(h_t)}{Z(h_{t-1})}, \qquad Z(h)=1+(e^{\beta}-1)p_{\text{succ}}(h), \] where \(p_{\text{succ}}(h)=\Pr_{\pi_0}(V=1\mid h)\) is the prefix-success probability.
Taking logs: \[ \log q_\beta(y_t\mid h_{t-1}) = \log \pi_0(y_t\mid h_{t-1}) +\big[\log Z(h_t)-\log Z(h_{t-1})\big]. \]
That extra term is a logit bias-a small additive shift that nudges the model toward continuations more likely to lead to success.
If we have a predictor \(s_\phi(h)\approx p_{\text{succ}}(h)\), we can practically implement this kind of “time travel” in modeling. For example, such predictions can be made using random sampling methods like MCTS.
The math of RLVR can be read as a gentle form of time travel.
A one-bit signal from the future—“your output passes the verifier”—induces an exponential bias on today’s generation. That bias is equivalent to optimizing a KL-regularized reward objective.At the token level, it becomes a clean logit adjustment guided by the probability of eventual success.
Please cite this blog post as:
@misc{dang2025rlvrtimetravel,
author = {Dang, Xingyu},
title = {RLVR is Time-Traveling},
year = {2025},
month = {November},
url = {https://dangxingyu.github.io/blog/rlvr-ttlm.html}
}