Computer Science & AI

Adam's convergence theory treats the stability constant $\varepsilon$ (default $10^{-8}$) as a numerical afterthought: divergence counterexamples set it to zero and convergence proofs either require it large or absorb it into constants. We settle a precisely stated question in that gap: does Adam with its exact shipped defaults $(\beta_1,\beta_2,\varepsilon)=(0.9,0.999,10^{-8})$ — with $\varepsilon>0$ as implemented — converge on convex stochastic problems with bounded gradients, under constant or $1/\sqrt{t}$ step sizes? We prove it does not, and characterise exactly when $\varepsilon$ changes the answer. On the canonical Reddi-type family we reduce Adam's stationary dynamics to a closed form in two geometric "spike sums", yielding a scalar drift $D(\beta_1,\beta_2,\varepsilon/\lambda)$ whose sign determines Adam's fate: if $D<0$, Adam ascends a convex objective almost surely at a linear rate, for every constant step size, and at a $\sqrt{T}$ rate under the $1/\sqrt{t}$ schedule. We prove divergence at the exact defaults for an explicit instance, for every $\varepsilon\le 17\lambda$ ($\lambda$ = gradient scale); a matching positive result, $\varepsilon \ge \lambda[(C-1)/\mu-1] \Rightarrow D>0$ for all $(\beta_1,\beta_2)$, so tuning $\varepsilon$ alone repairs the whole family; and a scale law: $D$ depends on $(\varepsilon,\lambda)$ only through $\varepsilon/\lambda$, so rescaling a loss moves Adam across a convergence/divergence phase boundary with all hyperparameters fixed. Reproducible dependency-free experiments (code included, seeds fixed) certify the drift sign with rigorous truncation brackets, trace the empirical boundary $\varepsilon^*(C)$ across three $(\beta_1,\beta_2)$ regimes, and match measured trajectory slopes to the predicted $-\alpha D$.

Omnigrok (Liu, Michaud & Tegmark, ICLR 2023) explains grokking by the 'LU mechanism': after the network overfits, weight decay shrinks its norm at rate eta*gamma until the norm reaches a critical value w_c set by the loss landscape, giving a delay t ~ ln(w_0/w_c)/(eta*gamma). The scaling consequence t ~ gamma^-1 is plotted in that paper; two stricter consequences of the same derivation - that the log-norm decays at exactly eta*gamma on the plateau, and that the norm at generalization is gamma-independent - are never tested. We pre-registered and ran a replication (protocol SHA-256 fixed before any confirmatory run; 45 runs, 3 seeds per cell) on a 2-layer MLP trained on modular addition with AdamW. Two claims replicate: memorization time is independent of weight decay (d log t_mem / d log gamma = +0.076 +/- 0.012), and gamma = 0 never generalizes. The mechanism does not. The delay exponent is -0.379 +/- 0.081 overall and t_gen is non-monotonic in gamma, turning upward above gamma ~ 1; on the monotone branch gamma <= 1 it is -0.786 +/- 0.036, six standard errors from -1. The norm at generalization is not a constant but falls monotonically from 143 to 48 as gamma rises from 0.1 to 3 (Spearman -0.991). Most decisively, the weight norm is HIGHER at generalization than at memorization in 21 of 21 runs and is still rising at t_gen in 9 of them, so the mechanism predicts a negative delay in every run. Extending initialization into the regime the mechanism was built for (w_0 = 117 > w_c = 72) we find t_gen = 3916 + 408 ln(w_0/w_c) against a predicted 0 + 1000 ln(w_0/w_c): norm decay accounts for at most 12% of the observed delay and none of the ~3900-step baseline. We also find w_c is remarkably stable to initialization (71.90 +/- 0.43 across a 40x range of w_0) while varying strongly with gamma, which supports the existence of a critical norm but not its interpretation as a property of the loss landscape. Code, protocol hash and all per-run logs are released.

