Refinement as a Service: Algorithmic Predictor Refinement

Wei Tang; Hanrui Zhang

cs.GTOct 8, 2026

Refinement as a Service: Algorithmic Predictor Refinement

Authors: Wei Tang, Hanrui Zhang

Organizations: Chinese University of Hong Kong.

Abstract

Prediction aggregation aims to combine information from multiple predictors into a more informative one. We study this question in the setting of calibrated predictors, where each prediction must equal the conditional expectation of the quantity being predicted given the predictor's signal. Given several calibrated input predictors and the feature distribution, but not the underlying Bayes probabilities, we ask when one can construct refined calibrated predictors that preserve the information in the original predictors and cannot be further refined using the available information. We formulate calibrated predictors as signaling schemes and define refinement through feature-independent garblings: a predictor refines another if its signal can simulate the other's signal. Constructibility is characterized through observable linear information: each signal corresponds to a vector over the feature space, and a new signal is constructible exactly when its vector lies in the linear span of the input signal vectors. Under this formulation, we establish a sharp algorithmic picture. For deterministic output predictors, bilateral refinement admits a polynomial-time algorithm based on a bipartite graph between the two input signal partitions, while refinement with an arbitrary number of input predictors is $\mathsf{NP}$ -hard. In contrast, when randomized output predictors are allowed, we give a polynomial-time algorithm for any number of input predictors by decomposing constructible signal vectors into extreme rays of the associated polyhedral cone.

Figures & tables

Panel of Figure 1 — Figure 1: Illustration of Algorithm 1 . In this example, the two deterministic predictors $f_{1}$ and $f_{2}$ induce signal partitions over the feature set. We write each signal cell by the feature indices it contains: $\Pi_{f_{1}}=\{A_{1},A_{2},A_{3}\}$ , where $A_{1}=\{x_{1},x_{2},x_{3},x_{4}\}$ , $A_{2}=\{x_{5}\}$ , and $A_{3}=\{x_{6}\}$ ; and $\Pi_{f_{2}}=\{B_{1},B_{2},B_{3}\}$ , where $B_{1}=\{x_{1},x_{5}\}$ , $B_{2}=\{x_{2},x_{3}\}$ , and $B_{3}=\{x_{4},x_{6}\}$ . Figure 1(a) shows the overlap graph $G$ , whose vertices are the signal cells of $f_{1}$ and $f_{2}$ , and where an edge indicates a nonempty intersection between two signal cells. The cell $A_{1}$ is an articulation vertex. Figure 1(b) shows that $G-A_{1}$ has three connected components: $K_{1}=\{A_{2},B_{1}\}$ , $K_{2}=\{B_{2}\}$ , and $K_{3}=\{A_{3},B_{3}\}$ . By Algorithm 1 , the cell $A_{1}$ is therefore split into the branch pieces $A_{1}^{K_{1}}=A_{1}\cap B_{1}=\{x_{1}\}$ , $A_{1}^{K_{2}}=A_{1}\cap B_{2}=\{x_{2},x_{3}\}$ , and $A_{1}^{K_{3}}=A_{1}\cap B_{3}=\{x_{4}\}$ . The remaining signal cells $A_{2}=\{x_{5}\}$ and $A_{3}=\{x_{6}\}$ are unchanged. Hence the finest constructible deterministic refinement of $f_{1}$ is $\widehat{\Pi}_{1}=\bigl\{\{x_{1}\},\{x_{2},x_{3}\},\{x_{4}\},\{x_{5}\},\{x_{6}\}\bigr\}$ .

Explore similar work

Jun 18, 2026cs.LG

Optimal Deterministic Multicalibration and Omniprediction

A model is multicalibrated on a collection of group weights

G

if it is calibrated -- i.e. unbiased even conditional on its prediction -- not just overall, but also after reweighting contexts by each

g \in G

. It is a useful property for many downstream applications and is a basic desideratum of trustworthy machine learning. Before this work, all predictors known to attain the minimax-optimal

