Source-linked AI summary
Refinement as a Service: Algorithmic Predictor Refinement
Wei Tang, Hanrui Zhang
TL;DR
The paper asks how calibrated predictors can be refined by combining information from multiple participants. It models refinement through constructible signals and presents a sharp algorithmic contrast: randomized outputs are tractable for any number of inputs, while deterministic outputs are tractable bilaterally but NP-hard with arbitrary input counts.
Problem
The paper asks when information from multiple calibrated predictors can be used to refine them and produce maximal refinements.
Source: §1 · p. 2Method
It uses a bipartite-graph procedure for bilateral deterministic refinement and support-minimal refiners and extreme rays for randomized refinement.
Source: §1.2 · pp. 6–7, §5 · p. 25Results
Deterministic refinement is polynomial-time for two inputs but NP-hard for arbitrary input counts, while randomized refinement is polynomial-time for any number of inputs.
Source: §1.2 · pp. 5–6Takeaways & Limitations
The results provide algorithms for maximal refinement across these settings, including a polynomial-time randomized approach for any number of inputs.
Source: §1.2 · pp. 6–7The observable signal-wise label masses used by the construction rely on signal-level calibration; prediction-level calibration alone may not make them observable.
Source: §3.2 · p. 13
Abstract
from arXiv · showhide
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.
1 Introduction
The introduction frames calibrated-predictor refinement as combining participants’ information while preserving each predictor’s information, then asks when maximal refinements are constructible. It presents a sharp algorithmic contrast between deterministic and randomized outputs.
1 Introduction
- The paper asks whether input predictors can refine one another and how to maximally refine them using available information.Different information in the inputs does not guarantee that refinement is possible.Source: §1 · pp. 2–3
1.1 Setting up the Stage
- Calibrated predictors are modeled as signaling schemes, and constructible signals correspond to vectors in the span of the input signal vectors.Observed input predictions can then be used to compute calibrated values for constructible refined signals.Source: §1.1 · pp. 3–5
1.2 Results and Techniques
- With deterministic outputs, refinement is polynomial-time for two input predictors but NP-hard for an arbitrary number of inputs.The bilateral algorithm builds a bipartite graph from overlapping signal cells and uses bottleneck vertices to obtain maximal refinements.Source: §1.2 · pp. 5–6
- With randomized outputs, refinement has a polynomial-time algorithm for any number of input predictors.The approach uses minimal-support refiners and extreme rays of the constructible signal cone.Source: §1.2 · pp. 6–7
- The proposed refinement algorithms can serve platforms that incorporate another participant’s constructible information while preserving domain-specific expertise.The service interpretation does not require access to the underlying Bayes probabilities.Source: §1.2 · p. 7
1.3 Further Related Work
- The paper distinguishes information refinement from forecast-aggregation rules evaluated by loss or regret, and uses feature-independent garbling as its refinement criterion.It notes that this criterion is typically stronger than the Blackwell-order comparison used by Tang and Zhang (2026).Source: §1.1 · p. 4, §1.3 · p. 8
2 Preliminary
The paper treats calibrated predictors as signal-generating schemes and compares their information through feature-independent garblings. It asks for constructible strict refinements that are undominated using the observed feature distribution and input predictors, without access to Bayes probabilities.
2 Preliminary
- A predictor is signal-level calibrated when each positive-probability signal’s prediction equals the conditional expected label given that signal.Signal-level calibration implies prediction-level calibration, but the converse can fail when distinct signals share a numerical prediction.Source: §2 · p. 9
- Signals, not just numerical predictions, are the primitives because distinct signals with equal predictions can carry different refinement information.One signal can be simulated from two distinct signals by forgetting their distinction, but the reverse simulation need not be possible.Source: §2 · p. 9
- A predictor informationally dominates another when a feature-independent stochastic channel can simulate the latter’s signals, but not conversely.This models refinement as preserving the original predictor’s signal structure while allowing additional distinctions.Source: §2 · p. 10
- Constructible predictors use only the feature distribution and input predictors, and the goal is an undominated strict improvement when one exists, or the original predictor otherwise.The aggregator does not observe the underlying Bayes probabilities.Source: §2 · pp. 10–11
3 Observable Linear Information
The section converts signal structures into vectors so observable information and refinement can be characterized with linear algebra. It then identifies constructible signals through a row-space condition on the input signal-feature matrix.
3 Observable Linear Information
- The section recasts signal kernels in linear form to define constructible predictors from observable information.The observable inputs are the feature distribution and the input predictors.Source: §3 · p. 11, §3.2 · p. 13
3.1 Representing Predictors via Bag-of-Vectors
- Each signal is represented by a nonnegative vector whose coordinates give its probabilities across features; the vectors sum coordinatewise to one.The raw bag is reduced by merging vectors on the same positive ray, which only merges signals differing by an independent random split.Source: §3.1 · pp. 11–12
- In bag form, informational dominance is expressed by a row-stochastic matrix that maps one predictor’s signal vectors to the other’s, with no reverse mapping.The bag formulation is equivalent to the signal-kernel definition.Source: §3.1 · pp. 12–13
3.2 Constructible Predictors from Observable Linear Information
- The input signal vectors form a matrix M, and observed signal-wise label masses give a linear system My = b for the unknown feature-level label masses.M comes from the input signal structures; b is computed from their calibrated predictions and the known feature distribution.Source: §3.2 · p. 13
- A vector’s label mass is uniquely determined by the observations exactly when the vector lies in the row space of M.For deterministic predictors, this means an output signal cell is observable exactly when its indicator vector lies in that row space.Source: §3.2 · pp. 14–15
- A constructible predictor’s signal vectors must be observable and sum coordinatewise to one, making them both identifiable and a valid stochastic kernel.This construction relies on signal-level calibration; prediction-level calibration alone may not make individual signal-wise label masses observable.Source: §3.2 · pp. 13–14
4 Hardness and Efficient Algorithms for Deterministic Predictors
This section studies refinement of deterministic predictors through signal partitions and the complexity of PredictorRefine. It shows that the problem is NP-hard in general but solvable in polynomial time with two inputs, where Algorithm 2 finds the finest constructible deterministic refinement for each input.
4 Hardness and Efficient Algorithms for Deterministic Predictors
- For deterministic predictors, one strictly informationally dominates another exactly when its signal partition strictly refines the other's.A deterministic predictor is constructible when every signal-cell indicator lies in Row(M).Source: §4 · p. 15
4.1 NP-Hardness for Solving PredictorRefine
- PredictorRefine is NP-hard for deterministic inputs and outputs, via a reduction from X3C3 exact cover.The reduction makes an exact cover equivalent to a nontrivial observable subset that permits a strict deterministic refinement.Source: §4.1 · pp. 15, 16, 19
4.2 Efficient Algorithm for Solving PredictorRefine with k = 2
- With two deterministic input predictors, Algorithms 1 and 2 solve PredictorRefine in polynomial time by refining cells into overlap-graph branch pieces.These pieces form the finest constructible deterministic refinement; if that partition is unchanged, no constructible deterministic predictor strictly dominates the input.Source: §4.2 · pp. 19–20
- For each input partition, the algorithm constructs a finest constructible deterministic refinement, returning the original predictor when no strict refinement exists.The constructed partition consists of branch pieces AK; if it equals the input partition, no strictly informationally dominating deterministic predictor exists.Source: §4.2 · pp. 23–24
- Algorithm 2 solves deterministic PredictorRefine for k = 2, producing the required output for both input predictors.The proof handles the first predictor and applies symmetrically to the second.Source: §4.2 · p. 24
- One call to Algorithm 1 runs in O(I(I + E + n)) time, which is polynomial in input size because I, E = O(n); rational arithmetic has polynomial bit complexity.The second call has the same complexity, so Algorithm 2 runs in polynomial time.Source: §4.2 · p. 24
5 Efficient Algorithms for Randomized Predictors
For randomized outputs, PredictorRefine is solvable in polynomial time by splitting constructible signal vectors into extreme-ray pieces. The resulting predictors are informationally undominated, while each input is either left unchanged or strictly refined.
5 Efficient Algorithms for Randomized Predictors
- Theorem 5.1 gives a polynomial-time algorithm for PredictorRefine with randomized outputs.The complexity assumption is rational input data encoded in binary.Source: §5 · p. 24
- The algorithm repeatedly decomposes each input signal vector into constructible pieces until each piece lies on an extreme ray of the constructible signal cone.Extreme rays are found through support-minimality and polynomial-time linear-feasibility tests.Source: §5 · pp. 24–25
- For each input predictor, the algorithm returns it unchanged if already undominated, and otherwise returns a strict constructible refinement that is undominated.The decomposition refines signals, and a feature-independent garbling can map each finer piece back to its parent signal.Source: §5 · pp. 24, 25, 28, 29
- A constructible predictor whose reduced signal vectors all span extreme rays is informationally undominated.Any constructible predictor that garbles to it must have the same reduced bag of vectors, up to reordering.Source: §5 · p. 27
- The full algorithm runs in polynomial time by using polynomially many rational linear-programming solves and computing calibrated predictions for its output rows.The analysis bounds the number of LP solves by O(N n^2), where N is the total number of input reduced-bag rows.Source: §5 · p. 29
A Missing Proofs in Section 4
The missing proofs connect deterministic refinement to refinement of signal partitions and use that connection to establish NP-hardness for deterministic PredictorRefine.
A Missing Proofs in Section 4
- For deterministic predictors, a feature-independent garbling exists exactly when the source signal partition refines the target partition.Strict informational dominance corresponds to strict partition refinement.Source: A Missing Proofs in Section 4 · p. 34
- A deterministic PredictorRefine algorithm would decide ifRefinable by checking whether its first output changes the first input predictor.The reduction returns No if the output is unchanged and Yes otherwise.Source: A Missing Proofs in Section 4 · p. 34
- Because ifRefinable is NP-hard, deterministic PredictorRefine is NP-hard under polynomial-time Turing reductions.Source: A Missing Proofs in Section 4 · p. 34
B Missing Proofs in Section 5
The missing proofs establish that ray reduction preserves informational comparisons and that support-minimal constructible vectors characterize extreme rays. These facts underpin the claim that predictors built from extreme-ray rows are undominated.
B Missing Proofs in Section 5
- Merging positive-ray-equivalent vectors preserves informational dominance in both directions, so it preserves strict comparisons.The raw and ray-reduced bags simulate one another through feature-independent garblings.Source: B Missing Proofs in Section 5 · pp. 34–35
- A nonzero constructible vector spans an extreme ray exactly when no nonzero constructible vector has support strictly contained in its support.The proof uses nonnegative decompositions to connect support minimality with extremality.Source: B Missing Proofs in Section 5 · pp. 35–36
- If every reduced-bag vector of a constructible predictor spans an extreme ray, any predictor that garbles to it has the same reduced bag, so it is undominated.The proof uses extremality to force each contributing source row onto the target row's ray.Source: B Missing Proofs in Section 5 · p. 36
C Signal-Level Calibration and Prediction-Level Calibration
Signal-level calibration requires each signal's conditional label mean to equal its prediction, whereas prediction-level calibration constrains only averages among signals sharing a value. Coarsening can represent prediction-calibrated inputs, but numerical outputs do not preserve all signal-based refinement guarantees.
C Signal-Level Calibration and Prediction-Level Calibration
- Signal-level calibration implies prediction-level calibration, but the converse can fail when distinct signals share a numerical prediction.The notions coincide when the prediction map is injective on positive-probability signals.Source: C Signal-Level Calibration and… · pp. 36–37
- Merging signals with equal numerical predictions converts prediction-level calibrated inputs into signal-level calibrated inputs and preserves their conditional numerical-prediction distribution given each feature.This representation requires the resulting signal kernels to be available.Source: C Signal-Level Calibration and… · p. 37
- Merging equal-valued output signals may destroy informational dominance, so the paper's maximality guarantees apply to signal-based dominance rather than numerical-output post-processing.The paper identifies signal-level calibration and signal-based dominance as the distinct formulation addressed by its algorithmic results.Source: C Signal-Level Calibration and… · pp. 37–38