Biological system process information despite noise-corrupted input, often operating at physical limits. A prime example is chemotaxis, i.e., active navigation of biological cells in spatial fields of chemical cues. Intriguingly, cells of different size use two different chemotaxis strategies, comparing concentrations in either space or time. Only heuristic arguments exist to explain this evolutionary choice. In this paper, an information theory of chemotaxis is presented, where an ideal agent combines both strategies and by this quantifies ‘chemotaxis in bits’. This enables us to predict when each strategy provides more information as function of a new powerlaw that combines agent size, motility noise and sensing noise. This theory is demonstrated via a bio-inspired search robot. JulianRode_2024