Message Passing Enables Efficient Reasoning

This paper introduces Message Passing Language Models (MPLMs), a novel framework designed to enable efficient reasoning in large language models by allowing threads to communicate directly via lightweight send and receive primitives. This approach addresses the computational bottleneck associated with generating long chains-of-thought (CoTs) in parallel settings, offering reduced communication costs and preemption capabilities that improve scalability compared to traditional fork-join methods.

How it works

MPLMs decompose reasoning into persistent, semi-independent threads that coordinate via explicit point-to-point message passing to enable more efficient use of test-time compute and improved scalability as problem complexity grows. These threads are indexed by an ID and associated with distinct prompts and contexts, allowing for concurrently decoded through batched inference rather than the sequential generation characteristic of standard CoT.

The framework is founded on a set of four fundamental execution control directives generated by the model:

1. Spawn: Requires generating a string of the format prompt , which generates N new LLM threads.

2. Send: Generates a string of the form message , which sends the message to specified threads.

3. Receive: Generates a string like ", which causes the thread to wait for messages from threads id1, id2….".

4. Stop: Triggered by generating a string of the form ", which results in the execution of an LLM thread being permanently stopped by the inference engine".

Key Mechanisms for Efficiency

MPLMs achieve efficiency through two primary mechanisms:

1. Reduced communication costs, achieved by avoiding redundant context sharing and utilizing explicit point-to-point message passing. This contrasts with prior paradigms where all coordination is centralized and context for workers is transient, which introduces communication bottlenecks and implicit serialization.

2. Preemption, which allows threads to terminate early based on partial information from their peers. This is supported by the runtime maintaining spawn tree and thread identities are globally addressable, so messages can be sent not only between siblings but also across different levels of the threads.

Empirical Validation on Structured Tasks

The framework was instantiated on two structured reasoning testbeds: Sudoku and 3-SAT puzzles.

(Sudoku)

MPLMs require an asymptotically smaller context than both serial CoT and parallel FJ for Sudoku, scaling to 25 × 25 Sudoku grids that remain out of reach even for frontier reasoning models such as GPT-5 Pro. The analysis shows that MPLMs exhibit significantly lower scaling exponents for both sequential tokens and maximum context required compared to Serial or Fork-Join (FJ) paradigms.

(3-SAT)

The capability of preemption allows for the termination of unpromising branches, resulting in improved efficiency, particularly when the search tree is highly unbalanced. For 3-SAT, MPLMs are faster than other baselines for all sizes of the problem, and their latency advantage is greatest when the SAT search tree is highly unbalanced.

Long Context Reasoning Performance

When applied to LongBench-v2, MPLMs demonstrate that sufficiently capable models can already follow message-passing directives and make use of persistent point-to-point communication at inference time. This approach decomposes context into chunks, where workers maintain persistent local state and communicate via a parent thread that performs selective queries to target agents based on aggregated summaries. The results show MPLM improves average accuracy from 29.7% to 37.8% on Qwen3-30B-A3B while reducing average latency by approximately 1.7×.

Theoretical Context Analysis

The theoretical analysis formalizes the efficiency gains, showing that for an N2 × N2 Sudoku, the maximum context required is C MPLM max = O(N4 + T · N2). This is superior to FJ's C FJ = O(T · N4) and Serial CoT's C Serial = O(T N kM), providing a theoretical justification for the context efficiency of MPLMs. Furthermore, the number of sequential tokens for MPLMs is SMPLM = O(N4 + T N2), which is asymptotically better than SFJ = O(T · (N4 + N2)).

Conclusion and Future Directions

In summary, MPLMs enable LLMs to dynamically create new threads and communicate through point-to-point messages, breaking down complex tasks into a decentralized fashion that resembles how an actual human organization might function. While the framework requires workers to determine communication needs, future work aims to generate parallel message-passing CoT data for training stronger MPLM policies beyond predefined scaffolds to enable generalization to less structured domains like agentic reasoning and code generation.

REFERENCES

Pranjal Aggarwal and Sean Welleck. L1: Controlling how long a reasoning model thinks with reinforcement learning. In Second Conference on Language Modeling, 2025. URL https://openreview.net/forum?id=4jdIxXBNve.

Milad Aghajohari, Kamran Chitsaz, Amirhossein Kazemnejad, Sarath Chandar, Alessandro Sordoni, Aaron Courville, and Siva Reddy. The markovian thinker: Architecture-agnostic linear scaling of reasoning, 2025. URL https://arxiv.org/abs/2510.06557.

Daman Arora and Andrea Zanette. Training language models to reason efficiently. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL https://openreview.net/forum?id=AiZxn84Wdo.

