Resilient Byzantine Agreement with Predictions

• URL: http://arxiv.org/abs/2605.19452v1
• Date: Tue, 19 May 2026 07:06:50 GMT
• Title: Resilient Byzantine Agreement with Predictions
• Abstract summary: We study the Byzantine Agreement problem where the nodes have access to a predictor that flags nodes for suspicion of faulty behavior.<n>We focus on algorithmic resilience -- the maximum number of faulty nodes an algorithm can tolerate.<n>We show that resilience linearly decreases in the number of wrong predictions as long as that number stays within a constant fraction of $n$.
• Score: 4.2331787771494875
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the Byzantine Agreement problem where the nodes have access to a predictor that flags nodes for suspicion of faulty (Byzantine) behavior. We focus on algorithmic resilience -- the maximum number of faulty nodes an algorithm can tolerate -- and present algorithms and impossibility results whose resilience depend on the accuracy of the predictor. As our first main result, we bring a complete characterization of the consistency--robustness trade-offs in both the non-authenticated and authenticated settings: for $n$ nodes and a parameter $α\in [0, 1]$, we present algorithms that tolerate up to $α\cdot n$ faulty nodes when the predictor is correct (consistency), and up to $\frac{1-α}{2} \cdot n - 1$ faulty nodes when the predictor is arbitrarily wrong (robustness); in the authenticated setting the robustness bound improves to $(1-α) \cdot n - 1$. These trade-offs are exactly tight as we show that one additional faulty node renders the problem impossible. Our second main result characterizes smoothness: the rate at which resilience degrades as the predictor becomes less accurate. We show that resilience linearly decreases in the number of wrong predictions as long as that number stays within a constant fraction of $n$. Concretely, in the non-authenticated setting each additional wrong prediction loses one unit of resilience, whereas in the authenticated setting the decline is halved since two wrong predictions are needed to lose one unit of resilience.

Related papers

• $TCP_α$: Margin-Controlled Confidence estimation for reliable Music Information Retrieval [7.679660052685777]
  Deep neural networks are often overconfident, assigning high confidence even to incorrect predictions.<n>Existing targets suffer from inherent ambiguity: they assign overlapping confidence values to correct and incorrect predictions, while errors near the decision boundary receive confidence scores indistinguishable from correct predictions.<n>We propose $ TCP_$, a novel confidence target that resolves these limitations by introducing a margin-controlled penalty for misclassified samples.
  arXiv  Detail & Related papers  (2026-08-20T17:58:50Z)
• CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees [1.7545090618311434]
  Machine-learned predictions can speed up offline NP-hard optimization, but asking a predictor what to do amounts to asking it to solve the problem.<n> CASP (Certificate-Augmented Solution Pruning) instead asks which parts of the search space may be ignored, and accepts each answer only after a sound-time verifier has checked it.<n>With trained predictors, unverified pruning loses up to $26%$ of the optimum under distribution shift, while the verified deployment of the same predictions loses nothing.
  arXiv  Detail & Related papers  (2026-07-16T04:02:15Z)
• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  We investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner.<n>The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm.<n>We establish an information-theoretic lower bound that scales as $(sqrtmathbbE[S_T])$, providing a fundamental characterization of the best achievable prediction-adaptive regret.
  arXiv  Detail & Related papers  (2026-05-21T08:57:38Z)
• Fundamental Novel Consistency Theory: $H$-Consistency Bounds [19.493449206135296]
  In machine learning, the loss functions optimized during training often differ from the target loss that defines task performance.<n>We present an in-depth study of the target loss estimation error relative to the surrogate loss estimation error.<n>Our analysis leads to $H$-consistency bounds, which are guarantees accounting for the hypothesis set $H$.
  arXiv  Detail & Related papers  (2025-12-28T11:02:20Z)
