CS Paper Radar

DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback

He Sun, Junyuan Mao, Wenhao Jiang, Mingjun Xiao, Shinan Liu

cs.LG cs.IT ·submitted 2026-10-09 03:59 UTC · v1
theory

Abstract

Matching repair after utility changes can reuse valid observations, but new evaluations must respect matching capacity and may return out of order. We study announced invalidations with bounded, possibly reward-dependent reporting delays and pending evaluations that do not occupy future matching capacity. Residualload repair (RLR) combines sound outcome certificates with batched matching schedules for unequal sample deficits. Its complete dyadic quota schedule admits a sharp issue-round bound with coefficient cb < 1.607 relative to the terminal residual endpoint load, together with separate delay and evidence-lifetime bounds. RLR-P monitors complete issue-order prefixes without changing the sampling plan before acceptance. With a deterministic pure oracle, a single-repair coupling from the same drained initial state guarantees no increase in certification time, issued observations, or time to a reusable checkpoint. We also derive an information-load lower bound. On fixed priority-star markets with unknown Bernoulli gaps, PrioritySearch attains the history-adjusted first-order constant for expected certification time as δ {\sim} 0, under hypothesis-independent linear history scaling and sublogarithmic reporting delays. Paired simulations and measured-feedback replay quantify the trade-offs: in the replay, RLR-P has lower mean capped update-certification time than a monitored width-based baseline, at higher oracle CPU cost.

Comment
2 figures, 8 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Before Agents Act: Assurance-Aware Semantic Scheduling for Evidence Acquisition in Distributed Systems

cs.DC cs.AIcs.CR ·2026-09-28 ·Jun He, Deying Yu
hot direction similarity 0.60
Abstract · 30 pages, 5 figures, 3 tables. Extended manuscript with formal proofs and operation catalogue

Tool-using agents can initiate consequential infrastructure changes, yet evidence required for admission may expire while other checks run or depend on a shared fault domain. We formulate evidence acquisition as joint witness selection and scheduling under quorum, diversity, freshness, deadline, and resource constraints. Assurance-Aware Semantic Scheduling (AAS) combines integer-program selection, dispatch-aware temporal scheduling, bounded diagnostic expansion, and receipt-aware repair. Formal results state the assumptions needed for dispatch-time freshness and finite diagnostic expansion. In three generated infrastructure workloads, AAS produces 1,075/1,200 valid candidates versus 647/1,200 for constraint-aware forward scheduling; stale candidates fall from 440 to 12. Paired sensitivity studies reuse the same instances and operation latency draws across parameter settings. A corrected timeout intervention finds 18/20 admissions with repair or full resynthesis versus 0/20 for a static plan, with lower committed cost when receipts are reused. On 20 constructed cases requiring a certified decomposition cut, refinement recovers an oracle-matching feasible plan every time. These are controlled simulation results; the bounded oracle shares a temporal search component, and transfer to deployed systems remains untested.

0.58

Fix, Not Just Resample: Bounded Compiler-Guided Repair in Lean 4

cs.AI ·2026-10-18 ·Haotian Deng, Chris Farber, Sonal Narasimha, Samskrithi Sivakumar, Yexiang Xue
benchmarktheory similarity 0.59
Abstract

Automated theorem provers often rely on sampling language models, but proof assistants like Lean reject each failed step with a precise error message --- information that pure sampling discards. To overcome this, we introduce a bounded, online step-level repair module. Our search samples $K$ candidate tactics at each step and repairs a failed tactic at most $R$ times. Instead of discarding failed tactics, we feed the compiler's error message to a pretrained repair model to fix individual rejected steps in place. This approach improves the solve rate over a sampling-only baseline across all tested candidate budgets ($K \in \{1,3,5,8\}$), achieving up to a $32\%$ relative gain and solving $82$ additional theorems on a $1{,}990$-theorem subset of the LeanDojo benchmark. Repair is not free: it trades extra runtime for reachable proofs. But the trade is predictable: repair pays most when sampling is constrained; its return is front-loaded, with the first repair attempt capturing $84\text{--}96\%$ of the total gain; and the gain comes almost entirely from shallow tactic-execution failures rather than structural errors such as type mismatches. This targeted repair successfully replicates on a second benchmark (Lean Workbook), nearly doubling the solve rate with zero regressions.

0.21

