source/paper/main.tex

\documentclass[11pt]{article}


\usepackage[margin=1in]{geometry}
% if you need to pass options to natbib, use, e.g.:
%     \PassOptionsToPackage{numbers, compress}{natbib}
% before loading neurips_2025


% ready for submission
\PassOptionsToPackage{numbers,sort&compress}{natbib}


\usepackage{tikz}
\usepackage{etoc}
\usepackage{etoolbox}
% Custom appendix ToC file
\newcommand{\appendixtocfile}{appendix_toc}
\newcommand{\addtoappendixtoc}[1]{\addcontentsline{\appendixtocfile}{section}{#1}}
\newcommand{\addsubtoappendixtoc}[1]{\addcontentsline{\appendixtocfile}{subsection}{#1}}


% To allow printing ToC from another file
\usepackage{titletoc}

\makeatletter
  % Flag: are we in the appendix?
  \newif\ifinappendix
  \inappendixfalse
  % Save original \addcontentsline
  \let\origaddcontentsline\addcontentsline
  % Override: only write to .toc when in appendix
  \renewcommand{\addcontentsline}[3]{%
    \ifinappendix
      \origaddcontentsline{#1}{#2}{#3}%
    \fi
  }
  % When \appendix is executed, turn the flag on
  \pretocmd{\appendix}{\inappendixtrue}{}{}
\makeatother

\renewcommand{\contentsname}{Table of Contents}



\setlength{\parindent}{0pt}
\setlength{\parskip}{8pt}
\usepackage{natbib}
%\usepackage[preprint]{neurips_2025}
\usepackage[inline]{enumitem}
\usepackage{multicol}
\usepackage{multirow}
\usepackage{fancyvrb}
\usepackage{framed}
\usepackage{wrapfig}
\usepackage{bbm}
\usepackage{tcolorbox}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{tcolorbox}
\usepackage{enumitem}
\usepackage{booktabs}
\usepackage{caption}
\usepackage{authblk} %for arxiv non neurips authors
% Theorem environments
% preamble

\newtheorem{theorem}{Theorem}[section]
\newtheorem{remark}{Remark}[section]
%more algorithm pretty box
\tcbuselibrary{skins,breakable}
\usepackage{graphicx}
%algorithms 
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}

\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    citecolor=blue,
    urlcolor=blue
}

% Custom appendix ToC file
%\newcommand{\appendixtocfile}{appendix_toc}
%\newcommand{\addtoappendixtoc}[1]{\addcontentsline{\appendixtocfile}{section}{#1}}
%\newcommand{\addsubtoappendixtoc}[1]{\addcontentsline{\appendixtocfile}{subsection}{#1}}

% To allow printing ToC from another file
\usepackage{titletoc}

\makeatletter
  % Flag: are we in the appendix?
  \newif\ifinappendix
  \inappendixfalse
  % Save original \addcontentsline
  \let\origaddcontentsline\addcontentsline
  % Override: only write to .toc when in appendix
  \renewcommand{\addcontentsline}[3]{%
    \ifinappendix
      \origaddcontentsline{#1}{#2}{#3}%
    \fi
  }
  % When \appendix is executed, turn the flag on
  \pretocmd{\appendix}{\inappendixtrue}{}{}
\makeatother

\renewcommand{\contentsname}{Table of Contents}


\usepackage{booktabs}
\usepackage{tabularx}
\usepackage{graphicx}   % for \resizebox
\usepackage{subcaption} % for subtables

\newtheorem{thm}{Theorem}
\newtheorem{proofpart}{Part}

% Share the same counter as theorem
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}

% Definitions/assumptions get a different style
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{assumption}[theorem]{Assumption}

% Remarks/examples (non-italic body)
\theoremstyle{remark}
%\newtheorem*{remark}{Remark}
%\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}




%\newtheorem{lemma}{Lemma}[section]
%title spcing
%\usepackage{titlesec}
% Format: \titlespacing{command}{left}{before-sep}{after-sep}
%\titlespacing\section{0pt}{1pt plus 0pt minus 2pt}{1pt plus 0pt minus 2pt}
%\titlespacing\subsection{0pt}{1pt plus 0pt minus 1pt}{1pt plus 0pt minus 1pt}
%\titlespacing\subsubsection{0pt}{1pt plus 0pt minus 1pt}{1pt plus 0pt minus 1pt}
\newcommand{\HH}[1]{\noindent{\textcolor{blue}{\textbf{\#\# HH:} #1 \#\#}}}
\newcommand{\SN}[1]{\noindent{\textcolor{purple}{\textbf{SN:}}}}

% Optional style settings
\tcbset{
  colback=gray!5,
  colframe=black!75!black,
  boxrule=0.5mm,
  arc=4mm
}


% to compile a preprint version, e.g., for submission to arXiv, add add the
%[preprint] option:
%\usepackage[preprint]{neurips_2025}


% to compile a camera-ready version, add the [final] option, e.g.:
%     \usepackage[final]{neurips_2025}


% to avoid loading the natbib package, add option nonatbib:
%\usepackage[]{neurips_2025}


\usepackage[utf8]{inputenc} % allow utf-8 input
\usepackage[T1]{fontenc}    % use 8-bit T1 fonts
\usepackage{hyperref}       % hyperlinks
\usepackage{url}            % simple URL typesetting
\usepackage{booktabs}       % professional-quality tables
\usepackage{amsfonts}       % blackboard math symbols
\usepackage{nicefrac}       % compact symbols for 1/2, etc.
\usepackage{microtype}      % microtypography
\usepackage{xcolor}         % colors
\usepackage{amsmath}
% Custom equal contribution symbol
\newcommand{\equalcontrib}{\textsuperscript{*}}

\newcommand{\sk}[1]{\textcolor{blue}{\textbf{Shayan:} #1}}

\title{Human-AI Collaborative Uncertainty Quantification}
%\title{Conformal prediction in the case of Infinite-label classification - an uncertainty quantification paradigm for LLMs}


% The \author macro works with any number of authors. There are two commands
% used to separate the names and addresses of multiple authors: \And and \AND.
%
% Using \And between authors leaves it to LaTeX to determine where to break the
% lines. Using \AND forces a line break at that point. So, if LaTeX puts 3 of 4
% authors names on the first line, and the last on the second line, try using
% \AND instead of \And before the third author name.
\newcommand{\equalcontribfootnote}{\begingroup
\renewcommand\thefootnote{*}
\footnotetext{Equal contribution.}
\endgroup}


\iffalse
\author{%
  Sima Noorani\thanks{Equal contribution.} \\
  University of Pennsylvania
  \And
  Shayan Kiyani\footnotemark[1] \\
  University of Pennsylvania
  \AND
  George Pappas \\
  University of Pennsylvania
  \And
  Hamed Hassani \\
  University of Pennsylvania
}
\fi

\author[1]{Sima Noorani\equalcontrib}
\author[1]{Shayan Kiyani\equalcontrib}
\author[1]{George Pappas}
\author[1]{Hamed Hassani}

\affil[1]{University of Pennsylvania}
\date{}
\begin{document}


\maketitle
\begingroup
\renewcommand\thefootnote{*}
\footnotetext{Equal contribution. Correspondence to: \texttt{nooranis@seas.upenn.edu}, \texttt{shayank@seas.upenn.edu}.}
\endgroup
%\equalcontribfootnote
\vspace{-2em}
\begin{abstract}
AI predictive systems are becoming integral to decision-making pipelines, shaping high-stakes choices once made solely by humans. Yet robust decisions under uncertainty still depend on capabilities that current AI lacks: domain knowledge not captured by data, long-horizon context, and the ability to reason and act in the physical world. This contrast has sparked growing efforts to design \emph{collaborative} frameworks that combine the complementary strengths of both agents. This work advances this vision by identifying the fundamental principles of Human-AI collaboration in the context of uncertainty quantification---an essential component of any reliable decision-making pipeline. We introduce Human-AI Collaborative Uncertainty Quantification, a framework that formalizes how an AI model can refine a human expert’s proposed prediction set with two goals in mind: \emph{avoiding counterfactual harm}, ensuring the AI does not degrade the human’s correct judgments, and \emph{complementarity}, enabling the AI to recover correct outcomes the human missed. At the population level, we show that the optimal collaborative prediction set takes the form of an intuitive two-threshold structure over a single score function, extending a classical result in conformal prediction. Building on this insight, we develop practical offline and online calibration algorithms with provable \emph{distribution free} finite-sample guarantees. The online algorithm adapts to \emph{any} distribution shifts, including the interesting case of human behavior evolving through interaction with AI, a phenomenon we call “Human-to-AI Adaptation.” We validate the framework across three modalities---image classification, regression, and text-based medical decision-making---using models from convolutional networks to LLMs \footnote{We release our code at \url{https://github.com/nooranisima/Human-AI-Collaborative-UQ}}. Results show that collaborative prediction sets consistently outperform either agent alone, achieving higher coverage and smaller set sizes across various conditions, including shifts in human behavior.

%Furthermore, we empirically validate our framework across three diverse data modalities: image classification, regression, and text-based medical decision-making with large language models. Our experiments span a range of AI systems from convolutional networks to LLMs, and systematically vary the strength of both the human and AI components. The results show that collaborative prediction sets consistently outperform either agent alone, achieving higher coverage and smaller set sizes across a wide range of conditions, including dynamic shifts in human behavior.

%we empirically validate our framework across three diverse domains, including image classification, regression, and medical decision-making with large language models. The results show that collaborative prediction sets can achieve higher coverage while simultaneously reducing the average prediction set size and thus outperforming both the human and AI components in isolation.

%\textcolor{red}{here please briefly mention the experiment results.}
\end{abstract}

\section{Introduction}\label{intro}

Artificial intelligence has demonstrated extraordinary predictive power, enabling data-driven decision-making in high-stakes domains such as healthcare, law, and autonomous systems. These systems excel at extracting patterns from vast amounts of data, offering statistical accuracy and consistency at a scale unattainable by human reasoning alone. Yet, robust decision-making in such settings requires more than predictive accuracy. Human experts contribute domain knowledge beyond data \citep{hansen2023importance}, persistent memory for long-term planning and context \citep{gradientflowbengio}, and the ability to reason and act within the physical world in ways still inaccessible to current AI systems \citep{agrawal2010study}. These complementary strengths point to the importance of human-AI collaboration, where computational precision and human judgment can jointly guide decisions under uncertainty.

A central challenge in realizing this vision lies in uncertainty quantification (UQ) \citep{marusich2024usingaiuncertaintyquantification}. Precise characterization of uncertainty is fundamental to robust decision-making, as it allows decision-makers to weigh risks, assess reliability, and allocate trust between human and machine. While UQ has been extensively studied in the machine learning community, these efforts largely focus on AI systems in isolation. In collaborative settings, however, it is not clear what principles of UQ should be when humans and AI are jointly in the loop. Identifying these principles is essential for designing frameworks that achieve the best of both worlds: combining AI’s predictive accuracy with human judgment to enable decisions more robust and effective than either could do alone. To this end, we ask:
\begin{center}
    \emph{What should characterize a successful collaboration \\ between a human expert and an AI system?}
\end{center}
 Two principles naturally emerge. First, the expert must trust the collaboration to even be willing to engage: the AI’s contribution should not degrade the quality of the human’s input. In other words, collaborating with AI should not make the outcome worse in the worst case---a notion we refer to as \emph{counterfactual harm}. Second, collaboration must offer clear benefits beyond what the expert could achieve alone. The AI should \emph{complement} the human by addressing blind spots, identifying correct outcomes that may have been overlooked, and thereby strengthening the overall decision process. Together, these two principles, trust through non-degradation and benefit through complementarity, capture the essential properties of a meaningful human–AI collaborative framework.

 In this work, motivated by recent advances in conformal prediction \citep{vovk2005algorithmic,lei2017distributionfreepredictiveinferenceregression,romano2019conformalizedquantileregression,romano2020classificationvalidadaptivecoverage,angelopoulos2022uncertaintysetsimageclassifiers}, we develop a framework that instantiates these two principles in the context of collaborative prediction sets. This allows us to design distribution-free sets that respect both principles without assumptions on the behavior of the AI model or the human, making the approach particularly practical for modern applications. Additionally, recent work shows that conformal prediction sets are essential for risk-sensitive decision making, where decisions must account for predictive uncertainty in a principled way \citep{kiyani2025decisiontheoreticfoundationsconformal}. This makes prediction sets an especially compelling subject of study for human–AI collaboration in high-stakes domains such as healthcare.

\textbf{Proposed Framework.} We propose a framework for 
\emph{human--AI collaborative uncertainty quantification}, where the two agents jointly construct a prediction set.

\begin{wrapfigure}{r}{0.5\textwidth} % r/l for right/left; set width
   \vspace{-0.5em}                     % tweak vertical alignment (optional)
  \centering
  \includegraphics[width=\linewidth]{correct-intro-fig.png}
  \caption{Schematic of the two guiding principles}
  \label{fig:ch-c}
  %\vspace{-0.8em}                     % reduce space below (optional)
\end{wrapfigure}
Formally, let $(X,Y)\sim \mathcal{P}$, where $X\in\mathcal{X}$ denotes the observed features and $Y\in\mathcal{Y}$ the corresponding label. The goal is to construct, for each input $x$, a set $C(x)\subseteq \mathcal{Y}$ that contains the true label $Y$ with high probability while remaining as small as possible. 

In our collaborative setting, a human expert first proposes an initial set of plausible outcomes $ H(x)\subseteq \mathcal{Y},$ based on their expertise. 
The AI system then refines this proposal by outputting a prediction set $C(x,H(x)) \subseteq \mathcal{Y},$ designed to complement the human input.

For notational convenience, we drop the explicit dependence on $H(x)$ in what follows, and have~$C(x)~:=~C(x,H(x))$.




This modification is guided by two principles. 
The first is \emph{low counterfactual harm}: the AI should not degrade the quality of the human proposal. Concretely, whenever the true label lies within the human’s proposed set, the AI’s refinement must preserve high coverage,
\[
\mathbb{P}\!\left(Y\notin C(X)\mid Y\in H(X)\right)\ < \varepsilon .
\]

The second is \emph{complementarity}: the AI should add value precisely when the human misses the correct outcome. That is, with high probability, the AI’s refinement recovers the true label whenever it is excluded from the human proposal,
\[
\mathbb{P}\!\left(Y\in C(X)\mid Y\notin H(X)\right)\ \ge 1-\delta .
\]

These two principles are illustrated schematically in Figure~\ref{fig:ch-c}. Together, they formalize a collaborative prediction strategy: the AI preserves the human’s expertise while compensating for potential blind spots. 
They come together in the following optimization problem, which serves as the collaboration framework we study in this work:

\begin{tcolorbox}
[colback=gray!5!white,colframe=black!70,title=Human-AI Collaboration Optimization (HACO)]
Let $(X,Y)\sim\mathsf{P}$ and $H(x)\subseteq\mathcal{Y}$ be a human-proposed set.
Let the prediction set returned by the AI be denoted as $C(x,H(x)) := C(x)\subseteq\mathcal{Y}$.
The Human-AI Collaboration Optimization (HACO) problem is
\begin{equation}
\tag{HACO}
\begin{aligned} \label{HACO}
\min_{C:\mathcal{X}\to 2^{\mathcal{Y}}}\quad & \mathbb{E}\,|C(X)| \\
\text{s.t.}\quad 
& \mathbb{P}\!\left(Y\notin C(X)\mid Y\in H(X)\right)\ <  \varepsilon,\\
& \mathbb{P}\!\left(Y\in C(X)\mid Y\notin H(X)\right)\ \ge\ 1 - \delta,
\end{aligned}
\end{equation}
where $\varepsilon$ and $\delta$ are two user-defined thresholds.
\label{p:haco}
\end{tcolorbox}


At a high level, the goal of prediction sets is to include the correct label with high probability while keeping the sets small --- set size serving as the measure of efficiency in uncertainty quantification. Within our framework, the AI contributes in two complementary ways: pruning and augmentation. On the one hand, the AI prunes labels from the human proposal whenever possible, since smaller sets are more informative, but does so without violating the counterfactual harm constraint. On the other hand, the AI augments the set by adding likely labels that the human may have overlooked, thereby ensuring complementarity. The human contribution, in turn, is to provide the AI with a stronger starting point. When the initial human-proposed sets are of high quality, the AI’s final sets achieve the same coverage level with significantly smaller size than what either could have produced in isolation. 

\textbf{Preview of Results.}
\begin{itemize}
    \item We characterize the optimal solution to HACO in Section \ref{sec:inf_sample}. As we will show, the optimal solution takes the intuitive form of ``two thresholds over one score function'', one threshold for pruning labels in the human set, and the other guides the labels that we will add to the human set. We will then build upon this result in Section~\ref{Sec:score} to design conformity scores that will be used by our finite sample algorithm. In particular, for the case of regression, our score is a novel extension of conformalized quantile regression \citep{romano2019conformalizedquantileregression}.
    \item In Section~\ref{sec:finite-sample-alg}, we derive practical finite sample algorithms with provable distribution-free guarantees, in two settings of offline, where the calibration and test data are separated and exchangeable, and online, where the data is streamed one by one. Notably, in the online setting, our algorithm also captures the novel concept of ``Human-to-AI Adaptation'', which might be of its own interest and a promising subject for further studies.
    \item In Section~\ref{sec:experiments}, we evaluate our finite sample offline and online algorithms on three data modalities: image classification, text based medical diagnosis, and real-valued regression. Across all settings, we show that the parameters \(\varepsilon\) and \(\delta\) can be tuned such that the collaborative prediction set outperforms both human and AI-only baselines, achieving higher coverage, smaller size, or both. We vary human and AI strength to study each component’s role and test robustness under various distribution shifts.
    
    %We systematically vary the strength of the human and the AI across our experiments to study how each component contributes to overall performance. In the online setting, we evaluate the framework under multiple forms of distribution shift, including human adaptation to AI, and show that the algorithm remains effective.
\end{itemize}

\subsection{Related Works}

%Conformal prediction (CP) provides distribution-free, finite-sample guarantees and has become a standard tool for uncertainty quantification in classification and regression \cite{vovk2005algorithmic,lei2017distributionfreepredictiveinferenceregression,romano2019conformalizedquantileregression,romano2020classificationvalidadaptivecoverage, angelopoulos2022uncertaintysetsimageclassifiers}. Furthermore, prediction sets are a natural primitive for risk-sensitive decision making: they communicate uncertainty in a form well-suited to risk-averse decision makers in high-stakes settings \cite{kiyani2025decisiontheoreticfoundationsconformal}. Additionally and more broadly, conformal risk control and related approaches calibrate decision rules to meet risk-sensitive or safety constraints, aligning predictions with operational goals \cite{angelopoulos2025conformalriskcontrol,lindemann2023safeplanningdynamicenvironments,lekeufack2024conformaldecisiontheorysafe}.  

We briefly discuss closely related works here and defer a full discussion to Section~\ref{appendix:lit-review}. In the context of the human–AI collaboration, a growing line of work studies prediction sets as advice to experts \citep{straitouri2024designingdecisionsupportsystems, pmlr-v202-straitouri23a,cresswell2024conformalpredictionsetsimprove, zhang2024evaluatingutilityconformalprediction, paat2025conformalsetbasedhumanaicomplementarity,hullman2025conformalpredictionhumandecision}. For instance, \citet{pmlr-v202-straitouri23a} propose improving expert predictions with Conformal Prediction sets, \citet{babbar2022utilitypredictionsetshumanai} show empirically that set-valued advice can boost human accuracy, and \citet{elanicounterfactual} analyze such systems through the lens of counterfactual harm. These works differ from ours in that they study how humans use AI-provided sets and evaluate downstream human accuracy, but do not construct a final \emph{collaborative} prediction set that algorithmically integrates human feedback with AI. A complementary literature on \emph{learning to defer} allocates instances between models and experts \citep{madras2018predictresponsiblyimprovingfairness,mozannar2021consistentestimatorslearningdefer,okati2021differentiablelearningtriage,verma2022calibratedlearningdeferonevsall}. This also differs from our goal in that we do not optimize who decides on each instance; instead, we collaboratively quantify uncertainty by combining the human’s initial set with AI to return a single, joint prediction set with explicit safeguards (e.g., counterfactual harm and complementarity constraints).
%\textcolor{blue}{make sure you cover ALL the relevant works}

    %\item In Section \ref{sex:experiments}, we empirically evaluate across three modalities of data: image classification, regression, and text-based decision making. We study both offline and online settings, comparing against human-only and AI-only baselines.
        
    %our framework on three different modalities of data classification images, text and regression in both the offline and online settings. in the offline setting we demosntrate the benefits of collaborative predicition sets over both human and ai in isolation, as well as we demonstrate the effect of each component in the effeciencty and overall benefit ahchieved ( human contribution if its smalelr or weak or ai contribution ). In the online setting, we looks at this phenomena we call "human adaptation to AI" which is liek a form of dist shift where human changes its strategy over time due to ai feedback. 

%\section{Scratch pad}
%Maybe mention why prediction sets are important. Risk-aversity.

%after HACO definition mention that when H is emoty or has everything, the problem gets reduced to length minimization in CP, which is studied, so in this sense this is a generalization ...


%Narrative : no matter what human you are this is kind of a wrapper around the AI model so that when you use it it adds to you, collaborates with you to optimize the final outcome given youre the initial starting point, to build trust and to make sure this collaboration is good for YOU.

%Add the values of $a^*$ and ... to the theorem.


\section{Optimal Prediction Sets Over Population}\label{sec:inf_sample}
% We formalize the objective of constructing joint human--AI prediction sets as follows.
% \begin{tcolorbox}[colback=gray!5!white,colframe=black!70,title=Problem (P)]
% Let $(X,Y)\sim\mathsf{P}$ with posterior $p(y\mid x)$ and a human-proposed set $H(x)\subseteq\mathcal{Y}$.
% Let the prediction set returned by the AI be denoted as $C(x,H(x)) := C(x)\subseteq\mathcal{Y}$.
% The primary optimization problem is
% \begin{equation}
% \tag{P}\label{P}
% \begin{aligned}
% \min_{C:\mathcal{X}\to 2^{\mathcal{Y}}}\quad & \mathbb{E}\,|C(X)| \\
% \text{s.t.}\quad 
% & \mathbb{P}\!\left(Y\in C(X)\mid Y\in H(X)\right)\ \le\ \varepsilon,\\
% & \mathbb{P}\!\left(Y\in C(X)\mid Y\notin H(X)\right)\ \ge\ \delta.
% \end{aligned}
% \end{equation}
% \end{tcolorbox}
We begin by characterizing the optimal solution to the optimization problem \ref{HACO}, the problem introduced in Section \ref{intro}, in the infinite-sample regime, where the data distribution $\mathcal{P}$ is fully known. This characterization uncovers the statistical framework that we will later use to design finite-sample algorithms, enabling us to tune the dynamics of Human-AI collaboration with fine control over counterfactual harm and the complementarity rate of the collaboration procedure.



% In this setting, the goal is to characterize the prediction sets that satisfy the desired counterfactual harm and complementarity constraints while minimizing set size. This leads to the following result
\begin{theorem}
\label{thm:pred-set}
The optimal solution to \ref{HACO} is of the form
\[
C^*(x)=\big\{\,y:\ 1 - p(y\mid x)\ \le\ a^*\,\mathbf{1}\{y\notin H(x)\}\,+b^*\,\mathbf{1}\{y\in H(x)\}\,\big\}, 
\quad \text{a.s. for any $x\in\mathcal{X}$},
\]
for some thresholds $a^*, b^* \in\mathbb{R}$.
\end{theorem}

The theorem shows that the optimal collaborative prediction set can be described by two thresholds: One, $b^*$, which is responsible for \emph{pruning}, i.e., for the labels $y\in H(x)$, $b^*$ determines which ones we keep and which ones we exclude; And the other, $a^*$, which is responsible for \emph{augmenting} new labels, i.e., for the labels $y\notin H(x)$, $a^*$ determines which ones to add to the final set. In other words, we include all labels whose $p(y\mid x)$ exceeds a threshold, and that threshold depends on whether the label was originally proposed by the human. If $y \in H(x)$, then the AI uses a threshold $b^*$, and if $y \notin H(x)$, the AI instead applies a different threshold $a^*$. 

% Alternatively, one can interpret this optimal set through the following simple manipulation:
% \begin{align}
%     a^*\,\mathbf{1}\{y\notin H(x)\}\,+b^*\,\mathbf{1}\{y\in H(x)\} 
%     &= a^* + (b^* - a^*)\,\mathbf{1}\{y\in H(x)\}.
% \end{align}
% In this way, the human set serves as a binary signal for the AI. When the label is in the human set, a $(b^* - a^*)$ correction applies to the threshold, which then modifies likelihood of including that label in the final set.

This theorem generalizes prior results on minimum set size conformal prediction \citep{sadinle2019least, kiyani2024lengthoptimizationconformalprediction}. When the human set always includes all the labels or is always empty---essentially the two cases in which the human set carries no information about the true label---the optimal set reduces to a one-scalar characterization of the form $\big\{\,y:\ 1 - p(y\mid x)\ \le\ q^*\,\big\}$, which corresponds to minimum set size conformal prediction. 

In what follows, we take advantage of the result of this theorem to design an algorithmic framework for Human-AI collaboration. In particular, in the characterization given by Theorem \ref{thm:pred-set}, there are three components that need to be approximated or estimated in a finite-sample setting: $p(y\mid x)$, $a^*$, and $b^*$. As we will see, the AI’s role will be to provide an approximation of $p(y\mid x)$. In the next section, we will discuss this in the two different settings of classification and regression. We will then discuss debiasing strategies to estimate $a^*$ and $b^*$ from data.

% For examples when the initial human sets are of high quality, meaning they include the correct label most of the time, the thresholds reflect this by treating the labels suggested by the human more leniently and the AI prunes them only if they are extremely unlikely, thereby avoiding counterfactual harm. In contrast, labels omitted by the human must clear a higher bar to be added, ensuring that augmentation occurs only when the AI model has strong evidence the human missed the correct outcome. Thus, this two threshold form balances the principles of trust and benefit, pruning when safe and augmenting when needed.

%AI-assisted prediction set can be described by two simple thresholds: one ($a^*$) that applies to labels the human \emph{did not include}, and one ($b^*$) for labels the human \emph{did include}.
%Intuitively, if the human already proposed a label, the AI can be more lenient in keeping it (using threshold $b^*$),
%while for labels the human did not propose, the AI must be more selective (using threshold $a^*$). this depends on the human accuracy honestly. 
\section{Conformal Scoring Rules}\label{Sec:score}


Building on the results of Theorem \ref{thm:pred-set}, our goal is to construct prediction sets of the form
\[
C^*(x)=\big\{\,y:\ s(x, y)\ \le\ a^*\,\mathbf{1}\{y\notin H(x)\}\,+b^*\,\mathbf{1}\{y\in H(x)\}\,\big\},
\]
where $s(x,y)$ is a  \textbf{non-conformity score} that measures how unusual a label $y$ is for a given input $x$. In the infinite-sample regime, Theorem~\ref{thm:pred-set} shows that the optimal non-conformity score is  $s(x,y) = 1 - p(y \mid x)$ where $p(y \mid x)$ is the true conditional distribution. However, since \(p(y \mid x)\) is unknown in practice, we design a non-conformity score to approximate the behavior of the optimal score. Below, we describe how such scores can be constructed for both classification and regression settings.


%this score is defined as $s(x,y) = 1 - p(y|x)$, but in practice, the true conditional probability $p(y|x)$ is unknown.
%\textcolor{red}{bad sentence. defined? say Theorem say the optimal conformity score is ....}

%This leads to a central subject of study in conformal prediction literature: designing a \textbf{surrogate non-conformity measure} that imitates the behavior of the ideal score. The design of this surrogate score is task-dependent. Below, we discuss how to define an appropriate score for both classification and regression tasks.

\paragraph{Classification} 
In classification tasks, predictive models typically output a probability distribution over labels, often obtained via a softmax layer. Formally, let 
\(f: \mathcal{X} \to \Delta_{\mathcal{Y}}\) 
map each input \(x \in \mathcal{X}\) to a \(|\mathcal{Y}|\)-dimensional vector of probabilities 
\(\hat{p}(y \mid x)\), which approximates the true conditional probabilities \(p(y \mid x)\). 
A widely used non-conformity score in classification \citep{sadinle2019least} that we adopt in our framework  is defined as
\[
\hat{s}(x,y) = 1 - \hat{p}(y \mid x),
\]
%and we adopt this score in our framework.

% This score assigns a low value to labels the model considers highly probable and a high value to labels it considers unlikely. 
% Thresholding this score naturally creates a prediction set that includes the most probable labels, aligning with the two-threshold structure described in Theorem~\ref{thm:pred-set}.


\paragraph{Regression}%\textcolor{red}{alpha-lo alpha-hi and ... should be changed to alpha/2 and ...}

%\textcolor{red}{define pinball loss---define quantile regression --- make it self-contained}

%\textcolor{red}{When writing, you are supposed to TEACH the reader, with information dense, justified, well-argued sentences. Your text does not reflect these properties.}

%In regression, the label space is continuous, and accurately estimating the full conditional distribution \(p(y\mid x)\) is often infeasible in practice. Consequently, unlike classification, directly approximating the optimal score \(1 - p(y\mid x)\) is not straightforward.
In regression, the continuous label space makes it difficult to estimate the full conditional distribution \(p(y\mid x)\), so directly approximating the optimal score \(1 - p(y\mid x)\) is not straightforward. To circumvent this, we build upon \emph{Conformalized Quantile Regression} (CQR) \citep{romano2019conformalizedquantileregression}. The idea of CQR is to estimate lower and upper conditional quantiles of \(Y\) given \(X=x\) and then use them to construct a conformal score.
Suppose we obtain an estimate \(\hat q_{\alpha/2}\) of the \(\alpha/2\) quantile of the distribution of \(Y \mid X=x\), and an estimate \(\hat q_{1-\alpha/2}\) for the \(1-\alpha/2\) quantile. We can then define the score
\[
\hat{s}(x,y) \;=\; \max\!\Bigl\{\hat q_{\alpha/2}(x)-y,\ \ y-\hat q_{1-\alpha/2}(x)\Bigr\},
\]
and use this to make prediction sets. One can verify that the resulting prediction sets are a calibrated version of
$
\bigl[\hat q_{\alpha/2},\ \hat q_{1-\alpha/2}\bigr]
$
(either expanded or shrunk symmetrically). The intuition is that the CQR score remains small within the learned central quantile band and increases linearly into the tails. For common unimodal distributions, this ordering is approximately monotone with \(1 - p(y \mid x)\), so thresholding the CQR score closely emulates the optimal rule. Prediction sets of this form have shown strong performance in terms of average set size in practice. We generalize the idea behind CQR to design a score function tailored to our two-threshold setting. The idea is to learn two distinct sets of quantile functions: one for counterfactual harm when \(Y \in H(x)\) and one for complementarity when \(Y \notin H(x)\). To achieve this, we learn two pairs of quantile functions, \((\hat q_{\varepsilon/2}, \hat q_{1-\varepsilon/2})\) for the counterfactual-harm constraint and \((\hat q_{\delta/2}, \hat q_{1-\delta/2})\) for the complementarity constraint. From these quantile estimates, we define the nonconformity score as  %\textcolor{red}{drop this from here and explain in experiment: Rather than fitting them on disjoint subsets, we pool all data and include \(\mathbf{1}\{Y \in H(x)\}\) as an auxiliary feature.}
\[
\hat{s}(x,y) :=
\begin{cases}
\max\{\hat q_{\varepsilon/2}(x) - y,\; y - \hat q_{1-\varepsilon/2}(x)\}, & y \in H(x), \\[2pt]
\max\{\hat q_{\delta/2}(x) - y,\; y - \hat q_{1-\delta/2}(x)\}, & y \notin H(x).
\end{cases}
\]
This score treats labels inside \(H(x)\) differently from those outside it, applying a distinct CQR-style score to each in an intuitive manner: for \(y \in H(x)\), the score is derived from the counterfactual-harm rate \(\varepsilon\); for \(y \notin H(x)\), it is derived from the complementarity rate \(1-\delta\).

% This score is nonpositive if \(y\) lies within the relevant quantile interval and becomes positive as it moves outside. Thresholding this score with the values \(a^*\) and \(b^*\) recovers the two-threshold structure predicted by Theorem~\ref{thm:pred-set}, thereby generalizing the classic CQR approach to our collaborative setting.


% A straightforward use of these estimates would be to form the interval
% \[
% [\hat q(x; \alpha/2), \hat q(x; 1-\alpha/2)]
% \]
% These quantile estimates can be obtained with standard quantile regression methods, which directly fit models to approximate conditional quantiles from data. But in practice this interval may not achieve the desired $1-\alpha$ coverage if the quantile estimates are imperfect. Thus in CQR, conformal calibration is then applied to these initial intervals to gaurantee valid finite-sample coverage. 

% In our collaborative framework, we build on the CQR framework to hand two distinct constraints: one for counterfactual harm when $Y \in H(x)$ and one for complementarity when $Y \notin H(x)$. To achieve this, we learn two pairs of quantile functions: $(\hat q_{\varepsilon \text{lo}}, \hat q_{\varepsilon \text{hi}})$ for the counterfactual harm constraint, and $(\hat q_{\delta \text{lo}}, \hat q_{\delta \text{hi}})$ for the complementarity constraint. Rather than fitting them on disjoint subsets, we pool all data and include $\mathbf{1}{Y \in H(x)}$ as an auxiliary feature.

% From these quantile estimates, we define the non-conformity score for a triple $(x,y,H(x))$ as
% \[
% s(x,y) :=
% \begin{cases}
% \max\{\hat q_{\varepsilon lo}(x) - y,\; y - \hat q_{\varepsilon hi}(x)\}, & y \in H(x) \\
% \max\{\hat q_{\delta lo}(x) - y,\; y - \hat q_{\delta hi}(x)\}, & y \notin H(x)
% \end{cases}
% \]
% This score is non-positive if $y$ lies within the relevant quantile interval and becomes positive as it moves outside. Thresholding this score with the values $a^*$ and $b^*$ recovers the two-threshold structure predicted by Theorem \ref{thm:pred-set}, generalizing the classic CQR approach to our collaborative setting. 

%editing above ... 
%\textit{Conformalized Quantile Regression} (CQR).
%The starting point is conditional quantile regression. To recall the goal of standard conditional quantile regression is to estimate a given quantile of Y conditional on X. Given the conditional distribution function $F( y \mid X = x) := \mathbb{P}(Y \leq y \mid X =x)$, the $\alpha$-th conditional quantile function is $q_{\alpha}(x) := inf \{ y \in \mathbb{R} : F ( y  \mid X =x) \geq \alpha \}$. 
%Fixing the lower and upper quantiles to be equal to $\alpha_{lo} = \alpha/2$ and $\alpha_{hi} = 1 - \alpha/2$, given the pair $q_{\alpha_{lo}}$ and $q_{\alpha_{hi}}$ of lower and upper conditional quantile functions we can construct a conditional prediction interval satisfying $\mathbb{P}(Y \in C(X) | X = x) \geq  1- \alpha$ by construction:
%\[ 
%C(x) = [q_{\alpha_{lo}}(x),  q_{\alpha_{hi}}(x)]
%\]
%In finite sample, we can estimate these conditional quantiles from data via quantile regression, which fits a function $q_{\tau}(x)$ by minimizing the pinball loss function defined as 
%\[
%\ell_\tau(y, q(x)) = \big(\tau - \mathbf{1}\{y < %q(x)\}\big)\,(y - q(x)),
%\]
%an asymmetric loss that penalizes underestimation and overestimation differently. Given a miscoverage rate $\alpha$, standard CQR fits lower and upper quantile regressors $\hat q_{\alpha_{lo}}$ and $\hat q_{\alpha_{lo}}$, and then applies conformal calibration to obtain valid finite-sample coverage gaurantees.

%In our Human-AI collaborative framework, instead of enforcing a single coverage condition, we must satisfy two distinct conditional probabilistic constraints simultaneously, one for counterfactual harm when $Y \in H(x)$ and one for complementarity when $ Y \notin H(x)$. Therefore, we need to estimate two separate sets of conditional quantile regressors each tailored for a specific constraint, $(\hat{q}_{\varepsilon lo}, \hat{q}_{\varepsilon hi}) \quad \text{for the case } Y \in H(x)$, and $(\hat{q}_{\delta lo}, \hat{q}_{\delta hi}) \quad \text{for } Y \notin H(x).$ Rather than fitting the quantile regressors on separate (and possibly imbalanced) subsets, we pool all data and include the indicator $\mathbf{1}\{Y \in H(x)\}$ as an auxiliary feature in training.   

%Next, we define the non-conformity score that quantify the error made by the plug-in prediction intervals. For a triplet $(x,y,H(x))$, the non-conformity score is: 
%\[
%s(x,y) :=
%\begin{cases}
%\max\{\hat q_{\varepsilon lo}(x) - y,\; y - \hat %q_{\varepsilon hi}(x)\}, & y \in H(x) \\
%\max\{\hat q_{\delta lo}(x) - y,\; y - \hat q_{\delta hi}(x)\}, & y \notin H(x)
%\end{cases}
%\]
%This score is non-positive if $y$ lies within the relevant quantile interval and becomes positive as it moves outside. Thresholding this score with the values $a^*$ and $b^*$ recovers the two-threshold structure predicted by Theorem \ref{thm:pred-set}, generalizing the classic CQR approach to our collaborative setting. 


% ABOVE THIS WAS THE PREVIOUS VERSION
%In standard CQR, the goal is to construct a prediction interval, $C(X)$, that guarantees coverage for a new, unseen data point with a desired miscoverage rate, i.e $\mathbb{P}\{Y \inC(X)\} \geq 1-\alpha$. 

%To achieve this, CQR uses quantile regression models to estimate the conditioan quantiles of $Y$ given $X$. Specifically, regressors are used to estimate a lower quantile $\hat{q}_{\alpha/2}(x)$ and one upper quantile $\hat{q}_{1-\alpha/2}(x)$. 

%Unlike standard CQR which is designed with the goal to satisfy a single coverage constraint, our collaborative framework must satisfy two distinct conditional probabilistic constraints, one for counterfactual harm and one for complementarity. Thus, instead we train two separate sets of conditional quantile functions each tailored ot a specific constraint: $(\hat{q}_{\varepsilon lo}, \hat{q}_{\varepsilon hi})$ are trained to estimate the conditional quantiles of $Y$ given $X$ when the true label is in the human's set ($Y \in H(X)$). These are used to control the counterfactual harm rate. On the other hand, $(\hat{q}_{\delta lo}, \hat{q}_{\delta hi})$ are trained to estimate the conditional quantiles of $Y$ given $X$ when the true label is not in the human's set ($Y \notin H(X)$). These are used to control the complementarity rate.

%Instead of training these quantile regressors on separate, potentially imbalanced subsets of data, we leverage all available data jointly by treating the indicator $\mathbf{1}\{Y \in H(x)\}$ as an auxiliary feature during the quantile regression training process.
%Lastly, for a triplet $(x,y, H(x))$ we define the conformity score as follows:
%\[
%s(x,y) :=
%\begin{cases}
%\max\{\hat q_{\varepsilon lo}(x) - y,\; y - \hat q_{\varepsilon hi}(x)\}, & y \in H(x) \\
%\max\{\hat q_{\delta lo}(x) - y,\; y - \hat %q_{\delta hi}(x)\}, & y \notin H(x)
%\end{cases}
%\]
%This score is non-positive if $y$ lies within the relevant quantile interval and becomes positive as it moves outside. Thresholding this score with the values $a^*$ and $b^*$ yields the two-threshold structure predicted by Theorem \ref{thm:pred-set}, generalizing the classic CQR approach to our collaborative setting. 
%In this way, the regression score balances the principles of \textbf{pruning} (to avoid counterfactual harm) and \textbf{augmentation} (to ensure complementarity).


 
 
%This is score is non-positive when y lies inside the relavant quantile interval and positive otherwise with larger values reflecting greater deviations. threshold Thresholding with respect to $a^$ and $b^$ thus yields exactly the two-threshold structure predicted by Theorem~\ref{thm:pred-set}. In this way, the regression score generalizes the classic CQR construction to the collaborative human–AI setting, balancing pruning (to avoid counterfactual harm) and augmentation (to ensure complementarity).

%\textcolor{red}{So for this Section, read what i wrote in the last section, try to have that format, detailed well structures, and insightful explanations. In the first paragraph, say that what we are doing in this Section is standard in conformal methods, and corresponds to the design of non-conformity score in CP literature. Explain that in principle, following the construction of Theorem \ref{thm:pred-set}, we want to make the set of the form, 
%$C^*(x)=\big\{\,y:\ s(x, y)\ \le\ a^*\,\mathbf{1}\{y\notin H(x)\}\,+b^*\,\mathbf{1}\{y\in H(x)\}\,\big\}, 
%\quad \text{a.s. for any $x\in\mathcal{X}$},$, where s is $1-p(y|x)$, but we dont have it and the idea is design a score that imitates the same behavior. Then say in the classification its straightforward but in regression there are some challenges that we address. Also rewrite the rest of this Section}

  

%Theorem~\ref{thm:pred-set} 
%shows that optimal collaborative sets can be constructed by thresholding a conformity score $s(x,y) = 1- p(y|x)$ which measures how atypical a label $y$ is for an input $x$. Lower scores indicate higher compatibility between y and x. The specific form of $s(x,y)$ depends on the task at hand. below we focus on the classification and regression task and define the score for each.

%\textbf{Classification}
%In classification tasks, a natural choice is to use the model’s estimated probabilities. 
%Given $\hat p(y \mid x)$, we define
%\[
%s(x,y) = 1 - \hat p(y \mid x).
%\]
%This score assigns small values to labels the model deems highly probable, and larger values to less likely labels. 
%Thresholding $s(x,y)$ therefore corresponds to including the most probable labels, which is consistent with the two-threshold structure of Theorem~\ref{thm:pred-set}. 

%\textbf{Regression}
%For regression, we build on the conformalized quantile regression (CQR) framework, which combines conformal prediction with classical quantile regression. 
%In standard CQR, conditional quantiles of $Y$ given $X$ are estimated from data by minimizing the pinball loss, and the conformity score is defined as the distance of the observed label $y$ from the fitted quantile interval. 

%In our collaborative setting, we adapt this idea to account for whether the human included the correct outcome. 
%Specifically, we fit two sets of conditional quantile functions: $(\hat q_{\varepsilon lo}, \hat q_{\varepsilon hi})$ to enforce the counterfactual harm constraint when $y \in H(x)$, and $(\hat q_{\delta lo}, \hat q_{\delta hi})$ to enforce the complementarity constraint when $y \notin H(x)$. Rather than splitting the data, we pass the indicator $\1\{Y \in H(x)\}$ as an additional feature to the quantile regression algorithm. This allows all calibration points to be used jointly for training, while enabling the regressors to condition on whether the human was correct. 

%For a point $(x,y,H(x))$, the conformity score is defined as
%\[
%s(x,y) :=
%\begin{cases}
%\max\{\hat q_{\varepsilon lo}(x) - y,\; y - \hat q_{\varepsilon hi}(x)\}, & y \in H(x), \\
%\max\{\hat q_{\delta lo}(x) - y,\; y - \hat q_{\delta hi}(x)\}, & y \notin H(x).
%\end{cases}
%\]
%In words, the score is non-positive whenever $Y_i$ lies inside the corresponding quantile interval and positive when it falls outside, with larger values reflecting greater violations. 
%Thresholding based on this score naturally leads to the two-threshold structure of Theorem~\ref{thm:pred-set}.

\section{Finite Sample Algorithms}
\label{sec:finite-sample-alg}
%\textcolor{red}{Add the algorithm Name CUP - Collaborative Uncertainty Prediction}
So far, we have shown that optimal collaborative prediction sets are of the form  
$
C^*(x) = \big\{\,y:\ s(x, y)\ \le\ a^*\,\mathbf{1}\{y\notin H(x)\}\,+b^*\,\mathbf{1}\{y\in H(x)\}\,\big\},
$
where we have also discussed strategies for designing the score \(s\) in both regression and classification. In this section, we fix the conformity score and focus on how to estimate the thresholds \(a\) and \(b\) from data.  We introduce \textit{Collaborative Uncertainty Prediction}-(CUP), our algorithmic framework for constructing collaborative prediction sets in finite samples. We consider two scenarios: (i) the offline setting, where calibration and test data are assumed exchangeable, and the task is to estimate thresholds on a held-out calibration set before evaluating on future points.; and (ii) the online setting, where data arrives sequentially and the underlying distribution may drift in arbitrary and unknown ways.

% THE PREVIOUS SHAY VERSION: In this section, we fix the conformity score and focus on how to estimate the thresholds \(a\) and \(b\) from data. We consider two scenarios: (i) the offline two-stage setting, where there is first a calibration phase followed by a test phase, with calibration and test data assumed to be exchangeable; and (ii) the online setting, where data arrives as a stream and no distributional assumptions are made.

% and shown that they depend on thresholding a non-conformity score based on the true conditional distribution $p(y \mid x)$, with different thresholds depending on whether a label is included in the human's proposed set. In practice, this ideal score must be approximated from data. In the previous section, we discussed how to construct such approximations in both classification and regression settings.
%in the infinite sample regime, the optimal prediction sets take the form
%\[
%C^*(x)=\big\{\,y:\ s(x, y)\ \le\ a^*\,\mathbf{1}\{y\notin H(x)\}\,+b^*\,\mathbf{1}\{y\in H(x)\}\,\big\},
%\]
%where the optimal non-conformity score is s(x,y) = 1- p(y \mid x)$ and the thresholds $a^*$ and $b^*$ are chosen to satsify the desired constraints on counterfactual harm and complemantarity. In practice, the true conditional probability $p(y \mid x)$ is unknown andm ust be approixmated using a prediction mdoel. In hte previous section, we described how to construct such approximations in both classification and regression setting.
% In this section, we assume a fixed, arbitrary score function $s(x,y)$, and shift out focus to calibrating the thresholds $a$ and $b$ from data to ensure that the resulting prediction sets satisfy the required guarantees in finite-sample regimes. 

% We begin by considering the \textbf{offline} setting, where we have access to calibrated data that is i.i.d with the test distribution.

% While exchangibility assumption is common in conformal prediction, it may not be appropriate for long-term human-AI collaboration. A key challenge in the collaborative setting is what we refer to as \textit{human adaptation to AI}. By this we mean that, as collaboration unfolds, humans may change the way they form their proposed sets $H(x)$ in respponse to how AI behaves. For instance, if a human repeatedly observes that the AI rarely incldues a particular label, they may gradually stop including that label in their own proposals, even if they would have otherwise considered it. This type of feedback loop alters the distribution of test-time data in ways that are not  captured by exchangeability assumption between the calibration and test-time data. 

% To account for this, we study the \textbf{online} setting, where the underlying data distribution can evolve over time, including the possibility of shifts that arise as a byproduct of the collaboration itself. Under this setting, we design algorithms that remain valid under distribution shift. 

% In the subsections that follow, we present finite-sample algorithms for both the offline and online settings, each designed to remain valid under their respective assumptions.

%So far, we have shown that the optimal prediction sets are of the form of thresholding the optimal score of 1- p(y | x) using two distinct threhsolds, depending on whether the a label is in the human proposed set or not. The optimal conformity score was based on p( y | x ) which needed to be approximated in the finite sample setting, and we showed how AI can provide an approximation for the score in both classification and regression. In this section, we fix an arbitary score and discuss debiasing methods for the threhsold a and b. We first begin by studying the offline setting, where we have access to a calibration data that is iid with the test time data - exchangable . Next, we argue that this setting might not be ideal/practical for prolonged collaborative interactions, due to a concept that we call huamn adaptation to AI, which is the concept that in collaborative interactions, a side product is usually the fact that the collaborators will learn from each other and adapt to each other style in  a sense like when i realized you really hate x, then i dont do x if its not productive for our collaborative common goal. Hence, we study an online setting, where exchanagibility between calibration and test data no longer hold and the underlying data generating distirbution will differ over time in section x. 



%\textcolor{red}{Here you should first remind the reader of the prediction set form brifely, and say we have discussed the conformity score design, in this section we fix an arbitrary score and discuss debiasing methods for a and b. then explain we begin by studying an offline setting where we have access to calibration and test time --- exchangeable calibration data and test sample. Then we will argue that this setting might not be ideal for prolonged collaborative interactions, due to a concept that we call human adaptation to AI, which means blah blah. Hence we will then study an online setting, where we no longer assume exchangeability and this setting allow for adaptations of human to AI.}

%The infinite-sample analysis establishes that the optimal collaborative sets are obtained by thresholding a conformity score with two thresholds, one governing labels inside the human set and another governing labels outside it. 
%In practice, however, these thresholds depend on the unknown data distribution and must be estimated from finite data. 
%This section develops practical algorithms for doing so. 
\subsection{CUP - Offline}\label{subsec:offline-alg}

%\textcolor{red}{Please read these Sections carefully!!!}

%\textcolor{red}{use capital or small letters consistently. when random variable capital letter, when not small.}

In the offline setting, we assume access to a held-out calibration dataset $\mathcal{D}_{\text{cal}} = \{(X_i,Y_i,H(X_i))\}_{i=1}^n$ that is exchangeable with the test data $\mathcal{D}_{\text{test}}= \{(X_j,Y_j,H(X_j)))\}_{j=1}^m$.
The goal is to estimate the thresholds $(\hat a, \hat b)$ that implement the two-threshold structure of Theorem~\ref{thm:pred-set}. For each calibration point $(x_i, y_i)$, we compute a non-conformity score $s_i = s(x_i,y_i)$, and separate the scores into two groups according to whether the true label lies in the human set or not. 
The thresholds are then obtained by taking empirical quantiles of these two groups: 
%\textcolor{red}{put this in a box.}
\begin{tcolorbox}
[colback=gray!5!white,colframe=black!70]
$
\hat b = \text{Quantile}_{1-\varepsilon}\!\Big(\{\,s_i : Y_i \in H(X_i)\,\} \cup \{\infty\}\Big),
\qquad
\hat a = \text{Quantile}_{1-\delta}\!\Big(\{\,s_i : Y_i \notin H(X_i)\,\} \cup \{\infty\}\Big).
$
\end{tcolorbox}
Given a new test input $x_{\text{test}}$, the collaborative prediction set is formed as
\[
C(x_{\text{test}}) \;=\; \{\, y :  s(x_{\text{test}},y) \le \hat a \cdot \mathbb{1}\{y \notin H(x_{\text{test}})\} + \hat b \cdot \mathbb{1}\{y \in H(x_{\text{test}})\} \}.
\]
The following Proposition shows these sets satisfy finite-sample guarantees.
%if $n_1$ is the number of calibration points with $Y_i \in H(X_i)$ and $n_2$ the number with $Y_i \notin H(X_i)$, then
%\[
%1-\varepsilon \;\le\; \Pr(Y_{n+1}\in C(X_{n+1}) \mid Y_{n+1}\in H(X_{n+1})) \;<\; 1-\varepsilon + \tfrac{1}{n_1+1},
%\]
%\[
%\delta \;\le\; \Pr(Y_{n+1}\in C(X_{n+1}) \mid Y_{n+1}\notin H(X_{n+1})) \;<\; \delta + \tfrac{1}{n_2+1}.
%\]
%\textcolor{red}{the upperbound typically needs an assumption, like the continuity. and then when writing the Theorem, first only say the lower bounds, as lower bounds only need exchangeability, and then say additionally, if we also assume blah blah, then say the upper bounds.}
\begin{proposition}[Finite-Sample Offline Guarantees]
Let $(X_{n+1}, Y_{n+1}, H(X_{n+1}))$ be a new test point, exchangeable with the calibration data. Let $n_{1}$ be the number of calibration points where $Y_i \in H(X_i)$ and $n_{2}$ the number where $Y_i \notin H(X_i)$. The thresholds $\hat{a}$ and $\hat{b}$ satisfy: 
\[
    \mathbb{P}(Y_{n+1} \in C(X_{n+1}) \mid Y_{n+1} \in H(X_{n+1})) \;\ge\; 1-\varepsilon
\quad \text{and} \quad 
    \mathbb{P}(Y_{n+1} \in C(X_{n+1}) \mid Y_{n+1} \notin H(X_{n+1})) \;\ge\; 1- \delta.
\]
Additionally, if the conformity scores have continuous distribution, then:
\[
\begin{aligned}
\mathbb{P}\!\left(Y_{n+1}\in C(X_{n+1}) \mid Y_{n+1}\in H(X_{n+1})\right)
&< 1-\varepsilon + \frac{1}{n_{1}+1},\\[2pt]
\mathbb{P}\!\left(Y_{n+1}\in C(X_{n+1}) \mid Y_{n+1}\notin H(X_{n+1})\right)
&< 1- \delta + \frac{1}{n_{2}+1}.
\end{aligned}
\]


\label{prop:finite-sample-offline-gaurantee}
\end{proposition}



\iffalse
\begin{proposition}[Finite-Sample Offline Guarantees]
Let $(X_{n+1}, Y_{n+1}, H(X_{n+1}))$ be a new test point, exchangeable with the calibration data. Let $n_1$ be the number of calibration points where $Y_i \in H(X_i)$ and $n_2$ be the number where $Y_i \notin H(X_i)$. The thresholds $\hat{a}$ and $\hat{b}$ satisfy:
\begin{align*}
    1-\varepsilon \le \mathbb{P}(Y_{n+1} \in C(X_{n+1}) \mid Y_{n+1} \in H(X_{n+1})) &< 1-\varepsilon + \frac{1}{n_1+1} \\
    \delta \le \mathbb{P}(Y_{n+1} \in C(X_{n+1}) \mid Y_{n+1} \notin H(X_{n+1})) &< \delta + \frac{1}{n_2+1}
\end{align*}
\label{prop:finite-sample-offline-gaurantee}
\end{proposition}
\fi

%\textcolor{blue}{the flow is natural to me.}
%\textcolor{red}{the flow is still not natural. each sentence should lead to the next one.}

The assumption of exchangeability for lower bound and continuity for upper bounds are both common in the conformal prediction literature (e.g., \cite{vovk2005algorithmic}). 

In practice the assumption of exchangeability is fragile and real-world deployments may inevitably face distribution shifts that undermine the validity of offline guarantees. Such shifts may stem from many sources, but in the context of long-term human-AI collaboration, a particularly salient one is what we call \emph{Human-to-AI Adaptation}. As collaboration unfolds, humans may gradually adjust how they construct their proposed sets $H(x)$ in response to the AI's behavior. For instance, the human might learn over time which types of instances--such as which patients in a medical setting--the AI tends to be more knowledgeable about, and tune their proposals accordingly to be maximally helpful to the final set. In some cases, this may mean proposing larger sets to improve coverage, while in others it may mean offering smaller, more decisive sets to sharpen outcomes. Such feedback loops alter the distribution of test-time data in ways that violate exchangeability between calibration and test sets.  This motivates the need for robustness to evolving distributions in collaborative settings. To address this challenge, we now turn to the \emph{online setting}, which relaxes exchangeability and explicitly allows the data distribution to evolve over time.



%distribution shifts may be inevitable, and the assumption of exchangeability underlying the finite-sample guarantees above can break. These shifts may arise in many forms, but in long-term human-AI collaboration, one particularly interesting source is what we call \textit{human adaptation to AI}:as collaboration unfolds, humans may change how they form their proposed sets H(x) in response to the AI’s behavior. For example, if a human repeatedly observes that the AI rarely includes a certain label, they may gradually stop proposing that label themselves, even if they would have otherwise considered it. Such feedback loops alter the distribution of test-time data in ways that violate exchangeability between calibration and test sets. This makes robustness to distribution shifts especially critical in collaborative settings. To capture this phenomenon, we next study the online setting, which relaxes the exchangeability assumption and explicitly allows the underlying data distribution to evolve over time.

%\textcolor{red}{this should be improved a bit. Start by saying that distribution shifts happen in practice of different form, and exchangeability could break. Then say in our scenario, there is specifically interesting distribution shift that can arise, and then introduce and motivate human to ai adaptation. And then conclude that here it is extra important to think about robustness about shifts and that is what we do next... keep the term long term collaboration ...}




%However, the assumption of exchangeability may not be appropriate in long-term human–AI collaboration. A key challenge is what we call \textit{human adaptation to AI}: as collaboration unfolds, humans may change how they form their proposed sets H(x) in response to the AI’s behavior. For example, if a human repeatedly observes that the AI rarely includes a certain label, they may gradually stop proposing that label themselves, even if they would have otherwise considered it. Such feedback loops alter the distribution of test-time data in ways that violate exchangeability between calibration and test sets. To address this, we next study the online setting, which relaxes the exchangeability assumption and explicitly allows the underlying data distribution to evolve over time.

%However it is natural to assume that  exchangeability assumption may fail in long-horizon collaborative scenarios, under human-AI adaptation assumption, where the human behavior may evolve over time. To address this we now turn to the online setting, which relaxes the echangeability assumption and allows the underlying data distribution to evolve over time. 


%\textcolor{red}{briefly interpret the results and the rates and cite and say this is standard. Then explain and argue for the human adaptation to AI, say what it is, say why it breaks the assumptions here, and prepare the reader for online setting.}

\subsection{CUP - Online}
\label{subsec:online-alg}

%\textcolor{red}{Read this section CAREFULLY again. make sure teh notations names equations, indices, etx are correct and consistent. particularly, check $C_t(x_t)$ and err definitions. i changed them! make sure they are consistent everywhere, here and proof. }

%\textcolor{red}{explain the setting!! at time t we observe $x_t$ and $H(x_t)$ and then we pick the set and the label reveals blah blah ....}
%\textcolor{red}{in this section use small letters for x y as they are not random and they could be adversarial ....}
%\textcolor{red}{it should flow ...}

In this Section, we move to the online setting where data arrives sequentially, one sample at a time. At each round $t$, the test input $x_t$ and the human’s proposed set $H(x_t)$ are provided to the AI, which must then output the final prediction set $C_t(x_t)$. Only after the final prediction set is announced is the true label $y_t$ revealed. Here, we make no assumptions about the distribution of the data stream, an assumption particularly natural for human-AI collaboration, where distribution shift is not merely accidental but may arise directly from the interaction itself.


% Our online algorithm, CUP (online), adapts the thresholds round by round with a simple update rule, ensuring that the long-run error rates converge to their targets.


% In the online setting, data arrive sequentially, one point at a time. This setting captures an interactive process where the human’s behavior and the data itself may itself change over time, which breaks the exchangeability assumption used with a fixed calibration set and offline guarantees are no longer sufficient. This setting is particularly natural for human–AI collaboration, where distribution shift is not just accidental but can arise as a direct consequence of the interaction.

We design an online algorithm, CUP--Online, that makes prediction sets of the form, $$C_t(x_t) = \big\{y\in\mathcal{Y}\,\mid\, s(x_t, y) \leq a_t\,\mathbf{1}\{y\notin H(x_t)\}\,+b_t\,\mathbf{1}\{y\in H(x_t)\}\, \big\},$$
where $s(., .)$ is a fixed non-conformity score (look at Section \ref{Sec:score}), and $(a_t, b_t)$ are the two thresholds that we will update in an online fashion. Let us also define
%\textcolor{red}{this notation is still not ideal. now it looks like err to power 2:). I like the 1 and 2 notation, but maybe put 1 and 2 somewhere else. alternatively, you can also use 'in' and 'out', for y in H and y out of H. that is also nice. That you can put in top right without confusion, maybe do that?}
\[
\mathrm{err}^{\mathrm{in}}_{t} := \mathbf{1}\{y_t \notin C_t(x_t),\ y_t \in H(x_t)\}, \quad
\mathrm{err}^{\mathrm{out}}_{t}  := \mathbf{1}\{y_t \notin C_t(x_t),\ y_t \notin H(x_t)\}.
\]
% handles this challenge but adapting the thresholds $(a_t, b_t)$ round by round with a simple online update so that the long-run error rates converge to their targets. At each time step $t$, we first observe the new test input $x_t$ along with the human proposed set $H(x_t)$. Then, based on this information and the current thresholds $(a_t,b_t)$, the algorithm outputs a collaborative prediction set $C_t(a_t,b_t)$. After this set is chosen, the true label $y_t$ is revealed and we use this feedback to update the thresholds for the next round.

% To guide the updates, we track two types of error. A \textbf{counterfactual harm error} occurs when the true label was in the human's set but excluded by the collaborative set. A \textbf{complementarity error} occurs when the true label was not in the human's set and also not recovered by the collaborative set. Formally, with $s(x, y) = 1 - p(y \mid x)$ as the nonconformity score, we recursively define the sequence of these two errors:

%To handle this, we study an online setting, where the data arrive sequentially and the dsitirbution including human behavior may evolve oveer time. Our goal is to design an online algorithm that maintains the similar gaurantees as in the offline case, but now under a fully dynamic and potentially non-stationary environemnt.

%We design an online algorithm, CUP-online, that adapts the thresholds $(a_t, b_t)$ round by round with a simple online update so that the long-run error rates converge to their targets. 

%This update starts by examining the empirical miscoverage frequency of the previous prediction sets for each of the constraints and then decreasing (resp. increasing) our thresholds if the prediction sets were historically undercovering ( resp. over-covering) with respect to our counterfactual harm and complementarity constraints. 
%At each time step $t$, let $s(x, y) = 1 - p(y \mid x)$ be the conformity score. We recursively define the sequence of two kind of errors:

%The first is a \emph{counterfactual harm} error (we excluded the true label even though the human had it), and the second is a \emph{complementarity} error (we excluded the true label when the human missed it).

Then, fixing a learning rate $\eta > 0$, CUP--Online updates only one threshold at a time, depending on whether the human included the true label in their proposed set.
\begin{tcolorbox}[colback=gray!5!white, colframe=black!70, boxrule=0.4pt]
\[
\begin{aligned}
if \quad y_t \in H(x_t): & \quad b_{t+1} = b_t + \eta\left( \mathbf{1}\{s(x_t, y_t) > b_t\} - \varepsilon \right), \quad a_{t+1} = a_t \\
if\quad y_t \notin H(x_t): & \quad a_{t+1} = a_t + \eta\left( \mathbf{1}\{s(x_t, y_t) > a_t\} - \delta \right), \quad b_{t+1} = b_t
\end{aligned}
\]
\end{tcolorbox}

%If $Y_t \in H(X_t)$, we update $b_t$ to keep the counterfactual harm rate close to $\varepsilon$:  

%\textcolor{red}{Put the updates in one box, no text inside the box. Structure in a way that inside the box there is the update rules for a and b.}

%\[
%b_{t+1} = b_t + \eta(\mathbf{1}\{s(Y_t|X_t) > b_t\} - \varepsilon), \qquad a_{t+1} = a_t.
%\]
%If $Y_t \notin H(X_t)$, we update $a_t$ to keep the advantage rate close to $\delta$:  
%\[
%a_{t+1} = a_t + \eta(\mathbf{1}\{s(Y_t|X_t) %> a_t\} - (1-\delta)), \qquad b_{t+1} = b_t.
%\]
Intuitively, if errors occur more often than expected, the threshold is relaxed to include more labels, if errors are too rare, the threshold is tightened. Over time this feedback process drives the empirical error rates toward their target values $\varepsilon$ and $\delta$. The choice of $\eta$ gives a tradeoff between adaptability and stability, while larger values will make the method more adaptive to observed distribution shifts (this will also show up in our guarantees) they also induce greater volatility in thresholds values, which may be undesirable in practice as it will allow the method to fluctuate between smaller sets to larger sets. Hence, in practice, a careful hyperparameter tuning for $\eta$ can enhance the performance of CUP--Online. We now outline the theoretical guarantees of our online algorithm.

% \subsubsection{Theoretical Guarantees}

 

%with bounded parameters, the long-run error rates converge to the desired values:  
%\textcolor{red}{mention all the assumptions precisely, like boundedness of score. Also, you might want to discuss briefly somewhere that how this assumption holds for regression...}

\begin{proposition}[Finite-Sample Online Guarantees]
Assume the conformity is bounded, i.e, $s(x,y) \in[0,1]$ and let
$N_1(T) = \sum_{t=1}^T \mathbf{1}\{y_t \in H(x_t)\}$ and $N_2(T) = \sum_{t=1}^T \mathbf{1}\{y_t \notin H(x_t)\}$. For any $T \ge 1$:
\[
\left| \frac{1}{N_1(T)} \sum_{t=1}^T \mathrm{err}^{\mathrm{in}}_{t} - \varepsilon \right|
\le \frac{1 + \eta \max(\varepsilon, 1-\varepsilon)}{\eta N_1(T)}, \quad
\left| \frac{1}{N_2(T)} \sum_{t=1}^T \mathrm{err}^{\mathrm{out}}_{t} - \delta \right|
\le \frac{1 + \eta \max(\delta, 1-\delta)}{\eta N_2(T)}.
\]

%\textcolor{red}{in the above, there is typo in err, the t indice is missing. make sure this does not happen elsewhere. Check the proof too ...}

%\textcolor{red}{the rest need to be explained to me! Maybe explain in words after the Theorem.}

In particular, if $N_1(T), N_2(T) \to \infty$, then almost surely
\[
\lim_{T\to\infty} \frac{1}{N_1(T)} \sum_{t=1}^T \mathrm{err}^{\mathrm{in}}_{t}  = \varepsilon, \qquad
\lim_{T\to\infty} \frac{1}{N_2(T)} \sum_{t=1}^T \mathrm{err}^{\mathrm{out}}_{t}  = \delta.
\]
\label{thm:finite-sample-online-gaurantees}
\end{proposition}
\begin{remark}
The boundedness assumption on the conformity score holds automatically in classification when $s$ is derived from a probability output (e.g., a softmax score, which lies in $[0,1]$). In regression, where scores may be unbounded, this condition can be enforced by rescaling and clipping the score.
\end{remark}
% Propostion~\ref{thm:finite-sample-online-gaurantees} guarantees that over-time the algorithm will calibrate itself so that the long-run error rates converge to the desired target rates $\varepsilon$ and $1 -\delta$. %\textcolor{red}{ 1-delta is coverage ... please check carefully}. 
% This kind of guarantee is typical in online conformal literature including \cite{gibbs2021adaptiveconformalinferencedistribution,angelopoulos2023conformalpidcontroltime}. 

%Together, these results say the algorithm self-adjusts: the thresholds never blow up, and over time the fraction of CH and advantage errors converges to the desired levels $(\varepsilon,\delta)$. 


%\textcolor{red}{explain properly how this is addressing human AI adaptation.}

These types of update rules and guarantees are common in the online conformal prediction literature for controlling marginal coverage \citep{gibbs2021adaptiveconformalinferencedistribution, angelopoulos2023conformalpidcontroltime}. We extend these ideas to simultaneously control counterfactual harm and complementarity rates.  Our results show that over long intervals, CUP--online achieves the desired rates without any assumption on the data-generating distribution. In particular, the algorithm addresses human–to-AI adaptation, among other shifts, by decoupling validity from assumptions about human behavior. By tracking how human proposals interact with prediction set errors and adjusting its thresholds accordingly, CUP--online ensures that the target error rates are maintained, even as human strategies evolve over time.

%his means our method remains valid even when the data stream is non-exchangeable and the human’s strategy changes with time.
\section{Experiments}
\label{sec:experiments}
First, we outline our experimental setup, and then evaluate our framework across three distinct data modalities:  (i) image classification, (ii) real-valued regression, and (iii) text based medical decision-making with large language models. For each modality, we study both the offline and online algorithms introduced in Section~\ref{sec:finite-sample-alg}.
%(i) \emph{images} for classification, (ii) \emph{tabular features} for regression, and (iii) \emph{text} for decision-making with large language models. For each modality, we study both the offline and online algorithms introduced in Section~\ref{sec:finite-sample-alg}. The experimental details are provided in the subsections that follow.

\textbf{Baselines.} We compare against the following natural baselines:  
\begin{itemize}
\item \textit{Human alone.} This baseline uses the human-proposed set $H(x)$ directly, without any AI refinement. 
    We treat the human policy as a black box and make no assumptions about how the sets are generated. Coverage depends entirely on the provided sets and may vary with human expert quality. %\textcolor{red}{last sentence is not ading anything, drop it?}.
    These human sets are constructed using crowd-sourced annotations, rule-based diagnostic systems or synthetic noise, depending on the task. Full details are provided in each experiment subsection. % We describe how the sets are constructed in each experiment-specific subsection. \textcolor{red}{maybe briefly say about the high level idea of how human sets are created. Crowd sourcing for some and adding noise blah blah for the other} 
    \item \textit{AI alone.} Uses the AI system without incorporating human input, reducing to standard conformal prediction based solely on the model scores. This provides a benchmark for how well the AI performs independently.
    Additionally, in the online setting we consider a fixed baseline that serves as a reference point for detecting and evaluating distribution shifts. This method uses a static set of thresholds computed from an initial subset of data (i.e early examples or a dedicated split), and then applies these thresholds over the online data stream without any further updates. This baseline provides a useful comparison to understand the value of adaptivity in the online setting.
\end{itemize}
\textbf{Evaluation metrics.} Across all experiments, we evaluate methods based on two key quantities: \emph{marginal coverage}, the probability that the true label lies in the prediction set, and \emph{average set size}, measured as cardinality in classification and interval length in regression. In the online setting, we use \emph{running} versions of these metrics, defined at each time step $t$ as $\widehat{\mathrm{cov}}_t = \frac{1}{t} \sum_{i=1}^t \mathbf{1}\{y_i \in C(x_i)\}$ for marginal coverage and $\widehat{\mathrm{size}}_t = \frac{1}{t} \sum_{j=1}^t |C(x_j)|$ for average set size.
%the expected cardinality (for classification) or length (for regression) \textcolor{red}{funky sentence}.
These metrics capture the central tradeoff in uncertainty quantification: higher coverage is desirable, but must be balanced against set informativeness. Our algorithm does not explicitly enforce a fixed marginal coverage. Instead, the counterfactual harm parameter $\varepsilon$ and the complementarity parameter $\delta$ shape the resulting coverage and set size. By adjusting these parameters, we can navigate tradeoffs between the two metrics.


A successful human–AI collaboration should improve upon the human baseline in at least one dimension, coverage or set size, without significantly worsening the other. For example, it may increase coverage while avoiding large increases in set size, or shrink the set without losing coverage. In the best case, both metrics improve together. The better the AI model, the more effectively it should recover missed outcomes without unnecessarily inflating sets. Similarly, the stronger the human baseline, the better the collaborative procedure can perform, since it starts from a higher-quality initial proposal. Thus our framework reflects the complementary contributions of both human and AI, and we will explore this dependence on human and AI quality across our experimental tasks.

%is one that improves on the human baseline in at least one dimension without substantially worsening the other. Ideally, collaborative sets increase coverage without bloating the set size, or reduce set size without sacrificing accuracy. In the best case, both metrics improve simultaneously.

%should improve upon the human baseline in at least one of the two dimensions, coverage or set size, without making the other much worse. For example, a good collaboration might increase coverage while avoiding large increases in set size, or shrink the set without losing coverage. In the best case, both metrics improve together. The better the AI model, the more effectively it should recover missed outcomes without unnecessarily inflating sets. Similarly, the stronger the human baseline, the better the collaborative procedure can perform, since it starts from a higher-quality initial proposal. Thus our framework naturally reflects the complementary contributions of both human and AI, and we will explore this dependence on human and AI quality across our experimental tasks.


%by raising coverage while avoiding large increases in set size. 
%The better the AI model, the more effectively it should recover missed outcomes without unnecessarily inflating sets. 
%Similarly, the stronger the human baseline, the better the collaborative procedure can perform, since it starts from a higher-quality initial proposal. 
%Thus our framework naturally reflects the complementary contributions of both human and AI, and we will explore this dependence on human and AI quality across our experimental tasks.
\subsection{Classification: ImagetNet-16H}

Our first set of experiments use the ImageNet-16H dataset \citep{imagenet16h}, which captures human prediction behavior under varying perceptual noise. It consists of 32,431 human predictions on 1,200 natural images, each annotated by multiple participants and perturbed with one of four noise levels $\omega \in \{80, 95, 110, 125\}$ that progressively increase task difficulty. The label space is restricted to a fixed set of 16 classes. For the AI component, we use a pre-trained VGG19 classifier \citep{simonyan2015deepconvolutionalnetworkslargescale} fine-tuned for 10 epochs. We evaluate our framework an offline setting and subsequently in an online setting, where we introduce various distribution shifts.

%We evaluate our framework using a pre-trained VGG19 \citep{classifiersimonyan2015deepconvolutionalnetworkslargescale} %(\textcolor{red}{maybe cite what model?})
%fine-tuned for 10 epochs, first in the offline setting and then moving to the online setting under various distribution shifts. \textcolor{red}{the sentence looks a bit confusing to me.}
%Our first set of experiments is conducted on the ImageNet-16H dataset, a image classification task designed to capture human prediction behavior under varying levels of perceptual noise. 
%It consists of 32,431 human predictions on 1,200 natural images, each annotated by multiple participants and perturbed with one of four noise levels $\omega \in {80, 95, 110, 125}$ that progressively increase task difficulty. The label space is restricted to a fixed set of 16 classes.
%Each image is perturbed with one of four phase noise levels $\omega \in \{80, 95, 110, 125\}$, which progressively increase the difficulty of the classification task. 
%The label space is restricted to $L=16$ categories. 
%We evaluate our framework using a pre-trained AlexNet classifier fine-tuned for 10 epochs. We begin with the offline setting, where  calibration and test batches are drawn from the same noise level. We then move to the online setting where we introduce various distribution shifts over time and assess how our online algorithm adapts. 
%Following prior work, we evaluate our framework using multiple pre-trained classifiers that are fine-tuned for 10 epochs, including VGG19, DenseNet161, GoogleNet, ResNet152, and AlexNet. 
%In the main text we present results with VGG19, while results for the other architectures are reported in the appendix.  
%\subsubsection{offline results}
%\label{subsec:imagenet-offline-experiments}
\textbf{Offline Setting.}
We compare three approaches: \emph{Human Alone}, \emph{AI Alone}, and CUP-offline. Results are averaged over 10 random calibration/test splits. Table~\ref{tab:imagenet-main} reports coverage and set size under two representative noise levels, $\omega=95$ and $\omega=125$. For the human baseline, we aggregate multiple annotations into empirical label frequencies and form top-$k$ sets by selecting the $k$ most frequently chosen labels. From the algorithm’s perspective, only the sets—not raw annotations or confidences—are observed. The AI baseline applies standard conformal prediction without human input. Since conformal methods allow direct control over target coverage, we evaluate AI Alone at the same realized coverage achieved by CUP-offline. This ensures a fair comparison, where the only meaningful dimension for improvement is set size (i.e., if CUP achieves the same coverage with smaller sets, it shows that human input is being used effectively to tighten predictions).
CUP-offline incorporates both sources, with coverage and size determined by $(\varepsilon,\delta)$ parameters that encode counterfactual harm and complementarity.
%In the offline experiments, we compare three approaches to constructing prediction sets: \emph{Human Alone}, \emph{AI Alone}, and our offline Collaborative Uncertainty Prediction (CUP-offline) algorithm. Each result is averaged over 10 random splits of the calibration and test sets. Table~\ref{tab:imagenet-main} summarizes the performance under two representative noise levels, $\omega = 95$ and $\omega = 125$.
%Table~\ref{tab:imagenet-main} reports results for two different noise levels using VGG19, with all numbers averaged over 10 random calibration/test splits. 
%The table compares three methods: \emph{Human Alone}, \emph{AI Alone}, and our collaborative procedure (HAI). 


%For the human baseline, we adopt a top-$k$ strategy. Given multiple annotations per image, we aggregate human responses into empirical label frequencies and include the top $k$ most frequently selected labels. Importantly, from the algorithm’s perspective, we only observe the final prediction sets—not the raw annotations or any probabilities. The human is treated as a black box.


%In the AI Alone case, we run standard conformal prediction using the AI model exclusively, without incorporating any human input. 
%Lastly we apply our proposed finite-sample offline algorithm: CUP (offline). 
%For each method, we report both the marginal coverage achieved and the average prediction set size. 
%It is important to note that for CUP, marginal coverage is not controlled directly; rather, the configuration of $(\varepsilon,\delta)$—which correspond to the counterfactual harm and complementarity constraints—governs the trade-off between the realized coverage and set size. 
%We present representative $(\varepsilon,\delta)$ settings in the main text and defer additional configurations to the appendix.

\begin{table*}[h]
\centering
\small
\begin{subtable}{0.95\textwidth}
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{lcc | cccc | cc}
\toprule
\multicolumn{9}{c}{\textbf{$\omega$ = 125}} \\
\toprule
 & \multicolumn{2}{c|}{\textbf{Human Alone}} 
 & \multicolumn{4}{c|}{\textbf{CUP}} 
 & \multicolumn{2}{c}{\textbf{AI Alone}} \\
\cmidrule(lr){2-3} \cmidrule(lr){4-7} \cmidrule(lr){8-9}
Strategy & Coverage & Size 
         & Coverage & Size & $\varepsilon$ & $\delta$
         & Coverage & Size \\
\midrule
Top-2 
& $0.8008 \pm 0.0090$ & $2.00 \pm 0.00$
& $\mathbf{0.9022 \pm 0.0083}$ & $\mathbf{1.49 \pm 0.04}$ & $0.05$ & $0.70$
& $0.9072 \pm 0.0138$ & $1.65 \pm 0.07$ \\
Top-1 
& $0.7245 \pm 0.0103$ & $1.00 \pm 0.00$
& $\mathbf{0.8823 \pm 0.0134}$ & $1.36 \pm 0.07$ & $0.05$ & $0.70$
& $0.8828 \pm 0.0140$ & $1.48 \pm 0.05$ \\
\bottomrule
\end{tabular}}
%\caption{VGG19, noise = 125}
\end{subtable}

\vspace{0.4em} % small gap between subtables

\begin{subtable}{0.95\textwidth}
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{lcc | cccc | cc}
\toprule
\multicolumn{9}{c}{\textbf{$\omega$ = 95}} \\
\toprule
 & \multicolumn{2}{c|}{\textbf{Human Alone}} 
 & \multicolumn{4}{c|}{\textbf{CUP}} 
 & \multicolumn{2}{c}{\textbf{AI Alone}} \\
\cmidrule(lr){2-3} \cmidrule(lr){4-7} \cmidrule(lr){8-9}
Strategy & Coverage & Size 
         & Coverage & Size & $\varepsilon$ & $\delta$
         & Coverage & Size \\
\midrule
% <-- plug in numbers for this noise/model combo
Top-2 
& $0.9613 \pm 0.0061$ & $2.00 \pm 0.00$
& $\mathbf{0.9825 \pm 0.0066}$ & $\mathbf{1.77 \pm 0.44}$ & $0.01$ & $0.80$
& $0.9830 \pm 0.0061$ & $2.10 \pm 0.15$ \\
\addlinespace
Top-1 
& $0.9257 \pm 0.0060$ & $1.00 \pm 0.00$
& $\mathbf{0.9763 \pm 0.0076}$ & $1.43 \pm 0.07$ & $0.01$ & $0.80$
& $0.9755 \pm 0.0053$ & $2.27 \pm 0.21$ \\
\bottomrule
\end{tabular}}
%\caption{ResNet152, noise = 95}
\end{subtable}

\caption{\textbf{ImageNet-16H – Offline Results:} Comparison of Human, AI, and CUP under two noise levels. Reports marginal coverage and average set size (mean ± std over 10 splits). CUP uses calibration parameters \((\varepsilon,\delta)\).}


\label{tab:imagenet-main}
\end{table*}



We include two noise levels to evaluate performance under varying task difficulty for the human experts. As shown in Table~\ref{tab:imagenet-main}, across both levels, our CUP-offline consistently improves on the human baseline. When the human sets are relatively large(e.g top -2), CUP-offline yields strict improvements in both dimensions, reducing set size while improving coverage. At $\omega=125$, for example, human top-2 sets cover 80\% of labels with size 2.0, whereas CUP-offline improves coverage to 90\% while reducing size to 1.49.
When human sets are very small (e.g., top-1), coverage improvements typically requires adding labels, slightly increasing set size. Even then, CUP-offline offers more efficient sets than AI Alone, leveraging human input to achieve better tradeoffs. At $\omega = 95$, for example, CUP-offline achieves 97.6\% coverage with an average size of 1.43, whereas AI Alone requires size 2.27 for similar coverage. Overall, CUP-offline improves on raw human sets and produces tighter predictions than AI Alone, adapting to the strengths and limits of each source to provide a clear advantage over both baselines.
%: at lower noise level, human achieve higher coverage, while at higher noise, performance deteriorates. For example, under $\omega = 95$, the top-2 human sets capture the true label roughly 96\% of the time, whereas under $\omega = 125$, this drops to around 80\%.%Our findings show that across both representative settings, our collaborative method consistently improves on the human baseline. When the human sets are relatively larger(e.g top -2), CUP is able to yield strict improvements in both of the evaluation dimensions, reducing set size while improving coverage. For instance, at $\omega = 125$, the top-2 human sets achieve 80\% coverage with an average size of 2.0, CUP boosts coverage to 90\% while shrinking the average set size to 1.49. %When human sets are very small (e.g., top-1), improving coverage typically requires adding labels, which slightly increases the set size. Yet in this regime, CUP offers more efficient sets than AI Alone, showing that the human input can be effectively utilized for improved performance. At $\omega = 95$, for example, CUP achieves 97.6\% coverage with an average size of 1.43, whereas AI Alone requires larger sets (size 2.27) to reach similar coverage.
%Overall, these results demonstrate the benefits of collaborative uncertainty quantification. Our method reliably improves upon the raw human sets and achieves tighter prediction sets than AI Alone. It adapts to the strengths and limitations of each source and provides a meaningful advantage over both baselines.
%As expected, the quality of the human predictions depends strongly on the noise level: at lower noise ($\omega = 95$), humans achieve substantially higher coverage than at higher noise ($\omega = 125$), reflecting the increased difficulty of the task under heavier perturbations. 
%Across both conditions, however, our method consistently improves upon the human sets. 
%Coverage gains emerge naturally as the algorithm prunes unnecessary labels from the human proposals while augmenting them with the true label whenever it is missing. 
%This effect is clear at $\omega = 125$ under the top-2 strategy, where coverage rises from $0.80$ to $0.90$ while the average set size drops from $2.0$ to $1.49$. 
%When human sets are very small, as in the top-1 strategy, raising coverage necessarily requires adding labels and therefore slightly increases set size. 
%Yet even in these cases, HAI produces more efficient sets than AI alone. 
%For instance, at $\omega = 95$, HAI attains $0.976$ coverage with an average size of $1.43$, whereas AI alone requires significantly larger sets (size $2.27$) to reach a similar coverage level. 
%Overall, these results demonstrate that our collaborative procedure leverages human input effectively: it consistently improves upon the raw human sets and achieves more compact prediction sets than AI alone, yielding meaningful gains over both baselines.

%It is important to note that naturally, the quality of the human predictions depends strongly on the noise level: at lower noise ($\omega = 95$), humans achieve substantially higher coverage than at higher noise ($\omega = 125$), reflecting that the task is easier for the human experts when images are less degraded. 

%Across both conditions, however, our method consistently improves upon the human sets. 
%Although the algorithm does not directly optimize for marginal coverage, coverage increases emerge naturally through the calibration parameters $(\varepsilon,\delta)$, which govern how aggressively we prune or augment the human proposals. 
%When the human sets contain unnecessary labels, our procedure prunes them away while still recovering the true label when it is missing, thereby achieving higher coverage with smaller prediction sets. 
%This is evident at $\omega = 125$ in the top-2 case, where coverage rises from $0.80$ to $0.90$ while the average set size drops from $2.0$ to $1.49$. 
%In other cases, particularly when the initial human sets are very small (e.g., top-1), increasing coverage requires adding labels, which naturally increases the set size slightly. 
%Yet even in these settings, HAI remains more efficient than AI alone: for instance, at $\omega = 95$ in the top-1 case, our method achieves coverage of $0.98$ with size $1.43$, whereas AI alone requires significantly larger sets (size $2.27$) to reach a similar coverage level. 
%Overall, these findings demonstrate that our collaborative procedure is able to leverage human input effectively: it raises coverage beyond what the human achieves on its own, while producing more compact sets than AI alone, thereby yielding meaningful gains over both baselines.


%\begin{itemize}
    %\item \textbf{Effect of noise.} Human performance improves at lower noise levels. For instance, at $\omega = 95$, humans achieve higher coverage than at $\omega = 125$. This reflects the fact that cleaner images make the classification task easier for human annotators. 

    %\item \textbf{Collaborative gains.} Our collaborative procedure (HAI) consistently improves upon the initial human sets. Even though the algorithm does not directly optimize marginal coverage, coverage increases emerge naturally through the calibration parameters $(\varepsilon,\delta)$. When $\varepsilon$ is set small and $\delta$ large, the procedure tends to add true labels that humans missed, thereby raising coverage.  

    %\item \textbf{Pruning and augmentation.} In many cases, HAI not only increases coverage but also reduces set size. For example, at $\omega = 125$ in the top-2 setting, human sets have coverage $0.80$ with size $2.0$, while HAI achieves coverage $0.90$ with size $1.49$. This occurs because the algorithm prunes incorrect labels from the human proposal while augmenting it with the correct label exactly when needed.  

    %\item \textbf{Tradeoffs when sets are small.} When human sets start very small (e.g., top-1), increasing coverage necessarily requires adding labels, which leads to a modest increase in set size. Crucially, however, HAI achieves these coverage gains more efficiently than AI alone. For example, at $\omega = 95$, HAI raises coverage to $0.976$ with size $1.43$, whereas AI alone requires much larger sets (size $2.27$) to reach a similar coverage level.  

    %\item \textbf{Efficiency compared to AI alone.} Across both noise conditions, we find that HAI produces smaller sets than AI alone at matched coverage levels. This demonstrates that leveraging human input, even when imperfect, leads to more efficient sets than relying on the AI in isolation.
%\end{itemize}

%\subsubsection{online results}
%\label{subsec:imagenet-online-experiments}
\textbf{Online Setting.}
We now turn to the online setting, where the data arrives sequentially and distributional shifts may occur during deployment.
We consider two types of shifts: a \emph{noise shift}, where inputs are ordered from high to low noise levels ($\omega = 125 \rightarrow 95$), and a \emph{human strategy shift}, where human prediction sets evolve from top-2 to top-3 strategies. The latter serves as a concrete instance of what we term \emph{Human-to-AI Adaptation} which is this case is how humans might adapt their behavior in response to increasing task difficulty or AI feedback. 


%we calibrate at $\omega=80$ and then evaluate on a stream moving from higher noise to lower levels ($\omega=125,110,95$). The second is a \emph{human strategy shift},  where we calibrate on human prediction sets constructed using a top-1 strategy, then evaluate on a stream where humans provide larger sets (e.g., top-2 or top-3). This serves as a concrete instance of what we term \emph{Human-to-AI Adaptation} which is this case is how humans might adapt their behavior in response to increasing task difficulty or AI feedback. 


\begin{figure}[h!]
    \centering
    % Left column
    \begin{minipage}[c]{0.48\linewidth}
        \includegraphics[width=\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-eps-0.01-delta-0.4-runningcov-humanshift.png}
        \includegraphics[width=\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-baselines-eps-0.01-delta-0.4-humanshift.png}
    \end{minipage}%
    \hfill
    % Vertical line
    \vrule width 1pt
    \hfill
    % Right column
    \begin{minipage}[c]{0.48\linewidth}
        \includegraphics[width=\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-eps-0.01-delta-0.4-runningcov-noiseshift.png}
        \includegraphics[width=\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-baselines-eps-0.01-delta-0.4-noiseshift.png}
    \end{minipage}
    
    \caption{\textbf{ImageNet-16H- Online Results:} 
Performance under human strategy shift (left) and noise shift (right). Top: running coverage for CUP-online vs fixed baseline. Bottom: CUP-online vs human-only and AI-only baselines on running set size and marginal coverage.}
\label{fig:online-imagenet-eps-delta}

\end{figure}
%and then evaluate on a stream from the highest noise level and moving to progressively lower ones: $\omega \in {125, 110, 95}$; this simulates a shift in the underlying data distribution as images become harder or easier to classify over time. 

%The second shift that we consider is the \emph{Human strategy shift} where  we calibrate on human prediction sets constructed using a top-1 strategy, then evaluate on a stream where humans provide larger sets (e.g., top-2 or top-3). This models how humans might adapt their behavior in response to increasing task difficulty or AI feedback. In short, we vary the size of the human proposal set $H(x)$ over time by varying number of $k$ labels in the set.

%In the appendix we further evaluate our algorithm under an induced label-shift. 

%that uses the same thresholds $(a, b)$ selected during calibration but holds them constant throughout the stream.

%\textcolor{red}{what are the initial calibration values? what does it mean? looks confusing.}. \textcolor{red}{all the following explanation about the metric sounds like might appear multiple time for each online setup, explain the metrics once in the beginning, tehn just use and interpret the results.}

We first compare CUP-online to the fixed baseline tuned on a separate segment of the data stream. For instance, in the noise shift setting, we tune $(a, b)$ on $\omega=80$, and for the human shift, on top-1 human prediction sets. To evaluate, we track \emph{constraint-specific coverage} over time. At each time step $t$, we compute $
{\mathrm{cov}}^{*}_t = 1 - 1/t \sum_{i=1}^t 1- \mathrm{err}_i^*,
$ where $\mathrm{err}_i^*$ is either a counterfactual harm error or a complementarity error defined in Section~\ref{subsec:online-alg}. Intuitively, this metric tracks how well the algorithm maintains the target coverage level over time. When the algorithm is effective, this running estimate converges to the nominal targets $1-\varepsilon$ and $1 - \delta$. 

%To evaluate performance, we use the following \emph{running coverage} metric. At each time step $t$, we compute $
%{\text{Cov}}_t = 1 - 1/t \sum_{j=1}^t 1- \text{err}_j,$
%where $\text{err}_j$ indicates an error under the constraint being enforced—either a \emph{counterfactual harm error}or a \emph{complementarity error} defined in Section~\ref{subsec:online-alg}. Intuitively, this metric tracks how well the algorithm maintains the target coverage level over time. When the algorithm is effective, this running estimate converges to the nominal targets $1-\varepsilon$ and $\delta$. 
Figure~\ref{fig:online-imagenet-eps-delta} (top row) shows the results for both forms of distribution shift: human strategy shift (left) and noise shift (right). In both cases, the online algorithm remains close to the target coverage levels throughout the stream, while the fixed baseline drifts away and fails to recover from the changes in the underlying distribution. In the bottom row of Figure~\ref{fig:online-imagenet-eps-delta}, we compare CUP-online with human-only and AI-only baselines, using the running marginal coverage and set size metrics defined earlier. For a fair comparison, we run the AI-only baseline at a target coverage level matched to the realized coverage achieved by CUP-online across the full stream. 
%Since AI-only conformal methods allow direct control over coverage, the only meaningful dimension for improvement in this comparison is set size. In other words, if CUP achieves the same coverage with smaller sets, it shows that human input is being used effectively to tighten the prediction sets.
The results show that CUP-online consistently improves over the human baseline by achieving higher coverage while keeping the prediction sets small. Compared to AI alone, where coverage is matched by design, CUP-online produces more compact sets. These trends mirror those seen in the offline setting, showing that our online collaborative procedure maintains the advantages of the framework under distribution shift. 

%show that the adaptive method remains close to the desired targets under both forms of shift, while the fixed baseline drifts away and fails to recover form the changes in the underlying distribution.



\iffalse
\begin{figure}[htp!]
    \centering
    % Top row: Human strategy shift
    \makebox[0.98\linewidth][c]{\textbf{Human Strategy shift}} \\[0.2em]
    \includegraphics[width=0.49\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-humanshift-eps0.01-delta0.4-running-epscov.png}
    \includegraphics[width=0.49\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-humanshift-eps0.01-delta0.4-running-deltacov.png} \\
    \makebox[0.98\linewidth][c]{\textbf{Noise shift}} \\[0.2em]
    % Bottom row: Noise shift
    \includegraphics[width=0.49\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-noiseshift-eps0.01-delta0.4-running-epscov.png}
    \includegraphics[width=0.49\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-noiseshift-eps0.01-delta0.4-running-deltacov.png}
    
    \caption{\textbf{Online results on ImageNet-16H under distribution shift.} 
    Top row: \emph{Human strategy shift}, where calibration is performed on top-1 human sets and testing is on top-2 and top-3 sets ($\varepsilon=0.01$, $\delta=0.4$).  
    Bottom row: \emph{Noise shift}, where calibration is performed at noise level $\omega=80$ and testing on $\omega \in \{95, 110, 125\}$ ($\varepsilon=0.05$, $\delta=0.8$, $k=2$).  
    Each panel shows the running conditional coverage over time, with the left plots corresponding to the counterfactual harm constraint $P(Y \in C(X) \mid Y \in H(X)) \geq 1-\varepsilon$ and the right plots to the complementarity constraint $P(Y \in C(X) \mid Y \notin H(X)) \geq\delta$.}
    \label{fig:online-imagenet-eps-delta}
\end{figure}
\fi

%We then compare HAI (online) against the human-only and AI-only baselines. For AI alone, we match its average coverage across the full stream to that achieved by HAI, ensuring fair comparison at the same realized coverage level. 
%We track both the running overall marginal coverage,$
%\widehat{\text{Coverage}}^{\text{marg}}_t = 1 - \frac{1}{t} \sum_{j=1}^t \1\{Y_j \notin C(X_j)\},
%$
%and the running average set size,
%$
%\widehat{\text{Size}}_t = \frac{1}{t} \sum_{j=1}^t |C(X_j)|.
%$
%As before, $(\varepsilon,\delta)$ are fixed to values that produce stable trends, with other configurations reported in the appendix. 
%\textcolor{red}{need to explain details, placeholder for now}The results (Figure~\ref{fig:online-imagenet-baselines}, bottom) demonstrate that HAI consistently improves coverage over the human baseline while producing smaller sets than AI alone at matched coverage, showing that our collaborative approach yields gains over both baselines in dynamic environments.
\iffalse
\begin{figure}[htp!]
    \centering
    % Row header: Human strategy shift
    \makebox[0.98\linewidth][c]{\textbf{Human strategy shift}} \\[0.2em]
    \includegraphics[width=0.49\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-humanshift-eps0.01-delta0.4-Baselines-marginal-cov.png}
    \includegraphics[width=0.49\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-humanshift-eps0.01-delta0.4-Baselines-set-size.png} \\[0.8em]
    % Row header: Noise shift
    \makebox[0.98\linewidth][c]{\textbf{Noise shift}} \\[0.2em]
    \includegraphics[width=0.49\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-noiseshift-eps0.01-delta0.4-Baselines-marginal-cov.png}
    \includegraphics[width=0.49\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-noiseshift-eps0.01-delta0.4-Baselines-set-size.png}
    
    \caption{\textbf{HAI vs AI alone vs Human alone - online results on ImageNet-16H under distribution shift.}  
    Each row shows the running overall marginal coverage (left) and the running average set size (right).  
    Our adaptive HAI method outperforms both the human-only and AI-only baselines, improving coverage without inflating set sizes.}
    \label{fig:online-imagenet-baselines}
\end{figure}

\fi


\iffalse
We now evaluate the online version of our algorithm on ImageNet-16H. 
The goal of this experiment is to test whether the adaptive updates maintain the conditional coverage guarantees over time, even under distribution shift. 
We induce shift by calibrating on a subset of the data and then evaluating on test examples with different noise levels $\omega$, which changes the difficulty of the task. We evaluate our algorithm under various distributions shifts, such as human-strategy shift and class-label shift in the appendix.

We compare our method to a non-adaptive baseline that keeps the thresholds $(a,b)$ fixed at their initial calibration values. 
To assess performance, we examine the \emph{local conditional coverage frequencies}, defined as the average coverage rate over the most recent $W=500$ examples:  

computed separately for the two conditional events $Y \in H(X)$ and $Y \notin H(X)$. 
If the method performs well, these local coverage frequencies should remain close to their target levels, namely $1-\varepsilon$ for the counterfactual harm constraint and $\delta$ for the complementarity constraint. 

Figure~\ref{fig:imagenet-online} shows that our adaptive procedure stays close to the target values throughout the data stream, even as the underlying noise level changes. 
By contrast, the fixed baseline exhibits larger deviations, drifting away from the desired levels under distribution shift. 
These results demonstrate that our online algorithm is able to dynamically adjust to changing conditions, ensuring that the conditional coverage guarantees hold in the long run.

\begin{figure}[htp!]
    \centering
    \includegraphics[width=0.49\linewidth]{figures/main-online-imagenet-eps.png}
    \includegraphics[]{}
    \includegraphics[width=0.49\linewidth]{figures/main-online-imagenet-delta.png}
    \caption{eps = 0.05, delta= 0.8, w= 500, k = 2, calibrated on omega = 80}
    \label{fig:online-imagenet-eps-delta}
\end{figure}
\fi
\subsection{LLMs for Medical Diagnosis Decision Making}

Our second set of experiments evaluates the framework in the text modality of data, focusing on a medical decision-making task using the DDXPlus dataset \citep{NEURIPS2022_ddxplus}. This dataset contains synthetic patient records generated from a medical knowledge base and rule-based diagnostic system.
Each record includes demographics, symptoms, and antecedents linked to an underlying condition, along with a differential diagnosis list. From this list we form human prediction sets using a top-$k$ strategy, where the human provides the $k$ most likely diagnoses. %As before, the human policy is treated as a black box: the algorithm observes only the sets, not confidences or probabilities.
For the AI component, we use two language models with contrasting accuracy: \textbf{GPT-5}, which performs strongly, and \textbf{GPT-4o}, which is weaker and often falls below the human baseline. This contrast highlights how the quality of the AI model shapes the trade-offs of collaboration. 

%\subsubsection{Offline results}
\textbf{Offline Setting.}
Tables~\ref{tab:ddxplus-compact} summarize the results for GPT-4o and GPT-5, respectively, under two different human strategies. Across all settings, CUP-offline improves on the human baseline by raising coverage, as the procedure explicitly augments human sets when the true label is missing. Naturally, this may increase set size, 
but when the AI is sufficiently strong, as with GPT-5, the algorithm is able to both prune away incorrect human labels and add the correct label when necessary more efficiently. This yields prediction sets that  improve across both dimensions: achieving higher coverage \emph{and} smaller size, outperforming both baselines.

\begin{table*}[h!]
\centering
\small
\setlength{\tabcolsep}{4pt}
\renewcommand{\arraystretch}{1.1}
\begin{tabular}{lcc|ccc|ccc}
\toprule
& \multicolumn{2}{c|}{\textbf{Human}} 
& \multicolumn{3}{c|}{\textbf{GPT-4o}} 
& \multicolumn{3}{c}{\textbf{GPT-5}} \\
\cmidrule(lr){2-3}\cmidrule(lr){4-6}\cmidrule(lr){7-9}
\textbf{Strategy} & \textbf{C/S} & 
& \textbf{CUP C/S} & \boldmath$(\varepsilon,\delta)$ & \textbf{AI C/S} 
& \textbf{CUP C/S} & \boldmath$(\varepsilon,\delta)$ & \textbf{AI C/S} \\
\midrule
%Top-1 & 0.71 / 1.00 && 0.89 / 2.56 & (0.01, 0.65) & 0.88 / 4.58 & 0.87 / 1.27 & (0.02, 0.55) & 0.88 / 1.54 \\
%Top-1 & 0.71 / 1.00 && 0.88 / 2.51 & (0.02, 0.65) & 0.88 / 4.40 & 0.88 / 1.36 & (0.01, 0.55) & 0.89 / 1.59 \\
%Top-1 & 0.71 / 1.00 && 0.85 / 1.77 & (0.01, 0.50) & 0.85 / 3.69 & 0.85 / 1.19 & (0.02, 0.50) & 0.86 / 1.42 \\
Top-1 & 0.71 / 1.00 && 0.90 / 2.84 & (0.02, 0.70) & 0.88 / 4.64 & 0.91 / 1.59 & (0.02, 0.70) & 0.91 / 1.76 \\
\midrule
\addlinespace[0.3em]
%Top-2 & 0.87 / 1.95 && 0.90 / 2.47 & (0.01, 0.30) & 0.88 / 4.57 & 0.95 / 2.31 & (0.01, 0.70) & 0.95 / 2.79 \\
Top-2 & 0.87 / 1.95 && 0.93 / 3.14 & (0.01, 0.45) & 0.90 / 9.12 & 0.93 / 1.65 & (0.02, 0.45) & 0.93 / 1.95 \\

%0.94 / 1.73 & (0.02, 0.55) & 0.94 / 2.10 \\
%Top-2 & 0.87 / 1.95 && 0.94 / 3.69 & (0.01, 0.55) & 0.93 / 22.41 & 0.91 / 1.51 & (0.02, 0.40) & 0.91 / 1.83 \\
%Top-2 & 0.87 / 1.95 && 0.93 / 3.41 & (0.01, 0.50) & 0.91 / 13.55 & 0.93 / 1.65 & (0.02, 0.45) & 0.93 / 1.95 \\
\bottomrule
\end{tabular}
\caption{\textbf{LLMs-Offline Results} %We compare Human Alone, CUP (ours), and AI Alone for GPT-4o and GPT-5-mini. 
Entries report coverage/size (C/S). Calibration parameters $(\varepsilon,\delta)$ shown for CUP.}
\label{tab:ddxplus-compact}
\end{table*}


With a weaker model such as GPT-4o, coverage gains may come at the cost of slightly larger sets, reflecting that the model is less capable of efficient pruning or complementarity. 
This does not undermine the approach but rather illustrates the role of the AI component in determining the ultimate efficiency of the collaborative sets. Still, CUP-offline produces smaller sets than AI alone at comparable coverage levels, showing that human knowledge is being used productively. 
Taken together, these results demonstrate that CUP-offline yields consistent benefits over both the human and  AI baselines, while the degree to which coverage and set size can be simultaneously optimized depends on the strength of the AI model.

%\subsubsection{Online setting}
\textbf{Online Setting.}
We next evaluate the CUP-online algorithm in the medical setting, using GPT-5 as the AI model. Human prediction sets follow a top-$k=2$ strategy, and distribution shift is induced by ordering test patients by age, from younger to older groups. We also include a non-adaptive baseline with fixed thresholds tuned on the earliest segment (ages 1–30) to isolate the effect of adaptivity in the face of demographic change, however due to space constraints direct comparison with this baseline is deferred to the Appendix~\ref{appendix:llm}.

%calibration is performed on subsets of patients restricted to younger age groups (ages 1–30), while testing is carried out sequentially across older age groups (30–40 through 100–110). 

%This setup mimics the realistic challenge of deploying a model trained on a limited subpopulation to a broader, shifted distribution.  

As in the ImageNet experiments, we benchmark CUP-online against human-only and AI-only baselines. 
%the direct comparison with a fixed non-adaptive baseline is deferred to the Appendix~\ref{appendix:llm}. 
Figure~\ref{fig:online-llm-regression} shows results under demographic shift. The pattern is consistent with the offline setting: CUP improves over the human baseline in both coverage and set size, and against AI Alone it achieves smaller sets at matched coverage.

\begin{figure}[htp!]
    \centering

    % -------- Left block: LLM --------
    \begin{minipage}[t]{0.48\linewidth}
        \centering
        \includegraphics[width=\linewidth]{iclr2026/figures/online-llm/online-llm-baselines-eps-0.02-delta-0.45-ageshift.png}
        \vspace{2pt}
        {\small \textbf{LLM (DDXPlus) under age shift}}
    \end{minipage}%
    \hfill
    % Vertical separator
    \vrule width 1pt
    \hfill
    % -------- Right block: Regression --------
    \begin{minipage}[t]{0.48\linewidth}
        \centering
        %\includegraphics[width=0.495\linewidth]{iclr2026/figures/online-regression/online-cc-eps0.15-delta0.25-Baselines-marginal-cov.png}%
        %\hfill
        %\includegraphics[width=0.495\linewidth]{iclr2026/figures/online-regression/online-cc-eps0.15-delta0.25-Baselines-set_size.png}
        %\vspace{2pt}
        \includegraphics[width=1\linewidth]{iclr2026/figures/online-regression/online-regression-baselines-finalplot.png}
        %\vspace{2pt}
        {\small \textbf{Regression - (Communities \& Crime) under demographic shift}}
    \end{minipage}

    \caption{Online results: LLM (left) and regression (right), comparing CUP–online with baselines Human and AI.}
\label{fig:online-llm-regression}

    \label{fig:online-llm-regression}
\end{figure}

\iffalse
\begin{figure}[htp!]
    \centering
    \includegraphics[width=0.49\linewidth]{iclr2026/figures/online-llm/online-llm-eps0.02-delta0.45-Baselines-marginal-cov.png}
    \includegraphics[width=0.49\linewidth]{iclr2026/figures/online-llm/online-llm-eps0.02-delta0.45-Baselines-set_size.png}
    \caption{}
    \label{fig:online-imagenet-eps-delta}
\end{figure}
\fi
\subsection{Regression: Communities \& Crime}
Our final set of experiments evaluates the framework in a regression setting using the UCI \emph{Communities \& Crime} dataset \citep{communities_and_crime_183}, where the goal is to predict the violent crime rate per community. To simulate human input, we generate intervals centered around noisy point estimates of the ground truth. Specifically, we perturb each true label with Gaussian noise to form $\hat y(x)$, then construct the interval $
H(x) = [\,\hat y(x) - w(x)/2,\ \hat y(x) + w(x)/2\,],
$ where $w(x)$ is a base width also subject to noise. By varying the noise levels, we simulate human experts of differing quality. As in earlier experiments, the algorithm only observes the final set $H(x)$, not how it was generated.
%The human is modeled as a black box that provides an interval for each input. 
%To simulate different levels of human expertise, we synthesize these intervals by perturbing the ground truth with Gaussian noise to form a noisy point estimate, then placing a small symmetric interval around it:
%\[
%H(x) = [\,\hat y(x) - w(x)/2,\ \hat y(x) + %w(x)/2\,],
%\]
%where $\hat y(x)$ is the noisy estimate and $w(x)$ is a base width also subject to noise. By varying the noise and base width, we create human experts of different strengths.
%Importantly, as in previous experiments, the algorithm observes only the final interval $H(x)$ and not the underlying generation process. This setup allows us to control the quality of the human inputs and study how collaboration adapts to stronger or weaker experts.
The AI model builds on the setting explained in Section~\ref{Sec:score}.%we build on the regression scoring rule introduced in Section~\ref{sec:scoring}.
 We train two MLPs using the pinball loss to estimate conditional quantiles: one for predicting $(\hat q_{\varepsilon/2}, \hat q_{1- \varepsilon/2})$, and one for $(\hat q_{\delta/2}, \hat q_{1-\delta/2})$. Each model shares a backbone with two output heads. The resulting four quantiles define the CQR-style score in Section~\ref{Sec:score}, to which we apply the CUP-offline procedure to obtain the two thresholds used at test time. 

%neural networks are trained to capture the collaborative constraints: one pair $(\hat q_{\varepsilon,\text{lo}}, \hat q_{\varepsilon,\text{hi}})$ for the counterfactual harm case ($Y \in H(x)$), and another pair $(\hat q_{\delta,\text{lo}}, \hat q_{\delta,\text{hi}})$ for the complementarity case ($Y \notin H(x)$).
%Each network is trained with the standard quantile regression objective introduced in Section~\ref{sec:scoring}, and all training data are used jointly by augmenting the features with the indicator $\1\{Y \in H(x)\}$. 

We compare
\emph{Human Alone}, which uses the raw intervals $H(x)$;  
\emph{AI Alone}, which applies standard conformalized quantile regression without access to the human sets;  
and CUP-offline, which combines both sources via the proposed collaborative algorithm.  
Results are reported in Table~\ref{tab:regression-crime-offline} for two human experts of different quality.
\begin{table}[htp!]
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{cccc|cccc}
\toprule
\multicolumn{4}{c|}{\textbf{Human A}} & \multicolumn{4}{c}{\textbf{Human B}} \\
\cmidrule(lr){1-4}\cmidrule(lr){5-8}
\textbf{Human A C/S} & \textbf{CUP C/S} & $(\varepsilon,\,1-\delta)$ & \textbf{AI C/S}
& \textbf{Human B C/S} & \textbf{CUP C/S} & $(\varepsilon,\,1-\delta)$ & \textbf{AI C/S} \\
\midrule
0.760 / 0.581 & 0.862 / 0.380 & (0.10, 0.70) & 0.862 / 0.394
& 0.872 / 0.618 & 0.948 / 0.528 & (0.05, 0.90) & 0.948 / 0.608 \\
0.760 / 0.581 & 0.825 / 0.326 & (0.15, 0.70) & 0.825 / 0.337
& 0.872 / 0.618 & 0.953 / 0.558 & (0.05, 0.95) & 0.953 / 0.588 \\
\bottomrule
\end{tabular}%
}
\caption{Regression–Offline Results: Coverage/size (C/S) under two human expert settings.}

\label{tab:regression-crime-offline}
\end{table}
First, we note that CUP improves upon the human baseline in terms of both coverage and interval width. Second, the results highlight the complementary role of human, with greater gains observed over AI Alone when initial human input is of higher quality. This complements the medical diagnosis results, where we varied the AI instead of the human. Together, the two experiments show that the collaboration efficiency depends on the quality of both parties.

%Size reduction is larger when the human input is stronger: with Human B ( the weaker expert) CUP reduces the average interval width by 0.08 compared to AI Alone, versus only 0.01 with Human A. This mirrors the pattern observed in the medical-diagnosis task, but from the opposite perspective: there we varied the AI model, here we vary the human. Together, the two experiments show that the collaboration efficiency depends on the quality of both parties.

\textbf{Online Setting.}
We evaluate CUP-online under a controlled distribution shift based on community demographics. Test examples are ordered by the proportion of residents identified by a randomly selected race-coded variable. Figure \ref{fig:online-llm-regression} reports the running marginal coverage and average set size for AI, Human, and CUP-online. Consistent with the previous experiments, we again observe that CUP-online improves upon both baselines: compared to Human Alone, it increases coverage without inflating intervals; compared to AI Alone, it reduces interval width while preserving coverage. The non-adaptive baseline with fixed thresholds is tuned on the earliest portion of the stream (i.e., communities with the lowest demographic proportion). Results for this baseline are deferred to Appendix~\ref{appendix:regression}. All together, the results underscore the robustness of the collaborative approach across modalities and under shifting data distributions.
%We then turn to the online evaluation, where we introduce a controlled distribution shift based on community demographics. Specifically, we sort test examples by the proportion of residents identified by a  randomly selected race-coded variable in the dataset. The non-adaptive baseline with fixed thresholds is tuned on the earliest portion of the stream (i.e., communities with the lowest values of the selected demographic proportion); the results for the fixed baseline are deferred to Appendix~\ref{fig:appendix-regression-fixed-vs-online}. 
%Calibration is performed on communities with the lowest proportions, and we then evaluate performance as this proportion increases across the test stream. \textcolor{red}{the last sentence is confusing. in online setting calibration is done online at each time t. what does it mean "Calibration is performed on communities with the lowest proportions". similar sentences exist in other parts of your experiment write up and they are equally confusing/wrong.}
%This setup mimics a deployment scenario where calibration data may not fully represent future populations, and it allows us to evaluate how effectively the online updates adapt under systematic covariate change.
%We move on to the online setting, where we study our online CUP algorithm under distirbution shift induced via varying the intensity of race code -1 feature. ( this is the whiteperCapita feature in this dataset but i need to somehow refer to it being policitcally correct ). We calibrate the threhsolds a and b on a subset of the data with lowest whitePerCap index and then test by moving the intensity of this... ( explain this right, easy to understand, minimal and academically polished at the same time ). The results are in figure~\ref{fig:online-baselines-regression}, which show the running maringal coverage and runnign set size defined in seciton~\ref{subsec:imagenet-online-experiments}. again as in previous modalities experiments we comapre our CUP algorithm to human only and ai only baseliens  and we observe the same trends, we're able to improve in both dimensiosn .... 
\iffalse
\begin{figure}
    \centering
    \includegraphics[width=0.49\linewidth]{iclr2026/figures/online-regression/online-cc-eps0.15-delta0.25-Baselines-marginal-cov.png}
    \includegraphics[width=0.49\linewidth]{iclr2026/figures/online-regression/online-cc-eps0.15-delta0.25-Baselines-set_size.png}
    \caption{Enter Caption}
    \label{fig:online-baselines-regression}
\end{figure}
\fi


\section{Extended Related Works}
\label{appendix:lit-review}
\paragraph{Conformal Prediction} The idea of constructing prediction regions can be traced back to classical work on tolerance intervals in statistics \citep{wilks1941determination, scheffe1945non}. Modern Conformal Prediction (CP), introduced by \cite{vovk1999machine,10.5555/1624312.1624322,vovk2005algorithmic}, builds on this foundation to provide distribution-free, finite-sample validity: given a desired confidence level, CP guarantees that the constructed prediction set contains the true outcome with the prescribed marginal probability. 

Over the past two decades, CP has become a standard tool in machine learning for both classification and regression tasks \citep{papadopoulos2002inductive, lei2017distributionfreepredictiveinferenceregression, romano2019conformalizedquantileregression, romano2020classificationvalidadaptivecoverage}, and recently extended to language models \citep{noorani2025conformalpredictionseenmissing,quach2024conformallanguagemodeling, mohri2024languagemodelsconformalfactuality,cherian2024largelanguagemodelvalidity,su2024apienoughconformalprediction} %\textcolor{red}{here cite our missing mass paper, and 1-2 more related ones}.
with a large literature on improving \emph{efficiency} (shrinking set size while preserving coverage)
\citep{fisch2024calibratedselectiveclassification, Gupta_2022, kiyani2024lengthoptimizationconformalprediction,stutz2022learningoptimalconformalclassifiers,noorani2025conformalriskminimizationvariance}.
A growing body of work extends CP beyond marginal coverage to control more general notions of risk. %\citep{lindemann2023safeplanningdynamicenvironments,angelopoulos2025conformalriskcontrol,cortesgomez2024,lekeufack2024conformaldecisiontheorysafe,zecchin2024riskcontrola,blot2024riskaware,zecchin2024riskcontrolb}.  
\cite{angelopoulos2025conformalriskcontrol} introduced conformal risk control, showing how prediction sets can be calibrated to satisfy monotone risk measures rather than coverage alone. \cite{lindemann2023safeplanningdynamicenvironments} applied these principles to safe planning in dynamic environments, demonstrating how conformal methods can enforce operational safety constraints. \cite{lekeufack2024conformaldecisiontheorysafe} developed a conformal decision-theoretic framework where decisions are parameterized by a single scalar and calibrated to control risk. \cite{cortesgomez2025utilitydirectedconformalpredictiondecisionaware} expands on this view by developing utility-directed conformal prediction, which constructs sets that both retain standard coverage guarantees and minimize downstream decision costs specified by a user-defined utility function. More broadly, \cite{kiyani2025decisiontheoreticfoundationsconformal} show that prediction sets can be viewed as a natural primitive for risk-sensitive decision making: they communicate calibrated uncertainty in a form well-suited for risk-averse decision makers operating in high-stakes domains. 
This perspective makes conformal prediction sets relevant for human–AI collaboration, particularly in high-stakes applications, where reliable uncertainty estimates are essential for enabling trust and complementarity between human expertise and machine predictions. Our work provides a principled way to generalize the methodologies developed by these studies to scenarios where humans are in the loop, contributing to the final design of prediction sets.
\paragraph{Human-AI collaboration} Human–AI decision-making has attracted growing interest across the machine learning community and social sciences \citep{jessicalhullman-aireliance-decision-theoretic-framework, marusich2024usingaiuncertaintyquantification, guo2025valueinformationhumanaidecisionmaking,jessicasurvey}. Yet, realizing true complementarity where the joint system outperforms either the human or the AI-alone, or both, remains challenging \citep{lai2021sciencehumanaidecisionmaking, vaccaro2024combinations, bansal2021does}. Interestingly, a recent meta analysis by \cite{vaccaro2024combinations} found out that, on average, human–AI teams under-perform the stronger individual agent. These findings underscore persistent difficulties around coordination, trust, and communication between machine and human, motivating the need for algorithmic frameworks that can systematically structure collaboration. This work takes a step toward a mathematically rigorous framework that combines the power of AI and humans in a way that complements human capabilities while controlling potential counterfactual harm.

\textbf{Learning to Defer}. One approach is the \emph{learning to defer} (L2D) paradigm, where the AI model learns when to predict on its own and when to defer to a human expert. Earlier work \cite{madras2018predictresponsiblyimprovingfairness} framed this as a mixture-of-experts problem, jointly training a classifier with a deferral mechanism. \cite{wilder-2021-learing-to-complement-humans} extended this with a decision-theoretic formulation, training models to complement human strengths rather than maximize accuracy alone. Subsequent work studied the design of surrogate losses for deferral, for example \cite{mozannar2021consistentestimatorslearningdefer} showed that standard training objectives can fail to produce optimal deferral policies and proposed a consistent surrogate loss that guarantees Bayes-optimal deferral. Extensions address various settings: \cite{verma2022calibratedlearningdeferonevsall} and \cite{pmlr-v162-charusaie22a} studied deferral with multiple experts, while \cite{wei-zizi-cao-exploiting-human-ai-dependence} emphasized that humans and models are not independent and introduced dependent Bayes optimality to exploit correlations between them. \cite{okati2021differentiablelearningtriage} formulated differentiable learning under triage, providing exact optimality guarantees for multi-expert deferral. \cite{bary2025needlearningdefertraining} proposed a training-free deferral framework that leverages conformal prediction to allocate decisions among multiple experts. And most recently, along these ideas, \cite{arnaizrodriguez2025humanaicomplementaritymatchingtasks} introduced a collaborative matching system that selectively defers to humans to maximize overall performance.

Overall, the L2D literature focuses on \emph{who decides} on each instance: the model or the human. These methods improve team performance by abstention or delegation, which is inherently different than our approach. We start from the human’s proposed \emph{set} and ask how to refine it with AI. The goal is to always produce a combined prediction set, particularly one that is simultaneously more reliable and more informative than either agent alone. In this sense, our approach complements deferral-based methods but addresses a different question: not \emph{who decides}, but \emph{how to decide together}.
%We seek to combine the powers of both AI and human expert to construct prediction sets that communicate uncertainty for every example x, rather than delegating which example to give to who.( Rather than routing or abstaining, we treat the human’s proposed \emph{set} as the starting point and ask how to algorithmically refine it with AI. The goal is not to decide whether the human or AI should act, but to produce a combined prediction set that is both more reliable and more informative than either agent alone. This perspective is complementary to deferral-based methods: instead of shifting control, we design a collaborative procedure that directly leverages both inputs.) 

\textbf{Agreement protocols} 




Another line of work views collaboration as an interactive process through \emph{agreement protocols}, where humans and models iteratively exchange feedback until consensus is reached \citep{aumann1976agreeing,10.1145/3717823.3718222,GEANAKOPLOS1982192, aaronson2004complexityagreement,collina2024tractableagreementprotocols}. Earlier formulations \cite{aaronson2004complexityagreement} assume perfect Bayesian updates under a common prior, and make assumptions that generally preclude tractable implementation. \cite{collina2024tractableagreementprotocols} generalize these results and introduce tractable agreement protocols that replace Bayesian rationality with statistically efficient calibration conditions which enable agreement theorems without distributional assumptions. More recent generalizations \cite{collina2025collaborativepredictiontractableinformation} develop collaboration protocols that achieve information aggregation as well in the setting where agents observe different features of the same instance.   These approaches assume that both agents maintain probabilistic beliefs and communicate probability vectors or expected-value estimates until their predictions become sufficiently close. In contrast, our framework differs in scope and considers a setting where the human provides only a prediction set, without the need to specify probabilities or beliefs over labels. Moreover, while agreement protocols emphasize belief convergence between agents, our work prioritizes the human and focuses on constructing collaborative prediction sets that balance the two objectives of counterfactual harm and promoting complementarity. The agreement protocol literature therefore captures a complementary aspect of human–AI collaboration, centering on belief alignment rather than prediction-set construction, and it remains nontrivial to translate the converged beliefs in these protocols into prediction sets that satisfy counterfactual harm or complementarity criteria.


%These approaches typically assume that both agents maintain probabilistic beliefs and communicate probability vectors or expected-value estimates until their beliefs converge. In contrast, our framework operates under a more practical assumption, specially from the human perspective, that the human only provides a prediction set $H(x)$, without the need to specify probabilities or beliefs over labels. Furthermore, while agreement protocols focus on achieving belief convergence between agents, our focus is on constructing collaborative predictiton sets that balance the two objectives of avoiding counterfactual harm and complementarity. Thus this line of work addresses complementarity facets of human and ai collaboration, emphasizing beleif convergence, whereas our framework .. 


\textbf{Prediction sets for human-AI decision support} A more related and recent strand of work has explored prediction sets as a structured interface for collaboration and human decision making support. \cite{pmlr-v202-straitouri23a} formalized the problem of improving expert predictions with Conformal Prediction in multiclass classification. In their setting, the AI provides a subset of candidate labels for each instance, from which the human selects, ensuring that the advice is structured but does not override the expert’s agency. In parallel, \cite{babbar2022utilitypredictionsetshumanai} empirically evaluated prediction sets in human–AI teams, and showed that set-valued advice can improve human accuracy compared to single-label predictions. However, they also found that large prediction sets may confuse or slow down human decision-making. To mitigate this, they introduced Deferral-CP (D-CP), where the AI is allowed to abstain entirely on instances for which no sufficiently small set can be produced, deferring the decision back to the human. Closely related,  \cite{hullman2025conformalpredictionhumandecision} analyzed Conformal Prediction from a decision-theoretic perspective, examining how coverage guarantees relate to human goals and strategies in decision making. They formalize possible ways a decision maker might use a prediction set and high tensions between conformal coverage and the forms of uncertainty information that best support human decisions. Other works have studied how to design prediction sets specifically tailored for human use, for example \cite{detonipredsets} proposed a greedy algorithm for constructing prediction sets and showed empirically that it can improve average human accuracy compared to standard conformal sets. 

While these studies focus on how prediction sets can support human decision-making, i.e. how humans utilize AI-generated sets to make final judgments, our framework addresses a complementary question: how human feedback can be used to construct a more reliable collaborative prediction set. Rather than treating the human as the end decision-maker, we model the prediction set itself as the outcomes of collaboration, designed jointly to reflect human and AI strengths. 



%investigates how prediction sets can be used to support human decision-making. Straitouri et al. \cite{pmlr-v202-straitouri23a} formalized the problem of probably improving expert predictions with conformal prediction in multiclass classification. In their setting, the AI provides a subset of candidate labels for each instance, from which the human selects, ensuring that the advice is structured but does not override the expert’s agency. In parallel, Babbar et al. \cite{babbar2022utilitypredictionsetshumanai} empirically evaluated prediction sets in human–AI teams, showing that set-valued advice can improve human accuracy compared to single-label predictions. However, they also found that large prediction sets may confuse or slow down human decision-making. To mitigate this, they introduced Deferral-CP (D-CP), where the AI is allowed to abstain entirely on instances for which no sufficiently small set can be produced, deferring the decision back to the human.Other works have studied how to design prediction sets specifically tailored for human use. Detoni et al. \cite{detonipredsets} proposed a greedy algorithm for constructing prediction sets and showed empirically that it can improve average human accuracy compared to standard conformal sets. 

\textbf{Counterfactual harm and complementarity}
In recent years, there has been growing concern about the unintended consequences of decision support systems using machine learning algorithms in high-stakes domains \citep{richens2022counterfactualharm,pmlr-v202-li23ay,beckers2022quantifyingharm}. %[1-4] 
To this end, \cite{elanicounterfactual} analyze decision-support systems based on prediction sets through the lens of \emph{counterfactual harm} \citep{Feinberg_1986}.%[5-7]. 
Their concern is that requiring humans to always select from a machine-provided set may, in some cases, harm performance: a human who would have been correct unaided might be misled by the system. Using structural causal models, they formally defined and quantified this notion of harm, and under natural monotonicity assumptions, provided methods to estimate or bound how frequently harm may occur without deploying the system. While closely related to our framework, their setting differs from ours in that they study systems where the AI supplies sets from scratch, and their definition of counterfactual harm focuses on the subsequent prediction accuracy of the human, whereas we start from sets already provided by the human and ask how to refine them collaboratively, and our definition of counterfactual harm is a direct measure of the quality of the refining procedure. %\textcolor{red}{sounds good to me}

%These ideas connect to a broader literature on counterfactual harm in machine learning, which has primarily focused on automated decision-making where models replace humans. Richens et al. \cite{richens2022counterfactual, beckers2022causal,beckers2023quantifying} provided a causal analysis and quantification framework.\cite{li2023trustworthy} extended the idea to policy learning under a no-harm criterion.

On the other hand, in the broader human-AI collaboration literature, complementarity is typically defined as whether the combined system achieves higher average accuracy than either the human or the model alone \citep{YinMingComplementarity,Suresh_2020, lai2021sciencehumanaidecisionmaking}%[13-16]
, and it is currently still unclear how to guarantee this. Our formulation of complementarity is different: it is set-based rather than accuracy-based. Instead of asking whether joint predictions improve overall accuracy, we require that the collaborative prediction set recovers outcomes the human initially missed, while simultaneously avoiding counterfactual harm. This shifts the focus from point-prediction accuracy to the tradeoff between set-based coverage and set size. Crucially, by defining complementarity in this way, our framework provides a principled way to formalize and guarantee it, with clear tradeoffs between the two central metrics of uncertainty quantification. %\textcolor{red}{sounds good.}

\section{Conclusion}
We introduced a framework for constructing prediction sets collaboratively between humans and AI, grounded in two core principles: avoiding counterfactual harm and enabling complementarity. We showed that the optimal sets take a simple two-threshold form, and developed finite-sample algorithms for both offline and online settings. Across diverse domains and agents (human or AI) strengths, our methods consistently leverage the collaboration capabilities of human and AI to produce sets that outperform either alone. This framework offers a principled and practical approach to structured collaboration under uncertainty.
\iffalse
\begin{figure}[htp!]
\centering

% ===== Top block: ImageNet-16H (keep as-is, 2x2) =====
\begin{minipage}[t]{0.48\linewidth}
  \centering
  \includegraphics[width=\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-eps-0.01-delta-0.4-runningcov-humanshift.png}
  \includegraphics[width=\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-baselines-eps-0.01-delta-0.4-humanshift.png}
\end{minipage}\hfill
\vrule width 1pt\hfill
\begin{minipage}[t]{0.48\linewidth}
  \centering
  \includegraphics[width=\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-eps-0.01-delta-0.4-runningcov-noiseshift.png}
  \includegraphics[width=\linewidth]{iclr2026/figures/online-imagenet/online-imagenet-baselines-eps-0.01-delta-0.4-noiseshift.png}
\end{minipage}

\vspace{3pt}
{\small \textbf{ImageNet-16H (online):} Human strategy shift (left) and noise shift (right).}

% ===== Horizontal rule separating top and bottom =====
\vspace{4pt}
\rule{\linewidth}{0.7pt}
\vspace{4pt}

% ===== Bottom row: LLM (left) | vertical rule | Regression (right) =====
\begin{minipage}[t]{0.48\linewidth}
  \centering
  \includegraphics[width=\linewidth]{iclr2026/figures/online-llm/online-llm-baselines-eps-0.02-delta-0.45-ageshift.png}
  \vspace{2pt}\\
  {\small \textbf{LLM (age shift)}}
\end{minipage}\hfill
\vrule width 1pt\hfill
\begin{minipage}[t]{0.48\linewidth}
  \centering
  \includegraphics[width=0.495\linewidth]{iclr2026/figures/online-regression/online-cc-eps0.15-delta0.25-Baselines-marginal-cov.png}\hfill
  \includegraphics[width=0.495\linewidth]{iclr2026/figures/online-regression/online-cc-eps0.15-delta0.25-Baselines-set_size.png}
  \vspace{2pt}\\
  {\small \textbf{Regression (Communities \& Crime)}}
\end{minipage}

\caption{Combined online results across modalities: ImageNet-16H (top), LLM and Regression (bottom).}
\label{fig:online-meta}
\end{figure}

\fi
\newpage


\iffalse
regression table 

\begin{table}[htp!]
\centering
\caption{Regression results (Top-5 $\varepsilon,\delta$ pairs) comparing Human Alone, HA-CQR (Ours), and AI Alone.}
\resizebox{\textwidth}{!}{%
\begin{tabular}{c|c|cc|cc|cc}
\toprule
$\varepsilon$ & $\delta$ & \multicolumn{2}{c|}{\textbf{Human Alone}} & \multicolumn{2}{c|}{\textbf{HA-CQR (Ours)}} & \multicolumn{2}{c}{\textbf{AI Alone}} \\
 & & Coverage & Size & Coverage & Size & Coverage & Size \\
\midrule
0.10 & 0.30 & 0.76 $\pm$ 0.02 & 0.58 $\pm$ 0.00 & 0.86 $\pm$ 0.02 & 0.38 $\pm$ 0.02 & 0.86 $\pm$ 0.02 & 0.39 $\pm$ 0.03 \\
0.05 & 0.10 & 0.76 $\pm$ 0.02 & 0.58 $\pm$ 0.00 & 0.93 $\pm$ 0.02 & 0.51 $\pm$ 0.03 & 0.93 $\pm$ 0.02 & 0.51 $\pm$ 0.05 \\
0.15 & 0.30 & 0.76 $\pm$ 0.02 & 0.58 $\pm$ 0.00 & 0.82 $\pm$ 0.02 & 0.33 $\pm$ 0.01 & 0.82 $\pm$ 0.02 & 0.34 $\pm$ 0.03 \\
0.05 & 0.20 & 0.76 $\pm$ 0.02 & 0.58 $\pm$ 0.00 & 0.91 $\pm$ 0.00 & 0.50 $\pm$ 0.02 & 0.91 $\pm$ 0.00 & 0.50 $\pm$ 0.03 \\
0.20 & 0.35 & 0.76 $\pm$ 0.02 & 0.58 $\pm$ 0.00 & 0.77 $\pm$ 0.02 & 0.26 $\pm$ 0.02 & 0.77 $\pm$ 0.02 & 0.28 $\pm$ 0.03 \\
\bottomrule
\end{tabular}%
}
\end{table}

\newpage
In the offline setting, we assume access to a calibration dataset $\mathcal{D}_{\text{cal}} = \{(X_i, Y_i, H(X_i))\}_{i=1}^n$ that is exchangeable with the test data. 

The thresholds are chosen by computing the empirical quantiles of the scores from the calibration set, conditioned on whether the true label was in the human's set. Let $s_i = 1-p(Y_i|X_i)$ be the score for calibration point $i$. We set:
\begin{align*}
    \hat{b} &= \text{Quantile}_{1-\varepsilon}\Big( \{s_i \mid Y_i \in H(X_i)\} \cup \{\infty\} \Big) \\
    \hat{a} &= \text{Quantile}_{\delta}\Big( \{s_i \mid Y_i \notin H(X_i)\} \cup \{\infty\} \Big)
\end{align*}
The final prediction set for a new test point $X_{\text{test}}$ is then given by $C(X_{\text{test}}) = \{y \mid s(y|X_{\text{test}}) \le \hat{a} \cdot \mathbf{1}\{y \notin H(X_{\text{test}})\} + \hat{b} \cdot \mathbf{1}\{y \in H(X_{\text{test}})\}\}$. This choice of thresholds leads to the following coverage guarantees.

\begin{proposition}[Finite-Sample Offline Guarantees]
Let $(X_{n+1}, Y_{n+1}, H(X_{n+1}))$ be a new test point, exchangeable with the calibration data. Let $n_1$ be the number of calibration points where $Y_i \in H(X_i)$ and $n_2$ be the number where $Y_i \notin H(X_i)$. The thresholds $\hat{a}$ and $\hat{b}$ satisfy:
\begin{align*}
    1-\varepsilon \le \mathbb{P}(Y_{n+1} \in C(X_{n+1}) \mid Y_{n+1} \in H(X_{n+1})) &< 1-\varepsilon + \frac{1}{n_1+1} \\
    \delta \le \mathbb{P}(Y_{n+1} \in C(X_{n+1}) \mid Y_{n+1} \notin H(X_{n+1})) &< \delta + \frac{1}{n_2+1}
\end{align*}
\end{proposition}
\section{Finite sample Online algorithm}\label{online}
In practice, the human may change their behavior over time, adapting to the AI model, and breaking changeability assumption with the calibration data. To handle this, we design an online algorithm that adapts the thresholds $(a_t, b_t)$ round by round so that the long-run error rates converge to their targets.  

At each time step $t$, let $s(y|x) = 1 - p(y|x)$ be the conformity score. We track two kinds of errors:  
\[
\text{err}_{\text{CH},t} := \mathbf{1}\{Y_t \notin C_t(a_t,b_t),\ Y_t \in H(X_t)\}, \quad
\text{err}_{\text{A},t} := \mathbf{1}\{Y_t \notin C_t(a_t,b_t),\ Y_t \notin H(X_t)\}.
\]
The first is a \emph{counterfactual harm} error (we excluded the true label even though the human had it), and the second is an \emph{advantage} error (we excluded the true label when the human missed it).  

The algorithm updates one threshold at a time, depending on whether the human included the true label. If $Y_t \in H(X_t)$, we update $b_t$ to keep the counterfactual harm rate close to $\varepsilon$:  
\[
b_{t+1} = b_t + \eta(\mathbf{1}\{s(Y_t|X_t) > b_t\} - \varepsilon), \qquad a_{t+1} = a_t.
\]
If $Y_t \notin H(X_t)$, we update $a_t$ to keep the advantage rate close to $\delta$:  
\[
a_{t+1} = a_t + \eta(\mathbf{1}\{s(Y_t|X_t) > a_t\} - (1-\delta)), \qquad b_{t+1} = b_t.
\]
Here $\eta>0$ is a learning rate. Intuitively, if errors happen too often, the threshold loosens; if errors are too rare, the threshold tightens. Over time this drives the empirical error rates toward their targets.  

\subsection{Theoretical Guarantees}

We now summarize the main guarantees of the online algorithm. First, the thresholds remain bounded:  

\begin{lemma}[Parameter Boundedness]
Let the scores $s(y|x) \in [0,1]$. For any $\eta > 0$, the sequences $\{a_t\}$ and $\{b_t\}$ are bounded. Specifically, for all $t > 1$:
\[
b_t \in [-\eta\varepsilon,\; 1+\eta(1-\varepsilon)], \qquad 
a_t \in [-\eta(1-\delta),\; 1+\eta\delta].
\]
\end{lemma}

With bounded parameters, the long-run error rates converge to the desired values:  

\begin{proposition}[Finite-Sample Guarantees]
Let $N_1(T) = \sum_{t=1}^T \mathbf{1}\{Y_t \in H(X_t)\}$ and $N_2(T) = \sum_{t=1}^T \mathbf{1}\{Y_t \notin H(X_t)\}$. For any $T \ge 1$:
\[
\left| \frac{1}{N_1(T)} \sum_{t=1}^T \text{err}_{\text{CH},t} - \varepsilon \right|
\le \frac{1 + \eta \max(\varepsilon, 1-\varepsilon)}{\eta N_1(T)}, \quad
\left| \frac{1}{N_2(T)} \sum_{t=1}^T \text{err}_{\text{A},t} - (1-\delta) \right|
\le \frac{1 + \eta \max(\delta, 1-\delta)}{\eta N_2(T)}.
\]
In particular, if $N_1(T), N_2(T) \to \infty$, then almost surely
\[
\lim_{T\to\infty} \frac{1}{N_1(T)} \sum_{t=1}^T \text{err}_{\text{CH},t} = \varepsilon, \qquad
\lim_{T\to\infty} \frac{1}{N_2(T)} \sum_{t=1}^T \text{err}_{\text{A},t} = 1-\delta.
\]
\end{proposition}

Together, these results say the algorithm self-adjusts: the thresholds never blow up, and over time the fraction of CH and advantage errors converges to the desired levels $(\varepsilon,\delta)$. This kind of gaurantee is typical in online conformal literature including\cite{gibbs2021adaptiveconformalinferencedistribution,angelopoulos2023conformalpidcontroltime}. This means our method remains valid even when the data stream is non-exchangeable and the human’s strategy changes with time.


\section{Human-AI Collaborative Conformalized Quantile Regression}
We now adapt conformalized quantile regression (CQR) to the human--AI collaborative framework introduced in Section~\ref{sec:inf_sample}. 
Recall that the goal is to produce prediction sets $C(x)$ that simultaneously satisfy the counterfactual harm and complementarity constraints:
\[
\mathbb{P}\!\left(Y \notin C(X)\mid Y\in H(X)\right) \le \varepsilon,
\qquad
\mathbb{P}\!\left(Y \in C(X)\mid Y\notin H(X)\right) \ge 1-\delta .
\]

Given any quantile regression algorithm $\mathcal{A}$, we then fit four conditional quantile functions. 
Two functions $\hat{q}_{\varepsilon_{lo}}$ and $\hat{q}_{\varepsilon_{hi}}$ estimate the lower and upper quantiles that enforce the \emph{counterfactual harm} constraint when the human is correct ($Y\in H(X)$). 
Two additional functions $\hat{q}_{\delta_{lo}}$ and $\hat{q}_{\delta_{hi}}$ enforce the \emph{complementarity} constraint when the human is incorrect ($Y\notin H(X)$). 
We pass the indicator $\mathbf{1}\{Y\in H(X)\}$ as an additional input feature during training. 
Hence we use all data are used to fit all quantile regressors, avoiding class imbalance issues.

Next, we define conformity scores that quantify how far the observed label $Y_i$ lies outside the plug-in intervals implied by the quantile functions. 
For calibration point $(X_i,Y_i,H(X_i))$, the score is
\[
S_i :=
\begin{cases}
\max\!\left\{\hat{q}_{\varepsilon_{lo}}(X_i)-Y_i,\;\; Y_i - \hat{q}_{\varepsilon_{hi}}(X_i)\right\}, & Y_i \in H(X_i), \\[1ex]
\max\!\left\{\hat{q}_{\delta_{lo}}(X_i)-Y_i,\;\; Y_i - \hat{q}_{\delta_{hi}}(X_i)\right\}, & Y_i \notin H(X_i).
\end{cases}
\]
In words, if the true label lies inside the interval, the score is non-positive; if it falls outside, the score is the magnitude of the error. 

Given the calibration set $\mathcal{D}_{\text{cal}}$, we compute empirical quantiles of the conformity scores separately for the two conditions:
\[
Q^{(\varepsilon)}_{1-\varepsilon}(S,\mathcal{I}_{\text{cal}}) := (1-\varepsilon)(1+1/|\{i: Y_i \in H(X_i)\}|)\text{-th quantile of }\{S_i: Y_i\in H(X_i)\},
\]
\[
Q^{(\delta)}_{\delta}(S,\mathcal{I}_{\text{cal}}) := (\delta)(1+1/|\{i: Y_i \notin H(X_i)\}|)\text{-th quantile of }\{S_i: Y_i\notin H(X_i)\}.
\]
Finally, for a new input $X_{test}$ with human proposal $H(X_{test})$, the HA-CQR prediction set is
\[
C(X_{n+1}) =
\begin{cases}
\big[\hat{q}_{\varepsilon_{lo}}(X_{test}) - Q^{(\varepsilon)}_{1-\varepsilon},\;\;
\hat{q}_{\varepsilon_{hi}}(X_{test}) + Q^{(\varepsilon)}_{1-\varepsilon}\big], 
& \text{if } Y \in H(X_{test}), \\[1ex]
\big[\hat{q}_{\delta_{lo}}(X_{test}) - Q^{(\delta)}_{\delta},\;\;
\hat{q}_{\delta_{hi}}(X_{test}) + Q^{(\delta)}_{\delta}\big],
& \text{if } Y \notin H(X_{test}).
\end{cases}
\]

\section{Experiments}\label{exp}

\subsection{ImageNet16H - Offline - Elani's}
We begin by outlining our experimental setup. Our goal is to empirically evaluate three different components: (i) Human Alone, (ii) AI Alone, and (iii) HAI (ours). In the Human Alone case, we consider prediction sets produced directly by human experts under different strategies. (\textcolor{red}{explain how we employ these strategies without confusing the reader that we assume we dont have probabilities}) For example, under the top-k strategy, the human provides the k labels they believe most likely to be correct. Importantly, we do not observe probabilities or confidence scores from humans and only have access to the raw set of labels they provide. In the AI Alone case, we run standard conformal prediction using the AI model exclusively, without incorporating any information provided by the human expert. Finally, in the HAI case, we apply our proposed finite-sample offline algorithm. For each of the three methods, we report the \textbf{marginal coverage} achieved as well as the \textbf{average prediction set size}. For HAI, we do not directly control the marginal coverage. Instead, the configuration of $\varepsilon$ and $\delta$—which correspond to the two conditional probabilities in our formulation—governs the trade-off between the coverage achieved and the resulting set size. We present representative settings in the main text and defer additional $(\varepsilon,\delta)$ configurations to the appendix.

Our first set of experiments is conducted on the ImageNet16H dataset. This dataset contains 32,431 predictions made by 145 human participants 
on noisy variants of 1,200 natural images from the ILSVRC-2012 benchmark. 
Each image is perturbed with one of four phase noise levels 
$\omega \in \{80, 95, 110, 125\}$, which progressively increase the difficulty 
of the classification task. The label space is restricted to $L=16$ categories. 
Following prior work, we evaluate our framework using multiple pre-trained 
classifiers that have been fine-tuned for 10 epochs, including VGG19, DenseNet161, 
GoogleNet, ResNet152, and AlexNet. In the main text we present results with VGG19, 
while results for the additional architectures are deferred to the appendix. 
All reported numbers are averaged over 10 random splits of calibration and test images.

\begin{table*}[h]
\centering
\small
\begin{subtable}{0.95\textwidth}
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{lcc | cccc | cc}
\toprule
\multicolumn{9}{c}{\textbf{VGG19, $\omega$ = 125}} \\
\toprule
 & \multicolumn{2}{c|}{\textbf{Human Alone}} 
 & \multicolumn{4}{c|}{\textbf{HAI (Ours)}} 
 & \multicolumn{2}{c}{\textbf{AI Alone}} \\
\cmidrule(lr){2-3} \cmidrule(lr){4-7} \cmidrule(lr){8-9}
Strategy & Coverage & Size 
         & Coverage & Size & $\varepsilon$ & $\delta$
         & Coverage & Size \\
\midrule
Top-2 
& $0.8008 \pm 0.0090$ & $2.00 \pm 0.00$
& $\mathbf{0.9022 \pm 0.0083}$ & $\mathbf{1.49 \pm 0.04}$ & $0.05$ & $0.70$
& $0.9072 \pm 0.0138$ & $1.65 \pm 0.07$ \\
Top-1 
& $0.7245 \pm 0.0103$ & $1.00 \pm 0.00$
& $\mathbf{0.8823 \pm 0.0134}$ & $1.36 \pm 0.07$ & $0.05$ & $0.70$
& $0.8828 \pm 0.0140$ & $1.48 \pm 0.05$ \\
\bottomrule
\end{tabular}}
%\caption{VGG19, noise = 125}
\end{subtable}

\vspace{0.4em} % small gap between subtables

\begin{subtable}{0.95\textwidth}
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{lcc | cccc | cc}
\toprule
\multicolumn{9}{c}{\textbf{VGG19, $\omega$ = 95}} \\
\toprule
 & \multicolumn{2}{c|}{\textbf{Human Alone}} 
 & \multicolumn{4}{c|}{\textbf{HAI (Ours)}} 
 & \multicolumn{2}{c}{\textbf{AI Alone}} \\
\cmidrule(lr){2-3} \cmidrule(lr){4-7} \cmidrule(lr){8-9}
Strategy & Coverage & Size 
         & Coverage & Size & $\varepsilon$ & $\delta$
         & Coverage & Size \\
\midrule
% <-- plug in numbers for this noise/model combo
Top-2 
& $0.9613 \pm 0.0061$ & $2.00 \pm 0.00$
& $\mathbf{0.9825 \pm 0.0066}$ & $\mathbf{1.77 \pm 0.44}$ & $0.01$ & $0.80$
& $0.9830 \pm 0.0061$ & $2.10 \pm 0.15$ \\
\addlinespace
Top-1 
& $0.9257 \pm 0.0060$ & $1.00 \pm 0.00$
& $\mathbf{0.9763 \pm 0.0076}$ & $1.43 \pm 0.07$ & $0.01$ & $0.80$
& $0.9755 \pm 0.0053$ & $2.27 \pm 0.21$ \\
\bottomrule
\end{tabular}}
%\caption{ResNet152, noise = 95}
\end{subtable}

\caption{\textbf{Results across different AI models and noise levels.}
Each subtable reports Human Alone, HAI (Ours), and AI Alone.
Coverage and average set size are mean $\pm$ std over 10 splits.
calibration parameters $(\varepsilon,\delta)$ only applies for HAI.}
\label{tab:imagenet-main}
\end{table*}

Table \ref{tab:imagenet-main} summarizes our findings. We observe that HAI consistently improves upon the initial human sets by raising marginal coverage, even though the algorithm does not directly target coverage. Instead, coverage emerges indirectly through the choice of calibration parameters: typically, we would like  
$\varepsilon$ to be small and 
$\delta$ to be large. In many cases HAI also \textbf{achieves smaller prediction sets} than the human input or the AI baseline. For instance, when humans provide two labels (\textit{top-2}), HAI both increases coverage (e.g., from 0.80 to 0.90) and reduces the set size (from 2.0 to 1.5). To benchmark against AI alone, we evaluate conformal prediction at the same realized coverage levels as HAI. Here we find that HAI produces noticeably smaller sets—especially in lower-noise conditions
$\omega \leq 95$ where human input is more accurate—demonstrating that our method effectively leverages human knowledge.

\subsection{LLM - Differential Medical Diagnosis}
We compare for two different AI models, one that performs significantly worse than the human expert, and one that is slightly better or equal performance than the human expert. it can be seen that the stronger model is able to get smaller sets that humans and improve the coverage, whereas the weaker model inflates the set size at the cost of the coverage gain. So the stronger the AI model, the less this trade-off.


\begin{table*}[htp!]
\centering
\small
\setlength{\tabcolsep}{6pt}
\begin{tabular}{lcccccccc}
\toprule
& \multicolumn{2}{c}{\textbf{Human Alone}} & \multicolumn{4}{c}{\textbf{HAI (Ours)}} & \multicolumn{2}{c}{\textbf{AI Alone (GPT-4o)}} \\
\cmidrule(lr){2-3}\cmidrule(lr){4-7}\cmidrule(lr){8-9}
\textbf{Strategy} & \textbf{Cov.} & \textbf{Size} & \textbf{Cov.} & \textbf{Size} & \boldmath$\varepsilon$ & \boldmath$\delta$ & \textbf{Cov.} & \textbf{Size} \\
\midrule
Top-1 & 0.712 & 1.000 & 0.890 & 2.557 & 0.010 & 0.650 & 0.881 & 4.578 \\
Top-1 & 0.712 & 1.000 & 0.882 & 2.508 & 0.020 & 0.650 & 0.876 & 4.404 \\
Top-1 & 0.712 & 1.000 & 0.845 & 1.766 & 0.010 & 0.500 & 0.850 & 3.692 \\
Top-1 & 0.712 & 1.000 & 0.901 & 2.840 & 0.020 & 0.700 & 0.883 & 4.639 \\
Top-1 & 0.712 & 1.000 & 0.907 & 2.904 & 0.010 & 0.700 & 0.883 & 4.639 \\
Top-1 & 0.712 & 1.000 & 0.775 & 1.134 & 0.020 & 0.200 & 0.775 & 2.490 \\
\midrule
% --- Top-2 (new rows) ---
Top-2 & 0.867 & 1.951 & 0.897 & 2.469 & 0.010 & 0.300 & 0.881 & 4.572 \\
Top-2 & 0.867 & 1.951 & 0.927 & 3.144 & 0.010 & 0.450 & 0.895 & 9.115 \\
Top-2 & 0.867 & 1.951 & 0.940 & 3.688 & 0.010 & 0.550 & 0.933 & 22.410 \\
Top-2 & 0.867 & 1.951 & 0.932 & 3.408 & 0.010 & 0.500 & 0.905 & 13.548 \\

\bottomrule
\end{tabular}
\caption{Top-5 \((\delta,\varepsilon)\) pairs maximizing coverage gain vs. Human and size gain vs. AI. AI model for the \emph{AI Alone} column is \textbf{GPT-4o}. Means shown; standard deviations not shown.}
\label{tab:gpt4o_hai_top5}
\end{table*}

\begin{table*}[htp!]
\centering
\small
\setlength{\tabcolsep}{6pt}
\begin{tabular}{lcccccccc}
\toprule
& \multicolumn{2}{c}{\textbf{Human Alone}} & \multicolumn{4}{c}{\textbf{HAI (Ours)}} & \multicolumn{2}{c}{\textbf{AI Alone (GPT-5-mini)}} \\
\cmidrule(lr){2-3}\cmidrule(lr){4-7}\cmidrule(lr){8-9}
\textbf{Strategy} & \textbf{Cov.} & \textbf{Size} & \textbf{Cov.} & \textbf{Size} & \boldmath$\varepsilon$ & \boldmath$\delta$ & \textbf{Cov.} & \textbf{Size} \\
\midrule
Top-1 & 0.712 & 1.000 & 0.869 & 1.269 & 0.020 & 0.550 & 0.880 & 1.536 \\
Top-1 & 0.712 & 1.000 & 0.876 & 1.356 & 0.010 & 0.550 & 0.889 & 1.592 \\
Top-1 & 0.712 & 1.000 & 0.853 & 1.185 & 0.020 & 0.500 & 0.855 & 1.419 \\
Top-1 & 0.712 & 1.000 & 0.910 & 1.592 & 0.020 & 0.700 & 0.911 & 1.757 \\
Top-1 & 0.712 & 1.000 & 0.916 & 1.669 & 0.010 & 0.700 & 0.916 & 1.812 \\
Top-1 & 0.712 & 1.000 & 0.759 & 0.960 & 0.150 & 0.500 & 0.760 & 0.987 \\
Top-1 & 0.712 & 1.000 & 0.775 & 0.953 & 0.100 & 0.450 & 0.775 & 1.045 \\
Top-1 & 0.712 & 1.000 & 0.806 & 0.993 & 0.050 & 0.400 & 0.809 & 1.176 \\
Top-1 & 0.712 & 1.000 & 0.770 & 0.902 & 0.050 & 0.300 & 0.766 & 1.017 \\
\midrule
% --- Top-2 (replaced with new values) ---
Top-2 & 0.868 & 1.947 & 0.953 & 2.311 & 0.010 & 0.700 & 0.953 & 2.790 \\
Top-2 & 0.868 & 1.947 & 0.935 & 1.726 & 0.020 & 0.550 & 0.938 & 2.098 \\
Top-2 & 0.868 & 1.947 & 0.911 & 1.505 & 0.020 & 0.400 & 0.909 & 1.831 \\
Top-2 & 0.868 & 1.947 & 0.926 & 1.646 & 0.020 & 0.450 & 0.926 & 1.951 \\
Top-2 & 0.868 & 1.947 & 0.942 & 1.974 & 0.010 & 0.550 & 0.943 & 2.244 \\
\bottomrule
\end{tabular}
\caption{Top \((\delta,\varepsilon)\) pairs maximizing coverage gain vs.\ Human and size gain vs.\ AI for \textbf{GPT-5-mini} with \emph{Top-1, top-2} strategy. Means shown; standard deviations not shown.}
\label{tab:gpt5mini_hai_topk1_extended}
\end{table*}

\fi

\bibliographystyle{iclr2026_conference}
\bibliography{iclr2026/iclr2026_conference}

\newpage
\appendix

\input{appendix.tex}

\end{document}

\end{document}