Trusted Bits Against Backdoored Advice

Many online algorithms make irrevocable decisions (evict this page, accept this item, move to this state) and now take hints from a learned predictor. The standard guarantee is double-sided. When the hints are good, the algorithm nearly matches the clairvoyant optimum. When they are bad, it falls back to its classical worst-case bound. A backdoored predictor breaks the assumption behind the first half of that guarantee. A backdoor is a hidden behavior planted during training that stays dormant until a specific input pattern, the trigger, appears. Such a predictor is almost perfect on nearly every request and badly wrong on the few requests the attacker chooses. Current theory measures prediction quality as total error. A handful of large, targeted errors can make that total comparable to the optimum's cost, so the algorithm keeps its worst-case safety net but loses its entire advantage from learning. The attacker pays for this with only a few triggered requests.

This note asks a question in the language of advice complexity, the study of how many bits of information about the future an online algorithm needs to reach a given performance. Suppose the untrusted predictor can be wrong on at most $s$ of $m$ requests. How many trusted bits, each obtained from a costly audit that checks whether one prediction is correct, are necessary and sufficient to recover near-perfect performance? The claim is that the answer scales with the number of corrupted steps, roughly $s\log(m/s)$, and not with the sequence length. The claim also has an algorithmic side: that budget can be spent well by auditing only the predictions whose acceptance would be expensive to undo. We will prove this for caching and online knapsack and test it against real backdoored predictors on the caching traces the learning-augmented literature already uses.

Core Claim

Existing robust algorithms already survive backdoors in the worst-case sense. The meta-algorithm of Online metric algorithms with untrusted predictions switches between following predictions and a robust fallback and guarantees $9\cdot\min\{\alpha, 1+4\eta/\mathrm{OFF}\}$. Here $\alpha$ is the fallback's competitive ratio, $\eta$ is the summed distance between predicted and optimal states, and $\mathrm{OFF}$ is the offline optimum's cost. We do not claim these algorithms become unsafe under attack. The problem is that $\eta$ counts magnitude. One trigger that sends the predicted state across the metric can contribute as much to $\eta$ as thousands of small errors. The bound, and the empirical behavior we expect, therefore slides toward $\alpha$ after only $s$ triggered steps.

We replace magnitude with a sparse-corruption model that matches how backdoors behave. The predictor is exact on all but a set $S$ of at most $s$ steps and arbitrary on $S$. The online algorithm may also request trusted verification bits, each revealing whether the current prediction is correct. A counting argument gives the target lower bound. An algorithm must effectively learn which $s$ of the $m$ steps are corrupted, and specifying such a set takes $$\log_2\binom{m}{s} \approx s\log_2(m/s)$$ bits. We conjecture this is tight up to constants for caching: with $O(s\log(m/s))$ trusted bits, the ratio is $1+O(s/\mathrm{OFF})$. With $o(s\log(m/s))$ bits, some sequence forces the ratio toward the unaugmented bound. The same structure should hold for unit-profit knapsack, where a corrupted prediction of the optimum's average item size is a single-shot corruption with $s=1$.

The mechanism behind the upper bound is stake-aware auditing. At each step the algorithm compares the action the prediction recommends with the action the robust fallback would take. It audits only when the cost of later reversing the recommended action exceeds a threshold. An attacker who wants to cause damage must corrupt high-stake steps, because a corrupted low-stake step costs the algorithm little by definition. The audit budget is therefore spent where the attacker has to be.

Research Program

The theoretical program has three parts. First, we will formalize the model: an online problem, an untrusted predictor with corruption set $S$ of size at most $s$ chosen adaptively by the attacker, and a trusted verification channel priced at $c$ per bit. The pricing follows the costly-query model of Online Algorithms with Costly Predictions, which charges a fixed fee per predictor query in ski rental and the Bahncard problem. We differ in that the costly resource is verification of a free but possibly poisoned prediction, not the prediction itself. Second, we will prove the counting lower bound for paging and for knapsack. The construction adapts the symmetric-fork arguments behind On the List Update Problem with Advice, which shows that two advice bits beat the deterministic barrier of 2 while nearing optimality needs linear advice. Our analogue says that beating the fallback needs few trusted bits only when corruption is sparse. Third, we will analyze stake-aware auditing on top of two known algorithms. For caching the base is TRUST&DOUBT from Online metric algorithms with untrusted predictions, which demotes mispredicting pages to a doubted set with logarithmic dependence on error. For knapsack the base is ATup from Online Unit Profit Knapsack with Untrusted Predictions, which degrades as $r/2$ or $1/(2r)$ in the ratio $r$ of true to predicted average size.

Two papers constrain the design. Parsimonious Learning-Augmented Caching queries predictions only on misses for $b$ sampled pages and falls back to randomized marking when eviction chains exceed $\log k$. That reset is exactly what a single triggered page can provoke on purpose, so query parsimony alone is not protection. The same paper also notes that weighted caching resists the state-prediction approach, so we restrict claims to unweighted paging and unit-profit knapsack.

The empirical program builds real backdoored predictors instead of synthetic noise. For caching, we will train a neural next-arrival predictor on request traces and poison it BadNets-style. The trigger is a rare pattern in the request context, and the target behavior is to predict "never again" for chosen pages, which induces eviction, or "immediately", which pins a page in cache. Evidence that dormant triggered subnetworks leave clean accuracy intact comes from Fine-Pruning: Defending Against Backdooring Attacks on Deep Neural Networks. Attack construction will reuse the modular implementations in SCLBD/BackdoorBench, adapted from images to sequence features.