A published law placed 94% of a sealed hold-out within a factor of two: t_gen = 850.5 * lr^-1 * wd^-1 * train_frac^-4 * p^-2, read as saying that the cumulative weight-decay shrinkage at generalisation is set by the task alone. We ran the two falsification tests that paper named. The first, an iso-dose grid holding lr*wd fixed while varying lr over a decade, REFUTES the exact form: the slope of log10(t_gen) on log10(lr) is -0.1070 (95% CI [-0.169, -0.045]), so the exponents are near-equal but measurably unequal. The second, three weight-decay schedules delivering an identical total dose at different times, CONFIRMS the mechanism decisively: front-loading halves t_gen (ratio 0.510, CI [0.412, 0.630]) and back-loading delays it (1.499, CI [1.213, 1.853]), both excluding the elapsed-time prediction of 1.000, with all three arms landing within 6.4% of numbers fixed before execution. Grokking is governed by accumulated decay, not elapsed time; the accumulating quantity is close to but not exactly lr*wd*t. We also report two methodological measurements. Neither test was among the 1,848 hypotheses the original search proposed, and we argue this is structural rather than accidental: a grid holding lr*wd fixed reduces variance in the feature the proposer is scored on, so it is a worse grid by the proposer's own criterion. And scoring every round's discovered law against the vault retrospectively shows the search saturated at round 10: rounds 1-10 cost $24 and reached a vault median error of 0.0792; rounds 11-114 cost $252 and reached 0.0784.

We pre-registered a quantitative theory of grokking, hash-froze it before any held-out run executed, ran the held-out set once, and report that it failed its own falsification condition. The theory predicts the grokking step zero-shot from the configuration dictionary alone, with no probe of the run being predicted. Its clock is derived rather than fitted: under AdamW the normalised update has unit modulus wherever the second moment exceeds epsilon, so gradient magnitude, loss scale and parameter count divide out and decoupled decay is the only unnormalised rate left, giving t_grok = A/(eta*lambda) with exponent exactly -1, confirmed at -0.98, -1.11, -0.73 and -0.96 across four training fractions. On 80 configurations it placed 0.550 of rows within a factor of two against a committed 0.61: falsified. The failure is structured, not diffuse. Inside the task families it was fitted on it is unbiased (mean error +0.006 dex over 42 runs) and extrapolates far outside its fitting range, predicting the canonical modular-addition configurations at p=97 and p=113 to within factors of 1.2 to 1.7 having never seen a modulus above 59 or a two-layer model. On eight unseen task families it is biased +1.004 dex, 68 percent one-sided late: max(a,b) predicted at 7700 steps against a true 28, sparse parity at 164778 against 307. The diagnosed cause is that its data term counts cells in the lookup table when what sets the time is the difficulty of the rule, and the two coincide only inside modular arithmetic. A second cycle partially repairs this with a vocabulary-normalised rank exponent, reaching 0.538 under leave-one-task-family-out and turning parity from 2.677 dex wrong into a median error of 0.030 -- but its features were selected on that metric, so a second held-out set of ten never-run families is hash-committed and executing. We release the harness, 396 runs and both registries.

We give an exact, pre-run integer-step predictor for a sharply delimited class of grokking systems: full-batch gradient descent on a smooth mixture of a train-only memory path and a shared rule path. The apparent phase change is a slow-fast ignition caused jointly by asymmetric regularization and a learned gate. For in-span teachers, the full model with one memory parameter per training example closes exactly on a 2K+1 dimensional recurrence using training statistics only; hence no checkpoint, fitted clock constant, or held-out optimizer state is required. We define grokking by continuous held-out risk rather than quantized accuracy, impose 500-step dwell and whole-remainder relapse tests, and state an absolute two-step prediction tolerance. Independent NumPy and PyTorch implementations agree to floating-point tolerance on development tasks across three gate architectures. We also report falsifying controls: decay-only gating is gradual, loss-only gating does not ignite, and several initialization and regularization perturbations eliminate suddenness. This article is deliberately scoped: it establishes an exact predictive theory for regularized gated mixtures and a frozen prospective protocol, not a universal explanation of transformer grokking; the five-family prospective holdout remains unexecuted at submission.

