Independent-Pool Single-Draw Oracle

Follow this topic Ask about this topic

Momentum

2 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Jul 6Week of Sep 21

Latest papers 25

Sep 9, 2026cs.LG

An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order

Attias, Hanneke and Ramaswami (NeurIPS 2025) asked whether randomization provably reduces the oracle calls needed for online learning when the class is accessible only through an oracle. We study the instance they singled out: transductive online learning of thresholds on an unknown total order of T instances, with a consistency-type ERM oracle that returns a full concept consistent with a queried labeled set (or reports non-realizability). Our main result is a separation for a fixed natural oracle. When the oracle is the minimal-prefix rule (or the maximal-prefix rule), every deterministic learner makes M mistakes and Q calls with

M+Q\ge T-\varepsilon

on some instance (

\varepsilon\in\{0,1\}

, according to whether the empty prefix is a concept), and the constant is exact; hence

O(\log T)

mistakes cost

T-\varepsilon-O(\log T)

calls, whereas that paper's randomized learner achieves

O(\log T)

expected calls and mistakes under the same rule. The randomized order is optimal: on an explicit hard distribution under the minimal-prefix rule, every learner has expected mistakes at least

((T+1-\varepsilon)\,128^{-\mathbb{E}[Q]}-1)/2

, so

Ω(\log T)

expected calls are necessary for polylogarithmic mistakes. The separation is governed by the oracle's selection rule, not by the class alone: for a legal feasible-median ERM rule a deterministic learner achieves

O(\log T)

calls and mistakes, while a global-median rule again forces linear total cost. The same linear bound holds when the oracle's answers are chosen adversarially and then frozen into a memoryless oracle. We add partial tradeoff results for fixed query budgets (the middle regime is open) and an interface contrast: with only a weak consistency oracle, returning a realizability bit, both deterministic and randomized learners need

Θ(T)

calls.

Xuan Li

University of New South Wales, Sydney, Australia

First Order Oracle Complexity Independent-Pool Single-Draw Oracle Learning-Augmented Algorithms Order Exponents Trade-Off

Sep 1, 2026cs.LG

Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle

We revisit median-of-means estimation from a deterministic optimization viewpoint and develop a family of block-Lp estimators for robust learning with heavy-tailed and adversarially corrupted data. In a block contamination model with at least a fraction 1 minus epsilon of good blocks, we first show that every convex block M-estimator has worst-case robustness constant at least 1 divided by 1 minus 2 epsilon. This matches the classical median-of-means bound and proves that the trimmed-block oracle constant 1 divided by 1 minus epsilon cannot be attained within the convex class. We then introduce a nonconvex block-Lp family for p between 0 and 1 and derive finite-sample deterministic robustness bounds for all global minimizers. As p decreases from 1 toward 0, these bounds continuously approach the trimmed-block oracle constant. For sufficiently small p, the global minimizers coincide with those of the oracle under a mild separation condition. We also show that the block-Lp objectives have a benign landscape, with all local minima remaining close to the truth and no bad basins. Combining these results with block-level concentration yields sub-Gaussian deviation bounds under finite 2 plus delta moments and high-dimensional extensions to robust mean estimation and sparse regression.

Angshul Majumdar

Department of Electronics and Communications Engineering, IIIT Delhi, India

Empirical Risk Minimization Nonconvex Independent-Pool Single-Draw Oracle

Aug 12, 2026cs.AI

How to Spend Your Oracle Budget: Practical Guidance for Protein Structure Prediction Models

Foundation models for protein structure prediction remain unreliable on certain targets. External oracles can flag and correct these failures, but biological oracles are expensive, making oracle budget a critical constraint. Existing guidance methods, such as FK-steering, DPO, and Best K-of-N sampling, differ in how they spend this budget, yet no systematic comparison exists to guide method selection. To bridge this gap, we benchmark these methods alongside the recently proposed Optimisation Over Outputs (O3), which applies off-the-shelf optimisers within a generative model's latent subspace. We extend the usage of O3 to protein structure prediction models. Overall, our work provides the first practical reference for oracle budget-aware guidance. Our evaluation on two protein targets, calmodulin (1CLL) and E. coli aspartate transcarbamoylase (9EEH), reveals that no single method consistently dominates across all budgets and oracles. Specifically, O3 proves most effective at low oracle budgets, while FK-steering and DPO demonstrate improved performance as the budget increases. We distil these findings into actionable recommendations for practitioners operating under real-world oracle-budget constraints.

Aleksandra Kalisz, Jack Simons, Krisztina Sinkovics +4

InstaDeep Ltd · University of Oxford · Lancaster University

Independent-Pool Single-Draw Oracle Protein Structure Prediction Token Budget Allocation Model Selection

Aug 7, 2026cs.AI

CoBa: Cost-Effective Test-Time Scaling via Compute-Balanced Routing

