We prove that for every odd $q\geq 3$, any $q$-query binary, possibly non-linear locally decodable code ($q$-LDC) $E:\{\pm 1\}^k \rightarrow \{\pm 1\}^n$ must satisfy $k \leq \tilde{O}(n^{1-2/q})$. For even $q$, this bound was established in a sequence of works (Katz and Trevisan (2000), Goldreich, Karloff, Schulman, and Trevisan (2002), and Kerenedis and de Wolf (2004)). For $q=3$, the above bound was achieved in a recent work of Alrabiah, Guruswami, Kothari, and Manohar (2023) using an argument that crucially exploits known exponential lower bounds for $2$-LDCs. Their strategy hits an inherent bottleneck for $q \geq 5$.

Our key insight is identifying a general sufficient condition on the hypergraph of local decoding sets called $t$-\emph{approximate strong regularity}. This condition demands that 1) the number of hyperedges containing any given subset of vertices of size $t$ (i.e., its \emph{co-degree}) be equal to the same but arbitrary value $d_t$ up to a multiplicative constant slack, and 2) all other co-degrees be upper-bounded \emph{relative} to $d_t$. This condition significantly generalizes related proposals in related prior works that demand \emph{absolute} upper bounds on all co-degrees.

We give an argument based on spectral bounds on \emph{Kikuchi Matrices} that lower bounds the blocklength of any LDC whose local decoding sets satisfy $t$-approximate strong regularity for any $t \leq q$. Crucially, unlike prior works, our argument works despite having no non-trivial absolute upper bound on the co-degrees of any set of vertices. To apply our argument to arbitrary $q$-LDCs, we give a new, greedy, approximate strong regularity decomposition that shows that arbitrary, dense enough hypergraphs can be partitioned (up to a small error) into approximately strongly regular pieces satisfying the required relative bounds on the co-degrees.