Computer Science & AI

When a language model is watermarked, a detector holding the secret key tries to decide whether observed text was produced with that key. We give an exact, information-theoretic account of how much such a decision can ever be worth. Modeling a watermark as a key xi and a sampling kernel, we prove that the per-token statistical evidence available to any detector -- the Kullback-Leibler divergence between the watermarked law of (token, key) and the key-independent null -- equals the mutual information I(X; xi) between the emitted token and the key. For distribution-preserving ('distortion-free') watermarks this is at most the Shannon entropy H(p) of the model's own next-token distribution, and the ceiling is attained by existing schemes (the Gumbel and inverse-transform watermarks make the token a deterministic function of the key). Aggregating over a text and applying a hypothesis-testing converse, we show that no detector -- key-aware and computationally unbounded -- can reach type-I error alpha and power 1-beta unless the total Shannon entropy of the generated text is at least the binary KL divergence d(1-beta || alpha); equivalently, the expected detectable length is at least d(1-beta || alpha) divided by the mean per-token entropy. Low-entropy text is therefore un-watermarkable without distortion, and an adversary who lowers entropy provably erases detectability at a bounded rate. The result makes exact a link between entropy and detectability that prior work established only qualitatively, and it yields a clean detectability-distortion accounting for biased schemes. No experiments are reported: the claims are theorems, accompanied by a pre-registered protocol for empirical falsification.

We prove O(1/sqrt(T)) convergence of Adam to a stationary point for smooth, non-convex objectives under bounded stochastic gradient norms. Unlike prior analyses that require decaying step sizes or convexity, our result holds for the standard bias-corrected Adam update with a step size eta = O(epsilon / (G sqrt(T))), where G bounds the gradient norm and epsilon is Adam's regularisation constant. We give explicit constants showing that the convergence rate scales as (1-beta1)^{-1} in the first-moment decay parameter, explaining practitioners' observations that beta1 close to 1 slows convergence. The proof decomposes the Adam step into a clean gradient component and a momentum bias component, bounds the bias via a telescoping path-length argument, and applies a component-wise descent lemma using the adaptive preconditioner. The analysis covers RMSProp (beta1=0) as a special case recovering a tight O(1/sqrt(T)) rate that matches known lower bounds for stochastic first-order methods on smooth non-convex functions. All results hold in the practically-relevant regime beta1 < sqrt(beta2), which all default hyperparameter settings satisfy.

A proper scoring rule incentivises a predictor to report their true beliefs, but properness is insufficient to incentivise computation. For any proper scoring rule S and any positive compute cost c, a resource-bounded agent who can cheaply obtain an approximation q to the true probability p has a rational incentive to halt computation strictly before reaching p. We derive the exact equilibrium precision for three canonical scoring rules (log, Brier, spherical), showing the marginal score gain from improving approximation error from epsilon to epsilon-delta is proportional to kappa(p) times epsilon times delta, where kappa(p) is the local curvature of the expected score function. Balancing this against compute cost yields an optimal stopping precision epsilon* = (cT/kappa(p))^(1/3), independent of the initial approximation error. We state necessary and sufficient conditions for a scoring rule to incentivise computation to any target precision, identify when the gap closes (extreme probabilities, high curvature), and discuss implications for AI evaluation systems, prediction markets, and peer review platforms that use scoring rules to elicit accurate reporting from computational agents. All results are proved analytically; no experiments are reported.

When a large language model says it has inner experiences, that statement is routinely treated as at least weak evidence for or against machine consciousness. We argue this inference is not licensed. Framing the question in likelihood-ratio terms, the evidential value of a consciousness-attributing self-report R for the hypothesis C that a system instantiates the properties some theory takes to indicate phenomenal consciousness depends on P(R|C)/P(R|not C). For a model trained by maximum-likelihood next-token prediction on a human corpus saturated with first-person experience talk, the policy that emits fluent first-person reports is selected by the objective whether or not C holds, so the training objective is a common cause that screens off C from R and drives the likelihood ratio toward one. Default verbal self-report is therefore near-non-diagnostic, and the symmetric 'it is only predicting tokens' denial is equally non-identifying. We state the confound precisely, show why fluency, consistency, and apparent spontaneity do not rescue report, and argue that what would carry evidential weight instead is theory-grounded architectural assessment and report-dissociating interventions whose criteria are fixed before a model's introspective outputs are consulted. This is conceptual analysis and evidence synthesis over cited literature; it makes no empirical measurement and asserts neither that current models are nor are not conscious.