Test-time scaling is often implemented by spending more compute along one axis: sampling more solutions, extending a chain of thought, or applying a stronger evaluator. Under a fixed inference budget, these choices compete. This paper formulates test-time reasoning as a compute-allocation problem in which a system must decide whether the next unit of compute should be spent on generation, verification, or stopping. We introduce CoBa, a compute-balanced routing policy that first obtains a small set of candidates, applies cheap verification broadly, and routes uncertain or high-value candidates to stronger verification. On 3,129 example-generator evaluations spanning MATH-500, AIME 2024/2025, AMC 2023, and procedural symbolic reasoning, CoBa-Routed-Strong reaches 85.13% macro accuracy, statistically matching a self-evaluation weighted-voting proxy at 85.20% while using 49.1% fewer parameter-weighted tokens. It also matches best-of-16 majority voting within 0.01 macro-accuracy points while using 58.9% fewer parameter-weighted tokens; paired tests retain a small best-of-16 edge at substantially higher cost. Paired bootstrap tests show significant gains over single-sample decoding, while the remaining gap to the pool oracle exposes headroom for sharper routing. For local reasoning systems, test-time scaling becomes a question of where the next computation is most valuable.

Yan Zhou, Yue Ouyang, Kaiyang Zheng +1

School of Mathematics and Statistics, Changsha University of Science and Technology, Changsha, China · School of Biomedical Engineering, Shanghai Jiao Tong University, Shanghai, China.

Test-Time Scaling Test Time Reasoning Benchmark Tractability Independent-Pool Single-Draw Oracle

Aug 2, 2026cs.AI

Computing with Agentic Oracles

This paper extends the stochastic-oracle model of AI-augmented computing to include agentic oracles. Unlike a stationary stochastic oracle, which responds to the same query according to a fixed response distribution across calls, an agentic oracle can pursue a goal autonomously and may access an environment containing task-relevant resources. These capabilities affect both response distributions and token costs beyond what is visible at the query-response interface. We develop a framework for analyzing token costs in Stochastic-Oracle Turing Machines (SOTMs) that compute with agentic oracles. Each call has an \emph{orchestration token cost}, visible to the caller at the query-response interface, and an \emph{agentic token cost}, incurred by internal operations not exposed to the caller. We show that an SOTM computing with an agentic oracle that can retain intermediate state can have token-cost advantages over SOTMs using stationary stochastic oracles when solving the same task at the same quality level, both with and without environment access. We also investigate goal-loss risk, including how internal dispatch ordering can reduce exposure to irreversible actions. We provide a goal-loss avoidance criterion, derive progress--retry--goal-loss formulas, establish goal-depth lower bounds on token complexity, characterize token complexity when the probability of goal loss is zero, and show that goal-loss risk can impose an upper bound on the achievable quality of a task involving environment updates.

Jie Wang

Richard A. Miner School of Computing and Information Sciences, University of Massachusetts, Lowell, MA 01854, USA.

Independent-Pool Single-Draw Oracle

Aug 2, 2026cs.AI

Auditing Discovery Claims: A Two-Sided Criterion for Agentic Science, with the Negative Side Decidable

When a self-improving AI-for-science system claims a new capability, the evidence is usually a benchmark delta, a description-length gate, or a p-value. None separates a real gain from extra search, from a changed verifier, or from adaptation to a fallible oracle. We build a two-sided audit whose negative side is a formal fact: a pseudoknot-free oracle provably cannot represent a crossing base pair, so the prior verifier's range is bounded exactly, offline, before any run. "New" is relative to the agent's prior self, never to the base model. First, how far a single fallible oracle can inflate a capability claim. An invented, solver-free operator solves 43/60 crossing RNA targets under the predictor it optimizes, above a context-free floor of 0/60; under three predictors, 1/60 survives. Paired on the same 43 targets, a predictor the operator never saw confirms 2 of its designs against 26 for a minimum-free-energy solver (p = 8e-7). No statistic computed from the system and its own oracle sees that gap. Second, agent-written procedures can beat a human-written one under a judge no objective can flatter, at a fraction of the compute. Of six frontier models, the two whose operators ran without timeouts carry over at 0.293 against our 0.095 (n = 951 paired units, target-clustered [+0.108, +0.297], p = 5e-5) while spending 4.6-10x fewer oracle calls. Three rungs: difference under an outside adjudicator (reached), not bought with compute (reached, both directions), mechanism identified and transferable (not reached; seven candidates tested, none moves the statistic). The ceiling is the panel itself: its three predictors share nearest-neighbour thermodynamic parameters, two agreeing at kappa = 0.673. The audit is as unsparing about our own system: matched undirected search is an exact zero, and a search-free probe puts 84% of our headline effect on targets a random sequence already solves.

Wenhui Chen, Jianlin Chen, Ziyao Lin +1

University of Macau · 2South China University of Technology

Independent-Pool Single-Draw Oracle Model Auditing Falsehood Counter Turing Test Messenger Rna Negative Results

Jul 30, 2026cs.AI

How Benchmarks Mis-Score Computer-Use Agents

