acceptodds
Under review as a conference paper at ICLR 2027

One Reference Bit and the Statistical Cost of Paired-Only Audits

Abstract

Paired audits may retain only whether two responses differ, discarding the responses themselves. We quantify the statistical cost of this record constraint in a two-hypothesis binary response model. Each acquired response costs one query and is independently flipped with probability ; comparisons are exact XORs of already acquired responses, not additional measurements. Under a common raw-response budget, we optimize the sampling allocation, pairing graph, and causal adaptive policy. For fixed designs, we derive the exact finite-budget minimax risk and show that the optimal error exponent is half the raw-record exponent. For causal policies whose actions depend only on released differences, we prove that an anytime, noise-rate-free rule—sample the less certain latent bit—is minimax optimal at every horizon. Its exponent is strictly between the fixed-design and raw-record exponents. Retaining one already acquired noisy reference response instead orients any connected difference record, reconstructs all raw responses, and attains the raw-record exponent without another query. Thus adaptivity recovers part, but not all, of the information lost by paired-only storage. The retained bit is an observed noisy response, not a true label or an oracle.

Primary area:
learning theory
Keywords:
statistical learning theory, adaptive hypothesis testing, controlled sensing, minimax risk, error exponents, paired-only observations, information retention

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_dRxUOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper asks how much statistical power is lost when an audit records only whether two responses differ rather than the responses themselves. In a binary two-hypothesis model (each raw response costs one acquisition and is flipped independently with known rate η; pairwise comparisons are noiseless XORs of already-acquired bits), the authors optimize three experiments under a common budget of N acquisitions: (i) fixed designs (allocation + pairing graph), (ii) causal adaptive designs whose actions use only released differences, and (iii) "retained-reference" designs that keep one already-acquired raw response.

Critical strengths

1.The problem is completely solved, not merely bounded.​ Theorem 2 gives an exact finite-N minimax risk and the exact optimal allocation (including the counter-intuitive "balanced is sometimes strictly worse" effect), and Theorem 3 gives an all-horizon optimal policy rather than an asymptotically optimal one. This level of closure is rare and valuable. 2.A genuinely implementable optimum.​ Two O(log N)-bit signed counters, one magnitude comparison per acquisition, needing neither η nor the horizon. The clean separation between what the acquisition interface may hold internally (the anchor) and what the auditor receives (differences only) makes it usable in a real logging pipeline. 3.The three-way strict separation is the real contribution, and the authors correctly frame it that way rather than as "information loss can hurt."

Critical weaknesses
  1. The motivating application is asserted, never connected.​ The paper opens with LLM vulnerability evaluation (LLM4Vuln, semantic transformations), but nothing in the model derives from, is validated on, or is calibrated against such an evaluation. There is no measurement of how common paired-only logging is, no instance of a real harness discarding raw responses, and no empirical section.

  2. State the novelty delta more sharply.​ Since the exponent is known, the contribution is: the exact finite-budget fixed-design optimum and β/2; the all-horizon optimality proof under the parity loss; and the three-way comparison. A reader must currently reconstruct this from scattered remarks. Add an explicit "what is new" paragraph/table vs. Nitinawarat et al. and Burnashev (their fixed-design exponent 2β/3 vs. your β/2; different terminal loss; different experiment triples).

Questions for authors

1.Is "at least one control" an assumption or forced by identifiability? With all-informative queries the two orbit laws coincide (risk 1/2), so I believe it is forced — if so, say so; it makes the premise far less arbitrary. 2.What if the retained reference is chosen after acquisition, or more than one raw bit is retained? 3.Under unknown/misspecified η, what is the risk of the η-free greedy policy? A robustness bound would turn a nice property into a strong one.

2 comments
AuthorsOpenReview ↗

Motivation, controls, reference retention, and noise uncertainty

Thank you for your assessment and questions. We have put the novelty comparison in Table 4 (p. 10), clarified controls in Section 2, and added exact budgets in Table 3.

