{"id":"737ba2dd-2f30-4a0a-bb92-0d3084cc75cd","arxiv_id":"2508.01134","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":4.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Decoder-only Transformers with chain-of-thought can simulate LCG and Mersenne Twister PRNGs, and their outputs pass most NIST tests.","lead":"This paper claims that decoder-only Transformer models using chain-of-thought can mimic two standard pseudo-random number generators, the linear congruential generator and the Mersenne Twister. The authors also report that Transformer-based generators pass most NIST randomness tests and connect this to a complexity theory result about non-uniform AC^0 circuits.","discovery_kind":"unclear","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The inference from simulating two PRNGs to representing all of non-uniform AC^0 is a non-sequitur unless the simulations are universal; MT's modular arithmetic also collides with known AC^0 lower bounds.","rationale":"The reader's weak assumption is on target: the abstract omits the formal conditions needed to evaluate the complexity claim. I sharpen this to a single load-bearing point: the implication from two successful simulations to representability of all of non-uniform AC^0 is invalid without a universality lemma, and the MT case raises a specific lower-bound red flag. Since the full text is not available, no machine-checked proof or reproducible code can offset the missing argument. I recommend keeping the UNVERDICTED status rather than accepting or rejecting, because a complete formal proof could in principle resolve the gap; the requested consistency check on MT's modular multiplication would decide whether the gap is fatal.","tokens_in":737,"tokens_out":6554,"duration_ms":85204,"concrete_test":"Request the omitted formal construction and run a consistency check: (1) define the log-precision decoder-only Transformer's precision bound, positional encoding, CoT length T(n), and arithmetic operations; (2) ask for the explicit AC^0-style circuit family that simulates MT; (3) verify whether that family can compute modular multiplication by a*c mod 2^w in constant depth with unbounded fan-in AND/OR/NOT gates. If it can, the proof contradicts Furst–Saxe–Sipser and must contain a hidden operation; if it cannot, the paper lacks a proof of representability of non-uniform AC^0. Alternatively, request a lemma embedding arbitrary AC^0 circuits into the same transformer framework.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract's central chain is: CoT decoder-only Transformers simulate LCG and MT; therefore log-precision decoder-only Transformers can represent non-uniform AC^0. The second step is not a logical consequence of the first unless the simulations are universal for the class AC^0 or a separate embedding lemma is supplied; the abstract provides neither. This is not merely a missing detail: it is the entire theoretical contribution. The tension is sharp because the Mersenne Twister's state update uses modular multiplication modulo 2^w together with shifts and XOR, and multiplication is provably outside AC^0 (Furst, Saxe, Sipser; Ajtai). If the claimed simulation really yields constant-depth, polynomial-size AND/OR/NOT circuits for MT, then either the construction smuggles in non-AC^0 capability through precision, positional encodings, or an unbounded chain-of-thought length, or the paper uses 'represent AC^0' in a non-standard sense. In either case the complexity-theoretic conclusion cannot be checked without specifying the formal model: precision as a function of sequence length, allowed arithmetic, CoT length bound, and the meaning of 'represent'.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":950,"tokens_out":3888,"duration_ms":47038,"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":[{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"Abstract"}],"minor_comments":[{"comment":"The phrase 'high-nonlinear processes' is imprecise; the authors should specify the notion of nonlinearity or replace it with a technical description.","section":"Abstract"},{"comment":"The phrase 'optimization of Large language models' is vague; the connection between PRNGs and LLM optimization should be clarified.","section":"Abstract"},{"comment":"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.","section":"Abstract"},{"comment":"The abstract mentions heat maps exhibiting 'clear statistical randomness' but does not describe them; the full text should include a detailed figure and explanation.","section":"Abstract"},{"comment":"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.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"This report is based only on the abstract, so I could not verify the full proofs or experiments. The central logical gap—simulating two PRNGs does not imply representability of all of non-uniform AC^0—is serious and will require either a general AC^0 simulation theorem or a reformulated claim. I recommend asking the authors to provide the full formal definitions, a complete proof outline, and detailed experimental parameters before the paper can be assessed for acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's central idea—giving a theoretical expressivity result for decoder-only Transformers with chain-of-thought simulating LCG and Mersenne Twister—is genuinely new as far as the abstract shows. Most neural PRNG work is purely empirical, and the dual theory/practice framing is a nice angle. The NIST test results, even if vaguely reported, suggest real experiments were run. So there is something here worth engaging with.\n\nThe soft spot is a big one. The abstract claims that simulating two specific PRNGs implies the log-precision decoder-only Transformer can represent non-uniform AC^0. That does not follow unless the simulation is universal for the class, or unless a separate embedding argument is supplied. The abstract gives neither. The tension is sharp because the Mersenne Twister's state update uses modular multiplication, and multiplication is provably outside AC^0 (Furst-Saxe-Sipser, Ajtai). If the construction really yields constant-depth, polynomial-size circuits for MT, then the model must be smuggling in extra power through precision, positional encodings, or an unbounded CoT length—or \"represent AC^0\" is being used in a non-standard sense. This is not a minor detail; it is the theoretical contribution. A referee would need to see the precise definitions: precision as a function of sequence length, allowed arithmetic, CoT length bound, and the exact meaning of \"represent.\"\n\nThe experimental reporting is also too thin. \"Majority of NIST tests\" and \"heat maps exhibit clear statistical randomness\" are not quantitative. No parameter counts, no training details, no actual NIST p-values, no description of the prediction attack setup. That is fixable in a full paper, but it matters because the practical claims are part of the abstract's promise.\n\nI cannot judge the citation pattern from the abstract alone, and I will not assume self-citation is a problem. The proof is the thing.\n\nMy take: this deserves a serious referee. The claim, if true, would be a real expressivity result, and the complexity-theoretic tension is exactly what a referee should pressure-test. I would not cite or trust the AC^0 conclusion based on the abstract; I would want the full derivation first. For a reading group, it is a maybe—the paper could be a useful springboard for discussing CoT expressivity, but you would need the full text to get value. Send it to peer review with a clear request to verify the logical bridge from simulating two PRNGs to representing all of non-uniform AC^0.","headline":"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.","tokens_in":1461,"tokens_out":1356,"would_cite":false,"duration_ms":18281,"reading_group":"maybe","serious_thinker":"unclear","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","68T07","65C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["pseudo-random number generation","Transformers","chain-of-thought","linear congruential generator","Mersenne Twister","non-uniform AC^0","NIST statistical tests","prediction attacks"],"falsifier":"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.","tokens_in":1367,"feed_emoji":"🎲","tokens_out":2396,"duration_ms":88002,"temperature":0.7,"pith_summary":"This paper tries to establish that Transformer language models can act as pseudo-random number generators (PRNGs), and that this fact has consequences for what Transformers can compute. The authors give constructions by which a decoder-only Transformer, allowed to emit chain-of-thought, simulates the state-update recurrences of the Linear Congruential Generator and the Mersenne Twister. From those simulations they conclude that a log-precision decoder-only Transformer can represent non-uniform $\\text{AC}^0$, the class of problems solvable by constant-depth Boolean circuits. Practically, they report that Transformer-generated random sequences pass most of the NIST statistical test suite and display clear randomness in heat maps, and they also assess how well a Transformer can predict PRNG outputs. If the theory holds, the same architecture that generates language can also produce deterministic pseudorandom streams without an external PRNG, which would matter for LLM-based sampling and optimization loops.","feed_headline":"Transformers can mimic two classic pseudo-random generators","feed_subtitle":"With chain-of-thought, log-precision Transformers reproduce the LCG and Mersenne Twister; most NIST tests pass.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[],"fun_headline_variants":["Chain-of-thought Transformers mimic LCG and Mersenne Twister, pass NIST","Transformers emulate classic PRNGs: proof and NIST-passing practice","CoT Transformers simulate LCG and MT, represent non-uniform AC^0","Transformers can step through LCG and MT recurrences; NIST approves"],"cache_read_input_tokens":3712,"weakest_assumption_plain":"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$.","fun_headline_variants_meta":{"raw":{"variants":["Chain-of-thought Transformers mimic LCG and Mersenne Twister, pass NIST","Transformers emulate classic PRNGs: proof and NIST-passing practice","CoT Transformers simulate LCG and MT, represent non-uniform AC^0","Transformers can step through LCG and MT recurrences; NIST approves"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000926,"raw_usage":{"total_tokens":3953,"prompt_tokens":912,"completion_tokens":3041,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":528,"completion_tokens_details":{"reasoning_tokens":2953}},"tokens_in":528,"tokens_out":3041,"duration_ms":25950,"temperature":1.0,"reasoning_tokens":2953,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T05:47:49.456941+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}