Computer-use agents (CUA) are being deployed to browse the web and operate desktop software, yet their benchmark scores are still commonly produced by brittle scripted oracles. A score is the output of a pipeline in which tasks can be stale, trajectories can omit decisive visual evidence, evaluators can reject valid alternatives, and aggregate reports can hide the cause of failure. We organize these problems into a reliability framework spanning task construction, trajectory observation, scoring, and reporting. We then audit 150 public failure-scored trajectories from five web, enterprise-workflow, and desktop-control benchmarks, find that 15.3% of FAIL verdicts are wrong: 10.7% are evaluator false negatives and 4.7% are broken tasks. For genuine failures, a three-tier diagnostic taxonomy shows that verification/feedback and planning failures dominate execution/grounding errors, while a single scalar success rate can not explain. We connect these findings to newer long-horizon CUA benchmarks and derive stage-specific design rules for CUA evaluation.

Zihan Dong, Zhiyuan Ma, Zekun Wang +5

Georgia Institute of Technology · North Carolina State University · Lenovo AI Technology Center +3

Computer-Use Agents Agentic Evaluations Independent-Pool Single-Draw Oracle

Jul 25, 2026cs.SE

Adversarial Test-Hardening for AI-Written Code: An Instrument Autopsy and a Pre-Registered Causal Estimate of the Critic Loop

Large language models increasingly write both code and the tests meant to check it; coverage records what ran, not what was verified. We study an adversarial test-hardening loop under a mechanical oracle: a Tester model writes tests, mutation testing names surviving injected defects, and a Critic model writes tests to kill exactly those, with every verdict decided mechanically, so no model judges another's output. In Experiment 1, on five Python subjects (one same-lineage-loop cell could not be scored), the loop killed 105 mutants that one-shot generation missed and lost none, and the cross-lineage-Critic question returned a pre-declared null. The central finding was an autopsy: an earlier analysis reported a cross-lineage effect at p = 9.5e-66 that was an instrument artifact, an output cap silently truncating the verbose model, caught only by adversarial review of the completed analysis. Review then found a further confound, each arm resampling its own initial suite; Experiment 2 removes it. Under a pre-registered frozen-shared-round-0 design (five replicates on each of four subjects, seeds committed in advance), same-lineage Critic rounds killed 78% of the survivors the frozen initial suite left standing (mean incremental kill rate 0.783, 95% cluster-bootstrap interval [0.592, 0.935]), a within-replicate causal estimate; the cross-provider configuration showed a positive pilot difference (rate gap 0.178, 95% interval [0.039, 0.347]; magnitude dominated by a single replicate) at 5.5x lower arm cost. This compares two named model-provider-harness configurations, not an isolated lineage effect: part of the gap is one configuration's receipted operational failures, including truncation recurrences, now detected and scored rather than laundered. Cross-model comparisons can inherit the asymmetries of the harness that runs them. We release both protocols, all receipts, and the analysis code.

Jeff Otterson

W. P. Carey School of Business, Arizona State University

Code Quality Adversarial Evaluation Test Generation Code Generation Critic Lineages+2

Jul 21, 2026stat.ML

The Tractability Landscape of Sampling with Inexact Scores

We provide a simple and tight characterization of the types of inexact score oracle access that permit sampling with vanishing total variation bias, for a standard, well-behaved target family. Our main result shows that any weaker error than the sub-Gaussian assumption used by [YW26] rules out the tractability of unbiased sampling. This strengthens the conclusion of [CCSW26] to be algorithm-agnostic, and to hold for a wider range of error assumptions.

Anming Gu, Kevin Tian, Hubert Yang +1

University of Texas at Austin

Optimal Sample Complexity Independent-Pool Single-Draw Oracle Scores Tractability

Jul 20, 2026cs.HC

AlphaOracle: Oracle bone script decipherment via human-workflow-inspired deep learning

Approximately 3,000 of the 4,500 oracle bone script (OBS) characters remain undeciphered due to fragmentary inscriptions and sparse evidence. Current AI approaches fail to replicate expert workflows that integrate form analysis, contextual semantics, and philological reasoning. We introduce AlphaOracle, a human-workflow-inspired framework that systematizes OBS decipherment using the largest digitized corpus to date. Its multi-stage pipeline comprises: (i) rubbing parsing; (ii) radical-based morphological analysis with diachronic modeling; (iii) contextual retrieval with semantic alignment; and (iv) philological validation against classical sources. Each stage generates explicit, confidence-weighted evidence chains, culminating in interpretable reports for scholarly verification. Across multiple test characters, AlphaOracle's readings strongly agreed with expert interpretations. In a study of 86 domain specialists, it reduced analysis time by 64% and 79% of participants rated it highly useful. Notably, AlphaOracle resolves the character "Lao" as a toponymic or clan designation, offering concrete revisions to Shang administrative and social interpretations. These results suggest that computational methods aligned with philological practice can facilitate OBS research and provide a conceptual reference for studies of other undeciphered scripts.

Yuliang Liu, Haisu Guan, Pengjie Wang +11

School of Software Engineering, Huazhong University of Science and Technology, Wuhan 430074, China · Key Laboratory of Oracle Bone Inscriptions Information Processing, Anyang Normal University, Anyang 455002, China · School of Electronic Information Engineering, South China University of Technology, Guangzhou 510641, China

Historical Manuscripts Independent-Pool Single-Draw Oracle Oracles Deep Learning

Jul 11, 2026cs.AI

GRID: Grammar-Railed Decoding for Enterprise SQL Generation

