arXiv CSopen access

Adaptive Budget Allocation in LLM-Augmented Surveys

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

machine learning, deep learning, neural networks

Adaptive Budget Allocation in LLM-Augmented Surveys Zikun Ye Michael G. Foster School of Business, University of Washington, [email protected]

Jiameng Lyu* Department of Management Science, School of Management, Fudan University, Shanghai, China, [email protected]

arXiv:2604.12497v1 [cs.LG] 14 Apr 2026

Rui Tao Guanghua School of Management, Peking University, [email protected]

Large language models (LLMs) can generate survey responses at low cost, but their reliability varies substantially across questions and is unknown before data collection. Deploying LLMs in surveys still requires costly human responses for verification and correction. How should a limited human-labeling budget be allocated across questions in real time? We propose an adaptive allocation algorithm that learns which questions are hardest for the LLM while simultaneously collecting human responses. Each human label serves a dual role: it improves the estimate for that question and reveals how well the LLM predicts human responses on it. The algorithm directs more budget to questions where the LLM is least reliable, without requiring any prior knowledge of question-level LLM accuracy. We prove that the allocation gap relative to the best possible allocation vanishes as the budget grows, and validate the approach on both synthetic data and a real survey dataset with 68 questions and over 2,000 respondents. On real survey data, the standard practice of allocating human labels uniformly across questions wastes 10–12% of the budget relative to the optimal; our algorithm reduces this waste to 2–6%, and the advantage grows as questions become more heterogeneous in LLM prediction quality. The algorithm achieves the same estimation quality as traditional uniform sampling with fewer human samples, requires no pilot study, and is backed by formal performance guarantees validated on real survey data. More broadly, the framework applies whenever scarce human oversight must be allocated across tasks where LLM reliability is unknown. Key words : Survey Design; Large Language Models; Online Learning Algorithms; Prediction-Powered Inference

Introduction

Generative AI is increasingly used as a low-cost first-pass layer in data collection workflows: it can produce predictions, content, and synthetic responses at scale, but its reliability varies sharply across tasks and is rarely known before deployment (Peng et al. 2025, Ziems et al. 2024, Dominguez-Olmedo et al. 2024). As a result, organizations still need human * Corresponding Author: Jiameng Lyu 1

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

verification and correction, yet human effort is costly, slow, and limited. A central operational question is how to allocate scarce human oversight across tasks in real time so that AI creates value without compromising quality. LLM-augmented surveys provide a concrete and important instance of this problem. Survey platforms and market research firms are exploring LLM-generated respondent panels to reduce fielding costs and accelerate data collection (Brand et al. 2023, Argyle et al. 2023, Wang et al. 2024). However, LLMs cannot reliably replace human respondents: their predictions exhibit systematic biases and question-type-dependent accuracy (Motoki et al. 2024, Brucks and Toubia 2025, Toubia et al. 2025). A more effective approach is to combine LLM predictions with human responses, using cheap LLM output to reduce the number of human labels needed while correcting for LLM errors. Several frameworks formalize this idea, including prediction-powered inference (PPI; Angelopoulos et al. 2023a,b), finetuning-then-rectification (Wang et al. 2025), and mixed human-LLM designs (Broska et al. 2025, Yin and Xin 2025). These hybrid frameworks reduce but do not eliminate the need for human labels: human responses remain the ground truth that corrects LLM bias, and collecting them is costly and slow. In practice, a study often involves many estimation targets sharing a limited labeling budget, such as questions in a survey, product concepts in a market test, or strata in a stratified study. A key challenge is that LLM prediction quality varies dramatically across survey questions (Dominguez-Olmedo et al. 2024, Peng et al. 2025, Toubia et al. 2025), and this heterogeneity persists even after prompt engineering or fine-tuning (Wang et al. 2025, Krsteski et al. 2025). This variation directly determines how many human labels each question requires: questions where LLM predictions closely match human responses need few human labels, while questions where they diverge need many more (Neyman 1934). When this variation is large, directing more of the budget to the harder targets can substantially reduce the aggregate estimation error compared to allocating labels uniformly. When the variation is small, uniform allocation is near-optimal, and no adaptive method is needed. In practice, however, how well the LLM performs on each question is unknown before data collection begins. Estimating this for every question would require a costly pilot study, and such estimates may not transfer across populations, prompts, or survey instruments. At the same time, in online data collection, human responses arrive sequentially, which

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

