When did blade fuller appear?

It seems that Roman spathas sometimes already had fullers:

But as this form was an adaption of a Celtic design of the La Tène culture:

Typical for swords from the Late Latène period are a large blade length as well as straight stitching bars and v***nal mouths. Bell-shaped sheath mouths still occur in the Late Latène period. The cross section of the blade changes from the flat lens shape common in the mid-Latène period to a more pronounced profiled cross section with partly very distinct concave grooves/fullers.
_{–– Lisa Deutscher: "Latènezeitliche Schwerter mit Stempelmarken", Jahrbuch des Römisch-Germanischen Zentralmuseums 59, 2012.}

Similarly the ancient Greek sica features:

The second type, not very different morphologically speaking, does not have the solid shape of the first type, but a longer blade, with a fuller, and keeps, most often, the haft's tongue short and of a triangular shape.

The third type, more numerous, gathers a series of daggers characterized by a long blade, elegantly manufactured in most cases, by the ornamentation with incised circles and/or lines along the blade, the presence of the fuller, the haft’s tongue as long as the haft and a guard muff. These distinctive elements are found either all together, or some of the pieces present one or more of these characteristic features. The sizes show a relative standardization, somewhere around 30–40 cm length and approximately 3 cm width. From a chronological point of view, this type of dagger is dated mostly in the 2nd and 1st centuries BC.

But when did it first appear? Very early it seems, out of necessity:

The first form (fig. 1 18) is the wedge that would be produced by taking for base the dorsal thickness of an ordinary blade, and by continuing it in an even line to the apex of the triangle – the point. The two sides meet at an angle of nine degrees; consequently the edge lacks the thickness, weight, and strength necessary for every cutting tool. For soft substances it should range from ten to twenty degrees, as in the common dinner knife. An angle of twenty-five to thirty-five degrees, being the best for wood-working, is found in the carpenter's plane and chisel. For cutting bone the obtuseness rises to forty degrees, and even to ninety ; the latter being the fittest for shearing metals, and the former for Sword-blades, which must expect to meet with hard substances. But even an angle of forty degrees will be ineffectual upon a thick head, unless the cut be absolutely true. No. 2 illustrates the angle of resistance (forty degrees) and the entering angle (ninety degrees). No. 3 shows that the true wedge of forty degrees is too thick and heavy for use, requiring some contrivance for lightening the blade, while preserving the necessary angle of resistance. The remaining sections display the principal modes of effecting this object. In Nos. 4 and 6 the angle is carried in a curved and bulging line, thus giving the section a bi-convex form. When the back or base is flat this is the Persian and Khordsdni, vulgarly called the * Damascus blade.* When baseless and two-edged it is the old * Toledo ' rapier — two shallow-crowned arches meeting (3^, fig. 1 24). In both cases the weapon is strong, but somewhat overweighted. In the next shapes (Nos. S and 7), the two sides are cut away to a flat surface and represent the *Talwdr' of India. When this flat surface is hollowed, as by the black lines of No. S (compare No. 8), we have the bi-concave section, as opposed to the bi-convex. This hollowing of the wedge into two broad grooves from the angle of resistance is one of the forms assumed by the English 'regulation' Sword: it was considered the lightest for a given breadth and thickness, but it is by no means the strongest, and there are sundry technical objections to it.

The remaining blades in the illustration are grooved in as many different ways.

The function of the cannelure is to obviate over-flexibility; it also takes from the weight and adds to the strength. By channelling either side of a thin or * whippy * blade it becomes stiffer, because any force applied to bend such a blade sideways meets with the greatest amount of resistance that form can supply. Mechanically speaking, it is to crush an arch inwards upon its crown, and the deeper the arch the greater the resistance. Hence the narrow groove is preferable to a broader channel of the same depth. No. 9, hollowed on each side near the base, is a good old form, superior to the * regulation * (No. 8): its weak point, the space between the grooves where the metal is thinnest, lies in the best place – near the back, where strength and thickness are least required. No. 10, though somewhat lighter, doubles its weak points. No. 11 is better in this respect: it has three grooves which are far shallower, and consequently the metal between them is thicker. The same remark applies to Nos. 12 and 13, which are sections of claymores, single- and treble-grooved.
_{–– Richard Francis Burton :"The Book of the Sword", London: Chatto and Windus, 1884. (archive.org)}

That means old Greek kopis can be found to have them:

^{Greek kopis, 5th–4th centuries BC, iron, Metropolitan Museum of Art.}

With this in mind, the earliest metal blades with some kind of fuller are found in ancient Egypt. And I say "metal blades" on purpose, as the concept is even older than Egypt's metal working tradition:

_{–– Archaeologist explains innovation of 'fluting' ancient stone weaponry}

_{–– Aurignacian blades personal scan from ''Manuel d'archéologie préhistorique, celtique et gallo-romaine'}

As for other types of metal swords in other cultures, also confer to Uni Kiel AMAT: Iron, Steel and Swords which is more materialistic and modern presentation than Burton.