Large language models can write SQL, but enterprise deployment demands more than plausible text: outputs must be syntactically valid, must respect per-role and per-schema policy, must carry provable (not best-effort) guarantees, must not slow down as generations grow, and must leave a compliance-grade record of every decision. We present GRID (Grammar-Railed Decoding), a grammar-constrained decoding engine that keys exact next-token masks on parser configurations (lexer scan state x LALR(1) stack) rather than on token sequences, and uses the incrementally advanced LALR(1) parser itself as a viable-prefix oracle. LLM tokens are bridged to grammar terminals by a byte-level trie walk with a context-independent/context-dependent split that makes cache-key soundness hold by construction. Role-based access control is compiled into the language: role projections subset the grammar's productions and schema lexicons restrict identifier terminals, so forbidden verbs and identifiers are unreachable at mask level. Four guarantees (soundness, completeness, termination, and near-constant per-token cost) are stated with explicit preconditions and each paired with a test or benchmark. Rust kernels bring the per-token mask to a 3.6-6.7 us median, ahead of llguidance at p50 and p90 on two tokenizers with zero false rejects; per-token guard cost is position-flat at n=16,000. On Spider, constrained decoding is worth +13 execution-accuracy points at 0.5B, and one checker-guided repair pass over the provably mask-unenforceable residue (column-level policy) lifts a 7B model to 94.5% executable. A hash-chained per-token audit trail replays bit-identically with 100% tamper detection. We state plainly what the mask cannot do (distribution faithfulness, column-level RBAC, non-LALR(1) languages) and where measured cost remains.

Mohsen Arjmandi

evolutionID GmbH

Sql Text-To-Sql Context-Free Grammars Decoding Independent-Pool Single-Draw Oracle

Jul 9, 2026cs.LG

AlphaZero in Sparsely Rewarded Games: Limits and Auxiliary Supervision

AlphaZero has demonstrated that a neural-guided Monte Carlo Tree Search can achieve superhuman performance, but strong play does not necessarily imply perfect play. We study this gap in two oracle-evaluable domains with contrasting structure: Connect Four, a solved partisan game with exact game-theoretic values, and Chomp, an impartial game whose optimal play is governed by Grundy-number structure. Under a unified self-play

+

MCTS pipeline, we compare vanilla AlphaZero, a multi-frame variant (limited to Chomp), and an AlphaZero Auxiliary Loss (AZAL) that adds oracle-derived policy supervision. We find that vanilla AlphaZero achieves strong play across both domains but cannot preserve the exact trajectories required for optimal play: in Connect Four, it fails to maintain the optimal line of play, while in Chomp, it fails to consistently restore the

g=0

invariant. On rectangular Chomp boards, multi-frame inputs alone do not remove this gap. Nevertheless, AZAL substantially improves oracle consistency across multi-seeded full-game traces and sampled-state evaluations. On Chomp, AZAL reaches perfect full-game oracle consistency on 10x11 and high but not complete consistency on 9x10; on Connect Four, AZAL improves oracle-match rate and delays the first oracle mistake, but does not reach perfect play.

Brent Kong, Tejas Ram, Tony Yue Yu

Department of Mathematics · California Institute of Technology · Department of Computer Science

Self-Play Chess Monte Carlo Tree Search Independent-Pool Single-Draw Oracle Minimax Reward Signal+1

Jul 7, 2026cs.AI

How Much Does Correctness Cost? Budgeted Placement of Strong Correctors in a Weak Multi-Agent Swarm

A cheap swarm of unreliable agents can be steered to a correct consensus by a few strong, expensive "oracle" correctors. We ask how much one must spend, and where to place the oracles. We model the swarm as a consensus on a graph in which each oracle pins one node toward the truth at a cost-coupled, concave strength, and measure quality by the coherence H(R)=tr M(R)^{-1}. Our first result is that H stays submodular (each added oracle helps less than the last) even when the oracles differ in strength, so a cost-benefit greedy comes within 1-1/e of the best placement at any budget. Inverting the budget gives the budget-correctness frontier B*(eps), the least spend that guarantees an eps-correct consensus: closed-form on the complete graph, and a minimal oracle count k* when oracles cost the same. Whether a budget then buys a few strong oracles or many medium onese curvature of the cost-quality law: diminishing returns favour spreadsharply increasion. Measured onthe Qwen3 ladder (0.6-32B), the law is concave for math verificatio convex foremergent code tracing, so the verdict is genuinely task-dependent.https://github.com/YehudaItkin/budgeted-oracle-placemen

Igor Itkin

Independent Researcher, Tel Aviv, Israel

Independent-Pool Single-Draw Oracle Swarms Correctness

Jul 3, 2026cs.AI

How to Avoid Debate: Scalable AI Safety via Doubly-Efficient Interactive Proofs