Motivation and contribution. The vulnerability-evaluation example explains how the two query signatures might arise. You are right that the submission provides no deployment evidence for paired-only logging. The opening now starts from the recording question. The finite program construction in Appendix D realizes the specified signatures; Table 3 quantifies the resulting statistical cost.

The comparison states the contributions you identified: the exact fixed-design risk and allocation, the all-horizon policy for parity loss, and the common-cost reference comparison. We credit Nitinawarat et al. and Burnashev for the shared adaptive exponent. Table 4 compares their three-state examples, with fixed rate 2β/32\beta/3 and location/message loss, to our β/2\beta/2 and parity loss. Soloviev and Halpern's noisy Boolean-testing framework contains our latent XOR experiment; Appendix E.3 gives its prior, budget and reward mapping. Our results solve this instance and compare the resulting risks with reference retention.

  1. Is a control required? In the submitted symmetric-channel model, an informative-only experiment has identical record laws under the two hypotheses. Changing θ\theta complements every raw response but preserves all XORs. A causal edge rule sees the same history, so it makes the same choices. Its minimax risk is 1/21/2. Controls alone are also uninformative about θ\theta. The optimal paired-only policy uses both query types for every N≥2N\ge2.

Requiring a control on every trajectory is our common finite-budget protocol. Once a retained response reconstructs the raw record, a control is no longer needed for identification. Dropping this convention changes retained risk from eN−1e_{N-1} to eNe_N, with the same exponent β\beta. Section 2 now separates the identifiability argument from this benchmark convention. The necessity uses symmetry: Appendix F.2 gives an asymmetric-channel example in which informative-only differences can distinguish the hypotheses.

  1. A reference chosen afterwards, or several references. For any index jj in a connected graph, Xv=Xj⊕⨁e∈path⁡(j,v)Ze.X_v=X_j\oplus\bigoplus_{e\in\operatorname{path}(j,v)}Z_e. This identity holds for every raw vector and noise law. A fixed public index recovers the entire record; selection after acquisition works too. Data-dependent selection cannot exceed full-record access because the index and its value are functions of the same vector. Once that vector is reconstructed, additional retained responses are already determined. For a disconnected graph, one reference per component gives full reconstruction, although a particular decision may require fewer.

Disclosure time affects the acquisition policy, not the reconstruction identity. Revealing a response at the end restores the final test's data; earlier decisions still used differences. Section 8 and Appendix F.5 state this distinction. Appendix G also gives a stopping construction attaining the retained-reference leading cost when the reference is disclosed only after stopping. For a control, the acquired response equals its realized flip, so disclosing the response also reveals that flip. This orients the existing differences without another acquisition.

  1. Unknown or misspecified η\eta. Under independent common-rate noise, the counter policy and terminal decision are optimal for every 0<η<1/20<\eta<1/2. No rate estimate enters its actions or decision; actual risk is the optimum at the true rate.

Proposition 6 turns this into a uniform guarantee. For an independently justified bound ηˉ<1/2\bar\eta<1/2, inf⁡πsup⁡0<η≤ηˉR(π,N;η)=Rad∗(N;ηˉ),\inf_\pi\sup_{0<\eta\le\bar\eta}R(\pi,N;\eta)=R^*_{\rm ad}(N;\bar\eta), attained by the same policy. To prove monotonicity, add independent artificial flips BvB_v to a lower-rate experiment. Each requested difference becomes (Xu⊕Xv)⊕Bu⊕Bv(X_u\oplus X_v)\oplus B_u\oplus B_v. This uses only available XORs and independent randomness, and simulates the noisier adaptive history. Pointwise optimality then places the worst risk at ηˉ\bar\eta.

For ηˉ=0.2\bar\eta=0.2 and error 0.0010.001, Table 3 gives minimum fixed, adaptive and retained budgets of 48, 34 and 22. Each budget attains the target and its predecessor fails; the adaptive implementation is unchanged. Evaluating the certificate uses no additional audit responses. Without a bound away from 1/21/2, worst-case finite-budget risk is 1/21/2.