Yushi Bai, Shangqing Tu, Jiajie Zhang, Hao Peng, Xiaozhi Wang, Xin Lv, Shulin Cao, Jiazheng Xu, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li. Longbench v2: Towards deeper understanding and reasoning on realistic long-context multitasks. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics, 2025. URL https://aclanthology.org/2025.acl-long.183.

Keyu Chen, Zhifeng Shen, Daohai Yu, Haoqian Wu, Wei Wen, Jianfeng He, Ruizhi Qiao, and Xing Sun. Aspd: Unlocking adaptive serial-parallel decoding by exploring intrinsic parallelism in llms, 2025. URL https://arxiv.org/abs/2508.08895.

Weize Chen, Yusheng Su, Jingwei Zuo, Cheng Yang, Chenfei Yuan, Chi-Min Chan, Heyang Yu, Yaxi Lu, Yi-Hsin Hung, Chen Qian, Yujia Qin, Xin Cong, Ruobing Xie. Agentverse: Facilitating multi-agent collaboration and exploring emergent behaviors. In The Twelfth International Conference on Learning Representations, 2024.

1. Bold header: Reduced Context Requirements for Complex Problems

This improvement allows models to tackle problems previously unreachable, as demonstrated by showing that MPLMs require an asymptotically smaller context than both serial CoT and parallel FJ for Sudoku puzzles, enabling them to scale to 25 × 25 Sudoku grids that remain out of reach even for frontier reasoning models such as GPT-5 Pro.

2. Bold header: Efficient Search Termination via Preemption

The system can improve efficiency on search tasks like 3-SAT by implementing preemption, which allows the system to terminate unpromising branches early, as the paper states that the capability of preemption allows termination of unpromising branches, which results in improved efficiency.

3. Bold header: Dynamic Task Decomposition via Message Passing

The system can decompose reasoning into persistent, semi-independent threads that coordinate via explicit point-to-point message passing, allowing a single model to dynamically decide when, with whom, and what to communicate using its own learned reasoning capabilities.

4. Bold header: Scalable Long Context Reasoning

By utilizing the MPLM framework for LongBench-v2, the system can perform iterative evidence aggregation by decomposing long contexts into chunks and using a targeted query-routing loop that sends targeted messages only to those workers relevant to current uncertainty.

5. Bold header: Improved Inference Latency on Structured Tasks

The system shows tangible speedups compared to baselines, with MPLM achieving better scaling exponents for sequential tokens and maximum context, resulting in a reduction in latency; for instance, on 9 × 9 Sudoku puzzles, the average latency dropped from 16.99s (Serial) to 16.68s (MPLM).

6. Bold header: Unbounded Reasoning Through Respawning

The framework enables respawning, where a worker can construct a compact inheritance payload that summarizes the minimal information required for future progress, which prevents context from becoming unbounded and leads to unbounded reasoning by allowing threads to run for arbitrarily many iterations without exceeding the model’s context window.

7. Bold header: Adaptive Synchronization Schemes

The system can utilize different synchronization primitives, such as wait-for-all and wait-for-any implementations, allowing it to dynamically choose the most efficient communication strategy based on the specific characteristics of a worker's latency, as observed in Sudoku instances where wait-for-any is faster because it doesn’t have to wait for the slowest worker.

While inference-time scaling has improved the reasoning abilities of large language models (LLMs), the need to generate long chains-of-thought (CoTs) is a computational bottleneck. Thus, in contrast to sequential scaling methods like CoT, recent parallel scaling techniques instead use fork and join (FJ) primitives to divide work across multiple LLM threads. However, in the fork-join paradigm, threads are typically transient and do not communicate pointwise with one another which limits scalability. To tackle this, we introduce Message Passing Language Models (MPLMs), a framework for LLM reasoning in which threads communicate directly via lightweight send and receive primitives. MPLMs enable efficient scaling through two key mechanisms: (1) reduced communication costs, achieved by avoiding redundant context sharing, and (2) preemption, which allows threads to terminate early based on partial information from their peers. We demonstrate the promise of MPLMs on 3 classes of tasks. First, on Sudoku puzzles, we show that MPLMs require an asymptotically smaller context than both serial CoT and parallel FJ. We then fine-tune a single model to solve 25 x 25 puzzles that remain challenging for standard CoT and FJ approaches, as well as frontier reasoning models without tools. Second, on 3-SAT puzzles, the capability of preemption allows termination of unpromising branches, which results in improved efficiency. Finally, we show that appropriately prompted large pre-trained models follow the MPLM protocol, achieving competitive results on long-context question answering relative to popular fork-join approaches.