The trusted audit has two instantiations. The idealized one reveals the true next arrival from the offline trace, and it is used to check the theory. The practical one is a detector: a STRIP-style perturbation-entropy test, following STRIP: A Defence Against Trojan Attacks on Deep Neural Networks, or multi-exit side networks in the manner of Orion: Online Backdoor Sample Detection via Evolution Deviance, attached to our predictor. Each practical audit is charged its measured compute cost and scored with its measured error rate.

Baselines

The naive reference points are pure LRU and randomized marking, which ignore the predictor, and blind follow-the-prediction, which evicts the page predicted furthest in the future with no safeguard. These bracket the space: no learning benefit and no attack exposure on one side, full benefit and full exposure on the other.

The strongest existing method is TRUST&DOUBT, because it already demotes mispredicting pages adaptively. On CitiBike and BrightKite it reported "competitive ratios near 1.2–1.3 on real data" with benign predictions, outperforming LRU and earlier prediction-augmented methods (Online metric algorithms with untrusted predictions). No reported result was found on Lacuna for any learning-augmented caching algorithm driven by a backdoored predictor, so we will measure TRUST&DOUBT's attacked ratio ourselves. For parsimony, the reference is AdaptiveQuery-8, which matched full-prediction algorithms while "querying predictions for only about 11% of the total requests" on CitiBike 2018 (Parsimonious Learning-Augmented Caching). For knapsack the reference is ATup.

For fairness, every method receives the same traces, cache sizes ($k=100$ for CitiBike and $k=10$ for BrightKite, following the prior papers), the same predictor weights, and the same attacker, who chooses $s$ triggered requests with knowledge of the defense. Any audit-using baseline receives exactly the same audit budget, counted in bits or in measured audit compute. We fix thresholds on held-out clean traces and give every method an identical hyperparameter search budget.

The key ablation is uniform random auditing at the same budget as stake-aware auditing. It isolates whether targeting high-stake steps matters, as opposed to simply having trusted bits. Beating the baselines means holding the ratio within a few percent of the clean-prediction ratio while TRUST&DOUBT and AdaptiveQuery-8 drift toward LRU or marking, at an audit count well below the per-request detector baseline.

Why not just…?

Why not just trust the existing robust algorithms? They remain safe in the worst case. Our concern is that their benefit from the predictor evaporates after a few triggers, because the ratio $9\cdot\min\{\alpha, 1+4\eta/\mathrm{OFF}\}$ charges error by magnitude, and a backdoor concentrates large magnitude in a few steps. This is an empirical question. The first experiment sweeps $s$ and plots TRUST&DOUBT's ratio. If that ratio stays near 1.2–1.3 under strong attacks, the threat is weaker than we believe and the proposal shrinks to its theoretical lower-bound part.

Why not just run STRIP or Orion on every prediction? This per-request audit is the real competitor, and we include it at full budget. Its cost is concrete. STRIP reports 1.32x inference latency and needs clean blending samples. Orion adds 1.7ms per sample on VGG16, needs about 1% clean data, and recovers labels 80% of the time. Paying this on every cache request is exactly the linear-advice regime our lower bound says is unnecessary under sparse corruption. The experiment reports ratio against audit spend for both methods. If always-on auditing is cheap enough in a given setting to be affordable, we will say so.

Why not just cross-check against a second, independently trained predictor and audit on disagreement? This is a serious alternative. When only one model is compromised, for example a supply-chain backdoor, disagreement may catch triggers almost for free. It fails when both models learn from the same poisoned data. We will run both regimes: separate poisoned checkpoints, and shared poisoned training data. We will also treat disagreement as a cheap pre-filter inside stake-aware auditing, not only as a rival. The regime where it suffices alone will be reported plainly.

Why not just purify the predictor offline? BackdoorBench: A Comprehensive Benchmark of Backdoor Learning documents that defenses are fragile across architectures and that clean accuracy drops, which lowers consistency on every clean step. We will nonetheless include a fine-pruned predictor as a baseline. Our method composes with purification, since audits cover whatever the purification missed.

Proposed Experiments

The decisive checks are four. First, we measure the attacked ratio of TRUST&DOUBT, AdaptiveQuery-8, and ATup as the number of triggered requests $s$ grows, on CitiBike, BrightKite, and synthetic knapsack streams. This establishes whether sparse triggers erase the learning benefit. Second, with the idealized audit, we trace the minimum audit budget needed to reach within 5% of the clean ratio as a function of $s$ and $m$, and check the predicted $s\log(m/s)$ shape. That shape follows from the counting bound. Third, we compare stake-aware auditing against uniform auditing at equal budgets. If the two perform alike, the stake mechanism is not doing the work, and we would report the result as a pure advice-complexity bound. Fourth, we run an adaptive attacker who spreads triggers across low-stake steps to evade audits. The theory predicts that this attacker gains little, because low-stake corruption is cheap to absorb, and a measurable gain for the attacker would falsify the design.

Throughout, the practical audits (STRIP-style and side-network detectors) are charged their measured cost and false-rejection rates, so the final curves show competitive ratio against real audit spend, not idealized bits.