Appendix F treats changes in the noise law. If every response probability, given the full raw history and action, changes by a factor in [e−κ,eκ][e^{-\kappa},e^\kappa], Proposition 7 bounds the unchanged policy's risk by e2Nκe^{2N\kappa} times the new optimum. Exact optimality can change under heterogeneity, as the explicit example shows. The supplementary program reproduces Table 3 and checks both conditional errors against an independent fair-measure calculation.

I keep my score

Reviewer_iYmqOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies the questions related to binary hypothesis testing. In particular, they consider a setting when one could only ask if two responses are different, without actually seeing the responses. The authors show (or attempt to show) that there is a statistical "cost", compared to having the actual answers. The authors optimize which quires to ask, also accounting for the causality.

Critical strengths

I cannot identify any strengths of the work. It is written in an obscure, not self-containing way. I had to read the cited works just to get an idea of what the authors intended to do.

Critical weaknesses

The paper is written in an obscure way preventing to understand the problem that is being studied, the method and its comparison to related works.

The paragraph of the problem formulation in the introduction introduces a new term without a proper clarification in every single sentence, preventing a reader to understand what is the problem.

The comparison with related works clearly states "Thus neither the expression nor finite-horizon optimality of feedback strategies in general is new". The next paragraph states that the problem is different, but without going into details on what is different. It raises concerns regarding the novelty.

Questions for authors

Could you formulate in your own words what is the problem you want to study, what is the contribution of the paper and how it relates to the prior works?

3 comments
AuthorsOpenReview ↗

Problem formulation, contributions, and relation to prior work

Thank you for identifying the unclear parts of the presentation. We have clarified the opening and gathered the closest-work comparison in Table 4. The question is whether better sampling can compensate for retaining differences rather than raw responses.

The experiment. There is an unknown bit θ\theta. A control returns a noisy zero, EE; an informative query returns θ⊕E\theta\oplus E. Each response costs one query and is independently flipped with probability 0<η<1/20<\eta<1/2. The auditor knows the query types, but sees only whether selected pairs of acquired responses agree or disagree. It may choose later queries from those differences. We minimize the larger of the two hypothesis-conditional errors after NN acquisitions, over query allocations, pairing graphs and decision rules.

For example, differences (X1⊕X2,X1⊕X3)=(1,1)(X_1\oplus X_2,X_1\oplus X_3)=(1,1) represent both (0,1,1)(0,1,1) and (1,0,0)(1,0,0). Comparing the last two responses gives zero in either case. Keeping the acquired X1X_1 resolves the ambiguity. A connected record has one missing orientation. More edges reuse the data; fresh acquisitions add noisy evidence.

Results and method. Theorem 2 gives the exact fixed-design risk eI+eK−2eIeKe_I+e_K-2e_Ie_K, for II informative and KK control responses, I+K=NI+K=N; ene_n is majority-testing error. It also solves the allocation. At N=4N=4 and η=0.1\eta=0.1, a 1+31+3 split has error 0.12240.1224, whereas 2+22+2 has 0.180.18. The decision uses only differences: choose either represented vector and XOR its two group majorities, returning a fair bit if a group ties. Its distribution is invariant to complementing the representative.

To analyze adaptation, give the hypotheses equal prior mass. Write UU for the hidden control response and V=θ⊕UV=\theta\oplus U. Then U∼Bern(η)U\sim\mathrm{Bern}(\eta) and VV is independent and uniform. Control differences observe noisy UU; informative differences observe noisy VV, and the target is U⊕VU\oplus V. Counters (A,B)=(1,0)(A,B)=(1,0) track these bits; the initial 1 records the control's prior bias. Query the bit with smaller absolute count and add 1−2y1-2y to its counter after observing difference yy. Return one if AB<0AB<0, zero if AB>0AB>0, and a fair bit on ties. The rule needs neither the noise rate nor the horizon. Theorem 3 proves its Bayes optimality at every horizon. Its two conditional errors are equal, so its optimal average error is also the minimax error.

