Order-Rewiring Particle Search for LLM Reasoning Over Noisy Context

When a language model reasons over several retrieved passages or auxiliary snippets, its answer depends on the order in which those passages appear. The usual fix is to shuffle the passages many times and take a majority vote. We study a stronger kind of inference-time search, particle search, where a population of partial reasoning chains is extended step by step and the unpromising ones are pruned. Our claim is that this search quietly brings order bias back. Each chain is tied to the passage ordering it started with. Pruning keeps duplicating the few chains that look best early. Those chains tend to be the ones whose ordering put a persuasive passage, often a misleading one, in a slot the model over-attends. Within a few steps every surviving chain descends from one ordering.

We propose to measure this collapse directly, then remove it with a move borrowed from particle Gibbs sampling. At each pruning step, a surviving reasoning prefix may "re-attach" to a different passage ordering, chosen in proportion to how well that ordering explains the prefix. The passage-ordering scores this move produces are reused to weight chains by a lower-tail statistic rather than an average. The reason is that position effects inflate a passage's apparent support in one direction (primacy dominated 73 of 104 evaluations in Serial Position Effects of Large Language Models). Averaging over orders, as shuffle-and-vote does, is justified only if those effects are symmetric and cancel.

Core Claim

Sequential Monte Carlo (SMC) runs a population of hypotheses ("particles"), weights them by how well they fit a target, and resamples by duplicating good ones and dropping bad ones. Its known failure is path degeneracy. Because resampling copies whole histories, looking backward from a late step all particles share a single ancestor (Elements of Sequential Monte Carlo). We claim that when the latent state includes a context ordering, path degeneracy concentrates exactly on the ordering. It does so in the direction of the model's positional preference, so particle search over reasoning chains inherits positional bias even when orderings are initialized uniformly at random.

The proposed remedy has two parts. The first is an ordering-rewiring move modeled on ancestor sampling. The second is an asymmetric weighting rule. Together they should recover the robustness that shuffle-averaging aims for, at matched compute, on tasks where reasoning is multi-step and the context contains hard distractors.

This differs from the closest work in what it searches over and what it corrects. REQUAL-LM shuffles inputs across independent queries and aggregates outputs at a centroid in embedding space. It keeps no lineages, so it has nothing to collapse or rewire. AutoSelect learns to build a demonstration order with a single-chain policy. We do not learn orders. We marginalize over them during reasoning. Critic Sequential Monte Carlo and the Twisted Diffusion Sampler supply the idea of guiding SMC with a learned or heuristic lookahead score. Neither treats input order as part of the latent state.

Research Program

The state of particle $i$ at reasoning step $t$ is a pair: an ordering $\pi_i$ of the $K$ context passages, and a reasoning prefix $s_{i,1:t}$ generated by the model while reading the passages in that order. Orderings start uniformly at random. Each step extends every prefix by one reasoning step. Each particle is then weighted by a step judge $v$, which is the same base model prompted in a fixed format to rate whether the prefix is sound, and the population is resampled.

The rewiring move happens after resampling. For a surviving prefix we draw $M$ candidate orderings uniformly, independently of the current one, and add the current ordering to that set. We then reassign the prefix to ordering $\pi_m$ with probability

$$P(\pi_m \mid s_{1:t}) \propto p_\theta(s_{1:t} \mid x, \pi_m),$$

where $x$ is the question and $p_\theta$ is the model's likelihood of the already-generated prefix when the passages are read in order $\pi_m$. This is the same structure as ancestor sampling in Ancestor Sampling for Particle Gibbs and Particle gibbs with ancestor sampling. There, the reference state's ancestor is resampled from every candidate in proportion to how well each explains it. Under a uniform prior on orderings, the move leaves the joint target over (ordering, prefix) unchanged, by the standard multiple-try argument. Scoring a fixed prefix needs only a prefill pass, which is much cheaper than generation.

The weighting rule reuses those $M+1$ scorings. For each of them we also compute the judge score, and we weight the particle by

$$w = Q_\alpha\big(\{v(s_{1:t}, x, \pi_m)\}_{m=0}^{M}\big),$$

the lower $\alpha$-quantile of the judge scores across orderings. Setting $\alpha = 0.5$ recovers a symmetric, median-like summary, so $\alpha$ is a direct test of the symmetry assumption. The rule follows the logic of the one-sided loss in Unilateral boundary time series forecasting, where errors from a known one-sided distortion are penalized in one direction only. It also follows Relaxed Quantile Regression, which shows that forcing symmetric quantiles onto skewed noise misplaces intervals. Here the distortion is an upward inflation of support for whatever passage sits in a privileged slot. We fit $\alpha$ once on a held-out split and also report a fitted two-piece skew model of per-position score shifts, following Bayesian modelling of skewness and kurtosis with Two-Piece Scale and shape distributions. This checks whether the skew is real rather than assumed.

