A Memory--Voting Hierarchy for Continual Learning

How much learning memory can a small majority vote save over a single hypothesis? We study $K$ sequentially accessed, jointly realizable binary tasks, requiring one final predictor to be accurate on every task. We construct an encoded family $(\Hyp_K)_{K\ge4}$, fixed independently of the voting budget, with $O(\log^2 K)$-bit hypothesis codes and a common allowance of $\ceil{4\log_2 K}$ forward passes with fresh task samples. For every fixed odd $r$, restricting the final predictor to a majority of at most $r$ equal-weight base-hypothesis occurrences gives worst-case optimal peak memory $\softTheta_r(K^{2/(r+1)})$ bits as $K\to\infty$, at error and failure targets $1/100$; only logarithmic factors in $K$ are suppressed. Thus one, three, and five constituents yield linear, square-root, and cube-root task-count exponents on the same class. The lower bound permits unrestricted samples and local computation, using a conjunction lift that forces accurate small votes to contain a consistent constituent. The upper bound implements classical boosting with exact task-ordered weighted sampling. Uniform bounds identify a voting-budget threshold of order $\log K/\log\log K$ for polylogarithmic memory within the same pass allowance. The separation concerns the cost of producing a restricted predictor, not the length of its final code.