The action comparison requires looking beyond immediate error reduction. At η=0.1\eta=0.1 and (A,B)=(2,1)(A,B)=(2,1), either action has one-step expected posterior error 9/829/82. With two acquisitions left, querying BB followed by an optimal final query gives 81/205081/2050, while querying AA first gives 9/829/82. Appendix B.5 gives this calculation. Eq. (8) proves the choice for every remaining budget, including boundaries.

Theorem 4 compares their exponents, with β=−log⁡(2η(1−η))\beta=-\log(2\sqrt{\eta(1-\eta)}) for raw records. At N=5N=5 and η=0.1\eta=0.1, the fixed, adaptive and retained-reference errors are 0.12240.1224, 0.06480.0648 and 0.0280.028. All three pay for five responses, including controls, with their own optimal allocations. Lemma 1 and the causal star simulation extend the lower bound to every legal pairing graph.

Relation to prior work. Nitinawarat et al.'s three-location example achieves the same adaptive exponent expression. Burnashev establishes it as the optimal three-message feedback exponent and gives an optimal finite-horizon partition. Table 4 (p. 10) compares these tasks and their fixed-design rates: 2β/32\beta/3 in those examples, versus β/2\beta/2 here. Our terminal loss adds posterior masses within the two parity classes, rather than minimizing location or message error. The likelihood factorization in Eq. (5) and action inequality in Eq. (8) solve the resulting finite-budget problem.

Soloviev and Halpern's noisy Boolean-testing game (JACM, 2022) contains this XOR experiment with the prior above, N−1N-1 tests and rewards +1/−1+1/-1. Their XOR discussion already explains why both variables require attention. Appendix E.3 specifies this mapping. Our contribution is the exact finite-budget solution and all-horizon policy for this instance, together with the comparison to retaining the acquired reference.

Two informative differences Yi=V⊕EiY_i=V\oplus E_i satisfy Pr⁡0(Y2=1∣Y1=1)=1/2\Pr_0(Y_2=1\mid Y_1=1)=1/2 but Pr⁡0(Y2=1)=2η(1−η)\Pr_0(Y_2=1)=2\eta(1-\eta). Given the complete star history, the posterior on (U,V)(U,V) factorizes: query-selection probabilities depend on observed prefixes and cancel on normalization, leaving separate response-likelihood factors for the two coordinates. Appendix B.1 writes this product explicitly. This explains the two-counter state and why the binary memoryless sensing theorem has different assumptions.

Table 3 translates these results into acquisition budgets. At η=0.2\eta=0.2, error at most 0.0010.001 requires 48 fixed paired-only responses, 34 adaptive responses, or 22 with retention. Appendix H and the supplementary program give exact risks at each threshold and its predecessor.

Dear Authors,

Thank you for your reply. Unfortunately, I still do not understand the problem being studied, though I must admit that I am only superficially familiar with hypothesis testing and causality.

In particular, what is "control", is the flipping probability η\eta included in the noisy zero EE? Who is the "auditor"? What are those query "types"? What are the query allocations? I thought that the goal is to estimate the unknown bit θ\theta, what could be a strategy there except for querying the noisy responses many times? What are the "pairing graphs"?

"More edges reuse the data" - is there a graph, how is it defined?

"A connected record has one missing orientation." What is an orientation, the edge orientation?

What is "noisy evidence" ?

What do you mean by "risk", a failing probability?

What is the "terminal loss"?

I made another attempt to read the abstract, I don't think that much has been changed, in my opinion it is not comprehensible.

AuthorsOpenReview ↗

Clarifying the queries, comparisons, and error probability

Thank you for reading the revision. Our earlier reply left several terms unexplained.

Controls, noise, and the auditor.