ERRAND: Budgeted Maintenance of Agent Memory

cs.AI ·2026-09-02 ·Beining Wu, Zihao Ding, Jun Huang
similarity 0.57
Abstract

Deployed agents run on handed-over knowledge: a frozen policy consults a briefing of consolidated items written before the stream begins. The world then moves while the store stands still: paths close, flags change, price bands move; every item was true at handover, and the failure is staleness, not ignorance. We introduce ERRAND, which treats revalidation as a priced errand: a recheck competes with the task it protects for the same scarce actions, funded only when the value per action of resolving a doubt clears a running wage. The errand index is single-peaked, vanishing at both ends of belief, so certainty in either direction costs nothing; free en-route receipts maintain on-path knowledge, and repair writes a version, never a deletion. Under equal action budgets in two drifting tool-use worlds, ERRAND clears every non-oracle policy on the preregistered calibers, primary in every setting and conditional at every binding budget, leading eager revalidation by 10.0pp at the base cap. Restraint wins: given no cap, ERRAND stops on its own, spending 11.0% of steps, while uncapped eager revalidation spends 70.7% and still finishes 4.5pp behind capped ERRAND. The margin sits where the briefing's coverage is thinnest, the shadow price of long-tail knowledge: a small budget, well priced, beats a bigger store that never rechecks.

0.51

Adaptive Decoding Methods for Token-Efficient Reinforcement Learning

cs.LG cs.AI ·2026-10-19 ·Zhaonan Li, Zelei Cheng, Amritansh Mishra, Chia-Hsuan Lee, Mann Patel +3 more
similarity 0.57
Abstract

Rollout decoding affects both which trajectories are used for reinforcement learning with verifiable rewards (RLVR) and how many completion tokens are spent collecting them. We study whether candidate-token support should remain fixed or widen during training in the context of rollout sampling efficiency. Our main schedule moves from top-K=10 to K=20 and then to full support as the attempted-token budget increases. In a 4B code-RLVR setting, the schedule has a higher interpolated 150M-token validation value than its matched fixed-K=10 continuation in all three runs, with a mean gain of $1.80{\pm}0.42$ points. The schedule also performs comparably to a separately trained fixed-K=20 baseline, the strongest fixed-support setting in our sweep. Follow-up experiments suggest that late widening to full support is the most promising variant, although the evidence remains noisy, and mixed-reward-group diagnostics do not clearly explain the gain. An exploratory single-run test replay yields identical point estimates for the schedule and fixed $K=10$. Overall, our results show that rollout support is an important control for sampling efficiency in RLVR and motivate further study of adaptive support schedules.

0.12

RCShift: Certifying When Partial Linkage Suffices for Finite-Sample Decisions

cs.AI ·2026-08-11 ·Shuheng Cao, Ruiqi Chen, Zhenhao Zhang, Renjie Cao, Siyu Zhang +3 more
similarity 0.57
Abstract

Systems with costly gold outcomes and cheaper auxiliary observations must decide how much record linkage to retain. Complete pairing retains every joint counter, while separate margins retain none. Neither endpoint is calibrated to a declared finite-sample decision. Universal reconstruction can retain cycle directions invisible to the likelihood-ratio family. Family-exact storage can exceed what the decision requires because certified residual loss may fit within finite-sample slack. We introduce RCShift, which certifies two routes to sufficiency under a declared observation contract. Its exact mode characterizes minimum-cost family-exact storage through LR-visible cycle directions. Its approximate mode bounds reverse Le Cam deficiency. Its integer mode certifies whether a chosen set preserves the full experiment's minimum integer record count at specified size and power. In a rank-two witness, one aligned counter preserves a four-record minimum. An equal-cost misaligned counter and the margins require eleven records, while universal reconstruction requires two counters. A local perturbation has positive reverse deficiency yet retains the four-record minimum. Proof-checked scheduling bounds instantiate the contract before gold computation and yield exact reconstruction on the admitted tree support. RCShift turns partial-linkage storage into decision-calibrated measurement design for the declared family, costs, target, and common strictly positive support.

0.04

Retaining Repair Hypotheses for Cost-Aware Execution

cs.AI ·2026-10-29 ·Jae Hun Hwang, Hong-In Won
similarity 0.57
Abstract · 17 pages, 5 figures; data and code in ancillary files

