Na frase «Ele levantou-se o mais cedo possível.», o não é classificável isoladamente, pois faz parte de uma locução adverbial¹. Sendo uma locução adverbial, fica invariável, como invariável ficaria qualquer advérbio empregado nessa frase: «Ele levantou-se muito cedo». 

Na Nova Gramática do Português Contemporâneo, de Celso Cunha e Lindley Cintra, lê-se nas pp. 544-547, sobre a gradação dos advérbios, que estes podem apresentar outras formas de superlativo: «o superlativo intensivo, denotador de limites da possibilidade, forma-se antepondo o mais ou o menos ao advérbio e pospondo-lhe a palavra possível ou uma expressão (ou oração) de sentido equivalente:

 Escreveram entretanto a D. Madalena, pedindo-lhe que os tirasse daquele purgatório o mais cedo possível. (Rebelo da Silva, Contos e Lendas)» 

¹«As locuções adverbiais são expressões com valor adverbial constituídas por mais do que uma palavra», in O advérbio em Português Europeu, João Costa, Edições Colibri, 2008