Message Passing Enables Efficient Reasoning

Source: arXiv:2607.01077 · Published 2026-07-01 · By Xuecheng Liu, Daman Arora, Gokul Swamy, Andrea Zanette

TL;DR

This paper addresses the efficiency and scalability limitations of current large language model (LLM) reasoning paradigms at inference time, particularly the bottleneck caused by long chain-of-thought (CoT) sequences generated autoregressively. Prior approaches have either employed sequential CoT inference or parallel fork-join (FJ) models, but both suffer from inefficiencies related to context growth and communication overhead. The authors introduce Message Passing Language Models (MPLMs), a novel framework where multiple persistent LLM threads directly communicate via explicit send and receive primitives to coordinate reasoning. This fine-grained message passing avoids redundant context sharing and enables preemption, allowing threads to terminate early when partial solutions suffice. By leveraging sparse, local communication among cooperating worker threads maintaining persistent state, MPLMs achieve significantly better asymptotic scaling in context length and inference latency compared to serial CoT and fork-join methods. The approach is instantiated and empirically evaluated on Sudoku puzzles and 3-SAT boolean satisfiability problems, showing MPLMs scale to much larger Sudoku grids (up to 25x25) that previous methods and advanced reasoning models fail to solve reliably. It also demonstrates improved efficiency on 3-SAT through preemption of unpromising branches. Finally, experiments with prompted large pretrained models on LongBench-v2 long-context question answering reveal that MPLM inference protocols can be followed without additional training, achieving competitive accuracy and roughly 2x latency reduction versus state-of-the-art fork-join baselines. Overall, the work offers a principled message-passing reasoning framework that more efficiently uses inference compute for complex multi-threaded LLM reasoning tasks.

Key findings

• MPLMs reduce maximum context length asymptotically to O(T k M) versus O(T N M) for fork-join and O(T N k M) for serial CoT, where T=iterations, N=#workers, k=#neighbors, and M=message size.
• On Sudoku, MPLM scales with problem size exponent α ≈1.2 for sequential tokens and α ≈1.1 for maximum context, significantly better than serial and FJ with α ≈1.8.
• MPLM solves 72% of 25x25 Sudoku puzzles after training on 1000 puzzles, while DeepSeek-R1 and GPT-5 Pro struggle (GPT-5 Pro solves 20% of 25x25 puzzles).
• In 3-SAT, MPLM achieves 1.6x to 3.5x latency speedups over fork-join baselines by preempting unpromising search branches and terminating early.
• On LongBench-v2 long-context QA, MPLM improves Qwen3-30B-A3B accuracy from 29.9% to 37.8% and reduces latency from 105.7s to 61.3s (1.7x speedup) compared to Recursive Language Models (RLM).
• On Qwen3.6-35B-A3B, MPLM matches RLM accuracy (46.5% vs 46.7%) but halves latency (102.2s vs 223.5s) on LongBench-v2 tasks.
• Persistent local state and selective point-to-point communication in MPLM enable iterative evidence refinement without reloading context, unlike transient fork-join workers.
• MPLM inference logic supports robust spawning, messaging, waiting, and preemption as explicit directives interpretable by the controlling scheduler.

Threat model

n/a — The paper focuses on computational efficiency and scalability of multi-threaded LLM reasoning rather than adversarial or security threat analysis. The assumed environment is benign inference-time execution where no malicious interference or adversary attempts to disrupt message passing.

Methodology — deep read

The authors first define the threat model as standard inference-time reasoning tasks on deterministic structured problems (Sudoku, 3-SAT) where an adversary is not considered; this is a computational efficiency and scalability study rather than adversarial security.

Data provenance involves generating structured datasets: 1000 training and 200 evaluation Sudoku puzzles at multiple sizes (4x4 to 25x25), designed to be solvable by naked-singles technique; 3-SAT instances generated with variable counts ranging from 8 to 20.

For architecture, MPLM decomposes LLM reasoning into multiple persistent concurrent threads, each corresponding to a subtask (e.g., a cell in Sudoku, or a branch in 3-SAT search). Threads run on a batched inference engine and use four atomic execution directives generated by the model itself: <spawn> to create new threads with distinct contexts; <send> to transmit messages to other threads; <recv> to wait for messages from specified peers; and <stop> to terminate threads. This implements explicit point-to-point message passing in analogy to distributed computing protocols like MPI.

Training involves supervised fine-tuning Qwen3-0.6B-Base LLM on generated CoT traces simulating message-passing reasoning steps. For Sudoku, simulated naked-singles executions produce trajectory data showing message patterns and dependency structures. For 3-SAT, trajectories are generated from distributed DPLL algorithm simulations including asynchronous preemption. Each training run takes under 48 hours on Nvidia H100 GPUs.

Evaluation compares three reasoning paradigms: Serial CoT (fully sequential autoregressive), Fork-Join (parallel threads spawned each iteration but no direct communication between workers), and MPLM. Metrics include puzzle accuracy, wall-clock inference latency, maximum context token consumption, and sequential token count (causally dependent tokens). Baselines include serial and fork-join trained on the same data, as well as commercial reasoning models DeepSeek-R1 and GPT-5 Pro evaluated via API (without external tools).

Scaling experiments characterize how inference latency and max context grow with Sudoku puzzle size and 3-SAT variable count. For LongBench-v2 long-context QA, the authors prompt large pretrained models Qwen3-30B-A3B and Qwen3.6-35B-A3B to emit MPLM directives without fine-tuning and compare performance to Recursive Language Models (RLM), a state-of-the-art fork-join approach equipped with specialized tools.

