ParaTempo: Efficient Parallel Reasoning via Temporal Confidence
Xuteng Zhang, Wenhao Zeng, Xiaodong Gu, Chao Hu, Haotian Lin, Yuling Shi, Min Wang, Beijun Shen
cs.AI
2026-08-17
ParaTempo prunes, retires, and forks parallel branches from temporally aggregated answer probes, cutting latency 21.8–32.2% and tokens 18.1–30.3% vs self-consistency.
Parallel reasoning samples multiple solution traces and votes. Accuracy goes up. Cost scales with both the number of branches and how long each one thinks. The default is a fixed budget: run every chain to completion, then majority-vote. Chains that already settled keep emitting leftover tokens. Weak chains keep the GPU busy with no evidence they will help.
Online controllers exist, but their signals are a poor match. Final-answer consensus is trustworthy and late. Token entropy and perplexity track local next-token uncertainty, which can stay low while the answer hypothesis is still flipping. A single intermediate probe can fire early, but mid-trace reasoning often leans on a wrong guess for a few hundred tokens, so the probe jitters. The missing object is a quantity aligned with the answer space, aggregated over time, and updated on each branch without a global barrier.
ParaTempo, from Shanghai Jiao Tong University and the University of Pennsylvania, is a training-free asynchronous controller. Every 500 generated tokens, an active branch is probed: an answer-forcing suffix such as </think> Final answer: is appended to the current prefix, and the top-20 candidate answer tokens are turned into a normalized distribution over answer buckets. The last W=7 probe distributions are averaged. Temporal confidence is exp(−H(g)) of that average. Near 1 means recent probes pile onto one answer; lower values mean several answers still compete.
That single number drives four actions.
Generation stops globally when the confidence-weighted vote for the leading answer is at least 0.50 times the number of voting branches. Branches never wait for each other at the same depth. Default K=16, vLLM on one A100 80GB, four-run averages.
Benchmarks are AIME 2026, HMMT November 2025, HMMT February 2026, and GPQA Diamond, on Qwen3.5-35B-A3B and GPT-OSS-20B.
On Qwen, ParaTempo averages 71.1% accuracy against 72.2% for self-consistency (SC@16), a 1.1-point gap, with 21.8% lower latency and 30.3% fewer tokens. Against Parallel-Probe, accuracy is 3.9 points higher and latency 10.6% lower. On GPT-OSS the same pattern holds versus Parallel-Probe (+3.8 points); versus SC, latency drops 32.2% and tokens 18.1%.
| Model | Bench | ParaTempo acc / lat | SC acc / lat | Parallel-Probe acc |
| Qwen | AIME26 | 83.3% / 198.4s | 87.5% / 250.6s | 76.7% |
| Qwen | HMMT25 | 73.3% / 205.7s | 69.2% / 257.8s | 65.0% |
| Qwen | HMMT26 | 42.4% / 208.0s | 45.5% / 254.8s | 42.4% |
| GPT-OSS | AIME26 | 86.7% / 79.3s | 90.0% / 110.6s | 81.7% |
A 90-million-token diagnostic without control: mean token entropy has volatility 0.54, Spearman |ρ| 0.13, AUC 0.58 for future answer stability (h=5). Token perplexity is similar (0.56 / 0.12 / 0.57). Instantaneous answer confidence is better (0.26 / 0.41 / 0.71) and still jumpy. Ablation on Qwen HMMT25: drop retirement and accuracy falls 6.6 points to 66.7%; drop forking and it falls 3.3 points, with the lowest compute; drop pruning and latency rises to 233.0s with accuracy 71.7%.
If a serving stack already runs SC@16, this is a drop-in controller that spends two to three tenths less compute and keeps most of the accuracy. It does not require training, and it does not require branches to synchronize. The paper also states a useful test for any future signal: answer-space alignment, temporal aggregation, branch locality. Token-level filters (DeepConf) and synchronized probes (Parallel-Probe) fail at least one of those.
This is an efficiency paper, not a new state of the art on AIME.
There is no limitations section. HMMT26 on Qwen is the tell: 42.4%, tied with Parallel-Probe and zero-shot, below SC at 45.5%. Temporal control did not buy accuracy there. Probes need a discrete, normalizable answer space; open-ended writing and code completion do not plug in cleanly. Warmup of 15 probes at 500-token intervals means roughly the first 7,500 tokens run unmanaged, so short traces save less. Probe forward-pass cost is not isolated. Only two mid-size open reasoning models were tested.