A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over 2-√2 Entails Exponential Queries or Linear Recourse

Consistent submodular maximization studies the tradeoff between solution quality and stability when elements arrive over time. For a monotone submodular objective, which models diminishing returns, an algorithm maintains a set of at most k available elements and changes only O(1) elements after each insertion. D"utting et al. [2025] established a tight 2/3 approximation with unrestricted computation and a polynomial-time 0.51 approximation. They left open at STOC 2025 whether efficient algorithms can match the offline 1-1/e guarantee. We resolve this problem by proving that the supremum approximation achievable with polynomially many value queries and worst-case constant recourse is [ β=2-√2≈0.5858<1-1/e. ] For every varepsilon>0, our randomized algorithm attains β-varepsilon with O(varepsilon-2) changes per insertion. Any fixed improvement requires exponentially many queries before one critical insertion or linear recourse of Omega(k) changes at that insertion, even with unlimited queries afterwards. This gap quantifies the cost of consistency: the current oracle hides which elements will be needed after an arrival. We also determine the exact curvature-dependent threshold 1-(√2-1)vartheta, attain 1-1/e-varepsilon for weighted coverage with O(varepsilon-1) recourse, and separate the existence of universal future-price certificates from their efficient computation. Our algorithm has a bounded-bit polynomial-time implementation for polynomial-bit rational oracle answers; the lower bound uses only logarithmic-bit rational answers.