acceptodds
Under review as a conference paper at ICLR 2027

Computational Reasoning Machine

Abstract

Contemporary work demonstrates that reasoning strategies can structure transformer inference, showing improved task-performance over pure streams of tokens. These frameworks enable : The reasoning processes feature causal dependency structures, procedural abstractions, and task concurrency. However, prior work implementing reasoning strategies requires ad-hoc programmatic wrappers, inflexible and blind to the problem at hand. All of these concepts have analogies to computational primitives in computer systems (e.g. programming languages, operating systems, and computer architecture). We demonstrate that, instead of requiring a model to reason solely in natural language in a stream of tokens, we can augment the model's vocabulary with computational primitives: variables with scopes, functions, and deferred execution. Doing so enables a model to manage its context (reducing the number of tokens attended to), to abstract and reuse its own reasoning process (reducing the number of generated tokens), and to multitask (increasing the decoding throughput) natively during the course of its decoding process. We augment the transformer architecture to produce what we term a to elicit computational reasoning naturally in transformers. Specifically, we modify self-attention to reflect the machine's causal dependency structures, reuse procedural abstractions, reveal task concurrency opportunities, and reject invalid executions of the machine. Our results show a reduction in mean attended tokens per token (39.0-60.8%) and an increase in available decoding parallelism (1.1-1.28x), at the cost of increased KV cache usage (2.6-40%) and a 1.9-17.7pp drop in accuracy. RL narrows the accuracy drop to 1.2-6.7pp.

Primary area:
foundation or frontier models, including LLMs
Keywords:
reasoning, transformer

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_BVsHOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces a Computational Reasoning Machine (CRM), which augments a transformer with a structured language called CRM ASSEMBLY. The model emits primitives that define variables and scopes, reusable functions, and deferred computations. These primitives determine which earlier reasoning tokens remain visible to subsequent tokens through dynamically constructed attention masks.

Critical strengths

Novel approach to structuring model reasoning through CRM ASSEMBLY, which supports scoped variables, reusable functions, deferred execution, and dynamic attention masking. The authors implement these mechanisms in a transformer and evaluate them across four reasoning benchmarks. Results show substantial reductions in attended tokens and shorter outputs, which means potential benefits in computational efficiency.

Critical weaknesses

Practical efficiency benefits are not sufficiently demonstrated. The paper reports reduced attention computation and theoretical parallelism, but does not establish corresponding end-to-end latency or throughput improvements. Accuracy also remains 1.2–6.7 percentage points below the CoT baseline after preference optimization. Evaluation lacks sufficient ablation studies to isolate the contributions of individual components, and syntax or runtime failures can truncate reasoning traces. The evaluation focuses on a single 4B model and a 4096-token context, so scalability and generalizability is unknown.

Questions for authors

Can you provide end-to-end inference latency, throughput, and memory measurements demonstrating that CRM delivers practical efficiency gains over CoT baselines, beyond reductions in attended tokens and theoretical parallelism?

What causes the remaining accuracy gap between CRM and CoT? How do you validate that generated computation graphs preserve correct reasoning dependencies despite syntax errors, runtime failures, and truncated traces?

1 comment

We thank the reviewer for the thoughtful feedback.

Practical efficiency benefits are not sufficiently demonstrated. The paper reports reduced attention computation and theoretical parallelism, but does not establish corresponding end-to-end latency or throughput improvements.

Can you provide end-to-end inference latency, throughput, and memory measurements demonstrating that CRM delivers practical efficiency gains over CoT baselines, beyond reductions in attended tokens and theoretical parallelism?

See Inference FLOPs, Wall-Clock Speedup Results, and Peak Resident KV Cache Tokens and Memory in the overview comment.

Accuracy also remains 1.2–6.7 percentage points below the CoT baseline after preference optimization.

See Significance: Generality in the overview comment.

syntax or runtime failures can truncate reasoning traces

Similar to LLM code generation, syntax and runtime failures can be addressed with additional training and with constrained decoding using methods such as SynCode[1].

Evaluation lacks sufficient ablation studies to isolate the contributions of individual components

See Feature Ablation Results in the overview comment.

The evaluation focuses on a single 4B model and a 4096-token context, so scalability and generalizability is unknown.