The inference controller coordinates parallel thread decoding, interprets special tokens as execution directives, manages blocking on receives using wait-for-all or wait-for-any variants, delivers messages, and supports thread preemption to cancel unneeded computations.

The experimental design isolates structured reasoning benefits from confounders by using idealized tasks with clear sparse dependencies, and measuring both theoretical and empirical scaling behaviors. Reproducible code and training details are available as per appendix sections. However, full model weights and datasets are not public at this time.

One concrete example end-to-end: In Sudoku, the parent thread spawns N⁴ worker threads corresponding to each cell. Each worker computes possible values, sends assignment messages to neighbors when uniquely solved, or generates <recv> waits to gather neighbor updates. This message passing iterates until convergence or timeout, after which the parent collates cell assignments to produce the final puzzle solution.

Technical innovations

• Introduction of an explicit message-passing framework (MPLM) for LLM reasoning where threads maintain persistent local context and communicate via send/recv directives.
• Analytical proof of context length scaling advantages: MPLM context scales as O(T k M) while fork-join and serial CoT scale as O(T N M) and O(T N k M) respectively, with potential orders-of-magnitude savings in sparse communication regimes.
• Implementation of thread preemption enabled by asynchronous messaging allowing early termination of unpromising branches in search-based reasoning (e.g., 3-SAT), improving latency.
• Demonstration that large pretrained LLMs can follow MPLM directives at inference time through prompting, enabling message-passing coordination without fine-tuning.
• Integration of message-passing primitives into LLM token streams as explicit control instructions, bridging distributed systems concepts with neural generative models.

Datasets

• Sudoku puzzles — 1000 train + 200 eval per size tier (4x4, 9x9, 16x16, 25x25) — synthetically generated solvable puzzles
• 3-SAT puzzles — 100 test problems per variable count (8-20 variables) — synthetically generated satisfiability instances
• LongBench-v2 — 503 multiple-choice questions with long contexts (8K to 2M words) — public benchmark for long-context QA

Baselines vs proposed

• Serial CoT on Sudoku 25x25: infeasible due to context and compute constraints vs MPLM solves 72% successfully
• Fork-Join on Sudoku 9x9 latency: 59.56s vs MPLM 14.94s (4x speedup) on same model backbone
• DeepSeek-R1 on Sudoku 9x9 accuracy: 90% vs MPLM 100%, latency 765.98s vs MPLM 14.94s
• GPT-5 Pro on Sudoku 25x25 accuracy: 20% vs MPLM 72%
• 3-SAT average latency for 20 variable problems: MPLM 10-35% faster than Fork-Join baseline (up to 3.5x in unbalanced cases)
• LongBench-v2 Qwen3-30B-A3B accuracy MPLM/RLM: 37.8% / 29.7%, latency MPLM/RLM: 61.3s / 105.7s
• LongBench-v2 Qwen3.6-35B-A3B accuracy MPLM/RLM: 46.5% / 46.7%, latency MPLM/RLM: 102.2s / 223.5s

Limitations

• Training experiments conducted on relatively small model (Qwen3-0.6B) rather than state-of-the-art multi-billion parameter models; unclear scalability.
• Evaluation on Sudoku and 3-SAT focuses on narrow classes of structured reasoning tasks; may not generalize to less structured or open-ended problems.
• Prompted evaluation on large pretrained models in LongBench-v2 lacks fine-tuning, potentially underutilizing MPLM benefits.
• Communication primitives introduce additional scheduling complexity and overhead not quantified in all settings.
• No explicit adversarial security or robustness evaluation; MPLM message passing could be vulnerable to adversarial message corruption or poisoning.
• Code and dataset release pending; reproducibility for large-scale experiments may be limited currently.

Open questions / follow-ons

• How do MPLMs scale with larger model sizes (tens or hundreds of billions of parameters) and more complex reasoning workloads in the wild?
• What are effective training regimes, objectives, or RL methods to optimize LLMs for emergent communication protocols in MPLMs beyond supervised fine-tuning?
• Can MPLM concepts extend to open-ended or ambiguous tasks requiring learned coordination rather than structured algorithmic workloads?
• What are the security implications and robustness concerns if message passing is exploited by attackers during distributed inference?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, this paper’s insights into efficient message-passing coordination among parallel LLM threads can inspire novel approaches to crafting puzzles or challenges that inherently require distributed reasoning. In particular, MPLMs demonstrate how large-scale reasoning may be decomposed into loosely coupled subtasks requiring careful inter-thread communication, suggesting CAPTCHAs or bot-detection challenges could leverage analogous structural complexity that resists naive parallel solution. Also, the demonstrated latency and context-efficiency gains imply such message-passing frameworks might enable faster, more scalable evaluation of complex puzzles on server side at inference time, improving real-time user experience without sacrificing difficulty. Finally, the asynchronous preemption features showcased in MPLM on SAT solving highlight possibilities for early detection of bot strategies, since spurious or inefficient message passing could signal non-human activity patterns. However, practical deployment would require further engineering to balance efficiency gains against implementation complexity.

Cite

@article{arxiv2607_01077,
  title={ Message Passing Enables Efficient Reasoning },
  author={ Xuecheng Liu and Daman Arora and Gokul Swamy and Andrea Zanette },
  journal={arXiv preprint arXiv:2607.01077},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.01077}
}

Read the full paper

• arXiv:2607.01077 (abstract)
• arXiv:2607.01077 (PDF)