makes it feasible to adapt the allocation in real time: the survey designer can use early responses to learn which questions are hard for the LLM and redirect subsequent budget accordingly. This motivates the central research question of this paper: how should a survey designer adaptively allocate a finite human-labeling budget across questions when questionlevel LLM accuracy is unknown before data collection begins? We address this question by developing an online learning framework for budget allocation within PPI. The key quantity governing the allocation is the variance of the humanLLM residual for each question, denoted Aq : it captures how much of the response variation the LLM fails to predict. We design a UCB-based algorithm that learns tAq u online while allocating the budget, and prove it achieves Opln B{B 2 q regret relative to the Neyman oracle. We compare UCB against several natural benchmarks on both synthetic and real survey data, where it consistently closes the majority of the gap between uniform allocation and the infeasible oracle. More precisely, Aq is the variance of the residual between human and LLM responses: when LLM predictions closely match human responses, Aq is small and few human labels suffice; when they diverge, Aq is large and more labels are needed. If tAq u were known, the optimal allocation would follow the classical Neyman square-root rule (Neyman 1934), a directing human labels in proportion to wq Aq {cq , where wq is the importance weight and cq is the per-label cost. The challenge is that they are unknown before data collection and must be learned from the same data used for estimation. To address this, we propose an Upper Confidence Bound (UCB) allocation policy that learns rectification difficulties online while allocating the budget. At each step, the algorithm selects the question with the highest uncertainty-adjusted marginal efficiency: a UCB index that balances the current difficulty estimate against a confidence bound reflecting estimation uncertainty. Each human label serves a dual role: it improves the population mean estimate for that question and simultaneously reveals information about the question’s difficulty through the paired human-LLM residual. The algorithm requires no prior knowledge of LLM accuracy, is computationally lightweight, and can serve as a practical alternative to uniform sampling. We prove that this policy achieves Opln B{B 2 q regret relative to the Neyman oracle for both PPI and PPI++ estimators, meaning that the efficiency loss from not knowing the difficulties vanishes rapidly as the budget grows.

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

We compare UCB against several allocation strategies on both synthetic and real survey data. In controlled synthetic experiments (Q“100), UCB tracks the oracle closely at every budget level, and its regret follows the predicted Opln B{B 2 q rate. The synthetic results also reveal that the value of adaptive allocation is driven by heterogeneity in tAq u rather than by overall LLM quality: improving LLM accuracy reduces the MSE for all strategies equally, but it does not change which one performs best. We then evaluate on real survey data from the Twin-2K-500 digital twin dataset (Toubia et al. 2025), which contains over 2,000 US respondents across 500+ survey questions; we use the 68-question retest battery from Wave 4, spanning cognitive heuristic tasks, behavioral economics experiments, and political opinion items, each with paired human and LLM responses. We compare UCB against four benchmarks: the oracle (Neyman allocation with known difficulties), uniform allocation (equal samples per question), ε-greedy (a standard adaptive baseline from the bandit literature), and explore-then-commit (ETC), which mimics the common practice of running a pilot study before committing to a fixed allocation. All policies use the same PPI++ estimator and differ only in how they allocate human labels. UCB achieves the lowest MSE among all implementable policies at every budget level. The standard uniform allocation (equal samples per question) wastes 10–12% of the budget relative to the oracle; UCB reduces this waste to 2–6%, with the gap shrinking as the budget grows. Beyond the baseline, we systematically vary importance weights and sampling costs and find that UCB maintains a gap of approximately 4% regardless of how heterogeneous the weights or costs are, while uniform allocation degrades substantially. We also vary the degree of heterogeneity in rectification difficulties and confirm the same pattern as in the synthetic experiments: the value of adaptive allocation grows monotonically with heterogeneity, and when all questions have similar difficulty, uniform allocation is near-optimal. 1.1.

Related Literature

LLM-augmented surveys and sample allocation. A growing literature studies the use of LLMs as synthetic survey respondents (Argyle et al. 2023, Brand et al. 2023, Ye et al. 2025, Wang et al. 2024, Li et al. 2024, Peng et al. 2025, Toubia et al. 2025, Ziems et al. 2024, Motoki et al. 2024, Brucks and Toubia 2025). Several frameworks have been proposed to combine human labels with LLM predictions, including prediction-powered inference (PPI; Angelopoulos et al. 2023a,b, Mozer 2026, Ji et al. 2025, Vafa et al. 2025),

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

fine-tuning-then-rectification (Wang et al. 2025), and mixed human-LLM designs (Broska et al. 2025, Yin and Xin 2025, Huang et al. 2025). These studies focus on how to combine human and LLM data for a given question. Our work addresses the complementary acrossquestion allocation decision. Classical Neyman allocation (Neyman 1934) assigns samples to strata in proportion to their variance-to-cost ratio, and a rich literature on adaptive survey design shares the philosophy of directing scarce respondent effort where it is most informative (e.g., Toubia et al. 2003, Raghunathan and Grizzle 1995). In LLM-augmented surveys, Neyman allocation requires the variance of the human-LLM residual for each question, which is unknown before data collection. Our work learns these residual variances online with formal regret guarantees. Online learning and bandit algorithms. Our problem of sequentially allocating a budget across estimation targets under uncertainty connects to the multi-armed bandit literature (Auer et al. 2002, Lattimore and Szepesvári 2020), its resource-constrained variants (bandits with knapsacks; Badanidiyuru et al. 2018, Agrawal and Devanur 2016), and UCB-based approaches in operational settings such as dynamic pricing (Cohen et al. 2025). However, these formulations target cumulative reward maximization, whereas our objective is to minimize the terminal aggregate estimation error across a portfolio of estimands. We adopt a terminal-MSE-gap regret definition similar to that of Carpentier et al. (2015), who model stratified sampling as a bandit problem. However, we focus on the LLM-augmented survey problem, where the information source is the PPI/PPI++ residual from paired human-LLM observations. Furthermore, we must handle heterogeneous costs in both PPI/PPI++ settings, and address the additional challenge of jointly learning the tuning parameter and the residual variance for each question in the PPI++ setting. In a related vein, Li et al. (2026) study sequential hypothesis testing with heterogeneous LLMs, and Simchi-Levi and Wang (2025) study the trade-off between regret minimization and statistical inference in bandit problems. Human-AI collaboration. More broadly, our problem connects to the growing literature on how to allocate human oversight across AI-generated outputs. Dai and Swaminathan (2025) identify human-AI interaction as a central pillar of AI in operations, emphasizing the need for frameworks that determine when and where human intervention adds value. Fügener et al. (2026) study when AI should automate tasks versus augment human judgment, showing that the optimal division depends on the type of complementarity

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

between human and AI capabilities. DiSorbo et al. (2025) study how to direct human attention to AI predictions most likely to be unreliable, using warnings and endorsements to improve human-AI collaboration. Related work includes fairness in human-AI collaboration (Ge et al. 2023) and trust in human-robot decision-making (Bhat et al. 2025). Our work contributes to this literature by providing an online algorithm that learns where human oversight is most needed and allocates effort accordingly, with formal performance guarantees. Organization of the paper. The remainder of this paper is organized as follows. Section 2 formalizes the problem. Section 3 presents the UCB algorithm and its regret guarantee. Section 4 extends the framework to the PPI++ estimator. Sections 5 and 6 validate the approach on synthetic and real survey data, respectively. Section 7 concludes. Online Appendix A extends the allocation framework to general M -estimation targets.

Problem Formulation

In the following, we formalize our LLM-augmented survey design problem. We first introduce the survey design setting in Section 2.1. We then review prediction-powered inference (PPI), highlighting the variance of the LLM prediction residual, called rectification difficulty, that governs estimation variance in Section 2.2. Last, we frame our problem as an online learning problem, in which rectification difficulties are unknown and must be learned sequentially, and define regret relative to the oracle in Section 2.3. 2.1.

Survey Design Setting

Consider a set of target survey questions T “ t1, . . . , Qu. For each question q P T and respondent i, let Xq,i P X denote the features associated with question q and respondent i (e.g., question text, response options, and respondent demographics), and let Yq,i P Y denote the human response (e.g., a rating or choice indicator). Within each question, observations are i.i.d. from a question-specific population distribution: i.i.d.

pXq,i , Yq,i q „ Pq . We write PqX for the marginal covariate distribution of Xq and Pq p¨ | Xq for the conditional response distribution, so that Pq “ PqX b Pq p¨ | Xq.

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

The estimand is the population mean response θq˚ :“ EPq rYq s. Given importance weights Q twq uQ q“1 of survey questions, the survey design goal is to choose sample sizes tnq uq“1 of

survey questions to minimize the weighted aggregate MSE: min tnq u

Q ÿ

ı ” wq E pθ̂q ´ θq˚ q2

q“1

s.t.

Q ÿ

cq nq ď B.

q“1

The per-label cost for question q is cq ą 0, and the total human-label budget is B. Throughout, we use individual survey questions as the allocation unit and scalar population means as the estimand. The framework extends in two directions. First, the allocation unit can be a question module rather than a single question: many surveys group questions into thematic modules and assign each respondent to one or more modules, as in split questionnaire designs (Raghunathan and Grizzle 1995). Section 6.5 validates modulelevel allocation on real data. Second, the estimand can be vector-valued (e.g., regression coefficients or conjoint partworths), with the scalar difficulty derived from a sandwich covariance; Online Appendix A develops this M -estimation extension with a synthetic data experiment of the MNL choice model estimation for illustration. 2.2.

Prediction-Powered Inference (PPI) and Rectification Difficulty

LLM An LLM provides a low-cost predictor f : X Ñ Y, yielding a surrogate prediction Yq,i :“

f pXq,i q. For each question q, the researcher has access to two data sources: a labeled sample of nq costly human responses, each paired with an LLM prediction on the same features, and an unlabeled synthetic pool of mq LLM predictions, obtained by querying the LLM at low cost and large scale without collecting any human responses. Prediction-powered inference (PPI; Angelopoulos et al. 2023a) combines these two sources into an unbiased estimator for θq˚ : mq

θ̂qPPI “

1 ÿ LLM Y mq j“1 q,j loooooomoooooon

˘ 1 ÿ` LLM ` Yq,i ´ Yq,i , nq i“1 looooooooooomooooooooooon

LLM prediction (unlabeled)

rectification (labeled)

where j indexes the unlabeled synthetic pool and i indexes the labeled sample. The first term averages the LLM’s predictions across the synthetic pool. The second term corrects for the LLM’s systematic bias using paired human–LLM observations: each difference LLM Ỹq,i :“ Yq,i ´ Yq,i isolates the LLM’s prediction error on respondent i, and averaging these

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

residuals yields an unbiased correction since ErỸq s “ θq˚ ´ Erf pXq qs exactly offsets the LLM bias in the first term. Since the labeled and synthetic samples are independent, the variance decomposes as ˘ ` ˘ ` ˘ ` 1 1 Var YqLLM ` Var Yq ´ YqLLM . Var θ̂qPPI “ mq nq

(1)

Define the rectification difficulty of question q as the residual variance ` ˘ Aq :“ VarpỸq q “ Var Yq ´ YqLLM . Since synthetic responses can be generated cheaply at any scale, we work in the syntheticdata-rich (SDR) regime and set mq Ñ 8 for theoretical analysis. This is without loss of generality: the synthetic pool size mq is not a decision variable and can be chosen independently of the human-label allocation tnq u. As mq Ñ 8, the first term in Eq. (1) vanishes and the PPI estimation variance reduces to ` ˘ Aq , Var θ̂qPPI “ nq which implies that optimal survey allocation is governed by tAq u. 2.3.

Online Learning Framework and Regret

We now frame the budget allocation problem as an online learning problem. Since θ̂qPPI is unbiased, its MSE equals its variance, so the design objective from Section 2.1 reduces ř ř to minimizing q wq Varpθ̂qPPI q “ q wq Aq {nq under the SDR regime. If the rectification difficulties tAq u were known, this becomes Q ÿ

Aq min wq tnq u nq q“1

s.t.

Q ÿ

cq nq ď B.

q“1

The optimal solution follows a Neyman-type square-root allocation rule: d wq A q B n˚q “ řQ a , qPT . cq wj Aj cj j“1

(2)

Thus, questions that are more important (large wq ), harder to rectify (large Aq ), or cheaper (small cq ) receive more human labels. We refer to Eq. (2) as the oracle allocation. However, this oracle is not directly implementable because it requires knowledge of tAq u. Since Aq “ VarpYq ´ YqLLM q depends on the joint distribution of human responses and

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

LLM predictions, it is unknown before any human data are collected and varies across questions, populations, and LLM models. One could run a pilot survey to estimate tAq u before committing to an allocation, but this requires choosing how much of the budget to spend on the pilot versus the main study, and pilot estimates from a small sample may be unreliable. This motivates an online formulation that learns tAq u while allocating the budget, avoiding the need for a separate pilot phase. We model data collection as a sequential allocation process. At each step t, a policy selects a question qt P T based on past observations, collects one additional human response for that question (paying cost cqt ), queries the LLM on the same covariates, and obtains one residual sample Ỹqt ,t “ Yqt ,t ´ YqLLM . Let nq,t be the number of human–LLM pairs collected t ,t for question q up to time t, and let nq,B be the final allocation to question q when the algorithm terminates. qut´1 An adaptive policy π “ tπt u maps the history ht´1 “ tpqs , Yqs ,s , YqLLM s“1 to the next s ,s question qt . Because tAq u are unknown, the policy faces an exploration–exploitation tradeoff: sampling a question to reduce uncertainty in its difficulty estimate versus allocating budget to questions that appear most impactful under current estimates. We measure performance by regret, which is the gap between the expected terminal objective achieved by π and that of the oracle allocation: «Q ff Q ÿ ÿ Aq Aq RpBq :“ Eπ wq wq ˚ . ´ nq,B nq q“1 q“1 The goal is to design an online allocation policy with sublinear regret as B grows. The next section develops a UCB-based algorithm that learns tAq u from PPI residuals and achieves RpBq “ Opln B{B 2 q. We note that the LLM augmentation and the adaptive allocation address complementary aspects of the problem. The LLM augmentation via PPI reduces the per-question variance from VarpYq q to Aq , lowering the overall number of human labels needed. The adaptive allocation exploits heterogeneity in tAq u across questions to further improve efficiency. Importantly, the allocation problem retains the same structure with or without LLM predictions. Without PPI, the estimator for each question is the sample mean Ȳq with perquestion variance VarpYq q{nq ; the allocation-relevant quantity is simply VarpYq q, playing the same role as Aq . With PPI, the variance reduces to Aq {nq where Aq “ VarpYq ´ YqLLM q

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

can be substantially smaller than VarpYq q for questions where the LLM is informative. In both cases, the online allocation problem has the same ¨{nq structure; the adaptive algorithm we develop in the next section applies to both settings. The case without LLM predictions corresponds to the classical adaptive stratified sampling problem studied in Carpentier et al. (2015).

Algorithm Design and Regret Analysis

We first motivate the algorithm design through a marginal-efficiency interpretation of the oracle allocation in Section 3.1, then construct the UCB index that replaces unknown difficulties with confidence-adjusted estimates in Section 3.2, and present the full algorithm in Section 3.3. Section 3.4 establishes the regret guarantee. 3.1.

Oracle Case with Known Aq : Marginal-Efficiency Interpretation

Recall from Section 2 that Varpθ̂qPPI q “ Aq {nq . To motivate our adaptive approach, we first analyze the case where the rectification difficulties Aq are known, but the budget is allocated sequentially. We frame this through the lens of Marginal Efficiency. To build intuition, consider two survey questions with A1 “ 4, A2 “ 1 and equal weights a and costs (wq “ cq “ 1). The oracle allocates n˚1 “ 2n˚2 (proportional to Aq ). Suppose both questions currently have nq “ 10 samples. The marginal efficiency of adding one more sample to question 1 is A1 {n21 “ 4{100 “ 0.04, versus A2 {n22 “ 1{100 “ 0.01 for question 2. The greedy rule correctly directs the next sample to the harder question. More generally, consider the current state at round t, where each question q has been allocated nq,t samples. If we were to allocate one additional sample to question q, the ř objective function q wq Anqq would decrease. The Marginal Variance Reduction is given by the negative partial derivative with respect to nq : ˆ ˙ B Aq wq Aq wq “ ´ Bnq nq n2q Since each sample for question q costs cq , we define the Marginal Efficiency Index Iq,t as the variance reduction per unit of currency spent: ˚ Iq,t “

Marginal Variance Reduction wq Aq “ . Marginal Cost cq n2q,t

˚ A policy that greedily selects q “ arg max Iq,t at each step converges to the optimal oracle

allocation n˚q , because the greedy rule drives the system toward a state where the marginal efficiency wq Aq {pcq n2q q is equalized across all q, which is precisely the first-order condition of the Lagrangian of the static optimization problem.

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

3.2.

UCB Index Construction

In practice, Aq is unknown. The key role of the LLM is to produce cheap paired predictions f pXq so that each costly human label immediately yields a variance-relevant residual sample Ỹ “ Y ´ f pXq. For each question q, let nq,t be the number of human labels collected pq,t be the unbiased sample variance of tỸq,i unq,t : up to round t, and let A i“1

pq,t “ A

nq,t ÿ 1 pỸq,i ´ Ỹ¯q,t q2 . nq,t ´ 1 i“1

(3)

pq,t can under-sample a A naive plug-in greedy approach using the empirical variance A pq,t was accidentally low. question whose true Aq is high but whose initial A To address this, we use the Upper Confidence Bound (UCB) principle. For a bounded random variable Ỹ with range R, the deviation of the sample variance from the true variance is controlled by: Aq ď AUCB q,t , where d p AUCB q,t :“ Aq,t ` 2R

pq,t lnp2{δq,t q 2R2 lnp2{δq,t q 2A ` . nq,t ´ 1 nq,t ´ 1

We define the UCB index to prioritize questions that either have high estimated difficulty (exploitation) or high estimation uncertainty (exploration): UCB Iq,t “

wq AUCB q,t . cq n2q,t

pq,t : when the The empirical Bernstein bound above contains the question-dependent A pq,t ), the confidence width shrinks faster, so “easy” questions exit LLM is accurate (small A the exploration phase sooner and stop consuming budget. This variance-adaptive tightening allows the algorithm to concentrate its exploration budget on questions with genuinely high uncertainty, echoing the structure of the Neyman rule that allocates proportionally a to Aq . 3.3.

Algorithm Description

pq,t wellThe algorithm enforces an initialization of K ě 2 labels per question to make A defined, then repeatedly allocates the next human query to the question with the largest UCB index. Each allocation uses the LLM on the same covariate/prompt to produce a

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

Algorithm 1 UCB-Based Online Survey Design with LLM Augmentation and PPI Q

1: Input: Budget B, costs tcq uq“1 , weights twq uq“1 , range R, confidence δ, initialization

K ě 2, LLM predictor f . 2: for each question q P t1, . . . , Qu do

Ź Initialization Phase

X Sample K initial covariates tXq,i uK i“1 „ Pq .

LLM Collect human responses Yq,i „ Pq p¨ | Xq,i q and compute LLM prediction Yq,i “

f pXq,i q, for each i P rKs. 5: 6:

Compute residuals: Ỹq,i “ Yq,i ´ f pXq,i q, for each i P rKs. řnq,QK 1 pq,QK “ Compute the variance A pỸq,i ´ Ỹ¯q,QK q2 , where nq,QK “ K. nq,QK ´1

i“1

7: Set Tmax “ tB{ minq cq u, δq,t “ δ{pQTmax q, t Ð QK, and Bt Ð B ´ 8: for t “ QK, QK`1, . . . until Bt ă maxq cq do 9: 10:

12:

q“1 cq K.

Ź UCB Selection Phase

Selection through UCB Indices: For each q, compute UCB Iq,t “

11:

řQ

wq ¨ AUCB q,t . 2 cq nq,t

UCB Select qt “ arg maxq Iq,t .

Query & LLM Pair:

13:

Sample a new covariate Xqt „ PqXt from the target population.

14:

Query human label Yqt „ Pqt p¨ | Xqt q

15:

“ f pXqt q for the same Xqt . Generate LLM prediction YqLLM t

16:

Compute residual: Ỹqt “ Yqt ´ YqLLM . t

17: 18:

Update: pqt ,t`1 . Let Bt`1 “ Bt ´ cqt . Let nqt ,t`1 “ nqt ,t ` 1. Update A

19: Output: For each q, report the PPI estimate θ̂qPPI “ Ȳq,nq `

˘ LLM LLM Ȳq,m ´ Ȳ , where q,nq q

LLM Ȳq,m is the LLM-only mean over a large unlabeled pool (mq " nq ) and the difference q LLM LLM Ȳq,m ´ Ȳq,n is the bias-correction term. q q

paired prediction and thus an immediate residual update. It then proceeds sequentially until the remaining budget falls below maxq cq . The adaptive phase stops once the remaining budget falls below cmax , so every question compared in the UCB arg max is feasible throughout the phase. The unspent remainder RemB P r0, cmax q is bounded and asymptotically negligible relative to B.

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

3.4.

Regret Analysis

We now state the main theoretical guarantee for Algorithm 1. Recall Aq :“ VarpỸq q with Ỹq :“ Yq ´ f pXq q. Let nq,B be the total number of human labels allocated to question q when the algorithm stops under budget B. Define cmin :“ minq cq , cmax :“ maxq cq , and Tmax :“ tB{cmin u. The oracle allocation is d Q ÿ a B wq Aq ˚ nq “ řQ a , Λ :“ wj Aj cj , cq wj Aj cj j“1 j“1

n˚q “ βq :“ B

a wq Aq {cq . Λ

The regret is defined as «Q ff Q ÿ wq Aq ÿ wq Aq RpBq :“ E ´ . nq,B n˚q q“1 q“1

(4)

We impose two assumptions for the theoretical analysis of Algorithm 1. Throughout, we assume wq ą 0 and cq ą 0 for all q, and that the budget is large enough for initialization: ř Bě Q q“1 cq K. Assumption 1. For every q P rQs and every draw i, the residual satisfies Ỹq “ Yq ´ YqLLM P rL, U s almost surely with range R :“ U ´ L ă 8. Assumption 2. We assume Amin :“ minq Aq ą 0, where Aq :“ VarpYq ´ YqLLM q. Assumption 1 requires the PPI residual Ỹq “ Yq ´ YqLLM to be bounded, which is needed to apply finite-sample variance concentration inequalities. This holds whenever survey responses are bounded, as in Likert scales, binary choices, or bounded-range ratings. Assumption 2 requires that no question is perfectly predicted by the LLM, so that every question retains some residual variance. If the LLM predicted a question perfectly, that question would require no human labels and could be excluded from the allocation problem. With these assumptions, we have the following theoretical guarantee for the regret of Algorithm 1. Theorem 1. Suppose Assumptions 1–2 hold. Run Algorithm 1 with K ě 2. Let Vmax :“ řQ q“1 wq Aq {K. Then for all sufficiently large B, ˆ ˙ lnpQTmax {δq RpBq ď O ` δVmax . B2 ` ˘ In particular, choosing δ “ B ´2 yields RpBq “ O lnBB2 . The proof proceeds in three steps. We present the key constructions and results here; complete algebraic details are in Online Appendix B.

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

Step I: Good Event and Optimism To control regret, we define a high-probability

good event under which the empirical variance concentrates uniformly around the true rq,s denote the sample variance difficulty for all questions and all rounds. For each pq, sq, let A computed from the first s i.i.d. residuals of question q. Set δq,s :“ δ{pQTmax q and define + #ˇ c ˇ b Q Tč max č ˇa ˇ rq,s ˇ ď R 2 lnp2{δq,s q . ˇ Aq ´ A (5) E :“ ˇ ˇ s´1 q“1 s“K pq,t “ A rq,nq,t , the event E implies the adaptive-time event Since A d + #ˇ ˇ b Q Tč max č a ˇ ˇ 2 lnp2{δ q q,t pq,t ˇ ď R ˇ Aq ´ A E 1 :“ , ˇ ˇ n ´ 1 q,t q“1 t“1 i.e., E Ď E 1 . Indexing by the deterministic sample count s avoids optional-stopping complications: nq,t is random, so a direct union bound over pq, tq in E 1 would be invalid, whereas each pq, sq in E involves a fixed-size i.i.d. sample. Lemma 1. Under Assumption 1, PpEq ě 1 ´ δ. Proof Sketch. By Assumption 1, Zq,i :“ pỸq,i ´ Lq{R P r0, 1s. For each fixed pq, sq, the square-root variance concentration inequality of Maurer and Pontil (2009) applied to b a rq,s | ą RHS of (5)q ď δq,s . A union bound over at tZq,i us and rescaled gives Pp| Aq ´ A i“1

most Q ¨ Tmax pairs yields PpE c q ď δ. ˝ b a pq,t ` ϵ implies Aq ď AUCB , so the true marginalOptimism. On E, the condition Aq ď A q,t efficiency index is upper-bounded by the optimistic index: wq Aq ˚ UCB Iq,t “ ď Iq,t :“ 2 cq nq,t

wq AUCB q,t . cq n2q,t

This ensures that the algorithm never systematically under-samples a question whose true difficulty is high. Step II: Allocation Gap Bound On the good event E, the UCB selection rule forces the

realized allocation to track the oracle proportions. The key argument uses a pigeonhole construction: there exists a question qa whose allocation is at least proportional to its ˚ oracle share, and the UCB selection rule ensures that every other question q satisfies Iq,t ď UCB Iq,t ď IqUCB . Chaining this inequality (see Online Appendix B for the full derivation) a ,t

yields |nq,B ´ n˚q | “ O

´a ¯ B lnp1{δq ,

@q P rQs.

(6)

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

Step III: From Allocation Gaps to Regret We convert the allocation gaps into regret

via a second-order Taylor expansion of fq pnq “ wq Aq {n around n˚q . Summing over questions: Q ÿ “

Q Q ÿ ÿ ‰ wq Aq wq Aq ˚ fq pnq,B q ´ fq pn˚q q “ ´ ` pn ´ n q pnq,B ´ n˚q q2 . q,B q ˚ q2 3 pn ξ q q q“1 q“1 q“1 looooooooooooomooooooooooooon loooooooooooomoooooooooooon Term 1

Term 2

Term 1 telescopes by the optimality condition wq Aq {pn˚q q2 “ λpBqcq , yielding Term 1 “ λpBq ¨ RemB where RemB P r0, cmax q is the leftover budget, contributing Op1{B 2 q. Term 2 is bounded using Eq. (6): each squared gap is OpB ln Bq, and the 1{ξq3 « 1{pn˚q q3 „ 1{B 3 prefactor yields a total of Opln B{B 2 q. Combining with PpE c q ď δ “ B ´2 completes the proof.

Extension to PPI++

The standard PPI estimator in Section 2.2 subtracts the full LLM prediction from each human response. This improves over the sample mean only when the LLM is sufficiently correlated with human responses: specifically, PPI reduces variance when CovpYq , YqLLM q ą VarpYqLLM q{2. When the LLM is a weak predictor, the rectification difficulty Aq “ VarpYq ´ YqLLM q can exceed VarpYq q, making PPI worse than the sample mean estimator. PPI++ (Angelopoulos et al. 2023b) addresses this by introducing a tuning parameter λ P r0, 1s that controls how much of the LLM prediction to use. The rectification residual becomes Y ´ λY LLM , where λ is learned from paired data to minimize residual variance. When λ˚ “ 0, the estimator ignores the LLM and reduces to the sample mean; when λ˚ ą 0, it leverages the LLM signal for variance reduction. We now extend our online allocation framework to this setting. Algorithmically, this alters only how we (i) construct residuals and (ii) build a valid UCB for the corresponding difficulty parameter. 4.1.

PPI++ Estimator and Tuned Rectification Difficulty

For completeness, we briefly review the PPI++ estimator and the optimal tuning parameter λ˚ ; the material in this subsection is standard and follows Angelopoulos et al. (2023b). Fix a question q P rQs. Recall that YqLLM “ f pXq q, i.e., the LLM-generated counterpart LLM of Yq introduced earlier. We observe paired samples tpYq,i , Yq,i quiě1 that are i.i.d. across

respondents: each pair is an independent draw from the joint distribution of pYq , YqLLM q. For any tuning parameter λ P r0, 1s, define the tuned residual Ỹq pλq :“ Yq ´ λYqLLM .

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

In the synthetic-data-rich regime (so that the LLM-only mean can be treated as known up to negligible error), the PPI++ estimator of θq˚ “ ErYq s can be written as ¯ ´ LLM LLM , λ P r0, 1s, ´ Ȳ θ̂qPPI`` pλq “ Ȳq,nq ` λ Ȳq,m q,nq q which is unbiased for any fixed λ, and when mq Ñ 8, satisfies ` ˘ ` PPI`` ˘ Var Yq ´ λYqLLM pλq “ Var θ̂q . nq The PPI++ tuning parameter is the clipped population regression coefficient ˜ ¸ LLM CovpY , Y q q q λ˚q :“ Πr0,1s , VarpYqLLM q

(7)

and the resulting tuned rectification difficulty is ` ˘ ` ˘ Aq pλ˚q q :“ Var Ỹq pλ˚q q “ Var Yq ´ λ˚q YqLLM . By optimality of λ˚q , Aq pλ˚q q ď VarpYq ´ YqLLM q, i.e., PPI++ is never worse (in asymptotic variance) than standard PPI. 4.2.

Algorithm Design with PPI++

Algorithm 2 presents the PPI++ variant of the UCB allocation procedure. Its high-level structure mirrors Algorithm 1: after initializing each question with K ě 2 paired samples, the algorithm sequentially allocates human labels to the question with the largest UCB index of marginal-efficiency until the remaining budget falls below maxq cq . The key differences from Algorithm 1 are threefold. 1. Residual construction and updating. In standard PPI, each human label yields LLM a fixed residual Ỹq,i “ Yq,i ´ Yq,i , and the unknown difficulty Aq “ VarpYq ´ YqLLM q

is estimated by the sample variance of these residuals. In PPI++, the residual is LLM parametrized by a tuning coefficient: Ỹq,i pλ̂q,t q “ Yq,i ´ λ̂q,t Yq,i , where λ̂q,t is the

clipped sample regression coefficient Eq. (7) computed from all paired observations available for question q at time t. The unknown difficulty accordingly becomes Aq pλ˚q q “ VarpYq ´ λ˚q YqLLM q, and the difficulty estimator is the sample variance of these tuned residuals. 2. UCB construction under joint uncertainty. This parametrization introduces an additional source of estimation noise, the coefficient λ̂q,t is itself learned, so the UCB must account for uncertainty in both the variance estimate and the tuning parameter.

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

3. PPI++ output estimator. At termination, the algorithm reports the PPI++ esti˘ ` LLM LLM , where mq " nq and λ̂q,B ´ Ȳq,n mate for each question: θ̂qPPI`` “ Ȳq,nq ` λ̂q,B Ȳq,m q q is the final tuning coefficient at termination. Setting λ̂q,B “ 1 recovers the standard PPI output of Algorithm 1.

Algorithm 2 UCB-Based Online Survey Design with LLM Augmentation and PPI++ Q

1: Input: Budget B, costs tcq uq“1 , weights twq uq“1 , range R, confidence δ, initialization K ě 2, LLM

predictor f . 2: for each question q P t1, . . . , Qu do

Ź Initialization Phase

X Sample K initial covariates tXq,i uK i“1 „ Pq .

LLM LLM K “ f pXq,i q. qui“1 where Yq,i Collect paired samples tpYq,i , Yq,i ˘ ` LLM LLM y y q using all K pairs. q{VarQK pY Fit λ̂q,QK “ Πr0,1s CovQK pYq , Y

y t p¨q and Cov y t p¨q denote the unbiased sample variance and covariance based on the nq,t paired samples (Var collected for question q up to time t. Here t “ QK.) LLM pq,QK pλ̂q,QK q “ Recompute all tuned residuals Ỹq,i pλ̂q,QK q “ Yq,i ´ λ̂q,QK Yq,i for i ď K, set A y QK pỸq pλ̂q,QK qq and nq,QK “ K. Var řQ 7: Set Tmax “ tB{ minq cq u, δq,t “ δ{pQTmax q, t Ð QK, and Bt Ð B ´ q“1 cq K.

8: for t “ QK, QK`1, . . . until Bt ă maxq cq do 9: 10:

Ź UCB Selection Phase

Selection through UCB Indices: UCB pλ̂q,t q “ Compute the marginal-efficiency index Iq,t

wq ¨AUCB q,t pλ̂q,t q cq n2 q,t

`b ˘2 pq,t pλ̂q,t q ` ρ`` (AUCB A ; the confidence radius ρ`` q,t pλ̂q,t q :“ q,t q,t is defined in Eq. (EC.9), Online Appendix C.1) 11: 12: 13: 14: 15: 16: 17:

UCB Select qt “ arg maxq Iq,t pλ̂q,t q.

Query & LLM Pair: Sample Xqt „ PqXt , query Yqt „ Pqt p¨ | Xqt q, generate YqLLM “ f pXqt q. t Update: Let nqt ,t`1 “ nqt ,t ` 1 and Bt`1 “ Bt ´ cqt . ` ˘ y t`1 pYq , Y LLM q{Var y t`1 pY LLM q using all nq ,t`1 pairs. Refit λ̂q ,t`1 “ Πr0,1s Cov t

LLM

Recompute all tuned residuals Ỹqt ,i pλ̂qt ,t`1 q “ Yqt ,i ´ λ̂qt ,t`1 Yqt ,i p y t`1 pỸq pλ̂q ,t`1 qq. Aqt ,t`1 pλ̂qt ,t`1 q “ Var t t

for i ď nqt ,t`1 , then recompute `

LLM LLM 18: Output: For each q, report the PPI++ estimate θ̂qPPI`` “ Ȳq,nq ` λ̂q,B Ȳq,m ´ Ȳq,n with mq " nq , q q

where λ̂q,B is the last updated estimate of λq for question q at termination.

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

4.3.

Regret Guarantee for PPI++

Define the oracle allocation by substituting Aq pλ˚q q into the offline rule: d Q b ÿ wq Aq pλ˚q q B ˚ ˚ nq “ ř b , Λpλ q :“ wj Aj pλ˚j qcj . Q c ˚ q w A pλ qc j“1 j“1

Let nq,B denote the number of labels allocated to question q by Algorithm 2. The regret is ff Q «Q ÿ wq Aq pλ˚q q ÿ wq Aq pλ˚q q ´ RpB; λ˚ q :“ E . (8) ˚ n n q,B q q“1 q“1 We impose two mild assumptions for the analysis, analogous to Assumptions 1–2 in the PPI case, with minor adjustments to accommodate the concentration of the tuning parameter λ˚q . Assumption 3. For each q P rQs, Yq P rLY , UY s,

YqLLM P rLY LLM , UY LLM s

almost surely.

Define RY :“ UY ´ LY , RY LLM :“ UY LLM ´ LY LLM , R :“ RY ` RY LLM , MY :“ maxp|LY |, |UY |q, and MY LLM :“ maxp|LY LLM |, |UY LLM |q. Then Ỹq pλq has range at most R for every λ P r0, 1s. Assumption 4. We assume (i) Amin :“ minq Aq pλ˚q q ą 0, where Aq pλ˚q q :“ VarpYq ´ LLM LLM λ˚q YqLLM q, and (ii) for each q P rQs, VarpYqLLM q ě Vmin for some constant Vmin ą 0.

Assumption 3 strengthens the bounded-residual condition (Assumption 1) by requiring Yq and YqLLM to be individually bounded, which ensures uniform variance concentration over all λ P r0, 1s. Assumption 4 extends the nondegeneracy condition (Assumption 2) to the PPI++ setting. Part (i) is the direct analogue: no question is perfectly predicted after tuning. Part (ii) additionally requires the LLM predictions to carry a nonvanishing signal, which is needed for the plug-in estimate λ̂q,t to concentrate around λ˚q . Algorithm 2 achieves the following regret guarantee. Theorem 2. Assume

Assumptions

3–4

hold.

Run

Algorithm

with

K ě

K0 rlnpQTmax {δqs, where K0 depends only on the parameters in Assumptions 3–4. Let ř ˚ Vmax pλ˚ q :“ Q q“1 wq Aq pλq q{K. Then for all sufficiently large B, ˆ ˙ lnpQTmax {δq ˚ RpB; λ q ď O ` δVmax pλ˚ q. B2 ` ˘ In particular, choosing δ “ B ´2 yields RpB; λ˚ q “ O lnBB2 .

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

Proof Sketch. The complete proof is in Online Appendix C. The high-level ideas are

by its identical to those of Theorem 1 after replacing Aq by Aq pλ˚q q and the UCB AUCB q,t PPI++ analogue. Steps II–III (allocation-gap control and corresponding regret conversion) are similar. The nontrivial change is Step I, where we must ensure optimism despite the additional estimation error from the plug-in λ̂q,t . This requires two auxiliary concentration results: (i) a bound on |λ̂q,t ´ λ˚q | via ratio perturbation (Lemma EC.3), and (ii) uniform concentration of σ̂q,t pλq over λ P r0, 1s via a grid-and-Lipschitz argument (Lemma EC.4). The combined PPI++ good event then holds with probability at least 1 ´ δ, and the remainder of the proof follows as in the PPI case.

Synthetic Data Analysis

Next, we evaluate Algorithm 2 on a controlled synthetic environment. All experiments use 200 Monte Carlo replications; shaded bands in figures indicate ˘1 standard error across replications. 5.1.

Experiment Setup

We simulate Q “ 100 survey questions with equal weights wq “ 1 and equal costs cq “ 1. Each question q has a per-question variance scale vq drawn from a log-uniform distribution to create heterogeneous difficulties: vq “

h ¨ eUq , sinh h

i.i.d.

Uq „ Uniformp´h, hq,

(9)

where h is a heterogeneity parameter controlling the spread of question difficulties. The scaling factor h{ sinh h ensures Ervq s “ 1 for all h, so varying h redistributes difficulty across questions without changing the overall MSE scale. Since log vq is uniform on p´h, hq, the ? standard deviation of log-difficulties is sdplog Aq q “ h{ 3 and the coefficient of variation ? of Aq is CVpAq q “ h coth h ´ 1. At the baseline h “ 2.0, CV « 1.04, indicating substantial heterogeneity; at h “ 0.5, CV « 0.29, a nearly homogeneous setting. For each question q, paired observations pY, Sq are generated from a bivariate Gaussian i.i.d.

model with independent standard normals U, ε, η „ N p0, 1q: ? vq U, a ˘ ? ` S “ vq ρ U ` 1 ´ ρ 2 ε , ˘ ? ` Y “ vq U ` σ η η ,

Ysig “

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

where Ysig is a latent signal, S “ f pXq is the LLM prediction correlated with the signal through ρ P r0, 1s, and ση scales additional human response noise. This gives VarpYsig,q q “ VarpSq q “ vq and VarpYq q “ vq p1 ` ση2 q. The true population mean is θq˚ “ 0 for all q. Under this model, the optimal PPI++ tuning parameter is λ˚q “ ρ for all q (since the LLM observes the signal but not the human noise), and the rectification difficulty is Aq “ vq p1 ´ ρ2 ` ση2 q. Since Aq 9vq , questions with larger variance scale are harder to rectify and receive more samples under the oracle allocation Eq. (2). Table 1 summarizes the baseline parameters; Experiments 2 and 3 vary one parameter at a time. Table 1

Baseline parameters for synthetic experiments.

Parameter

Symbol Baseline Role

Questions LLM quality Heterogeneity Human noise Budget (Exp. 1) Budget (Exp. 2–3) Initialization

Q ρ h ση B B K

100 0.7 2.0 0.5 2,000 1,000 3

Number of survey questions Correlation between S and Ysig Spread of vq across questions (CV « 1.04) Additional noise on human response Y « 20 samples per question « 10 samples per question Samples per question before adaptive phase

We compare four allocation policies, all using the PPI++ estimator with plug-in λ̂q and no data splitting: (i) Oracle (Neyman): allocates proportional to

Aq using the true difficulties, i.e., the

offline optimum Eq. (2). (ii) Uniform: equal allocation across all questions, serving as a no-information baseline representing conventional survey sampling. (iii) ε-Greedy: a standard decaying ε-greedy policy from the bandit literature. At round t, with probability εt “ minp1, cQ{tq (where c “ 5) a question is selected uniformly at pq,t {n2 is made. random; otherwise the greedy choice qt “ arg maxq A q,t

(iv) UCB: Algorithm 2 with variance-adaptive confidence bounds, balancing exploitation and exploration. To compare these policies, the primary metric throughout Sections 5–6 is the expected MSE at budget t, defined as MSEptq :“

Q ÿ wq Aq

nq,t q“1

(10)

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

evaluated at each budget step in Figure 1 and at the terminal budget B in all subsequent ř figures and tables. In the equal-weight baseline (wq “ 1 for all q), this reduces to q Aq {nq,t . This is the natural performance measure for two reasons. First, it is the quantity that appears in the regret definition (Eqs. (4) and (8)): the regret RpBq “ MSEpBq ´ MSE˚ pBq ř a directly compares each policy’s expected MSE to the oracle MSE˚ pBq “ p q wq Aq cq q2 {B, so reporting expected MSE aligns the empirical evaluation with the theory. Second, in ř the SDR regime, q wq Aq {nq,t is the oracle allocation objective implied by the asymptotic variance formula. For the plug-in PPI++ implementation used in our experiments, we therefore interpret this quantity as an allocation-quality metric rather than the exact finite-sample conditional MSE of the estimator. 5.2.

Numerical Results

Experiment 1: Policy comparison (Q“100, B“2,000, ρ“0.7, h“2.0). Figure 1 reports results at the baseline parameters. At the terminal budget B “ 2,000, the oracle achieves an expected MSE of 2.628; UCB attains 2.712, ε-greedy 2.857, and uniform 3.529. Measuring the percentage gap to oracle, pMSE ´ MSE˚ q{MSE˚ , UCB is within 3.2%, ε-greedy 8.8%, and uniform 34.4%. The left panel shows how the expected MSE decreases as budget is spent; UCB tracks the oracle closely after the initialization phase (K ¨ Q “ 300 samples), whereas ε-greedy converges more slowly. The center panel (log–log scale) confirms that UCB converges to the oracle rate. The right panel plots the terminal regret of UCB alone across budgets B P t500, 1,000, 2,000, 5,000, 10,000u, showing that UCB regret is consistent

Oracle Uniform -Greedy UCB (Ours)

Expected MSE

20 15 10 5 400

Figure 1

600

800

1000

1200

Budget used

1400

1600

1800

2000

Oracle Uniform -Greedy UCB (Ours) 101

3 × 102 4 × 102

6 × 102

103

Budget used (log scale)

2 × 103

UCB (Ours) O(lnB/B 2)

100

Terminal Regret R(B)

Expected MSE (log scale)

with an Opln B{B 2 q rate, with an empirical log–log slope near ´2.

10 1

10 2

103

Budget B

104

Experiment 1 (Q“100, B“2,000, ρ“0.7, h“2.0, 200 reps). Left: expected MSE Eq. (10) vs. budget (linear). Center: same on log–log scale. Right: UCB terminal regret RpBq across budgets B P t500, . . . , 10,000u with Opln B{B 2 q reference line. Shaded bands: ˘1 SE across replications.

UCB dominates all other policies at every budget level. The ε-greedy policy outperforms uniform only when the budget is sufficiently large (at B “ 2,000 it achieves an 8.8% gap

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

versus uniform’s 34.4%, but at B “ 1,000 it is slightly worse), because its undirected exploration phase consumes a large share of the budget before exploitation begins. UCB, by contrast, directs exploration through variance-adaptive confidence bounds, building reliable Aq estimates faster. Having established UCB’s overall advantage, we next examine how LLM quality and difficulty heterogeneity affect performance. Experiment 2: Effect of LLM quality (B“1,000, varying ρ). Figure 2 varies ρ P t0.0, 0.3, 0.5, 0.7, 0.9, 0.95u. Higher ρ reduces the expected MSE for all policies equally, because Aq “ vq p1 ´ ρ2 ` ση2 q scales all difficulties by the same factor. The relative gap between policies is stable across ρ: this stability is a consequence of the synthetic design, in which ρ is a global parameter that preserves the heterogeneity structure. In real surveys, LLM quality varies across question types (see Section 6, where λ˚q ranges from 0 to 0.72);

Oracle Uniform -Greedy UCB (Ours)

Terminal MSE

10 8 6 4 2

0.0

Figure 2

0.2

0.4

LLM quality

0.6

0.8

Gap to Oracle (Terminal Regret)

the digital twin experiments provide a more demanding test. Oracle Uniform -Greedy UCB (Ours)

3.0 2.5 2.0 1.5 1.0 0.5 0.0 0.0

0.2

0.4

LLM quality

0.6

0.8

Effect of LLM quality ρ (Q“100, B“1,000, h“2.0, 200 reps). Left: expected MSE. Right: terminal regret RpBq. Shaded bands: ˘1 SE across replications. All policies benefit from higher ρ through the PPI++ estimator; relative performance gaps are stable across ρ.

Experiment 3: Effect of heterogeneity (B“1,000, varying h). Figure 3 varies h P t0.5, 1.0, 1.5, 2.0u and reveals the central insight: the value of adaptive allocation is determined by difficulty heterogeneity. When questions are nearly homogeneous (h “ 0.5), uniform allocation is near-optimal and adaptive methods incur unnecessary exploration cost. As heterogeneity increases, uniform’s gap grows from 2.2% to 34.4%, while UCB’s gap grows only from 6.2% to 8.1%, because its directed exploration successfully tracks the increasingly non-uniform oracle allocation.

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

8.0

Gap to Oracle (Terminal Regret)

2.00

Terminal MSE

7.5 7.0 6.5 6.0

Oracle Uniform -Greedy UCB (Ours)

5.5

0.6

Figure 3

0.8

1.0

1.2

1.4

Heterogeneity h

1.6

1.8

2.0

1.75 1.50

Oracle Uniform -Greedy UCB (Ours)

1.25 1.00 0.75 0.50 0.25 0.00 0.6

0.8

1.0

1.2

1.4

Heterogeneity h

1.6

1.8

2.0

Effect of heterogeneity h (Q“100, B“1,000, ρ“0.7, 200 reps). Left: expected MSE. Right: terminal regret RpBq. Shaded bands: ˘1 SE across replications. UCB’s advantage over uniform and ε-greedy grows with heterogeneity; at low h, all policies perform similarly as the oracle allocation is nearly uniform.

Digital-Twin Data Analysis

We now evaluate the UCB allocation algorithm on real survey data from the Twin-2K-500 dataset (Toubia et al. 2025), a large-scale digital twin benchmark in which each human respondent is paired with an LLM-generated “digital twin.” This provides a realistic testbed where the rectification difficulties tAq u arise from genuine human-LLM disagreement patterns rather than a parametric data-generating process. 6.1.

Data and Setup

The Twin-2K-500 dataset contains four survey waves administered to over 2,000 US respondents. Waves 1–3 each cover around 500 questions spanning demographics, psychological scales, cognitive tasks, and behavioral economics. Wave 4 re-administers a subset of questions to the same respondent panel for test-retest reliability assessment. Following the same evaluation protocol of Toubia et al. (2025), we focus on the Wave 4 retest battery and restrict attention to multiple-choice questions. This yields Q “ 68 questions across 14 task types, with between 651 and 2,058 respondents per question (mean 1,271). The dataset provides paired LLM responses generated by GPT-4o from each respondent’s “digital twin” profile. Human and LLM responses are min-max scaled to r0, 1s following the same data processing. We compute the full-sample rectification difficulty Aq “ VarpYq ´ λ˚q YqLLM q for each question, where λ˚q “ CovpYq , YqLLM q{VarpYqLLM q, clipped to r0, 1s, is the optimal PPI++ tuning parameter. Figure 4 plots each question’s rectification difficulty Aq against its optimal PPI++ tuning parameter λ˚q , colored by task type. Two features stand out. First, difficulties are

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

heterogeneous (Aq ranges from 0.024 to 0.239, CV “ 0.63). Second, 38% of questions have λ˚q « 0, meaning the LLM signal does not reduce residual variance for those items. Abs vs Rel Savings (2) Allais Problem (2) Anchoring (4) Conjunction (Linda) (6) Framing Problem (2) Myside Bias (2) Outcome Bias (2)

Rectification difficulty Aq

0.20

Denominator Neglect (1) Less is More (9) Nonseparability of Risks and Benefits (8) Omission Bias (1) Probability Matching vs Maximizing (16) WTA/WTP Thaler Problem (3) False Consensus (10)

0.15

0.10

0.05 0.0 Figure 4

0.1

0.2 0.3 0.4 0.5 0.6 Optimal PPI++ tuning parameter q*

0.7

0.8

Rectification difficulty Aq versus optimal PPI++ tuning parameter λ˚ q for the 68 Wave 4 questions, colored by task type (number of questions in parentheses). Questions with λ˚ q « 0 (left cluster) receive no variance reduction from the LLM.

Experiment setup. We evaluate the same four policies as in Section 5.1: Oracle, Uniform,

ε-greedy, and UCB. In addition, we introduce a fifth policy, Explore-then-Commit (ETC), which operationalizes the natural “pilot study” approach from survey practice. ETC allocates a fraction α of the post-initialization budget uniformly across all questions b to estimate pq {cq comtAq u, then commits the remaining budget to the Neyman allocation nq 9 wq A puted from the pilot estimates. We use α “ 0.3 as the default and examine sensitivity to α below. At each replication, human–LLM pairs are drawn with replacement from the respondent pool, simulating the sequential survey process on real data. As in Section 5, we report the expected MSE Eq. (10) evaluated at the terminal budget B. All experiments use 500 Monte Carlo replications. 6.2.

Policy Comparison

As in Section 5, we evaluate all policies using the expected MSE

q wq Aq {nq pBq, which

measures allocation quality at the terminal budget using the true Aq values. Table 2 reports

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

this metric across budgets B P t500, 1,000, 1,500, 2,000u, along with each policy’s gap to oracle in parentheses. UCB achieves the lowest MSE among all implementable policies at every budget level. At B “ 1,000, the ordering is UCB (3.9% gap to oracle), ε-greedy (6.2%), uniform (10.6%), and ETC (19.7%). UCB’s gap decreases monotonically with budget, from 5.5% at B “ 500 to 2.1% at B “ 2,000, while uniform’s gap remains stable near 10–12%, reflecting its structural inability to adapt. The ε-greedy policy performs particularly poorly at small budgets (19.8% gap at B “ 500) because its undirected exploration phase consumes most of the budget before exploitation begins; it overtakes uniform only above B “ 1,000. ETC with pilot fraction α “ 0.3 is consistently worse than uniform, because the pilot phase provides only „ 6 samples per question, too few to estimate tAq u reliably. ETC is also sensitive to α: it requires α ě 0.4 to match uniform (see Table EC.2 in the Online Appendix), meaning a substantial share of the budget must be spent on undirected pilot sampling before any informed allocation begins. We interpret the gap to oracle as wasted budget: a policy with a 10% gap produces the same estimation error as the oracle would with only 90% of the budget, effectively wasting the remaining 10%. Under this interpretation, uniform allocation wastes 10–12% of the human-labeling budget at every budget level, whereas UCB wastes only 2–6%. At B “ 2,000, UCB’s waste shrinks to just 2.1%, meaning it operates near the efficiency frontier despite having no prior knowledge of question-level LLM accuracy. To understand where UCB’s gains come from, we group the 68 questions by whether the LLM provides useful signal: 32 “LLM-weak” questions where λ˚q ă 0.05 and 36 “LLMuseful” questions where λ˚q ě 0.05. For LLM-useful questions, the plug-in λ shrinks Aq by absorbing LLM-predictable variance, leaving these questions with low residual difficulty. LLM-weak questions, by contrast, retain high Aq and dominate the total estimation error. The oracle allocation directs 56% of the budget to the LLM-weak group, compared to uniform’s 47% (“ 32{68). UCB learns this imbalance online and shifts budget toward the high-Aq questions that uniform allocation under-serves. 6.3.

Weight and Cost Sensitivity

In practice, questions may differ in importance or sampling cost. We examine sensitivity to these factors by varying the dispersion parameter a P t0, 0.25, 0.5, 0.75, 1.0u for importance

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

Expected MSE (ˆ10´2 ) across budgets on Twin-2K-500 (500 reps). Gap to oracle (%) in parentheses.

Table 2

B Oracle 500 1,000 1,500 2,000

89.1 44.6 29.7 22.3

Notes: Expected MSE “

ε-Greedy

Uniform

94.0 (5.5%) 107.9 (21.1%) 106.7 (19.8%) 46.3 (3.9%) 53.3 (19.7%) 47.3 (6.2%) 30.5 (2.7%) 33.8 (13.9%) 30.9 (4.0%) 22.8 (2.1%) 24.5 (9.9%) 23.1 (3.7%)

99.6 (11.8%) 49.3 (10.6%) 32.7 (10.0%) 24.6 (10.3%)

UCB

q Aq {nq pBq

ETC

measures allocation quality at the terminal budget, using the true Aq

values; same primary metric as in Section 5. Gap to oracle: pMSE ´ MSE˚ q{MSE˚ ˆ 100. ETC uses pilot fraction α “ 0.3. All standard errors ď 0.1 (ˆ10´2 ).

weights (panel a: wq “ 1 ` a ¨ zq , zq „ Uniformp´1, 1q, clipped to r0, 2s, cq “ 1) and sampling costs (panel b: same construction applied to cq , wq “ 1), fixing B “ 1,000. Table 3 shows that UCB maintains a stable gap of approximately 4% regardless of weight or cost dispersion, while uniform allocation degrades sharply (from 10.6% to 27.9% under heterogeneous weights) because it ignores both importance and cost structure. UCB’s Neyman-style index automatically concentrates budget on questions that are both important and hard to rectify. Sensitivity to weight and cost heterogeneity: expected MSE (ˆ10´2 ), B“1,000, 500 reps.

Table 3

(a) Varying weights, cq “ 1 a Oracle 0.00 0.25 0.50 0.75 1.00

44.6 43.8 42.4 40.4 37.1

(b) Varying costs, wq “ 1

ETC ε-Gr.

UCB 46.3 (3.8%) 45.4 (3.7%) 44.1 (4.0%) 42.0 (4.0%) 38.7 (4.3%)

Notes: Expected MSE “

53.3 52.5 51.1 49.1 46.4

47.3 46.6 45.6 44.2 42.4

Unif. 49.3 (10.5%) 48.8 (11.4%) 48.4 (14.2%) 47.9 (18.6%) 47.5 (28.0%)

a Oracle 0.00 0.25 0.50 0.75 1.00

44.6 44.9 44.7 44.0 42.3

q wq Aq {nq ; all standard errors ď 0.1 (ˆ10

UCB 46.3 (3.8%) 46.6 (3.8%) 46.5 (4.0%) 45.7 (3.9%) 44.0 (4.0%) ´2

ETC ε-Gr. 53.3 53.5 53.2 52.3 50.4

47.3 47.7 47.7 47.4 46.9

Unif. 49.3 (10.5%) 49.6 (10.5%) 49.9 (11.6%) 50.1 (13.9%) 50.1 (18.4%)

). Weights (costs) are wq “ 1 ` a ¨ zq with

i.i.d.

zq „ Uniformp´1, 1q, clipped to r0, 2s. The draw tzq u is fixed across a. ETC uses α “ 0.3. Oracle is the Neymanoptimal MSE.

6.4.

Effect of Difficulty Heterogeneity

We rescale the spread of rectification difficulties using a log-space transformation that mirrors the synthetic DGP Eq. (9): log Aphq q “ log A ` h ¨ plog Aq ´ log Aq, where log A “ Q´1 phq

The resulting Aq

q log Aq

(11)

is the mean log-difficulty and h ě 0 controls heterogeneity.

are then renormalized so that Āphq “ Ā, preserving the overall MSE

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

scale. At h “ 0 all difficulties are equal; h “ 1 recovers the original data; h ą 1 amplifies heterogeneity. Table 4 reports the terminal regret (absolute, not percentage) for each policy. When difficulties are homogeneous (h “ 0), uniform allocation is oracle-optimal and both UCB and ε-greedy incur unnecessary exploration cost. As heterogeneity grows, the benefit of adaptive allocation increases sharply: uniform regret rises from near zero to 14.22 (ˆ10´2 ), while UCB regret grows only from 0.95 to 4.12 (4-fold). ETC regret is nearly constant across heterogeneity levels („ 8.7–9.1), because the noisy pilot estimates produce similarly suboptimal commit allocations regardless of the underlying difficulty structure. The comparison with the synthetic heterogeneity experiment (Section 5.2) is instructive: on the real data, the same qualitative pattern holds (UCB’s advantage grows monotonically with heterogeneity), but the absolute magnitudes are smaller, reflecting the more moderate difficulty distribution in real surveys. Table 4

Terminal regret and oracle MSE (ˆ10´2 ) under varying Aq heterogeneity (B“1,000, 500 reps). Mean Aq is held constant at 0.106 across all h. h Oracle 0.00 0.25 0.50 1.00 1.50 2.00

49.1 48.7 47.8 44.6 40.1 35.3

UCB 0.95 (1.9%) 0.95 (2.0%) 1.05 (2.2%) 1.70 (3.8%) 2.85 (7.1%) 4.12 (11.7%)

ETC

Oracle column reports MSE pBq (ˆ10

´2

Uniform

8.71 (17.7%) 1.81 (3.7%) 0.00 (0.0%) 8.75 (18.0%) 1.79 (3.7%) 0.37 (0.8%) 8.76 (18.3%) 1.93 (4.0%) 1.31 (2.7%) 8.77 (19.7%) 2.73 (6.1%) 4.68 (10.5%) 8.90 (22.2%) 4.30 (10.7%) 9.31 (23.2%) 9.12 (25.8%) 6.39 (18.1%) 14.22 (40.3%)

Notes: Regret RpBq “ MSEpBq ´ MSE˚ pBq where MSEpBq “ ˚

ε-Greedy

q Aq {nq pBq. Gap to oracle (%) in parentheses.

). ETC uses α “ 0.3. h “ 0: all Aq equal (uniform is oracle-optimal);

h “ 1: original data. All standard errors ď 0.2 (ˆ10´2 ).

6.5.

Module-Level Allocation

As discussed in Section 2.1, many surveys assign respondents to question modules rather than individual questions. We demonstrate that the UCB algorithm applies directly at this coarser level. We group the 68 questions into Q “ 14 task-type modules (e.g., “Anchoring” with 4 questions, “Probability Matching” with 16 questions). Each budget unit allocates one respondent to a module, and that respondent answers all questions in the module, so ř the module-level difficulty is Aw “ qPw Aq (a sum, not an average, because each respondent contributes one observation to every question in the module). The resulting Aw values range from 0.08 to 2.71, exhibiting substantial heterogeneity.

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

With Q “ 14 modules and budget B “ 200 respondent-module assignments (approximately 14 per module under uniform allocation), UCB achieves a 3.8% gap to oracle, closely matching its 3.9% gap in the question-level experiment (Table 2). Uniform allocation incurs a 29.7% gap, while ETC (9.1%) and ε-greedy (10.6%) fall between. The same algorithm applies without modification because the Aw {nw objective structure is preserved. Together, these experiments confirm that the theoretical advantages of UCB-based adaptive allocation demonstrated on synthetic data carry over to a real survey environment: UCB consistently achieves the smallest regret among all implementable policies, outperforming not only uniform allocation and ε-greedy but also the explore-then-commit approach that operationalizes the natural pilot-study heuristic. UCB adapts to heterogeneous weights and costs, and scales its advantage with the degree of difficulty heterogeneity across questions. Moreover, the framework applies equally well at coarser operational units: when allocation targets are survey modules rather than individual questions, UCB continues to track the oracle closely.

Conclusion

This paper studies a resource allocation problem that arises when generative AI is deployed as a low-cost prediction layer but human verification remains the ground truth: how to allocate scarce human oversight across tasks when AI reliability varies and is unknown before deployment. We develop a UCB-based online algorithm that learns where human effort is most needed while allocating the budget, with formal regret guarantees. Experiments on LLM-augmented surveys confirm that the algorithm substantially outperforms uniform allocation, pilot-study approaches, and standard bandit baselines. The framework extends to module-level allocation and to general M -estimation targets, including regression coefficients and conjoint partworths (Online Appendix A), with a synthetic MNL experiment validating the extension. More broadly, the same principle applies whenever AI generates cheap but unevenly reliable outputs across tasks and humans provide the ground truth. The operational value of generative AI depends not only on model capability but also on how the surrounding human-oversight system is designed. Future directions include batched allocation for panel survey operations, adaptation to model drift, and settings where human feedback triggers model updates or escalation policies.

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

References Agrawal S, Devanur N (2016) Linear contextual bandits with knapsacks. Advances in neural information processing systems 29. Angelopoulos AN, Bates S, Fannjiang C, Jordan MI, Zrnic T (2023a) Prediction-powered inference. Science 382(6671):669–674. Angelopoulos AN, Duchi JC, Zrnic T (2023b) PPI++: Efficient prediction-powered inference. arXiv preprint arXiv:2311.01453 . Argyle LP, Busby EC, Fulda N, Gubler JR, Rytting C, Wingate D (2023) Out of one, many: Using language models to simulate human samples. Political Analysis 31(3):337–351. Auer P, Cesa-Bianchi N, Fischer P (2002) Finite-time analysis of the multiarmed bandit problem. Machine Learning 47(2-3):235–256. Badanidiyuru A, Kleinberg R, Slivkins A (2018) Bandits with knapsacks. Journal of the ACM (JACM) 65(3):1–55. Bhat S, Lyons JB, Shi C, Yang XJ (2025) Effects of learning state dependence of reward weights on trust and team performance in a human-robot sequential decision-making task. 2025 IEEE 5th International Conference on Human-Machine Systems (ICHMS), 35–40 (IEEE). Brand J, Israeli A, Ngwe D (2023) Using LLMs for market research. HBS Working Paper (23-062). Broska D, Howes M, van Loon A (2025) The mixed subjects design: Treating large language models as potentially informative observations. Sociological Methods & Research 54(3):1074–1109. Brucks M, Toubia O (2025) Prompt architecture induces methodological artifacts in large language models. PLOS ONE 20(4):e0319159. Carpentier A, Munos R, Antos A (2015) Adaptive strategy for stratified monte carlo sampling. Journal of Machine Learning Research 16(69):2231–2271. Cohen MC, Miao S, Wang Y (2025) Dynamic pricing with fairness constraints. Operations Research 73(6):3027–3043. Dai T, Swaminathan JM (2025) Artificial intelligence and operations: A foundational framework of emerging research and practice. Production and Operations Management . DiSorbo MD, Ferreira KJ, Balakrishnan M, Tong J (2025) Warnings and endorsements: Improving human-AI collaboration in the presence of outliers. Manufacturing & Service Operations Management 27(6):1814– 1831. Dominguez-Olmedo R, Hardt M, Mendler-Dünner C (2024) Questioning the survey responses of large language models. Advances in Neural Information Processing Systems 37:45850–45878. Fügener A, Walzner DD, Gupta A (2026) Roles of artificial intelligence in collaboration with humans: Automation, augmentation, and the future of work. Management Science 72(1):538–557.

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

Ge H, Bastani H, Bastani O (2023) Rethinking algorithmic fairness for human-AI collaboration. arXiv preprint arXiv:2310.03647 . Huang C, Wu Y, Wang K (2025) How many human survey respondents is a large language model worth? An uncertainty quantification perspective. International Conference on Machine Learning (ICML). Ji W, Lei L, Zrnic T (2025) Predictions as surrogates: Revisiting surrogate outcomes in the age of AI. arXiv preprint arXiv:2501.09731 . Krsteski S, Russo G, Chang S, West R, Gligorić K (2025) Valid survey simulations with limited human data. arXiv preprint arXiv:2510.11408 . Lattimore T, Szepesvári C (2020) Bandit Algorithms (Cambridge University Press). Li G, Liang A, Liu M, Lei M, Jasin S, Yang F, Baxi P (2026) Asymptotically optimal sequential testing with heterogeneous llms. arXiv preprint arXiv:2604.01086 . Li P, Castelo N, Katona Z, Sarvary M (2024) Frontiers: Determining the validity of large language models for automated perceptual analysis. Marketing Science 43(2):254–266. Maurer A, Pontil M (2009) Empirical bernstein bounds and sample variance penalization. Proceedings of the 22nd Annual Conference on Learning Theory (COLT), 115–124. Motoki F, Pinho Neto V, Rodrigues V (2024) More human than human: Measuring ChatGPT political bias. Public Choice 198:3–23. Mozer R (2026) PPI is the difference estimator: Recognizing the survey sampling roots of prediction-powered inference. arXiv preprint arXiv:2603.19160 . Neyman J (1934) On the two different aspects of the representative method. Journal of the Royal Statistical Society 97(4):558–625. Peng T, Gui G, Merlau DJ, Fan GJ, Sliman MB, Brucks M, Johnson EJ, Morwitz V, et al. (2025) A megastudy of digital twins reveals strengths, weaknesses and opportunities for further improvement. arXiv preprint arXiv:2509.19088 . Raghunathan TE, Grizzle JE (1995) A split questionnaire survey design. Journal of the American Statistical Association 90(429):54–63. Simchi-Levi D, Wang C (2025) Multi-armed bandit experimental design: Online decision-making and adaptive inference. Management Science 71(6):4828–4846. Toubia O, Gui GZ, Peng T, Merlau DJ, Li A, Chen H (2025) Database report: Twin-2K-500: A data set for building digital twins of over 2,000 people based on their answers to over 500 questions. Marketing Science 44(6):1446–1455. Toubia O, Simester DI, Hauser JR, Dahan E (2003) Fast polyhedral adaptive conjoint estimation. Marketing Science 22(3):273–303.

Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

Vafa K, Athey S, Blei DM (2025) Estimating wage disparities using foundation models. Proceedings of the National Academy of Sciences 122(22):e2427298122. Wang L, Ye Z, Zhao J (2025) Efficient inference using large language models with limited human data: Fine-tuning then rectification. arXiv preprint arXiv:2511.19486 . Wang M, Zhang DJ, Zhang H (2024) Large language models for market research: A data-augmentation approach. arXiv preprint arXiv:2412.19363 . Ye Z, Yoganarasimhan H, Zheng Y (2025) LOLA: LLM-assisted online learning algorithm for content experiments. Marketing Science 44(5):995–1016. Yin QE, Xin L (2025) Synthetic but not infinite: How much LLM-generated data to use in market research. Available at SSRN 6078686 . Ziems C, Held W, Shaikh O, Chen J, Zhang Z, Yang D (2024) Can large language models transform computational social science? Computational Linguistics 50(1):237–291.

ec1

e-companion to Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

Online Appendix: Adaptive Budget Allocation in LLM-Augmented Surveys Appendix A:

Extension to General M -Estimation

The main text focuses on population means (θq˚ “ ErYq s), but many survey applications target richer estimands such as category choice probabilities, regression coefficients, or conjoint partworths. Here we show that the Aq {nq variance structure, and therefore the entire UCB allocation framework, carries over to any estimand defined through an M -estimation problem, once the multi-dimensional asymptotic covariance is reduced to a scalar difficulty index. We fix a question q and suppress subscripts throughout, writing P, θ ˚ , d, n, etc. A.1.

Setup and examples

Consider a convex, twice-differentiable loss ℓpX, Y ; θq whose population risk has a unique minimizer θ ˚ “ arg minθPRd ErℓpX, Y ; θqs, with score function ψpX, Y ; θq :“ ∇θ ℓpX, Y ; θq satisfying ErψpX, Y ; θ ˚ qs “ 0. Let H :“ Er∇θ ψpX, Y ; θ ˚ qs denote the nonsingular population Hessian. This setup covers four common cases. (i) Mean estimation: d “ 1, ℓ “ 21 pY ´ θq2 , recovering θ˚ “ ErY s. ř (ii) Categorical responses: for Y P t1, . . . , Ku, the loss ℓ “ k 21 p1tY “ku ´ θk q2 yields category probabilities θk˚ “ PrpY “kq. (iii) Linear regression: ℓ “ 12 pY ´ X J θq2 gives θ ˚ “ ErXX J s´1 ErXY s. (iv) Multinomial ř ř J logit: the MNL negative log-likelihood ℓ “ logp k eXk θ q ´ k pXkJ θq1tY “ku yields conjoint partworths. A.2.

PPI++ M -estimator and variance structure

Given an LLM predictor f pXq, define the surrogate score ψ LLM pX; θq :“ ψpX, f pXq; θq. For tuning parameter λ P r0, 1s, the PPI++ M -estimator solves ˜ ¸ n n ÿ 1 1ÿ ψpXi , Yi ; θq ` λ Erψ LLM pX; θqs ´ ψ LLM pXi ; θq , 0“ n i“1 n i“1

(EC.1)

where the expectation is approximated from a large synthetic pool. Because the surrogate terms cancel at θ ˚ , the estimator is consistent for any λ regardless of LLM misspecification. In the synthetic-data-rich regime, linearizing Eq. (EC.1) around θ ˚ yields

p ´ θ˚ q Ñ npθpλq Ý N p0, Σpλqq,

where the sandwich covariance is Σpλq “ H ´1 V ∆pλq H ´J ,

` ˘ V ∆pλq :“ Var ψpX, Y ; θ ˚ q ´ λ ψ LLM pX; θ ˚ q .

p As in the scalar case, Varpθpλqq « Σpλq{n: the labeled sample size n enters only through a 1{n prefactor. A.3.

Scalar difficulty index for allocation

The allocation framework requires a scalar difficulty per question. Two standard design criteria reduce Σpλq to a scalar while preserving the 1{n structure. The A-optimal (trace) criterion defines ApAq pλq :“ trpΩ Σpλqq for a weight matrix Ω “ LJ L ľ 0 reflecting which linear functions of θ matter most. The Doptimal (determinant) criterion defines ApDq pλq :“ detpΣpλqq1{d , which is reparameterization-invariant. Under either criterion, the per-question objective takes the form Apλq{n, so the UCB allocation algorithm and its regret guarantee apply directly after replacing the scalar rectification difficulty with the chosen scalarization.

ec2 A.4.

e-companion to Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

Numerical illustration: MNL partworth estimation

We verify the above framework with a synthetic multinomial logit (MNL) experiment. Consider Q “ 50 choice tasks, each with K “ 3 alternatives and d “ 2-dimensional partworths. For each task q, alternatives have features Xq P RKˆd constructed from a rotated balanced design scaled by a per-question factor sq , where tsq u are drawn from the same log-uniform distribution as in Eq. (9) with h “ 1.0. True partworths βq˚ are unit-norm random directions, and LLM partworths are generated as βqLLM “ ρ βq˚ ` εq with ρ “ 0.7 and εq „ N p0, 0.32 Id q. Human and LLM choices are sampled from MNLpXq , βq˚ q and MNLpXq , βqLLM q, respectively. For each task, we compute the scalar difficulty Aq “ trpHq´1 Vq∆ Hq´J q via Monte Carlo with 50,000 samples, where Hq is the MNL Hessian and Vq∆ is the score residual covariance. The resulting Aq values range from 4.8 to 39.7 (coefficient of variation 0.72), reflecting substantial heterogeneity driven by the feature scaling. We then run the allocation experiment with budget B “ 2,000, initialization K0 “ 3, and 200 replications.

Table EC.1

MNL partworth estimation: expected MSE at B“2,000 (Q“50, K“3, d“2, 200 reps). Gap to oracle (%) in parentheses. Policy

MSE

Oracle 15.74 UCB 16.06 ETC 16.44 Uniform 17.79

Gap (%) — 2.0 4.5 13.1

Notes: Aq “ trpHq´1 Vq∆ Hq´J q computed via Monte Carlo. ETC uses pilot fraction α “ 0.3. All standard errors ď 0.02.

Table EC.1 confirms that the UCB allocation framework extends to vector-valued M -estimation targets. UCB achieves a 2.0% gap to oracle, comparable to the mean-estimation results in Sections 5–6, while uniform allocation wastes 13.1% of its budget. The allocation mechanism depends only on the scalar difficulties tAq u, so the UCB algorithm applies without modification once Aq is computed from the sandwich covariance.

Appendix B: B.1.

Proof of Theorem 1

Step I: Define the Good Event and Bound its Probability

To control regret, we first define a high-probability good event under which the true rectification difficulty Aq “ VarpỸq q is uniformly close to its empirical estimate. rq,s be the unbiased sample variance of the first s i.i.d. residuals For each q and sample size s ě 2, let A tỸq,i usi“1 , rq,s “ A

s ˘2 1 ÿ` Ỹq,i ´ Ỹ q,s . s ´ 1 i“1

At adaptive time t, the algorithm has collected nq,t samples for question q, and its running sample variance pq,t “ A rq,n . satisfies A q,t

ec3

e-companion to Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

Set δq,s :“ δ{pQTmax q and define the good event as the intersection of two-sided concentration events of sample variance for all questions and per-arm sample sizes: #ˇ + c ˇ b Q Tč max č ˇ ˇa 2 lnp2{δq,s q r ˇ ˇ E :“ . ˇ Aq ´ Aq,s ˇ ď R s´1 q“1 s“K

(EC.2)

Note that the intersection is over deterministic indices pq, sq, which avoids any optional-stopping complications that would arise from indexing by adaptive time. Lemma EC.1. Under Assumption 1, PpEq ě 1 ´ δ. Proof of Lemma 1.

We prove this using an empirical Bernstein-style concentration bound for the sample

variance. First, define the normalized variables: Zq,i :“

Ỹq,i ´ L P r0, 1s, R

implying

VarpỸq q “ R2 VarpZq q.

For each fixed sample size s ě K ě 2, let vrq,s be the unbiased sample variance of tZq,i usi“1 . Because s is deterministic, the concentration inequality for the square root of sample variance Maurer and Pontil (2009) applies directly: for any fixed pq, sq, ¸ ˜ c b a 2 lnp2{δq,s q ď δq,s . P | VarpZq q ´ vrq,s | ą s´1 Rescaling back to the original Ỹ scale by multiplying by R (where we obtain:

b a rq,s | ą R P | Aq ´ A

b a a a rq,s “ R vrq,s ), Aq “ R VarpZq q and A

2 lnp2{δq,s q s´1

¸ ď δq,s .

Applying a union bound over all questions q P t1, . . . , Qu and all sample sizes s P tK, . . . , Tmax u: PpE c q ď

Q Tÿ max ÿ q“1 s“K

δq,s ď

Q ÿ q“1

Tmax ¨

δ “ δ. QTmax

Thus, PpEq ě 1 ´ δ. At any adaptive time t, the algorithm has nq,t “ s samples for question q and its sample pq,t “ A rq,n , so E covers all pq, tq pairs encountered during execution. ˝ variance satisfies A q,t b a pq,t | ď ϵ Implications for Optimism. On the good event E, for every q and t, the condition | Aq ´ A b a pq,t ` ϵ. Squaring both sides, we define the variance-UCB as: implies Aq ď A d ˜b ¸2 2 lnp2{δq,t q UCB p Aq,t :“ Aq,t ` R nq,t ´ 1 d 2 p pq,t ` 2R 2Aq,t lnp2{δq,t q ` 2R lnp2{δq,t q . “A nq,t ´ 1 nq,t ´ 1 ˚ Consequently, on E, the true marginal-efficiency index Iq,t is upper-bounded by the optimistic index: ˚ Iq,t “

wq AUCB w q Aq q,t UCB ď I :“ . q,t cq n2q,t cq n2q,t

This optimism property is the key output of Step I and will be used in the subsequent regret analysis. b b a pq,t ď Aq ` R 2 lnp2{δq,t q , hence Moreover, on E we have A nq,t ´1 d d b b a 2 lnp2{δ q 2 lnp2{δq,t q q,t pq,t ` R AUCB “ A ď Aq ` 2R . q,t nq,t ´ 1 nq,t ´ 1

ec4 B.2.

e-companion to Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

Step II: Bounding the Allocation Gap |nq,B ´ n˚q |

In this step, we show that on the good event E, the sequential allocation nq,B concentrates around the optimal řQ a allocation n˚q . We define Λ “ j“1 wj Aj cj and recall n˚q “ Bβq , where the target allocation ratio is: a wq Aq {cq βq “ . Λ ř ? ř ř wj Aj cj Note that j cj βj “ j Λ “ 1. Let Bucb “ B ´ j cj K denote the budget remaining for the UCB selection phase after initialization. ř Since B ą q cq K, there is a remaining resource budget after the initialization phase. Let RemB P r0, cmax q be the leftover budget when the algorithm stops. Then Q ÿ

cj pnj,B ´ Kq “ Bucb ´ RemB ě Bucb ´ cmax .

j“1

By the pigeonhole principle, there exists an arm q such that cq pnq,B ´ Kq ě cq βq pBucb ´ RemB q ě cq βq pBucb ´ cmax q. Let qa be such a question. This implies cqa pnqa ,B ´ Kq ě cqa βqa pBucb ´ cmax q ą 0 and nqa ,B ´ 1 ě βqa pBucb ´ cmax q ` K ´ 1. Let t be the time step when qa is pulled for the last time, meaning nqa ,t “ nqa ,B ´ 1 ě K and nqa ,t`1 “ nqa ,B . UCB . On event E, the true variance is ě Iq,t Since qa is selected at time t, for any question q, we have IqUCB a ,t

bounded by the UCB and the UCB selection rule: Since nq,t ď nq,B , on E for any q, we have the chain wq Aq wq Aq ˚ UCB ď “ Iq,t ď Iq,t , cq n2q,B cq n2q,t where the last inequality uses optimism on E (i.e., Aq ď AUCB q,t ). Therefore, d ˜ ¸2 a wqa wq Aq 2 lnp2{δqa ,t q UCB UCB ď Iq,t ď Iqa ,t ď . Aqa ` 2R cq n2q,B cqa pnqa ,B ´ 1q2 nqa ,B ´ 2 Taking the square root and multiplying by nq,B : d ˜ ¸ a a wq Aq {cq wqa {cqa a 2 lnp2{δqa ,t q ď Aqa ` 2R . nq,B nqa ,B ´ 1 nqa ,B ´ 2 a Distributing the wqa {cqa term: a a a a wq Aq {cq wqa Aqa {cqa 2R wqa {cqa 2 lnp2{δqa ,t q a ď ` . nq,B nqa ,B ´ 1 pnqa ,B ´ 1q nqa ,B ´ 2 looooooomooooooon looooooooooooooooomooooooooooooooooon Leading Term

Fluctuation Term

Since K ě 2 implies nqa ,B ě K `1 ě 3, we have nqa ,B ´2 ě nqa ,B ´1´1, so both nqa ,B ´1 ě βqa pBucb ´cmax q and nqa ,B ´ 2 ě βqa pBucb ´ cmax q hold (the latter because the pigeonhole bound ? already gives nqa ,B ´ K ě βqa pBucb ´ cmax q and K ě 2). Substituting these and using the identity βqa “ term :

wqa Aqa {cqa

a a wqa Aqa {cqa wqa Aqa {cqa Λ a “ “ βqa pBucb ´ cmax q p wqa Aqa {cqa {ΛqpBucb ´ cmax q Bucb ´ cmax

: For the leading

ec5

e-companion to Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

? a 2RΛ 2 lnp2{δq,t q β Λ wqa {cqa “ ?qAa , the second term becomes ?A β pB ´c q3{2 .

For the Fluctuation Term, Using

ucb

max

Combining these, we obtain: a a wq Aq {cq 2RΛ 2 lnp2{δq,t q Λ . ď `a nq,B Bucb ´ cmax Aqa βqa pBucb ´ cmax q3{2 ´cmax and rearranging for nq,B : Multiplying by Bucb Λ a 2R 2 lnp2{δq,t q pBucb ´ cmax qβq ùñ nq,B ě ď1` a nq,B Aqa βqa pBucb ´ cmax q

pBucb ´ cmax qβq ? 2R 2 lnp2{δq,t q 1` ?

Aqa βqa pBucb ´cmax q

řQ Using the inequality 1{p1 ` xq ě 1 ´ x as x ě 0, substituting Bucb ´ cmax “ B ´ j“1 cj K ´ cmax , and noting ? ? Bucb ´ cmax ď B: ˜Q ¸ a ÿ 2Rβq 2B lnp2{δq,t q a nq,B ě Bβq ´ βq . cj K ` cmax ´ Aqa βqa j“1 Since n˚q “ Bβq , we identify ∆q,B (scaling away Aqa via βmin :“ minq βq and Amin ): ˜Q ¸ a ÿ 2R 2B lnp2{δq,t q ? ∆q,B “ βq cj K ` cmax ` . Amin βmin j“1 we have nq,B ě n˚q ´ ∆q,B . Similarly, to upper bound nq,B ´ n˚q , we use the budget constraint cq nq,B ď B ´

cj nj,B ď B ´

j‰q

řQ j“1

cj nj,B ď B:

cj pn˚j ´ ∆j,B q “ cq n˚q `

j‰q

cj ∆j,B .

j‰q

Thus, nq,B ´ n˚q ď

ÿ cj j‰q

∆j,B

Combining the lower bound nq,B ´ n˚q ě ´∆q,B with the above upper bound yields ¸ ˜ ÿ cj ˚ ∆j,B , |nq,B ´ nq | ď max ∆q,B , c j‰q q a which is Op B lnp1{δqq. B.3.

(EC.3)

Step III: Convert the Allocation Gaps into Regret Bound

To bound the regret RpBq, we convert the allocation gaps in Step II into the objective deviation using the Taylor expansion of fq pnq “

wq Aq n

. By Taylor’s theorem, there exists ξq between nq,B and n˚q such that:

fq pnq,B q ´ fq pn˚q q “ ´

w q Aq wq Aq pnq,B ´ n˚q q ` 3 pnq,B ´ n˚q q2 . pn˚q q2 ξq

(EC.4)

Summing over q P T , the total variance gap is: Q ÿ w q Aq w q Aq ´ ˚ 2 pnq,B ´ n˚q q ` pnq,B ´ n˚q q2 . pn q ξq3 q q“1 q“1 looooooooooooomooooooooooooon looooooooooooomooooooooooooon Q ÿ

Term 1

Term 2

(EC.5)

ec6

e-companion to Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

w A

Analysis of Term 1: By the optimality condition pnq˚ qq2 “ λpBqcq , where λpBq “

ř p j

wj Aj cj q2 B2

Term 1 “ ´λpBq

Q ÿ q“1

˚ q

cq pnq,B ´ n q “ λpBqpB ´

Q ÿ

cq nq,B q.

, we have: (EC.6)

q“1

Since the algorithm terminates only when the remaining budget is less than cmax “ maxq cq , recall that ř RemB “ B ´ cq nq,B P r0, cmax q. Thus: ř a p j wj Aj cj q2 cmax . (EC.7) Term 1 ď B2 ? Since |nq,B ´ n˚q | ď Op Bq, there exists a budget threshold B0 that ensures that for all B ě B0 , |nq,B ´ n˚q | ď 1 Bβq . 2

Analysis of Term 2: For all B ě B0 , the condition ξq ě 12 n˚q holds almost surely on the good event E. For B ě B0 , by the conclusion in step II, Term 2 from the Taylor expansion is bounded by: ¸2 ˜ a Q Q ÿ 8wq Aq C1 ÿ wq Aq 2 2R 2B lnp2{δq,B q ˚ 2 ? Term 2 ď . pnq,B ´ nq q ď 3 β pBβq q3 B q“1 βq3 q Amin βmin q“1

(EC.8)

Final Regret Bound: With δ “ B ´2 , in Lemma 1, PpE c q ď B ´2 . On E c , the gap is bounded by Vmax “ ř wq Aq K

. Combining all components: the total expected regret RpBq is: « ˜Q ¸ Q ff ÿ w q Aq 1 C1 R2 lnp2QTmax B 2 q ÿ wq Aq 2 RpBq ď 2 Λ cmax ` ` . B Amin βmin βq K q“1 q“1

Where Λ “

řQ a j“1

Appendix C:

wj Aj cj and βq “

a wq Aq {cq {Λ. This bound holds for all B ě B0 .

Proof of Theorem 2

The proof structure is identical to that of Theorem 1: only Step I (the good-event construction) changes to account for the additional estimation error from the plug-in λ̂q,t . Steps II–III carry over verbatim with Aq replaced by Aq pλ˚q q. C.1.

Step I for PPI++: Define the Good Event and Bound its Probability

Recall YqLLM :“ YqLLM “ f pXq q and the tuned residual Ỹq pλq :“ Yq ´ λYqLLM . Let ˙ ˆ CovpYq , YqLLM q . Aq pλ˚q q :“ VarpỸq pλ˚q qq, λ˚q :“ Πr0,1s VarpYqLLM q At time t, the algorithm forms the plug-in estimator ˜ ¸ y t pYq , Y LLM q ` ˘ Cov q pq,t pλ̂q,t q :“ Var y t Yq ´ λ̂q,t Y LLM , λ̂q,t :“ Πr0,1s , A q LLM y Vart pY q q

y t p¨q and Cov y t p¨q denote the unbiased sample variance and covariance based on the nq,t paired where Var samples collected for question q up to time t. As in the PPI case, we distinguish notationally between fixedsample-size statistics (indexed by s) and adaptive-time statistics (indexed by t): we write λ̃q,s and σ̃q,s pλq for the plug-in tuning parameter and sample standard deviation computed from the first s i.i.d. pairs of pq,t for the same quantities evaluated at adaptive time t (with nq,t pairs). The question q, and reserve λ̂q,t and A

e-companion to Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

ec7

pq,t pλ̂q,t q “ A rq,n pλ̃q,n q. Set Tmax :“ tB{cmin u and δq,s :“ δ{pQTmax q. two are related by λ̂q,t “ λ̃q,nq,t and A q,t q,t Define the radius d ρ

`` q,s

:“ R

` ˘ ? ` ˘ 2 ln 4pTmax ` 1q{δq,s 2 RY LLM RY LLM ` ` ∆λ s, δq,s {2 , s´1 Tmax 2

(EC.9)

where ∆λ p¨, ¨q will be specified in Eq. (EC.10). We define the PPI++ good event as ˇ * "ˇb b Q Tč max č ˇ ˇ rq,s pλ̃q,s qˇ ď ρ`` . ˇ Aq pλ˚q q ´ A E `` :“ q,s ˇ ˇ q“1 s“K

Lemma EC.2. Under Assumptions 3 and 4, if K ě K0 rlnpQTmax {δqs where K0 depends only on the parameters in Assumptions 3–4, then PpE `` q ě 1 ´ δ. The explicit choice of K0 is given in Section C.1.2 below. This logarithmic initialization is required for the concentration of λ̃ for theoretical purposes and does not affect the Opln B{B 2 q regret rate. In Step II, ? ř ř the allocation gap is ∆q,B “ βq p j cj K ` cmax ` Op B ln Bqq; the term j cj K “ OpQ ln Bq is dominated ? ? by Op B ln Bq, so ∆q,B “ Op B ln Bq as before. In Step III, the bad-event contribution δ ¨ Vmax pλ˚ q “ δ ¨ Op1{ ln Bq “ Op1{pB 2 ln Bqq under δ “ B ´2 is dominated by the Opln B{B 2 q main term. The proof of Lemma EC.2 combines two auxiliary results whose detailed proofs are deferred to the next subsubsection. First, Lemma EC.3 establishes the concentration of the plug-in tuning parameter λ̃q,s around its population counterpart λ˚q , yielding the explicit deviation bound ∆λ . Second, Lemma EC.4 provides a uniform concentration inequality for the standard deviation function σ̃q,s pλq over all λ P r0, 1s, which accounts for both the grid-discretization error and the within-grid-point sampling error. Combining these two lemmas with a triangle inequality and a union bound over all pq, sq pairs gives PpE `` q ě 1 ´ δ, which is presented in Section C.1.2. C.1.1.

Auxiliary Lemmas

Lemma EC.3 (Concentration of plug-in λ̃). Under Assumptions 3 and 4, fix q and let s ě 2 i.i.d. a pairs tpYi , YiLLM qusi“1 . For δ P p0, 1q define gs pδq :“ lnp8{δq{p2sq and ´ ¯ ∆a ps, δq :“ 2MY MY LLM ` MY LLM RY ` MY RY LLM gs pδq ` RY RY LLM gs pδq2 , ¯ ´ ∆b ps, δq :“ MY2 LLM ` 2MY LLM RY LLM gs pδq ` RY2 LLM gs pδq2 . LLM If ∆b ps, δq ď Vmin {2, then with probability at least 1 ´ δ,

|λ̃ ´ λ˚ | ď ∆λ ps, δq :“

2 4MY MY LLM ∆a ps, δq ` ∆b ps, δq, LLM LLM 2 Vmin pVmin q

(EC.10)

where λ̃ “ Πr0,1s pã{b̃q and λ˚ “ Πr0,1s pa{bq. Proof of Lemma EC.3.

Let a :“ CovpY, Y LLM q, b :“ VarpY LLM q, and let ã, b̃ be their sample counterparts,

so that λ˚ “ Πr0,1s pa{bq and λ̃ “ Πr0,1s pã{b̃q. Let µY :“ ErY s and µY LLM :“ ErY LLM s. Define the event Emom that the following four inequalities hold simultaneously: |Ȳ ´ µY | ď RY gs pδq,

|Ȳ LLM ´ µY LLM | ď RY LLM gs pδq,

ec8

e-companion to Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

|Y ¨ Y LLM ´ ErY ¨ Y LLM s| ď 2MY MY LLM gs pδq,

|pY LLM q2 ´ ErpY LLM q2 s| ď MY2 LLM gs pδq.

Each bound follows from Hoeffding’s inequality applied to the corresponding bounded variable (Y P rLY , UY s, Y LLM P rLY LLM , UY LLM s, Y ¨ Y LLM P r´MY MY LLM , MY MY LLM s, pY LLM q2 P r0, MY2 LLM s), with failure probability at most δ{4; thus by a union bound, PpEmom q ě 1 ´ δ. On Emom we bound |ã ´ a| and |b̃ ´ b|. First, ˇ ˇ |ã´a| “ ˇpY ¨ Y LLM ´ErY ¨Y LLM sq´pȲ Ȳ LLM ´µY µY LLM qˇ ď |Y ¨ Y LLM ´ErY ¨Y LLM s|`|Ȳ Ȳ LLM ´µY µY LLM |. Moreover, Ȳ Ȳ LLM ´ µY µY LLM “ pȲ ´ µY qpȲ LLM ´ µY LLM q ` pȲ ´ µY qµY LLM ` pȲ LLM ´ µY LLM qµY , so using |µY | ď MY , |µY LLM | ď MY LLM and the moment bounds in Emom , |Ȳ Ȳ LLM ´ µY µY LLM | ď pRY gs pδqqpRY LLM gs pδqq ` MY LLM pRY gs pδqq ` MY pRY LLM gs pδqq. Combining with |Y ¨ Y LLM ´ ErY ¨ Y LLM s| ď 2MY MY LLM gs pδq yields ´ ¯ |ã ´ a| ď 2MY MY LLM ` MY LLM RY ` MY RY LLM gs pδq ` RY RY LLM gs pδq2 “ ∆a ps, δq. Second, ˇ ˇ |b̃ ´ b| “ ˇppY LLM q2 ´ ErpY LLM q2 sq ´ pȲ LLM 2 ´ µ2Y LLM qˇ ď |pY LLM q2 ´ ErpY LLM q2 s| ` |Ȳ LLM 2 ´ µ2Y LLM |. Since |Ȳ LLM 2 ´ µ2Y LLM | “ |Ȳ LLM ´ µY LLM | |Ȳ LLM ` µY LLM | ď pRY LLM gs pδqqp2MY LLM ` RY LLM gs pδqq on Emom , we get |b̃ ´ b| ď MY2 LLM gs pδq ` 2MY LLM RY LLM gs pδq ` RY2 LLM gs pδq2 “ ∆b ps, δq. LLM LLM LLM {2. {2, hence b̃ ě b ´ |b̃ ´ b| ě Vmin {2, we have |b̃ ´ b| ď Vmin Under the lemma’s condition ∆b ps, δq ď Vmin

Now write

ˇ ˇ ˇ ˇ ˇ ã a ˇ ˇˇ ãb ´ ab̃ ˇˇ |ã ´ a| b ` |a| |b̃ ´ b| ˇ ´ ˇ“ˇ . ˇ b̃ b ˇ ˇ bb̃ ˇˇ ď bb̃

LLM 2 LLM LLM q {2, and thus {2, we have bb̃ ě pVmin and b̃ ě Vmin Using b ě Vmin ˇ ˇ ˇ ã a ˇ ˇ ´ ˇ ď 2 |ã ´ a| ` 2|a| |b̃ ´ b|. ˇ b̃ b ˇ V LLM pV LLM q2 min

min

Finally, |a| “ |CovpY, Y LLM q| ď E|Y ¨ Y LLM | ` |µY µY LLM | ď 2MY MY LLM , hence ˇ ˇ ˇ ã a ˇ ˇ ´ ˇ ď 2 |ã ´ a| ` 4MY MY LLM |b̃ ´ b|. ˇ b̃ b ˇ V LLM pV LLM q2 min

min

ˇ ˇ Because Πr0,1s is 1-Lipschitz (nonexpansive), |Πr0,1s pxq ´ Πr0,1s pyq| ď |x ´ y|, we obtain |λ̃ ´ λ˚ | ď ˇ ãb̃ ´ ab ˇ. Plugging in the bounds on |ã ´ a| and |b̃ ´ b| proves this lemma.

Lemma EC.4 (Uniform concentration). Under Assumption 3, fix q and a sample size s ě 2. Define b b Ą s pYq ´ λY LLM q, σq pλq :“ VarpYq ´ λYqLLM q, σ̃q,s pλq :“ Var q Ą s is computed from the first s i.i.d. pairs for question q. Let N :“ Tmax ` 1 and ΛT where Var :“ max t0, 1{Tmax , . . . , 1u. Then for any δ P p0, 1q, with probability at least 1 ´ δ, d ` ˘ ? 2 ln 2N {δ 2 RY LLM sup |σq pλq ´ σ̃q,s pλq| ď R ` . s ´ 1 Tmax λPr0,1s

(EC.11)

ec9

e-companion to Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

Proof of Lemma EC.4.

For each fixed λ P ΛTmax , the random variable Yq ´ λYqLLM has range at most R.

Applying the square-root variance concentration inequality of Maurer and Pontil (2009) to the first s i.i.d. pairs with confidence level δ{N gives ˜

P |σq pλq ´ σ̃q,s pλq| ą R

2 lnp2N {δq s´1

¸ ď

δ . N

Union bounding over λ P ΛTmax yields, with probability at least 1 ´ δ, c 2 lnp2N {δq sup |σq pλq ´ σ̃q,s pλq| ď R . s´1 λPΛTmax

(EC.12)

For any λ, λ1 P r0, 1s, |σq pλq ´ σq pλ1 q| ď

b b RY LLM Varppλ ´ λ1 qYqLLM q “ |λ ´ λ1 | VarpYqLLM q ď |λ ´ λ1 | , 2

and similarly, for the sample standard deviation, b b b pq,s pλq ´ A pq,s pλ1 q| ď |λ ´ λ1 | Var Ą s pY LLM q ď |λ ´ λ1 | RY?LLM . |σ̃q,s pλq ´ σ̃q,s pλ1 q| “ | A q 2 Now for any λ P r0, 1s, choose λ˝ P ΛTmax such that |λ ´ λ˝ | ď 1{Tmax . Then on the event Eq. (EC.12), |σq pλq ´ σ̃q,s pλq| ď |σq pλq ´ σq pλ˝ q| ` |σq pλ˝ q ´ σ̃q,s pλ˝ q| ` |σ̃q,s pλ˝ q ´ σ̃q,s pλq| c ˆ ˙ 2 lnp2N {δq RY LLM RY LLM 1 ` ` ? . ďR s´1 2 Tmax 2 ? Since 12 ` ?12 ď 2, we obtain Eq. (EC.11) with probability at least 1 ´ δ. ˝ C.1.2.

Proof of Lemma EC.2.

We first verify that the choice of K ensures the precondition ∆b ps, δq,s {2q ď

LLM Vmin {2 of Lemma EC.3 for all pq, sq. Since ∆b ps, δq,s {2q is decreasing in s and δq,s does not depend on s,

only the binding case s “ K needs to be checked. With δq,s “ δ{pQTmax q, we have c lnp16QTmax {δq . gK pδq,K {2q “ 2K Since lnp16QTmax {δq ď 4 lnpQTmax {δq for QTmax {δ ě e2 and K ě K0 lnpQTmax {δq, this gives gK ď

a 2{K0 .

Substituting into the definition of ∆b and using gK ď 1 (which holds for K0 ě 2): a ˘ ` 2 ď 2pMY LLM ` RY LLM q2 2{K0 . ∆b pK, δq,K {2q ď MY2 LLM ` 2MY LLM RY LLM gK ` RY2 LLM gK LLM 2 LLM q s ensures ∆b pK, δq,K {2q ď Vmin {2, and monotonicity extends Setting K0 :“ r32pMY LLM ` RY LLM q4 {pVmin

this to all s ě K. Fix pq, sq with s P tK, . . . , Tmax u. Write σq pλq :“

b b VarpYq ´ λYqLLM q. Note that Aq pλ˚q q “ σq pλ˚q q and

b rq,s pλ̃q,s q “ σ̃q,s pλ̃q,s q. A By Lemma EC.3 with confidence δq,s {2, with probability at least 1 ´ δq,s {2, ` ˘ |λ̃q,s ´ λ˚q | ď ∆λ s, δq,s {2 . By Lemma EC.4 with confidence δq,s {2, with probability at least 1 ´ δq,s {2, d ` ˘ ? ˇ ˇ 2 ln 4pTmax ` 1q{δq,s 2 RY LLM ˇ ˇ ` . ˇσq pλ̃q,s q ´ σ̃q,s pλ̃q,s qˇ ď R s´1 Tmax

(EC.13)

(EC.14)

ec10

e-companion to Ye, Lyu, and Tao: Adaptive Budget Allocation in LLM-Augmented Surveys

On the intersection of Eq. (EC.13) and Eq. (EC.14), we bound the target deviation by the triangle inequality: ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇσq pλ˚q q ´ σ̃q,s pλ̃q,s qˇ ď ˇσq pλ˚q q ´ σq pλ̃q,s qˇ ` ˇσq pλ̃q,s q ´ σ̃q,s pλ̃q,s qˇ . For the first term, note by Popoviciu’s inequality that b RY LLM . VarpYqLLM q ď 2 Therefore, b ˇ b ˇ ` ˘ RY LLM ˚ ˇ ˇ |λq ´ λ̃q,s |. ˇσq pλ˚q q ´ σq pλ̃q,s qˇ ď Var pλ˚q ´ λ̃q,s qYqLLM “ |λ˚q ´ λ̃q,s | VarpYqLLM q ď 2 Combining with Eq. (EC.13) and Eq. (EC.14) yields ˇb ˇ ˇ b ˇ ˇ ˇ rq,s pλ̃q,s qˇ “ ˇˇσq pλ˚ q ´ σ̃q,s pλ̃q,s qˇˇ ď ρ`` , ˇ Aq pλ˚q q ´ A q q,s ˇ ˇ with failure probability at most δq,s for this fixed pq, sq. Finally, a union bound over all pq, sq P rQs ˆ tK, . . . , Tmax u gives Q Tÿ max ` ˘ ÿ P pE `` qc ď δq,s ď δ, q“1 s“K

hence PpE `` q ě 1 ´ δ. At any adaptive time t with nq,t “ s, the algorithm’s statistics satisfy λ̂q,t “ λ̃q,nq,t pq,t pλ̂q,t q “ A rq,n pλ̃q,n q, so E `` covers all pq, tq encountered during execution. ˝ and A q,t

Appendix D: Table EC.2

q,t

ETC Pilot Fraction Sensitivity

ETC sensitivity to pilot fraction α on Twin-2K-500 (B“1,000, 500 reps). UCB and Uniform shown as reference. Policy Oracle UCB ETC (α “ 0.1) ETC (α “ 0.2) ETC (α “ 0.3) ETC (α “ 0.4) ETC (α “ 0.5) Uniform

MSE (ˆ10´2 ) Gap (%) 44.6 46.3 74.4 60.2 53.3 49.5 47.4 49.3

— 3.9 66.9 35.2 19.7 11.1 6.4 10.6

Notes: α is the fraction of the post-initialization budget allocated to uniform pilot sampling before committing to the Neyman rule. ETC requires α ě 0.4 to match uniform and α ě 0.5 to approach ε-greedy (6.2% gap, not shown).

Record · ID 13117 · SHA-256 291567035994d3a3
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.