TL;DR
Rather than treating an LLM's position bias (like "lost-in-the-middle") as noise to be averaged away, Gold Panning Bandits turns it into an asset. By treating context positions as heterogeneous diagnostic detectors with known error rates, the algorithm greedily places the most ambiguous documents into the most informative positions, identifying relevant content using up to 65% fewer queries than random shuffling.
What Problem Does This Paper Address?
Large language models (LLMs) struggle with multi-document reasoning due to pronounced position bias: models disproportionately attend to documents placed near the beginning or end of their prompt while neglecting content in the middle.
Existing mitigation strategies, such as Permutation Self-Consistency (PSC), treat this bias as random noise by shuffling documents across multiple forward passes and averaging the outputs. However, this is computationally wasteful—each random shuffle is treated independently, ignoring what the model has already learned about document relevance in previous iterations. The authors set out to answer: Can we use an LLM's systematic position bias to discover relevant documents faster?
Methods
The authors formulate document permutation as an active learning / combinatorial multi-armed bandit problem called Gold Panning Bandits:
- Positions as Detectors: Each context position $j$ acts as a binary detector characterized by its pre-calibrated True Positive Rate ($\text{TPR}_j$) and False Positive Rate ($\text{FPR}_j$). Its diagnosticity is measured via Youden's J-statistic: $d_{\text{diag}}(j) = |\text{TPR}_j - \text{FPR}_j|$.
- Bayesian Belief Dynamics: The system tracks a posterior probability belief $b_{t,i} \in [0, 1]$ indicating whether document $i$ is relevant. With each query and observed citation, beliefs are updated via Bayes' rule.
- Greedy Matching Algorithm: An exact one-step optimal assignment requires solving a maximum-weight bipartite matching problem using the Hungarian algorithm in $O(N^3)$ time. Instead, the authors introduce Gold Panning, an efficient greedy heuristic:
- Rank documents in descending order of uncertainty (entropy $\mathcal{H}(b_{t,i})$).
- Rank context positions in descending order of diagnosticity ($d_{\text{diag}}$).
- Match the most uncertain document to the most diagnostic position, the second-most uncertain to the second-most diagnostic, and so on.
- This sorts in $O(N \log N)$ time per iteration.
- Theoretical Justification: The authors prove that when detectors are symmetric ($\text{TPR}_j = 1 - \text{FPR}_j$), the information gain matrix is anti-Monge. Consequently, the $O(N \log N)$ greedy assignment is provably identical to the optimal $O(N^3)$ Hungarian solution.
Datasets
- Controlled Synthetic Simulations: Simulated setups with $N \in \{10, 30, 50\}$ documents, varying degrees of environmental heterogeneity (modeled via symmetric Beta distributions), and sparse ground-truth targets ($k \le \sqrt{N}$).
- MonoRel (Levy et al., 2024): A real-world fact-finding QA dataset used for empirical validation. Each prompt contains 1 "gold" fact and $N - 1$ distractor facts (tested at context lengths of $N = 100$ and $N = 400$). Evaluated primarily on
GPT-4o-mini.
Key Insights and Ideas
- Biases as Diagnostic Lenses: Instead of fighting the model’s attentional quirks, the authors use them. Sensitive positions act as broad filters that surface even moderately relevant items, while selective positions verify candidates.
- The "Rich Get Richer" Property (Anti-Monge): Highly diagnostic positions provide disproportionately greater information gains when evaluating highly uncertain documents compared to already-resolved ones. This mathematical structure guarantees greedy sorting optimality under natural conditions.
- Offline Calibration Beats Online Bandit Learning: Attempting to learn position properties online (e.g., using Thompson Sampling) fails because the combinatorial search space is too large. A lightweight, one-time offline calibration amortizes across inference runs and makes targeted active learning practical.
Key Results
- Computational Efficiency: Gold Panning requires up to 65% fewer LLM queries than random permutation baselines to identify relevant documents.
- Simulation Accuracy: In controlled benchmarks across all scales ($N=10, 30, 50$), Gold Panning's $O(N \log N)$ curve is virtually indistinguishable from the exact $O(N^3)$ Hungarian upper bound, while massively outpacing random Permutation Self-Consistency (e.g., reaching 75% accuracy in 10 rounds at $N=50$, where PSC fails to reach 75% after 20 rounds).
- Real-World Benchmark (MonoRel on GPT-4o-mini):
- At 400 facts (where position bias exhibits a strong U-shaped curve), Gold Panning boosted accuracy from 0.57 to 0.75 (a ~34% improvement).
- Baselines like PSC and Thompson Sampling stagnated near the single-shot average (~0.57), failing to learn from previous iterations.
Limitations and Future Work
- Calibration Overhead: Gold Panning assumes access to a pre-calibrated bias profile ($\text{TPR}/\text{FPR}$ per context slot), which requires dedicated upfront queries.
- Conditional Independence: The Bayesian updates assume each position’s output is conditionally independent, abstracting away complex inter-token and inter-document cross-attention dynamics.
- Stationary Bias Assumptions: The model assumes positional bias is invariant to domain, prompt formatting, and query types; in practice, position bias may fluctuate across tasks.
- Binary Relevance: The formulation assumes binary document relevance ($Z_i \in \{0, 1\}$); future extensions must generalize to continuous or multi-hop, graded relevance settings.
Summary updated