The Randomized Learning-Augmented Linear-Search Frontier and Sharp Local Error Limits

We characterize the complete robustness-consistency frontier for randomized linear search, proving optimality of the existing construction of Lee, Lee, Lee, Shin, and Yun. At exact frontier budgets, we establish low-robustness rigidity of the entire expected prediction-error curve for bi-infinite strategies, with pointwise asymptotic transfer to ordinary algorithms whose guarantees hold uniformly over predictions. We also determine a sharp, unattained local underprediction infimum in the high-robustness range. Explicit profile interpolations approach the infimum, while strict-record atom bounds and integral convergence prove nonattainment, including for ordinary uniform-prediction envelopes. Hence no pointwise-best exact-frontier error envelope exists in the high-robustness range. Full proofs specify the known minimum target distance, uniformity over unbounded prediction magnitudes, and the order of all limits. The finite-error pointwise infimum and tradeoffs permitting consistency slack are not characterized. This version extends the frontier result with the error-limit theorems and includes an AI assistance disclosure.