We have updated the paper with results using 8192-token context length, which maintains the task-performance trends previously observed at 4096. Our work is the first to present a system that performs general computational reasoning in one model, and our evaluation demonstrates empirically that CRM reduces mean attended tokens and enables parallelism. These savings come from the semantics of CRM Assembly implemented through attention masks, which is present in all transformer models.

What causes the remaining accuracy gap between CRM and CoT?

Figures 15 and 23 in the revised draft show the breakdown of the failure reasons for CRM and CRM-RL: 10.4-31.0% of CRM runs and 0.2-4.4% of CRM-RL runs failed due to incorrect syntax. Similar to LLM code generation, syntax errors can be addressed with additional training and constrained decoding. 16-29% of CRM runs and 13-32% of CRM-RL runs failed due to reasoning, which can be addressed with better quality training data annotations and additional training.

How do you validate that generated computation graphs preserve correct reasoning dependencies despite syntax errors, runtime failures, and truncated traces?

The CRM runtime aborts generation at syntax and runtime errors. Aborted and truncated traces are scored as-is using the official scorers of the benchmarks to extract an answer to score. Our evaluation methodology does not validate the traces for any other properties.

[1] Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. Syncode: LLM generation with grammar augmentation. arXiv preprint arXiv:2403.01632, 2024.

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

The paper proposes CRM Assembly, a CoT language based of special tokens that enable parallel execution of reusable functions, limiting attention to relevant parts of the reasoning trace. This is shown to reduce attention requirements by up to 50% at the cost of increased KV cache and reduced accuracy on tasks. On evaluation, standard benchmarks such as GSM8K, AIME 2025, MMLU-Pro, and GPQA-Diamond are used.

Critical strengths

The idea is clear and quite appealing to me. The CRM language unifies different aspects such as dependency, concurrency, function calling, etc. cleanly in a single CoT trace. It required some strong engineering to make this work along with all the KV cache optimizations. On long-reasoning benchmarks, CRM-RL attends to substantially fewer tokens than CoT-RL, which shows the key benefit of such an approach.

Critical weaknesses

While the idea is refreshing, the results are negative/discouraging at this point. On accuracy of comparable methods (non-RL CRM vs CoT or RL-CRM vs RL-CoT), the accuracy of the approach is lower than the baselines. Along with increased memory requirements due to KV caching recomputation, it's unclear why this tradeoff (efficiency vs both memory and accuracy) might be interesting. If both accuracy and efficiency could be improved together, then this has potential to be a solid research contribution in future.

The parallelism claim is mostly theoretical and not realized. There are no wall-clock time or throughput reported anywhere. This significantly weakens the claim of parallelism which is not empirically demonstrated.

There are many typos and incomplete sentences in the draft that the authors should carefully review in final version.

Questions for authors

NA

1 comment

We thank the reviewer for the thoughtful feedback.

On accuracy of comparable methods (non-RL CRM vs CoT or RL-CRM vs RL-CoT), the accuracy of the approach is lower than the baselines. Along with increased memory requirements due to KV caching recomputation, it's unclear why this tradeoff (efficiency vs both memory and accuracy) might be interesting. If both accuracy and efficiency could be improved together, then this has potential to be a solid research contribution in future.

See Significance: Generality in the overview comment.

The parallelism claim is mostly theoretical and not realized. There are no wall-clock time or throughput reported anywhere. This significantly weakens the claim of parallelism which is not empirically demonstrated.

See Wall-Clock Speedup Results in the overview comment.

There are many typos and incomplete sentences in the draft that the authors should carefully review in final version.

We thank the reviewer for pointing this out. We have corrected these mistakes in the revised version of the paper and will carefully review the final version.

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

CRM lets a model organize its reasoning with variables, scopes, and functions. These operations control which earlier tokens the model can attend to. The authors use a trie to cache different versions of the context and train the model on annotated reasoning traces, followed by preference optimization. On four benchmarks, CRM reduces the number of attended tokens but loses accuracy. The paper also estimates how much of the reasoning could run in parallel.

Critical strengths

S1. Letting the model choose what to keep in context is an interesting direction. The scope and load operations give this idea a concrete implementation.

S2. The authors handle KV recomputation when the visible context changes and report its costs in the appendix. The FLOPs, cache, and failure statistics are useful for assessing the method.

