5arXiv cs.CL (Computation and Language)·
Certify-then-Rectify framework adds accuracy guarantees to HNSW approximate nearest neighbor search
A new arXiv technical report proposes a 'Certify-then-Rectify' framework that augments HNSW approximate nearest neighbor search with formal accuracy guarantees. The approach uses a distribution-free statistical certifier to assess search quality at runtime, escalating to exact retrieval only when needed, and reinterprets the HNSW graph as a geometric spanner to bound worst-case distances via Extreme Value Theory. Evaluations on benchmark datasets show the method preserves HNSW's average-case speed while guaranteeing worst-case correctness, outperforming comparable approaches.
Related guides (2)
Related events (8)
Structural certification framework for general agents in the big-world regime
A new arXiv preprint introduces 'structural certification,' a transition-local framework for formally bounding the reliability of general agents in environments too large for universal competence. The authors prove that general agents cannot be universal, making standard worst-case guarantees uninformative, and then provide algorithms that filter transitions via deep compositional goals to produce entry-wise error bounds of O(1/n) + O(δ) on an agent's internal world model. The work aims to enable certifiable deployment of general agents by identifying specific transitions where long-horizon planning is provably reliable.
SIFT and WSP: Claim-conditioned re-scoring to close the warrant gap in LLM fact-checking
A new arXiv preprint identifies a 'warrant gap' in LLM-based fact-checking systems: models frequently output Supports verdicts whose cited evidence does not actually entail the claim. The authors introduce SIFT, a claim-conditioned re-scoring method for extracted evidence spans, and WSP (Warranted Supports Proportion), an automatic NLI-based metric that checks whether cited warrants entail the claim. Evaluated on FEVER, SciFact, 5PILS, and DP across four open-source backbones, SIFT recovers up to 27.6 accuracy points lost by naive decomposition, while WSP calibrates against human gold evidence at AUC 0.92 and precision 0.98.
Online Safety Monitoring for LLMs via Threshold-Based Risk Control
A new arXiv preprint proposes a real-time safety monitor for LLMs that converts an external verifier signal into an alarm by thresholding, with the threshold calibrated via risk control. The authors evaluate the approach on mathematical reasoning and red-teaming datasets, finding it competitive with more complex sequential hypothesis testing monitors. The work addresses the practical deployment problem of detecting unsafe outputs after alignment training.
New CDF-based estimators for Sliced-Wasserstein distance enable federated and parallel computation
A new arXiv preprint introduces a class of estimators for the Sliced-Wasserstein (SW) distance that use cumulative distribution functions (CDFs) of projected measures rather than sorting-based quantile functions. The estimators avoid sorting, scale via massive dataset parallelism, and are naturally compatible with federated learning since local CDFs can be aggregated without sharing raw samples. The work also shows advantages for mixture-of-Gaussians settings where CDFs are more tractable than quantile functions.
The Matching Principle: A Geometric Theory Unifying Robustness, Domain Adaptation, and Alignment via Nuisance Covariance
This paper proposes the 'matching principle': a unified geometric framework arguing that robustness methods (CORAL, IRM, adversarial training, augmentation, metric learning, Jacobian penalties, alignment constraints) are all estimators of the same object—the covariance of label-preserving deployment nuisance—and that regularizing the encoder Jacobian along this covariance's range is the core statistical problem. The authors prove closed-form optimality results in a linear-Gaussian model, introduce the Trajectory Deviation Index (TDI) as a label-free embedding sensitivity probe, and validate predictions across 13 pre-registered experimental blocks including Qwen2.5-7B. At 7B scale, matched style-PMH improves selective honesty while standard DPO degrades Style TDI, connecting the theory to alignment safety.
LLM-as-a-Verifier: Training-free verification framework scales along granularity, repetition, and criteria decomposition
Researchers introduce LLM-as-a-Verifier, a general-purpose verification framework that treats verification as a new scaling axis for LLMs, computing continuous scores from token logit distributions rather than discrete judge outputs. The framework scales along three dimensions—score granularity, repeated evaluation, and criteria decomposition—and achieves state-of-the-art results on Terminal-Bench V2 (86.5%), SWE-Bench Verified (78.2%), RoboRewardBench (87.4%), and MedAgentBench (73.3%) without requiring additional training. The authors also demonstrate that the framework's fine-grained signals can serve as dense RL feedback, improving sample efficiency for SAC and GRPO on robotics and math benchmarks, and build a Claude Code extension for monitoring agentic systems.
HKVM-RAG: Hypergraph key-value separation improves multi-hop retrieval-augmented generation
A new arXiv preprint introduces HKVM-RAG, an evidence-organization layer for multi-hop RAG that uses weighted hyperedges as retrieval keys while retaining passage text as answer values. Under a fixed-substrate protocol controlling for tuple cache, reader, and evaluation budget, the hypergraph key-value approach improves over KG-PPR by +3.4 F1 on 2WikiMultiHopQA and +3.6 F1 on MuSiQue. A dense-aware controller combining frozen ColBERTv2 with HKVM features reaches 88.8, 65.1, and 85.8 F1 on three benchmarks, outperforming ColBERTv2 alone by 5–11 F1 points. The work positions hypergraph organization as a reusable evidence-control mechanism rather than a dense-retrieval replacement.
Framework for quantifying faithful confidence expression in large reasoning models
A new arXiv preprint introduces a framework to measure faithful calibration (FC) in large reasoning models (LRMs)—the alignment between a model's intrinsic confidence and its linguistically expressed confidence. The authors analyze linguistic decisiveness against three internal uncertainty sources (token probabilities, hidden states, sampled response consistency) and introduce prefix-conditioned sampling to handle structural variation in chain-of-thought traces. Applying the framework across leading models, they find FC is a significant and distinct failure mode for LRMs: extended reasoning traces do not automatically improve calibration, prompt interventions that help non-reasoning models fail in the reasoning setting, and different confidence estimators produce divergent assessments of the same traces.