Token-Efficient Change Detection in LLM APIs

AI summary

Overview

Research area: Machine learning, specifically the security and reliability of LLM inference APIs — statistical change detection, hypothesis testing, and black-box model monitoring.

Technical level: Advanced. The paper builds on Local Asymptotic Normality (LAN) theory, Fisher information, Jacobian decompositions of the softmax head, and Neyman–Pearson optimal testing, though the resulting method itself is simple enough to describe in a paragraph.

Scope (one sentence): The paper proposes B3IT, a strictly black-box method that finds low-temperature "Border Inputs" — prompts whose top logit is tied — and uses the collapse of their output distribution as a cheap, sensitive signal that a served LLM has been modified.

What This Paper Is About

Users of LLM APIs have no guarantee that the model behind an endpoint stays the same: providers may quietly swap in quantized, fine-tuned, or differently prompted models, or suffer infrastructure bugs, without notifying anyone. Existing detection methods force a trade-off — white-box methods need model weights, grey-box methods need log-probabilities (available on only a fraction of public endpoints), and fully black-box methods like MET need so many queries that continuous monitoring becomes prohibitively expensive. The goal of this paper is to achieve both low cost and strict black-box operation, observing only the output tokens returned by the API.

Key Contributions

1. Theoretical foundations for change detection in LLMs. The authors characterize the difficulty of detecting a small parameter perturbation θ ↦ θ + εh through a single scalar, SNR²(h) = hᵀ(JᵀF(p₀)⁻¹J)h, where J is the Jacobian of the output distribution and F is the Fisher information matrix. They simplify this for transformer LLMs by exploiting the last linear layer, and prove a phase transition: as temperature τ → 0, SNR²(h) → 0 when one logit is maximal (k = 1), but SNR²(h) → +∞ when at least two logits are tied (k ≥ 2).

2. The B3IT method (Black-Box Border Input Tracking). A two-stage scheme that (i) discovers "Border Inputs" by black-box sampling at minimum temperature and (ii) monitors for change by comparing output token supports against a reference distribution.

3. In vitro validation on TinyChange. B3IT achieves detection performance comparable to the grey-box LT baseline at 1/30th the cost of the next-best black-box baselines, evaluated across 9 instruction-tuned models from 0.5B to 9B parameters under fine-tuning, pruning, and parameter-noise perturbations.

4. In vivo validation on 131 live endpoints (78 models, 34 providers). Demonstrates broad applicability for continuous, cost-effective API monitoring, plus nonasymptotic Type-I/Type-II error guarantees and a matching lower bound showing the test is optimal up to a constant factor when k = 2.

Main Findings

• A phase transition governs detectability. At low temperature, if the output distribution collapses to a single token (k = 1), SNR²(h) → 0 and detection becomes nearly impossible; if at least two logits are tied (k ≥ 2), SNR²(h) diverges and detectability is maximal. The condition hᵀ(J_zᵀΣ_M J_z)h ≠ 0 holds for almost every direction h, so the divergence is obtained regardless of the model's weights — which is what enables a black-box approach.

• Border Inputs are abundant in practice. Despite exact logit ties having probability zero in theory, ties are observed frequently, attributed to limited floating-point precision and inference-time non-determinism. On 131 endpoints at T = 0, coverage of endpoints with at least one BI rose from 73% (1k prompts) to 76% (2k prompts) using the cheap strategies; adding reasoning-budget queries brought coverage to 78%.

• B3IT beats black-box baselines and approaches grey-box performance. At the selected operating point ($2.2/year), B3IT reaches a ROC AUC of 0.9, whereas the next-best black-box method (MET at T = 0) reaches only 0.61. No black-box baseline reaches ROC AUC 0.9; the closest, MET at T = 0, requires $67/year to reach 0.88.

• Strong performance on hard, tiny changes. B3IT retains a ROC AUC of 0.87 for detecting the extreme single-step fine-tuning case on the TinyChange fine-tuning difficulty scale. MMLU-ALG, and to a lesser extent MET, exhibit low detection accuracy.

• Spreading queries across prompts beats concentrating them. At fixed cost, sampling 5 prompts 10 times outperforms sampling a single prompt 50 times. The authors select 5 prompts with 3 samples each.

• Initialization is cheap. With m = 3 samples per candidate prompt — identified by a back-of-the-envelope analysis as optimal if less than 75% of candidates are BIs — BIs can be discovered for fewer than 1,500 requests on a majority of production APIs. Per-endpoint, initialization cost $0.0045, negligible versus ongoing detection.

• Hourly monitoring is cheap in the field. At an average (input, output) endpoint cost of ($0.38, $1.2) per million tokens, hourly monitoring averaged $0.52 per endpoint per year.

• Border Inputs generalize across providers but not across models. A Cochran-Mantel-Haenszel analysis gives an odds ratio of 2.40 for BIs shared across endpoints serving the same model from different providers, versus 1.07 across endpoints serving different models.

• Persistent changes were detected in the wild. Using a mean total-variation threshold of 0.5 (the bimodal-to-unimodal transition point), sustained below for at least 4 days and then above for an equal period, 8 endpoints out of the 53 monitored were flagged. One is corroborated by Together AI's public changelog, which on January 29 redirected Mistral-7B-Instruct-v0.3 to the entirely different Ministral-3-14B-Instruct-2512.

• A documented failure mode. For two endpoints (gpt-oss-20b and gpt-oss-120b on amazon-bedrock), strategy discovery fails because the reasoning trace is hidden from the API response, so the first output token cannot be observed.

• T = 0 behavior is not always the T → 0 limit. Many endpoints appear to behave differently at T = 0 than their limit as T → 0 would indicate, which the authors hypothesize is due to hard-coded patterns at T = 0.