The goal is to estimate a fixed unknown bit θ∈{0,1}\theta\in\{0,1\}. Each query produces one response. There are two query types: a control, whose answer before noise is 0 for either value of θ\theta, and an informative query, whose answer before noise is θ\theta.

For each response, a random bit EE records whether it flips: Pr⁡(E=1)=η\Pr(E=1)=\eta and Pr⁡(E=0)=1−η\Pr(E=0)=1-\eta, with 0<η<1/20<\eta<1/2. Thus η\eta is a probability, while EE is the realized 0 or 1. A control returns EE; an informative query returns θ\theta if E=0E=0 and 1−θ1-\theta if E=1E=1. Every acquisition uses an independent flip. A control's actual response can therefore be 1 despite its known answer before noise.

The auditor is the algorithm choosing queries and making the final guess. It knows the query types but cannot inspect individual responses. It receives only whether selected pairs are the same or different. These comparisons are exact. They are "noisy evidence" because the responses may have flipped. Each new response, including a control, costs one query. Comparing responses already acquired uses no additional query. We ask whether better querying can compensate for hiding the responses.

Query allocation and strategy.

Repeated queries help only if their comparisons distinguish the two possible values of θ\theta. With informative queries alone, changing θ\theta reverses every response but leaves every same/different comparison unchanged. The auditor therefore cannot learn θ\theta from those comparisons, however many responses it acquires.

With one hidden control, the best error approaches η\eta as informative queries accumulate: comparisons to that control share its flip. More controls help resolve that uncertainty, but leave fewer queries for informative responses. Choosing how many of each type to acquire within a budget NN is the query allocation. The strategy also chooses which pairs to compare and how to make the final guess. A fixed strategy makes the acquisition and comparison choices in advance. An adaptive strategy can choose later queries and comparisons from earlier results; "causal" means each choice uses only information already available.

For a concrete example, let η=0.1\eta=0.1 and acquire one control and one informative response. If θ=0\theta=0, the responses differ only when exactly one flips, with probability 2(0.1)(0.9)=0.182(0.1)(0.9)=0.18. If θ=1\theta=1, they differ with probability 0.820.82. Guessing 1 for "different" and 0 for "same" has error 0.180.18 in either case. Keeping the actual control response as well lets us recover the informative response and reduces the error to 0.10.1. Both procedures use the same two acquisitions; the retained response is still noisy.

Pairing graphs, extra edges, and orientation.

The graph has one vertex per acquired response and an undirected edge per compared pair, labelled 0 for "same" and 1 for "different". If response 1 differs from both responses 2 and 3, responses 2 and 3 must agree. Adding that third edge reveals no new information. This is what "more edges reuse the data" meant: a comparison within an already connected component is determined by the comparisons along an existing path.

In a connected graph, every pair of vertices is joined by a path. Its comparisons determine the response vector up to reversing every bit. The three-response example permits exactly (0,1,1)(0,1,1) or (1,0,0)(1,0,0). "Orientation" meant choosing between these two vectors; the edges have no direction. Knowing any one actual response selects the vector and reconstructs all acquired responses. It does not remove the noise already present in them.

Risk and terminal loss.

The terminal loss records one final decision: 1 if the guess is wrong and 0 if correct. For a fixed value of θ\theta, its average over repeated runs is the error probability for that case. Yes, risk is a failure probability: we take the larger of the error probabilities for θ=0\theta=0 and θ=1\theta=1.

Contribution and the revised abstract.

The results are the exact best fixed-design error and allocation, an adaptive strategy optimal at every budget, and the comparison with retaining one response at the same acquisition cost. As the budget grows, the optimal error decreases exponentially; adaptation improves this rate, and retention improves it further. The adaptive rate is known from Nitinawarat et al. and Burnashev (Table 4). Soloviev and Halpern's framework contains our paired-only problem; we solve this instance and quantify the cost of discarding the raw responses.