• Beyond Greedy Exits: Improved Early Exit Decisions for Risk Control and Reliability [14.00844847268286]
  Early-Exit Deep Neural Networks enable adaptive inference by allowing prediction at intermediary layers.<n>Our framework demonstrates consistent improvements in speedup (1.70-2.10x) with a minimal performance drop (2%) as compared to full model performance.
  arXiv  Detail & Related papers  (2025-09-28T06:05:24Z)
• Uncertainty-Aware Graph Neural Networks: A Multi-Hop Evidence Fusion Approach [55.43914153271912]
  Graph neural networks (GNNs) excel in graph representation learning by integrating graph structure and node features.<n>Existing GNNs fail to account for the uncertainty of class probabilities that vary with the depth of the model, leading to unreliable and risky predictions in real-world scenarios.<n>We propose a novel Evidence Fusing Graph Neural Network (EFGNN for short) to achieve trustworthy prediction, enhance node classification accuracy, and make explicit the risk of wrong predictions.
  arXiv  Detail & Related papers  (2025-06-16T03:59:38Z)
• Adversarial Robustness of Nonparametric Regression [13.139603473712425]
  We characterize the adversarial robustness in nonparametric regression, assuming the regression function belongs to the second-order Sobolev space.<n>We show that, perhaps surprisingly, the classical smoothing spline estimator, when properly regularized, exhibits robustness against adversarial corruption.
  arXiv  Detail & Related papers  (2025-05-23T00:18:20Z)
• Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification [50.717692060500696]
  Next-token prediction with the logarithmic loss is a cornerstone of autoregressive sequence modeling.<n>Next-token prediction can be made robust so as to achieve $C=tilde O(H)$, representing moderate error amplification.<n>No computationally efficient algorithm can achieve sub-polynomial approximation factor $C=e(log H)1-Omega(1)$.
  arXiv  Detail & Related papers  (2025-02-18T02:52:00Z)
• Collective Robustness Certificates: Exploiting Interdependence in Graph Neural Networks [71.78900818931847]
  In tasks like node classification, image segmentation, and named-entity recognition we have a classifier that simultaneously outputs multiple predictions. Existing adversarial robustness certificates consider each prediction independently and are thus overly pessimistic for such tasks. We propose the first collective robustness certificate which computes the number of predictions that are simultaneously guaranteed to remain stable under perturbation.
  arXiv  Detail & Related papers  (2023-02-06T14:46:51Z)
• Learning to Predict Trustworthiness with Steep Slope Loss [69.40817968905495]
  We study the problem of predicting trustworthiness on real-world large-scale datasets. We observe that the trustworthiness predictors trained with prior-art loss functions are prone to view both correct predictions and incorrect predictions to be trustworthy. We propose a novel steep slope loss to separate the features w.r.t. correct predictions from the ones w.r.t. incorrect predictions by two slide-like curves that oppose each other.
  arXiv  Detail & Related papers  (2021-09-30T19:19:09Z)
• Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations [78.23408201652984]
  Top-k predictions are used in many real-world applications such as machine learning as a service, recommender systems, and web searches. Our work is based on randomized smoothing, which builds a provably robust classifier via randomizing an input. For instance, our method can build a classifier that achieves a certified top-3 accuracy of 69.2% on ImageNet when an attacker can arbitrarily perturb 5 pixels of a testing image.
  arXiv  Detail & Related papers  (2020-11-15T21:34:44Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  We propose a weaker assumption that we call $2$-adjacency faithfulness. We propose a sound orientation rule for causal discovery that applies under weaker assumptions.
  arXiv  Detail & Related papers  (2020-10-27T13:04:08Z)
• Revisiting One-vs-All Classifiers for Predictive Uncertainty and Out-of-Distribution Detection in Neural Networks [22.34227625637843]
  We investigate how the parametrization of the probabilities in discriminative classifiers affects the uncertainty estimates. We show that one-vs-all formulations can improve calibration on image classification tasks.
  arXiv  Detail & Related papers  (2020-07-10T01:55:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.