REVIEW 2 major objections 5 minor
Transformers in Pseudo-Random Number Generation: A Dual Perspective on Theory and Practice
T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read The paper argues that decoder-only Transformers with chain-of-thought can exactly simulate the Linear Congruential Generator and the Mersenne Twister, and that this simulation implies log-precision Transformers can represent non-uniform…
desk verdict Interesting claim, but the AC^0 conclusion is a logical leap the abstract doesn't support; worth a referee only if the full proof closes the gap. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is a decoder-only Transformer in a log-precision arithmetic model augmented with chain-of-thought (CoT): the model is allowed to write intermediate tokens that carry the PRNG state forward step by step. The argument uses those CoT steps to simulate a recurrence (LCG: $x_{n+1} = (a x_n + c) \bmod m$) and a state update plus tempering transform (Mersenne Twister), giving a concrete constructive path from Transformer computation to a non-uniform AC$^0$ circuit family. The identity doing the work is the claimed equivalence between simulating these recurrences in the CoT model and representing the corresponding Boolean function class; the authors rely on this equivalence to conclude that log-precision decoder-only Transformers can represent non-uniform $\text{AC}^0$.
What would settle it
Run the proposed simulation with explicit log-precision arithmetic on Mersenne Twister states of growing length n: if tempering requires storing more than $O(\log n)$ bits per intermediate value, or if the chain-of-thought length needed for one state update grows super-polynomially in n, the log-precision AC$^0$ conclusion collapses.
Extended reading notes
Core claim
The paper's central claim is that simulation is provable: a decoder-only Transformer with chain-of-thought can step through the recurrence of an LCG and the state-update plus tempering of the Mersenne Twister, so the Transformer's output can be made to equal the PRNG's sequence. The authors then draw a complexity conclusion: because these generators can be simulated in this setting, the log-precision decoder-only Transformer can represent non-uniform $\text{AC}^0$ — constant-depth, unbounded fan-in Boolean circuit families of polynomial size — and is therefore not confined to weaker uniform circuit classes sometimes assumed for fixed-depth attention. In practice they find that sequences from Transformer-based PRNGs pass the majority of NIST randomness tests, show clear statistical randomness in heat maps, and they report experiments that assess whether generated numbers can be forecast by a prediction attack. The paper thus presents the Transformer as both a theoretical model of PRNG computation and a practical random-number source inside LLM pipelines.
Load-bearing premise
The conclusion depends on an unstated precise limit on chain-of-thought length and on intermediate precision in the log-precision Transformer model; if that limit is loose enough to allow full-precision state tracking, simulating these PRNGs would not imply anything about non-uniform AC$^0$.
Editorial extensions
If this is right
- Log-precision decoder-only Transformers with chain-of-thought can reproduce the exact output sequence of the Linear Congruential Generator and the Mersenne Twister.
- The class of functions representable by such Transformers includes non-uniform AC$^0$, so complexity statements about these models must account for chain-of-thought.
- Transformer-based PRNGs pass most of the NIST randomness tests, making them statistically plausible random sources in practice, at least on the tested suite.
- Prediction attacks on these generators are feasible enough to assess, which matters for any security- or optimization-sensitive use of learned randomness.
- Because the model itself can generate pseudo-random numbers, LLM pipelines may embed randomness generation without separate external PRNG calls.
Reading between the lines
- The paper does not claim exact equivalence between its theory and practice: the theoretical claim is about exact simulation, while the empirical claim is that most NIST tests pass, so a natural follow-up is to compare Transformer output against the true seeded LCG/MT sequence across many seeds and measure disagreement.
- If the simulation result transfers to other recurrence-based PRNGs, such as xorshift or PCG, the AC$^0$-representability conclusion would generalize; the paper does not make that claim.
- The existence of a simulating weight assignment does not imply gradient descent will find it, so a useful extension is to train small models with program-style objectives and see whether they discover the LCG/MT state transition.
- Successful prediction attacks would warn against using Transformer-based PRNGs for cryptographic or secret-dependent sampling, because the generator's structure could be learnable from outputs.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims to demonstrate, from a theoretical and practical viewpoint, that decoder-only Transformer models with Chain-of-Thought can simulate both the Linear Congruential Generator and the Mersenne Twister PRNGs, and from this concludes that log-precision decoder-only Transformers can represent non-uniform AC^0. It further reports that the simulation is validated by NIST tests and that prediction-attack capability is assessed. This review is based solely on the abstract, as the full text was not available for inspection.
Significance. If the theoretical result is established under rigorous formal conditions, it would provide a concrete example of Transformer computation of nonlinear arithmetic and a complexity-theoretic statement about log-precision Transformers. However, as presented, the abstract does not provide the formal model, proof outline, or experimental details needed to assess the strength of these claims. The manuscript appears to offer no machine-checked proofs, reproducible code, or parameter-free derivations in the abstract. The claimed connection to non-uniform AC^0 is not justified by simply simulating two PRNGs, and the experimental validation as described is too vague to support the theoretical conclusion.
major comments (2)
- [Abstract] The inference from simulating LCG and MT to 'log-precision decoder-only Transformer can represent non-uniform AC^0' is not a logical consequence of the stated simulation. To conclude representability of the whole class AC^0, one needs either a universal construction that simulates an arbitrary constant-depth polynomial-size circuit or a separate embedding lemma; the abstract supplies neither. Moreover, the Mersenne Twister's state update uses modular multiplication modulo 2^w, which is not computable in AC^0 under standard definitions (Furst-Saxe-Sipser, Ajtai). If the simulation is claimed to yield constant-depth circuits, the paper must specify how the modular multiplication is implemented and which resources (precision, chain-of-thought length, positional encodings) are used; otherwise the complexity-theoretic conclusion cannot be checked.
- [Abstract] The statement that 'the random numbers generated by Transformer-based PRNGs successfully pass the majority of NIST tests' is too vague to constitute validation. NIST SP 800-22 consists of many tests with multiple parameters; passing a majority is a weak and ambiguous criterion. The abstract does not report the number of bit sequences, sequence lengths, p-value thresholds, the specific tests passed or failed, or the Transformer architecture and training details. Without these, the experimental support for the theoretical claim cannot be evaluated.
minor comments (5)
- [Abstract] The phrase 'high-nonlinear processes' is imprecise; the authors should specify the notion of nonlinearity or replace it with a technical description.
- [Abstract] The phrase 'optimization of Large language models' is vague; the connection between PRNGs and LLM optimization should be clarified.
- [Abstract] The notation 'AC^0' should be defined as non-uniform constant-depth polynomial-size circuits with unbounded fan-in AND/OR/NOT gates, and the meaning of 'represent' should be stated explicitly.
- [Abstract] The abstract mentions heat maps exhibiting 'clear statistical randomness' but does not describe them; the full text should include a detailed figure and explanation.
- [Abstract] The abstract mentions assessing prediction-attack capability but gives no result or comparison; a quantitative statement is needed for the reader to understand the practical contribution.
Circularity Check
No circularity found in the abstract-only derivation; the theoretical claim is presented as a derivation and the experiments as validation, with no fitted parameter masquerading as a prediction.
full rationale
This review covers only the abstract and reader-provided context; the full derivation is unavailable. Within the provided text, the paper's central chain is: decoder-only Transformers with Chain-of-Thought can simulate LCG and MT, therefore log-precision decoder-only Transformers can represent non-uniform AC^0, and the simulation findings are then validated by NIST tests. None of these steps reduces to its own input by construction. The theoretical claim is stated as a demonstrated result rather than as a fit, and the NIST tests are presented as independent empirical validation of the generated random numbers. No fitted parameter is renamed as a prediction, no self-citation is invoked as load-bearing evidence, and no definition is circular in the available text. The abstract does not provide the proof, so one cannot verify the AC^0 inference, and the inference may be a non-sequitur if the simulations are not universal for AC^0; that is a correctness or completeness concern, not a circularity concern. Since no specific reduction can be quoted, the honest finding is no significant circularity.
Assumptions & free parameters
assumptions (2)
- domain assumption The formal model of a 'log-precision decoder-only Transformer' matches prior standard definitions used in expressivity results.
- domain assumption Chain-of-Thought can grow arbitrarily long, allowing simulation of an arbitrary number of PRNG update steps.
Cite this review
Pith. "Pith review of Transformers in Pseudo-Random Number Generation: A Dual Perspective on Theory and Practice." pith.science (2026). https://pith.science/paper/QAMTBXI5
@misc{pith2026250801134,
author = {Pith},
title = {Pith review of: Transformers in Pseudo-Random Number Generation: A Dual Perspective on Theory and Practice},
year = {2026},
howpublished = {\url{https://pith.science/paper/QAMTBXI5}},
note = {Machine review of arXiv:2508.01134}
}
abstract
Pseudo-random number generators (PRNGs) are high-nonlinear processes, and they are key blocks in optimization of Large language models. Transformers excel at processing complex nonlinear relationships. Thus it is reasonable to generate high-quality pseudo-random numbers based on transformers. In this paper, we explore this question from both theoretical and practical perspectives, highlighting the potential benefits and implications of Transformer in PRNGs. We theoretically demonstrate that decoder-only Transformer models with Chain-of-Thought can simulate both the Linear Congruential Generator (LCG) and Mersenne Twister (MT) PRNGs. Based on this, we conclude that the log-precision decoder-only Transformer can represent non-uniform $\text{AC}^0$. Our simulative theoretical findings are validated through experiments. The random numbers generated by Transformer-based PRNGs successfully pass the majority of NIST tests, whose heat maps exhibit clear statistical randomness. Finally, we assess their capability in prediction attacks.
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.