The revised abstract now states what the two query types return before noise, where noise enters, what the auditor observes, what each query costs, and which choices we optimize. It describes risk as the worst-case error probability and states the three results after the setup. Sections 1 and 2 give the definitions and example above.

Reviewer_FfD9OpenReview ↗
Rating
4
Confidence
1
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the statistical efficiency loss when an audit records only pairwise differences (XORs) between binary responses rather than the raw responses themselves, under a fixed acquisition budget and binary symmetric noise. For fixed designs, it exactly characterizes the finite-budget minimax risk and shows the optimal error exponent is halved relative to the raw-record benchmark; for causal adaptive designs using only released differences, it proves a simple “sample the less-certain side” policy is minimax optimal at every horizon, with an exponent strictly between the fixed-design and raw-record exponents. A single retained raw response (already acquired, no extra query) orients any connected difference record, recovers all raw responses, and restores the raw-record exponent, cleanly quantifying the cost of the paired-only constraint.

Critical strengths

The core problem, assumptions, and contributions are precisely stated; key lemmas (graph quotient, star dominance) and their implications are clearly explained.

Critical weaknesses

Please refers to the questions.

Questions for authors
  1. How robust are the fixed-design and adaptive exponents to mild violations of the assumptions—e.g., slightly asymmetric BSCs, heterogeneous per-sample noise rates, or weakly correlated flips? Does the “less-certain side” rule remain optimal or near-optimal?

  2. Is there a tight converse or characterization for variable-length stopping policies under the same storage constraint? Could stopping close the remaining gap to β\beta without retaining a reference?

1 comment
AuthorsOpenReview ↗

Noise robustness and variable-length stopping

Thank you for these helpful questions. Section 8 summarizes both answers, with proofs in Appendices F and G. All acquisitions, including the initial control, are counted.

Q1. Noise assumptions and the uncertainty policy. For independent symmetric channels with known informative/control rates ηI,ηC∈(0,1/2)\eta_I,\eta_C\in(0,1/2), constant within each query type, Appendix F.6 gives the exact connected-record risk r(I,K)=eI(ηI)+eK(ηC)−2eI(ηI)eK(ηC).r(I,K)=e_I(\eta_I)+e_K(\eta_C)-2e_I(\eta_I)e_K(\eta_C). Minimizing over I+K=NI+K=N, K≥1K\ge1, gives the fixed-design optimum over all graphs. With βj=−log⁡(2ηj(1−ηj))\beta_j=-\log(2\sqrt{\eta_j(1-\eta_j)}), the optimized exponents are Efix=βIβCβI+βC,Ekeep=βI.E_{\rm fix}=\frac{\beta_I\beta_C}{\beta_I+\beta_C},\qquad E_{\rm keep}=\beta_I. The informative fraction tends to βC/(βI+βC)\beta_C/(\beta_I+\beta_C), balancing the two groups' evidence. Equal rates recover the original β/2\beta/2 and β\beta.

For an unknown common rate, Theorem 3's counter rule remains exactly optimal. Proposition 6 gives its worst risk over 0<η≤ηˉ<1/20<\eta\le\bar\eta<1/2 as Rad∗(N;ηˉ)R^*_{\rm ad}(N;\bar\eta) without estimating the rate.

Asymmetric, heterogeneous or history-dependent changes are covered by a conditional perturbation bound. Suppose every response probability, conditional on the complete raw history and action, changes by a factor in [e−κ,eκ][e^{-\kappa},e^\kappa] under either hypothesis. Proposition 7 gives, for the same legal policy including its decision, e−NκR(π,N)≤R~(π,N)≤eNκR(π,N).e^{-N\kappa}R(\pi,N)\le\widetilde R(\pi,N)\le e^{N\kappa}R(\pi,N). The bounds also hold for optimized risks. A nominal optimum thus has perturbed risk at most e2NκR~∗(N)e^{2N\kappa}\widetilde R^*(N). Conditional flip-rate deviations δ<η\delta<\eta permit κ=−log⁡(1−δ/η)\kappa=-\log(1-\delta/\eta). This includes bit-dependent asymmetry and controlled temporal dependence. A conditional total-variation bound δ\delta instead gives additive excess risk at most 2[1−(1−δ)N]2[1-(1-\delta)^N].

