- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
A number of sequence processing primitives have been developed, such as self-attention and SSM layers. This paper studies the second-order sample complexity of these: each primitive is associated with a smooth operator that takes input sequences with an index set rather than discrete sequences. For each of these operators, matching sample complexity upper bounds and lower bounds are identified on Gevrey- classes, representing the required number of input locations that need to be sampled. The four operators studied are uniform (simple averaging), softmax attention, SSMs, and selective SSMs. For the longer-range operators of attention and uniform, these bounds depend on , the context length, while the shorter-range operators from SSMs do not. This forms a separation between these operators.
Critical strengths
Using second-order analysis, with representative operators for various language modeling components, is a clean way to analyze differences between these components. It provides a handful of matching lower and upper bounds for sample complexity, depending on the smoothness of the input. These separate SSMs from attention, showing that attention requires more samples, adding to the memory complexity and computational complexity of evaluating attention.
Critical weaknesses
Second-order complexity seems to rely on continuous forms of smoothness, which may not hold in practice. While the theory for continuous inputs is quite insightful, translating this to models with discrete inputs, such as those processing natural language, may be challenging. This is especially true as many operations that attention and SSMs are expected to do, such as associative recall and selective copying, are not smooth and require careful long-range dependencies. The results for discrete data bound the error based on the certificates rather than establishing similar sample complexity bounds.
Questions for authors
- Notation in general is understandable, but could there be a consolidated table of most notation at the start of the appendix? It would be a very useful reference when reading.
- Does the term "certificate" come from prior work? The work and abstract reference certificates before they are defined at the beginning of Section 4, making understanding difficult on the first few reads.
- Is there some connection that can be made to settings with smooth inputs, possibly relating to time-series or something similar? If there is, that would motivate using second-order complexity.
Response to Authors
Thank you for the detailed response. The attention results and Mamba experiment address some of my concerns. The signal example also illustrates the assumption but it is not still clear whether the derivative bounds in assumption are realistic for measured signals. My main concern is the lack of synthetic and real data experiments for directly testing the theoretical results. Also, the new results are only in the rebuttal and there is no revised version of the paper available. Therefore, I will keep my current rating.