{"id":"6b98cb0f-4b9c-4d93-aa00-12529349e64d","arxiv_id":"2504.20771","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"TMBench measures LLM computational reasoning by having models simulate m-tag systems step by step, and its pass rates correlate with AIME2024, MATH500, GPQA Diamond, and MMLU Pro scores across 12 leading models.","lead":"This paper introduces TMBench, a benchmark that asks large language models to simulate a simple rule-based machine called a tag system, step by step. It argues that performance on this abstract task predicts how well the same models reason on math and science benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Correlation claim in Sec. 4.3 lacks control for model scale and family; the composite reasoning-score correlation may overstate TMBench's proxy validity.","rationale":"The reader's weakest_assumption is exactly the confound concern I identify: correlations across 12 models without scale/family control. I agree with the CONDITIONAL verdict. The benchmark design itself (m-tag simulation, step accuracy, pass rate) is clean, reproducible, and genuinely knowledge-agnostic; the main risk is the over-interpretation of correlational evidence as validating TMBench as a proxy. My concrete test would settle the concern by expanding the model set and controlling for scale. I do not see a fatal flaw in the construction, so I would not move to REJECT; but the proxy claim needs the added analysis before full acceptance.","tokens_in":18457,"tokens_out":1227,"duration_ms":10941,"concrete_test":"Recompute the Sec. 4.3 correlations including the 24 additional models already evaluated in Table 2 (which have both TMBench and benchmark scores), then fit a multiple regression of reasoning-benchmark average on TMBench pass rate, log-parameter count, and model family/date dummies. Report partial correlation of TMBench controlling for scale; if it drops below significance or changes sign, the proxy claim is not supported. Also run a leave-one-out analysis on the 12-model set and report the minimum R^2 across deletions.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central proxy claim rests on Sec. 4.3's correlations between TMBench pass rate and AIME2024/MATH500/GPQA/MMLU Pro across 12 models. The paper reports R^2=0.72, 0.64, 0.82, 0.63 and a composite Pearson r=0.882. No partial correlations, residual analyses, or regressions controlling for model parameter count, model family, or API-access/training recency are reported. Given that both TMBench and the reasoning benchmarks improve strongly with scale and recent post-training, the observed correlations could be driven by a confound rather than a shared \"computational reasoning\" factor. The claim that the correlation order (GPQA > AIME > MATH > MMLU) reflects reasoning depth is also unsupported without controlling for benchmark-specific noise. Crucially, the empirical setup does not establish that TMBench adds predictive information beyond a simple scale/recency proxy, so the headline claim that TMBench is a validated cross-domain proxy is conditional at best. A second weak spot is that the correlation uses normalized scores and only 12 selected models; a single outlier (e.g., Gemini or Grok) can drive R^2. The reasoning-score correlation r=0.882 is presented without confidence intervals or leave-one-out checks.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Turing Machine Bench (TMBench), a benchmark that evaluates LLMs on the step-by-step execution of m-tag systems, a Turing-complete queue-based rewriting model. Each problem provides a small alphabet, production rules, an initial queue, and a step limit; the model must output the queue state after each transition. The authors define three metrics—step accuracy, step-weighted accuracy, and pass rate—and evaluate roughly three dozen open-source and proprietary models, producing per-step accuracy curves (Figure 1) and a model ranking table (Table 2). The central validation claim, in Section 4.3 and Figure 2, is that TMBench pass rate correlates strongly with AIME2024, MATH500, GPQA Diamond, and MMLU Pro across 12 models (reported R² values 0.63–0.82 and a composite Pearson r = 0.882), supporting TMBench as a proxy for general computational reasoning. The paper also reports ablations on unbounded-step execution, temperature, alphabet type, and deletion number (Section 4.4).","tokens_in":18746,"tokens_out":4409,"duration_ms":46120,"significance":"If the proxy claim holds, TMBench would be a valuable addition to LLM evaluation: it is knowledge-agnostic, has exact ground truth at every step, offers controllable difficulty, and yields interpretable step-wise performance curves. The core measurement is straightforward and internally consistent, and the paper covers a broad and current model set. The main contribution is empirical rather than theoretical—the m-tag system is a known Turing-complete model—but the benchmark design and metrics are clean and reproducible in principle. The significance is therefore contingent on whether the cross-benchmark correlations in Section 4.3 survive appropriate statistical controls; in its current form, the evidence for the headline proxy claim is suggestive but not conclusive.","major_comments":[{"comment":"The central proxy-validity claim rests on correlations across only 12 models with no control for model scale, model family, or training recency. TMBench pass rate and the four reasoning benchmarks all improve substantially with model size and recent post-training, so the reported correlations could be driven by a common scaling/recency confound rather than by a shared 'computational reasoning' factor. The claim that TMBench 'serves as an effective proxy' therefore needs support from partial correlations controlling for log parameter count, within-family comparisons (e.g., Qwen models alone), or residual analysis after removing a scale trend. Please add these analyses and report model parameter counts for the 12 models.","section":"Section 4.3, Figure 2, Table 2"},{"comment":"The correlation analysis uses min-max normalized scores on a small, nonrandom sample of 12 models, and the reported p-values are not corrected for multiple comparisons. A single outlier can drive an R² value when n=12, and min-max normalization can exaggerate correlation magnitudes. Please report raw-score correlations with confidence intervals, add leave-one-out or bootstrap analyses, and report Spearman correlations as a robustness check. The composite reasoning score (r = 0.882, Figure 5) is also presented without a confidence interval; the claim that the correlation order GPQA > AIME2024 > MATH500 > MMLU reflects reasoning depth is not supported without additional error bars and a test of the differences between these correlations.","section":"Section 4.3, Figure 2, Figure 5"},{"comment":"The step-accuracy curves and SWA values are presented without error bars or variance estimates, making it difficult to know whether differences between models (e.g., Qwen3-32B at 10.5 vs. R1-Distill-Qwen-32B at 33.5 in Table 2) are meaningful. Since each configuration appears to use a single greedy decoding pass per instance, please report standard errors, bootstrap confidence intervals, or repeated sampling results for the per-step accuracies and the SWA metrics.","section":"Section 3.3, Figure 1, Table 2"},{"comment":"The unbounded-step ablation is based on a single model (Gemini-2.5-Pro) with 10 samples and budget forcing. The statement that LLMs 'inevitably fail with increasing steps due to their autoregressive nature' is too strong for this evidence. Either restrict the conclusion to Gemini-2.5-Pro or include additional models and more samples before making a general claim about autoregressive LLMs.","section":"Section 4.4, Figure 3a"}],"minor_comments":[{"comment":"The step-by-step queue states in Table 1 are inconsistent: some rows appear to show the queue after appending but before deletion, while others appear to show the state after deletion. Please clarify the convention used in the table so that it matches the formal step definition in Eq. (1) and the prompt template in Appendix B.2.","section":"Table 1"},{"comment":"The phrase 'strictly follow rules and accurately manage internal states for multi-step' is missing a noun (e.g., 'multi-step computation'), and the phrase 'referred to as computational reasoning' is grammatically incomplete. Please revise for clarity.","section":"Abstract and Section 1"},{"comment":"Figure 3c does not identify which models are included in the alphabet ablation, and the text says 'as illustrated in Figure Figure 3c.' Please label the models and fix the typo.","section":"Section 4.4, Figure 3c"},{"comment":"The caption contains the typo 'Token Distrubition' and should be 'Token Distribution.'","section":"Figure 4 caption"},{"comment":"The composite 'Reasnoing Score' in Figure 5 is labeled inconsistently with the text (the text says Reasoning Score) and it averages only AIME2024, MATH500, and GPQA, while MMLU Pro is shown separately in Figure 2. Please define the composite score clearly and consistently.","section":"Figure 5 and Section 4.3"},{"comment":"Reference [70] is cited for GPT-4.1 but is titled 'OpenAI o1 system card'; please verify the citation and provide the correct source for GPT-4.1.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The benchmark itself is simple, reproducible, and likely useful as a diagnostic tool, and the per-step accuracy curves are a nice feature. The main risk is the validation section: the headline correlation claim is not yet supported by analysis that controls for scale and family, and the small selected sample makes the reported R² values fragile. If the authors can add partial correlations, leave-one-out checks, confidence intervals, and within-family comparisons, the paper would be much stronger. I do not see a fundamental flaw in the benchmark design, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, you should know this: the benchmark is real, new, and clean. m-tag systems are a good choice — simple, Turing-complete, and the per-step queue evaluation gives you a fine-grained view of where models fail. The code, prompt, and data are released, and the step-accuracy curves are informative. I'd be happy to see TMBench used as a synthetic probe for instruction-following and state tracking.\n\nThe problem is Section 4.3. The paper claims TMBench is an effective proxy for real-world reasoning based on correlations with AIME2024, MATH500, GPQA, and MMLU across 12 models. Those correlations are plausible but unproven. There is no control for model size or family, no partial correlations, no confidence intervals, no leave-one-out. With 12 points, a single outlier (Grok or Gemini) can move an R^2 a lot. Both TMBench and these benchmarks improve with scale and recent post-training, so the shared variance could just be \"new model does everything better.\" The r=0.882 composite is presented without any uncertainty quantification. The authors say the correlation order (GPQA > AIME > MATH > MMLU) is \"expected\" and reflects reasoning depth, but that's post hoc and unsupported without controlling for benchmark-specific noise.\n\nOther soft spots: the ablations on temperature, alphabet, and difficulty are on Gemini-2.5-Pro only, so those robustness claims are really about one model. The alphabet-robustness conclusion (\"relies on reasoning rather than statistics\") is stronger than the evidence. And the unbounded-step section is a single-model case study, which is fine, but shouldn't be phrased as a general law of autoregressive models.\n\nNone of this kills the paper. The benchmark is a solid contribution on its own. The proxy claim just needs to be tempered. I'd send it to a serious referee, but I'd ask for a revised validation section that at least does a partial correlation with a parameter-count proxy, leave-one-out correlations, and bootstrap confidence intervals. The authors should also acknowledge the narrowness of \"computational reasoning\" — executing a tag system is a useful sub-skill, not the same as the reasoning needed for AIME.\n\nBottom line: cite the benchmark, treat the proxy claim as promising but conditional.","headline":"A genuinely useful synthetic benchmark for rule-execution, but the cross-domain proxy claim rests on a correlation analysis that doesn't control for scale or family.","tokens_in":19246,"tokens_out":3142,"would_cite":true,"duration_ms":31201,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Turing Machine Bench scores LLMs by how faithfully they simulate a queue-based m-tag system, and reports that those scores strongly correlate with mainstream reasoning benchmarks.","keywords":["LLM evaluation","computational reasoning","Turing machine","tag system","multi-step reasoning","rule following","benchmark correlation"],"falsifier":"Regress established-benchmark scores on TMBench pass rate within model families matched for parameter count: if the correlation largely disappears, the claim that TMBench measures a distinct computational-reasoning factor is falsified. A single counterexample model with a high TMBench pass rate but poor AIME or GPQA performance, or the reverse, would also break the reported relationship.","tokens_in":18300,"feed_emoji":"🧮","tokens_out":9553,"duration_ms":84030,"temperature":0.7,"pith_summary":"TMBench asks an LLM to simulate an m-tag system step by step: read the head symbol of a growing queue, append the production rule's output to the tail, then delete m symbols. The paper argues that this isolates a basic, knowledge-free ability it calls computational reasoning—strictly following rules and accurately managing internal state across many steps. Its central empirical claim is that the pass rate on TMBench strongly correlates with performance on established reasoning benchmarks across twelve leading LLMs, with the strongest correlations on GPQA and AIME2024. If that claim holds, a small simulation task can serve as a cross-domain proxy for LLM reasoning without depending on domain knowledge that may leak into training data.","feed_headline":"A Turing-machine benchmark predicts LLM reasoning scores","feed_subtitle":"TMBench scores rule-following and state tracking; those scores line up with AIME, MATH, GPQA, and MMLU-Pro results.","key_machinery":"The m-tag system is a queue-based computational model: at each step the machine reads the queue head, appends the production word for that symbol to the tail, and deletes the first m symbols; for $m > 1$ it is Turing-complete, so any computable function can in principle be encoded. This machinery carries the argument because the LLM must perform exactly the operations that define computational reasoning—reading a rule, updating a queue, deleting symbols, and tracking a growing state—with every intermediate queue recorded for scoring. The benchmark defines three metrics on the resulting trace: per-step accuracy, step-weighted accuracy under uniform and linear weights, and pass rate, the probability of completing the simulation within the step limit without error.","core_discovery":"The paper's discovery is a measurable, controllable proxy for multi-step rule execution. On TMBench, accuracy declines smoothly with simulation step number for every model, yet overall pass rate tracks real-task reasoning performance; the top proprietary models keep accuracy above 90% at step 30, while models below about 4 billion parameters struggle even at the first step. Across twelve models, TMBench pass rate correlates with AIME2024, MATH500, GPQA Diamond, and MMLU Pro, with reported $R^2$ values of 0.72, 0.64, 0.82, and 0.63, and the average reasoning score across AIME, MATH, and GPQA gives a Pearson correlation of 0.882. The authors read the correlation pattern—stronger on GPQA and AIME than on MMLU—as evidence that tasks demanding deeper computation depend more heavily on computational reasoning. The benchmark also produces clean step-wise accuracy curves, so it can reveal exactly where multi-step execution breaks down.","pith_inferences":["Beyond the paper: a TMBench-style simulator run could serve as a cheap pre-screen before expensive multi-benchmark evaluations, provided the reported correlation generalizes past the twelve models.","Beyond the paper: a natural next test is whether pass rates also predict execution-style tasks such as code tracing or formal proof step-checking, which share the same rule-following load.","Beyond the paper: because the reported correlations do not control for model scale or API availability, the shared-factor interpretation is not yet separated from overall capability; controlling for parameter count within a family would make the proxy claim much stronger.","Beyond the paper: the smooth difficulty curve in the deletion-number ablation suggests a scaling-law-style experiment measuring how model size or inference compute must grow with step depth to keep pass rate constant."],"forward_implications":["A strong TMBench pass rate gives a knowledge-agnostic signal that the same model will likely do well on reasoning-heavy benchmarks such as GPQA and AIME2024.","The step-wise accuracy curves localize error propagation, so users can see at which step a model starts to lose the state rather than only whether the final answer is correct.","Because the deletion number m, rule lengths, and initial string lengths can be varied, TMBench can generate a continuous difficulty gradient for evaluating reasoning at chosen depths.","Because the tasks are self-contained and synthetic, benchmark scores are largely resistant to contamination by memorized test questions from pre-training data.","Since every autoregressive model eventually fails as the number of steps grows, TMBench can also serve as a stress test for long-horizon rule following."],"supporting_citations":[{"why":"Defines the Turing machine, the model of computation whose universality motivates the benchmark's theoretical framing.","marker":"[54]"},{"why":"Introduces the tag system, the queue-based computational model that TMBench asks LLMs to simulate.","marker":"[57]"},{"why":"Proves universality of 2-tag systems, grounding the claim that m-tag simulation is a Turing-complete task.","marker":"[56]"},{"why":"Extends the theory of tag and lag systems and supports the Turing-completeness statement for m > 1.","marker":"[55]"},{"why":"Supplies AIME2024 scores used as one of the real-reasoning benchmarks in the correlation analysis.","marker":"[13]"},{"why":"Supplies MATH500 scores used as one of the real-reasoning benchmarks in the correlation analysis.","marker":"[58]"},{"why":"Supplies GPQA Diamond scores used as the reasoning-heavy benchmark in the correlation analysis.","marker":"[2]"},{"why":"Supplies MMLU Pro scores used as the knowledge-heavy benchmark in the correlation analysis.","marker":"[59]"},{"why":"Shows LLMs can be trained to execute arithmetic by simulating a Turing machine, motivating simulation-based evaluation.","marker":"[16]"}],"fun_headline_variants":["Turing machine benchmark predicts LLM reasoning performance","TMBench: a simple proxy for multi-step LLM reasoning","Step-wise accuracy curves expose LLM reasoning breakdowns","TMBench scores track reasoning on AIME, MATH, and GPQA","Controllable difficulty benchmark reveals LLM reasoning limits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"TMBench's value as a proxy depends on the assumption that the observed correlations across twelve models reflect one shared computational-reasoning ability, and not simply model size, API access, or general instruction-following strength.","fun_headline_variants_meta":{"raw":{"variants":["Turing machine benchmark predicts LLM reasoning performance","TMBench: a simple proxy for multi-step LLM reasoning","Step-wise accuracy curves expose LLM reasoning breakdowns","TMBench scores track reasoning on AIME, MATH, and GPQA","Controllable difficulty benchmark reveals LLM reasoning limits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000788,"raw_usage":{"total_tokens":3533,"prompt_tokens":1061,"completion_tokens":2472,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":677,"completion_tokens_details":{"reasoning_tokens":2396}},"tokens_in":677,"tokens_out":2472,"duration_ms":19784,"temperature":1.0,"reasoning_tokens":2396,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:19:47.927951+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Regress established-benchmark scores on TMBench pass rate within model families matched for parameter count: if the correlation largely disappears, the claim that TMBench measures a distinct computational-reasoning factor is falsified. A single counterexample model with a high TMBench pass rate but poor AIME or GPQA performance, or the reverse, would also break the reported relationship.","supporting_citations":[{"cited_title":"On computable numbers, with an application to the entschei- dungsproblem","cited_arxiv_id":null,"evidence_quote":"Defines the Turing machine, the model of computation whose universality motivates the benchmark's theoretical framing."},{"cited_title":"Formal reductions of the general combinatorial decision problem","cited_arxiv_id":null,"evidence_quote":"Introduces the tag system, the queue-based computational model that TMBench asks LLMs to simulate."},{"cited_title":"Universality of tag systems with p = 2","cited_arxiv_id":null,"evidence_quote":"Proves universality of 2-tag systems, grounding the claim that m-tag simulation is a Turing-complete task."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Extends the theory of tag and lag systems and supports the Turing-completeness statement for m > 1."},{"cited_title":"Executing Arithmetic: Fine-Tuning Large Language Models as Turing Machines","cited_arxiv_id":"2410.07896","evidence_quote":"Shows LLMs can be trained to execute arithmetic by simulating a Turing machine, motivating simulation-based evaluation."}],"review_version":1}