Critical weaknesses

W1. My main concern is that the method does not seem to pay off in overall cost and accuracy. Comparing CRM-RL with CoT-RL, which also receives preference optimization, Tables 6 and 10 show 71.1% more FLOPs on GSM8K and 21.3% more on MMLU-Pro, with pass@3 lower by 3.7 and 5.0 points. On AIME 2025 and GPQA-Diamond, it saves only 2.4% and 0.4% of FLOPs while losing 10.0 and 9.6 points. The reduction in attended tokens is real, but these results leave me unconvinced that CRM is more efficient in practice. Parallel execution could help, but it has not been implemented, and the theoretical parallelism after preference optimization is only 1.03-1.08x (Table 11).

W2. The current comparison changes both the training traces and the execution mechanism. CRM uses annotated traces that can include rewritten reasoning, while CoT uses the original traces. This makes it hard to tell what comes from the data and what comes from the attention control. One useful check would be an SFT baseline on the same annotated traces with ordinary causal attention, compared with CRM before preference optimization. This would require a separate training run; simply changing the mask of the trained CRM model at inference would not be a fair test. I would find even a limited comparison informative, without requiring a new skill/tool system or a full set of component ablations.

Questions for authors

Q1. How do you interpret the cost and accuracy comparison between CRM-RL and CoT-RL in Tables 6 and 10? If timing measurements are available for the current sequential implementation, do they show an advantage?

Q2. Is there existing evidence that separates the effect of the annotated data from attention control? A limited SFT comparison on the same annotated traces with ordinary causal attention would help; it need not include another round of preference optimization.

Q3. Can the generated traces help explain why theoretical parallelism falls to 1.03-1.08x after preference optimization? For example, does the model generate fewer independent branches?

1 comment

We thank the reviewer for the thoughtful feedback.

My main concern is that the method does not seem to pay off in overall cost and accuracy. [...] The reduction in attended tokens is real, but these results leave me unconvinced that CRM is more efficient in practice.

See Significance: Generality and Inference FLOPs in the overview comment.

One useful check would be an SFT baseline on the same annotated traces with ordinary causal attention, compared with CRM before preference optimization. Q2. Is there existing evidence that separates the effect of the annotated data from attention control? A limited SFT comparison on the same annotated traces with ordinary causal attention would help; it need not include another round of preference optimization.

See Feature Ablation Results in the overview comment.

Parallel execution could help, but it has not been implemented [...] If timing measurements are available for the current sequential implementation, do they show an advantage?

See Wall-Clock Speedup Results in the overview comment.

How do you interpret the cost and accuracy comparison between CRM-RL and CoT-RL in Tables 6 and 10? Q3 Can the generated traces help explain why theoretical parallelism falls to 1.03-1.08x after preference optimization? For example, does the model generate fewer independent branches

See Preference Optimization Results in the overview comment.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Overview Comment

We thank the reviewers for the thoughtful feedback and comments. We address in this comment the common concerns raised by reviewers. We also summarize the changes made to the revised draft.

Significance: Generality (Reviewer UyMh, Reviewer JpTS, Reviewer BVsH). The primary significance of the Computational Reasoning Machine is that it enables general computational reasoning capabilities in one model. Existing computational reasoning methods each target an individual computational reasoning capability. For example, Memento[1] enables a model to perform context management and Pasta[2] enables a model to perform parallel decoding. However neither jointly enables both capabilities. In contrast, the Computational Reasoning Machine unifies computational reasoning capabilities into a single execution model and language (CRM Assembly) that enables multiple different capabilities to be incorporated at the same time.

To demonstrate this, we have updated the paper with evaluation results of Memento[1] and Pasta-SFT[2] methodologies as baselines. Memento iteratively masks sections of reasoning after generating a summary. Memento reduces mean attended tokens by 39.7-59.2% from CoT and exposes no decoding parallelism.

Pasta-SFT annotates its generations with asynchronous decoding primitives to orchestrate parallel decoding. Pasta-SFT exposes 1.12-1.37x mean theoretical parallelism. CRM reduces both mean attended tokens by 39.3-74.9% and exposes 1.17-1.37x mean theoretical parallelism, matching the savings of these other techniques.