The diagnostic is a contribution independent of the method. For plain SMC we record two quantities. The first is coalescence time, the number of steps until all survivors share one ancestral ordering. The second is the survival odds of a lineage as a function of which passage occupied its first and last slots, where we know from labels whether that passage is gold or misleading. If positional bias re-enters through degeneracy, lineages with a misleading passage in a privileged slot will be over-represented among survivors.

Baselines

The naive reference point is single-pass generation on one random ordering, run with thinking on and with thinking off. On SciAux, Thinking in a Crowd reports 96.22% accuracy for Qwen3-8B on clean inputs, 77.03% with two misleading snippets and thinking on, and 74.87% with thinking off. We use Qwen3-8B so those numbers are directly comparable, and gains are judged against the 77.03% figure.

The strongest existing method is shuffle-and-majority-vote, as used in QMOS, where 20-fold inference-time shuffling with voting contributed about a 10% accuracy boost on TeleQnA. For retrieval-augmented question answering, Do RAG Systems Suffer From Positional Bias? reports 71.00% for random Shuffle and 71.73% for relevance-aware placement (MaxRel), using Qwen 2.5 7B with BGE plus a reranker. That paper shows clever placement does not beat shuffling, so shuffle-and-vote is the competitor to beat. We run it with as many shuffles as fit the same total token budget as our method. Prefill tokens and generated tokens are both counted, and generated tokens are weighted by measured wall-clock cost. Its sampling temperature is tuned on the same held-out split we use to tune $\alpha$ and $M$.

A second strong baseline is best-of-N with the same step judge, again on random orderings and at matched budget. This separates the value of the judge from the value of sequential search.

The ablations isolate each ingredient. Plain SMC without rewiring and with mean weighting shows the collapse. SMC with rewiring but $\alpha = 0.5$ isolates the move. SMC with lower-quantile weights but no rewiring isolates the asymmetric rule. For SMC itself on LLM reasoning, we found no reported result on Lacuna for these benchmarks.

Beating the strongest baseline means a statistically significant accuracy gain over budget-matched shuffle-and-vote on SciAux-misleading and on the hard-distractor subset of the open-domain QA sets. It also means the gain holds across at least two model families.

Why not just…?

Why not just shuffle many times and vote? This is the real threat. On single-step multiple-choice it may well match us, and we include MMLU partly to confirm that it does. The argument for particle search is narrower. In multi-step reasoning, a vote over independent chains cannot recombine a good early step from one ordering with a good later step from another. It also spends its full budget on chains that commit to a misleading premise in the first step, which is the rationalization failure seen on SciAux. If budget-matched voting equals our method on SciAux and on hard-distractor retrieval, the method claim fails, and we will report the coalescence diagnostic as the main finding.

Why not just calibrate the output distribution, as OTTER does? OTTER removes letter-selection bias by forcing predictions to match a uniform label distribution through optimal transport over a batch. That fits balanced multiple-choice benchmarks. It does not apply to free-form multi-step answers over passages, it needs batches, and it assumes a symmetric target. We still run it on the MMLU control as a reference.

Why not just score each passage separately so order cannot matter? The "Separation" format removes order effects but discards comparative context. ARC 'Challenge' Is Not That Challenging reports 64% versus 93% for Llama 3.1 70B on ARC Challenge when options are scored separately rather than together. Multi-hop questions also need passages read jointly. We include a passage-by-passage baseline to confirm this tax holds in our setting.

Why not just turn on chain-of-thought? Chain-of-thought reduced serial position effects in Serial Position Effects of Large Language Models. However, thinking made Qwen3-8B worse under misleading snippets on SciAux, so it is a baseline condition here, not a solution.

Proposed Experiments

The main testbed is SciAux, which has 6,828 multi-hop questions with helpful, irrelevant, and misleading snippets. The second testbed is Natural Questions, TriviaQA, and PopQA with top-10 dense retrieval. We stratify the open-domain QA results by whether a hard distractor is present, which the RAG positional-bias paper reports for over 60% of queries. MMLU serves as a single-step control where we predict little gain over voting. Models are Qwen3-8B and Llama 3.1 8B. We sweep particle counts from 4 to 32 and $M$ from 2 to 8, and plot accuracy against total tokens for every method.

Three outcomes decide the project. First, plain SMC must show measurable ordering coalescence, with survival odds skewed toward lineages that had a misleading passage in a privileged slot. If not, the motivating mechanism is wrong. Second, rewiring must lengthen coalescence time and close that survival skew. Third, the fitted per-position score shifts must be measurably skewed, and lower-quantile weighting must beat $\alpha = 0.5$ only when they are. A gain from low $\alpha$ without measured skew would mean the rule is acting as generic pessimism rather than correcting a one-sided order effect. We will report it that way.