\widetilde O(\varepsilon^{-3})

sample complexity rate for

\varepsilon

-multicalibration were randomized, while deterministic predictors were known only with substantially worse sample complexity. Whether randomization is necessary for optimal sample complexity in multicalibration was explicitly asked by [CLNR26] and implicitly in several prior works. We resolve this open problem by giving a minimax-optimal multicalibration algorithm that outputs a deterministic predictor. We then generalize the algorithm to produce optimal deterministic predictors that satisfy outcome indistinguishability (OI) with respect to finite or finitely covered collections of tests. As an application, this also gives deterministic omnipredictors and panpredictors with optimal sample complexity, resolving open problems posed by [OKK25] and [BHHLZ25].

Georgy Noarov, Aaron Roth

University of Pennsylvania

Minimax Estimation Model Calibration Multicalibration

Ask PDF

Jul 22, 2026stat.ML

Optimal Recalibration of an Online Predictor

We study the problem of recalibrating an online predictor [KE17, OKS24]: given an arbitrary "hint" sequence of forecasts, the learner must output new predictions that are calibrated while incurring small excess error relative to the original forecasts, under a proper loss. We give an online algorithm that achieves

(\varepsilon, \varepsilon^2)

-recalibration for Lipschitz proper losses in

T \approx \varepsilon^{-3}

rounds, using an imbalanced extension of the recent simultaneous Blackwell approachability reduction framework of [HTY26]. We show that this tradeoff is optimal by proving a matching lower bound for recalibrating against the squared loss. We also prove a companion

\mathcal{K}_2

-recalibration theorem that obtains the same tradeoffs up to a logarithmic factor. As our main application, we show how our recalibration algorithms can be combined with the online refinement method of [FH23] to obtain simultaneous

\varepsilon

-calibration and

\varepsilon^2

-calibeating for smooth proper losses at the same asymptotic rate, improving upon prior works that achieved these properties separately or with a worse

\varepsilon

dependence. In particular, the

\mathcal{K}_2

variant answers a question of [CHJL26] on simultaneously achieving near-optimal calibeating and calibration rates. We also derive extensions to settings with multiple hint sequences. Finally, we empirically evaluate our algorithms on a classification dataset undergoing distribution shift.

Lunjia Hu, Kevin Tian, Chutong Yang

Northeastern University · University of Texas at Austin

Model Calibration

Ask PDF

Apr 17, 2026cs.AI

Harnessing Pre-Resolution Signals for Future Prediction Agents

Many high-stakes decisions depend on forecasts made before outcomes are known. In this future prediction setting, the central challenge is that public evidence evolves over time, while the main supervision signal arrives only after resolution: the realized outcome mainly assesses final correctness, offering only coarse guidance on what to track, what to verify, and which judgments to leave uncertain along the way. Our key observation is that revisiting the same unresolved question over time creates informative temporal contrasts across evolving evidence and repeated forecasts, exposing what earlier attempts missed before resolution and yielding a diagnostic signal we call the pre-resolution signal. We instantiate this idea in Milkyway, a future prediction agent with a persistent future prediction harness, an editable external state that stores reusable procedural guidance across revisits to the same unresolved question. As the same unresolved question is revisited, Milkyway extracts pre-resolution signals from evolving evidence and repeated forecasts, uses them to update the harness, and improves later forecasts on that question before resolution. After resolution, the realized outcome serves as a post-resolution check of provisional updates. On the FutureX and FutureWorld benchmarks, Milkyway achieves strong performance against competitive baselines, and a mechanism study suggests that the gains stem from harness evolution driven by pre-resolution signals rather than repeated prediction alone.

Chuyang Wei, Maohang Gao, Zhixin Han +12

University of Science and Technology of China · Zhongguancun Academy, Beijing, China · IIIS, Tsinghua University

Agent Memory Online Learning

Ask PDF