Both of these baselines have little impact on the accuracy. In contrast, the cost of CRM's generality is accuracy and total resident KV cache size per response. However, our results on preference optimization point in the direction of future work to improve the accuracy of CRM responses.

Preference Optimization Results (Reviewer UyMh, Reviewer BVsH). The accuracy and memory costs of CRM are the cost of generality: CRM learns a single language that captures the computational reasoning capabilities that each baseline targets alone. The accuracy drop is due to a lack of consistency, not capability: Figure 16 in the revised draft shows that CRM solves the problems that CoT solves on AIME 2025, but it needs 10 samples to match the pass@1 accuracy of CoT.

Following the evaluation methodology of Memento[1] and Pasta[2] to compare the RL-trained model to the SFT baseline, we observe that preference optimization with an accuracy objective narrows the pass@1 accuracy gap between CRM and CoT from 14.7-25.3pp to 4.7-10.9pp. However, it reduces the theoretical parallelism of CRM from 1.17-1.37x to 1.01-1.09x, because the objective does not account for parallelism. The resulting model generates traces that mostly execute one step at a time with a load primitive in between, with no function call or nested scope.

Pasta[2] demonstrated that using BoNBoN with a mixed objective incorporating both quality and theoretical parallelism jointly optimizes response quality and speedup. Similar methodologies can apply to CRM to jointly improve accuracy, attended tokens, and theoretical parallelism. Our work focuses on presenting the first system capable of unified and general computational reasoning, so a deep exploration of different, more sophisticated training methodologies is beyond the scope of this work. To streamline the narrative, we have moved the preference optimization results and future work discussion to Appendix E.5 of the revised draft.

Inference FLOPs (Reviewer UyMh, Reviewer BVsH). Inference FLOPs are dominated by dense layer computations at short context lengths (< 32k) and by attention compute at long context lengths (>= 32k), as the FLOPs per token of Qwen3-4B-Instruct show:

Context lengthDense GFLOP / tokenAttention GFLOP / tokenAttention share
1k8.040.303.6%
4k8.041.2113.1%
8k8.042.4223.1%
16k8.044.8337.5%
32k8.049.6654.6%
64k8.0419.3370.6%
128k8.0438.6682.8%
256k8.0477.3190.6%

At 4k context length, attention is only 13.1% of the compute of decoding a token under full causal attention. Due to compute constraints, we are only able to train models for up to 8k context length, which increases the attention share to 23.1%. We have updated the revised draft with the results of the models trained at 8k context length.

The updated Table 12 and Figure 14 breaks down the inference FLOPs by computation type. CRM reduces inference FLOPs by 14.1-16.5% compared to CoT on AIME and GPQA-Diamond. In these benchmarks, the reasoning traces are longer, so the attention savings exceed the recomputation cost. CRM increases the inference FLOPs on GSM8K because CRM produced 24.8% longer responses than CoT on this short-response task. CRM also increases the inference FLOPs on MMLU-Pro because its responses are short. The recomputation cost of switching graph views exceeds the attention compute savings. An interesting direction for future work is to explore how alternative runtime implementations and optimizations affect this tradeoff between attention savings and recomputation cost.

Wall-Clock Speedup Results (Reviewer UyMh, Reviewer JpTS, Reviewer BVsH). We have implemented parallel decoding and added the wall-clock latency results to the revised draft (Figure 5, Table 15, and Figure 11).

Under sequential decoding, CRM achieves 1.09-1.12x wall-clock speedup over CoT on AIME 2025 and GPQA-Diamond, and 0.64-0.84x on GSM8K and MMLU-Pro. CRM is slower on GSM8K and MMLU-Pro due to the recomputation overhead and longer generations compared to CoT.

Under parallel decoding, CRM achieves 1.01-1.29x wall-clock speedup over CoT on AIME 2025, MMLU-Pro and GPQA-Diamond, comparable to the 1.07-1.16x of Pasta-SFT. On GSM8K, CRM is slower than CoT (0.78x) while Pasta-SFT achieves 1.13x speedup. This is because CRM generated longer responses than both CoT and Pasta-SFT and exhibits less theoretical parallelism than Pasta-SFT on GSM8K. For MMLU-Pro, parallel decoding recoups CRM's recomputation overhead observed when decoded sequentially.