For classes with nominal exponents Ej<EkE_j<E_k and Δ=Ek−Ej>2κ\Delta=E_k-E_j>2\kappa, the perturbed risks satisfy R~k∗(N)/R~j∗(N)≤exp⁡[−N(Δ−2κ)+o(N)]\widetilde R_k^{\ast}(N)/\widetilde R_j^{\ast}(N)\le\exp[-N(\Delta-2\kappa)+o(N)]. Their ordering therefore persists for all sufficiently large budgets, even if perturbed exponent limits do not exist. Where the limits exist, each moves by at most κ\kappa.

Exact policy optimality can change. With four acquisitions and initial/control/informative rates 1/51/5, 1/5+δ1/5+\delta, 1/5−δ1/5-\delta, the correctly calibrated uncertainty policy has larger risk than three informative endpoints by 21125δ+1425δ2>0(0<δ≤1/100).\frac{21}{125}\delta+\frac{14}{25}\delta^2>0\quad(0<\delta\le1/100). Appendix F.3 proves the action choices and risk identity. The gap vanishes with the perturbation. For weak correlation, pairwise covariance alone is insufficient: Appendix F.4 preserves marginal rate η\eta and arbitrarily small covariance, yet a persistent fair-noise regime of probability δ\delta produces error floor δ/2\delta/2. This regime violates the small conditional bound required to preserve the exponent gap. With known independent false-positive/false-negative rates 0<α,γ<1/20<\alpha,\gamma<1/2, two informative responses have XOR-one probabilities 2α(1−α)2\alpha(1-\alpha) and 2γ(1−γ)2\gamma(1-\gamma). When α≠γ\alpha\ne\gamma, repeated disjoint pairs permit consistent testing without controls (Appendix F.2).

Q2. Variable-length stopping. A hard cap τ≤N\tau\le N cannot improve the fixed-horizon optimum: pad a stopped policy with ignored acquisitions. For expected cost, fix known 0<η<1/20<\eta<1/2 and minimize the worst-hypothesis mean acquisition count subject to both conditional errors being at most ε\varepsilon. Put Dη=(1−2η)log⁡((1−η)/η)D_\eta=(1-2\eta)\log((1-\eta)/\eta). Proposition 8 proves

C_{\rm keep}(\varepsilon)=\frac{1}{D_\eta}\log\frac1\varepsilon+O_\eta(1).$$ For the paired-only converse, let $U$ be the initial hidden control response and $V=\theta\oplus U$. Condition on $(U,V)$ and compare with $(1-U,V)$ and $(U,1-V)$. Each alternative changes parity, and only queries to that coordinate distinguish it. For $0<\varepsilon<\eta/2$, each state has hypothesis-conditional weight at least $\eta$, so its error is at most $b=\varepsilon/\eta<1/2$. Stopped KL divergence forces $D_\eta\mathbb E n_U,D_\eta\mathbb E n_V\ge\operatorname{kl}(1-b,b)$. Two scalar sequential likelihood-ratio tests attain the matching coefficient; Appendix G gives explicit finite-error upper and lower bounds. For retention, test $V$ from informative differences and decide when to stop without observing $U$. Then reveal the acquired $U$ and return $U\oplus\widehat V$. One scalar test suffices. A raw-record stopped-KL lower bound matches this construction, so even disclosure only at stopping attains the retained coefficient. Thus stopping can exceed the fixed-horizon retained exponent ($D_\eta/2>\beta$), but under matched expected costs the reference still halves the leading sample cost. The result is first-order sharp at fixed $\eta$; its attaining thresholds use the known rate.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.