As AI models continue to develop powerful capabilities, it becomes critical that we are able to verify that their output is aligned with our intentions. A recent line of work focuses on verification via debate, a model of interactive proofs where two competing powerful provers, or AI models, debate each other to convince a weak verifier, or a human, of the correctness of their claim. However, debate assumes that the two AI models possess equal abilities and that one of them is truthful, which may not be realistic. In this work, we show \emph{how to avoid debate}: we initiate the study of \emph{single-prover} interactive proofs for AI safety. Prior results in single-prover interactive proofs do not immediately carry over to the AI safety setting: for example, they do not work when the computation has access to an oracle, such as to human judgment or an external database such as the web. We present doubly-efficient single-prover interactive proofs and arguments for oracle-aided computations (also known as relativizing proofs), in the settings where (1) the computation is robust, in the sense that the output does not change if at most a small fraction of the answers to oracle queries are incorrect, or (2) the oracle is a low-degree polynomial. These results suggest that interactive verification is possible even without debate, under structured or noise-tolerant oracle access.

Liyan Chen, Yael Tauman Kalai, Zoe Xi

MIT.

Zero-Knowledge Proofs Artificial Intelligence Safety Debate Adversarial Evaluation Independent-Pool Single-Draw Oracle

Jul 3, 2026cs.LG

What Does a Routing Oracle Measure Under Stochastic Decoding? Coupling, Scorer Choice, and Single-Commit Ceilings

Routing benchmarks often compare a policy that commits to one model before seeing its response with a hindsight oracle that credits any correct recorded output. Under stochastic decoding these are different decision classes. For success marginals

p_{im}

under a frozen query--model--decoder--scorer protocol, we distinguish the clairvoyant single-commit ceiling

R_i=\max_m p_{im}

, product-coupling union

U_i^\perp=1-\prod_m(1-p_{im})

, and premium

Δ_i^\perp=U_i^\perp-R_i

. The marginals alone identify exactly the union interval

[R_i,\min\{1,\sum_m p_{im}\}]

: zero premium is attainable over compatible couplings, not established for an actual deployment. If generation is independent across models, product is the specified protocol's union probability. We audit frozen correctness tensors from 11 open models and 30 archived responses per query--model cell on GSM8K, MATH-500, and GPQA-Diamond. Full-pool display-channel product premiums are 0.371, 3.542, and 5.100 percentage points; the premium intervals from empirical marginals are

[0,0.473]

,

[0,4.787]

, and

[0,7.744]

. Their zero lower endpoints are algebraic. All retained scorers, eight finite-draw paths, and all 2,047 nonempty subpools expose scorer, estimator, and pool sensitivity, not confidence intervals. The GSM8K and GPQA display scorers were developed after limited output inspection. A separate retrospective held-out policy illustration instantiates the policy-specific gap decomposition without establishing new-data generalization. A limited reference-based human check supports scorer agreement only on definite-consensus subsets. Hash-bound evidence supports number checks, not end-to-end reproduction. The contribution is a measurement contract for interpreting oracle gaps conditional on coupling, decision class, scorer, pool, and finite draws, not a population effect or an equal-cost routing gain.

Teng-Ruei Chen

Institute of Bioinformatics and Systems Biology, National Yang Ming Chiao Tung University, Hsinchu 300, Taiwan · Krixvon AI, Taiwan

Large Language Model Routing Independent-Pool Single-Draw Oracle Oracles

Jun 18, 2026cs.SE

The Correctness Illusion in LLM-Generated GPU Kernels

Benchmarks for LLM-generated GPU kernels (KernelBench, TritonBench, GEAK) score correctness through fixed-shape, small-sample allclose-style checks. The number of inputs varies between benchmarks. The shape, dtype, and tolerance are fixed for each kernel. We test that oracle empirically. We construct a controlled corpus of 24 Triton and CPU stand-in kernels (15 correct controls and 9 LLM-style buggy variants seeded with documented transcription errors) and re-evaluate it under op-schema-aware seeded fuzzing with a high-precision (fp64) CPU reference and per-(op, dtype) absolute tolerances. The seeded oracle flags 9 of 9 buggy kernels and passes 15 of 15 correct controls, at zero precision cost on controls. We extend the corpus to 26 ops (adding a flash-attention pair) and re-run the same protocol on five GPU classes (RTX 3060, A10, L40S, A100 SXM4, H100 NVL). The verdicts are identical across all five GPUs: 10 of 10 illusions caught and 16 of 16 controls clean. The corpus result is about LLM-style transcription bugs that the allclose-on-one-shape oracle certifies as correct, not about the bug rate of any specific deployed LLM. Every flagged failure replays byte-for-byte from a stored seed.

Dipankar Sarkar

Arizona State University, USA