Several corrections of an executable model can fit the same observations while predicting different execution outcomes. We study a repair-to-execution interface that retains compatible finite guard repairs, conditions their weights on diagnostic and ordinary-execution observations, and uses their predictions to choose routes, priced tests, or a backup. On 24 synthetic two-stage devices, an equal mixture of a language-model-generated repair and a uniform belief over compatible repairs (the AI-weighted belief) lowers no-test cost by 2.14 percent relative to committing to the generated repair. Access charges can erase the benefit of diagnosis on isolated tasks, while repeated work can recover it under the AI-weighted belief. With normal-execution learning in every repeated-work arm, workload-valued testing costs 3.33 percent less than same-budget random selection under the AI-weighted belief. Weighting changes the comparison: uniform normal learning costs 540.75 less than AI-weighted normal learning on this cohort, with a device-paired interval excluding zero. Testing recovers part of that gap, but uniform normal learning still has a lower aggregate cost than AI-weighted workload-valued selection. Under uniform beliefs, information-gain selection has the lowest total among the compared selectors, while workload-valued testing costs more than normal learning. These results support retaining alternatives to a generated repair and evaluating diagnostic selection together with repair weighting and learning from execution.

0.30

What Do RTL Repair Benchmarks Actually Measure?

cs.AI ·2026-10-20 ·Yeyin Eva Zhu, Rishabh Ranawat
benchmarkdatasetcode/data similarity 0.56
Abstract

RTL repair benchmarks should measure whether a model can fix broken RTL given a specification. To this end, we construct and hash-bind RTLRepairDataset, 5,784 (broken, fixed) training pairs; RTLRepairBench, 459 held-out cases with 374 syntactic and 85 behavioral mutations; and an evaluation harness supporting simulation and formal equivalence. We then use this infrastructure to identify two measurement confounds. First, simulation and formal scoring give opposite signs for the apparent effect of providing a specification in one evaluated cohort; reset-aware rescoring attributes almost all of the simulation-formal disagreement to reset and first-cycle comparison semantics. Second, on 274 mined model failures, the specification-only minus specification-conditioned recovery point estimate ranges from -8.5 to +18.3 percentage points across six models. Thus, a conventional repair score need not isolate whether the model used the faulty RTL. We translate these findings into evaluation controls: report initialization, reset, first-cycle, and unknown-value semantics; disclose oracle coverage and undecided cases; and include a specification-only baseline. Together, the resources and audit provide both a benchmark for behavioral repair and a protocol for diagnosing what contributes to its measured score. We release the benchmark, the training set, construction code, sanitized aggregate evidence, and reproduction materials at https://github.com/Evaaaz/RTLRepairBench.

0.46

Trigger Timing, Deadline Readiness, and Event-Aligned Accounting for Dynamic Ad Insertion

cs.MM cs.NIcs.PF ·2026-09-17 ·Prashant Chaudhary, Kapil Khandelwal
theory similarity 0.56
Abstract · 16 pages, 2 figures, 5 tables; 11-page supplement in ancillary files. Code and data: https://doi.org/10.5281/zenodo.22774143. v2: rewritten …

An ad break in a live stream is a hard deadline. Once a cue arrives, the ad path has seconds to produce a state the player can use, and starting that work earlier buys time while giving the prepared state longer to expire before the break. Comparing trigger policies means scoring which of these happened; the records easiest to collect do not. We separate trigger, reach, readiness, playback, billability and measurement in an observed-event ledger, fix the reference-deadline rule before candidates are assigned, and account for contribution over every planned break-session pair, reached or not. Readiness means the declared state is valid at that deadline. We prove when scoring completion by the deadline instead reverses a policy comparison: for monotone playback with a shared latency law, a fixed state lifetime and common coefficients, the reversal occurs when the earlier policy's extra trigger cost falls between its validity gain and its completion gain. A synthetic study of 45,000 scripted sessions matches this condition on monotone paths, a check of its generator, and, outside its assumptions, finds the same reversal in mixtures with restarts, seeks, late joins and pauses. Playhead summaries misclassify up to 41% of reach indicators yet reverse no comparison in the study: maximum-position errors cancel exactly, and terminal-position errors change only magnitudes. Completion scoring reverses the comparison in three of nine short-lifetime conditions, all at the one latency setting where the proved condition holds. The evidence is synthetic by design; code, seeds and event histories are public.

0.40