The pasuk requires one to say birchas ha'mazon (see Ohr sameiach who questions whether m'doraysa one needs to make all 3 brachos or perhaps just give some type of bracha to hashem for the food) after meeting the requirements of ואכלת ושבעת וברכת. The gemara 20b refers to a kezayis as a shiur d'rabonon because the torah doesn't require you to bentch until you eat a shiur of se'viah.
Rav Moshe (Igros Moshe O.C. 1:76) cites a pri megadim who says that a person who eats enough to fill himself up, but does so by spreading the eating over time so that he never ate a kezayis within a shiur of כדי אכילת פרס would still need to bentch. Essentially, he meets the requirement of שביעה but never met the requirement of אכילה, yet the pri megadim says that he is required to bentch m'doraysa. Rav Moshe disagrees and says that achila is also a d'oraysa condition and without an achila, one is not required to bentch on seviah alone. His proof is from a sick person who is satisfied after eating a half kezayis, and the halacha is that he doesn't bentch. He further proves this from a Radvaz cited by the Sha'arei Teshuva 197:8 who says that a sick or elderly person who eats a kezayis and is satisfied can make birchas hamazon to be motzi those who are chayev m'doraysa. The implication is that because they ate a kezayis they can be motzi others, but if they wouldn't have eaten a kezayis, they can't even bentch themselves. Therefore, Rav Moshe concludes that one must be careful to at least eat one kezayis within a כדי אכילת פרס in order to be chayev to bentch. If one has a safeik, he leans toward saying they shouldn't bentch and this doesn't qualify as a safeik d'oraysa l'chumra because he thinks that the halacha is not like the pri megadim.
Rashi on our daf seems to support Rav Moshe's approach. The gemara says that by removing the pit from the olive the shiur is reduced. Rashi comments that by birchas ha'peiros the Torah says אכילה, which means a kezayis. Rashi seems to be following the approach of Rabbeinu Yona at the beginning of the perek (24b and 25a on bottom) that the bracha achrona on 7 species of E.Y. is d'oraysa. But aside from that he seems to say clearly that the Torah insists on an achila as a condition for bracha achrona. If the only d'oraysa requirement were שביעה, rashi shouldn't be citing a pasuk and interpreting it as requiring a kezayis. Therefore, the Torah requires 2 conditions for Birchas HaMazon, אכילה which requires a kezayis within k'dei achilas pras and שביעה.