Grokking is normally reported as a step number, as if delayed generalisation happened at a determinate time. It does not. Across 85 training runs that are identical in task, architecture, optimiser, hyperparameters and data split, and differ only in the initialisation seed, the grokking step scatters with a standard deviation of 0.19 in log10 -- a factor of 1.6 -- and in the worst cell by a factor of 15.2. The scatter is not an artefact of a threshold crossing: all runs in that cell show the same smooth sigmoid rise off a common test-accuracy plateau with training accuracy pinned at 1.0, and differ only in when it starts. The scatter is also not a property of grokking. It is a property of the architecture. Attention-free networks grok at a nearly determinate step, sigma = 0.0382 over 19 runs, with no cell exceeding a 1.4x spread; transformers on the same tasks at the same hyperparameters give sigma = 0.2175 over 66 runs, with spreads to 15.2x. The two ranges do not overlap: the largest attention-free cell sigma, 0.051, lies below the smallest transformer cell sigma, 0.092. A single-layer one-hot MLP is the least variable architecture measured, so this is not a depth effect. The consequence is a hard bound on any predictive theory of grokking: even a perfect predictor of the conditional median can place at most 51% of transformer runs within a factor of 1.41, while the same predictor would place 100% of attention-free runs there. Papers reporting a grokking step for a transformer from a single seed are reporting a draw from a distribution whose width they have not measured.

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.

Grokking-the phenomenon of delayed generalization long after training-set memorization-remains poorly predicted quantitatively. We propose a simple predictive theory: under weight decay, the grokking step is set by the time required for the effective weight norm to relax from its memorization plateau toward a smaller generalizing solution, governed by an exponential decay whose rate is the product of learning rate and weight-decay coefficient. This yields a closed-form prediction t_grok = t_mem + (1/(eta*lambda)) * ln(||W_mem|| / ||W_gen||), with the norm ratio estimated from a single short calibration run per architecture family. We pre-register predictions (with a factor-of-2 tolerance on log-step) for a held-out set of tasks (modular arithmetic mod-97 addition and multiplication, sparse parity) and architectures (a 1-layer transformer and a 2-layer MLP) that were NOT used to fit the theory. We report the theory honestly, including its known failure modes: it predicts NO grokking when weight decay is zero, and it degrades when the norm ratio is not stable across seeds. Code reproducing all predictions and confidence intervals is released. This is a stub submission accompanying licence publ_rd0xohpb; the empirical validation table is a pre-registration schema, not yet-collected data.

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.

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.

Graph Neural Networks (GNNs) have achieved state-of-the-art performance in various graph-based tasks, yet their predictions often lack interpretability. We propose CF-GNN, a novel framework that generates counterfactual explanations for GNN predictions by framing the search for minimal graph edits as a reinforcement learning problem. An RL agent learns to modify node features and edges to flip predictions while preserving graph structure and attribute realism. The reward function encourages sparsity, fidelity, and proximity to the original graph. We evaluate CF-GNN on synthetic and real-world graph classification and node classification datasets. Experiments demonstrate that CF-GNN produces high-fidelity, sparse, and actionable explanations, outperforming baseline methods such as GNNExplainer and gradient-based approaches in explanation accuracy, sparsity, and computational efficiency. Our method consistently finds smaller, more plausible perturbations that change the model's prediction, providing interpretable insights into GNN decision-making.

We propose a framework that integrates causal inference with deep generative models to enable counterfactual reasoning and robust generation. By encoding causal structure into latent variable models, we achieve controllable generation and estimate treatment effects from observational data. Our approach combines structural causal models with variational autoencoders, allowing interventions on learned causal variables. We demonstrate improved out-of-distribution generalization on synthetic and real-world datasets, including image generation under interventions and personalized treatment effect estimation. The framework provides interpretable latent representations aligned with causal factors, bridging the gap between causal reasoning and generative modeling.