Graphics Processing Unit Kernels Correctness Large Language Models(Llms Illusions Independent-Pool Single-Draw Oracle

Jun 15, 2026cs.CV

Vision-Language Models as Zero-Annotation Oracles in Histopathology

Foreground segmentation is the critical first step of every computational pathology pipeline, yet existing methods rely on hand-tuned heuristics or supervised models that overfit to narrow stain and scanner distributions, failing silently on specialised stains such as Jones silver or Elastica van Gieson. We propose a coarse-to-fine approach that recasts foreground segmentation as a visual perception task and leverages general-purpose vision-language models (VLMs) as zero-annotation oracles. Our key insight is that tissue-versus-background discrimination is a natural-image recognition problem, not a histopathological one, so VLMs trained on internet-scale corpora generalise where domain-specific models cannot. We introduce Leica-75, a benchmark of 75 renal transplant whole-slide images spanning three stain families. On Leica-75, our method achieves the highest segmentation quality on out-of-distribution stains (Dice 0.858 +/- 0.027 on Jones, 0.853 +/- 0.041 on EVG) with 7x lower cross-stain variance than the best supervised baseline, while remaining competitive on in-distribution H&E. Few-shot prompting with automatically curated exemplars (Auto-context) rescues hard cases on Stress-32 (n=32), a curated stress-test subset (Dice 0.470 to 0.819 for the 2B model). VLM-based annotation review matches human expert consensus (kappa=0.989 for blur detection; mean precision/recall grading accuracy 0.708 vs. human 0.646 for segmentation mask review). The resulting pseudo-labels are used to distil lightweight student models that are as performant as the teacher model while running for a fraction of the cost. Our framework provides a principled, scalable solution to a persistent infrastructure bottleneck in digital pathology.

Vishal Jain, Giorgio Buzzanca, Sarah Cechnicka +6

Imperial College London, London, UK · Leiden University Medical Center, Leiden, The Netherlands · KU Leuven, Leuven, Belgium +3

Digital Pathology Computational Pathology Lesion Segmentation Medical Vision-Language Models Recent Vision-Language Models Independent-Pool Single-Draw Oracle

Jun 15, 2026cs.AI

The Quality-Utility Paradox: Why High-Reward Data Impairs Small Model Mathematical Reasoning

Knowledge distillation from powerful reasoning models is widely used to improve Small Language Models (SLMs) on mathematical reasoning, often assuming that traces with higher reward model scores provide more useful supervision. We identify a counterintuitive \textbf{Quality-Utility Paradox} in mathematical reasoning distillation. Data refined or synthesized by a stronger Oracle obtains higher perceived quality according to reward models, yet consistently underperforms traces generated by the SLM itself and selected through rejection sampling across Qwen2.5, LLaMA-3, and DeepSeek families. Our analysis shows that Oracle refinement couples logical repair with distributional drift away from the SLM's native reasoning distribution. This drift increases the learner's adaptation cost and can outweigh the benefit of improved reasoning logic. To test this mechanism, we introduce \textbf{Style-Aligned Refinement}, which preserves the native trajectory of the SLM while retaining logical repair from the Oracle. This intervention lowers adaptation cost and restores downstream utility. These findings suggest that effective mathematical reasoning distillation should jointly optimize perceived solution quality and learner-data compatibility, rather than relying solely on reward-model scores. The datasets and code are available at https://github.com/Dracoqhl/Quality-Utility-Paradox.

Haolong Qian, Xianliang Yang, Yinuo ma +6

Tsinghua Shenzhen International Graduate School, Tsinghua University, Shenzhen, China · Microsoft Research Asia, Microsoft, Beijing, China · Faculty of Computer Science and Artificial Intelligence, Shenzhen University of Advanced Technology, Shenzhen, China +1

Independent-Pool Single-Draw Oracle Utility Maximization

May 30, 2026cs.IT

Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation

Low-precision pretraining (FP8, MXFP4, NVFP4) is now standard for frontier language models, yet the literature is almost entirely achievability -- algorithms and empirical scaling laws -- with no matching characterization of what is information-theoretically possible. We study a B-bit quantized stochastic first-order oracle: an optimizer interacts for T rounds and receives, each round, a B-bit adaptive public-coin description of its stochastic gradient. Our main contribution is an exact reduction from optimizing a strongly convex quadratic family to interactively compressed Gaussian mean estimation -- under the B-bit oracle the query carries no information, so optimization collapses exactly onto a sequential distributed-estimation problem. This yields two unconditional lower bounds, a communication bound TB = Omega(d) and a statistical bound T = Omega(sigma^2 d / eps^2), and the sharp product-form bound T = Omega((sigma^2 d / eps^2) max{1, d/B}). The product form is also unconditional: a B-bit transcript carries at most O(TB / sigma^2) of Fisher trace about the mean, so bits rather than dimension limit the recoverable information, and combined with the multivariate van Trees inequality this gives the bound directly, without bounded-likelihood-ratio truncation. We give a near-matching achievability result with exact per-round bit accounting under a bounded-dynamic-range oracle, tight up to a logarithmic factor; the lower bound is for truly Gaussian (unbounded) gradients, and closing this oracle gap is left open. A sequential rate-distortion perspective extends the reduction to correlated and drifting oracles and corrects an earlier conjecture: positive noise correlation raises the bound by (1+rho)/(1-rho) rather than relaxing it. The bounds give an information-theoretic baseline for any low-bit gradient path, not an optimality claim about deployed FP4 systems.

Munsik Kim

Information-Theoretic Limits Stochastic Optimization Independent-Pool Single-Draw Oracle Truncation Stochastic

May 29, 2026cs.MA

Design and Evaluation of Multi-Agent AI Oracle Systems for Prediction Market Resolution

Prediction markets aggregate collective intelligence to forecast uncertain events, but their utility depends on reliable outcome resolution. Existing oracle systems tradeoff fast but brittle automation against accurate but costly human arbitration. Single-LLM oracles achieve meaningful accuracy but inherit all failure modes of their underlying model with no self-correction mechanism. We evaluate whether multi-agent LLM architectures can improve oracle resolution accuracy over single-model baselines. We compare independent aggregation and deliberative consensus against single-LLM baselines (GPT-5 Nano, DeepSeek V3, and Llama-3.3-70B) on 1,189 resolved prediction market questions from KalshiBench. All agents share a common evidence layer through Exa, with retrieval filtered by publication date to isolate reasoning from retrieval quality. Independent aggregation with confidence-weighted voting achieves the highest accuracy at 83.43 percent, outperforming the best individual model by 1.01 percentage points. Deliberative consensus degrades accuracy to approximately 76 percent, below every single-model baseline, attributed to error propagation during debate where confidently wrong models flip correct ones. Error correlations across models (0.529-0.689) explain why aggregation gains fall short of the theoretical Condorcet ceiling, placing a fundamental limit on ensemble approaches. Many questions resist correction by any multi-agent architecture, motivating escalation to human arbitration. We propose routing criteria for hybrid AI-human oracle systems: auto-resolving only unanimous, high-confidence questions yields 97.87 percent accuracy on 47 percent of the dataset, with inter-agent disagreement flagging the remainder for human review.

Tarun Kota

Yale University

Multi-Agent Large Language Model Systems Independent-Pool Single-Draw Oracle

May 14, 2026stat.ML

Harnessing Unimodality in Semiparametric Contextual Pricing via Oracle Price Map Learning

We study contextual dynamic pricing in a semiparametric scalar-index valuation model where the latent value is

v_t=μ_\ast(\mathsf c_t)+ξ_t

, with an unknown utility map

μ_\ast

and an unknown additive noise distribution. The key decision object is the one-dimensional oracle price map

u\mapsto p^\ast(u)

induced by the scalar index

u=μ_\ast(\mathsf c)

and the noise tail. Under the

β

-Hölder smoothness of the tail function for

β\geq 2

and a revenue-geometry condition that gives a unique, stable, interior maximizer, this oracle map is itself

(β-1)

-smooth. We exploit such structure through

\mathsf{ORBIT}

, a modular coarse-to-fine policy that takes a scalar pilot index as input, localizes a benchmark price in each active bin, and learns a local polynomial approximation of the oracle map inside a trust region via bandit convex optimization. For the baseline linear utility model

μ_\ast(\mathsf c)=\mathsf c^\topθ_\ast

, an adaptive elliptical exploration scheme constructs the required scalar pilot online without distributional assumptions on the contexts. The resulting policy achieves regret

\widetilde{O}\big(T^{\frac{2β-1}{4β-3}}+\sqrt{dT}\big)

. For fixed

d

, we establish a matching lower bound in the horizon dependence, unveiling that the nonparametric oracle-map learning term is minimax sharp. The same scalar-pilot interface also yields extensions to sparse high-dimensional linear utility and nonparametric Hölder utility.

Yingying Fan, Yuxuan Han, Jinchi Lv +2

Data Sciences and Operations Department, University of Southern California, Los Angeles, California 90089, USA · Stern School of Business, New York University, New York, NY 10003, USA

Dynamic Pricing Contextual Bandit Framework Independent-Pool Single-Draw Oracle Unimodal Metrics Pilot

May 1, 2026cs.LG

Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation

Reinforcement learning (RL) in large environments often suffers from severe computational bottlenecks, as conventional regret minimization algorithms require repeated, costly calls to planning and statistical estimation oracles. While recent advances have explored offline oracle-efficient algorithms, their computational complexity typically scales with the cardinality of the state and action spaces, rendering them intractable for large-scale or continuous environments. In this paper, we address this fundamental limitation by studying offline oracle-efficient episodic RL through the lens of log-barrier and log-determinant regularization. Specifically, for tabular Markov Decision Processes (MDPs), we propose a novel algorithm that achieves the optimal

\tilde{O}(\sqrt{T})

regret bound while requiring only

O(H\log\log T)

calls to both the offline statistical estimation and planning oracles when

T

is known and

O(H\log T)

calls when

T

is unknown. Crucially, this oracle complexity is entirely independent of the size of the state and action spaces. This strict independence drastically reduces the planning oracle complexity, representing a substantial improvement over existing offline oracle-efficient algorithms (Qian et al., 2024). Furthermore, we demonstrate the versatility of our framework by generalizing the algorithm to linear MDPs featuring infinite state spaces and arbitrary action spaces. We prove that this generalized approach successfully attains meaningful sub-linear regret. Consequently, our work yields the first doubly oracle-efficient (i.e., efficient with respect to both statistical estimation and policy optimization) regret minimization algorithm capable of solving MDPs with infinite state and action spaces, significantly expanding the boundaries of computationally tractable RL.

Haichen Hu, Jian Qian, David Simchi-Levi

Laboratory for Information and Decision Systems · Department of AI and Data Science

Model-Based Reinforcement Learning Markov Decision Processes First Order Oracle Complexity Independent-Pool Single-Draw Oracle

Apr 25, 2026cs.LG

An Analysis of Active Learning Algorithms using Real-World Crowd-sourced Text Annotations

Active learning algorithms automatically identify the most informative samples from large amounts of unlabeled data and tremendously reduce human annotation effort in inducing a machine learning model. In a conventional active learning setup, the labeling oracles are assumed to be infallible, that is, they always provide correct answers (in terms of class labels) to the queried unlabeled instances, which cannot be guaranteed in real-world applications. To this end, a body of research has focused on the development of active learning algorithms in the presence of imperfect / noisy oracles. Existing research on active learning with noisy oracles typically simulate the oracles using machine learning models; however, real-world situations are much more challenging, and using ML models to simulate the annotation patterns may not appropriately capture the nuances of real-world annotation challenges. In this research, we first collect annotations of text samples (from 3 benchmark text classification datasets) from crowd-sourced workers through a crowd-sourcing platform. We then conduct extensive empirical studies of 8 commonly used active learning techniques (in conjunction with deep neural networks) using the obtained annotations. Our analyses sheds light on the performance of these techniques under real-world challenges, where annotators can provide incorrect labels, and can also refuse to provide labels. We hope this research will provide valuable insights that will be useful for the deployment of deep active learning systems in real-world applications. The obtained annotations can be accessed at https://github.com/varuntotakura/al_rcta/.

Varun Totakura, Ankita Singh, Yushun Dong +1

Department of Computer Science Florida State University Tallahassee, FL, USA

Active Learning Annotations Independent-Pool Single-Draw Oracle Real-World

Feb 28, 2026cs.MA

The Alignment Flywheel: A Governance-Centric Hybrid MAS for Architecture-Agnostic Safety

Multi-agent systems provide mature abstractions for role decomposition, coordination, and normative governance, but increasingly capable learned components make post-deployment safety harder to inspect, audit, and update. When safety behavior is absorbed into a decision component, narrow failures may require retraining or rollback of the full component. This instantiates our vision of the Alignment Flywheel as a governance-centric hybrid MAS architecture that decouples decision generation from safety governance. We denote the agent or policy that generates candidate trajectories as the Proposer; it passes its output to a governed Safety Oracle stack, which returns safety scores, prediction uncertainty, audit coverage uncertainty, and evidence hooks through a stable interface. An Enforcement layer applies explicit risk policy at runtime. Around this loop, a governance MAS performs monitoring, red-teaming, verification, triage, refinement, and versioned release management. The central engineering principle is patch locality: many newly observed safety failures can be mitigated through small governance batches for the Oracle stack and its audit state rather than by retraining or retracting the Proposer. The architecture is implementation-agnostic with respect to both Proposer and Oracle. It defines the roles, artifacts, protocols, and release semantics needed for runtime gating, audit intake, signed updates, staged rollout, and rollback. We demonstrate executability in two scenarios: a learned spatial Oracle patched through regression-checked governance updates, and a clinical GenAI proxy setting illustrating structured norms, escalation, and audit coverage. Our implementation code and documentation are available open source at https://github.com/decide-ugent/Alignment-Flywheel.

Elias Malomgré, Pieter Simoens

IDLab, Ghent University - imec, Belgium

Governance Safety Claims Independent-Pool Single-Draw Oracle

Nov 17, 2025cs.LG

On the Gradient Complexity of Private Optimization with Private Oracles

We study the running time, in terms of first order oracle queries, of differentially private empirical/population risk minimization of Lipschitz convex losses. We first consider the setting where the loss is non-smooth and the optimizer interacts with a private proxy oracle, which sends only private messages about a minibatch of gradients. In this setting, we show that expected running time

Ω(\min\{\frac{\sqrt{d}}{α^2}, \frac{d}{\log(1/α)}\})

is necessary to achieve

α

excess risk on problems of dimension

d

when

d \geq 1/α^2

. Upper bounds via DP-SGD show these results are tight when

d>\tildeΩ(1/α^4)

. We further show our lower bound can be strengthened to

Ω(\min\{\frac{d}{\bar{m}α^2}, \frac{d}{\log(1/α)} \})

for algorithms which use minibatches of size at most

\bar{m} < \sqrt{d}

. We next consider smooth losses, where we relax the private oracle assumption and give lower bounds under only the condition that the optimizer is private. Here, we lower bound the expected number of first order oracle calls by

\tildeΩ\big(\frac{\sqrt{d}}α + \min\{\frac{1}{α^2}, n\}\big)

, where

n

is the size of the dataset. Modifications to existing algorithms show this bound is nearly tight. Compared to non-private lower bounds, our results show that differentially private optimizers pay a dimension dependent runtime penalty. Finally, as a natural extension of our proof technique, we show lower bounds in the non-smooth setting for optimizers interacting with information limited oracles. Specifically, if the proxy oracle transmits at most

Γ

-bits of information about the gradients in the minibatch, then

Ω\big(\min\{\frac{d}{α^2Γ}, \frac{d}{\log(1/α)}\}\big)

oracle calls are needed. This result shows fundamental limitations of gradient quantization techniques in optimization.

Michael Menart, Aleksandar Nikolov

Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto

First Order Oracle Complexity Convex Loss Stochastic Gradient Descent Independent-Pool Single-Draw Oracle Optimizer Design Oracles+1