To implement challenge-response in ROM only (no computations), you basically need a lookup table, a mapping from challenges to responses. So for a $k$ bit challenge, you would need $2^k$ entries in your lookup table.
How would this work on a PUF?
Consider the following PUF example (taken from Improved Ring Oscillator PUF: An FPGA-friendly Secure
Primitive, Journal of Cryptology, 2011):
The portion on the right shows the ring oscillator (RO), whose value is going to be entirely dependent on the fabrication process and therefore is "unclonable". You put a bunch of these ROs together, feeding into two MUXs, with the challenge determining which RO value to select. Finally, the outputs of the two MUXs are used to increment two counters, which are (after some short period of time) used to determine a single bit by doing a comparison. Your $k$ bit challenge may be divided up into smaller challenges to get a larger response from the PUF than a single bit. This would be a deterministic process so that given the same $k$ bit challenge, you would get the same response (in practice there is some probability of bits being flipped in the response, so typically some error correcting is done).
To get a secure $k$ bit response, you will need some number of ROs, but you won't need an exponential number of ROs. If you have $N$ ROs, there are $N(N-1)/2$ distinct pairs of ROs. Each pairing can be used to generate a single bit using the setup shown above. However, as noted in Physical Unclonable Functions for Device Authentication
and Secret Key Generation, the entropy of the circuit will not be as high as that. In that paper, the authors derive the maximum entropy of the circuit as $\log_2(N!)$. So for a desired $k$, you could compute $N$. As an alternative method, the authors note that for simplicity, you could design the system such that each oscillator is used only once for any challenge value. If you did this, you would need $2k$ oscillators to generate a $k$ bit response. I would note that due to error correcting, you may need additional bits, but this should only increase the number of oscillators by a constant factor.
Now, how would this be used in a challenge/response protocol. Well, first there must be a trusted setup. The challenger, in a clean environment, sends a bunch of challenges to the PUF and records the responses. So, the challenger may have to store a lot of challenge/response pairs depending on the application. The point is, the hardware does not have to store all that information.
Then, when the system is fielded, the challenger sends a challenge to the device. The device runs it through the PUF and returns the response. Someone without access to the PUF could not compute the correct response. Further, someone trying to clone the PUF would not succeed because of the manufacturing variations in the ROs. Those manufacturing variations, even when very subtle, would be enough that the responses would not be the same.