Kernel-Prompted Random Transformer

1. Integration point: implement a frozen one-layer attention module with randomly sampled Gaussian query, key, value, and output matrices. Reserve N prompt slots followed by one query slot. Encode each support example (x_i,y_i) into a prompt token, exposing enough hidden coordinates to control its key and value. Encode the query as [x^T,1,0,...,0]. Read the output at the query position and decode it as the prediction.

2. Pseudocode:

sample frozen Q,K,V,O ~ Normal(0, 1/d_h)
choose support set {(x_i,y_i)} and bandwidth sigma
for each support i:
    construct target coefficients c_i from
        b_i(x)=-(||x||^2 - 2*x^T*x_i + ||x_i||^2)/(2*sigma^2)
    probe the frozen logit ell_i(x; z) on d_in+2 basis query embeddings
    construct M mapping free prompt coordinates z to logit coefficients
    z_i = solve_ridge(M, c_i, lambda)
    write z_i into prompt token p_i
    choose remaining value coordinates so V(p_i) decodes to y_i
for query x:
    run frozen attention on [p_1,...,p_N,E(x)]
    return decoded query-position output

3. Compute M analytically from the frozen linear query/key maps when possible; otherwise estimate it with finite differences around a zero prompt. Use SVD to measure rank and condition number. If the smallest singular value is small, use the ridge solution above and record the residual ||Mz_i-c_i||_2. Estimate sigma using validation data or sigma equal to a multiple of the median pairwise support distance. The paper provides the full-rank/almost-sure-randomness rationale, but the implementation must empirically measure prompt norm, logit residual, attention-weight error relative to the Gaussian kernel, and final prediction error. If key and value coordinates are coupled, solve one joint least-squares system that matches both logit coefficients and the decoded labels.

4. First experiment: compare analytical prompting against gradient-optimized soft prompts, a frozen random transformer without prompting, k-nearest neighbors, and direct Nadaraya-Watson regression. Start with a two-dimensional synthetic Holder function and 32, 64, 128, and 256 support tokens; then test MNIST or CIFAR-10 embeddings. Sweep hidden dimension, bandwidth, ridge coefficient, and prompt length. Measure adaptation time, inference latency, prompt memory, test MSE or accuracy, logit residual, and prompt norm. Success means reaching kernel-regression accuracy with no backpropagation during adaptation, lower adaptation cost than prompt tuning, and decreasing error as prompt length and hidden dimension increase.