Feature Ablation Results (Reviewer UyMh, Reviewer BVsH). We have added CRM Full Attention (base model trained with CRM traces under full causal attention) as an ablation. CRM reduces the mean attended tokens by 74.8-77.5% against CRM Full Attention. CRM Full Attention achieves 1.8-20.0pp higher pass@3 accuracy than CRM on AIME 2025, MMLU-Pro, and GPQA-Diamond, and 0.7pp lower pass@3 accuracy on GSM8K. This shows that some of the lost accuracy is due to incorrect primitive usages. Increasing the quality of training data and the training compute could address this.

We have added the results of ablating features of CRM Assembly to Appendix E.6. We finetune five variants of CRM that each keep a subset of the CRM Assembly primitives. We finetune them on the same training problems and with the same hyperparameters as CRM. The first variant keeps only the step and value primitives, so a step's work can never be attended to. It attends 44.4-73.3% fewer tokens than CoT. With the load primitive added, the variant attends 37.2-69.5% fewer tokens than CoT. With scopes (the push and pop primitives) also added, the variant attends 52.8-81.6% fewer tokens than CoT. None of these three variants exposes theoretical parallelism. Adding deferred execution (the work primitive) exposes 1.14-1.26x theoretical parallelism. Adding functions without deferred execution exposes 1.19-1.45x theoretical parallelism, and CRM with every primitive exposes 1.17-1.37x.

Peak Resident KV Cache Tokens and Memory (Reviewer BVsH). We have updated the paper with peak resident KV cache tokens and peak KV cache memory per response instead of mean resident KV tokens per token. Peak resident KV cache tokens measure the memory that must be reserved to decode a response. The submitted draft reported that at 4k context length, CRM increases mean resident KV tokens per token by 2.6-40% from CoT. The per-token metric divides the KV cache over a response by the response length, so it does not show how much memory a response needs.

Peak resident KV cache tokens measure this memory pressure directly. At 4k context length, CRM increases peak resident KV cache tokens by 1.2-15.1% from CoT on GSM8K and MMLU-Pro. On AIME 2025 and GPQA-Diamond, it decreases peak resident KV cache tokens by 4.4-13.1%. This reflects the fact CRM generated shorter traces than CoT on AIME 2025 and GPQA-Diamond, enough to offset the recomputation cost.

At 8k context length, CRM increases peak resident KV cache tokens from CoT by 3.9-59.6% on GSM8K, AIME 2025, and MMLU-Pro. It decreases them by 1.6% on GPQA-Diamond. The translates directly to KV cache memory: CRM increases the peak KV cache memory by 0.04-0.10 GB from CoT on GSM8K, AIME, and MMLU-Pro. It decreases peak KV cache memory by 0.01 GB on GPQA-Diamond. In exchange, CRM reduces the attended tokens per response by 39.3-74.9% from CoT.

Mean Attended Tokens Measure. We have updated the paper with mean attended tokens per response as opposed to the previous mean attended tokens per token. Mean attended tokens per response encapsulates both attention cost as well as overall response length. The submitted draft reported that CRM reduces mean attended tokens per token by 39.0-60.8% from CoT at 4k context length. At 8k context length, CRM reduces mean attended tokens per token by 44.7-76.6%. It reduces mean attended tokens per response by 39.3-74.9% from CoT. The reduction from CoT in the per-response measure is smaller than the per-token measure on GSM8K, because CRM generates longer responses than CoT.

Writing Changes. We addressed typos and made minor phrasing adjustments. We combined Figure 1 and Figure 2 into a single figure as some aspects of the diagrams were redundant.

[1] Vasilis Kontonis, Yuchen Zeng, Shivam Garg, Lingjiao Chen, Hao Tang, Ziyan Wang, Ahmed Hassan Awadallah, Eric Horvitz, John Langford, and Dimitris Papailiopoulos. Memento: Teaching LLMs to manage their context. In Conference on Language Modeling, 2026.

[2] Tian Jin, Ellie Y. Cheng, Zack Ankner, Nikunj Saunshi, Blake M Elias, Amir Yazdanbakhsh, Jonathan Ragan-Kelley, Suvinay Subramanian, and Michael Carbin. Learning to keep a promise: Scaling language model decoding parallelism with learned asynchronous decoding. In International Conference on Machine Learning, 2025.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.