Methodology in Plain English

The researchers start from a statistical question: if a model's parameters shift slightly, how hard is it to tell, given only samples of its output tokens? Writing the parameters as θ + εh and working in the local regime where the perturbation shrinks at the critical rate, they show the answer depends on a signal-to-noise ratio built from two quantities — how much the output distribution moves when parameters move (the Jacobian, the signal), and how noisy the sampling is (the Fisher information, the noise). For an LLM, the softmax head lets them rewrite this quantity in terms of the logits and the sampling temperature. That rewriting yields the key result: drive the temperature toward zero and the situation splits in two. If one token dominates, sensitivity vanishes. If two or more tokens are tied at the top, sensitivity diverges, so even arbitrarily small changes flip the model between behaving unimodally and multimodally.

That gives a practical recipe. Initialization: submit many short random prompts at the lowest available temperature, sample each a few times (m = 3), and keep the prompts that return more than one distinct output — these are the Border Inputs, and their initial distribution is estimated by repeated sampling. Detection: re-sample the same Border Inputs at minimum temperature and compare. Because the distribution concentrates on a small support at low temperature, the comparison reduces to checking whether the set of observed tokens matches — a support-mismatch test that rejects when a token seen under one model never appears under the other. The authors derive nonasymptotic Type-I and Type-II error bounds for this test, and a lower bound showing that when the support has size 2 and the candidate collapses to a singleton, no test can do better than a constant factor.

Experimentally they validate in two ways: in vitro on the TinyChange benchmark, which generates controlled perturbations (fine-tuning for 1 epoch with 1 to 4096 single-sample steps, LoRA variants, magnitude and random pruning removing fractions from 2⁻²⁰ to 1, and Gaussian parameter noise with σ ∈ [2⁻³⁰, 1]) of 9 open-weight instruction-tuned models; and in vivo on live commercial APIs selected from OpenRouter under cost and prompt-format filters. Since the theory yields a binary test but ROC curves need a tunable threshold, they use total variation distance between reference and detection samples as a continuous statistic, averaging across prompts.

Why This Matters

Impact on research. The paper reframes LLM change detection as a local asymptotic testing problem and derives a sharp phase transition that no generic multinomial testing result provides. It shows that the temperature knob — usually treated as a user-facing sampling parameter — is actually the control that determines whether detection is possible at all, and it establishes optimality (up to a constant) for the practical k = 2 regime with matching upper and lower bounds.

Real-world applications.

• Continuous API monitoring for enterprises: hourly verification that a critical endpoint has not silently changed, at $0.52 per endpoint per year.
• Detecting silent model swaps: the confirmed Mistral-7B-Instruct-v0.3 → Ministral-3-14B-Instruct-2512 redirect shows that provider-side substitution is real, not hypothetical.
• Quantization and cost-optimization auditing: catching quietly deployed quantized variants that could degrade quality on tasks users depend on.
• Safety and compliance checks: verifying that a model's behavior has not drifted due to safety updates, system prompt changes, or misrouted requests.

Industry relevance. The incidents cited — Grok on X suffering three 2025 incidents from modified system prompts deployed by rogue employees or bad updates, and Anthropic's 2025 infrastructure bugs that degraded Claude responses for weeks while affecting 16% of Claude Sonnet 4 requests at peak — illustrate that unnoticed changes already happen at scale. A strictly black-box method matters commercially because it works on the endpoints actually available to customers, and its 30× cost reduction over prior methods is what makes always-on monitoring economically viable rather than a spot check.

Future Directions

• Handling endpoints that hide their reasoning trace. The method fails on gpt-oss-20b and gpt-oss-120b on amazon-bedrock because the first output token is not exposed; a workaround would extend coverage.
• Explaining and handling the T = 0 anomaly. Many endpoints behave differently at T = 0 than the T → 0 limit predicts, hypothesized to stem from hard-coded patterns at T = 0. Understanding this could improve both the theory and the method.
• Going beyond the first output token. The analysis is restricted to the first output token because inter-token dependencies complicate it substantially; extending the theory to multi-token responses could improve sensitivity at no extra query cost.
• Pushing coverage past 78%. Three endpoints out of four are covered cheaply; raising the fraction, and characterizing which endpoints fundamentally resist BI discovery, remains open.

Target Audience

This paper suits ML researchers and engineers working on model monitoring, trustworthy ML, and API security; statisticians interested in hypothesis testing applications to foundation models; and platform or reliability engineers who need to verify that a third-party LLM endpoint has not silently changed. It is most useful to readers with some background in statistics or LLM inference, since the theory sections rely on Fisher information, LAN asymptotics, and Jacobian decompositions — although the B3IT scheme itself is straightforward enough that practitioners can implement it from the pseudocode alone.

Authors’ abstract

Remote change detection in LLMs is a difficult problem. Existing methods are either too expensive for deployment at scale, or require initial white-box access to model weights or grey-box access to log probabilities. We aim to achieve both low cost and strict black-box operation, observing only output tokens. Our approach hinges on specific inputs we call Border Inputs, for which there exists more than one output top token. From a statistical perspective, optimal change detection depends on the model's Jacobian and the Fisher information of the output distribution. Analyzing these quantities in low-temperature regimes shows that border inputs enable powerful change detection tests. Building on this insight, we propose the Black-Box Border Input Tracking (B3IT) scheme. Extensive in-vivo and in-vitro experiments show that border inputs are easily found for non-reasoning tested endpoints, and achieve performance on par with the best available grey-box approaches. B3IT reduces costs by $30\times$ compared to existing methods, while operating in a strict black-box setting.