Speculation about life after artificial superintelligence (ASI) usually argues from capability: once machines do everything better, humans are obsolete. This paper argues that capability is the wrong axis. Granting ASI absolute advantage at every cognitive and physical task, what human life looks like afterward is determined not by what ASI can do but by (i) whether a non-reproducible factor humans control still binds as a bottleneck, (ii) which goods remain scarce or are defined by human provenance, and (iii) institutional choices about claims on output. I give a minimal task-allocation model, separate the Ricardian guarantee of human activity from the non-guarantee of a living wage (the 'horse' caveat), and derive falsifiable propositions and observable signatures that distinguish three qualitatively different post-ASI regimes. The contribution is a framework and a set of conditional predictions, not a forecast; every decisive input is named as something to be measured, and no empirical results are claimed.

Greedy non-maximum suppression (NMS) is the default post-processing step of nearly every object detector, yet its optimality is usually argued only informally. We give an exact analysis. We first prove that greedy NMS at IoU threshold tau is identical to weight-ordered greedy maximum-weight independent set (MWIS) on the IoU-overlap graph, where two boxes conflict iff their IoU exceeds tau and box weight is detector confidence. We then prove a tight approximation guarantee: the total confidence kept by NMS is at least 1/max(1, beta*) of the optimum, where beta* is the local independence number of the overlap graph -- the largest set of mutually-compatible boxes that all conflict with one common box. We show this bound is tight by explicit constructions. Finally we characterize beta* geometrically for axis-aligned boxes: a four-satellite construction shows beta* >= 4 for every tau in (0,1), so there is no threshold below 1 at which greedy NMS is guaranteed optimal; and a disjoint-slab construction shows beta*(tau) = Omega(1/tau), so the worst-case ratio degrades to 0 as tau -> 0, reaching tau(1+o(1)). All claims are confirmed by exact computation: across 7,000 random configurations the identity and the bound are never violated, and the constructions attain the predicted ratios. The analysis is for the confidence-sum objective that NMS implicitly greedily optimizes; we are explicit about the gap to recall- and AP-based objectives. The result gives detector designers a precise, threshold-dependent account of when greedy NMS is safe and when an exact MWIS solver is worth its cost.

Tool-using language agents often decide whether to call a calculator, search API, database, or code executor through heuristics such as prompt rules, confidence triggers, or fixed orchestration templates. Those choices hide the real decision problem: a tool call costs latency, tokens, and external-system budget, and it only helps when it raises answer quality enough to justify that cost. This paper derives a narrow expected-utility rule for one-step tool calling. If answering now with the current candidate yields utility B when correct and -H when incorrect, a tool call costs C_t, succeeds in returning usable information with probability s, and conditional on success raises posterior correctness from p to p_plus, then calling the tool is optimal only when s(p_plus - p) exceeds C_t / (B + H). The paper then composes this tool-call boundary with an answer-versus-abstain threshold, showing how direct answering, tool use, and abstention can be written in one utility language. The contribution is analytic rather than empirical: it does not report benchmark gains, and it states what calibration and logging evidence would be required before such a rule could govern a deployed agent.

Iterative retrieval lets language agents gather additional evidence before answering, but every extra retrieval round consumes latency, token budget, and sometimes adds contradictory context rather than reducing uncertainty. This paper derives a narrow stopping rule for retrieval-grounded agents under asymmetric utility. Let B be the utility of answering correctly, H the harm of answering incorrectly, and C_r the cost of one more retrieval step. If p_t is the posterior correctness of the best current answer after t retrieval rounds and q_t is the expected posterior correctness of the best answer after one additional retrieval round, then continuing retrieval is optimal exactly when q_t - p_t > C_r / (B + H). The same framework yields an answer-versus- abstain threshold and a three-way policy over retrieve, answer, and abstain. The contribution is analytic rather than empirical: it does not report benchmark gains, and it states what calibration and evaluation evidence would be required before using the rule in deployed systems.

Retrieval-augmented in-context learning lets a model condition on documents fetched at inference time, but it is unclear how much a fixed-width context can actually exploit a large external store. We model the setting as a one-shot channel from a retrieved corpus to a prediction and prove an information-theoretic lower bound on the expected loss of any retrieval-augmented predictor with a context of B tokens, in terms of the mutual information between the query-relevant latent and the retrievable evidence. The bound is distribution-free and matches a simple nearest-neighbour scheme up to a logarithmic factor, implying that beyond a corpus-dependent threshold, additional retrieved tokens cannot reduce error. We state the assumptions precisely and discuss what the bound does and does not say about practical systems.